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

孫 綿 侯再恩 韓肖赟

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

0 引 言

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

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

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

1 CFSFDP算法

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

算法的基本模型是：

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

2) 根據γ函數選取聚類中心；

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

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

(1)

式中:

高斯核定義為：

(2)

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

截斷核表示離散值，高斯核表示連續值。考慮到截斷核對于不同數據點易出現具有同一局部密度值的情況，本文采用高斯核計算方式。

ρq1≥ρq2≥…≥ρqN

則考慮δi定義如下：

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

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

(a)

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

2 CFSFDP算法的改進

2.1 距離δ的確定

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

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

2.2 聚類中心的選取

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

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

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

γi=ρiδii∈IS

本文選用max-min標準化方法，對ρ和δ原始數據進行線性變換，則γ函數重新定義如下：

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

綜上所述，改進CFSFDP算法以代價函數取得最小值作為聚類準則：

s.t.qj>qi,j

2.3 改進算法實現

算法的具體實現步驟如下：

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

輸出：數據集S各樣本點的聚類結果

步驟：

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

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

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

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

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

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

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

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

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

3 數值模擬

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

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

3.1 聚類效果圖

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

表1 實驗各數據集屬性表

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

(a)

(b)

(c)

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

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

(a)

(b)

(c)

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

3.2 各聚類算法評價指標對比

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

表2 實驗各數據集屬性表

設U為樣本實際類別分配情況，V為樣本聚類后的標簽預測情況。各評價指標[15]定義如下:

1) 調整蘭德系數:

2) 同質性:

3) 完整性:

4) V_measure:

5) 標準互信息評分:

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

表3 各算法在Iris數據集的各指標值對比

表4 各算法對R15數據集的各指標值對比

表5 各算法對waveform數據集的各指標值對比

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

3.3 各算法時間復雜度分析

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

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

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

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

4 結 語

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