王 超 潘正高 路紅梅 李雪竹

（宿州學(xué)院信息工程學(xué)院 安徽宿州 234000）

基于拉普拉斯矩陣的K-mean聚類

王 超 潘正高 路紅梅 李雪竹

（宿州學(xué)院信息工程學(xué)院 安徽宿州 234000）

譜聚類的方法被廣泛用在模式識別各個(gè)領(lǐng)域。文章運(yùn)用K-mean聚類方法，主要闡述了如何由樣本的相似度矩陣構(gòu)造的拉普拉斯矩陣來求解樣本的低維映射譜，根據(jù)低維映射譜進(jìn)行譜聚類。

拉普拉斯矩陣；譜聚類；K-means

樣本聚類是無監(jiān)督學(xué)習(xí)的一種重要分類方法。對于無標(biāo)簽的樣本，要實(shí)現(xiàn)分類只能根據(jù)樣本本身的相似度進(jìn)行分類，度量樣本相似度就是相似度聚類[1]。傳統(tǒng)聚類方法要知道樣本在N維空間的矢量[2]。但是拉普拉斯譜聚類的方法只需要知道樣本的相似度矩陣就能進(jìn)行聚類。

一、圖譜理論到拉普拉斯矩陣

拉普拉斯矩陣式表示圖的一種矩陣，給定一個(gè)n個(gè)頂點(diǎn)的圖，則拉普拉斯矩陣被定義為：L=D-W

其中D為圖的度矩陣，W為圖的鄰接矩陣。

舉個(gè)例子，給定一個(gè)簡單圖，如下:

圖1 一個(gè)鄰接圖

把該圖轉(zhuǎn)化成鄰接矩陣的形式記為W則：

把W的每一列元素加起來得到n個(gè)數(shù)，然后把這個(gè)數(shù)放在對角線上其余位置都是零，組成一個(gè)n×n的對角矩陣，記為度矩陣D，如下所示：

根據(jù)拉普拉斯定義L=D-W可得拉普拉斯矩陣如下所示：

通過上面這個(gè)簡單例子，我們明白了拉普拉斯矩陣在連接圖上的定義。下面我們對于更一般的情況的數(shù)學(xué)描述如下：對于一個(gè)圖中定義A子圖和B子圖[3]，它們之間的所有邊的權(quán)值之和可以由鄰接矩陣W的一般形式求解如下：

其中，Wij定義為節(jié)點(diǎn)i到節(jié)點(diǎn)j的權(quán)值，如果兩個(gè)節(jié)點(diǎn)不相連，則權(quán)值為零。與某個(gè)節(jié)點(diǎn)i鄰接的所有邊的權(quán)值之和定義為該頂點(diǎn)i的度di，多個(gè)di形成一個(gè)度矩陣D。

由以上定義可知拉普拉斯矩陣的性質(zhì)如下：

（1）L是對稱半正定矩陣；

（2）L·1=0·1，即L的最小特征值是0，相應(yīng)的特征向量是1；

（3）L有n個(gè)非負(fù)特征值0=λ1≤λ2≤…λn；

（4）對于任何一個(gè)實(shí)向量υ?Rn，有以下表達(dá)式成立：

對性質(zhì)（4）的證明如下：

二、聚類的圖譜解釋

聚類是把一堆樣本合理地分成兩份或份。從圖論的角度看，聚類問題就是圖的分割問題[4]。給定一個(gè)圖G=（V,M），頂點(diǎn)集表示各樣本，帶權(quán)的邊表示各樣本之間的相似度，譜聚類的目的是要找到一種合理的分割圖的方法，把圖分割為若干個(gè)子圖，使得連接不同子圖的邊的權(quán)重或者相似度盡可能的低，同一子圖內(nèi)邊的權(quán)重或者相似度盡可能高。相似的聚集在一起，不相似的彼此遠(yuǎn)離。為了達(dá)到這樣一個(gè)目的，就需要被切割的這些邊的權(quán)值之和最小[5]。

假設(shè)圖不相交的子圖分別為A1，A2，…，AK，求其代價(jià)最小的分割的目標(biāo)函數(shù)如下：

其中k表示分成了k個(gè)組，Ai表示第i組，Ai表示Ai的補(bǔ)集表示Ai,與Ai相連的所有邊之和。綜合上式就表示所有要切割的邊的權(quán)重之和。就是分割成個(gè)組要使得上式取最小值。這個(gè)目標(biāo)函數(shù)在實(shí)際的操作中，常常把圖分割為一個(gè)點(diǎn)和其余n-1各點(diǎn)。為了讓每個(gè)圖都有合適的大小，上述的目標(biāo)函數(shù)改寫成如下式子：

下面對這個(gè)目標(biāo)函數(shù)進(jìn)行推導(dǎo)：

則上式可以化為：

我們從RatioCut推導(dǎo)出了vTLv，這也就是說拉普拉斯矩陣L和我們要優(yōu)化的目標(biāo)函數(shù)RatioCut有密切的聯(lián)系。因?yàn)槭且粋€(gè)常量。最小化RatioCut，也就是最小化vTLv。

又因?yàn)椋?/p>

顯然上式n是一個(gè)定值，要最小化vTLv也就是最小化λ。因此我們下面只有找到拉普拉斯矩陣L最小特征值是零，對應(yīng)的特征向量就行了。這里有一個(gè)問題，就是我們討論過的拉普拉斯矩陣最小特征值是零，對應(yīng)的特征向量是1。不滿足v⊥1的條件了，這里根據(jù)文獻(xiàn)[2]所說理論。我們?nèi)〉?小特征值對應(yīng)特征向量。進(jìn)一步，由于實(shí)際中的特征向量里的元素是連續(xù)的任意實(shí)數(shù)，所以可以根據(jù)v是大于0還是小于0對應(yīng)到離散情況下的，決定vi是取還是取。而如果能求取v的前K個(gè)特征向量，進(jìn)行K-means聚類，得到K個(gè)簇，便從二聚類擴(kuò)展到了K聚類問題。而這里要求的K個(gè)特征向量就是拉普拉斯矩陣的特征向量。所以問題就轉(zhuǎn)換成了：求取拉普拉斯矩陣的前K特征值對應(yīng)的特征向量，然后用這前K個(gè)特征值對應(yīng)的特征向量進(jìn)行K-means聚類。

三、K-means聚類

（一）隨機(jī)在圖中取K個(gè)點(diǎn)作為中心點(diǎn)。

（二）然后計(jì)算圖中所有點(diǎn)到K個(gè)中心點(diǎn)距離，假如P點(diǎn)離中心點(diǎn)S點(diǎn)最近，那么P點(diǎn)屬于S點(diǎn)群。

（三）分完群計(jì)算點(diǎn)群中心，用新的中心點(diǎn)作為點(diǎn)群中心點(diǎn)。

（四）重復(fù)步驟（2）和（3），直到中心點(diǎn)不再移動(dòng)，聚類完畢。

四、結(jié)語

基于拉普拉斯矩陣的K-means聚類,一般步驟如下：

（一）根據(jù)數(shù)據(jù)構(gòu)造一個(gè)圖，圖中每一個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)數(shù)據(jù)點(diǎn)，將各個(gè)數(shù)據(jù)點(diǎn)連接起來，并且邊的權(quán)重表示數(shù)據(jù)的相似度。把這個(gè)圖用鄰接矩陣W表示出來。

（二）把鄰接矩陣每一列元素加起來得到n個(gè)數(shù)，把它們放在對角線上，其他地方補(bǔ)零構(gòu)成一個(gè)的對角陣，記為度矩陣D，并構(gòu)造拉普拉斯矩陣L且L=D-W。

（三）求出拉普拉斯矩陣的前K個(gè)特征值對應(yīng)的特征向量，特征值由小到大順序排列的。

（四）把這些特征向量（列向量）排列在一起組成一個(gè)nx·k的矩陣，將其中每一行看做k維空間的一個(gè)向量，并使用K-means算法進(jìn)行聚類。聚類結(jié)果每一行所屬類別就是圖中節(jié)點(diǎn)也就是n個(gè)數(shù)據(jù)點(diǎn)分別所屬類別。

譜聚類算法和傳統(tǒng)聚類方法相比，譜聚類只需要數(shù)據(jù)之間的相似度矩陣就可以了，而不必想單純K-means聚類需要數(shù)據(jù)在N維歐式空間中的向量。

[1]H.Zha,C.Ding,M.Gu,X.He,and H.D.Simon.Spectral relaxationfor K-meansclustering[C].AdvancesinNeuralInformation ProcessingSystems14,Vancouver,Canada.Dec.2001:1057-1064.

[2]Fouss,F.,Pirotte,A.,Renders,J.-M.,and Saerens,M.. Random-walk computation of similar-ities between nodes of a graph with application to collaborative recommendation[J].IEEE Trans.Knowl.DataEng.[J].2007,19(3):355-369.

[3]Kannan,R.,Vempala,S.,andVetta,A..Onclusterings:Good, badandspectral.JournaloftheACM[J].2004,51(3):497-515.

[4]Hagen,L.andKahng,A.Newspectralmethodsforratiocut partitioning and clustering.IEEE Trans.Computer-Aided Design [J].1992,11(9):1074-1085.

[5]Gutman,I.andXiao,W.Generalizedinverse of the Laplacian matrixandsomeap plications[J].Bulletindel’Academie Serbedes Sciencesatdes Arts(Cl.Math.Natur.),2004,129:15-23.

[責(zé)任編輯 鄭麗娟]

TP391

A

2095-0438（2017）09-0153-03

2017-05-09

王超（1981-），男，安徽宿州人，宿州學(xué)院信息工程學(xué)院助教，碩士，研究方向：模式識別、人工智能、物聯(lián)網(wǎng)、圖像處理。

安徽省青年人才支持項(xiàng)目（gxfxzd2016256）；安徽省科技廳科技攻關(guān)項(xiàng)目（1502052053）。