自動(dòng)確定聚類中心的勢(shì)能聚類算法*

于曉飛，葛洪偉,2+

1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122

2.江南大學(xué) 輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214122

1 引言

聚類算法是數(shù)據(jù)挖掘中的重要分支，是在沒有關(guān)于潛在數(shù)據(jù)分布的先驗(yàn)知識(shí)情況下，通過(guò)某種相似性度量和聚類準(zhǔn)則對(duì)數(shù)據(jù)進(jìn)行聚集。聚類分析在許多領(lǐng)域有著重要的作用，包括生物學(xué)、人工智能、客戶關(guān)系管理、信息檢索、機(jī)器學(xué)習(xí)等[1-3]。

然而，現(xiàn)在有許多應(yīng)用廣泛的聚類算法無(wú)法自動(dòng)確定聚類數(shù)目。如基于劃分的K-means[4-5]，該算法需人工設(shè)定聚類數(shù)目而且對(duì)初始類簇中心有很大的依賴；基于層次的聚類方法如CURE（clustering using representatives）[6-7]、Chameleon[8]等，這些算法可以發(fā)現(xiàn)任意形狀的簇，但均不能在無(wú)輸入?yún)?shù)的條件下自動(dòng)確定聚類數(shù)目；基于密度的聚類方法如DBSCAN（density-based spatial clustering of applications with noise）[9]、OPTICS（ordering points to identify the clustering structure）[10]等，這些算法雖有較好的聚類效果，但也不能自動(dòng)確定聚類數(shù)目，在具體實(shí)踐中影響了算法的應(yīng)用效果。

目前，有許多學(xué)者針對(duì)自動(dòng)確定聚類數(shù)目的問題進(jìn)行了研究。如Rodriguze等人[11]于2014年提出的密度峰算法（density peaks clustering，DPC），該算法雖然無(wú)需提前設(shè)置聚類數(shù)目，但要通過(guò)決策圖來(lái)人工選取聚類中心。針對(duì)這一缺陷，李濤等人[12]對(duì)密度峰算法進(jìn)行了改進(jìn)，改進(jìn)后的算法雖然可以自動(dòng)確定聚類數(shù)目，但在聚類中心點(diǎn)判斷時(shí)，對(duì)參數(shù)dc（截?cái)嗑嚯x）的依賴很大。顯然，如何使相關(guān)算法能在沒有參數(shù)依賴的前提下自動(dòng)確定聚類數(shù)目是頗具現(xiàn)實(shí)意義的研究課題。

Lu等人[13]提出一種基于勢(shì)能的聚類算法（clustering by sorting potential values，CSPV），該算法雖提出了基于勢(shì)能的相似性度量準(zhǔn)則，但聚類效果完全依賴于對(duì)參數(shù)B的選取。針對(duì)這一問題，Lu等人于2013年[14]提出了一種基于勢(shì)能的快速凝聚層次聚類方法（potential-based hierarchical agglomerative clustering，PHA）。該算法首先依據(jù)各點(diǎn)的勢(shì)能和與父節(jié)點(diǎn)的距離構(gòu)造邊緣加權(quán)樹，最后通過(guò)人為設(shè)定的聚類數(shù)目使用層次聚類算法得到最終的聚類結(jié)果。PHA算法使用基于勢(shì)能的相似性度量準(zhǔn)則，在時(shí)間上更快速，在過(guò)程上更便捷，在精度上可以得到更好的聚類效果。

然而PHA算法需要提前設(shè)定聚類數(shù)目，而且在確定數(shù)據(jù)點(diǎn)類別的機(jī)制上，使用了層次聚類方法，僅考慮距離的作用，忽視了勢(shì)能的影響。針對(duì)上述問題，本文提出了一種自動(dòng)確定聚類中心的勢(shì)能聚類算法（automatically clustering based on potential metric，ACP）。首先，通過(guò)計(jì)算各數(shù)據(jù)點(diǎn)的勢(shì)能和其到父節(jié)點(diǎn)距離的乘積，并通過(guò)區(qū)分聚類中心點(diǎn)和非聚類中心點(diǎn)，實(shí)現(xiàn)自動(dòng)確定聚類數(shù)目的目的；其次，綜合考慮勢(shì)能和距離兩個(gè)因素對(duì)非聚類中心點(diǎn)進(jìn)行分類。在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)證明，與PHA算法相比，本文ACP算法不僅可以自動(dòng)準(zhǔn)確地確定聚類數(shù)目，而且具有更優(yōu)的聚類效果。

2 PHA算法及其缺陷分析

PHA算法[14]認(rèn)為，數(shù)據(jù)點(diǎn)的勢(shì)能大小與其概率密度分布是密切相關(guān)的。該算法首先根據(jù)重力勢(shì)能的物理意義來(lái)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的勢(shì)能。每?jī)牲c(diǎn)之間的勢(shì)能Φij定義如下：

其中，rij是點(diǎn)i與點(diǎn)j之間的歐式距離；δ用來(lái)避免分母為0的情況出現(xiàn)。δ計(jì)算方式為：

其中，MinDi是點(diǎn)i到其他各點(diǎn)的最短距離；S是一個(gè)尺度因子[14]，一般設(shè)為10；mean為求均值的函數(shù)；N是數(shù)據(jù)點(diǎn)的個(gè)數(shù)。計(jì)算了每?jī)牲c(diǎn)之間的勢(shì)能Φij后，每個(gè)點(diǎn)的勢(shì)能Φi定義為：

文獻(xiàn)[14]使用Parzen窗口函數(shù)[15]這一非參數(shù)估計(jì)方法來(lái)證明勢(shì)能和概率密度分布的關(guān)系。在Parzen窗口函數(shù)中概率密度的定義如下：

文獻(xiàn)[14]經(jīng)過(guò)證明得到：

即勢(shì)能和概率密度函數(shù)成反比。因此，勢(shì)能可以反映數(shù)據(jù)點(diǎn)的分布情況，如勢(shì)能越小的點(diǎn)的周圍數(shù)據(jù)點(diǎn)分布越密集。

將勢(shì)能從小到大排序，并以勢(shì)能最小的點(diǎn)作為根節(jié)點(diǎn)，構(gòu)造邊緣加權(quán)樹，其他數(shù)據(jù)點(diǎn)尋找自身的父節(jié)點(diǎn)。其中，父節(jié)點(diǎn)定義為：

即勢(shì)能小于點(diǎn)i且與i距離最近的點(diǎn)為其父節(jié)點(diǎn)。點(diǎn)i到父節(jié)點(diǎn)parent[i]的距離ρi為：

對(duì)于勢(shì)能最小的點(diǎn)i，其ρi=max(ri,j|j≠i)。在邊緣加權(quán)樹中，每個(gè)數(shù)據(jù)點(diǎn)與父節(jié)點(diǎn)之間的權(quán)值為兩者的距離。在樹構(gòu)造完成后，使用凝聚層次聚類算法進(jìn)行聚類，得到聚類結(jié)果。

PHA算法雖然十分便捷快速，但由于需要提前設(shè)定聚類數(shù)目，而且在使用層次聚類方法來(lái)確定數(shù)據(jù)點(diǎn)的類別時(shí)，沒有考慮勢(shì)能的影響。因?yàn)槿藗冴P(guān)于數(shù)據(jù)集的先驗(yàn)知識(shí)的了解是有限的，人為確定聚類數(shù)目往往有較大的困難，所以如何使該算法能自動(dòng)確定聚類數(shù)目且采用更好的分配機(jī)制是值得研究的課題。

3 自動(dòng)確定聚類中心的勢(shì)能聚類算法

3.1 聚類中心的自動(dòng)確定

基于對(duì)重力勢(shì)能物理意義的分析發(fā)現(xiàn)，勢(shì)能在分布上表現(xiàn)出類似年輪的特點(diǎn)，即數(shù)據(jù)點(diǎn)的勢(shì)能隨著層數(shù)的增大而增大。中心數(shù)據(jù)點(diǎn)的勢(shì)能最小，最外層數(shù)據(jù)點(diǎn)的勢(shì)能最大。如圖1所示。

Fig.1 Graph of potential field圖1 勢(shì)能分布圖示例

A、B、C、D、E這5個(gè)點(diǎn)的勢(shì)能最小，而且在每個(gè)單獨(dú)的類簇中，沿著中心點(diǎn)向外，數(shù)據(jù)點(diǎn)所處層數(shù)越高勢(shì)能越大。并且A、B、C、D、E這5個(gè)點(diǎn)作為類中心，相互之間的距離相對(duì)較大。

Fig.2 Analysis of determining cluster center by potential圖2 勢(shì)能確定聚類中心的分析

然而，僅以數(shù)據(jù)點(diǎn)的勢(shì)能大小為依據(jù)不能確定聚類中心。以圖2（a）所示的數(shù)據(jù)集為例，該數(shù)據(jù)集的勢(shì)能分布如圖2（b）所示。由圖可見，各點(diǎn)勢(shì)能大小的差異不足以直接區(qū)分聚類中心點(diǎn)與非聚類中心點(diǎn)。而且，有些數(shù)據(jù)點(diǎn)雖然勢(shì)能很小，但與其他勢(shì)能更小或勢(shì)能相等的數(shù)據(jù)點(diǎn)的距離較小，因此在數(shù)據(jù)分布圖上不是聚類中心點(diǎn)，而是距離聚類中心較近的數(shù)據(jù)點(diǎn)。可見，單獨(dú)以勢(shì)能的影響為依據(jù)無(wú)法直接確定聚類中心。

僅以與父節(jié)點(diǎn)的距離為依據(jù)同樣無(wú)法確定聚類中心。如圖3（a）所示，該圖表示各點(diǎn)的ρ值分布。若以此來(lái)區(qū)分聚類中心點(diǎn)和非聚類中心點(diǎn)，直觀來(lái)看，會(huì)得到A、B、C、D共4個(gè)聚類中心，但該數(shù)據(jù)集僅有A、B兩個(gè)聚類中心，因此會(huì)導(dǎo)致錯(cuò)誤的聚類結(jié)果。這是由于有些數(shù)據(jù)點(diǎn)與父節(jié)點(diǎn)的距離很大，但其勢(shì)能也很大，在數(shù)據(jù)點(diǎn)分布圖上其周圍數(shù)據(jù)點(diǎn)的密度較小，則不能作為聚類中心點(diǎn)。可見，單獨(dú)考慮距離的影響也無(wú)法準(zhǔn)確地確定聚類中心。

Fig.3 Graph of distance andγidistribution圖3 距離與γi值的分布圖

通過(guò)上述分析得出結(jié)論，聚類中心點(diǎn)應(yīng)具備兩個(gè)特點(diǎn)：（1）相對(duì)較小的勢(shì)能Φi；（2）較大的與父節(jié)點(diǎn)的距離ρi。基于以上發(fā)現(xiàn)，在確定聚類中心的過(guò)程中應(yīng)同時(shí)考慮勢(shì)能和與父節(jié)點(diǎn)的距離兩個(gè)因素。

定義1γi是評(píng)價(jià)數(shù)據(jù)點(diǎn)為聚類中心可能性的指標(biāo)：

由于勢(shì)能Φi恒為負(fù)數(shù)，勢(shì)能越小，其絕對(duì)值越大。故取勢(shì)能的絕對(duì)值與距離的乘積作為評(píng)判聚類中心可能性的尺度。數(shù)據(jù)點(diǎn)的γi值越大，是聚類中心點(diǎn)的可能性越大。

圖3（b）為圖2（a）中數(shù)據(jù)集的各點(diǎn)γi值分布圖，圖中橫坐標(biāo)代表每個(gè)數(shù)據(jù)點(diǎn)的γi值，為了使數(shù)據(jù)點(diǎn)在圖上處于中間位置方便觀察，設(shè)置縱坐標(biāo)為0。從圖3（b）可以看出，聚類中心點(diǎn)與非聚類中心點(diǎn)的γi值具有明顯差異：非聚類中心點(diǎn)的數(shù)目較多且其γi值集中分布在一個(gè)區(qū)間內(nèi)，而聚類中心點(diǎn)的數(shù)目較少，且彼此分布得相對(duì)比較分散；另外，聚類中心的γi值也明顯大于非聚類中心的γi值。

基于上述發(fā)現(xiàn)與分析，可以根據(jù)γi值的分布圖明顯地將聚類中心點(diǎn)和非聚類中心點(diǎn)區(qū)別開來(lái)，直接確定聚類中心：即根據(jù)γi值，使用簡(jiǎn)單高效的分類或聚類方法區(qū)分聚類中心點(diǎn)和非聚類中心點(diǎn)兩類，如回歸分析離群點(diǎn)檢測(cè)、K-means算法或其他更好的方法。在此過(guò)程中，將數(shù)據(jù)點(diǎn)較少的那一類作為聚類中心點(diǎn)，如圖3（b）中的A、B。至此ACP算法在沒有人為設(shè)定聚類數(shù)目的條件下能夠自動(dòng)確定聚類中心。

聚類中心確定后，應(yīng)根據(jù)算法的分配機(jī)制對(duì)剩余數(shù)據(jù)點(diǎn)進(jìn)行類別確定。PHA算法僅依據(jù)數(shù)據(jù)點(diǎn)相互之間的距離大小來(lái)確定其類別，這會(huì)導(dǎo)致某一類中的邊緣數(shù)據(jù)點(diǎn)由于與其他類的邊緣數(shù)據(jù)點(diǎn)距離更近而錯(cuò)誤地分配到了其他類中。這種情況在類似DS2的數(shù)據(jù)集中表現(xiàn)顯著。而本文ACP算法綜合考慮距離和勢(shì)能兩個(gè)因素，對(duì)于剩余樣本j，將其歸入勢(shì)能比j小且距離j最近的樣本所在類簇，即依次分配到與自身父節(jié)點(diǎn)相同的類別中去，直到所有數(shù)據(jù)點(diǎn)的類別都確定為止。由于增加勢(shì)能的限制，在數(shù)據(jù)點(diǎn)的類別分配上就會(huì)更加嚴(yán)格。如圖1所示，勢(shì)能越小說(shuō)明周圍數(shù)據(jù)點(diǎn)越密集，那么在此基礎(chǔ)上，距離這種勢(shì)能相對(duì)小的點(diǎn)越近則越能確認(rèn)兩者為相同類。ACP算法在該數(shù)據(jù)集上的聚類結(jié)果見4.2.1節(jié)中介紹。

綜上所述，ACP算法不僅可以自動(dòng)確定聚類中心，而且在分配機(jī)制上同時(shí)考慮了勢(shì)能和距離兩個(gè)因素，在一定程度上改進(jìn)了PHA算法需人為設(shè)定聚類數(shù)目和分配機(jī)制上僅考慮距離的兩個(gè)缺陷。

3.2 ACP算法步驟

ACP算法流程簡(jiǎn)單描述如下：

步驟1由式（1）到式（4）求出每個(gè)數(shù)據(jù)點(diǎn)的勢(shì)能Φi，由式（7）找出每個(gè)數(shù)據(jù)點(diǎn)的父節(jié)點(diǎn)parent[i]，并由式（8）計(jì)算數(shù)據(jù)點(diǎn)到父節(jié)點(diǎn)的距離ρi。

步驟2根據(jù)式（9）計(jì)算各點(diǎn)的γi值。

步驟3根據(jù)步驟2中各點(diǎn)的γi值，在一維特征空間中，使用K-means算法對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分類，K值恒為2，并選取數(shù)據(jù)點(diǎn)少的一類作為聚類中心集。

步驟4確定聚類中心后，每個(gè)聚類中心各代表一類，標(biāo)記為{1,2,…,C}，C表示數(shù)據(jù)集的類別總數(shù)。

步驟5將剩余數(shù)據(jù)點(diǎn)歸入勢(shì)能比其小且與其距離最近的樣本所在類簇，即與自身的父節(jié)點(diǎn)劃為一類，并標(biāo)記相同的類標(biāo)簽，直到所有數(shù)據(jù)點(diǎn)的類別都確定為止。

3.3 算法復(fù)雜度分析

假設(shè)聚類對(duì)象有n個(gè)數(shù)據(jù)，本文ACP算法的時(shí)間復(fù)雜度主要是由計(jì)算勢(shì)能和距離及對(duì)γi值分類時(shí)產(chǎn)生的。ACP算法在計(jì)算勢(shì)能時(shí)的時(shí)間復(fù)雜度為O(n2)，計(jì)算距離時(shí)的時(shí)間復(fù)雜度為O(n)，在對(duì)γi值分類時(shí)的時(shí)間復(fù)雜度為O(n)，因此ACP算法的時(shí)間復(fù)雜度為O(n2)。文獻(xiàn)[14]指出，PHA算法的時(shí)間復(fù)雜度主要是由構(gòu)建邊緣加權(quán)樹以及通過(guò)樹狀圖進(jìn)行層次聚類所產(chǎn)生的。其中，構(gòu)建邊緣加權(quán)樹時(shí)的時(shí)間復(fù)雜度為O(n2)，通過(guò)樹狀圖層次聚類時(shí)的時(shí)間復(fù)雜度為O(n2)，因此PHA算法的時(shí)間復(fù)雜度為O(n2)[14]。可見，本文在沒有提升算法復(fù)雜度的同時(shí)，不僅解決了PHA算法如何自動(dòng)確定聚類數(shù)目的問題，而且完善了樣本分配機(jī)制，提高了聚類效果。

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

4.1 聚類結(jié)果評(píng)價(jià)

實(shí)驗(yàn)中使用Fowlkes-Mallows index（FMIndex）[16]、F1-measure[17]和 ARI（adjusted Rand index）[18]3 個(gè)聚類評(píng)價(jià)指標(biāo)來(lái)對(duì)算法進(jìn)行對(duì)比。其中FMIndex的定義如下：

假設(shè)給定兩個(gè)不同的聚類結(jié)果R1和R2，TP表示在R1、R2中都為相同類的數(shù)據(jù)點(diǎn)個(gè)數(shù)；FP表示在R1中是相同類在R2中不是相同類的數(shù)據(jù)點(diǎn)個(gè)數(shù)；FN表示在R2中是相同類在R1中不是相同類的數(shù)據(jù)點(diǎn)個(gè)數(shù)。FM值介于0~1之間，越接近0聚類效果越差，越接近1聚類效果越好。F1-measure和ARI為兩個(gè)常用的聚類評(píng)價(jià)指標(biāo)，這里不再詳細(xì)介紹。

4.2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證ACP算法的性能，分別在人工數(shù)據(jù)集和UCI[19]數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。

4.2.1 人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析

表1中DS1由3組服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)構(gòu)成，各組的中心數(shù)據(jù)點(diǎn)分別為（0,0）、（3,5）和（6,0），每組有300個(gè)數(shù)據(jù)。DS2由4組服從正態(tài)分布且期望值均為0的隨機(jī)數(shù)構(gòu)成，第一組是200個(gè)數(shù)據(jù)點(diǎn)，標(biāo)準(zhǔn)差為2，中心在（0,0）；第二組是400個(gè)數(shù)據(jù)點(diǎn)，標(biāo)準(zhǔn)差為3，中心在（6,13）；第三組是800個(gè)數(shù)據(jù)點(diǎn)，標(biāo)準(zhǔn)差為4，中心在（12,0）；第四組是200個(gè)數(shù)據(jù)點(diǎn)，標(biāo)準(zhǔn)差為2，中心在（16,11）。DS3由兩組服從二元正態(tài)分布的隨機(jī)數(shù)構(gòu)成，每組有500個(gè)數(shù)據(jù)點(diǎn)，且x的標(biāo)準(zhǔn)差均為1，y的標(biāo)準(zhǔn)差均為5，期望均為0，協(xié)方差均為0。第一組數(shù)據(jù)點(diǎn)中心是（0,0），第二組數(shù)據(jù)點(diǎn)中心為（5,0）。

Table 1 4 artificial data sets表1 4個(gè)人工數(shù)據(jù)集信息

基于歐氏距離測(cè)度，分別使用CSPV、PHA、ACP和DPC算法在表1中的人工數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，其中圖4為ACP算法在各數(shù)據(jù)集上得到的γi值分布圖，圖上的A、B、C、D字母表示該算法在各數(shù)據(jù)集上得到的聚類中心。圖5、圖6、圖7分別為ACP、PHA和CSPV算法得到的實(shí)驗(yàn)結(jié)果（由于DPC算法得到的實(shí)驗(yàn)結(jié)果圖與PHA算法相似，在此不一一列出）。實(shí)驗(yàn)后4種算法得到的3種聚類評(píng)價(jià)指標(biāo)值對(duì)比如表2~表4所示。

圖4、圖5表明，ACP算法在上述4個(gè)人工數(shù)據(jù)集上均可準(zhǔn)確地確定聚類數(shù)目并得到理想的聚類結(jié)果。表2~表4表明，在DS2、DS3兩個(gè)數(shù)據(jù)集上，ACP算法的FM聚類評(píng)價(jià)指標(biāo)值均高于PHA算法，F(xiàn)1-measure、ARI兩個(gè)聚類評(píng)價(jià)指標(biāo)值與PHA算法相等；在DS1、Spiral兩個(gè)數(shù)據(jù)集上，雖然兩種算法的精確度相等，如Spiral數(shù)據(jù)集的精確值均達(dá)到了1，但ACP算法可以自動(dòng)確定出正確的聚類數(shù)目并得到上述的聚類結(jié)果，而PHA算法需在人工設(shè)定正確的聚類數(shù)目前提下，才能夠得到與ACP算法相等的聚類精確度。

Fig.4 Graph ofγidistribution on artificial data sets圖4 人工數(shù)據(jù)集的γi值分布圖

Fig.5 Clustering result on artificial data sets byACP圖5ACP在人工數(shù)據(jù)集的聚類結(jié)果

Fig.6 Clustering result on artificial data sets by PHA圖6 PHA在人工數(shù)據(jù)集的聚類結(jié)果

Fig.7 Clustering result on artificial data sets by CSPV圖7 CSPV在人工數(shù)據(jù)集的聚類結(jié)果

Table 2 FM index values of 4 methods on artificial data sets表2 4種算法在人工數(shù)據(jù)集上的FM值

Table 3 F1-measure index values of 4 methodson artificial data sets表3 4種算法在人工數(shù)據(jù)集上的F1-measure值

Table 4 ARI index values of 4 methods on artificial data sets表4 4種算法在人工數(shù)據(jù)集上的ARI值

在DS2、Spiral兩個(gè)數(shù)據(jù)集上，ACP算法的3個(gè)評(píng)價(jià)指標(biāo)值均高于CSPV算法，其余兩個(gè)數(shù)據(jù)集上二者相等。DPC算法在DS3、Spiral兩個(gè)數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)值與ACP算法相等；在DS1、DS2兩個(gè)數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)值雖然略高于ACP算法，但該算法需多次實(shí)驗(yàn)并選擇最優(yōu)的dc值才可得到理想的實(shí)驗(yàn)結(jié)果，而ACP算法不需任何輸入?yún)?shù)，且對(duì)參數(shù)沒有依賴，在任何情況下得到的實(shí)驗(yàn)結(jié)果都是相同的。

整體而言，ACP算法不僅可以自動(dòng)確定聚類數(shù)目，而且更為有效的分配機(jī)制使得算法能夠得到更優(yōu)的聚類效果。

4.2.2 真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析

為了進(jìn)一步驗(yàn)證ACP算法性能，基于歐式距離，分別用CSPV、PHA、ACP和DPC算法對(duì)表5中來(lái)自UCI[19]的真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，并用3個(gè)聚類評(píng)價(jià)指標(biāo)FM、F1-measure、ARI對(duì)4種算法的聚類結(jié)果進(jìn)行評(píng)價(jià)，實(shí)驗(yàn)結(jié)果如表6~表8所示。由于DPC算法對(duì)dc值有依賴，表6~表8所列的各評(píng)價(jià)指標(biāo)值均取DPC算法多次實(shí)驗(yàn)的最優(yōu)值。

Table 5 4 real data sets表5 4個(gè)真實(shí)數(shù)據(jù)集信息

Table 6 FM index values of 4 methods on real data sets表6 4種算法在真實(shí)數(shù)據(jù)集上的FM值

Table 7 F1-measure index values of 4 methods on real data sets表7 4種算法在真實(shí)數(shù)據(jù)集上的F1-measure值

Table 8 ARI index values of 4 methods on real data sets表8 4種算法在真實(shí)數(shù)據(jù)集上的ARI值

從表6~表8可以看出，在iris和letter數(shù)據(jù)集上，ACP算法的3個(gè)聚類評(píng)價(jià)指標(biāo)值均高于PHA算法；在seeds數(shù)據(jù)集上，雖然兩者的3個(gè)聚類評(píng)價(jià)指標(biāo)值相等，但ACP算法能夠自動(dòng)確定3個(gè)類別，而PHA算法需人為設(shè)定聚類數(shù)目；而在vehicle數(shù)據(jù)集上，雖然PHA的F1-measure值高于ACP算法，但在FM和ARI兩個(gè)評(píng)價(jià)指標(biāo)上，ACP算法要高于PHA算法。

在iris數(shù)據(jù)集上，ACP算法的3個(gè)聚類評(píng)價(jià)指標(biāo)值均高于CSPV算法，與DPC算法相等；在letter數(shù)據(jù)集上，3種算法取得的3個(gè)指標(biāo)值相同；在seeds數(shù)據(jù)集上，ACP算法的FM值最大，F(xiàn)1-measure值略低于DPC算法但高于CSPV算法，ARI值略低于DPC算法；在vehicle數(shù)據(jù)集上，ACP算法的FM值最大，F(xiàn)1-measure值略低于CSPV算法，ARI值略低于CSPV算法但高于DPC算法。

上述結(jié)果表明，整體而言，在真實(shí)數(shù)據(jù)集上，當(dāng)取得相似聚類結(jié)果時(shí)，ACP算法有效避免了PHA算法需要人工指定聚類數(shù)目的缺陷，也不存在CSPV、DPC兩種算法對(duì)參數(shù)具有依賴性的問題；另外，ACP算法改善的樣本分配機(jī)制使得其能夠取得比PHA算法更優(yōu)的聚類結(jié)果。

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

針對(duì)PHA算法不能自動(dòng)確定聚類數(shù)目以及分配樣本時(shí)僅考慮單一變量的兩個(gè)缺陷，本文提出了一種自動(dòng)確定聚類中心的勢(shì)能聚類算法。與PHA算法相比，ACP算法在保留算法思想新穎及性能高效的同時(shí)，可以在沒有任何參數(shù)依賴的前提下自動(dòng)確定聚類數(shù)目，而且在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上能夠取得更好的聚類效果。

然而，ACP算法采用歐式距離測(cè)度度量樣本之間相似度，在一些維數(shù)相對(duì)較低的數(shù)據(jù)集中可以得到較好的效果。但歐式距離在度量高維數(shù)據(jù)對(duì)象之間的相似度時(shí)存在不足：隨著數(shù)據(jù)維數(shù)的增加，它會(huì)導(dǎo)致數(shù)據(jù)點(diǎn)之間的最大距離與最小距離的差異不明顯，即歐式距離測(cè)度在高維數(shù)據(jù)中會(huì)失效。因此，如何使ACP算法能夠有效處理高維數(shù)據(jù)集，將是下一步的研究?jī)?nèi)容。

:

[1]von Luxburg U,Williamson R C,Guyon I.Clustering:science or art?[C]//Proceedings of the 2011 International Conference on Unsupervised and Transfer Learning Workshop,Bellevue,Jul 2,2011:65-80.

[2]Guang Junye,Liu Mingxia,Zhang Daoqiang.Spectral clustering algorithm based on effective distance[J].Journal of Frontiers of Computer Science and Technology,2014,8(11):1365-1372.

[3]Yang Jing,Gao Jiawei,Liang Jiye,et al.An improved DBSCAN clustering algorithm based on data field[J].Journal of Frontiers of Computer Science and Technology,2012,6(10):903-911.

[4]Jain A K.Data clustering:50 years beyondk-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[5]Xu Rui,Wunsch D.Survey of clustering algorithms[J].IEEE Transactions on Neural Networks,2005,16(3):645-678.

[6]Guha S,Rastogi R,Shim K.CURE:an efficient clustering algorithm for large databases[C]//Proceeding of the 1998 ACM SIGMOD International Conference on Management of Data,Seattle,Jun 1-4,1998.NewYork:ACM,1998:73-84.

[7]Przybyla T,Pander T,Czabański R.Deep data fuzzy clustering[C]//Proceedings of the 7th Joint International Information Technology and Artificial Intelligence Conference,Chongqing,Dec 20-21,2014.Piscataway:IEEE,2014:130-134.

[8]Wilcox H,Nichol R C,Zhao Gongbo,et al.Simulation tests of galaxy cluster constraints on chameleon gravity[J].Monthly Notices of the royal astronomical society,2016,462(1):715-725.

[9]Kumar K M,Reddy A R M.A fast DBSCAN clustering algorithm by accelerating neighbor searching using groups method[J].Pattern Recognition,2016,28:39-48.

[10]Kalita H K,Bhattacharya D K,Kar A.A new algorithm for ordering of points to identify clustering structure based on perimeter of triangle:OPTICS(BOPT)[C]//Proceedings of the 18th International Conference on Advanced Computing and Communications,Guwahati,Dec 18-21,2007.Washington:IEEE Computer Society,2007:523-528.

[11]Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[12]Li Tao,Ge Hongwei,Su Shuzhi.Density peaks clustering by automatic determination of cluster centers[J].Journal of Frontiers of Computer Science and Technology,2016,10(11):1614-1622.

[13]Lu Yonggang,Wan Yi.Clustering by sorting potential values(CSPV):a novel potential-based clustering method[J].Pattern Recognition,2012,45(9):3512-3522.

[14]Lu Yonggang,Wan Yi.PHA:a fast potential-based hierarchical agglomerative clustering method[J].Pattern Recognition,2013,46(5):1227-1239.

[15]Parzen E.On estimation of a probability density function and mode[J].Annals of Mathematical Statistic,1962,33(3):1065-1076.

[16]Fowlkes E B,Mallows C L.A method for comparing two hierarchical clusterings[J].Journal of the American StatisticalAssociation,1983,78(383):553-569.

[17]Yang Yan,Jin Fan,Mohamed K.Survey of clustering validity evaluation[J].Application Research of Computers,2008,25(6):1630-1632.

[18]Nguyen X V,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,Jun 14-18,2009.New York:ACM,2009:1073-1080.

[19]Lichman M.UCI machine learning repository[EB/OL].http://archive.ics.uci.edu/ml.Irvine:University of California,2013.

附中文參考文獻(xiàn)：

[2]光俊葉,劉明霞,張道強(qiáng).基于有效距離的譜聚類算法[J].計(jì)算機(jī)科學(xué)與探索,2014,8(11):1365-1372.

[3]楊靜,高嘉偉,梁吉業(yè).基于數(shù)據(jù)場(chǎng)的改進(jìn)DBSCAN聚類算法[J].計(jì)算機(jī)科學(xué)與探索,2012,6(10):903-911.

[12]李濤,葛洪偉,蘇樹智.自動(dòng)確定聚類中心的密度峰聚類[J].計(jì)算機(jī)科學(xué)與探索,2016,10(11):1614-1622.

[17]楊燕,靳蕃,Mohamed K.聚類有效性評(píng)價(jià)綜述[J].計(jì)算機(jī)應(yīng)用研究,2008,25(6):1630-1632.