聚类有效性评价新指标

谢娟英，周颖，王明钊，姜炜亮

随着人工智能技术如火如荼地发展，机器学习在各行业得到了空前的重视和应用，并取得了前所未有的成功[1-5]。聚类分析作为无监督学习方法，是各行业数据分析的主要工具之一，其旨在发现数据集样本的潜在分布模式与内在结构，发现数据集样本中所隐藏的知识。聚类分析使得同类簇的样本尽可能相似，不同类簇的样本尽可能不相似[6-7]。聚类评价指标是度量聚类结果有效性的客观指标，也是衡量聚类算法性能的客观依据，设计一个全面的聚类结果评价指标是一个困难而复杂的问题[8-13]。

根据是否利用数据集样本真实类标信息(真实的样本分布信息)，聚类有效性评价指标分为外部评价指标和内部评价指标。外部评价指标通过比较聚类结果与真实分布的匹配程度，对聚类结果进行评价。现有外部评价指标分为基于相依表的，基于样本对的和基于信息熵的指标[8,13-14]。F-measure[17-18]是最先提出的外部评价指标，是针对两类问题的评价指标，是精度和召回率的调和平均，后来被推广到多类问题。常用的外部评价指标还有Jaccard系数、Rand index参数、ARI (adjusted rand index)参数、标准化互信息NMI (normalized mutual information)和调整互信息AMI (adjusted mutual information)，以及B3(bcubed index)等[8,17-19]。不同外部评价指标侧重点不同，Amigó等[20]提出4个形式化约束(cluster homogeneity, cluster completeness, rag bag和clusters size vs. quantity)对现有外部评价指标进行比较。Vinh等[21]指出ARI指标是目前最好的聚类评价指标。聚类结果类偏斜是现实世界数据，特别是生物医学数据聚类分析中的普遍现象[22-23]。尽管已经出现针对不平衡数据和不同类簇密度的聚类评价指标研究[8,24]，但还没有考虑聚类结果偏斜的外部评价指标。鉴于此，本文利用聚类结果的相依表和样本对信息，同时考虑聚类结果的正负类信息，提出分别基于相依表和基于样本对的外部评价指标S2(harmonic mean of sensitivity and specificity)和PS2(harmonic mean of sensitivity and specificity based on pairwise)，以期有效评价偏斜聚类结果。

内部评价指标没有使用原始数据分布的先验信息，常通过评价聚类结果优劣来发现数据集的内部结构和分布状态，是发现数据集最佳类簇数的常用办法[25]。内部指标有基于统计信息和基于样本几何结构的指标。IGP指标[26](in-group proportion)是基于统计信息的指标，通过度量在某一类簇中，距离某个样本最近的样本是否和该样本在同一类簇，来评价聚类结果的优劣。常用的基于数据集样本几何结构的内部指标有DB指标(davies-bouldin)[27-28]、XB 指标 (xie-beni)[29]、Sil指标 (silhouettes)[30]、BWP指标(between-within proportion)[31]等。这些聚类有效性评价内部指标自身的缺陷，使得其对于类簇结构难以判别，聚类有效性检验效果不理想，很难得到正确的聚类结果和发现最佳类簇数。针对现有内部评价指标的上述问题，本文利用方差的性质，定义类内距离和类间距离，以表达类簇间的分离性与类簇内的紧促性，提出基于类间分离性与类内紧密性之比的新内部评价指标STDI(standard deviation based index)，以期发现数据集的真实类簇分布结构。

UCI机器学习数据库真实数据集和人工模拟的带有刁难性的及带有噪音与类偏斜的人工模拟数据集实验测试表明，提出的内部评价新指标STDI能发现更合理的数据集类簇数；提出的分别基于相依表和样本对的外部评价指标S2和PS2可以有效评价有类偏斜现象的聚类结果。

1 外部指标

聚类分析中可能遇到如表1所示的极端情况。此时，若用F-measure指标评价表1所示极端聚类结果的有效性，将失去意义。因为，此时的F-measure指标值是0.67，但实际聚类结果毫无意义。导致这种现象的原因是：F-measure是精度和召回率的调和平均。对于两类问题，F-measure只强调了聚类算法对正类的聚类效果，而未考虑聚类算法对负类的聚类效果。

表1 极端聚类结果示例Table 1 Rare case of clustering

为了避免此类问题，本文提出一种基于相依表的、同时考虑正负类聚类结果的评价指标S2。S2指标调和了聚类算法对于正负类的聚类效果，是灵敏度和特异度的调和平均。如同F-measure可推广于多类问题一样，S2同样适用于作为多类问题的聚类评价指标。

设聚类结果类簇数为K，原始类簇数为C，则聚类结果相依表是表2所示的C×K矩阵，U是真实分布，V是聚类算法所得聚类结果，则任意类簇c的TPc、FNc、FPc、TNc分别定义如式 (1)所示。其中，l为原始类标信息，L为聚类所得类标信息，n为样本数。以类簇c为正类的sensitivity和specificity定义如式(2)所示。则新聚类指标S2如式(3)定义。当类簇数K=2时，式(3)的S2指标退化为式(4)，其中的sensitivity和specificity同F-measure指标在两类问题中的定义一致。由此可见，我们定义的新指标S2适用于任意类的聚类问题。

表2 聚类结果相依表Table 2 The contingency table of a clustering

外部评价指标中的Rand index、Adjusted rand index、Jaccard系数，AMI等均是基于样本对的聚类评价指标。因此，本文类似地提出基于样本对的聚类结果外部评价指标PS2，调和聚类结果的正类识别率和负类识别率，以评价聚类结果的有效性。

表3 聚类结果混淆矩阵Table 3 Confusion matrix of a clustering

2 内部指标

方差作为一种度量样本分布情况的概率统计量，通常用来描述样本的离散程度[32]。样本方差越小，样本分布越密集，反之则越分散。方差的性质可以用于计算类内距离和类间距离，同一类簇中样本分布越密集，方差越小，因此将同一类簇中样本的方差作为类内距离，度量类簇内部的紧促性。

基于“类内尽可能紧密，类间尽可能分离”原则，利用方差思想定义度量类内距离和类间距离测度，类间距离越大越好，类内距离越小越好，提出将类间距离与类内距离之比作为聚类效果的内部评价指标 STDI(standard deviation based index)，如式 (9)所示。从式(9)STDI的定义可知，其值越大，表明聚类结果越好。

式中：ck是类簇k的质心，是所有样本的质心，xi是类簇k的第i个样本，nk是类簇k的样本数，K是数据集的类簇数。STDI指标的分子表示各类簇间方差，分母表示各类簇方差之和。显然簇内方差越小，则分母越小，表示类簇内部分布越紧密，簇间方差越大，则分子越大，表示各类簇的分离性越好。因此，STDI的值越大越好。

3 实验分析

本节将分别测试提出的内部指标和外部指标的性能。因为篇幅所限，内部指标只使用图1所示的具有挑战性的人工模拟数据集进行测试，该数据集经常被识别为3个类簇。外部评价指标将使用来自UCI机器学习数据库[33]的真实数据集和人工模拟数据集两大类数据进行测试。其中的人工模拟数据包括：类簇样本分布不平衡的偏斜数据，以及类簇样本分布平衡但各类簇间存在部分交叠的数据。这样设计人工模拟数据集的目的在于：检测提出的外部指标S2与PS2对带有噪音以及类别分布不平衡数据聚类结果的判断能力。测试外部指标的人工模拟数据集如图2所示，表4是图2各数据集的详细信息，测试外部指标的UCI机器学习数据库的真实数据集如表5所示。

图1 测试内部指标STDI的人工数据集原始分布Fig. 1 The synthetic data set to test the new internal criteria STDI

图2 测试外部指标S2和PS2的人工数据集原始分布Fig. 2 The synthetic data sets to test the new external criteria S2 and PS2

表4 测试新外部指标S2和PS2的人工模拟数据集信息Table 4 The detail information of synthetic data sets to test the proposed external criteria S2 and PS2

3.1 内部指标有效性测试实验

内部指标不需要任何先验知识，通过评价聚类结果，发现数据集样本的潜在分布与内在结构，常用于发现数据集的类簇数。因此，我们以能否准确发现数据集的真实类簇数来测试提出的内部指标STDI指标的有效性，并与现有内部指标DB、XB、IGP、Sil和BWP的性能进行比较。图3给出了各内部指标对图1所示人工模拟数据集的实验结果。这里的聚类算法使用的是SD算法[35]。

表5 测试新外部指标S2和PS2的UCI数据集Table 5 The data sets from UCI machine learning repository to test the proposed external criteria S2 and PS2

从图3各指标的实验结果可以看出，只有图3(a)展示的STDI指标的实验结果可以发现图1所示人工数据集的真实类簇数9，其余5个指标均在类簇数为3时最佳，即其余指标发现的该数据集类簇数是3。因此，只有用本文提出内部聚类指标STDI可以得到该人工模拟数据集的正确类簇数。分析原因是：本文提出的STDI指标采用各类簇质心方差度量类间分离程度，用各类簇样本方差度量类内紧密程度，当类簇数为9时，各类簇质心方差较大，而簇内样本方差较小，因此得到最佳聚类结果，发现数据集的正确类簇数。由此可见，本文提出的STDI指标是非常有效的一种聚类评价指标。

图3 各内部指标在人工数据集的测试结果Fig. 3 The results on synthetic data set of internal criteria

3.2 外部指标有效性测试实验

本小节对提出的2种聚类有效性评价外部指标S2和PS2进行测试，聚类算法选取快速K-medoids算法[35]。为了充分说明提出的外部评价指标S2和PS2的有效性，特别设计了带有噪音，类簇分布平衡和不平衡的人工模拟数据集，并选择了来自UCI机器学习数据库的样本数、类簇数和各类簇样本规模各异的真实数据集来进行测试，同时将提出的S2和PS2指标与聚类准确率Accuracy，以及经典外部评价指标F-measure、Rand index、Jaccard系数和ARI的指标值进行比较。

图2和表4所示人工模拟数据集的类簇数从2～6，类簇数相同的人工模拟数据集包括两类：类簇样本数均衡，但簇间样本重叠的情况；类簇样本数不平衡，即存在类簇偏斜，簇间样本重叠或很少量重叠的情况。这样的人工模拟数据集将测试提出的外部评价指标S2和PS2对存在类偏斜或样本重叠分布的数据聚类结果的评价情况。表5来自UCI机器学习数据库的12个真实数据集的样本数，类簇数和类簇样本分布也各不相同。这些真实数据集将进一步检测提出的外部评价指标S2和PS2的有效性。

为了清楚展示S2和PS2指标的性能，分别将S2和PS2的实验测试结果与聚类准确率Accuracy，经典外部评价指标F-measure、Rand index、Jaccard系数和ARI指数进行比较，并将S2和PS2指标与聚类准确率独立比较。图4展示了S2指标在人工模拟数据集和真实数据集的测试结果与其他指标的比较。图5给出了PS2指标的实验测试结果与其他指标的比较。S2与PS2的性能比较如图6所示，图6同时展示了聚类准确率指标。图4和图5中的R是Rand index的简写。

图4 S2指标与其他指标的测试结果比较Fig. 4 The comparison of S2 with other criteria

图5 PS2指标的测试结果与其他指标的比较Fig. 5 The comparison of PS2 with other criteria

图6 S2与PS2指标与聚类准确率比较Fig. 6 The comparison of S2 and PS2 and clustering accuracy

图4 (a)人工模拟数据集的实验结果揭示，除了含有6个不平衡类簇的人工模拟数据集外，本文提出的同时考虑正负类信息的聚类有效性评价指标S2与其他指标相比具有最高值，且与其他指标在各数据集测试的指标值走势一致。因此，可以说提出的S2指标可以有效评价存在类偏斜分布的聚类结果。图4(b)所示的UCI机器学习数据库真实数据集的实验测试结果显示，提出的外部评价指标S2在12个真实数据集的指标值只有在Segmentation和Bupa两个数据集的测试指标值不是最高，在其余10个真实数据集的测试结果值均高于聚类准确率Accuracy，以及经典外部指标Rand index指数，ARI，Jaccard系数和F-measure。另外，提出的S2指标在各真实数据集的测试值与Accuracy，Jaccard，ARI和F-measure各指标值的走势基本一致，但与Rand index指标不太一致。图4(a)和(b)的实验结果共同揭示，提出的S2指标的测试值与聚类准确率Accuracy，外部指标F-measure，Rand index指数，ARI和Jaccard系数在各数据集的基本走势大体一致。当前最优的外部评价指标ARI在各指标值中位居后两位，特别是在真实数据集，ARI特别突出的位于后两位。这更进一步说明了提出的同时考虑正负类信息的外部评价指标S2的有效性。

图5(a)人工模拟数据集的实验结果显示，除了含有6个不平衡类簇的人工模拟数据集，提出的基于样本对信息，同时考虑正负类信息的外部评价指标PS2在其他人工模拟数据集的指标值基本与聚类准确率重合，或略低于聚类准确率，但走势一致。图5(b)真实数据集实验结果显示，提出的PS2指标低于或等于聚类准确率，聚类准确率或Rand index指数在真实数据集的测试结果高于等于提出的PS2指标。当前最佳聚类评价指标ARI在带有噪音和类簇分布不平衡的人工模拟数据集，以及样本规模，类簇数和各类簇样本规模变化各异的真实数据集的测试结果与其他指标相比，取值较低，在6个比较指标中居后两位。

图6(a)人工模拟数据集实验结果显示，除了在含有6个不平衡类簇的人工模拟数据集的S2指标低于PS2指标和聚类准确率外，在其余人工模拟数据集上，S2指标的指标值均高于PS2指标，聚类准确率居中。图6(b)真实数据集实验结果显示，在真实数据集的S2指标明显高于PS2指标值。真实数据集的聚类准确率Accuracy除了在Bupa数据集高于S2和PS2指标，在Segmentation数据集低于S2和PS2指标外，在其余数据集的聚类准确率均低于等于S2指标，但高于PS2指标。聚类分析的目的是发现数据集的正确类簇分布。图6(a)～(b)的实验结果揭示，提出的分别基于相依表和样本对，且同时考虑正负类信息的外部评价指标S2和PS2均能正确评价聚类结果的有效性，其走势与聚类准确率大体一致。其中，S2指标的走势更趋近于聚类准确率。

4 结束语

聚类作为无监督学习，是大数据集背景下知识发现的重要方法之一。聚类学习结果的有效性评价是聚类分析不可或缺的重要组成部分。现有聚类评价指标的外部评价指标侧重于正类，对聚类结果类偏斜问题缺少考虑，为此，提出了分别基于相依表和样本对的，同时考虑正负类信息的外部评价新指标S2和PS2。另外，针对现有内部评价指标在发现数据集最佳类簇数方面的局限，提出了基于方差的类内紧密度和类间分离性度量，定义了以类间分离性与类内紧密度之比为度量指标的内部评价新指标STDI。UCI机器学习数据库真实数据集和带有刁难性的人工模拟数据集实验测试表明，提出的新内部指标STDI能有效发现数据集的真实类簇数；提出的外部指标S2和PS2是非常有效的聚类有效性外部评价指标，可有效评价存在类偏斜与噪音数据的聚类结果。

[1]ESTEVA A, KUPREL B, NOVOA RA, et al. Dermatologist-level classification of skin cancer with deep neural networks[J]. Nature, 2017, 542(7639): 115–118.

[2]FARINA D, VUJAKLIJA I, SARTORI M, et al. Man/machine interface based on the discharge timings of spinal motor neurons after targeted muscle reinnervation[J].Nature biomedical engineering, 2017, 1: 25.

[3]GULSHAN V, PENG L, CORAM M, et al. Development and validation of a deep learning algorithm for detection of diabetic retinopathy in retinal fundus photographs[J].JAMA, 2016, 316(22): 2402–2410.

[4]LONG E, LIN H, LIU Z, et al. An artificial intelligence platform for the multihospital collaborative management of congenital cataracts[J]. Nature biomedical engineering, 2017, 1:0024.

[5]ORRINGER DA, PANDIAN B, NIKNAFS Y S, et al. Rapid intraoperative histology of unprocessed surgical specimens via fibre-laser-based stimulated Raman scattering microscopy[J]. Nature biomedical engineering, 2017, 1: 0027.

[6]HAN J, PEI J, KAMBER M. Data mining: concepts and techniques[M]. Singapore: Elsevier, 2011.

[7]JAIN AK, DUBES RC. Algorithms for clustering data[M]. Prentice-Hall, 1988.

[8]DE SOUTO MCP, COELHO ALV, FACELI K, et al. A comparison of external clustering evaluation indices in the context of imbalanced data sets[C]//2012 Brazilian Symposium on Neural Networks (SBRN). [S.l.], 2012: 49-54.

[9]HUANG S, CHRNG Y, LANG D, et al. A formal algorithm for verifying the validity of clustering results based on model checking[J]. PloS one, 2014, 9(3): e90109.

[10]RENDÓN E, ABUNDEZ I, ARIZMENDI A, et al. Intern-al versus external cluster validation indexes[J]. International journal of computers and communications, 2011, 5(1):27–34.

[11]ROSALES-MENDÉZ H, RAMÍREZ-CRUZ Y. CICEBCubed: A new evaluation measure for overlapping clustering algorithms[C]//Iberoamerican Congress on Pattern Recognition. Berlin: Springer Berlin Heidelberg, 2013:157-164.

[12]SAID AB, HADJIDJ R, FOUFOU S. Cluster validity index based on jeffrey divergence[J]. Pattern analysis and applications, 2017, 20(1): 21–31.

[13]XIONG H, WU J, CHEN J. K-means clustering versus validation measures: a data-distribution perspective[J]. IEEE transactions on systems, man, and cybernetics, part b (cybernetics), 2009, 39(2): 318–331.

[14]POWERS D M W. Evaluation: from precision, recall and F-factor to ROC, informedness, markedness and correlation[J]. Journal of machine learning technologies, 2011, 2:2229–3981.

[15]LARSEN B, AONE C. Fast and effective text mining using linear-time document clustering[C]//Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining. New York, USA: ACM,1999: 16-22.

[16]ZU EISSEN, B S S M, WIßBROCK F. On cluster validity and the information need of users[C]//Conference on Artificial Intelligence and Applications, Benalmádena, Spain,2003. Calgary, Canada: ACTA Press, 2003: 216-221.

[17]谢娟英. 无监督学习方法及其应用[M]. 北京: 电子工业出版社, 2016.XIE Juanying, Unsupervised learning methods and applications[M]. Beijing: Publishing House of Electronics Industry, 2016.

[18]XIE J Y, GAO H C, XIE W X, et al. Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors[J]. Information sciences, 2016, 354: 19–40.

[19]谢娟英, 高红超, 谢维信. K 近邻优化的密度峰值快速搜索聚类算法[J]. 中国科学: 信息科学, 2016, 46(2):258–280.XIE Juanying, GAO Hongchao, XIE Weixin. K-nearest neighbors optimized clustering algorithm by fast search and finding the density peaks of a dataset[J]. Scientia sinica informationis, 2016, 46(2): 258–280.

[20]AMIGÓ E, GONZALO J, ARTILES J, et al. A comparison of extrinsic clustering evaluation metrics based on formal constraints[J]. Information retrieval, 2009, 12(4):461–486.

[21]VINH NX, EPPS J, BAILEY J. Information theoretic measures for clusterings comparison: is a correction for chance necessary [C]//Proceedings of the 26th Annual International Conference on Machine Learning, Montreal,Canada, 2009. New York, USA: ACM, 2009: 1073-1080.

[22]D'HAESELEER P. How does gene expression clustering work[J]. Nature biotechnology, 2005, 23(12): 1499.

[23]QUACKENBUSH J. Computational analysis of microarray data[J]. Nature reviews genetics, 2001, 2(6): 418–427.

[24]CHOU CH, SU MC, LAI E. A new cluster validity measure for clusters with different densities[C]//IASTED International Conference on Intelligent Systems and Control.Calgary, Canada: ACTA Press, 2003: 276-281.

[25]谢娟英, 周颖. 一种新聚类评价指标[J]. 陕西师范大学学报: 自然科学版, 2015, 43(6): 1–8.XIE Juanying, ZHOU Ying. A new criterion for clustering algorithm[J]. Journal of Shaanxi normal university: natural science edition, 2015, 43(6): 1–8.

[26]KAPP AV, TIBSHIRANI R. Are clusters found in one dataset present in another dataset[J]. Biostatistics, 2007,8(1): 9–31.

[27]DAVIES DL, BOULDIN DW. A cluster separation measure[J]. IEEE transactions on pattern analysis and machine intelligence, 1979(2): 224–227.

[28]HASHIMOTO W, NAKAMURA T, MIYAMOTO S.Comparison and evaluation of different cluster validity measures including their kernelization[J]. Journal of advanced computational intelligence and intelligent informatics, 2009, 13(3): 204–209.

[29]XIE XL, BENI G. A validity measure for fuzzy clustering[J]. IEEE transactions on pattern analysis and machine intelligence, 1991, 13(8): 841–847.

[30]ROUSSEEUW PJ. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis[J]. Journal of computational and applied mathematics, 1987, 20: 53–65.

[31]周世兵, 徐振源, 唐旭清. 一种基于近邻传播算法的最佳聚类数确定方法[J]. 控制与决策, 2011, 26(8): 1147–1152.ZHOU Shibing, XU Zhenyuan, TANG Xuqing. Method for determining optimal number of clusters based on affinity propagation clustering[J]. Control and decision, 2011, 26(8): 1147–1152.

[32]盛骤, 谢式千. 概率论与数理统计及其应用[M]. 北京: 高等教育出版社, 2004.SHENG Zhou, XIE Shiqian. Probability and mathematical statistics and its application[M]. Beijing: Higher education press, 2004.

[33]LICHMAN M, UCI Machine learning repository[EB/OL].2013, University of California, Irvine, School of Information and Computer Sciences. http://archive.ics.uci.edu/ml.

[34]谢娟英, 高瑞. 方差优化初始中心的K-medoids聚类算法[J]. 计算机科学与探索, 2015, 9(8): 973–984.XIE Juanying, GAO Rui. K-medoids clustering algorithms with optimized initial seeds by variance[J]. Journal of fron-tiers of computer science and technology, 2015, 9(8):973–984.

[35]PARK HS, JUN CH. A simple and fast algorithm for K-medoids clustering[J]. Expert systems with applications,2009, 36(2): 3336–3341.