Scalable robust covariance and correlation estimates for data mining

ABSTRACT

Covariance and correlation estimates have important applications in data mining. In the presence of outliers, classical estimates of covariance and correlation matrices are not reliable. A small fraction of outliers, in some cases even a single outlier, can distort the classical covariance and correlation estimates making them virtually useless. That is, correlations for the vast majority of the data can be very erroneously reported; principal components transformations can be misleading; and multidimensional outlier detection via Mahalanobis distances can fail to detect outliers. There is plenty of statistical literature on robust covariance and correlation matrix estimates with an emphasis on affine-equivariant estimators that possess high breakdown points and small worst case biases. All such estimators have unacceptable exponential complexity in the number of variables and quadratic complexity in the number of observations. In this paper we focus on several variants of robust covariance and correlation matrix estimates with quadratic complexity in the number of variables and linear complexity in the number of observations. These estimators are based on several forms of pairwise robust covariance and correlation estimates. The estimators studied include two fast estimators based on coordinate-wise robust transformations embedded in an overall procedure recently proposed by [14]. We show that the estimators have attractive robustness properties, and give an example that uses one of the estimators in the new Insightful Miner data mining product.

REFERENCES

• 1: M. B. Abdullah. On a Robust Correlation Coefficient. In The Statistician, 39, pp. 455--460, 1990.
• 2: P. Davies. Asymptotic Behavior of S-Estimates of Multivariate Location Parameters and Dispersion Matrices. In The Annals of Statistics, 15, pp. 1269--1292, 1987.
• 3: S. J. Devlin, R. Gnanadesikan and J. R. Kettenring. Robust Estimation of Dispersion Matrices and Principal Components. In Journal of the American Statistical Association, 76, pp. 354--362, 1981.
• 4: D. L. Donoho. Breakdown Properties of Multivariate Location Estimators. Ph.D. Qualifying Paper. Dept. of Statistic, Harvard University, 1982.
• 5: R. Gnanadesikan and J. R. Kettenring. Robust Estimates, Residuals, and Outlier Detection with Multiresponse Data. In Biometrics, 28, pp. 81--124, 1972.
• 6: F. Hampel, P. Ronchetti, P. Rousseeuw and W. Stahel. Robust Statistics: The Approach Based on Influence Functions. John Wiley & Sons, 1986.
• 7: P. J. Huber. Robust Statistics. John Wiley & Sons, 1981.
• 8: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Random sampling techniques for space efficient online computation of order statistics of large datasets, ACM SIGMOD Record, v.28 n.2, p.251-262, June 1999
• 9: A. Marazzi and C. Ruffieux. Implementing M-Estimators of the Gamma Distribution, in Robust Statistics. :Data Analysis and Computer Intensive Methods, in Honor of Peter J. Huber's 60th Birthday, Springer Verlag, 1996.
• 10: R. Maronna. Personal Communication. In International Conference on Robust Statistics, 2002.
• 11: R. Maronna. Robust M-Estimators of Multivariate Location and Scatter. In The Annals of Statistics, 4, pp. 51--67, 1976.
• 12: Ricardo A. Maronna , Werner A. Stahel , Victor J. Yohai, Bias-robust estimators of multivariate scatter based on projections, Journal of Multivariate Analysis, v.42 n.1, p.141-161, July 1992 [doi>10.1016/0047-259X(92)90084-S]
• 13: R. Maronna and V. Yohai. The Behaviour of the Stahel-Donoho Robust Multivariate Estimator. In Journal of the American Statistical Association, 90 (429), pp. 330--341, 1995.
• 14: R. Maronna and R. Zamar. Robust Estimates of Location and Dispersion for High Dimensional Data Sets. In Technometrics, to appear, 2002.
• 15: D.M. Rocke and D.L. Woodruff. Identification of Outliers in Multivariate Data. In Journal of the American Statistical Association, 91 (435), pp. 1047--1061, 1996.
• 16: P. Rousseeuw. Least Median of Squares Regression. In Journal of the American Statistical Association, 79, pp. 871--880, 1984.
• 17: P. Rousseeuw. Multivariate Estimation with High Breakdown Point. Mathematical Statistics and Applications, pp. 283--297, Reidel Publishing, 1985.
• 18: Peter J. Rousseeuw , Katrien Van Driessen, A fast algorithm for the minimum covariance determinant estimator, Technometrics, v.41 n.3, p.212-223, Aug. 1999 [doi>10.2307/1270566]
• 19: P. J. Rousseeuw , A. M. Leroy, Robust regression and outlier detection, John Wiley & Sons, Inc., New York, NY, 1987
• 20: W. A. Stahel. Breakdown of Covariance Estimators. Research report, 31, Fachgruppe fur Statistik, ETH, Zurich, 1981.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Statistical methods

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Performance, Reliability

Keywords:
data mining, outliers, robust estimators, robust statistics, scalable algorithm