一、概述
對(duì)于下圖所示的數(shù)據(jù)進(jìn)行聚類废酷,可以采用GMM或者K-Means的方法:
然而對(duì)于下圖所示的數(shù)據(jù)瘟檩,單純的GMM和K-Means就無(wú)效了,可以通過(guò)核方法對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換澈蟆,然后再進(jìn)行聚類:
如果直接對(duì)上圖所示的數(shù)據(jù)進(jìn)行聚類的話可以考慮采用譜聚類(spectral clustering)的方法墨辛。
總結(jié)來(lái)說(shuō),聚類算法可以分為兩種思路:
①Compactness趴俘,這類有 K-means睹簇,GMM 等,但是這類算法只能處理凸集寥闪,為了處理非凸的樣本集太惠,必須引?核技巧。
②Connectivity疲憋,這類以譜聚類為代表凿渊。
二、基礎(chǔ)知識(shí)
- 無(wú)向權(quán)重圖
譜聚類的方法基于帶權(quán)重的無(wú)向圖缚柳,圖的每個(gè)節(jié)點(diǎn)是一個(gè)樣本點(diǎn)埃脏,圖的邊有權(quán)重,權(quán)重代表兩個(gè)樣本點(diǎn)的相似度秋忙。
假設(shè)總共個(gè)樣本點(diǎn)彩掐,這些樣本點(diǎn)構(gòu)成的圖可以用
表示,其中
灰追,圖中的每個(gè)點(diǎn)
也就代表了一個(gè)樣本
堵幽,
是邊,用鄰接矩陣(也是相似度矩陣)
來(lái)表示弹澎,
朴下,由于是無(wú)向圖,因此
裁奇。
另外還有度的概念桐猬,這里可以類比有向圖中的出度和入度的概念,不過(guò)圖中的點(diǎn)的度
并不是和該點(diǎn)相連的點(diǎn)的數(shù)量刽肠,而是和其相連的邊的權(quán)重之和溃肪,也就是鄰接矩陣的每一行的值加起來(lái)免胃,即:
而圖的度矩陣(對(duì)角矩陣)可以表示如下:
另外我們定義,對(duì)于點(diǎn)集的一個(gè)子集
惫撰,我們定義:
- 鄰接矩陣
構(gòu)建鄰接矩陣一共有三種方法羔沙,分別是
-近鄰法、
近鄰法和全連接法厨钻。
-
-近鄰法
首先需要設(shè)置一個(gè)閾值扼雏,比較任意兩點(diǎn)
與
之間的距離
與
的大小,定義鄰接矩陣如下:
這種方法表示如果兩個(gè)樣本點(diǎn)之間的歐氏距離的平方小于閾值夯膀,則它們之間是有邊的诗充。
使用這種方法,兩點(diǎn)相似度只有和
兩個(gè)值诱建,這種度量很不精確蝴蜓,因此在實(shí)際應(yīng)用中很少使用
-近鄰法。
-
近鄰法
使用KNN算法遍歷所有樣本點(diǎn)俺猿,取每個(gè)樣本點(diǎn)最近的個(gè)點(diǎn)作為近鄰茎匠。這種方法會(huì)造成構(gòu)造的鄰接矩陣不對(duì)稱,而譜聚類算法需要一個(gè)對(duì)稱的鄰接矩陣押袍。因此有以下兩種方法來(lái)構(gòu)造一個(gè)對(duì)稱的鄰接矩陣:
①只要一個(gè)點(diǎn)在另一個(gè)點(diǎn)的近鄰內(nèi)诵冒,則
,否則為
谊惭,相似度
可以使用徑向基函數(shù)來(lái)度量:
②只有兩個(gè)點(diǎn)互為近鄰汽馋,才會(huì)有
,否則為
:
上述方法是不用先建立圖而直接獲得鄰接矩陣午笛,在編程實(shí)現(xiàn)時(shí)能夠更加簡(jiǎn)便惭蟋,構(gòu)建的鄰接矩陣也就表明了哪些樣本點(diǎn)之間有邊連接。也可以采用先建立圖然后再在圖上有邊的數(shù)據(jù)點(diǎn)上保留權(quán)重獲得鄰接矩陣的方法药磺。
- 全連接法
這種方法會(huì)使所有的都大于
,可以選擇不用的核函數(shù)來(lái)度量相似度煤伟,比如多項(xiàng)式核函數(shù)癌佩、徑向基核函數(shù)和
核函數(shù)。最常用的是徑向基核函數(shù):
在實(shí)際應(yīng)用時(shí)選擇全連接法建立鄰接矩陣是最普遍的便锨,在選擇相似度度量時(shí)徑向基核函數(shù)是最普遍的围辙。
- 拉普拉斯矩陣
圖的拉普拉斯矩陣(Graph Laplacian)是一個(gè)對(duì)稱矩陣,用度矩陣減去鄰接矩陣得到的矩陣就被定義為拉普拉斯矩陣放案,
姚建。拉普拉斯矩陣有一些性質(zhì)如下:
①對(duì)稱性。
②由于其對(duì)稱性吱殉,則它的所有特征值都是實(shí)數(shù)掸冤。
③對(duì)于任意向量厘托,有:
這一性質(zhì)利用拉普拉斯矩陣的性質(zhì)很容易可以得到:
④拉普拉斯矩陣是半正定的,則其所有特征值非負(fù)稿湿,這個(gè)性質(zhì)由性質(zhì)③很容易得出铅匹。并且其最小的特征值為,這是因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=L" alt="L" mathimg="1">的每一行和為
饺藤,對(duì)于全
向量
包斑,有
。
- 無(wú)向圖切圖
對(duì)于無(wú)向圖的切圖涕俗,我們的目標(biāo)是將
切成相互沒有連接的
個(gè)子圖罗丰,每個(gè)子圖節(jié)點(diǎn)的集合為
,它們滿足
再姑,且
萌抵。
對(duì)于任意兩個(gè)子圖點(diǎn)的集合,定義
和
之間的切圖權(quán)重為:
對(duì)于個(gè)子圖的集合询刹,定義切圖
為:
上式中是
的補(bǔ)集谜嫉,意為除
子集以外的其他子集的并集。
每個(gè)子圖就相當(dāng)于聚類的一個(gè)類凹联,找到子圖內(nèi)點(diǎn)的權(quán)重之和最高沐兰,子圖間的點(diǎn)的權(quán)重之和最低的切圖就相當(dāng)于找到了最佳的聚類。實(shí)現(xiàn)這一點(diǎn)的一個(gè)很自然的想法是最小化蔽挠。然而這種方法存在問(wèn)題住闯,也就是最小化的
對(duì)應(yīng)的切圖不一定就是符合要求的最優(yōu)的切圖,如下圖:
在上面的例子中澳淑,我們選擇在最小的權(quán)重上進(jìn)行切圖比原,比如在和
之間進(jìn)行切圖,這樣可以使得
最小杠巡,但并不是最優(yōu)的切圖量窘。
接下介紹譜聚類使用的切圖方法。
三氢拥、譜聚類之切圖聚類
為了避免上述最小化存在的問(wèn)題蚌铜,需要對(duì)每個(gè)子圖的規(guī)模做出限制,接下來(lái)介紹兩種切圖方法嫩海,分別是
和
冬殃。
-
切圖
切圖為了避免上述最小切圖,對(duì)于每個(gè)切圖叁怪,不只考慮最小化
审葬,還考慮最大化每個(gè)子圖點(diǎn)的個(gè)數(shù),即:
為了最小化這個(gè)函數(shù),我們引入指示向量
涣觉,對(duì)于每一個(gè)向量
痴荐, 它是一個(gè)
維向量,另外定義
為:
那么對(duì)于旨枯,有:
由上式可知蹬昌,某一個(gè)子圖的也就是
,所有的
個(gè)子圖的
表達(dá)式也就是:
上式中為矩陣
的跡攀隔,
皂贩,需要注意這里的
滿足
,并且
的元素只能取
或者
昆汹。也就是說(shuō)我們需要優(yōu)化以下目標(biāo)函數(shù):
由于每個(gè)元素只能取兩個(gè)值明刷,因此上面的目標(biāo)函數(shù)是不可求導(dǎo)的。這里每個(gè)指示向量都是維的满粗,而且每個(gè)元素只有兩種取值辈末,所以就有
種取值方式,一共有
個(gè)指示向量映皆,因此共有
種
挤聘,因此想要找到滿足使目標(biāo)函數(shù)最小的
是一個(gè)NP難的問(wèn)題。
由于存在上述問(wèn)題捅彻,所以我們采用降維的思想來(lái)考慮解決這個(gè)優(yōu)化問(wèn)題组去。我們需要最小化,也就是需要優(yōu)化每一個(gè)
步淹,這里的
是單位正交基从隆,
是對(duì)稱矩陣,因此
的最大值是
的最大特征值缭裆,最小值是
的最小特征值键闺。之所以有這種結(jié)論可以參考主成分分析PCA的解法,在PCA中需要找到協(xié)方差矩陣(類比此處的拉普拉斯矩陣
澈驼,它們都是對(duì)稱的)的最大特征值辛燥,而在譜聚類中需要找到最小的
個(gè)非零特征值尔艇,然后得到這些特征值對(duì)應(yīng)的特征向量溺森,通過(guò)這個(gè)過(guò)程我們也就完成了數(shù)據(jù)的降維,最終
就是降維的結(jié)果菠隆,使用這個(gè)結(jié)果來(lái)近似解決這個(gè)NP難的問(wèn)題氏淑。
一般我們?nèi)匀恍枰獙?duì)按行做標(biāo)準(zhǔn)化,也就是:
由于在降維時(shí)損失了少量信息硕噩,導(dǎo)致得到的優(yōu)化后的指示向量對(duì)應(yīng)的
現(xiàn)在不能完全指示各樣本的歸屬假残,因此在得到降維結(jié)果
后還需要進(jìn)行一次傳統(tǒng)的聚類,比如K-Means。
-
切圖
切圖的方法與
切圖的方法很類似辉懒,只是把
的分母
換成
阳惹。使用
切圖時(shí),由于子圖樣本個(gè)數(shù)多不一定權(quán)重就大(只有權(quán)重大時(shí)眶俩,子圖內(nèi)樣本點(diǎn)的相似度才高)莹汤,因此切圖時(shí)基于權(quán)重也更符合目標(biāo),一般來(lái)說(shuō)
切圖優(yōu)于
切圖:
另外需要修改指示向量的表示形式颠印,的指示向量使用
來(lái)標(biāo)示樣本歸屬纲岭,而
使用子圖權(quán)重
來(lái)標(biāo)示指示向量
,定義如下:
類似的线罕,對(duì)于止潮,有:
同樣的優(yōu)化目標(biāo)也就是:
但是現(xiàn)在的約束條件不再滿足,而是
钞楼,證明如下:
對(duì)于對(duì)角線元素有:
由于和
不可能同時(shí)非零喇闸,因此對(duì)于非對(duì)角線元素有:
因此有。我們最終優(yōu)化的目標(biāo)函數(shù)為:
此時(shí)指示向量并不是標(biāo)準(zhǔn)正交基询件,所以在
中的降維思想不能直接使用燃乍。對(duì)于這個(gè)問(wèn)題,只需要將指示向量
做一個(gè)轉(zhuǎn)化即可宛琅,我們令
刻蟹,則:
也就是說(shuō)優(yōu)化的目標(biāo)變成了:
可以發(fā)現(xiàn)這個(gè)式子和基本一致,只是中間的
變成了
夯秃。如此我們就可以按照
的思想座咆,求出
的前
個(gè)最小非零特征值,然后求對(duì)應(yīng)的特征向量再進(jìn)行標(biāo)準(zhǔn)化得到最后的特征矩陣
仓洼,然后再使用K-Means等傳統(tǒng)方法進(jìn)行聚類即可介陶。
一般來(lái)說(shuō),相當(dāng)于對(duì)拉普拉普斯矩陣做了一次標(biāo)準(zhǔn)化色建,即
哺呜。
四、總結(jié)
- 算法流程
以切圖為例總結(jié)一下譜聚類算法的流程:
輸入:樣本集
箕戳,鄰接矩陣的生成方式某残,降維后的維度
,聚類方法陵吸,聚類的簇個(gè)數(shù)
玻墅。
輸出:簇劃分。
①根據(jù)輸入的鄰接矩陣生成方式構(gòu)建樣本的鄰接矩陣矩陣和度矩陣
壮虫;
②計(jì)算拉普拉斯矩陣澳厢;
③構(gòu)建標(biāo)準(zhǔn)化后的拉普拉斯矩陣环础;
④計(jì)算的最小的前
個(gè)非零特征值對(duì)應(yīng)的特征向量
;
⑤將各自對(duì)應(yīng)的特征向量組成的矩陣按行標(biāo)準(zhǔn)化剩拢,最終得到
維的特征矩陣
线得;
⑥對(duì)的每一行作為一個(gè)
維的樣本,共
個(gè)樣本徐伐,用輸入的聚類方法進(jìn)行聚類贯钩,聚類的簇的個(gè)數(shù)為
;
⑦得到簇劃分办素。
- 優(yōu)缺點(diǎn)
譜聚類的優(yōu)點(diǎn)有:
①譜聚類只需要數(shù)據(jù)之間的相似度矩陣角雷,因此對(duì)于處理稀疏數(shù)據(jù)的聚類很有效。這點(diǎn)傳統(tǒng)聚類算法比如K-Means很難做到摸屠。
②由于使用了降維谓罗,因此在處理高維數(shù)據(jù)聚類時(shí)的復(fù)雜度比傳統(tǒng)聚類算法好。
譜聚類的缺點(diǎn)有:
①如果最終聚類的維度非常高季二,則由于降維的幅度不夠檩咱,譜聚類的運(yùn)行速度和最后的聚類效果均不好。
②聚類效果依賴于相似矩陣胯舷,不同的相似矩陣得到的最終聚類效果可能很不同刻蚯。