Matrix-Based Genetic Algorithm for Computing the Minimum Volume Ellipsoid

摘要

The minimum volume ellipsoid (MVE) is a useful tool in multivariate statistics and data mining. It is used for computing robust multivariate outlier diagnostics and for calculating robust covariance matrix estimates. Various search algorithms for finding or approximating the MVE have been developed, but due to the combinatorial nature of the problem, exact computation of the MVE is impractical for all but the smallest datasets. Since large datasets are increasingly common, alternative algorithms are desired. Even among small datasets, performance of the existing algorithms varies considerably—no single algorithm dominates in performance. This paper presents a unique matrix-structured genetic algorithm (GA) that directly searches the ellipsoid space for the MVE. By directly searching the space of ellipsoids, the impact of the combinatorial nature of the problem is minimized. The matrix-structured GA is described in detail, and evidence is provided to illustrate the performance of the new algorithm in detecting multivariate outliers.