基于微簇融合的密度峰值聚類算法

宋紫陽，張 菁，劉小康，劉傳修

(上海工程技術大學 電子電氣工程學院，上海 201620)

0 引 言

聚類屬于無監(jiān)督分類，度量根據(jù)數(shù)據(jù)的相似性，將數(shù)據(jù)劃分為不同簇，使得同簇中數(shù)據(jù)具有較高的相似性，不同簇的數(shù)據(jù)間具有較大差異性[1]。常見的聚類算法有三種：1)K-means算法屬于基于分區(qū)的算法，參數(shù)設置簡單，但該算法存在對聚類中心較為敏感、需要手動設置聚類中心個數(shù)和無法辨別噪聲點的不足[2,3]；2)BIRCH算法屬于層次劃分，聚類結果與數(shù)據(jù)輸入順序有關[4]；3)STING算法作為基于網格劃分算法，將空間劃分為不同的網格單元[5]，效果取決于網格的最低力度，太大或者太小都無法識別[6]。

基于密度的聚類算法屬于典型非參數(shù)型算法，其樣本點的分布具有某種概率[7]。Rodriguez A和Laio A[8]開發(fā)了一種密度峰值聚類(density peak clustering,DPC)算法，該算法可以根據(jù)決策圖確定聚類中心并檢測非球形聚類，而無需指定聚類數(shù)。文獻[9]認為DPC算法的參數(shù)計算過于簡單，忽略數(shù)據(jù)間的相關性，并在高維數(shù)據(jù)表現(xiàn)結果不佳，對此提出了ADPC-FLD算法，該算法引入皮爾遜相關系數(shù)來計算ρi和δi，采用Fisher對數(shù)據(jù)進行降維處理。文獻[10]認為DPC算法過于依賴ρi和δi，存在參數(shù)選擇的問題，提出了一種基于GSA的混合聚類方法(GSA-DPC)，改進了截止距離的選擇機制，提高聚類精度，并基于GSA框架設計了優(yōu)化聚類中心的方法，采用遺傳算法(GA)尋優(yōu)。文獻[11]認為當簇中含有多個密度峰時，DPC算法易將一個簇分為多個簇，提出一種基于支持向量機的新型合并策略(FDPC)，利用支持向量機(SVM)計算每個聚類結果之間的反饋值，并根據(jù)反饋值進行微簇合并。

DPC算法在處理稀疏簇和密集簇時無法高效地找到聚類中心，在數(shù)據(jù)融合方面容錯性差。因此,本文提出一種新的聚類方法，即微簇可融合的密度峰值聚類算法。首先,重新定義了局部密度ρi計算公式，其次將融合策略與DPC算法結合，最后引入非負分解(NMF)算法，對高維數(shù)據(jù)進行降維，提高算法的魯棒性能。通過不同的數(shù)據(jù)集進行實驗，證明了本文改進算法在處理不同形狀簇的有效性。

1 DPC算法

DPC算法2014年發(fā)表在《Nature》上[12]，具有不需迭代、參數(shù)設置少及等快速找到聚類中心等特點，近年來其衍生的相關算法迅速發(fā)展。DPC算法的核心思想為：對于每個采樣點，首先計算兩個變量，即局部密度ρi和到鄰近最大密度δi的距離，然后每個采樣點xi∈X，X={x1,x2,…,xn}，局部密度ρi定義為

(1)

(2)

式中dij為數(shù)據(jù)點xi與數(shù)據(jù)點xj之間的距離，dc為截止距離。

到鄰近最大密度δi的距離定義為

(3)

對于具有高局部或全局密度的樣本點，沒有高密度的最近鄰，并且距離最近的較大密度點的距離簡單描述為

(4)

具有ρi和δi，以γ作為選擇聚類中心的指標，γ的計算公式為

γ=ρδ

(5)

2 MCF-DPC算法

2.1 改進的局部密度計算公式

K最近鄰(KNN)常用于分類、聚類等鄰域測量中[13]，給定數(shù)據(jù)點i，其knn(i)可表示為

knn(i)={j|dij≤di,kth(i)}

(6)

式中dij為i到j之間的歐氏距離，kth(i)為i的第k個鄰域。

本文根據(jù)KNN算法的思想定義一些MCF-DPC算法使用的概念，如下：

定義1 累計最近鄰度βk(i)

(7)

式中knn(i)為數(shù)據(jù)點i的k鄰域集合。

定義2 離心率φi

(8)

定義3 基于k鄰域的局部密度ρi

(9)

2.2 融合策略

傳統(tǒng)DPC算法對于數(shù)據(jù)聚合根據(jù)ρi和δi決定的決策圖選擇前幾個γ值大的點作為聚類中心，這種方案在處理同時具有密集和稀疏形狀的數(shù)據(jù)集時，算法的容錯性差，某一點的分配錯誤，帶來的影響將會被放大，嚴重影響聚類效果。因此本文提出了一種新的融合策略——微簇融合(micro-cluster fusion,MCF)。

定義4 數(shù)據(jù)加權內平均距離α

(10)

定義5 簇間密度差CD

(11)

定義6 簇間距離CB

CB=min(d(ri,rj))

(12)

式中n為數(shù)據(jù)維度，αij為數(shù)據(jù)點i到j的加權內平均距離。A和B為兩個微簇，ri和rj分別為A和B內的點，d(ri,rj)為ri和rj的距離。MCF可表示為

MCF(A,B)=CB·CD2

(13)

MCF(A,B)的值越大，說明微簇間差異性越大;反之，說明簇間相似性很大，可以進行微簇融合。對此需要設置一個閾值作為衡量簇間相似性的標準。通過實驗發(fā)現(xiàn)當MCF(A,B)小于閾值時，進行微簇融合聚類效果較佳。設閾值為所有數(shù)據(jù)MCF的平均值的1/5，即0.2×avg(MCF)時。微簇融合策略主要步驟如算法1。

輸入：處理后數(shù)據(jù)及聚類中心

輸出：聚類結果

1)按式(10)計算數(shù)據(jù)加權平均距離

2)按式(11)計算簇間密度差

3)按式(12)計算簇間距離

4)判斷MCF(A,B)是否小于閾值，符合則進行簇間融合

由表3可以看出，對于B分量圖像：面積在190～250之間的雞蛋，蛋黃指數(shù)大于0.72則判定為雙黃雞蛋；面積小于190的雞蛋，蛋黃指數(shù)的大于0.84則判定為雙黃雞蛋。

5)輸出聚類結果

2.3 非負矩陣分解

NMF由Lee和Seung在2000年提出的基于特征變換的數(shù)據(jù)降維方法[14]。NMF的思想：給定要分解的非負矩陣X(m*n)，計算滿足以下表達式的非負矩陣B(m*r)和H(r*n)

X≈B*H

(14)

式中 矩陣B稱為基矩陣，H稱為系數(shù)矩陣。參數(shù)r表示矩陣分解的秩，且小于m和n

(15)

minE(B,H),B>0,H>0

(16)

用梯度下降法求解目標函數(shù)，公式如下

(17)

數(shù)據(jù)降維主要步驟如算法2。

算法2數(shù)據(jù)降維算法

輸入：高維數(shù)據(jù)集X={x1,x2,…,xn}，n為樣本數(shù)

輸出：低維數(shù)據(jù)集Y={y1,y2,…,yn}

1)輸入原始矩陣X

2)設置迭代次數(shù)k

fort

end for

3)輸出Y=H

2.4 算法流程

MCF-DPC算法主要步驟如算法3所示。

算法3 MCF-DPC算法

輸入：數(shù)據(jù)集X={x1,x2,…,xn}，n為樣本數(shù)

輸出：聚類結果

1)調用算法2，獲得數(shù)據(jù)的系數(shù)矩陣H

2)計算距離矩陣dij

3)根據(jù)式(8)計算ρi，根據(jù)式(3)和式(4)計算δi

4)由式(5)計算γi，繪制決策圖并選擇聚類中心

5)將其他數(shù)據(jù)分配給聚類中心

6)刪除噪聲數(shù)據(jù)和異常值

7)按照算法1進行微簇融合

8)輸出聚類結果

3 實驗結果與分析

選取9個數(shù)據(jù)集，將本文所提的MCF-DPC算法與傳統(tǒng)的DPC算法、K-means以及DBSCAN算法進行比較，9個數(shù)據(jù)集具體參數(shù)如表1所示。

表1 6個合成數(shù)據(jù)集參數(shù)

K-means算法和DBSCAN算法具體參數(shù)均根據(jù)文獻[15]設置。部分MCF-DPC的聚類結果如圖1所示，各算法在不同數(shù)據(jù)集詳細的性能指標如表2。

圖1 MCF-DPC的聚類結果

表2 各聚類算法在不同數(shù)據(jù)集上的性能

表2所示的五種算法在所有綜合數(shù)據(jù)集上得分，最佳得分以粗體顯示。從表2中，可以看出該算法在大多數(shù)綜合數(shù)據(jù)集上的表現(xiàn)很好。MCF-DPC算法在7個數(shù)據(jù)集上表現(xiàn)最佳，在Jain，Iris，Wine和Seeds數(shù)據(jù)集上MCF-DPC算法是表現(xiàn)最佳的唯一算法。在Spiral數(shù)據(jù)集上除K-means算法外均能取得不錯的效果，可見對于簡單的螺旋狀的Spiral算法的參數(shù)設置對聚類結果影響不大。本文提出的微簇融合機制對聚類具有良好容錯性。

4 結束語

本文對傳統(tǒng)的DPC算法進行改進，通過改進局部密度計算公式和微簇融合策略引入提出了一種基于微簇融合的密度峰值聚類算法。改進的ρi更有效地解決傳統(tǒng)DPC聚類問題。提出的微簇融合策略改善DPC算法的容錯性，提高算法魯棒性。實驗結果表明:MCF-DPC算法可準確找到不規(guī)則形狀數(shù)據(jù)集聚類中心。

對于下一步工作，分為兩個方面：1)繼續(xù)改進ρi和δi自動根據(jù)不同數(shù)據(jù)集尋找對聚類中心;2)將MCF-DPC算法與其他算法結合，發(fā)揮其他算法優(yōu)勢，彌補MCF-DPC算法不足。