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

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

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

0 引 言

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

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

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

1 DPC算法

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

(1)

(2)

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

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

(3)

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

(4)

具有ρi和δi，以γ作為選擇聚類中心的指標(biāo)，γ的計(jì)算公式為

γ=ρδ

(5)

2 MCF-DPC算法

2.1 改進(jìn)的局部密度計(jì)算公式

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

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

(6)

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

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

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

(7)

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

定義2 離心率φi

(8)

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

(9)

2.2 融合策略

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

定義4 數(shù)據(jù)加權(quán)內(nèi)平均距離α

(10)

定義5 簇間密度差CD

(11)

定義6 簇間距離CB

CB=min(d(ri,rj))

(12)

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

MCF(A,B)=CB·CD2

(13)

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

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

輸出：聚類結(jié)果

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

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

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

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

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

5)輸出聚類結(jié)果

2.3 非負(fù)矩陣分解

NMF由Lee和Seung在2000年提出的基于特征變換的數(shù)據(jù)降維方法[14]。NMF的思想：給定要分解的非負(fù)矩陣X(m*n)，計(jì)算滿足以下表達(dá)式的非負(fù)矩陣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)

用梯度下降法求解目標(biāo)函數(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è)置迭代次數(shù)k

fort

end for

3)輸出Y=H

2.4 算法流程

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

算法3 MCF-DPC算法

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

輸出：聚類結(jié)果

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

2)計(jì)算距離矩陣dij

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

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

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

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

7)按照算法1進(jìn)行微簇融合

8)輸出聚類結(jié)果

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

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

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

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

圖1 MCF-DPC的聚類結(jié)果

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

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

4 結(jié)束語

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

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