完整文檔和代碼

https://gitee.com/youryouth/mc/tree/master/spectral_clustering

一、概述

對(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，這類以譜聚類為代表。

關(guān)于凸集和非凸，如下圖左非凸，圖右凸

二、基礎(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è)子集，我們定義等于子集A中點(diǎn)的個(gè)數(shù)

構(gòu)建鄰接矩陣

-近鄰法

首先需要設(shè)置一個(gè)閾值，比較任意兩點(diǎn)和之間的距離與的大小，定義鄰接矩陣如下：

這種方法表示如果兩個(gè)樣本點(diǎn)之間的歐氏距離的平方小于閾值，則它們之間是有邊的。

因?yàn)椴恢С謒arkdown語(yǔ)法，關(guān)于其他構(gòu)建鄰接矩陣方法可以參考鏈接，下面只貼出代碼的運(yùn)行結(jié)果。

運(yùn)行結(jié)果