It is critical to determine the optimal number of clusters (NC) in cluster analysis. Many cluster validity indices have been proposed, such as the Silhouette index and In-group proportion index. However, these validity indices have more time complexity. From the viewpoint of sample geometry, a new internal cluster validity index for determining the optimal NC is proposed. The new index can evaluate the clustering quality of a certain clustering algorithm and determine the optimal NC for many kinds of data sets, including synthetic data sets, benchmark data sets, and real data sets. Compared with many well-known validity indices, the proposed index is more effective and efficient. Theoretical analysis and experimental results show the effectiveness and high efficiency of the new index.
LiuY., LiZ., XiongH., GaoX., WuJ. and WuS., Understanding and enhancement of internal clustering validation measures, IEEE Transactions on Cybernetics43(3) (2013), 982–994.
2.
DaviesD.L. and BouldinD.W., A cluster separation measure, IEEE Transactions on Pattern Analysis and Machine Intelligence1(2) (1979), 224–227.
3.
RousseeuwP.J., Silhouettes: A graphical aid to the interpretation and validation of cluster analysis, Journal of Computational and Applied Mathematics20(1) (1987), 53–65.
4.
DudoitS. and FridlyandJ., A prediction-based resampling method for estimating the number of clusters in a dataset, Genome Biology3(7) (2002), 1–21.
5.
StrehlA., Relationship-based clustering and cluster ensembles for high-dimensional data mining, Austin: University of Texas at Austin, 2002.
6.
WangK., LiJ., ZhangJ. and GuoL., Experimental comparison of clusters number estimation for cluster analysis, Computer Engineering34(9) (2008), 198–199.
7.
KappA.V. and TibshiraniR., Are clusters found in one dataset present in another dataset?Biostatistics8(1) (2007), 9–31.
8.
LiangJ., ZhaoX., LiD., CaoF. and DangC., Determining the number of clusters using information entropy for mixed data, Pattern Recognition45(6) (2012), 2251–2265.
9.
ZhaoQ. and FräntiP., WB-index: A sum-of-squares based index for cluster validity,&, Knowledge Engineering92 (2014), 77–89.
10.
XuR., XuJ. and WunschD.C.II, A comon study of validity indices on swarm-intelligence-based clustering, IEEE Transactions on Systems, Man, and Cybernetics–Part B: Cybernetics42(4) (2012), 1243–1256.
11.
StarczewskiA., A new validity index for crisp clusters, Pattern Analysis and Application20(3) (2017), 687–700.
12.
YueS., WangJ., WangJ. and BaoX., A new validity index for evaluating the clustering results by partitional clustering algorithms, Soft Computing20(3) (2016), 1127–1138.
13.
BhargaviM.S. and GowdaS.D., A novel validity index with dynamic cut-off for determining true clusters, Pattern Recognition48(11) (2015), 3673–3687.
14.
ShiehH., Robust validity index for a modified subtractive clustering algorithm, Applied Soft Computing22 (2014), 47–59.
15.
Rojas-ThomasJ.C., SantosM. and MoraM., New internal index for clustering validation based on graphs, Expert Systems with Applications86 (2017), 334–349.
16.
BezdekJ.C., MoshtaghiM., RunklerT. and LeckieC., The generalized C index for internal fuzzy cluster validity, IEEE Transactions on Fuzzy Systems24(6) (2016), 1500–1512.
17.
LiuC.-M., NiuZ. and LiaoK., Mechanisms to improve clustering uncertain data with UKmeans,&, Knowledge Engineering116 (2018), 61–79.
18.
ArbelaitzO., GurrutxagaI., MuguerzaJ., Pe'rezJ.M. and PeronaI., An extensive comparative study of cluster validity indices, Pattern Recognition46(1) (2013), 243–256.
19.
FreyB.J. and DueckD., Clustering by passing messages between data points, Science315(5814) (2007), 972–976.
20.
DudaR.O., HartP.E. and StorkD.G., Pattern Classification (2nd), John Wiley & Sons, New York, NY, 2001.
21.
GurrutxagaI., AlbisuaI., ArbelaitzO., MartinJ.I., MuguerzaJ., Pe'rezJ.M. and PeronaI., SEP/COP: An efficient method to find the best partition in hierarchical clustering based on a new cluster validity index, Pattern Recognition43(10) (2010), 3364–3373.
22.
KaufmanL. and RousseeuwP.J., Finding groups in data: An introduction to cluster analysis, John Wiley & Sons, Hoboken, NJ, 1990.
23.
PalN.R. and BezdekJ.C., On cluster validity for the fuzzy c-means model, IEEE Transactions on Fuzzy Systems3(3) (1995), 370–379.
24.
BezdekJ.C. and PalN.R., Some new indexes of cluster validity, IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics28(3) (1998), 301–315.
25.
Iam-OnN., BoongoenT., GarrettS. and PriceC., A link-based approach to the cluster ensemble problem, IEEE Transactions on Pattern Analysis and Machine Intelligence33(12) (2011), 2396–2409.
