K-Means算法

**_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^{4}M^{2})$ 。

## 演算法的變體

## 更多的討論

使得 _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 （頁面存檔備份，存於網際網路檔案館）