Application of two-order difference to gap statistic

Abstract

Gap statistic is a well-known index of clustering validity, but its realization is difficult to be comprehended and accurately determined. A direct method is presented to improve the performance of the Gap statistic, which applies the two-order difference of within-cluster dispersion to replace the constructed null reference distribution in the Gap statistic. Hence, the realization of the Gap statistic becomes easy and is reformulated, and its uncertainty in applications is reduced. Also, the limitation of the Gap statistic is analyzed by two typical examples, that is, the Gap statistic is difficult to be applied to the dataset that contains strong-overlap or uneven-density clusters. Experiments verify the usefulness of the proposed method.

Keywords

clustering validity / Gap statistic / data structure

References

[1] Xu R., Wunsch D.. Survey of clustering algorithm[J]. IEEE Trans Neural Network, 2005, 16(3): 645-661.

[2] Huang Z., Ng M. K., Rong H.. Automated variable weighting in k-means type clustering[J]. IEEE Trans Patt Anal Mach Intell, 2005, 27 657-668.

[3] Tibshirani R., Walther G., Hastie T.. Estimating the number of clusters via the Gap statistic[J]. J Royal Statist Soc B, 2001, 63(2): 411-423.

[4] Lange T.. An objective solution to clustering index[J]. Patt Rec Lett, 2006, 27(3): 700-712.

[5] Xie X., Beni G.. A validity method for fuzzy clustering[J]. IEEE Trans Patt Anal Mach Intell, 1991, 13(8): 841-847.

[6] Kim Y. I., Kim D. W., Lee D.. A cluster validation index for GK cluster analysis based on relative degree of sharing[J]. Information Sci, 2004, 168(1/2/3/4): 225-242.

[7] Lange T.. Stability-based validation of clustering solutions[J]. Neu Comp, 2004, 16(2): 1299-1323.

[8] Yue S., Li P.. The validity of clustering algorithm[J]. J Chinese Electronic, 2005, 13(1): 841 847

[9] Kim D., Lee K., Lee D.. On cluster validity index for estimation of the optimal number of fuzzy clusters[J]. Patt Recog, 2004, 37(10): 2009-2025.

[10] Kim D., Lee K., Lee D.. Validity index for crisp and fuzzy clusters[J]. Patt Recog, 2004, 37(3): 487-496.

[11] Yu J.. A general c-means clustering approach[J]. IEEE Trans Patt Anal Mach Intell, 2003, 25(8): 944-952.

[12] UCI Machine Learning Repository(University of California, Irvine, CA)[z]. ftp://ftp.cs.cornell.edu/pub/smart