CLUC: a natural clustering algorithm for categorical datasets based on cohesion

ABSTRACT

We propose a clustering algorithm for categorical datasets, called CLUC (CLUstering with Cohesion), which uses a novel similarity measure, called cohesion, to determine the degree with which items/objects stick to clusters. We have implemented CLUC and carried out extensive experiments on real-life and synthetic datasets. The results of experiments and their analyses indicate that CLUC generates high quality clusters in that they conform to expert's opinion. Our experiments on large synthetic data confirm that CLUC is scalable when the dataset grows in the number of objects and/or dimensions. We also repeated the experiments with different orders of the items in the datasets. The results show that the proposed algorithm is order insensitive

REFERENCES

• 1: P. Andritson, P. Tsaparas, R. J. Miller, and K. C. Seveik. LIMBO: Scalable clustering of categorical data. In EDBT, 2004.
• 2: D. Barbara, Y. Li, and J. Couto. Coolcat: An entropy-based algorithm for categorical clustering. In ACM Press, pages 582--589, 2002.
• 3: S. Guha, R. Rastogi, and K. Shim. Rock: A robust clustering algorithm for categorical attributes. In ICDE, 1999.
• 4: Mohammed J. Zaki , Markus Peters, CLICKS: Mining Subspace Clusters in Categorical Data via K-Partite Maximal Cliques, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.355-356, April 05-08, 2005 [doi>10.1109/ICDE.2005.33]
• 5: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 6: Y. Yiling, G. Xudong, and Y. Jinyuan, CLOPE: A fast and effective clustering algorithm for transactional data, In. KDD, pp 682--687, 2002.
• 7: UCI Machine Learning Repository, http://www.ics.uci.edu/~mlear/MLRepository.html.
• 8: Datagen http://www2.dcc.ufmg.br/~meira/ch/tp2/datgen

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Experimentation, Performance

Keywords:
categorical data, clustering, scalability, similarity