資料探勘入門筆記——譜聚類（初來乍到）

寫在前面：健忘星人自學筆記，僅供參考

本章預計簡單介紹一下譜聚類的內容，由於譜聚類是基於圖論的，雖然使用起來簡單，但是理解清楚並不容易，需要一定的知識鋪墊，對萌新很不友好，一部分推導內容下文省略。

但是大家如果能認真啃下來問題不是很大，下面是一篇較為簡單易懂的閱讀材料，希望能有幫助

譜聚類詳細、入門級介紹 - 百度文庫

專業性較好的參考資料：

https：//

blog。csdn。net/qq_245196

77/article/details/82291867

一、譜聚類原理

譜聚類，是一種基於

圖論

的聚類方法，透過樣本資料的

拉普拉斯矩陣的特徵向量

進行聚類。

上面的定義看不懂沒關係，我們換一種說法。

譜聚類的思想，是將原問題轉化為“圖分割“的問題。

這裡面涉及兩個關鍵的步驟：

（1） 如何將原資料，轉化為“無向權重圖“

（2）如何對圖進行分割？

1.1 無向圖定義

上圖是一張“無向權重圖“示例

圖，是若干個

頂點

和

邊

相互連線組成的，分為無向圖和有向圖。

邊沒有方向的圖，稱為無向圖。

在上圖中，我們觀察到有6個頂點，也就是有6組資料樣本，用 V={

} 表示。兩個頂點之間由藍色的邊連線，用字母 E 表示邊集。

無向圖，表示為 G（V, E）

我們注意到，邊上顯示的數字

表示的是兩個頂點之間的邏輯關係

（相似程度），我們稱之為“權重”，用

來表示。（

>0 ）

在無向圖中，邊的權重

（ 因為邊沒有方向 ）

並且，

1.2 圖分割初探

在繪製出無向圖之後，我們想要做的，是將圖完全分成若干個子圖。

要求： 同子圖內的點相似度高；

不同子圖內的點相似度低；

上圖的劃分，看起來似乎是一個不錯的選擇。

這樣切圖的方法，我們截斷了兩條邊，

損失函式可以定義為被截斷邊的權重之和

如何選擇一個最佳的截斷方式？ 我們很自然會想到最小化

損失函式。

但是直接最小化，又會遇到一個問題，

錯誤的分割

例如，按照上圖的分割，切成了單點離散的圖，顯然這樣是最快且最能滿足那個最小化操作的。但這明顯不是想要的結果，合理的切分結果應該是組內的樣本點儘可能的多，所以後面我們要學習 RatioCut 和 Ncut 的分割方法。

透過上面的介紹，希望大家能對譜聚類的原理有一個大體上的瞭解，下面我們將對演算法詳細展開。

二、無向圖權重

在上面的例子裡，我們定義了頂點 i 和 頂點 j 連線起來的邊的權重為

將所有權重以矩陣的形式存放，我們稱之為

鄰接矩陣

以上圖為例，

注意：

（ 因為邊沒有方向 ），並且，

這裡我們直接給出了鄰接矩陣裡的數值。但是在譜聚類問題中，我們只有頂點向量，怎麼才能計算得到鄰接矩陣呢？

權重的基本思想是，距離較遠的兩個點之間的邊權重值較低，而距離較近的兩個點之間的邊權重值較高。

但這僅僅是定性，我們需要定量的權重值。

一般來說，

我們可以透過樣本點距離度量的相似矩陣 S 來獲得鄰接矩陣W。

構建鄰接矩陣W的方法有三類：

ϵ-鄰近法，Knn 和全連線法。

（1）ϵ-鄰近法

（很少用）

對於ϵ-鄰近法，它設定了一個距離閾值ϵ，然後用歐式距離

度量任意兩點

和

的距離。

然後根據

和 ϵ 的大小關係，來定義鄰接矩陣W ：

從上式可見，兩點間的權重要不就是ϵ ，要不就是0，矩陣中沒有攜帶關於資料集的太多資訊，所以該方法一般很少使用，在sklearn中也沒有使用該方法。

（2）Knn

基本思想是，利用 Knn 演算法遍歷所有的樣本點，取每個樣本最近的 k 個點作為近鄰，只有和樣本距離最近的 k 個點之間的

。

但是，由於每個樣本點的 k 個近鄰可能不是完全相同的，所以用此方法構造的相似度矩陣並不是對稱的。

為了解決這種問題，一般採取下面兩種方法之一：

方法一、只要一個點在另一個點的K近鄰中，就保留

方法二、必須兩個點互為K近鄰，才能保留

（很顯然第二種方式比第一種方式生成的相似度矩陣要稀疏。）

（3）全連線法

（最常用）

相比前兩種方法中，全連線法中所有的點之間的權重值都大於0。

可以選擇不同的核函式來定義邊權重，常用的有：多項式核函式，高斯核函式和Sigmoid核函式。

其中，最常用的是高斯核函式RBF

，在sklearn中預設的也是該方法，此時相似矩陣和鄰接矩陣相同：

高斯核函式

從公式中可以看出，任意兩個樣本點都有相似度，但是距離較遠的樣本點之間相似度較低，甚至可以忽略。

其中，引數

控制著樣本點的鄰域寬度，

越大表示樣本點與距離較遠的樣本點的相似度越大，反之亦然。

上面說了這麼多，還只解決了第一個問題，

如何將原資料轉化為無向權重圖 ?

下面我們要說，

如何對圖進行分割？

三、損失函式與拉普拉斯矩陣

之前，我們定義了損失函式——被截斷邊的權重之和

假設 G（ V， E） 被劃分為 G1，G2 兩個子圖，設G有 n 個頂點

定義 q = ［

］ 是一個 n 維向量，用來表示劃分方案

例如，

按照上圖劃分，q = ［

］

分子可變換為，

因此，

其中，

為拉普拉斯矩陣。

補充知識：

若一個矩陣為拉普拉斯矩陣，則其對任意一個向量

都有，

拉普拉斯矩陣的計算：

其中，D 為度矩陣，W 為鄰接矩陣

鄰接矩陣在上面已經介紹過，下面補充介紹一下

度矩陣

對於任意一個點 i，它的度 di 定義為

和它相連的所有邊的權重之和

，即

利用點的定義，度矩陣D是一個對角矩陣，只有主對角線有值。

舉例，

頂點1的度，d1 = 0。8 +0。6 +0。1 = 1。5

圖片引用自推薦閱讀材料1

圖片引用自，推薦閱讀材料1

四、圖分割

上面我們對損失函式進行了一系列變換，最終得到

圖形分割的一種方法——

最小切（Minimum Cut）

，就是直接最小化上式。

但是之前我們也說過，在許多情況下 Minimum Cut 只是簡單的將圖中的一個頂點與其餘的頂點分開，這並不是我們想要的結果。所以mincut在實際中並不常用。

合理的切分應該是組內的樣本點儘可能的多。

下面我們介紹另外兩個切圖方式 Ratio Cut 和 Normalized Cut，二者都在上式的基礎上進行了一定的改進。

在 RatioCut 切圖中，不僅要考慮使不同組之間的權重最小化，也考慮了使每個組中的樣本點儘量多。

在 N Cut 切圖中，除了考慮最小化損失函式之外，還考慮了子圖之間的權重大小。

由於子圖樣本的個數多並不一定權重就大，切圖時基於權重也更合目標，

因此一般來說Ncut 切圖優於 RatioCut 切圖。

證明及推導過程省略，詳細請參考推薦閱讀2

也可以參考，

轉載自：【聚類演算法】譜聚類（Spectral Clustering）

（有空的時候再詳細分解）

五、優缺點

優點：

1）譜聚類只需要資料之間的相似度矩陣，因此對於處理稀疏資料的聚類很有效。這點傳統聚類演算法比如K-Means很難做到

2）由於使用了降維，因此在處理高維資料聚類時的複雜度比傳統聚類演算法好。

缺點：

1）如果最終聚類的維度非常高，則由於降維的幅度不夠，譜聚類的執行速度和最後的聚類效果均不好。

2） 聚類效果依賴於相似矩陣，不同的相似矩陣得到的最終聚類效果可能很不同

今天的內容就到這裡，感謝觀看~~