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