一種改進(jìn)節(jié)點(diǎn)凝聚度的密度峰值聚類算法

吳辰文，魏立鑫，劉曉光

1(蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070) 2(蘭州交通大學(xué) 電子與信息工程學(xué)院 計(jì)算機(jī)應(yīng)用技術(shù)，蘭州 730070) 3(蘭州交通大學(xué) 電子與信息工程學(xué)院 軟件工程，蘭州 730070)

1 引 言

在數(shù)據(jù)挖掘領(lǐng)域中，聚類是一種無(wú)監(jiān)督的學(xué)習(xí)方法，其目的就是將含有雜亂無(wú)章數(shù)據(jù)的集合分為若干簇，并且使簇中的數(shù)據(jù)盡可能相似，簇間的差別盡可能大[1]，以便為我們提供有價(jià)值的信息.聚類分析在模式識(shí)別、醫(yī)學(xué)、數(shù)據(jù)挖掘、圖像識(shí)別等領(lǐng)域有著廣泛的應(yīng)用.

根據(jù)聚類原理將這些算法分為5類：基于劃分的聚類算法(K-Means，F(xiàn)uzzy C-Means等)、基于層次的聚類算法(Clustering Using Representative，Chameleon等)、基于網(wǎng)格的聚類算法(MAFIA，STatistical INformation Grid等)、基于密度的聚類算法(Density-Based Spatial Clustering of Applications with Noise，Ordering Points to Identify the Clustering Structure等)和基于模型的聚類算法(Self-Organizing Maps，Expectation-Maximization Algorithm等)[2-7].除了這些經(jīng)典的算法之外，于2014年在《Science》學(xué)術(shù)期刊中發(fā)表了一種新的密度峰值聚類算法[8](Density Peaks Clustering，DPC)引起了廣泛的關(guān)注.

DPC算法的核心思想是尋找被低密度區(qū)域劃分開(kāi)的高密度區(qū)域.利用局部密度ρ和不同簇高密度點(diǎn)之間的距離指標(biāo)δ來(lái)生成“決策圖”，并選取異常大的ρ、δ值作為類簇中心，將剩余數(shù)據(jù)點(diǎn)分配到已選取的類簇中心，直至完成數(shù)據(jù)點(diǎn)的分配.該算法具有簡(jiǎn)單高效、發(fā)現(xiàn)任意形狀簇、樣本歸類無(wú)需迭代、參數(shù)設(shè)置少等優(yōu)點(diǎn)，但是該算法規(guī)定每個(gè)簇中必須有密度最大的點(diǎn)作為簇中心，當(dāng)數(shù)據(jù)分布不均或同一簇含有多個(gè)高密度點(diǎn)，很容易將一個(gè)簇分為幾個(gè)子簇.近些年來(lái)，很多學(xué)者對(duì)密度峰值聚類算法進(jìn)行了一些改進(jìn)，并且也取得了一些研究成果，包括對(duì)聚類中心判斷、經(jīng)驗(yàn)截?cái)嗑嚯xdc的選擇、密度計(jì)算方法改進(jìn)等問(wèn)題[9].例如，Ma C等[10]在文中指出，按照給定的評(píng)價(jià)指標(biāo)對(duì)數(shù)據(jù)點(diǎn)排序，選取前m個(gè)最大值作為聚類中心；Wang S等[11]在基于信息熵的基礎(chǔ)上提出一種自動(dòng)獲取截?cái)嗑嚯xdc的方法，但是時(shí)間成本會(huì)增大；高詩(shī)瑩等[12]利用樣本的密度比，避免丟失低密度的簇，從而提高聚類效率；Zhang W，Li J[13]將DPC算法與Chameleon算法結(jié)合，避免了將一個(gè)簇分為幾個(gè)子簇的情況，但是時(shí)間復(fù)雜度高達(dá)O(N2+NlbN+NM)；Du M等[14]采用Principal Components Analysis方法對(duì)高維數(shù)據(jù)點(diǎn)降維，然后利用K-Nearest Neighbor思想估計(jì)密度，提高了對(duì)高維數(shù)據(jù)的處理能力.

從上面的研究可以知道，密度峰值聚類算法有很多的改進(jìn)算法.數(shù)據(jù)點(diǎn)在不同類別中密度差值太大，或者在具有多個(gè)類簇中心的同一類別中密度差值太小，這些條件都會(huì)影響最終的聚類結(jié)果.目前DPC改進(jìn)算法的文章很少考慮上述兩個(gè)要素，而且點(diǎn)與點(diǎn)之間的相互關(guān)系不明確，但是在本文研究中，很好的兼顧了上述情況.針對(duì)密度峰值聚類算法(Density Peak Clustering，DPC)處理密度分布不均勻的數(shù)據(jù)集或在同一簇中有多個(gè)高密度點(diǎn)的情況，難以準(zhǔn)確選取聚類中心，很可能將同一個(gè)簇劃分為若干個(gè)子簇.本文提出一種改進(jìn)節(jié)點(diǎn)凝聚度的密度峰值聚類算法(Improved Aggregation Density Peak Clustering，IA-DPC).首先，將要數(shù)據(jù)轉(zhuǎn)換為加權(quán)完全圖，由于完全圖是每對(duì)頂點(diǎn)之間恰有一條邊的無(wú)向圖，可以看做是一個(gè)完全連接的無(wú)權(quán)網(wǎng)絡(luò)，采用不同的加權(quán)方式對(duì)完全圖進(jìn)行加權(quán)，形成加權(quán)完全圖.其次，利用網(wǎng)絡(luò)中改進(jìn)節(jié)點(diǎn)凝聚度的思想構(gòu)建數(shù)據(jù)節(jié)點(diǎn)的重要度的評(píng)價(jià)函數(shù)，對(duì)節(jié)點(diǎn)局部重要度進(jìn)行計(jì)算并排序.然后，選取重要度與距離乘積異常大的點(diǎn)作為類簇中心.最后，將剩余點(diǎn)進(jìn)行分配直至完成.經(jīng)過(guò)一系列的實(shí)驗(yàn)仿真，研究表明該算法在密度分布不均勻及有多個(gè)高密度點(diǎn)的數(shù)據(jù)集中具有更準(zhǔn)確選取聚類中心的能力.

2 密度峰值聚類算法與改進(jìn)節(jié)點(diǎn)凝聚度

在整個(gè)研究工作開(kāi)始時(shí)，定義數(shù)據(jù)集為U={vi},i=1,2,…,N，vi表示數(shù)據(jù)集中的任意數(shù)據(jù)點(diǎn)，將數(shù)據(jù)集轉(zhuǎn)化為加權(quán)完全圖，因?yàn)榧訖?quán)完全圖能更好的反映節(jié)點(diǎn)間的緊密度，而且也能很好的表達(dá)其中的結(jié)構(gòu).在整個(gè)無(wú)權(quán)圖向加權(quán)圖的轉(zhuǎn)化中，應(yīng)該考慮圖的相異權(quán)值和相似權(quán)值問(wèn)題[15]，相異權(quán)表示權(quán)值越大，點(diǎn)之間距離越大，反應(yīng)它們之間的關(guān)系越疏遠(yuǎn)；相似權(quán)表示權(quán)值越大，點(diǎn)之間距離越小，反應(yīng)它們之間的關(guān)系越緊密.本文采用相異權(quán)的方法給圖賦予權(quán)值，由于該圖是加權(quán)完全圖，所以可將它看作完全連接的加權(quán)網(wǎng)絡(luò)，假設(shè)vi是網(wǎng)絡(luò)G=(V,E)中的任意一節(jié)點(diǎn).需要對(duì)每個(gè)數(shù)據(jù)節(jié)點(diǎn)定義兩個(gè)指標(biāo)：1)vi節(jié)點(diǎn)重要度評(píng)價(jià)指標(biāo)ui；2)節(jié)點(diǎn)vi與比vi有更高重要度的節(jié)點(diǎn)間距離δi.

2.1 密度峰值聚類算法原理

對(duì)于數(shù)據(jù)集U中的任意數(shù)據(jù)點(diǎn)vi，DPC算法都要求計(jì)算數(shù)據(jù)點(diǎn)的兩個(gè)屬性值：局部密度ρi和與高密度點(diǎn)間的距離δi.根據(jù)上述兩個(gè)屬性值來(lái)確定DPC算法的聚類中心.

定義局部密度ρi：

(1)

其中：當(dāng)x<0時(shí)，函數(shù)χ(x)=1；當(dāng)x≥0時(shí)，函數(shù)χ(x)=0.dij表示數(shù)據(jù)點(diǎn)vi與vj之間的歐式距離，dc表示截?cái)嗑嚯x，可以由用戶設(shè)置，一般情況下，在所有數(shù)據(jù)點(diǎn)的距離值從小到大排序后，首先選取距離值個(gè)數(shù)的1%～2%，然后選擇其中最大的一個(gè)距離值作為截?cái)嗑嚯xdc.x表示節(jié)點(diǎn)之間的距離值dij與截?cái)嗑嚯x值dc之差，j表示除了節(jié)點(diǎn)vi以外的任意節(jié)點(diǎn).等式(1)表明，截?cái)嗑嚯x的選取會(huì)影響DPC算法的局部密度.當(dāng)樣本較小時(shí)，使用核算法來(lái)計(jì)算樣本的局部密度[16]，這種方式可以避免截?cái)嗑嚯x對(duì)樣本局部密度甚至聚類結(jié)果的影響.表達(dá)式如下：

(2)

定義距離值δi：

(3)

其中：如果δi越小，dij也就越小，因此點(diǎn)vi和vj可能在同一簇中；當(dāng)δi越大時(shí)，dij也就越大，vi與vj越不可能為同一類.對(duì)于具有高密度的點(diǎn)，通常使用δi=maxj(dij)來(lái)表示點(diǎn)間距離，需要保證高密度點(diǎn)之間的距離是最大的.如果一個(gè)點(diǎn)的δi值大于其最近鄰點(diǎn)距離，那么就認(rèn)為該點(diǎn)是聚類中心.

文獻(xiàn)[8]指出，可以通過(guò)上述公式計(jì)算局部密度ρi和距離δi繪制決策圖.橫軸表示局部密度，縱軸表示距離.根據(jù)聚類中心的特點(diǎn)，在決策圖中選擇局部密度和距離異常大的點(diǎn)作為聚類中心.但是，在確定聚類中心的過(guò)程中，包含有許多的主觀因素，不同的用戶可能通過(guò)在決策圖上不同的選擇，得到不同的聚類結(jié)果，尤其對(duì)于密度分布不均勻的數(shù)據(jù)集，很可能會(huì)發(fā)生將同一簇劃分為若干簇的情況.

2.2 改進(jìn)的節(jié)點(diǎn)凝聚度

在網(wǎng)絡(luò)G中，一個(gè)節(jié)點(diǎn)的凝聚度是依據(jù)節(jié)點(diǎn)的收縮情況而定.節(jié)點(diǎn)收縮是指將vi相連接的k個(gè)節(jié)點(diǎn)收縮成一個(gè)新的節(jié)點(diǎn)v′i并用v′i表示這k+1個(gè)節(jié)點(diǎn).vi節(jié)點(diǎn)以最短路徑收縮于v′i，如果新節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)至關(guān)重要，那么整個(gè)網(wǎng)絡(luò)在節(jié)點(diǎn)收縮后可以更具好的凝聚在一起.

為了更清楚的理解凝聚度的概念，文獻(xiàn)[17]給出了網(wǎng)絡(luò)凝聚度的定義，用節(jié)點(diǎn)間最短距離的算術(shù)平均值L與節(jié)點(diǎn)總數(shù)目N乘積的倒數(shù)來(lái)表示凝聚度.

定義網(wǎng)絡(luò)G的凝聚度：

(4)

其中：要求節(jié)點(diǎn)總數(shù)N≥2，dij表示數(shù)據(jù)點(diǎn)vi與vj之間的距離.當(dāng)N=1時(shí)，凝聚度?的取值為1.

定義節(jié)點(diǎn)重要度為：

(5)

其中：G*vi表示節(jié)點(diǎn)vi收縮以后的網(wǎng)絡(luò).?(G*vi)表示節(jié)收縮以后的網(wǎng)絡(luò)凝聚度.

通過(guò)式(4)、式(5)可以得到節(jié)點(diǎn)重要度為：

(6)

其中：ki表示與vi相連接的k個(gè)節(jié)點(diǎn).

因此，從式(6)中看出，vi的重要度與vi在整個(gè)網(wǎng)絡(luò)中的位置相關(guān).連接度指從一個(gè)節(jié)點(diǎn)出發(fā)到另一個(gè)節(jié)點(diǎn)，最短距離經(jīng)過(guò)該點(diǎn)邊的數(shù)目，如果一個(gè)節(jié)點(diǎn)的連接度很大并且位置很重要，則節(jié)點(diǎn)收縮后的網(wǎng)絡(luò)的凝聚度也會(huì)變大.所以，可以認(rèn)為該節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中比其他節(jié)點(diǎn)更為重要.

凝聚度的定義適合于無(wú)權(quán)網(wǎng)絡(luò).當(dāng)該定義用于加權(quán)網(wǎng)絡(luò)時(shí)，它會(huì)受不同權(quán)重的影響.點(diǎn)權(quán)表示與節(jié)點(diǎn)i關(guān)聯(lián)的邊權(quán)之和，由于該網(wǎng)絡(luò)是無(wú)向網(wǎng)絡(luò)，邊權(quán)賦值方式為相異權(quán)，則點(diǎn)權(quán)應(yīng)該表示為邊權(quán)倒數(shù)之和.所以對(duì)于加權(quán)網(wǎng)絡(luò)，應(yīng)該重新定義加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)的重要度.文獻(xiàn)[18]重新定義了加權(quán)網(wǎng)絡(luò)的凝聚度：

(7)

其中：W(G)表示加權(quán)網(wǎng)絡(luò)中所有點(diǎn)權(quán)相加的平均值，L(G)表示在加權(quán)的路徑前提下加權(quán)網(wǎng)絡(luò)變?yōu)闊o(wú)權(quán)網(wǎng)絡(luò)后的平均最短距離，重新定義后的網(wǎng)絡(luò)凝聚度為：

(8)

其中：Mi表示與節(jié)點(diǎn)i相關(guān)聯(lián)的節(jié)點(diǎn)總數(shù)目，ωij表示與節(jié)點(diǎn)i相連的邊權(quán).等式(8)中，要求節(jié)點(diǎn)數(shù)N≥2，dij表示vi和vj在加權(quán)路徑下的無(wú)權(quán)距離.當(dāng)節(jié)點(diǎn)數(shù)目N為1時(shí)，凝聚度?(WG)的取值為1.

定義節(jié)點(diǎn)vi的重要度：

(9)

其中：WG′表示在加權(quán)網(wǎng)絡(luò)下節(jié)點(diǎn)i收縮以后的網(wǎng)絡(luò).根據(jù)式(8)、式(9)，點(diǎn)與點(diǎn)連接的緊密度越高，點(diǎn)權(quán)和的平均值就越小.在相同條件下，網(wǎng)絡(luò)凝聚度越高，定義的節(jié)點(diǎn)重要度就越高，那么這個(gè)點(diǎn)的就會(huì)顯得比其他點(diǎn)更加重要.

上述對(duì)加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要度的描述僅僅只考慮了點(diǎn)權(quán).在某些情況下，邊權(quán)很大程度上也會(huì)影響節(jié)點(diǎn)的重要度.因此，文獻(xiàn)[19]提供了一種使用邊代替加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)的方法，將邊與邊連接關(guān)系作為點(diǎn)，將網(wǎng)絡(luò)G轉(zhuǎn)化為G*.當(dāng)邊權(quán)重的差異度消失時(shí)，加權(quán)網(wǎng)絡(luò)將轉(zhuǎn)化為無(wú)權(quán)網(wǎng)絡(luò)，如圖1～圖2所示.

G*是用節(jié)點(diǎn)替代邊后的網(wǎng)絡(luò)，可以通過(guò)計(jì)算該網(wǎng)絡(luò)中節(jié)點(diǎn)的凝聚度來(lái)替代邊的凝聚度，為了綜合考慮兩種情況，將在網(wǎng)絡(luò)G中vi的重要度和在網(wǎng)絡(luò)G*中vj的重要度相加，得到：

圖1 網(wǎng)絡(luò)G

圖2 網(wǎng)絡(luò)G*

(10)

其中：IMCn表示在網(wǎng)絡(luò)G中任意節(jié)點(diǎn)vi的重要度，IMCe表示在網(wǎng)絡(luò)G*中任意節(jié)點(diǎn)vj的重要度，α表示點(diǎn)權(quán)權(quán)重系數(shù)，β表示邊權(quán)權(quán)重系數(shù)，T表示在G*中的節(jié)點(diǎn)數(shù).為了避免節(jié)點(diǎn)重要度值的差異度過(guò)大，進(jìn)行歸一化處理：

(11)

令γ=α/β且α+β=1，γ表示點(diǎn)權(quán)與邊權(quán)的比例系數(shù).要依據(jù)實(shí)際情況，進(jìn)行比例系數(shù)的調(diào)節(jié).γ的取值與點(diǎn)重要度和邊重要度都相關(guān)，也就是說(shuō)比例系數(shù)與G和G*都相關(guān).在G和G*中，利用圖論中度的概念設(shè)置比例系數(shù).

(12)

由于該比例系數(shù)的確定也帶有一定的主觀性，所以通過(guò)α+β=1可以相互適當(dāng)?shù)剡M(jìn)行調(diào)節(jié).在調(diào)節(jié)過(guò)程中，適當(dāng)擴(kuò)大α取值范圍，在(0，1)范圍中，用原α值加上幾個(gè)差異不是很大的數(shù)，調(diào)整α后對(duì)得到的多個(gè)α值求平均值，利用α+β=1計(jì)算出β，進(jìn)而求得不同的γ值.

2.3 基于改進(jìn)節(jié)點(diǎn)凝聚度的密度峰值聚類(IA-DPC)

在IA-DPC算法中，先將數(shù)據(jù)集轉(zhuǎn)為加權(quán)完全圖，把數(shù)據(jù)點(diǎn)作為節(jié)點(diǎn)，通過(guò)計(jì)算兩個(gè)節(jié)點(diǎn)之間的距離作為兩點(diǎn)之間的邊權(quán)重，進(jìn)行存儲(chǔ).將節(jié)點(diǎn)的點(diǎn)權(quán)與該節(jié)點(diǎn)相連的邊權(quán)和作為網(wǎng)絡(luò)節(jié)點(diǎn)總權(quán)值，并用改進(jìn)節(jié)點(diǎn)凝聚度方法評(píng)估每個(gè)節(jié)點(diǎn)的重要程度.類簇中心的局部重要度高于周圍鄰居，具有較高重要度的節(jié)點(diǎn)間距離更大.對(duì)節(jié)點(diǎn)重要度進(jìn)行排序，比較選取重要度ui和距離δi乘積的異常大點(diǎn)作為類簇中心.選取類簇中心后，將剩余點(diǎn)進(jìn)行分配，得到最終的聚類結(jié)果.

IA-DPC算法具體步驟：

Step 1.數(shù)據(jù)歸一化并初始化變量dc、γ，將數(shù)據(jù)轉(zhuǎn)化為加權(quán)完全圖G；

Step 3.計(jì)算vi(i=1,2,3,…,N)節(jié)點(diǎn)收縮后網(wǎng)絡(luò)G′的平均無(wú)權(quán)最短距離L′和平均點(diǎn)權(quán)和W′；

Step 4.計(jì)算G′的加權(quán)凝聚度，并計(jì)算G中節(jié)點(diǎn)的重要度IMCn(當(dāng)G轉(zhuǎn)化為G*后，計(jì)算G*中邊轉(zhuǎn)化為節(jié)點(diǎn)后的重要度IMCe)；

Step 5.將G轉(zhuǎn)化為G*，重復(fù)Step 2～Step 4；

Step 6.調(diào)節(jié)比例系數(shù)γ，計(jì)算數(shù)據(jù)點(diǎn)重要度IMC(vi)，并對(duì)其進(jìn)行排序；

Step 7.比較選取重要度ui和距離δi乘積異常大的點(diǎn)作為聚類中心；

Step 8.分配剩余數(shù)據(jù)點(diǎn)到相應(yīng)最近的類簇中心，完成聚類.

從上述算法步驟中，可以知算法的主要復(fù)雜度集中在對(duì)加權(quán)圖之間轉(zhuǎn)化、節(jié)點(diǎn)重要度的計(jì)算和數(shù)據(jù)遍歷的計(jì)算.由于算法是構(gòu)造的完全圖，復(fù)雜度至少是O(n2)，為了計(jì)算網(wǎng)絡(luò)G中的節(jié)點(diǎn)凝聚度，其核心的計(jì)算部分復(fù)雜度為O(n3)，由于必須考慮網(wǎng)絡(luò)G*中的復(fù)雜度，轉(zhuǎn)換后的網(wǎng)絡(luò)與原網(wǎng)絡(luò)具有相同的計(jì)算復(fù)雜度.那么G與G*的復(fù)雜度是一樣的.對(duì)于數(shù)據(jù)的遍歷，采用用鄰接矩陣進(jìn)行存儲(chǔ)，由于矩陣中元素?cái)?shù)量為n2，其復(fù)雜度為O(n2).就整體性能而言，算法的復(fù)雜度在O(n3)的數(shù)量級(jí)上.

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

選擇5個(gè)人工數(shù)據(jù)集和4個(gè)真實(shí)數(shù)據(jù)集來(lái)驗(yàn)證IA-DPC算法性能.選用聚類算法常用的兩個(gè)指標(biāo)F-measure和ARI對(duì)算法性能進(jìn)行評(píng)估.同時(shí)，給出兩種比較算法(DPC，ADPC-KNN[20]).具體數(shù)據(jù)集及其特征如表1所示.

在所有算法中，三種算法都有設(shè)置參數(shù)的情況，DPC需要設(shè)置截?cái)嗑嚯xdc，通過(guò)決策圖需要手動(dòng)選取聚類中心，ADPC-KNN該算法需要設(shè)置k近鄰的個(gè)數(shù)，對(duì)于IA-DPC算法需要調(diào)節(jié)比例系數(shù)γ及截?cái)嗑嚯xdc的設(shè)定.在IA-DPC算法中根據(jù)γ的調(diào)節(jié)方式選取效果最好的聚類結(jié)果進(jìn)行展示.DPC和IA-DPC截?cái)嗑嚯xdc值都是選取所有數(shù)據(jù)點(diǎn)中距離值個(gè)數(shù)排序的1%～2%處距離值的平均值.經(jīng)過(guò)算法在數(shù)據(jù)集上的多次實(shí)驗(yàn)，選擇結(jié)果最佳的圖形展示.

表1 實(shí)驗(yàn)數(shù)據(jù)集

Table 1 Experimental datasets

DatasetInstancesDimensionsClustersCompound39926Aggregation78827Banded_d51234Scatter1000100034D313100331Iris15053Wine178143Glass214106CellCycle_384384175

3.1 聚類結(jié)果分析

圖3～圖4顯示了9個(gè)數(shù)據(jù)集中的兩個(gè)數(shù)據(jù)集在算法(DPC，ADPC-KNN，IA-DPC)上的聚類結(jié)果.實(shí)驗(yàn)數(shù)據(jù)集在MATLAB 2014a版本的win10環(huán)境中運(yùn)行.硬件配置為4G內(nèi)存和2.6GHz主頻.

圖3 D31數(shù)據(jù)集

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

首先，使用人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，包括Compound數(shù)據(jù)集、Aggregation數(shù)據(jù)集、Banded_d數(shù)據(jù)集、Scatter1000數(shù)據(jù)集和D31數(shù)據(jù)集.

如圖3所示，顯示D31數(shù)據(jù)集在三種算法中的聚類結(jié)果.可以看出三種算法都出現(xiàn)了錯(cuò)誤聚類的情況.DPC算法和ADPC-KNN算法都不能劃分某些簇.IA-DPC(γ= 0.752)算法在對(duì)某些點(diǎn)的劃分上也不清楚，并且在該數(shù)據(jù)集上難以區(qū)分邊界點(diǎn).

接下來(lái)，使用真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，這些數(shù)據(jù)集來(lái)自UCI，包括Iris數(shù)據(jù)集，Wine數(shù)據(jù)集和Glass數(shù)據(jù)集.還使用了一個(gè)酵母菌Gene數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如下：

CellCycle_384數(shù)據(jù)集[21，22]用于觀察細(xì)胞中基因轉(zhuǎn)錄水平的周期性變化.它是具有先驗(yàn)知識(shí)的數(shù)據(jù)集.從全基因組中選擇總共384個(gè)基因，將同一時(shí)刻達(dá)到轉(zhuǎn)錄峰值的基因作為一個(gè)標(biāo)準(zhǔn)類.

如圖4所示，顯示CellCycle_384數(shù)據(jù)集在三種算法中的聚類結(jié)果.在所有酵母菌轉(zhuǎn)錄水平的17個(gè)時(shí)間點(diǎn)中，選擇第一個(gè)時(shí)間點(diǎn)和第二個(gè)時(shí)間點(diǎn)作為水平軸和垂直軸.從聚類可視化結(jié)果可以看出DPC算法的聚類結(jié)果效果較差.ADPC-KNN算法雖然能夠識(shí)別幾個(gè)類，但是直觀上效果依然不是很好.對(duì)于IA-DPC(γ=1.500)算法能夠識(shí)別出5個(gè)類別.

3.2 算法指標(biāo)分析

為了分析聚類結(jié)果的差異性，在聚類中選擇了兩個(gè)指標(biāo)進(jìn)行結(jié)果分析：調(diào)整后的蘭德指數(shù)(ARI)和F-measure(F1).ARI和F1的值越大，就越接近真實(shí)的聚類效果.同時(shí)，表2、表3分別列出了聚類結(jié)果下的F1和ARI的值.IA-DPC算法在這9個(gè)數(shù)據(jù)集的聚類過(guò)程中，γ取值會(huì)對(duì)重要度產(chǎn)生影響進(jìn)而對(duì)該聚類算法聚類性能產(chǎn)生影響，用更直觀的可視化展示其影響結(jié)果.

表格中的黑體數(shù)據(jù)表示最優(yōu)值.F1結(jié)果顯示在表2中，可以看到IA-DPC算法在一些數(shù)據(jù)集中具有低的F1值，但是相較于其他兩個(gè)算法，本文算法總體上優(yōu)于其他兩個(gè)算法.ARI結(jié)果顯示在表3中，從表3可以看出，IA-DPC算法在這些數(shù)據(jù)集中相較其他兩種算法，該算法幾乎都具有最大的ARI值.為了方便直觀的判斷，對(duì)表格中的數(shù)據(jù)集進(jìn)行可視化.

表2 F-MEASURE指標(biāo)

Table 2 F-measure index

AlgorithmsDatasetsCompoundAggregationBanded_dScatter1000D31IrisWineGlassCellCycle_384DPC0.7710.8120.7940.9600.9120.9520.8530.5250.475ADPC-KNN0.9020.9751.0000.8810.9550.9380.8100.8100.690IA-DPC0.8890.9381.0000.9480.9700.9400.9310.8270.899

表3 ARI指標(biāo)

Table 3 ARI index

AlgorithmsDatasetsCompoundAggregationBanded_dScatter1000D31IrisWineGlassCellCycle_384DPC0.7370.7540.7800.8260.8790.8780.5440.382-0.020ADPC-KNN0.8420.8751.0000.7610.9240.8300.5030.4930.393IA-DPC0.8550.8311.0000.8540.9470.8780.6100.5580.779

根據(jù)表中數(shù)據(jù)，可視化F1值、ARI值分別如圖5、圖6顯示，在人工數(shù)據(jù)集方面，IA-DPC算法具有更高的性能，或與其他兩種算法的性能幾乎相同.但在真實(shí)數(shù)據(jù)集方面，IA-DPC算法優(yōu)于其他兩種算法.

圖5 F1指標(biāo)

同時(shí)，如圖7所示，在IA-DPC算法中，根據(jù)調(diào)節(jié)比例系數(shù)的方法最終得到三個(gè)γ值，通過(guò)在算法中的比較，可以看出不同數(shù)據(jù)集的最優(yōu)γ值是不同的，并且可知比例系數(shù)越大，節(jié)點(diǎn)凝聚度也就越大，對(duì)區(qū)分聚類中心和其他節(jié)點(diǎn)的重要程度影響也就越大.因此，IA-DPC算法在實(shí)際應(yīng)用中具有特定的參考價(jià)值.

圖6 ARI指標(biāo)

4 結(jié) 論

在本研究中，針對(duì)密度峰值聚類算法在密度分布不均勻的數(shù)據(jù)集中難以產(chǎn)生良好的聚類效果，提出了一種改進(jìn)策略的算法.在實(shí)驗(yàn)數(shù)據(jù)集的驗(yàn)證中，IA-DPC算法在處理密度分布不均勻的數(shù)據(jù)集時(shí)具有一定的優(yōu)勢(shì)，能夠提高DPC算法的聚類效率，從而更加準(zhǔn)確的聚類.但是該算法也需要一定的參數(shù)設(shè)置，有人為因素的影響，并且該算法時(shí)間復(fù)雜度高，核心算法時(shí)間復(fù)雜度高達(dá)O(n3)，對(duì)于處理高維數(shù)據(jù)，效果不理想.在以后的研究中，重點(diǎn)會(huì)放在解決高維數(shù)據(jù)聚類方面.

圖7 比例系數(shù)γ