k-means聚類和PCA有什麼關係？

在聚類算法（例如 k-means）之前應用 PCA（主成分分析）是一種常見的做法。相信它在實踐中改善了聚類結果（降噪）。

但是，我對 PCA 和 k-means 之間的關係進行比較和深入的研究很感興趣。例如，Chris Ding 和 Xiaofeng He，2004，K-means Clustering via Principal Component Analysis表明“主成分是 K-means 聚類的離散聚類成員指標的連續解”。但是，我很難理解這篇論文，而維基百科實際上聲稱它是錯誤的。

此外，這兩種方法的結果有些不同，因為 PCA 有助於在保持方差的同時減少“特徵”的數量，而聚類通過按期望/手段總結幾個點來減少“數據點”的數量（在 k 均值的情況下）。所以如果數據集包含在點與每個特徵，PCA 旨在壓縮特徵，而聚類旨在壓縮數據點。

我正在尋找對這兩種技術之間關係的外行解釋以及更多與這兩種技術相關的技術論文。

的確，K-means 聚類和 PCA 似乎有非常不同的目標，乍一看似乎並不相關。然而，正如 Ding & He 2004 年的論文K-means Clustering via Principal Component Analysis中所解釋的，它們之間存在著深厚的聯繫。

直覺是 PCA 試圖代表所有 $ n $ 數據向量作為少量特徵向量的線性組合，並且這樣做是為了最小化均方重構誤差。相比之下，K-means 試圖代表所有 $ n $ 通過少量聚類質心的數據向量，即將它們表示為少量聚類質心向量的線性組合，其中線性組合權重必須全為零，除了單個 $ 1 $ . 這樣做也是為了最小化均方重構誤差。

所以 K-means 可以看作是一種超稀疏的 PCA。

丁和的論文使這種聯繫更加精確。

---

不幸的是，丁和賀的論文包含一些草率的表述（充其量），很容易被誤解。例如，似乎 Ding & He 聲稱已經證明 K-means 聚類解決方案的聚類質心位於 $ (K-1) $ 維 PCA 子空間：

定理 3.3。簇質心子空間由第一個 $ K-1 $ 主要方向[…]。

為了 $ K=2 $ 這意味著 PC1 軸上的投影必然對一個集群為負，而對另一個集群為正，即 PC2 軸將完美地分離集群。

這要么是一個錯誤，要么是一些草率的寫作；無論如何，從字面上看，這種特殊的說法是錯誤的。

讓我們從 2D 中的一些玩具示例開始 $ K=2 $ . 我從兩個具有相同協方差矩陣但均值不同的正態分佈中生成了一些樣本。然後我運行了 K-means 和 PCA。下圖顯示了上面數據的散點圖，同樣的數據根據下面的 K-means 解決方案著色。我還將第一個主要方向顯示為一條黑線和由 K-means 找到的帶有黑色十字的類質心。PC2 軸用黑色虛線表示。重複 K-means $ 100 $ 次隨機種子，以確保收斂到全局最優。

可以清楚地看到，儘管類質心往往非常接近第一個 PC 方向，但它們並不完全落在它上面。此外，即使 PC2 軸在子圖 1 和 4 中完美地分離了簇，但在子圖 2 和 3 的錯誤一側仍有幾個點。

所以 K-means 和 PCA 之間的一致性很好，但並不准確。

那麼丁和他證明了什麼？為簡單起見，我將只考慮 $ K=2 $ 案件。讓分配給每個簇的點數為 $ n_1 $ 和 $ n_2 $ 和總點數 $ n=n_1+n_2 $ . 繼丁赫之後，我們來定義聚類指標向量 $ \mathbf q\in\mathbb R^n $ 如下： $ q_i = \sqrt{n_2/nn_1} $ 如果 $ i $ -th 個點屬於集群 1 並且 $ q_i = -\sqrt{n_1/nn_2} $ 如果它屬於簇 2。簇指示向量具有單位長度 $ |\mathbf q| = 1 $ 並且是“居中”的，即它的元素總和為零 $ \sum q_i = 0 $ .

Ding & He 證明了 K-means 損失函數 $ \sum_k \sum_i (\mathbf x_i^{(k)} - \boldsymbol \mu_k)^2 $ （即 K-means 算法最小化），其中 $ x_i^{(k)} $ 是個 $ i $ - 簇中的第一個元素 $ k $ , 可以等效地改寫為 $ -\mathbf q^\top \mathbf G \mathbf q $ ， 在哪裡 $ \mathbf G $ 是個 $ n\times n $ 所有點之間的標量積的 Gram 矩陣： $ \mathbf G = \mathbf X_c \mathbf X_c^\top $ ， 在哪裡 $ \mathbf X $ 是個 $ n\times 2 $ 數據矩陣和 $ \mathbf X_c $ 是居中的數據矩陣。

（注意：我使用的符號和術語與他們的論文略有不同，但我覺得更清楚）。

所以K-means解決方案 $ \mathbf q $ 是一個中心單位向量最大化 $ \mathbf q^\top \mathbf G \mathbf q $ . 很容易證明，第一個主成分（當歸一化為單位平方和時）是 Gram 矩陣的主要特徵向量，即它也是一個居中的單位向量 $ \mathbf p $ 最大化 $ \mathbf p^\top \mathbf G \mathbf p $ . 唯一的區別是 $ \mathbf q $ 還被限制為只有兩個不同的值，而 $ \mathbf p $ 沒有這個約束。

換句話說，K-means 和 PCA 最大化相同的目標函數，唯一的區別是 K-means 有額外的“分類”約束。

正如我們在上面的模擬中看到的那樣，大多數時候 K-means（受約束的）和 PCA（不受約束的）解決方案會非常接近，但人們不應該期望它們是相同的，這是理所當然的。服用 $ \mathbf p $ 並將其所有負面元素設置為 $ -\sqrt{n_1/nn_2} $ 及其所有積極因素 $ \sqrt{n_2/nn_1} $ 一般不會準確給出 $ \mathbf q $ .

Ding & He 似乎很理解這一點，因為他們將他們的定理表述如下：

定理 2.2。對於 K-means 聚類，其中 $ K= 2 $ ，聚類指標向量的連續解是[first]主成分

請注意“連續解決方案”一詞。在證明了這個定理之後，他們還評論說 PCA 可用於初始化 K-means 迭代，這完全有意義，因為我們期望 $ \mathbf q $ 靠近 $ \mathbf p $ . 但是仍然需要執行迭代，因為它們並不相同。

然而，Ding & He 隨後開發了一種更通用的治療方法 $ K>2 $ 並最終將定理 3.3 表述為

定理 3.3。簇質心子空間由第一個 $ K-1 $ 主要方向[…]。

第 3 節的數學我沒有去，但是我相信這個定理其實也指的是 K-means 的“連續解”，即它的陳述應該是“K-means 的連續解的簇質心空間是跨越[…]”。

然而，丁和赫並沒有做出這個重要的限定，而且在他們的摘要中寫道：

在這裡，我們證明了主成分是 K-means 聚類離散聚類成員指標的連續解。等效地，我們表明，由簇質心跨越的子空間是由截斷的數據協方差矩陣的譜擴展給出的 $ K-1 $ 條款。

第一句話是絕對正確的，但第二句話不是。**我不清楚這是（非常）草率的寫作還是真正的錯誤。**我非常有禮貌地給兩位作者發了電子郵件，要求澄清。（兩個月後更新：我從未收到他們的回复。）

---

Matlab仿真代碼

figure('Position', [100 100 1200 600])

n = 50;
Sigma = [2 1.8; 1.8 2];

for i=1:4
   means = [0 0; i*2 0];
   
   rng(42)
   X = [bsxfun(@plus, means(1,:), randn(n,2) * chol(Sigma)); ...
        bsxfun(@plus, means(2,:), randn(n,2) * chol(Sigma))];
   X = bsxfun(@minus, X, mean(X));
   [U,S,V] = svd(X,0);
   [ind, centroids] = kmeans(X,2, 'Replicates', 100);
   
   subplot(2,4,i)
   scatter(X(:,1), X(:,2), [], [0 0 0])

   subplot(2,4,i+4)
   hold on
   scatter(X(ind==1,1), X(ind==1,2), [], [1 0 0])
   scatter(X(ind==2,1), X(ind==2,2), [], [0 0 1])
   plot([-1 1]*10*V(1,1), [-1 1]*10*V(2,1), 'k', 'LineWidth', 2)
   plot(centroids(1,1), centroids(1,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
   plot(centroids(1,1), centroids(1,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)
   plot(centroids(2,1), centroids(2,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
   plot(centroids(2,1), centroids(2,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)
   
   plot([-1 1]*5*V(1,2), [-1 1]*5*V(2,2), 'k--')
end

for i=1:8
   subplot(2,4,i)
   axis([-8 8 -8 8])
   axis square
   set(gca,'xtick',[],'ytick',[])
end    

引用自：https://stats.stackexchange.com/questions/183236