Covariance Matrix Analysis for Outlier Detection

In this paper we introduce COV, a novel information retrieval
and data mining algorithm that uses vector space modeling
and spectral analysis of the document vector covariance matrix to
map the retrieval/mining problem into a lower dimensional space. Since
the dimension of the covariance matrix depends on that of the
attribute space and is independent of the number of documents, COV
can be applied to databases that are too massive to be processed by
methods based on the singular value decomposition (SVD) of the
document-attribute matrix, such as latent semantic indexing
(LSI). In addition to improved scalability, COV selects basis vectors
for the lower dimensional space and shifts the origin so that subtle
differences in document
vectors can be more readily detected than LSI. We demonstrate the
significance of this feature of COV through an important application
in data mining, known as outlier cluster detection. We propose two
new algorithms for detecting major and outlier clusters in databases
-- the first is based on LSI, the second on COV -- and show through
implementation studies that our algorithm based on COV outperforms
the one based on LSI.