Dimension induced clustering

ABSTRACT

It is commonly assumed that high-dimensional datasets contain points most of which are located in low-dimensional manifolds. Detection of low-dimensional clusters is an extremely useful task for performing operations such as clustering and classification, however, it is a challenging computational problem. In this paper we study the problem of finding subsets of points with low intrinsic dimensionality. Our main contribution is to extend the definition of fractal correlation dimension, which measures average volume growth rate, in order to estimate the intrinsic dimensionality of the data in local neighborhoods. We provide a careful analysis of several key examples in order to demonstrate the properties of our measure. Based on our proposed measure, we introduce a novel approach to discover clusters with low dimensionality. The resulting algorithms extend previous density based measures, which have been successfully used for clustering. We demonstrate the effectiveness of our algorithms for discovering low-dimensional m-flats embedded in high dimensional spaces, and for detecting low-rank sub-matrices.

REFERENCES

• 1: Pankaj K. Agarwal , Nabil H. Mustafa, k-means projective clustering, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055581]
• 2: Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu , Cecilia Procopiuc , Jong Soo Park, Fast algorithms for projected clustering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.61-72, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.70-81, May 15-18, 2000, Dallas, Texas, United States
• 4: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 5: Mihael Ankerst , Markus M. Breunig , Hans-Peter Kriegel , Jörg Sander, OPTICS: ordering points to identify the clustering structure, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.49-60, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 7: Daniel Barbará , Ping Chen, Using the fractal dimension to cluster datasets, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.260-264, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347145]
• 8: Alberto Belussi , Christos Faloutsos, Self-spacial join selectivity estimation using fractal concepts, ACM Transactions on Information Systems (TOIS), v.16 n.2, p.161-201, April 1998 [doi>10.1145/279339.279342]
• 9: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 10: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 11: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusteris in large spatial databases with noise. In Proc. KDD, 1996.
• 12: Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
• 13: Roberto F. Santos Filho , Agma J. M. Traina , Caetano Traina, Jr. , Christos Faloutsos, Similarity Search without Tears: The OMNI Family of All-purpose Access Methods, Proceedings of the 17th International Conference on Data Engineering, p.623-630, April 02-06, 2001
• 14: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 15: T. Hastie, R. Tibshirani, and J. H. Friedman. The Elements of Statistical Learning. Springer-Verlag, 2001.
• 16: A. Hinneburg and D. Keim. An efficient approach to clustering in large multimedia databases with noise. In Proc. KDD, 1998.
• 17: Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
• 18: R. Krauthgamer and J. R. Lee. The black-box complexity of nearest neighbor search. In Proc. ICALP, 2004.
• 19: Deflating the Dimensionality Curse Using Multiple Fractal Dimensions, Proceedings of the 16th International Conference on Data Engineering, p.589, February 28-March 03, 2000
• 20: S. Papadimitriou, H. Kitagawa, P. B. Gibbons, and C. Faloutsos. LOCI: Fast outlier detection using the local correlation integral. In Proc. ICDE, 2003.
• 21: Cecilia M. Procopiuc , Michael Jones , Pankaj K. Agarwal , T. M. Murali, A Monte Carlo algorithm for fast projective clustering, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564739]
• 22: S. N. Rasband. Chaotic Dynamics of Nonlinear Systems. Wiley-Interscience, 1990.
• 23: Haixun Wang , Wei Wang , Jiong Yang , Philip S. Yu, Clustering by pattern similarity in large data sets, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564737]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.m MISCELLANEOUS

General Terms:
Algorithms, Measurement

Keywords:
clustering, fractal dimension