Finding generalized projected clusters in high dimensional spaces

By Charu C. Aggarwal, Philip S. Yu. ACM SIGMOD Conference, 2000

693 citations recorded by the source corpus.

High dimensional data has always been a challenge for clustering algorithms because of the inherent sparsity of the points. Recent research results indicate that in high dimensional data, even the concept of proximity or clustering may not be meaningful. We discuss very general techniques for projected clustering which are able to construct clusters in arbitrarily aligned subspaces of lower dimensionality. The subspaces are specific to the clusters themselves. This definition is substantially more general and realistic than currently available techniques which limit the method to only projections from the original set of attributes. The generalized projected clustering technique may also be viewed as a way of trying to redefine clustering for high dimensional applications by searching for hidden subspaces with clusters which are created by inter-attribute correlations. We provide a new concept of using extended cluster feature vectors in order to make the algorithm scalable for very large databases. The running time and space requirements of the algorithm are adjustable, and are likely ta tradeoff with better accuracy.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/73b5b8419c038e77b80d4781c189777ac17d047a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Feature bagging for outlier detection (2005, methodology): “In addition, a few clustering-based techniques have also been used to detect outliers either as side products of the clustering algorithms (points that do not belong to clusters) [2, 31] or as clusters that are significantly smaller than others [13].”
An Evaluation on Feature Selection for Text Clustering (2003, background): “The performance of clustering algorithms will decline dramatically due to the problems of high dimensionality and data sparseness ( Aggrawal &Yu, 2000 ).”
A Survey of Clustering Data Mining Techniques (2006, methodology): “is used in algorithms as ORCLUS [4] that do not make this assumption.”
Clustering by pattern similarity in large data sets (2002, methodology): “Recent research work [4, 2, 3, 12, 6, 15] has focused on discovering clusters embedded in the subspaces of a high dimensional data set.”
Automatic Subspace Clustering of High Dimensional Data (2005, methodology): “ORCLUS ( Aggarwal and Yu , 2000 ) modifies the PROCLUS algorithm by adding a merging process of clusters , and selecting for each cluster principal components instead of attributes .”
What Is the Nearest Neighbor in High Dimensional Spaces? (2000, background): “Note that the projected nearest neighbor problem is closely related to the problem of projected clustering [1, 2] which determines clusters in the database by examining points and dimensions which also de ne some speci c notion of data locality.”
An Entropy Weighting k-Means Algorithm for Subspace Clustering of High-Dimensional Sparse Data (2007, methodology): “The first type is to find out the exact subspaces of different clusters (see, for instance, [6], [7], [8], [9], [10], [11], [12]).”
Evaluating Clustering in Subspace Projections of High Dimensional Data (2009, methodology): “Also, it is beyond the scope to this work to include more specialized algorithms like correlation clustering [2] which transform the data space based on detected cor-”
A Monte Carlo algorithm for fast projective clustering (2002, methodology): “In order to evaluate the competitiveness of our method, we implemented both PROCLUS [1] and ORCLUS [2], the two previous algorithms that compute axis-parallel projective clusters.”
Subspace clustering for high dimensional data: a review (2004, background): “ORCLUS [6] is an extended version of the algorithm PROCLUS[5] that looks for non-axis parallel subspaces.”
A Survey of Text Clustering Algorithms (2012, background): “This is also known as local dimensionality reduction [22] or generalized projected clustering [6] in the traditional database literature.”
Outlier Analysis (2013, methodology): “The method discussed in [7] has a built-in mechanism in order to determine the outliers in addition to the clusters.”