K-平均演算法

k-均值演算法（英文：k-means clustering）源於信號處理中的一種向量量化方法，現在則更多地作為一種聚類分析方法流行於數據挖掘領域。k-平均聚類的目的是：把$n$個點（可以是樣本的一次觀察或一個實例）劃分到k個聚類中，使得每個點都屬於離他最近的均值（此即聚類中心）對應的聚類，以之作為聚類的標準。這個問題將歸結為一個把數據空間劃分為Voronoi cells的問題。

這個問題在計算上是NP困難的，不過存在高效的啟發式算法。一般情況下，都使用效率比較高的啟發式算法，它們能夠快速收斂於一個局部最優解。這些演算法通常類似於通過迭代優化方法處理高斯混合分布的最大期望算法（EM演算法）。而且，它們都使用聚類中心來為數據建模；然而k-平均聚類傾向於在可比較的空間範圍內尋找聚類，期望-最大化技術卻允許聚類有不同的形狀。

k-平均聚類與k-近鄰之間沒有任何關係（後者是另一流行的機器學習技術）。

## 描述

已知觀測集$(x_1,x_2,...,x_n)$，其中每個觀測都是一個$d$-維實向量，k-平均聚類要把這$n$個觀測劃分到k個集合中(k≤n),使得組內平方和（WCSS within-cluster sum of squares）最小。換句話說，它的目標是找到使得下式滿足的聚類$S_i$。

$\underset{\mathbf{S}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|^2$ 其中$\mu _i$是$S_i$中所有點的均值。

## 歷史源流

雖然其思想能夠追溯到1957年的胡戈·施泰因豪斯

術語「k-均值」於1967年才被詹姆斯·麥昆（James MacQueen）

首次使用。標準演算法則是在1957年被史都華·勞埃德（Stuart Lloyd）作為一種脈衝碼調製的技術所提出，但直到1982年才被貝爾實驗室公開出版。在1965年，E·W·弗吉（E. W. Forgy）發表了本質上相同的方法，所以這一演算法有時被稱為勞埃德-弗吉方法。更高效的版本則被J·A·哈蒂根（J. A. Hartigan）和M·A·王（M. A. Wong）提出（1975/1979）。

## 演算法

### 標準演算法

最常用的演算法使用了迭代優化的技術。它被稱為k-平均演算法而廣為使用，有時也被稱為Lloyd演算法（尤其在電腦科學領域）。已知初始的k個均值點$m_1^{(t)},...,m_k^{(t)}$,演算法的按照下面兩個步驟交替進行

- 分配(Assignment)：將每個觀測分配到聚類中，使得組內平方和（WCSS）達到最小。

因為這一平方和就是平方後的歐氏距離，所以很直觀地把觀測分配到離它最近的均值點即可。（數學上，這意味依照由這些均值點生成的Voronoi圖來劃分上述觀測）。

$S_i^{(t)}=\left \{ x_p:\left \| x_p-m_i^{(t)} \right \|^2\leq \left \| x_p -m_j^{(t)} \right \|^2\forall j,1\leq j\leq k \right \}$ 其中每個$x_p$都只被分配到一個確定的聚類$S^{t}$中，儘管在理論上它可能被分配到2個或者更多的聚類。

- 更新(Update)：對於上一步得到的每一個聚類，以聚類中觀測值的圖心，作為新的均值點。

$m_i^{(t+1)}=\frac{1}{\left | S_i^{(t)} \right |}\sum_{x_j\in S_i^{(t)}}x_j$ 因為算術平均是最小平方估計，所以這一步同樣減小了目標函數組內平方和（WCSS）的值。

這一演算法將在對於觀測的分配不再變化時收斂。由於交替進行的兩個步驟都會減小目標函數WCSS的值，並且分配方案只有有限種，所以演算法一定會收斂於某一（局部）最優解。注意：使用這一演算法無法保證得到全局最優解。

這一算法經常被描述為「把觀測按照距離分配到最近的聚類」。標準演算法的目標函數是組內平方和（WCSS），而且按照「最小平方和」來分配觀測，確實是等價於按照最小歐氏距離來分配觀測的。如果使用不同的距離函數來代替（平方）歐氏距離，可能使得演算法無法收斂。然而，使用不同的距離函數，也能得到k-均值聚類的其他變體，如球體k-均值演算法和k-中心點演算法。

### 初始化方法

通常使用的初始化方法有Forgy和隨機劃分(Random Partition)方法。Forgy方法隨機地從數據集中選擇k個觀測作為初始的均值點；而隨機劃分方法則隨機地為每一觀測指定聚類，然後運行「更新(Update)」步驟,即計算隨機分配的各聚類的圖心，作為初始的均值點。Forgy方法易於使得初始均值點散開，隨機劃分方法則把均值點都放到靠近數據集中心的地方。參考Hamerly et al的文章

可知隨機劃分方法一般更適用於k-調和均值和模糊k-均值演算法。對於期望-最大化(EM)演算法和標準k-均值演算法，Forgy方法作為初始化方法的表現會更好一些。

這是一個啟發式算法，無法保證收斂到全局最優解，並且聚類的結果會依賴於初始的聚類。又因為演算法的運行速度通常很快，所以一般都以不同的起始狀態運行多次來得到更好的結果。不過，在最差的情況下，k-均值算法會收斂地特別慢：尤其是已經證明了存在這一的點集（甚至在2維空間中），使得k-均值演算法收斂的時間達到指數級（$2^{\Omega(n)}$）。好在在現實中，這樣的點集幾乎不會出現：因為k-均值演算法的平滑運行時間是多項式時間的。

註：把「分配」步驟視為「期望」步驟，把「更新」步驟視為「最大化步驟」，可以看到，這一演算法實際上是廣義期望-最大化演算法（GEM）的一個變體。

## 複雜度

在$d$維空間中找到k-均值聚類問題的最優解的計算複雜度：

- NP-hard：一般歐式空間中，即使目標聚類數僅為2
- NP困難：平面中，不對聚類數目k作限制
- 如果k和$d$都是固定的，時間複雜度為$O(n^{dk+1}logn)$,其中$n$為待聚類的觀測點數目

相比之下，Lloyds演算法的運行時間通常為$O(nkdi)$,k和$d$定義如上，$i$為直到收斂時的迭代次數。如果數據本身就有一定的聚類結構，那麼收斂所需的迭代數目通常是很少的，並且進行少數迭代之後，再進行迭代的話，對於結果的改善效果很小。鑑於上述原因，Lloyds演算法在實踐中通常被認為幾乎是線性複雜度的。

下面有幾個關於這一演算法複雜度的近期研究：

- Lloyd's k-均值演算法具有多項式平滑運行時間。對於落在空間$[0,1]^d$任意的$n$點集合，如果每一個點都獨立地受一個均值為$0$，標準差為$\sigma$的正態分布所影響，那麼k-均值演算法的期望運行時間上界為$O(n^{34}k^{34}d^{8}log^4(n)/\sigma^6)$，即對於$n,k,i,d$和$1/\sigma$都是多項式時間的。
- 在更簡單的情況下，有更好的上界。例如，在整數網格$\left \{ 1,...,M \right \}^d$中，k-均值演算法運行時間的上界為$O(dn^4M^2)$。

## 演算法的知名變體

### k-means++

K-means++是一種改進的k-means聚類演算法，通過優化初始聚類中心的選擇提升傳統K-means的性能。其核心思想是讓初始中心儘可能分散：首先隨機選取一個點作為首個中心，後續每個中心的選擇機率與其到已有中心的最短距離平方成正比。這種策略降低了隨機初始化導致的局部最優風險，使聚類結果更穩定。相比傳統K-means的隨機初始化，K-means++在保持演算法高效性的同時，顯著提升了聚類質量。

### BisectingKMeans

BisectingKMeans（二分K均值）是一種改進的k-means聚類演算法，結合了K-means的高效性與層次聚類的結構化特性。其核心思想是自上而下逐步分裂數據集：初始將所有數據視為一個簇，通過K-means迭代將其分為兩個子簇，並選擇分裂後誤差平方和（SSE）最小的簇繼續分裂，直到達到預設簇數。相比傳統K-means，它減少了隨機初始質心的影響，聚類結果更穩定。該演算法適用於大規模數據，能生成類似樹狀圖的層次結構，常用於文本聚類等領域。

### Fuzzy C-Means

Fuzzy C-Means（FCM）是一種基於模糊理論的軟聚類演算法，通過計算樣本對各簇的隸屬度矩陣實現數據劃分，允許數據點以不同機率屬於多個簇，從而提升分類靈活性。其核心思想是通過優化目標函數，使同一簇內數據相似度最大化，不同簇間相似度最小化。相較於K-means的硬劃分，FCM更適用於邊界模糊或重疊的數據場景，如圖像分割、雜草識別等領域。然而，FCM對噪聲敏感，後續衍生出改進演算法（如增量式FCM）以增強魯棒性。該演算法在數據挖掘和模式識別中廣泛應用，尤其適合處理不確定性數據。

## 更多的討論

使得k-均值演算法效率很高的兩個關鍵特徵同時也被經常被視為它最大的缺陷：

- 聚類數目k是一個輸入參數。選擇不恰當的k值可能會導致糟糕的聚類結果。這也是為什麼要進行特徵檢查來決定數據集的聚類數目了。
- 收斂到局部最優解，可能導致「反直觀」的錯誤結果。

k-均值演算法的一個重要的局限性即在於它的聚類模型。這一模型的基本思想在於：得到相互分離的球狀聚類，在這些聚類中，均值點趨向收斂於聚類中心。

一般會希望得到的聚類大小大致相當，這樣把每個觀測都分配到離它最近的聚類中心（即均值點）就是比較正確的分配方案。

k-均值聚類的結果也能理解為由均值點生成的Voronoi cells。

## 相關應用

k-均值聚類（尤其是使用如Lloyd's演算法的啟發式方法的聚類）即使是在巨大的數據集上也非常容易部署實施。正因為如此，它在很多領域都得到成功的應用，如市場劃分、機器視覺、地質統計學、天文學和農業等。它經常作為其他演算法的預處理步驟，比如要找到一個初始設置。

### 向量的量化

k-均值起源於信號處理領域，並且現在也能在這一領域找到應用。例如在電腦圖形學中，色彩量化的任務，就是要把一張圖像的色彩範圍減少到一個固定的數目k上來。k-均值演算法就能很容易地被用來處理這一任務，並得到不錯的結果。其它得向量量化的例子有非隨機抽樣，在這裡，為了進一步的分析，使用k-均值演算法能很容易的從大規模數據集中選出k個合適的不同觀測。

### 聚類分析

在聚類分析中，k-均值演算法被用來將輸入數據劃分到k個部分(聚類)中。

然而，純粹的k-均值演算法並不是非常靈活，同樣地，在使用上有一定局限（不過上面說到的向量量化，確實是一個理想的應用場景）。特別是，當沒有額外的限制條件時，參數k是很難選擇的（正如上面討論過的一樣）。演算法的另一個限制就是它不能和任意的距離函數一起使用、不能處理非數值數據。而正是為了滿足這些使用條件，許多其他的演算法才被發展起來。

### 特徵學習

在（半）監督學習或無監督學習中，k-均值聚類被用來進行特徵學習（或字典學習）步驟。基本方法是，首先使用輸入數據訓練出一個k-均值聚類表示，然後把任意的輸入數據投射到這一新的特徵空間。

k-均值的這一應用能成功地與自然語言處理和電腦視覺中半監督學習的簡單線性分類器結合起來。在對象識別任務中，它能展現出與其他複雜特徵學習方法（如自動編碼器、受限Boltzmann機等）相當的效果。然而，相比複雜方法，它需要更多的數據來達到相同的效果，因為每個數據點都只貢獻了一個特徵（而不是多重特徵）。

## 與其他統計機器學習方法的關係

k-均值聚類，以及它與EM演算法的聯繫，是高斯混合模型的一個特例。很容易能把k-均值問題一般化為高斯混合模型。另一個k-均值演算法的推廣則是k-SVD演算法，後者把數據點視為「編碼本向量」的稀疏線性組合。而k-均值對應於使用單編碼本向量的特殊情形（其權重為1）。

### Mean Shift 聚類

基本的Mean Shift聚類要維護一個與輸入數據集規模大小相同的數據點集。初始時，這一集合就是輸入集的副本。然後對於每一個點，用一定距離範圍內的所有點的均值來迭代地替換它。與之對比，k-均值把這樣的迭代更新限制在（通常比輸入數據集小得多的）K個點上，而更新這些點時，則利用了輸入集中與之相近的所有點的均值（亦即，在每個點的Voronoi劃分內）。還有一種與k-均值類似的Mean shift演算法，即 似然Mean shift，對於迭代變化的集合，用一定距離內在輸入集中所有點的均值來更新集合里的點。Mean Shift聚類與k-均值聚類相比，有一個優點就是不用指定聚類數目，因為Mean shift傾向於找到儘可能少的聚類數目。然而，Mean shift會比k-均值慢得多，並且同樣需要選擇一個「寬度」參數。和k-均值一樣，Mean shift演算法有許多變體。

### 主成分分析（PCA）

有一些研究表明，k-均值的放鬆形式解（由聚類指示向量表示），可由主成分分析中的主成分給出，並且主成分分析由主方向張成的子空間與聚類圖心空間是等價的。不過，主成分分析是k-均值聚類的有效放鬆形式並不是一個新的結果(如，見)，並且還有的研究結果直接揭示了關於「聚類圖心子空間是由主成分方向張成的」這一論述的反例。

### 獨立成分分析(ICA)

有研究表明，在稀疏假設以及輸入數據經過白化的預處理後，k-均值得到的解就是獨立成分分析的解。這一結果對於解釋k-均值在特徵學習方面的成功應用很有幫助。

### 雙向過濾

k-均值演算法隱含地假設輸入數據的順序不影響結果。雙向過濾與k-均值演算法和Mean shift演算法類似之處在於它同樣維護著一個迭代更新的數據集（亦是被均值更新）。然而，雙向過濾限制了均值的計算只包含了在輸入數據中順序相近的點，這使得雙向過濾能夠被應用在圖像去噪等數據點的空間安排是非常重要的問題中。

## 相似問題

目標函數是使得聚類平方誤差最小化的演算法還有k-中心點演算法，該方法保持聚類的中心在一個真實數據點上，亦即使用中心而非圖心作為均值點。

## 外部連結

- Numerical Example of k-means clustering
- Application example which uses k-means clustering to reduce the number of colors in images
- Interactive demo of the k-means-algorithm(Applet)
- An example of multithreaded application which uses k-means in Java
- k-means application in php
- k-means application in image retrieval
- Another animation of the k-means-algorithm