Algorithm Design for Cluster Validity Based on Geometric Probability

Abstract:

Determining optimum cluster number is a key research topic included in cluster validity. Based on geometric probability, this article proposes a new cluster validity algorithm to determine optimum cluster number for two-dimension datasets. The algorithm measure the cluster structure of the data set according to the distributive feature of the point set in the characteristic space. The structure information of the point set has been stored in a line segment set generated by connecting each pair points in the point set and the cluster validity function is formed by comparing the values of line segment direction in the line segment set with those resulted from completely random condition. Experiments prove that the pattern of the function curve generated with a given example data set effectively enables determining the optimum cluster number of the data set.

• Periodical: Applied Mechanics and Materials (Volume 311)
• Pages: 117-122
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.311.117
• Online since: February 2013
• Authors: Xiao Wen Li, Hua Lei Wu, Jian Wei Li
• Keywords: Cluster Validity, Geometric Probability, Optimum Cluster Number

References

[1] Han, J. and Kamber, M., 2001. Data Mining: Concepts and Techniques. Morgan Kaufmann, Los Altos, CA.

[2] Bezdek JC and Pal NR. Some new indexes of cluster validity. IEEE Transactions on ystems, Man and Cybernetics—Part B: Cybercetics, 1998, 28(3):301-305.

DOI: 10.1109/3477.678624

[3] Backer E and Jain AK. A clustering performance measure based on fuzzy set decomposition. IEEE Trans PAMI 1981;3:66–95.

DOI: 10.1109/tpami.1981.4767051

[4] Windham MP. Cluster validity for the fuzzy c-means clustering algorithm. IEEE Trans PAMI 1982;4:357–63.

[5] Al Sultan KS and Selim SZ. Global algorithm for fuzzy clustering problem. Pattern Recogn 1993;26:1357–61.

DOI: 10.1016/0031-3203(93)90141-i

[6] Nizar Grira, Michel Crucianu, Nozha Boujemaa. Unsupervised and Semi-supervised Clustering: a Brief Survey. in A Review of Machine Learning Techniques for Processing Multimedia Content, Re-port of the MUSCLE European Network of Excellence (6th Framework Programme), October 26, 2004.

[7] Jain AK and Murty MN and Flynn PJ．Data clustering：a review．ACM Computing Surveys，1999，31 (3)：265-323．

[8] Eiji Nakamura and Nasser Kehtarnavaz. Determining number of clusters and prototype locations via multi-scale clustering. Pattern Recognition Letters 19 (1998) 1265±1283.

DOI: 10.1016/s0167-8655(98)00099-3

[9] Malay K. Pakhiraa and Sanghamitra Bandyopadhyay and Ujjwal Maulik. Validity index for crisp and fuzzy clusters. Pattern Recognition 37 (2004) 487 – 501.

DOI: 10.1016/j.patcog.2003.06.005

[10] MAO Zheng-yuan and LI Lin.The Measurement of Spatial Patterns and Its Application．Beijing：Science Press，2004.