吳辰文，魏立鑫，劉曉光

1(蘭州交通大學 電子與信息工程學院，蘭州 730070) 2(蘭州交通大學 電子與信息工程學院 計算機應用技術，蘭州 730070) 3(蘭州交通大學 電子與信息工程學院 軟件工程，蘭州 730070)

1 引 言

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

根據(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].除了這些經典的算法之外，于2014年在《Science》學術期刊中發(fā)表了一種新的密度峰值聚類算法[8](Density Peaks Clustering，DPC)引起了廣泛的關注.

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

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

2 密度峰值聚類算法與改進節(jié)點凝聚度

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

2.1 密度峰值聚類算法原理

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

定義局部密度ρi：

(1)

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

(2)

定義距離值δi：

(3)

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

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

2.2 改進的節(jié)點凝聚度

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

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

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

(4)

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

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

(5)

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

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

(6)

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

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

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

(7)

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

(8)

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

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

(9)

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

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

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

圖1 網(wǎng)絡G

圖2 網(wǎng)絡G*

(10)

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

(11)

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

(12)

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

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

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

IA-DPC算法具體步驟：

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

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

Step 4.計算G′的加權凝聚度，并計算G中節(jié)點的重要度IMCn(當G轉化為G*后，計算G*中邊轉化為節(jié)點后的重要度IMCe)；

Step 5.將G轉化為G*，重復Step 2～Step 4；

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

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

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

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

3 實驗仿真與結果分析

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

在所有算法中，三種算法都有設置參數(shù)的情況，DPC需要設置截斷距離dc，通過決策圖需要手動選取聚類中心，ADPC-KNN該算法需要設置k近鄰的個數(shù)，對于IA-DPC算法需要調節(jié)比例系數(shù)γ及截斷距離dc的設定.在IA-DPC算法中根據(jù)γ的調節(jié)方式選取效果最好的聚類結果進行展示.DPC和IA-DPC截斷距離dc值都是選取所有數(shù)據(jù)點中距離值個數(shù)排序的1%～2%處距離值的平均值.經過算法在數(shù)據(jù)集上的多次實驗，選擇結果最佳的圖形展示.

表1 實驗數(shù)據(jù)集

Table 1 Experimental datasets

DatasetInstancesDimensionsClustersCompound39926Aggregation78827Banded_d51234Scatter1000100034D313100331Iris15053Wine178143Glass214106CellCycle_384384175

3.1 聚類結果分析

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

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

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

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

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

接下來，使用真實數(shù)據(jù)集進行實驗驗證，這些數(shù)據(jù)集來自UCI，包括Iris數(shù)據(jù)集，Wine數(shù)據(jù)集和Glass數(shù)據(jù)集.還使用了一個酵母菌Gene數(shù)據(jù)集進行實驗，實驗結果如下：

CellCycle_384數(shù)據(jù)集[21，22]用于觀察細胞中基因轉錄水平的周期性變化.它是具有先驗知識的數(shù)據(jù)集.從全基因組中選擇總共384個基因，將同一時刻達到轉錄峰值的基因作為一個標準類.

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

3.2 算法指標分析

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

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

表2 F-MEASURE指標

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指標

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ù)據(jù)集方面，IA-DPC算法優(yōu)于其他兩種算法.

圖5 F1指標

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

圖6 ARI指標

4 結 論

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

圖7 比例系數(shù)γ