聚類(lèi)有效性評(píng)價(jià)新指標(biāo)

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

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

根據(jù)是否利用數(shù)據(jù)集樣本真實(shí)類(lèi)標(biāo)信息(真實(shí)的樣本分布信息)，聚類(lèi)有效性評(píng)價(jià)指標(biāo)分為外部評(píng)價(jià)指標(biāo)和內(nèi)部評(píng)價(jià)指標(biāo)。外部評(píng)價(jià)指標(biāo)通過(guò)比較聚類(lèi)結(jié)果與真實(shí)分布的匹配程度，對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)價(jià)?，F(xiàn)有外部評(píng)價(jià)指標(biāo)分為基于相依表的，基于樣本對(duì)的和基于信息熵的指標(biāo)[8,13-14]。F-measure[17-18]是最先提出的外部評(píng)價(jià)指標(biāo)，是針對(duì)兩類(lèi)問(wèn)題的評(píng)價(jià)指標(biāo)，是精度和召回率的調(diào)和平均，后來(lái)被推廣到多類(lèi)問(wèn)題。常用的外部評(píng)價(jià)指標(biāo)還有Jaccard系數(shù)、Rand index參數(shù)、ARI (adjusted rand index)參數(shù)、標(biāo)準(zhǔn)化互信息NMI (normalized mutual information)和調(diào)整互信息AMI (adjusted mutual information)，以及B3(bcubed index)等[8,17-19]。不同外部評(píng)價(jià)指標(biāo)側(cè)重點(diǎn)不同，Amigó等[20]提出4個(gè)形式化約束(cluster homogeneity, cluster completeness, rag bag和clusters size vs. quantity)對(duì)現(xiàn)有外部評(píng)價(jià)指標(biāo)進(jìn)行比較。Vinh等[21]指出ARI指標(biāo)是目前最好的聚類(lèi)評(píng)價(jià)指標(biāo)。聚類(lèi)結(jié)果類(lèi)偏斜是現(xiàn)實(shí)世界數(shù)據(jù)，特別是生物醫(yī)學(xué)數(shù)據(jù)聚類(lèi)分析中的普遍現(xiàn)象[22-23]。盡管已經(jīng)出現(xiàn)針對(duì)不平衡數(shù)據(jù)和不同類(lèi)簇密度的聚類(lèi)評(píng)價(jià)指標(biāo)研究[8,24]，但還沒(méi)有考慮聚類(lèi)結(jié)果偏斜的外部評(píng)價(jià)指標(biāo)。鑒于此，本文利用聚類(lèi)結(jié)果的相依表和樣本對(duì)信息，同時(shí)考慮聚類(lèi)結(jié)果的正負(fù)類(lèi)信息，提出分別基于相依表和基于樣本對(duì)的外部評(píng)價(jià)指標(biāo)S2(harmonic mean of sensitivity and specificity)和PS2(harmonic mean of sensitivity and specificity based on pairwise)，以期有效評(píng)價(jià)偏斜聚類(lèi)結(jié)果。

內(nèi)部評(píng)價(jià)指標(biāo)沒(méi)有使用原始數(shù)據(jù)分布的先驗(yàn)信息，常通過(guò)評(píng)價(jià)聚類(lèi)結(jié)果優(yōu)劣來(lái)發(fā)現(xiàn)數(shù)據(jù)集的內(nèi)部結(jié)構(gòu)和分布狀態(tài)，是發(fā)現(xiàn)數(shù)據(jù)集最佳類(lèi)簇?cái)?shù)的常用辦法[25]。內(nèi)部指標(biāo)有基于統(tǒng)計(jì)信息和基于樣本幾何結(jié)構(gòu)的指標(biāo)。IGP指標(biāo)[26](in-group proportion)是基于統(tǒng)計(jì)信息的指標(biāo)，通過(guò)度量在某一類(lèi)簇中，距離某個(gè)樣本最近的樣本是否和該樣本在同一類(lèi)簇，來(lái)評(píng)價(jià)聚類(lèi)結(jié)果的優(yōu)劣。常用的基于數(shù)據(jù)集樣本幾何結(jié)構(gòu)的內(nèi)部指標(biāo)有DB指標(biāo)(davies-bouldin)[27-28]、XB 指標(biāo) (xie-beni)[29]、Sil指標(biāo) (silhouettes)[30]、BWP指標(biāo)(between-within proportion)[31]等。這些聚類(lèi)有效性評(píng)價(jià)內(nèi)部指標(biāo)自身的缺陷，使得其對(duì)于類(lèi)簇結(jié)構(gòu)難以判別，聚類(lèi)有效性檢驗(yàn)效果不理想，很難得到正確的聚類(lèi)結(jié)果和發(fā)現(xiàn)最佳類(lèi)簇?cái)?shù)。針對(duì)現(xiàn)有內(nèi)部評(píng)價(jià)指標(biāo)的上述問(wèn)題，本文利用方差的性質(zhì)，定義類(lèi)內(nèi)距離和類(lèi)間距離，以表達(dá)類(lèi)簇間的分離性與類(lèi)簇內(nèi)的緊促性，提出基于類(lèi)間分離性與類(lèi)內(nèi)緊密性之比的新內(nèi)部評(píng)價(jià)指標(biāo)STDI(standard deviation based index)，以期發(fā)現(xiàn)數(shù)據(jù)集的真實(shí)類(lèi)簇分布結(jié)構(gòu)。

UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)真實(shí)數(shù)據(jù)集和人工模擬的帶有刁難性的及帶有噪音與類(lèi)偏斜的人工模擬數(shù)據(jù)集實(shí)驗(yàn)測(cè)試表明，提出的內(nèi)部評(píng)價(jià)新指標(biāo)STDI能發(fā)現(xiàn)更合理的數(shù)據(jù)集類(lèi)簇?cái)?shù)；提出的分別基于相依表和樣本對(duì)的外部評(píng)價(jià)指標(biāo)S2和PS2可以有效評(píng)價(jià)有類(lèi)偏斜現(xiàn)象的聚類(lèi)結(jié)果。

1 外部指標(biāo)

聚類(lèi)分析中可能遇到如表1所示的極端情況。此時(shí)，若用F-measure指標(biāo)評(píng)價(jià)表1所示極端聚類(lèi)結(jié)果的有效性，將失去意義。因?yàn)?，此時(shí)的F-measure指標(biāo)值是0.67，但實(shí)際聚類(lèi)結(jié)果毫無(wú)意義。導(dǎo)致這種現(xiàn)象的原因是：F-measure是精度和召回率的調(diào)和平均。對(duì)于兩類(lèi)問(wèn)題，F(xiàn)-measure只強(qiáng)調(diào)了聚類(lèi)算法對(duì)正類(lèi)的聚類(lèi)效果，而未考慮聚類(lèi)算法對(duì)負(fù)類(lèi)的聚類(lèi)效果。

表1 極端聚類(lèi)結(jié)果示例Table 1 Rare case of clustering

為了避免此類(lèi)問(wèn)題，本文提出一種基于相依表的、同時(shí)考慮正負(fù)類(lèi)聚類(lèi)結(jié)果的評(píng)價(jià)指標(biāo)S2。S2指標(biāo)調(diào)和了聚類(lèi)算法對(duì)于正負(fù)類(lèi)的聚類(lèi)效果，是靈敏度和特異度的調(diào)和平均。如同F(xiàn)-measure可推廣于多類(lèi)問(wèn)題一樣，S2同樣適用于作為多類(lèi)問(wèn)題的聚類(lèi)評(píng)價(jià)指標(biāo)。

設(shè)聚類(lèi)結(jié)果類(lèi)簇?cái)?shù)為K，原始類(lèi)簇?cái)?shù)為C，則聚類(lèi)結(jié)果相依表是表2所示的C×K矩陣，U是真實(shí)分布，V是聚類(lèi)算法所得聚類(lèi)結(jié)果，則任意類(lèi)簇c的TPc、FNc、FPc、TNc分別定義如式 (1)所示。其中，l為原始類(lèi)標(biāo)信息，L為聚類(lèi)所得類(lèi)標(biāo)信息，n為樣本數(shù)。以類(lèi)簇c為正類(lèi)的sensitivity和specificity定義如式(2)所示。則新聚類(lèi)指標(biāo)S2如式(3)定義。當(dāng)類(lèi)簇?cái)?shù)K=2時(shí)，式(3)的S2指標(biāo)退化為式(4)，其中的sensitivity和specificity同F(xiàn)-measure指標(biāo)在兩類(lèi)問(wèn)題中的定義一致。由此可見(jiàn)，我們定義的新指標(biāo)S2適用于任意類(lèi)的聚類(lèi)問(wèn)題。

表2 聚類(lèi)結(jié)果相依表Table 2 The contingency table of a clustering

外部評(píng)價(jià)指標(biāo)中的Rand index、Adjusted rand index、Jaccard系數(shù)，AMI等均是基于樣本對(duì)的聚類(lèi)評(píng)價(jià)指標(biāo)。因此，本文類(lèi)似地提出基于樣本對(duì)的聚類(lèi)結(jié)果外部評(píng)價(jià)指標(biāo)PS2，調(diào)和聚類(lèi)結(jié)果的正類(lèi)識(shí)別率和負(fù)類(lèi)識(shí)別率，以評(píng)價(jià)聚類(lèi)結(jié)果的有效性。

表3 聚類(lèi)結(jié)果混淆矩陣Table 3 Confusion matrix of a clustering

2 內(nèi)部指標(biāo)

方差作為一種度量樣本分布情況的概率統(tǒng)計(jì)量，通常用來(lái)描述樣本的離散程度[32]。樣本方差越小，樣本分布越密集，反之則越分散。方差的性質(zhì)可以用于計(jì)算類(lèi)內(nèi)距離和類(lèi)間距離，同一類(lèi)簇中樣本分布越密集，方差越小，因此將同一類(lèi)簇中樣本的方差作為類(lèi)內(nèi)距離，度量類(lèi)簇內(nèi)部的緊促性。

基于“類(lèi)內(nèi)盡可能緊密，類(lèi)間盡可能分離”原則，利用方差思想定義度量類(lèi)內(nèi)距離和類(lèi)間距離測(cè)度，類(lèi)間距離越大越好，類(lèi)內(nèi)距離越小越好，提出將類(lèi)間距離與類(lèi)內(nèi)距離之比作為聚類(lèi)效果的內(nèi)部評(píng)價(jià)指標(biāo) STDI(standard deviation based index)，如式 (9)所示。從式(9)STDI的定義可知，其值越大，表明聚類(lèi)結(jié)果越好。

式中：ck是類(lèi)簇k的質(zhì)心，是所有樣本的質(zhì)心，xi是類(lèi)簇k的第i個(gè)樣本，nk是類(lèi)簇k的樣本數(shù)，K是數(shù)據(jù)集的類(lèi)簇?cái)?shù)。STDI指標(biāo)的分子表示各類(lèi)簇間方差，分母表示各類(lèi)簇方差之和。顯然簇內(nèi)方差越小，則分母越小，表示類(lèi)簇內(nèi)部分布越緊密，簇間方差越大，則分子越大，表示各類(lèi)簇的分離性越好。因此，STDI的值越大越好。

3 實(shí)驗(yàn)分析

本節(jié)將分別測(cè)試提出的內(nèi)部指標(biāo)和外部指標(biāo)的性能。因?yàn)槠?，?nèi)部指標(biāo)只使用圖1所示的具有挑戰(zhàn)性的人工模擬數(shù)據(jù)集進(jìn)行測(cè)試，該數(shù)據(jù)集經(jīng)常被識(shí)別為3個(gè)類(lèi)簇。外部評(píng)價(jià)指標(biāo)將使用來(lái)自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)[33]的真實(shí)數(shù)據(jù)集和人工模擬數(shù)據(jù)集兩大類(lèi)數(shù)據(jù)進(jìn)行測(cè)試。其中的人工模擬數(shù)據(jù)包括：類(lèi)簇樣本分布不平衡的偏斜數(shù)據(jù)，以及類(lèi)簇樣本分布平衡但各類(lèi)簇間存在部分交疊的數(shù)據(jù)。這樣設(shè)計(jì)人工模擬數(shù)據(jù)集的目的在于：檢測(cè)提出的外部指標(biāo)S2與PS2對(duì)帶有噪音以及類(lèi)別分布不平衡數(shù)據(jù)聚類(lèi)結(jié)果的判斷能力。測(cè)試外部指標(biāo)的人工模擬數(shù)據(jù)集如圖2所示，表4是圖2各數(shù)據(jù)集的詳細(xì)信息，測(cè)試外部指標(biāo)的UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)的真實(shí)數(shù)據(jù)集如表5所示。

圖1 測(cè)試內(nèi)部指標(biāo)STDI的人工數(shù)據(jù)集原始分布Fig. 1 The synthetic data set to test the new internal criteria STDI

圖2 測(cè)試外部指標(biāo)S2和PS2的人工數(shù)據(jù)集原始分布Fig. 2 The synthetic data sets to test the new external criteria S2 and PS2

表4 測(cè)試新外部指標(biāo)S2和PS2的人工模擬數(shù)據(jù)集信息Table 4 The detail information of synthetic data sets to test the proposed external criteria S2 and PS2

3.1 內(nèi)部指標(biāo)有效性測(cè)試實(shí)驗(yàn)

內(nèi)部指標(biāo)不需要任何先驗(yàn)知識(shí)，通過(guò)評(píng)價(jià)聚類(lèi)結(jié)果，發(fā)現(xiàn)數(shù)據(jù)集樣本的潛在分布與內(nèi)在結(jié)構(gòu)，常用于發(fā)現(xiàn)數(shù)據(jù)集的類(lèi)簇?cái)?shù)。因此，我們以能否準(zhǔn)確發(fā)現(xiàn)數(shù)據(jù)集的真實(shí)類(lèi)簇?cái)?shù)來(lái)測(cè)試提出的內(nèi)部指標(biāo)STDI指標(biāo)的有效性，并與現(xiàn)有內(nèi)部指標(biāo)DB、XB、IGP、Sil和BWP的性能進(jìn)行比較。圖3給出了各內(nèi)部指標(biāo)對(duì)圖1所示人工模擬數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果。這里的聚類(lèi)算法使用的是SD算法[35]。

表5 測(cè)試新外部指標(biāo)S2和PS2的UCI數(shù)據(jù)集Table 5 The data sets from UCI machine learning repository to test the proposed external criteria S2 and PS2

從圖3各指標(biāo)的實(shí)驗(yàn)結(jié)果可以看出，只有圖3(a)展示的STDI指標(biāo)的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)圖1所示人工數(shù)據(jù)集的真實(shí)類(lèi)簇?cái)?shù)9，其余5個(gè)指標(biāo)均在類(lèi)簇?cái)?shù)為3時(shí)最佳，即其余指標(biāo)發(fā)現(xiàn)的該數(shù)據(jù)集類(lèi)簇?cái)?shù)是3。因此，只有用本文提出內(nèi)部聚類(lèi)指標(biāo)STDI可以得到該人工模擬數(shù)據(jù)集的正確類(lèi)簇?cái)?shù)。分析原因是：本文提出的STDI指標(biāo)采用各類(lèi)簇質(zhì)心方差度量類(lèi)間分離程度，用各類(lèi)簇樣本方差度量類(lèi)內(nèi)緊密程度，當(dāng)類(lèi)簇?cái)?shù)為9時(shí)，各類(lèi)簇質(zhì)心方差較大，而簇內(nèi)樣本方差較小，因此得到最佳聚類(lèi)結(jié)果，發(fā)現(xiàn)數(shù)據(jù)集的正確類(lèi)簇?cái)?shù)。由此可見(jiàn)，本文提出的STDI指標(biāo)是非常有效的一種聚類(lèi)評(píng)價(jià)指標(biāo)。

圖3 各內(nèi)部指標(biāo)在人工數(shù)據(jù)集的測(cè)試結(jié)果Fig. 3 The results on synthetic data set of internal criteria

3.2 外部指標(biāo)有效性測(cè)試實(shí)驗(yàn)

本小節(jié)對(duì)提出的2種聚類(lèi)有效性評(píng)價(jià)外部指標(biāo)S2和PS2進(jìn)行測(cè)試，聚類(lèi)算法選取快速K-medoids算法[35]。為了充分說(shuō)明提出的外部評(píng)價(jià)指標(biāo)S2和PS2的有效性，特別設(shè)計(jì)了帶有噪音，類(lèi)簇分布平衡和不平衡的人工模擬數(shù)據(jù)集，并選擇了來(lái)自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)的樣本數(shù)、類(lèi)簇?cái)?shù)和各類(lèi)簇樣本規(guī)模各異的真實(shí)數(shù)據(jù)集來(lái)進(jìn)行測(cè)試，同時(shí)將提出的S2和PS2指標(biāo)與聚類(lèi)準(zhǔn)確率Accuracy，以及經(jīng)典外部評(píng)價(jià)指標(biāo)F-measure、Rand index、Jaccard系數(shù)和ARI的指標(biāo)值進(jìn)行比較。

圖2和表4所示人工模擬數(shù)據(jù)集的類(lèi)簇?cái)?shù)從2～6，類(lèi)簇?cái)?shù)相同的人工模擬數(shù)據(jù)集包括兩類(lèi)：類(lèi)簇樣本數(shù)均衡，但簇間樣本重疊的情況；類(lèi)簇樣本數(shù)不平衡，即存在類(lèi)簇偏斜，簇間樣本重疊或很少量重疊的情況。這樣的人工模擬數(shù)據(jù)集將測(cè)試提出的外部評(píng)價(jià)指標(biāo)S2和PS2對(duì)存在類(lèi)偏斜或樣本重疊分布的數(shù)據(jù)聚類(lèi)結(jié)果的評(píng)價(jià)情況。表5來(lái)自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)的12個(gè)真實(shí)數(shù)據(jù)集的樣本數(shù)，類(lèi)簇?cái)?shù)和類(lèi)簇樣本分布也各不相同。這些真實(shí)數(shù)據(jù)集將進(jìn)一步檢測(cè)提出的外部評(píng)價(jià)指標(biāo)S2和PS2的有效性。

為了清楚展示S2和PS2指標(biāo)的性能，分別將S2和PS2的實(shí)驗(yàn)測(cè)試結(jié)果與聚類(lèi)準(zhǔn)確率Accuracy，經(jīng)典外部評(píng)價(jià)指標(biāo)F-measure、Rand index、Jaccard系數(shù)和ARI指數(shù)進(jìn)行比較，并將S2和PS2指標(biāo)與聚類(lèi)準(zhǔn)確率獨(dú)立比較。圖4展示了S2指標(biāo)在人工模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集的測(cè)試結(jié)果與其他指標(biāo)的比較。圖5給出了PS2指標(biāo)的實(shí)驗(yàn)測(cè)試結(jié)果與其他指標(biāo)的比較。S2與PS2的性能比較如圖6所示，圖6同時(shí)展示了聚類(lèi)準(zhǔn)確率指標(biāo)。圖4和圖5中的R是Rand index的簡(jiǎn)寫(xiě)。

圖4 S2指標(biāo)與其他指標(biāo)的測(cè)試結(jié)果比較Fig. 4 The comparison of S2 with other criteria

圖5 PS2指標(biāo)的測(cè)試結(jié)果與其他指標(biāo)的比較Fig. 5 The comparison of PS2 with other criteria

圖6 S2與PS2指標(biāo)與聚類(lèi)準(zhǔn)確率比較Fig. 6 The comparison of S2 and PS2 and clustering accuracy

圖4 (a)人工模擬數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果揭示，除了含有6個(gè)不平衡類(lèi)簇的人工模擬數(shù)據(jù)集外，本文提出的同時(shí)考慮正負(fù)類(lèi)信息的聚類(lèi)有效性評(píng)價(jià)指標(biāo)S2與其他指標(biāo)相比具有最高值，且與其他指標(biāo)在各數(shù)據(jù)集測(cè)試的指標(biāo)值走勢(shì)一致。因此，可以說(shuō)提出的S2指標(biāo)可以有效評(píng)價(jià)存在類(lèi)偏斜分布的聚類(lèi)結(jié)果。圖4(b)所示的UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)測(cè)試結(jié)果顯示，提出的外部評(píng)價(jià)指標(biāo)S2在12個(gè)真實(shí)數(shù)據(jù)集的指標(biāo)值只有在Segmentation和Bupa兩個(gè)數(shù)據(jù)集的測(cè)試指標(biāo)值不是最高，在其余10個(gè)真實(shí)數(shù)據(jù)集的測(cè)試結(jié)果值均高于聚類(lèi)準(zhǔn)確率Accuracy，以及經(jīng)典外部指標(biāo)Rand index指數(shù)，ARI，Jaccard系數(shù)和F-measure。另外，提出的S2指標(biāo)在各真實(shí)數(shù)據(jù)集的測(cè)試值與Accuracy，Jaccard，ARI和F-measure各指標(biāo)值的走勢(shì)基本一致，但與Rand index指標(biāo)不太一致。圖4(a)和(b)的實(shí)驗(yàn)結(jié)果共同揭示，提出的S2指標(biāo)的測(cè)試值與聚類(lèi)準(zhǔn)確率Accuracy，外部指標(biāo)F-measure，Rand index指數(shù)，ARI和Jaccard系數(shù)在各數(shù)據(jù)集的基本走勢(shì)大體一致。當(dāng)前最優(yōu)的外部評(píng)價(jià)指標(biāo)ARI在各指標(biāo)值中位居后兩位，特別是在真實(shí)數(shù)據(jù)集，ARI特別突出的位于后兩位。這更進(jìn)一步說(shuō)明了提出的同時(shí)考慮正負(fù)類(lèi)信息的外部評(píng)價(jià)指標(biāo)S2的有效性。

圖5(a)人工模擬數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果顯示，除了含有6個(gè)不平衡類(lèi)簇的人工模擬數(shù)據(jù)集，提出的基于樣本對(duì)信息，同時(shí)考慮正負(fù)類(lèi)信息的外部評(píng)價(jià)指標(biāo)PS2在其他人工模擬數(shù)據(jù)集的指標(biāo)值基本與聚類(lèi)準(zhǔn)確率重合，或略低于聚類(lèi)準(zhǔn)確率，但走勢(shì)一致。圖5(b)真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果顯示，提出的PS2指標(biāo)低于或等于聚類(lèi)準(zhǔn)確率，聚類(lèi)準(zhǔn)確率或Rand index指數(shù)在真實(shí)數(shù)據(jù)集的測(cè)試結(jié)果高于等于提出的PS2指標(biāo)。當(dāng)前最佳聚類(lèi)評(píng)價(jià)指標(biāo)ARI在帶有噪音和類(lèi)簇分布不平衡的人工模擬數(shù)據(jù)集，以及樣本規(guī)模，類(lèi)簇?cái)?shù)和各類(lèi)簇樣本規(guī)模變化各異的真實(shí)數(shù)據(jù)集的測(cè)試結(jié)果與其他指標(biāo)相比，取值較低，在6個(gè)比較指標(biāo)中居后兩位。

圖6(a)人工模擬數(shù)據(jù)集實(shí)驗(yàn)結(jié)果顯示，除了在含有6個(gè)不平衡類(lèi)簇的人工模擬數(shù)據(jù)集的S2指標(biāo)低于PS2指標(biāo)和聚類(lèi)準(zhǔn)確率外，在其余人工模擬數(shù)據(jù)集上，S2指標(biāo)的指標(biāo)值均高于PS2指標(biāo)，聚類(lèi)準(zhǔn)確率居中。圖6(b)真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果顯示，在真實(shí)數(shù)據(jù)集的S2指標(biāo)明顯高于PS2指標(biāo)值。真實(shí)數(shù)據(jù)集的聚類(lèi)準(zhǔn)確率Accuracy除了在Bupa數(shù)據(jù)集高于S2和PS2指標(biāo)，在Segmentation數(shù)據(jù)集低于S2和PS2指標(biāo)外，在其余數(shù)據(jù)集的聚類(lèi)準(zhǔn)確率均低于等于S2指標(biāo)，但高于PS2指標(biāo)。聚類(lèi)分析的目的是發(fā)現(xiàn)數(shù)據(jù)集的正確類(lèi)簇分布。圖6(a)～(b)的實(shí)驗(yàn)結(jié)果揭示，提出的分別基于相依表和樣本對(duì)，且同時(shí)考慮正負(fù)類(lèi)信息的外部評(píng)價(jià)指標(biāo)S2和PS2均能正確評(píng)價(jià)聚類(lèi)結(jié)果的有效性，其走勢(shì)與聚類(lèi)準(zhǔn)確率大體一致。其中，S2指標(biāo)的走勢(shì)更趨近于聚類(lèi)準(zhǔn)確率。

4 結(jié)束語(yǔ)

聚類(lèi)作為無(wú)監(jiān)督學(xué)習(xí)，是大數(shù)據(jù)集背景下知識(shí)發(fā)現(xiàn)的重要方法之一。聚類(lèi)學(xué)習(xí)結(jié)果的有效性評(píng)價(jià)是聚類(lèi)分析不可或缺的重要組成部分?，F(xiàn)有聚類(lèi)評(píng)價(jià)指標(biāo)的外部評(píng)價(jià)指標(biāo)側(cè)重于正類(lèi)，對(duì)聚類(lèi)結(jié)果類(lèi)偏斜問(wèn)題缺少考慮，為此，提出了分別基于相依表和樣本對(duì)的，同時(shí)考慮正負(fù)類(lèi)信息的外部評(píng)價(jià)新指標(biāo)S2和PS2。另外，針對(duì)現(xiàn)有內(nèi)部評(píng)價(jià)指標(biāo)在發(fā)現(xiàn)數(shù)據(jù)集最佳類(lèi)簇?cái)?shù)方面的局限，提出了基于方差的類(lèi)內(nèi)緊密度和類(lèi)間分離性度量，定義了以類(lèi)間分離性與類(lèi)內(nèi)緊密度之比為度量指標(biāo)的內(nèi)部評(píng)價(jià)新指標(biāo)STDI。UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)真實(shí)數(shù)據(jù)集和帶有刁難性的人工模擬數(shù)據(jù)集實(shí)驗(yàn)測(cè)試表明，提出的新內(nèi)部指標(biāo)STDI能有效發(fā)現(xiàn)數(shù)據(jù)集的真實(shí)類(lèi)簇?cái)?shù)；提出的外部指標(biāo)S2和PS2是非常有效的聚類(lèi)有效性外部評(píng)價(jià)指標(biāo)，可有效評(píng)價(jià)存在類(lèi)偏斜與噪音數(shù)據(jù)的聚類(lèi)結(jié)果。

[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]謝娟英. 無(wú)監(jiān)督學(xué)習(xí)方法及其應(yīng)用[M]. 北京: 電子工業(yè)出版社, 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 近鄰優(yōu)化的密度峰值快速搜索聚類(lèi)算法[J]. 中國(guó)科學(xué): 信息科學(xué), 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]謝娟英, 周穎. 一種新聚類(lèi)評(píng)價(jià)指標(biāo)[J]. 陜西師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 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]周世兵, 徐振源, 唐旭清. 一種基于近鄰傳播算法的最佳聚類(lèi)數(shù)確定方法[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]盛驟, 謝式千. 概率論與數(shù)理統(tǒng)計(jì)及其應(yīng)用[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]謝娟英, 高瑞. 方差優(yōu)化初始中心的K-medoids聚類(lèi)算法[J]. 計(jì)算機(jī)科學(xué)與探索, 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.