k-means projective clustering

ABSTRACT

In many applications it is desirable to cluster high dimensional data along various subspaces, which we refer to as projective clustering. We propose a new objective function for projective clustering, taking into account the inherent trade-off between the dimension of a subspace and the induced clustering error. We then present an extension of the k-means clustering algorithm for projective clustering in arbitrary subspaces, and also propose techniques to avoid local minima. Unlike previous algorithms, ours can choose the dimension of each cluster independently and automatically. Furthermore, experimental results show that our algorithm is significantly more accurate than the previous approaches.

REFERENCES

• 1: Pankaj K. Agarwal , Sariel Hal-Peled, Maintaining approximate extent measures of moving points, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.148-157, January 07-09, 2001, Washington, D.C., United States
• 2: Pankaj K. Agarwal , Sariel Har-Peled , Nabil H. Mustafa , Yusu Wang, Near-Linear Time Approximation Algorithms for Curve Simplification, Proceedings of the 10th Annual European Symposium on Algorithms, p.29-41, September 17-21, 2002
• 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: 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
• 5: 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
• 6: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 7: Kaushik Chakrabarti , Sharad Mehrotra, Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces, Proceedings of the 26th International Conference on Very Large Data Bases, p.89-100, September 10-14, 2000
• 8: Qiang Du , Vance Faber , Max Gunzburger, Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Review, v.41 n.4, p.637-676, Dec. 1999 [doi>10.1137/S0036144599352836]
• 9: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States
• 10: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 11: S. Har-Peled, Approximate Shape Fitting via Linearization, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.66, October 14-17, 2001
• 12: R. M. Heiberger, Algorithm AS 127: Generation of random orthogonal matrices, Appl. Statist., 27 (1978), 199--206.
• 13: Alexander Hinneburg , Charu C. Aggarwal , Daniel A. Keim, What Is the Nearest Neighbor in High Dimensional Spaces?, Proceedings of the 26th International Conference on Very Large Data Bases, p.506-515, September 10-14, 2000
• 14: Alexander Hinneburg , Daniel A. Keim, Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering, Proceedings of the 25th International Conference on Very Large Data Bases, p.506-517, September 07-10, 1999
• 15: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 16: W. Johnson and J. Lindenstrauss, Extensions of Lipschitz maps into a Hilbert space, Contemp. Math., 26 (1984), 189--206.
• 17: T. T. Jolliffe, Principal component analysis, Springer-Verlag, New York, 2002.
• 18: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 19: 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]
• 20: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada