High-Dimensional Data Mining: Subspace Clustering, Outlier Detection and applications to classification

by Andrew Foss

Data mining in high dimensionality typically faces the consequences of increasing sparsity and declining differentiation between points, while sparsity tends to increase false negatives. Here, the problem of solving high-dimensional problems using low-dimensional solutions is addressed. In clustering, we provide a new framework for finding candidate subspaces and the clusters within them using only two-dimensional clustering. It is robust to noise and handles overlapping clusters. In the field of outlier detection, several novel algorithms suited to high-dimensional data are presented.m These outperform state-of-the-art outlier detection algorithms in ranking outlierness for many datasets regardless of whether they contain rare classes or not. This approach can be a powerful means of classification for heavily overlapping classes given sufficiently high dimensionality. This is achieved solely due to the differences in variance among the classes. On some difficult datasets, this unsupervised approach yielded better separation than the very best supervised classifiers. This opens a new field in data mining, classification through differences in variance rather than spatial location.

152 pages, Paperback

Published August 4, 2011