基于多密度峰值的CFSFDP算法改進

孫 綿 侯再恩 韓肖赟

(陜西科技大學(xué)文理學(xué)院 西安 710021)

0 引 言

基于密度的聚類算法是遵循數(shù)據(jù)點的密集程度展開聚類，主要針對任意形狀的數(shù)據(jù)集。經(jīng)典的基于密度的聚類算法有OPTICS算法、DBSCAN算法等，其中，OPTICS算法存在擴展性低、算法復(fù)雜度高的缺陷；DBSCAN算法對輸入?yún)?shù)敏感、聚類收斂時間較長等。

針對這些不足，CFSFDP算法[1]作為一種新的密度算法被提出，其對任意形狀的數(shù)據(jù)集尤其是非球形數(shù)據(jù)集能夠有效識別，并且算法僅需設(shè)定一個參數(shù)，算法結(jié)果對參數(shù)選取也不敏感[2]。同時因為其算法原理簡單易實現(xiàn)、聚類效果優(yōu)而備受關(guān)注。經(jīng)過深入研究，盡管該算法有許多優(yōu)點，但是也存在一些缺陷有待完善。文獻[3-4]采用簇中心點自動選擇策略，避免通過決策圖主觀確定聚類中心個數(shù)帶來的誤差；文獻[5]將模糊的概念用到CFSFDP算法來實現(xiàn)聚類中心的自適應(yīng)選??；文獻[6]利用局部反差方法解決了CFSFDP算法難以發(fā)現(xiàn)稀疏類簇的問題；文獻[7-8]采用熵實現(xiàn)了截斷距離的自適應(yīng)，并取得了良好的聚類效果；文獻[9-12]提出了一種基于網(wǎng)格的CFSFDP算法，該算法利用網(wǎng)格劃分來計算局部密度并降低算法的時間復(fù)雜度；文獻[13]將密度比例引入到CFSFDP算法，解決了對類簇間密度較小數(shù)據(jù)集不能很好聚類的問題，提高了聚類準(zhǔn)確率；文獻[14]為了克服無法準(zhǔn)確聚類多密度峰值的缺陷，提出了一種基于近鄰距離曲線和類合并優(yōu)化的CFSFDP算法。

考慮到單個簇中存在多密度峰值時易造成簇的分裂，以及利用決策圖無法正確選取存在多個聚類中心個數(shù)的問題，本文提出把所有密度大于當(dāng)前位置的數(shù)據(jù)點以及與當(dāng)前位置的最小距離分別做成一個集合，對局部密度進行排序。在存在多個密度峰值時，僅選擇第一個點作為聚類中心，并且利用歸一化的γ函數(shù)數(shù)值分布做決策圖輔助圖選取聚類中心數(shù)量。模擬實驗結(jié)果表明，本文提出的改進CFSFDP算法與CFSFDP相比，聚類效果更好，更適合于對較低維度的不規(guī)則形數(shù)據(jù)集進行聚類。

1 CFSFDP算法

CFSFDP算法是一種簡潔優(yōu)美的聚類算法，可識別任意形狀的類簇，并且僅有一個參數(shù)。核心思想是，在聚類中心的選擇中，聚類中心本身具有相對高的密度，而密度較大的其他數(shù)據(jù)點之間的距離相對較大。

算法的基本模型是：

1) 計算各數(shù)據(jù)點的密度以及高局部密度點距離；

2) 根據(jù)γ函數(shù)選取聚類中心；

3) 對非聚類中心點進行聚類，確定每個數(shù)據(jù)點的最終歸類。

1) 局部密度ρ。計算局部密度有截斷核和高斯核兩種方式，前者定義如下：

(1)

式中:

高斯核定義為：

(2)

式中：IS={1,2,…,N}為數(shù)據(jù)集S對應(yīng)的指標(biāo)集，dij=dist(xi,xj)表示數(shù)據(jù)點xi和xj之間的距離，參數(shù)dc>0，需提前設(shè)定，通常取所有數(shù)據(jù)點兩兩之間的距離經(jīng)過升序排列后的前1%～2%。

截斷核表示離散值，高斯核表示連續(xù)值?？紤]到截斷核對于不同數(shù)據(jù)點易出現(xiàn)具有同一局部密度值的情況，本文采用高斯核計算方式。

ρq1≥ρq2≥…≥ρqN

則考慮δi定義如下：

由定義可知當(dāng)數(shù)據(jù)點xqi具有最大局部密度時，δqj取最大值，足以保證xqi被選為聚類中心。

3) 決策圖。文獻[2]中對28個數(shù)據(jù)點的原始數(shù)據(jù)圖分布以及關(guān)于(ρ,δ)做出的決策圖如圖1所示，決策圖對聚類中心的選取起著關(guān)鍵作用。對照圖1(a)和(b)發(fā)現(xiàn)，1號和10號數(shù)據(jù)點同時有著較大的ρ和δ值，并且恰好是原始數(shù)據(jù)集中的聚類中心；而對于26、27、28號數(shù)據(jù)，由于其δ值很大，ρ值很小，在原始數(shù)據(jù)集中充當(dāng)離群點。上述聚類中心的選取方案中定性因素太多，即使是同樣的決策圖，不同的人得到的結(jié)果也不同，尤其是對有著多個聚類中心并且個數(shù)難以確定的數(shù)據(jù)，利用決策圖無法正確選出聚類中心。文獻[2]中提到綜合考慮ρ和δ值，建立γ函數(shù)，依據(jù)γi=ρiδi的值選取聚類中心，值越大，越有可能是聚類中心。并將所有γ值進行降序排列，取前若干個數(shù)據(jù)點作為聚類中心即可，但是若干個并非自動選取，也是帶有一定的主觀性。同時，對于較大的γ值存在ρ值很大δ值很小或者δ值很大ρ值很小的情況，易誤將離群點選作聚類中心。針對這一缺陷，本文將做出一定改進，提高聚類中心選取的準(zhǔn)確率。

(a)

(b)圖1 關(guān)于決策圖的實例示意圖

2 CFSFDP算法的改進

2.1 距離δ的確定

對于單個簇中存在多個密度大于自身且距離自身的最小距離δ相同的數(shù)據(jù)點，這些點均易被選為聚類中心，從而造成簇的分裂，以及聚類中心的多選。

針對這一問題，對式(2)所得數(shù)據(jù)點的密度進行降序排列，形成先后順序，并且對點密度大于當(dāng)前點的所有數(shù)據(jù)點以及與當(dāng)前點的所有最小距離分別做成一個集合，保證在存在多個密度大于自己且距離自己最近的點中只選擇排在前面的第一個點作為聚類中心，避免簇的分裂。

2.2 聚類中心的選取

針對CFSFDP算法易將數(shù)據(jù)集中密度大而距離小或者距離大而密度小的數(shù)據(jù)點選為聚類中心，從而造成聚類中心的錯選，文獻[8]提出利用信息熵實現(xiàn)截斷距離dc的自適應(yīng)，并將得到的最優(yōu)值設(shè)為潛在聚類中心的距離閾值，避免將密度大而距離小的數(shù)據(jù)錯選為聚類中心。

本文分析了局部密度和最小距離的數(shù)值，可知它們是兩個不同數(shù)量級的。為了避免不同數(shù)量級數(shù)字之間相互影響，防止大數(shù)吃小數(shù)等情況，對其進行歸一 化處理，原始數(shù)據(jù)經(jīng)過處理后，各指標(biāo)處于同一數(shù)量級的，使得聚類中心點到非聚類中心點的γ值變化趨勢更加明顯，尤其是非聚類中心點的γ值變化趨勢更加平滑，從而實現(xiàn)聚類中心的正確選取。

文獻[2]中提到聚類中心的選取依靠γ函數(shù)，綜合考慮ρ和δ值，定義如下：

γi=ρiδii∈IS

本文選用max-min標(biāo)準(zhǔn)化方法，對ρ和δ原始數(shù)據(jù)進行線性變換，則γ函數(shù)重新定義如下：

對有著多個聚類中心并且個數(shù)難以確定的數(shù)據(jù)集，利用決策圖無法正確選取出聚類中心。利用上式求出各數(shù)據(jù)點的γ值，并對各數(shù)據(jù)點γ值的分布做決策圖輔助圖，圖中從聚類中心到非聚類中心時會有一個明顯的跳躍，根據(jù)這個趨勢可實現(xiàn)聚類中心個數(shù)的準(zhǔn)確選取。

綜上所述，改進CFSFDP算法以代價函數(shù)取得最小值作為聚類準(zhǔn)則：

s.t.qj>qi,j

2.3 改進算法實現(xiàn)

算法的具體實現(xiàn)步驟如下：

輸入：數(shù)據(jù)集S={x1,x2,…,xN}，截斷距離參數(shù)dc

輸出：數(shù)據(jù)集S各樣本點的聚類結(jié)果

步驟：

1) 計算數(shù)據(jù)集S中任意兩點間的距離矩陣；

2) 根據(jù)t(t=2)選擇合適的dc；

3) 按照式(2)計算各樣本點的局部密度ρ；

4) 根據(jù)式(3)計算各樣本點的距離δ；

5) 把大于當(dāng)前位置的多個密度值和最小距離各歸為一個集合，只選擇第一個點作為聚類中心；

6) 按照式(4)計算各樣本點的γ值；

7) 利用各點降序排列的γ值分布圖做決策圖輔助圖選取聚類中心數(shù)量；

8) 對非聚類中心點完成聚類，確定各點最終的歸屬。

本文提出的改進CFSFDP算法在保持原有算法尋找聚類中心的思想上，對γ函數(shù)進行了歸一化處理，利用各數(shù)據(jù)點γ值的分布圖做決策圖輔助圖，實現(xiàn)聚類中心個數(shù)的選取。并且為了防止簇的分裂，對于同一簇中存在多個密度峰值的簇，只選擇第一個高局部密度點計算局部高密度最小距離，避免簇的分裂，也提高了聚類中心選取的準(zhǔn)確率。

3 數(shù)值模擬

為了檢驗改進算法的聚類效果，本文利用人工數(shù)據(jù)集和UCI數(shù)據(jù)集進行數(shù)值模擬實驗，分別對DBSCAN算法、k-means算法、CFSFDP算法和改進的CFSFDP算法的實驗結(jié)果以聚類效果圖和各聚類算法的調(diào)整蘭德系數(shù)、互信息評分、同質(zhì)性、完整性和V-measure等評價指標(biāo)結(jié)果對比呈現(xiàn)改進性能。

實驗軟件和硬件環(huán)境是：CPU：Inter(R) Core(TM) i5-3470@ 3.20 GHz；操作系統(tǒng)：Windows10 64位，內(nèi)存：4 GB；編程軟件：Python 3。

3.1 聚類效果圖

這部分實驗采用數(shù)據(jù)集Spiral和Aggregation，具體屬性如表1所示。

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

Spiral數(shù)據(jù)集分布較為特殊，呈環(huán)狀分布，因此其對算法的參數(shù)設(shè)置十分敏感，圖2是各算法對Spiral數(shù)據(jù)集的聚類效果圖。由圖2(a)可知DBSCAN算法因為對參數(shù)選取敏感，故其在聚類過程中產(chǎn)生了少量噪聲點；圖2(b)中K-means算法出現(xiàn)了混亂的聚類結(jié)果；圖2(c)和2(d)所示的CFSFDP算法和改進的CFSFDP算法因為僅有一個參數(shù)，并且算法對參數(shù)的選取有一定魯棒性，因此都產(chǎn)生了較好的聚類效果。

(a)

(b)

(c)

(d)圖2 Spiral數(shù)據(jù)集各算法聚類效果圖

Aggregation數(shù)據(jù)集中有幾個類簇距離較近，易產(chǎn)生簇的混亂。圖3(b)和(c)分別為K-means算法和CFSFDP算法的聚類效果圖，聚類效果不佳，CFSFDP算法由于利用決策圖主觀性地對聚類中心個數(shù)進行選擇，導(dǎo)致聚類中心個數(shù)的錯選，使得聚類結(jié)果出錯；圖3(a)和(d)所示,DBSCAN算法和改進的CFSFDP算法對數(shù)據(jù)集的聚類效果良好，尤其是改進的CFSFDP算法利用重新定義的γ函數(shù)值做決策圖輔助圖，實現(xiàn)了聚類中心的正確選取。

(a)

(b)

(c)

(d)圖3 Aggregation數(shù)據(jù)集各算法聚類效果圖

3.2 各聚類算法評價指標(biāo)對比

實驗采用人工數(shù)據(jù)集R15和UCI數(shù)據(jù)集Iris和waveform進行測試，數(shù)據(jù)的具體屬性如表2所示。利用這些數(shù)據(jù)集主要對各算法的調(diào)整蘭德系數(shù)、同質(zhì)性、完整性、V-measure和標(biāo)準(zhǔn)互信息評分等評價指標(biāo)的結(jié)果進行對比。

表2 實驗各數(shù)據(jù)集屬性表

設(shè)U為樣本實際類別分配情況，V為樣本聚類后的標(biāo)簽預(yù)測情況。各評價指標(biāo)[15]定義如下:

1) 調(diào)整蘭德系數(shù):

2) 同質(zhì)性:

3) 完整性:

4) V_measure:

5) 標(biāo)準(zhǔn)互信息評分:

上述公式中，ARI測量兩個數(shù)據(jù)分布之間的一致程度，它具有高度的區(qū)分性，并且值范圍是[-1,1]。V-measure是H和C的調(diào)和平均，取值范圍為[0,1]，常用來評估聚類模型的性能好壞。NMI是MI的標(biāo)準(zhǔn)化，用來衡量實際類別和預(yù)測類別的相似性，取值范圍為[0,1]，上述范圍越接近于1說明聚類結(jié)果越好。實驗結(jié)果如表3至表5所示。

表3 各算法在Iris數(shù)據(jù)集的各指標(biāo)值對比

表4 各算法對R15數(shù)據(jù)集的各指標(biāo)值對比

表5 各算法對waveform數(shù)據(jù)集的各指標(biāo)值對比

Iris數(shù)據(jù)集是聚類分析中常用的數(shù)據(jù)集，由表3可知，本文改進的CFSFDP算法的各項評價指標(biāo)都優(yōu)于其他算法，并且ARI的指標(biāo)值最好，高于0.95，DBSCAN算法的聚類效果最差，這是因為此數(shù)據(jù)集中存在樣本分布稀疏的簇，使得DBSCAN算法將這些稀疏點作為噪聲點處理，導(dǎo)致聚類精度較差。R15數(shù)據(jù)集中間的8個類簇距離很近，易造成簇混亂的情況，從表4的結(jié)果來看，改進的CFSFDP算法取得了較好的聚類結(jié)果，各項評價指標(biāo)都很優(yōu)，K-means算法中的k是需要提前指定的，k的隨機選取易使得算法陷入局部最優(yōu)，導(dǎo)致聚類結(jié)果不理想，造成各項評價指標(biāo)最低。waveform數(shù)據(jù)集共21維，有5 000個樣本點，是一個有著較高維度的大數(shù)據(jù)集，從表5的實驗結(jié)果來看，改進的CFSFDP算法ARI指標(biāo)值雖然是最好的，但是其他指標(biāo)的值還是略低于K-means算法，但是遠好于DBSCAN算法。

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

觀察到改進CFSFDP算法對較高維度的大數(shù)據(jù)集聚類效果不理想，因此比較和分析各算法的時間復(fù)雜度，對上述實驗各算法運行時間進行對比分析，結(jié)果如表6所示。

表6 各算法運行時間對比分析 s

從表6可以看出，改進CFSFDP算法雖然產(chǎn)生了較好的聚類效果，但是其算法運行時間略長于其他算法。這是由于其在具體計算中，需要對數(shù)據(jù)集中任意兩點間的歐式距離進行計算，尤其是對維度較高的大數(shù)據(jù)集進行計算時，需要完成大量歐式距離的計算，還要完成數(shù)據(jù)集樣本點局部密度和最小距離的計算，因此算法的時間復(fù)雜度至少為O(N2)。CFSFDP算法的時間復(fù)雜度是O(N2)，K-means算法的時間復(fù)雜度為O(Nkt)，DBSCAN算法的時間復(fù)雜度與數(shù)據(jù)集的維度有關(guān)，上界為O(N2)。

綜上所述，改進CFSFDP算法的聚類性能整體上優(yōu)于基本CFSFDP算法、K-means算法和DBSCAN算法，該算法非常適合于對較低維度數(shù)據(jù)集的聚類處理。

4 結(jié) 語

本文針對CFSFDP算法對單個簇中存在多密度峰值時聚類效果不理想的情況，提出將所有密度大于當(dāng)前位置的數(shù)據(jù)點以及與當(dāng)前位置的較近距離各做成一個集合，對局部密度進行排序，在存在多個密度峰值時只選擇第一個點作為聚類中心，并且利用各數(shù)據(jù)點歸一化的γ值分布圖確定聚類中心數(shù)。通過數(shù)值分析發(fā)現(xiàn)，改進的CFSFDP算法適用于對任意形狀特別是存在多密度峰值的較低維數(shù)據(jù)集的聚類。但是其算法運行時間還是略長，如何提升算法運行效率，尤其是對較高維度數(shù)據(jù)集的聚類將是下一步的研究重點。