A new cell-based clustering method for large, high-dimensional data in data mining applications

ABSTRACT

Recently data mining applications require a large amount of high-dimensional data. However, most clustering methods for data miming do not work efficiently for dealing with large, high-dimensional data because of the so-called 'curse of dimensionality'[1] and the limitation of available memory. In this paper, we propose a new cell-based clustering method which is more efficient for large, high-dimensional data than the existing clustering methods. Our clustering method provides an efficient cell creation algorithm using a space-partitioning technique and uses a filtering-based index structure using an approximation technique. Finally, we compare the performance of our cell-based clustering method with the CLIQUE method in terms of cluster construction time, precision, and retrieval time. The experimental results show that our clustering method achieves better performance on cluster construction time and retrieval time.

REFERENCES

• 1: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263671]
• 2: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 3: Ester M., Kriegel H.-P., Sander J., Xu X., "A Density Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining, AAAI Press, 1996.
• 4: Wei Wang , Jiong Yang , Richard R. Muntz, STING: A Statistical Information Grid Approach to Spatial Data Mining, Proceedings of the 23rd International Conference on Very Large Data Bases, p.186-195, August 25-29, 1997
• 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: http://www.almaden.ibm.com/cs/que

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
cell-based clustering, data mining, filtering-based index structure, high dimensional data