Computing LTS Regression for Large Data Sets |
| |
Authors: | PETER J ROUSSEEUW KATRIEN VAN DRIESSEN |
| |
Affiliation: | (1) Department of Mathematics and Computer Science, Universiteit Antwerpen, Middelheimlaan 1, B-2020 Antwerpen, Belgium;(2) Faculty of Applied Economics, Universiteit Antwerpen, Prinsstraat 13, B-2000 Antwerpen, Belgium |
| |
Abstract: | Data mining aims to extract previously unknown patterns or substructures from large databases. In statistics, this is what
methods of robust estimation and outlier detection were constructed for, see e.g. Rousseeuw and Leroy (1987). Here we will focus on least trimmed squares (LTS) regression, which is based on the subset of h cases (out of n) whose least squares fit possesses the smallest sum of squared residuals. The coverage h may be set between n/2 and n. The computation time of existing LTS algorithms grows too much with the size of the data set, precluding their use for data
mining. In this paper we develop a new algorithm called FAST-LTS. The basic ideas are an inequality involving order statistics
and sums of squared residuals, and techniques which we call ‘selective iteration’ and ‘nested extensions’. We also use an
intercept adjustment technique to improve the precision. For small data sets FAST-LTS typically finds the exact LTS, whereas
for larger data sets it gives more accurate results than existing algorithms for LTS and is faster by orders of magnitude.
This allows us to apply FAST-LTS to large databases. |
| |
Keywords: | breakdown value linear model outlier detection regression robust estimation |
本文献已被 SpringerLink 等数据库收录! |
|