一種基于圖金字塔的聚類算法

呂曉波　馬　燕　張相芬　李順寶　張玉萍

1(上海師范大學(xué)信息與機(jī)電工程學(xué)院　上海 200234) 2(上海師范大學(xué)數(shù)理學(xué)院　上海 200234 )

0　引　言

聚類是按照數(shù)據(jù)集中數(shù)據(jù)間的相似性進(jìn)行區(qū)分和分類的過(guò)程，其分類原則是使同一簇中的數(shù)據(jù)具有盡可能大的相似性，不同簇中的數(shù)據(jù)具有盡可能大的相異性。聚類算法可分為基于劃分的、分層的、密度的、網(wǎng)格的、模型等類型。作為基于劃分的聚類算法，k-means聚類算法[1]因其算法簡(jiǎn)單、執(zhí)行高效而被廣泛應(yīng)用，但其聚類結(jié)果依賴于初始聚類中心的選取，目前提出的k-means++[2]、CCIA[3]、kd-tree[4]等初始聚類中心確定方法無(wú)法普適于任何數(shù)據(jù)集，并且k-means算法易受離群點(diǎn)影響，導(dǎo)致聚類結(jié)果不穩(wěn)定，聚類精度不高。作為基于分層的層次聚類算法，包括兩種類型：凝聚的層次聚類和分裂的層次聚類[5]，層次聚類方法的缺點(diǎn)在于不能改進(jìn)先前的錯(cuò)誤分類，一旦一個(gè)樣本被分在一個(gè)類之后，便不再有變化，缺乏穩(wěn)健性和抗干擾能力，特別是當(dāng)簇間有交疊時(shí)，會(huì)產(chǎn)生錯(cuò)誤聚類結(jié)果。為改進(jìn)其效果，一些新的層次聚類算法被提出，包括CURE、ROCK、CHAMELEON和BIRCH[6]。基于密度的聚類算法，如DBSCAN方法[7]，將密度較大的點(diǎn)集劃分為簇，彌補(bǔ)了基于劃分和基于層次的聚類算法只能發(fā)現(xiàn)凸形簇的缺陷，但該方法對(duì)于高維數(shù)據(jù)和密度變化較大的數(shù)據(jù)集聚類效果較差。

受小波多分辨率分析[8]啟發(fā)，數(shù)據(jù)集中的所有數(shù)據(jù)點(diǎn)可以看作是高分辨率表示，這些數(shù)據(jù)點(diǎn)逐步被歸類到不同簇，不同簇的代表點(diǎn)又可看作是低分辨率的近似。因此，本文提出一種基于圖金字塔的聚類算法，首先輸入數(shù)據(jù)集的類別數(shù)目K，利用圖論對(duì)數(shù)據(jù)點(diǎn)構(gòu)建最小生成樹(shù)，按節(jié)點(diǎn)優(yōu)先值由高到低遍歷最小生成樹(shù)，進(jìn)行節(jié)點(diǎn)間的合并，反復(fù)進(jìn)行此過(guò)程，由此建立從高分辨率到低分辨率、由合并數(shù)據(jù)點(diǎn)構(gòu)成的金字塔結(jié)構(gòu)，位于金字塔塔頂?shù)腒個(gè)代表點(diǎn)即為最終聚類結(jié)果。

1　基于圖金字塔的聚類算法

1.1　構(gòu)建最小生成樹(shù)

當(dāng)以較小的尺度去觀察數(shù)據(jù)集時(shí)，看到的是數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)，相當(dāng)于金字塔的最底層[9]。對(duì)應(yīng)高分辨率表示，這里的高分辨率指數(shù)據(jù)點(diǎn)未參加合并，相當(dāng)于數(shù)據(jù)集中的原始數(shù)據(jù)點(diǎn)。假定數(shù)據(jù)集中一共有9個(gè)數(shù)據(jù)點(diǎn)，圖1中0層，其中包括9個(gè)數(shù)據(jù)點(diǎn)，則可以認(rèn)為0層即為高分辨率表示。而當(dāng)我們以較大的尺度去觀察數(shù)據(jù)集時(shí)，在0層中距離較近的數(shù)據(jù)點(diǎn)可以被合并為一個(gè)新的數(shù)據(jù)點(diǎn)，如圖1中的1層，對(duì)應(yīng)低分辨率近似，其數(shù)據(jù)點(diǎn)個(gè)數(shù)分別為5個(gè)。假定數(shù)據(jù)集的類別數(shù)目K等于2時(shí)，圖1的2層中的2個(gè)數(shù)據(jù)點(diǎn)已包含2個(gè)簇中所有數(shù)據(jù)點(diǎn)的信息。

圖1　數(shù)據(jù)點(diǎn)的金字塔結(jié)構(gòu)

要實(shí)現(xiàn)基于多分辨率思想的聚類，可以通過(guò)將數(shù)據(jù)點(diǎn)表示為最小生成樹(shù)(MST)[11]來(lái)完成，從MST中進(jìn)一步獲取節(jié)點(diǎn)的密度及其相鄰節(jié)點(diǎn)等信息。給定包含n個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集D，數(shù)據(jù)集中的n個(gè)數(shù)據(jù)點(diǎn)可以看作是MST中的n個(gè)節(jié)點(diǎn)，MST中邊的權(quán)重等于對(duì)應(yīng)兩個(gè)數(shù)據(jù)點(diǎn)間的歐幾里德距離，生成的MST是在所有由n個(gè)節(jié)點(diǎn)構(gòu)成的樹(shù)中，n-1條邊的權(quán)重總和最小的生成樹(shù)。

1.2　節(jié)點(diǎn)優(yōu)先級(jí)的計(jì)算

當(dāng)對(duì)數(shù)據(jù)集中的所有數(shù)據(jù)點(diǎn)構(gòu)建了MST以后，下一步就要遍歷各節(jié)點(diǎn)，將一些距離鄰近的節(jié)點(diǎn)進(jìn)行合并，形成新的節(jié)點(diǎn)并用于下一次遍歷。在遍歷中如果順序遍歷節(jié)點(diǎn)，則會(huì)導(dǎo)致錯(cuò)誤的聚類結(jié)果。如圖2所示，理想的節(jié)點(diǎn)合并方案是節(jié)點(diǎn)1、2合并，節(jié)點(diǎn)3、4、5合并，但如果在遍歷時(shí)，首先找到節(jié)點(diǎn)3，則極有可能將其鄰節(jié)點(diǎn)2、4、5與節(jié)點(diǎn)3合并，而距離較近的節(jié)點(diǎn)1、2則未被合并。

圖2　數(shù)據(jù)點(diǎn)示意圖

為得到正確的聚類結(jié)果，應(yīng)按節(jié)點(diǎn)的優(yōu)先級(jí)由高到低的順序遍歷節(jié)點(diǎn)。對(duì)于密度較大的節(jié)點(diǎn)應(yīng)具有較高的優(yōu)先級(jí)，使其能合并鄰節(jié)點(diǎn)，MST中節(jié)點(diǎn)的度與其密度呈正比關(guān)系，因此，

在定義節(jié)點(diǎn)的優(yōu)先級(jí)時(shí)，應(yīng)遵循以下原則：

(1) 節(jié)點(diǎn)的度越大，優(yōu)先級(jí)應(yīng)該越高，反之，則越低。

(2) 在節(jié)點(diǎn)度相同的情況下，與節(jié)點(diǎn)相連的最短邊的長(zhǎng)度越短，則該節(jié)點(diǎn)優(yōu)先級(jí)應(yīng)該越高，反之，則越低。

按上述原則，我們定義節(jié)點(diǎn)vi的優(yōu)先級(jí)pi：

(1)

(2)

(3)

1.3　節(jié)點(diǎn)的遍歷與合并

獲得MST中所有節(jié)點(diǎn)的優(yōu)先級(jí)以后，進(jìn)行節(jié)點(diǎn)間的合并，具體步驟如下：

按優(yōu)先級(jí)降序遍歷MST中的所有n個(gè)節(jié)點(diǎn)，并判斷遍歷到的節(jié)點(diǎn)vi是否參與過(guò)合并，如果已參與過(guò)合并，則不再參與合并，否則在MST中找到與vi存在邊相連的所有節(jié)點(diǎn)，在這所有的節(jié)點(diǎn)中，將符合如下要求的節(jié)點(diǎn)挑選出來(lái)并與vi合并：該節(jié)點(diǎn)未參與過(guò)合并，在所有與vi存在邊相連的節(jié)點(diǎn)中，該節(jié)點(diǎn)與vi的距離最小；這里，如果有多個(gè)節(jié)點(diǎn)與vi的距離相等且最小，則與vi合并的節(jié)點(diǎn)數(shù)目大于1。

(4)

整個(gè)算法流程見(jiàn)圖3。

圖3　算法流程

MST中所有節(jié)點(diǎn)的初始值為1，合并后新節(jié)點(diǎn)的質(zhì)量等于合并前所有節(jié)點(diǎn)質(zhì)量之和，該值其實(shí)就是參與合并的節(jié)點(diǎn)總數(shù)。按式(4)，參與合并的節(jié)點(diǎn)質(zhì)量越大，則在屬性值中所占的權(quán)重越大，即合并后的新節(jié)點(diǎn)越接近該節(jié)點(diǎn)。當(dāng)遍歷完所有n個(gè)節(jié)點(diǎn)或n等于類別數(shù)K，則結(jié)束本次遍歷；否則繼續(xù)本次遍歷。若當(dāng)前總的節(jié)點(diǎn)數(shù)目大于類別數(shù)K，則對(duì)當(dāng)前的節(jié)點(diǎn)生成MST，繼續(xù)進(jìn)行遍歷與合并；若當(dāng)前總的節(jié)點(diǎn)數(shù)目等于類別數(shù)K，則聚類結(jié)束，K個(gè)節(jié)點(diǎn)中所有參與合并的節(jié)點(diǎn)分別構(gòu)成K個(gè)簇，從而得到聚類結(jié)果。

2　算法分析

其次，將本文方法與k-means方法在數(shù)據(jù)集中有離群點(diǎn)的情況下的性能作一比較。

在k-means方法中，常用k-means++方法來(lái)選取初始聚類中心，該方法僅考慮數(shù)據(jù)點(diǎn)間的距離因素，而忽略數(shù)據(jù)點(diǎn)的密度，從而易將離群點(diǎn)作為聚類中心，最終導(dǎo)致錯(cuò)誤聚類結(jié)果。而在利用本文方法時(shí)，由于離群點(diǎn)與其他數(shù)據(jù)點(diǎn)的屬性相差較大，在對(duì)所有數(shù)據(jù)點(diǎn)生成MST時(shí)，離群點(diǎn)大多是MST中的葉子節(jié)點(diǎn)，且與鄰接點(diǎn)間的距離較大，按式(1)計(jì)算得到的優(yōu)先級(jí)較小，遍歷MST中參與合并的機(jī)會(huì)也較小，其質(zhì)量也相應(yīng)低于其他優(yōu)先級(jí)高的節(jié)點(diǎn)。由于式(4)是以參與合并節(jié)點(diǎn)的質(zhì)量為權(quán)重計(jì)算新節(jié)點(diǎn)的屬性值，參與合并節(jié)點(diǎn)的質(zhì)量越小則權(quán)重越小，從而使得離群點(diǎn)對(duì)于新節(jié)點(diǎn)屬性值的影響較小。因此，本文方法受離群點(diǎn)的影響較小。

接著，將本文方法與層次聚類法在簇間有交疊的情況下的性能作一比較。

在層次聚類法的每次迭代中，以距離作為合并準(zhǔn)則，將距離最近的兩個(gè)簇合并為新的簇，在合并過(guò)程中，忽略了密度因素。在遇到兩個(gè)簇發(fā)生交疊的情況時(shí)，則會(huì)將交疊部分錯(cuò)誤地歸為某一簇，又由于層次聚類法的聚類過(guò)程是不可逆的，由此導(dǎo)致錯(cuò)誤聚類結(jié)果。本文方法是按節(jié)點(diǎn)優(yōu)先級(jí)降序遍歷節(jié)點(diǎn)，位于兩個(gè)簇交疊處的節(jié)點(diǎn)，又可以認(rèn)為是位于簇邊界的節(jié)點(diǎn)，其度數(shù)一般小于位于簇中心的節(jié)點(diǎn)，故優(yōu)先級(jí)也較小，往往在較后面才會(huì)被遍歷到。而該節(jié)點(diǎn)與同屬本簇的相鄰節(jié)點(diǎn)的距離一般小于與異簇節(jié)點(diǎn)的距離，因此，在該節(jié)點(diǎn)被遍歷前，大多已被本簇優(yōu)先權(quán)值較高的節(jié)點(diǎn)合并。由此，本文提出的方法較好地解決了簇間有交疊的情況。

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

3.1　離群點(diǎn)的影響

為了驗(yàn)證本算法相對(duì)于k-means算法在處理離群點(diǎn)時(shí)的穩(wěn)定性，我們產(chǎn)生了具有330個(gè)數(shù)據(jù)點(diǎn)，每個(gè)數(shù)據(jù)點(diǎn)包含2個(gè)屬性的人工合成數(shù)據(jù)集SYN1，該數(shù)據(jù)集的類別數(shù)K=3，對(duì)應(yīng)在二維空間下的數(shù)據(jù)點(diǎn)集如圖4所示。從圖4可以看出該SYN1中包含部分離群點(diǎn)。圖5為利用k-means方法聚類結(jié)果，其中，初始聚類中心確定方法是采用k-means++[2]，其基本思想是初始聚類中心間的相互距離盡可能遠(yuǎn)。我們?nèi)? 000次結(jié)果的均值作為最終聚類結(jié)果。圖中“▲”表示通過(guò)隨機(jī)選取法選擇的3個(gè)初始聚類中心。圖6為利用本文方法的聚類結(jié)果。圖5和圖6中利用“+”，“°”與“×”表示聚類得到的三類數(shù)據(jù)。從圖5與圖6，可以看出，利用本文方法準(zhǔn)確地得到了聚類結(jié)果，而利用k-means++方法選取的3個(gè)初始聚類中心，其中有2個(gè)初始聚類中心位于離群點(diǎn)，從而導(dǎo)致k-means方法陷入局部最優(yōu)解，最終導(dǎo)致錯(cuò)誤聚類結(jié)果。

圖4　SYN1數(shù)據(jù)集

圖5　k-means方法

圖6　本文方法

3.2　簇間有交疊的影響

為進(jìn)一步驗(yàn)證本文方法相對(duì)于層次聚類算法在簇間有交疊時(shí)聚類結(jié)果的穩(wěn)定性，我們產(chǎn)生了具有800個(gè)數(shù)據(jù)點(diǎn)，簇間有一定的交疊，每個(gè)數(shù)據(jù)點(diǎn)包含兩個(gè)屬性的人工合成數(shù)據(jù)集SYN2，該數(shù)據(jù)集的類別數(shù)K=3，對(duì)應(yīng)在二維空間下的數(shù)據(jù)點(diǎn)集如圖7所示。圖8為利用層次聚類法得到的聚類結(jié)果，其中，層次聚類法中的類間距離計(jì)算方法使用離差法，圖9為利用本發(fā)明方法得到的聚類結(jié)果。圖8和圖9中利用“+”，“°”與“×”表示聚類得到的三類數(shù)據(jù)。從圖8可見(jiàn)，由于中間與下面這2個(gè)簇間有交疊，導(dǎo)致下面的簇被錯(cuò)誤聚類。從圖9中可見(jiàn)，利用本文方法獲得了正確的聚類結(jié)果。

圖7　SYN2數(shù)據(jù)集

圖8　層次聚類法

圖9　本文方法

3.3　真實(shí)數(shù)據(jù)集

利用本文方法分別對(duì)UCI[10]里的4個(gè)數(shù)據(jù)集：Iris、Wine、Soybean-small、Segment進(jìn)行實(shí)驗(yàn)并得出實(shí)驗(yàn)結(jié)果，然后將其與k-means方法以及層次聚類法得出的結(jié)果進(jìn)行比較。這四個(gè)數(shù)據(jù)集的信息如表1所示。

表1　數(shù)據(jù)集信息

對(duì)于k-means方法，挑選了具有代表性初始聚類中心確定方法：k-means++，CCIA和kd-tree，取1 000次結(jié)果的均值作為k-means++最終聚類結(jié)果。為評(píng)價(jià)上述聚類方法的優(yōu)劣，我們運(yùn)用4種聚類有效性評(píng)價(jià)指標(biāo)：Accuracy(AC)、Adjusted Rand Index(ARI)、Rand Index(RI)和Mirkin Metric Index(MI)[11]對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)。除了MI之外的所有指標(biāo)，其評(píng)價(jià)指標(biāo)越高則說(shuō)明聚類效果越好，而對(duì)于MI來(lái)說(shuō)，評(píng)價(jià)指標(biāo)越低則說(shuō)明聚類效果越好。表2顯示了利用本文方法、k-means++、CCIA、kd-tree、層次聚類這5種方法在Iris，Wine，Soybean-small和Segment數(shù)據(jù)集上的評(píng)價(jià)結(jié)果及其運(yùn)行時(shí)間，為清楚起見(jiàn)，對(duì)每個(gè)數(shù)據(jù)集中效果最好的方法所對(duì)應(yīng)的指標(biāo)值用粗體表示。對(duì)于層次聚類法的類間距離計(jì)算，我們分別采用了離差法、最短距離法、最大距離法、平均距離法、中位數(shù)法和重心法，并取最優(yōu)的指標(biāo)結(jié)果列在表2。從表2可以看出，對(duì)于Iris、Wine、Soybean-small和Segment數(shù)據(jù)集，本文方法所需時(shí)間略高于k-means++、CCIA、kd-tree，但聚類效果明顯優(yōu)于k-means++、CCIA、kd-tree。另外，除了Soybean-small數(shù)據(jù)集，本文方法在其余3個(gè)數(shù)據(jù)集上所需時(shí)間均低于層次聚類法。從聚類效果來(lái)看，本文方法在4個(gè)數(shù)據(jù)集上的聚類效果優(yōu)于層次聚類法或與層次聚類法持平。

表2　聚類結(jié)果和運(yùn)行時(shí)間

4　結(jié)　語(yǔ)

本文提出一種圖金字塔的聚類算法，該算法通過(guò)遍歷與合并節(jié)點(diǎn)將數(shù)據(jù)點(diǎn)逐步歸類到不同簇。我們將本文方法與k-means方法，層次聚類法在有離群點(diǎn)和簇間交疊情況的人工數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)比較，驗(yàn)證本文方法在數(shù)據(jù)集有離群點(diǎn)和簇間交疊情況下不受影響，聚類結(jié)果具有穩(wěn)定性。另外，我們將本文方法、k-menas++、CCIA、kd-tree和層次聚類法共5種方法在Iris，Wine，Soybean-small和Segment數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)比較。就4個(gè)指標(biāo)(包括AC，ARI，RI和MI)的結(jié)果而言，本文算法的聚類性能是最優(yōu)的。如何利用本文方法進(jìn)一步確定類別數(shù)目K，是將來(lái)研究的方向之一。

[1] Forgy E W.Cluster Analysis of Multivariate Data:Efficiency vs.Interpretability of Classification[J].Biometrics,1965,21(3):41-52.

[2] Arthur D,Vassilvitskii S.k-means++:the advantages of careful seeding[C]//Eighteenth Acm-Siam Symposium on Discrete Algorithms.Society for Industrial and Applied Mathematics,2007:1027-1035.

[3] Khan S S,Ahmad A.Cluster center initialization algorithm for K-modes clustering[J].Expert Systems with Applications,2013,40(18):7444-7456.

[4] Redmond S J,Heneghan C.A method for initialising the K-means clustering algorithm using kd-trees[J].Pattern Recognition Letters,2007,28(8):965-973.

[5] 文順,趙杰煜,朱紹軍.基于貝葉斯和諧度的層次聚類[J].模式識(shí)別與人工智能,2013,26(12):1161-1168.

[6] Rafsanjani M K,Varzaneh Z A,Chukanlo N E.A survey of hierarchical clustering algorithms[J].International Journal of Applied Mathematics & Computer Science,2012,5(3):229-240.

[7] Abbas O A.Comparisons Between Data Clustering Algorithms[J].International Arab Journal of Information Technology,2007,5(3):320-325.

[8] Mallat S G.A Theory for Multiresolution Signal Decomposition:The Wavelet Representation[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1989,11(7):674-693.

[9] Cheng C Y,Hu Y J.Extracting the abstraction pyramid from complex networks[J].BMC bioinformatics,2010,11(1):411.

[10] Celebi M E,Kingravi H A,Vela P A.A comparative study of efficient initialization methods for the k-means clustering algorithm[J].Expert Systems with Applications,2012,40(1):200-210.

[11] Yang J,Ma Y,Zhang X,et al.A Minimum spanning tree-based method for initializing the k-means clustering algorithm[J].International Journal of Computer,Electrical,Automation,Control and Information Engineering,2016,11(1):13-17.