為什麼特徵向量揭示譜聚類中的組
根據聚類分析手冊，光譜聚類是用以下算法完成的：
輸入相似矩陣 S , 簇數 K
- 形成轉移矩陣 P 和 Pij=Sij/di 為了 i,j=1:n 在哪裡 di=∑nj=1Sij
- 計算最大的 K 特徵值 λ1≥⋯≥λk 和特徵向量 v1≥⋯≥vk 的P。
- 將數據嵌入第 K 個主子空間，其中 xi=[v2iv3i…vki] 為了 i=1…n
- 運行 K-means 算法 x1:n .
接下來是具有以下特徵值圖形的人工示例，並形成了點的低維表示：
但是，我不知道特徵向量的什麼屬性使它們揭示了組，以便可以使用簡單的 K-means 對它們進行聚類。我也沒有得到特徵向量圖形——儘管第三個特徵向量似乎有三個級別的觀察值，每個都低於前一個，第二個似乎只有兩個——最後回到觀察值的高值的樣本。它與發現的集群有什麼關係？
我想我缺少一些線性代數知識。所以我的問題是它為什麼有效？為什麼我們取最大的 k 個特徵值和它們各自的特徵向量？
這是一個偉大而微妙的問題。
在我們轉向你的算法之前，讓我們首先觀察相似度矩陣 S . 它是對稱的，如果您的數據形成凸簇（見下文），並且通過適當的點枚舉，它接近於塊對角矩陣。這是因為集群中的點往往具有較高的相似性，而來自不同集群的點的相似度較低。
下面是流行的“鳶尾花”數據集的示例：
（第二個和第三個集群之間有明顯的重疊，因此這兩個塊有些連接）。
您可以將此矩陣分解為其特徵向量和相關的特徵值。這被稱為“頻譜分解”，因為它在概念上類似於將光或聲音分解為基本頻率及其相關振幅。
特徵向量的定義為：
A⋅e=e⋅λ
和 A 作為一個矩陣， e 一個特徵向量和 λ 其對應的特徵值。我們可以將所有特徵向量收集為矩陣中的列 E ，以及對角矩陣中的特徵值 Λ ，所以如下：
A⋅E=E⋅Λ
現在，在選擇特徵向量時有一定的自由度。它們的方向由矩陣決定，但大小是任意的：如果 A⋅e=e⋅λ ， 和 f=7⋅e （或任何縮放 e 你喜歡），然後 A⋅f=f⋅λ ， 也。因此，通常縮放特徵向量，使其長度為 1 ( ‖e‖2=1 ）。此外，對於對稱矩陣，特徵向量是正交的：
$$ e^i \cdot e^j = \Bigg{ 1 for i=j 0 otherwise
$$或者，以矩陣形式：
E⋅ET=I
將其代入上述特徵向量的矩陣定義會導致：
A=E⋅Λ⋅ET
你也可以用擴展的形式寫下來，如下：
A=∑iλi⋅ei⋅(ei)T
（如果它對你有幫助，你可以想到這裡的 dyads ei⋅(ei)T 作為“基本頻率”和 λi 作為頻譜的“幅度”）。
讓我們回到我們的 Iris 相似矩陣並查看它的光譜。前三個特徵向量如下所示：
您會看到，在第一個特徵向量中，對應於第一個簇的前 50 個分量都是非零（負），而其餘分量幾乎完全為零。在第二個特徵向量中，前 50 個分量為零，其餘 100 個非零。這 100 個對應於“超集群”，包含兩個重疊的集群 2 和 3。第三個特徵向量具有正分量和負分量。它根據其組成部分的符號將“超集群”分成兩個集群。以每個特徵向量表示特徵空間中的一個軸，並將每個分量作為一個點，我們可以將它們繪製成 3D：
要了解這與相似度矩陣有何關係，我們可以看一下上述總和的各個項。 λ1⋅e1⋅(e1)T 看起來像這樣：
即它幾乎完全對應於矩陣中的第一個“塊”（以及數據集中的第一個簇）。第二個和第三個集群重疊，所以第二項， λ2⋅e2⋅(e2)T , 對應於包含兩個的“超集群”：
第三個特徵向量將其分成兩個子簇（注意負值！）：
你明白了。現在，您可能會問為什麼您的算法需要轉移矩陣 P ，而不是直接處理相似度矩陣。相似矩陣僅對凸簇顯示這些漂亮的塊。對於非凸簇，最好將它們定義為與其他點分開的點集。
您描述的算法（算法 7.2，書中第 129 頁？）基於聚類的隨機遊走解釋（也有類似但略有不同的圖形切割解釋）。如果您將點（數據、觀察）解釋為圖中的節點，則每個條目 pij 在轉移矩陣中 P 給你概率，如果你從節點開始 i ，隨機遊走的下一步將帶你到節點 j . 矩陣 P 只是一個縮放的相似性矩陣，因此它的元素，按行（你也可以按列）是概率，即它們總和為 1。如果點形成簇，那麼隨機遍歷它們將在簇內花費大量時間，並且只是偶爾從一個簇跳到另一個簇。服用 P 的力量 m 向您展示您在起飛後每個點降落的可能性有多大 m 隨機步驟。適當高 m 將再次導致類似塊矩陣的矩陣。如果 m 太小，塊還不會形成，如果太大， Pm 已經接近趨於穩定狀態。但是塊結構仍然保留在特徵向量中 P .
