聚類有效性評價新指標

謝娟英，周穎，王明釗，姜煒亮

隨著人工智能技術如火如荼地發展，機器學習在各行業得到了空前的重視和應用，并取得了前所未有的成功[1-5]。聚類分析作為無監督學習方法，是各行業數據分析的主要工具之一，其旨在發現數據集樣本的潛在分布模式與內在結構，發現數據集樣本中所隱藏的知識。聚類分析使得同類簇的樣本盡可能相似，不同類簇的樣本盡可能不相似[6-7]。聚類評價指標是度量聚類結果有效性的客觀指標，也是衡量聚類算法性能的客觀依據，設計一個全面的聚類結果評價指標是一個困難而復雜的問題[8-13]。

根據是否利用數據集樣本真實類標信息(真實的樣本分布信息)，聚類有效性評價指標分為外部評價指標和內部評價指標。外部評價指標通過比較聚類結果與真實分布的匹配程度，對聚類結果進行評價?，F有外部評價指標分為基于相依表的，基于樣本對的和基于信息熵的指標[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 結束語

聚類作為無監督學習，是大數據集背景下知識發現的重要方法之一。聚類學習結果的有效性評價是聚類分析不可或缺的重要組成部分?，F有聚類評價指標的外部評價指標側重于正類，對聚類結果類偏斜問題缺少考慮，為此，提出了分別基于相依表和樣本對的，同時考慮正負類信息的外部評價新指標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.