當我們在談論K-means：論文概述（2）

01-30

本系列意在長期連載分享，內容上可能也會有所增刪改減；

因此如果轉載，請務必保留源地址，非常感謝！

知乎專欄：當我們在談論數據挖掘

博客園：當我們在談論數據挖掘（暫時公式顯示有問題）

2001年

在「Estlick, Mike, et al. "Algorithmic transformations in the implementation of K- means clustering on reconfigurable hardware." 2001」中，作者將K-means演算法用在FPGA板子中。在傳統K-means中，用到了浮點數運算與乘法運算，而這兩種運算在FPGA中非常耗時。為了能在FPGA中高效使用K-means演算法，作者提出了修改的K-means演算法。

1. 先介紹一下明氏距離（Minkowski Distance），其定義如下

1-1. 如果令 $P=2$ ，即得到常見的歐氏距離（Euclidean Distance）；從概率的角度看，歐氏距離即認為數據服從標準多維正態分布，其概率密度函數中，歐氏距離描述的就是空間中的點偏離中心的概率，相同的歐氏距離即對應著概率密度函數的等高線

1-2. 如果令 $P=0$ ，即得到曼哈頓距離（Manhattan Distance），即每個維度的絕對值的和；當計算像素歐氏距離複雜度較高，有時候可以使用曼哈頓距離作為替代

1-3. 令 $Prightarrow infty$ ，即切比雪夫距離（Chebyshev Distance），即取不同緯度間的最大值；不過我也不知道什麼時候會用上它

1-4. 在此我們可以再總結一些常見的距離度量，如馬氏距離(MahalanobisDistance)；從概率角度看，其作用就是用多維正態分布擬合數據，描述的同樣是空間中的點偏離中心的概率，相同的馬氏距離即對應著概率密度函數的等高線

1-5. 餘弦相似度（Cosine Similarity），描述的是兩個向量的夾角大小

1-6. Jaccard相似係數（Jaccard Coefficient），描述的是兩個集合的相似性

2. 作者表示在FPGA中，歐氏距離的計算量太大，他希望用「曼哈頓距離」和「切比雪夫距離」替代。下圖表示，空間中兩個聚類中心，使用不同距離的分界面

3. 單獨使用「曼哈頓距離」和「切比雪夫距離」都無法很好地替代「歐氏距離」，於是作者將兩者融合，並說明效果的下降在允許範圍內，而計算量大大降低。（想法很有趣）

2002年

在"Kanungo, Tapas, et al. "An Efficient k-Means Clustering Algorithm: Analysis and Implementation." 2002"中，面對K-means運算量較大的問題，作者提出了「KD樹」加速K-means演算法的方法。

但是，其方法基本跟"Pelleg, et al. "Accelerating exact k -means algorithms with geometric reasoning." 1999."沒什麼區別。此處不再贅述。

2004年

在"Lee, Sangkeun, and M. H. Hayes. "Properties of the singular value decomposition for efficient data clustering." 2004"中，作者對SVD的性質進行了討論，並表示這些性能能加快K-means的過程。

1. 作者首先給出了對數據集A進行SVD的解釋

2. 然後給出了本文最主要的公式，即 $A$ 中每兩個向量的歐氏距離，可以用對應的「右奇異向量」的加權和表示。（註：這裡我們進一步分析，由於 $A$ 是一個 $m*n$ 的矩陣， $V$ 是一個 $n*n$ 的矩陣，若要SVD分解後能加速K-means，至少要求 $m>n$ ，即樣本維數大於樣本數量，然而這種情況比較少見。同時，SVD分解本身也是個非常耗時的操作。因此此方法更多的是提供一種思考方式。）

3. 本文還給出了一種設置聚類中心數量 $K$ 的方法。本質跟PCA類似，就是計算數據集 $A$ 的主要能量聚集在多少維度上。區別是PCA需要的是這幾個維度對應的向量，而這裡只需要維度的數量。

4. 文中還有更多利用SVD加速K-means聚類的細節，不再贅述

2005年

在"Huang, Joshua Zhexue, et al. "Automated Variable Weighting in k-Means Type Clustering." 2005"中，作者針對K-means演算法中，每一維特徵在聚類結果中權重相同的情況，提出了修改的K-mwans。

1. 作者首先提出，在數據挖掘過程中，往往數據的維數都是成百上千，而其中對分析有意義的維數只是部分。以往根據經驗給每一維數據賦權重，作者提出一種演算法來自動求出權重。
2. 先給出原始K-means的損失函數，即最小均方誤差

3. 然後作者給出修改的K-means的損失函數。本質就是在損失函數里增加了權重，然後繼續通過EM演算法求解。在最小均方誤差的約束下，類內距離小的那一維特徵會被賦予較大的權重，類內距離較大的則會被賦予較小的權重。即作者所說的，自動求解權重

4. 關於詳細的求解步驟，與收斂性的證明，可以參考原論文

2006年

在"Kuncheva, L. I., and D. P. Vetrov. "Evaluation of Stability of k-Means Cluster Ensembles with Respect to Random Initialization." 2006"中，作者研究了通過Ensembling來提升K-means等演算法的穩定性

1. 作者先明確了研究的問題，即

Ensembling是否能提升聚類的穩定性？
是否聚類的穩定性能與準確性正相關？
是否能利用聚類穩定性指標來描述聚類的有效性？

2. 作者給出了Ensembling的方法，即把數據分成 $L$ 組，再分別對 $L$ 組的數據進行聚類，並將結果融合

3. 對於上述問題，作者都沒有給出理論證明，都是實驗上的說明：

Ensembling是否能提升聚類的穩定性？大部分情況下，Ensembling能提升聚類的穩定性。同時需要說明的是，Ensembling更穩定的情況基本發生在聚類中心較大的時候，即Ensembling會傾向於選擇更多的聚類中心
是否聚類的穩定性能與準確性正相關？ 跟設想的結果差不多，聚類的穩定性跟準確性並沒有明確的正相關。不同的數據集上，有著完全不同的相關性。
是否能利用聚類穩定性指標來描述聚類的有效性？在這部分，作者主要闡述了利用聚類穩定性指標來選擇聚類中心數量的想法。即，作者通過給出一個穩定性指標，表示在穩定性較大的時候的聚類中心數量會很接近真實的類別數量。

2007年

在"Arthur, David, and S. Vassilvitskii. "k-means++: the advantages of careful seeding." 2007"中，作者提出了K-means++演算法，也是較為常用的K-means修改演算法之一。這個演算法主要提出了一種選擇初始化聚類中心的方法，並從理論上證明了這個方案會使收斂更快，且效果更好

1. 這個初始化聚類中心的方法其實很簡單：即以概率的形式逐個選擇聚類中心，並在選擇聚類中心時，給距離較遠的點更高的權重，即更容易被選擇為聚類中心

2. 這個想法其實並不是非常新奇，這種逐個選擇聚類中心的思想，在1997年就有作者提出過（參考「當我們在談論kmeans：論文概述（1），1997」）。但是作者在這個初始化聚類中心方法的基礎上，接下來又證明了通過這種方法，平均均方誤差大大降低，且收斂速度更快。證明過程好複雜，大家可以自己去研讀。

2010年

在"Chiang, Ming Tso, and B. Mirkin. "Intelligent Choice of the Number of Clusters in K-Means Clustering: An Experimental Study with Different Cluster Spreads." 2010"中，針對K-means演算法中聚類中心數量難以確定的問題，作者通過實驗的方式，比較了多種估計K-means聚類中心數量的方法。並通過實驗對比了這些方法在估計類別數量、中心、標記時的準確度。

1. 作者首先介紹了Mirkin提出的Intelligent K-means演算法，本質是通過異常檢測的思想，一步步確定每個類別。具體描述如下

2. 為了選擇對照演算法，作者總結了其他估計聚類數量 $K$ 的演算法。針對不同類型的方法，作者也給出了例子。有興趣的同學可以參考原文。

基於變化的演算法：即定義一個函數，隨著 $K$ 的改變，認為在正確的 $K$ 時會產生極值。如Gap Statistic（Estimating the number of clusters in a data set via the gap statistic, Tibshirani, Walther, and Hastie 2001），Jump Statistic （finding the number of clusters in a data set, Sugar and James 2003）
基於結構的演算法：即比較類內距離、類間距離以確定 $K$ 。這個也是最常用的辦法，如使用平均輪廓係數，越趨近1聚類效果越好；如計算類內距離/類間距離，值越小越好；等。
基於一致性矩陣的演算法：即認為在正確的 $K$ 時，不同次聚類的結果會更加相似，以此確定 $K$ 。
基於層次聚類：即基於合併或分裂的思想，在一定情況下停止獲得 $K$ 。
基於採樣的演算法：即對樣本採樣，分別做聚類；根據這些結果的相似性確定 $K$ 。如，將樣本分為訓練與測試樣本；對訓練樣本訓練分類器，用於預測測試樣本類別，並與聚類的類別比較。

3. 最後通過對比實驗，作者給出結論認為Intelligent K-means能較為有效的估計真實聚類中心、以及樣本所屬類別。同時，Intelligent K-means對類別數量的估計普遍較大。不過由於實驗是在高斯分布的模擬實驗下進行的，結論並非我所關注，不再贅述。

本系列其他文章：