K-平均演算法

"k"-均值演算法對應的聚類，以之作為聚類的標準。這個問題將歸結為一個把資料空間劃分為Voronoi cells的問題。這個問題在計算上是NP困難的，不過存在高效的啟發式演算法。一般情況下，都使用效率比較高的啟發式演算法，它們能夠快速收斂於一個區域性最優解。這些演算法通常類似於透過迭代最佳化方法處理高斯混合分佈的最大期望演算法。而且，它們都使用聚類中心來為資料建模；然而"k"-平均聚類傾向於在可比較的空間範圍內尋找聚類，期望-最大化技術卻允許聚類有不同的形狀。"k"-平均聚類與"k"-近鄰之間沒有任何關係。描述.已知觀測集formula_2，其中每個觀測都是一個formula_3-維實向量，"k"-平均聚類要把這formula_1個觀測劃分到"k"個集合中(k≤n),使得組內平方和最小。換句話說，它的目標是找到使得下式滿足的聚類formula_5，formula_6其中formula_7是formula_5中所有點的均值。歷史源流.雖然其思想能夠追溯到1957年的，術語“"k"-均值”於1967年才被詹姆斯·麥昆首次使用。標準演算法則是在1957年被史都華·勞埃德作為一種脈衝碼調製的技術所提出，但直到1982年才被貝爾實驗室公開出版。在1965年，E·W·弗吉演算法.標準演算法.最常用的演算法使用了迭代最佳化的技術。它被稱為"k"-平均演算法而廣為使用，有時也被稱為Lloyd演算法。已知初始的"k"個均值點formula_9,演算法的按照下面兩個步驟交替進行因為這一平方和就是平方後的歐氏距離，所以很直觀地把觀測分配到離它最近的均值點即可。。formula_10其中每個formula_11都只被分配到一個確定的聚類formula_12中，儘管在理論上它可能被分配到2個或者更多的聚類。formula_13因為算術平均是最小平方估計，所以這一步同樣減小了目標函式組內平方和的值。這一演算法將在對於觀測的分配不再變化時收斂。由於交替進行的兩個步驟都會減小目標函式WCSS的值，並且分配方案只有有限種，所以演算法一定會收斂於某一最優解。注意：使用這一演算法無法保證得到全域性最優解。這一演算法經常被描述為“把觀測按照距離分配到最近的聚類”。標準演算法的目標函式是組內平方和歐氏距離，可能使得演算法無法收斂。然而，使用不同的距離函式，也能得到"k"-均值聚類的其他變體，如球體"k"-均值演算法和"k"-中心點演算法。初始化方法.通常使用的初始化方法有Forgy和隨機劃分(Random Partition)方法。Forgy方法隨機地從資料集中選擇"k"個觀測作為初始的均值點；而隨機劃分方法則隨機地為每一觀測指定聚類，然後執行“更新(Update)”步驟,即計算隨機分配的各聚類的圖心，作為初始的均值點。Forgy方法易於使得初始均值點散開，隨機劃分方法則把均值點都放到靠近資料集中心的地方。參考Hamerly et al的文章，可知隨機劃分方法一般更適用於"k"-調和均值和模糊"k"-均值演算法。對於期望-最大化(EM)演算法和標準"k"-均值演算法，Forgy方法作為初始化方法的表現會更好一些。這是一個啟發式演算法，無法保證收斂到全域性最優解，並且聚類的結果會依賴於初始的聚類。又因為演算法的執行速度通常很快，所以一般都以不同的起始狀態執行多次來得到更好的結果。不過，在最差的情況下，"k"-均值演算法會收斂地特別慢：尤其是已經證明了存在這一的點集。好在在現實中，這樣的點集幾乎不會出現：因為"k"-均值演算法的平滑執行時間是多項式時間的注：把“分配”步驟視為“期望”步驟，把“更新”步驟視為“最大化步驟”，可以看到，這一演算法實際上是廣義期望-最大化演算法的一個變體。複雜度.在formula_3維空間中找到"k"-均值聚類問題的最優解的計算複雜度：相比之下，Lloyds演算法的執行時間通常為formula_19,"k"和formula_3定義如上，formula_21為直到收斂時的迭代次數。如果資料本身就有一定的聚類結構，那麼收斂所需的迭代數目通常是很少的，並且進行少數迭代之後，再進行迭代的話，對於結果的改善效果很小。鑑於上述原因，Lloyds演算法在實踐中通常被認為幾乎是線性複雜度的。下面有幾個關於這一演算法複雜度的近期研究：更多的討論.使得"k"-均值演算法效率很高的兩個關鍵特徵同時也被經常被視為它最大的缺陷："k"-均值演算法的一個重要的侷限性即在於它的聚類模型。這一模型的基本思想在於：得到相互分離的球狀聚類，在這些聚類中，均值點趨向收斂於聚類中心。一般會希望得到的聚類大小大致相當，這樣把每個觀測都分配到離它最近的聚類中心就是比較正確的分配方案。"k"-均值聚類的結果也能理解為由均值點生成的Voronoi cells。相關應用."k"-均值聚類即使是在巨大的資料集上也非常容易部署實施。正因為如此，它在很多領域都得到成功的應用，如市場劃分、機器視覺、 地質統計學、天文學和農業等。它經常作為其他演算法的預處理步驟，比如要找到一個初始設定。向量的量化."k"-均值起源於訊號處理領域，並且現在也能在這一領域找到應用。例如在計算機圖形學中，色彩量化的任務，就是要把一張影象的色彩範圍減少到一個固定的數目"k"上來。"k"-均值演算法就能很容易地被用來處理這一任務，並得到不錯的結果。其它得向量量化的例子有非隨機抽樣，在這裡，為了進一步的分析，使用"k"-均值演算法能很容易的從大規模資料集中選出"k"個合適的不同觀測。聚類分析.在聚類分析中，"k"-均值演算法被用來將輸入資料劃分到"k"個部分(聚類)中。然而，純粹的"k"-均值演算法並不是非常靈活，同樣地，在使用上有一定侷限。演算法的另一個限制就是它不能和任意的距離函式一起使用、不能處理非數值資料。而正是為了滿足這些使用條件，許多其他的演算法才被髮展起來。特徵學習.在步驟。基本方法是，首先使用輸入資料訓練出一個"k"-均值聚類表示，然後把任意的輸入資料投射到這一新的特徵空間。"k"-均值的這一應用能成功地與自然語言處理和計算機視覺中半監督學習的簡單線性分類器結合起來。在物件識別任務中，它能展現出與其他複雜特徵學習方法。與其他統計機器學習方法的關係."k"-均值聚類，以及它與EM演算法的聯絡，是高斯混合模型的一個特例。很容易能把"k"-均值問題一般化為高斯混合模型。另一個"k"-均值演算法的推廣則是"k"-SVD演算法，後者把資料點視為“編碼本向量”的稀疏線性組合。而"k"-均值對應於使用單編碼本向量的特殊情形。Mean Shift 聚類.基本的Mean Shift聚類要維護一個與輸入資料集規模大小相同的資料點集。初始時，這一集合就是輸入集的副本。然後對於每一個點，用一定距離範圍內的所有點的均值來迭代地替換它。與之對比，"k"-均值把這樣的迭代更新限制在。還有一種與"k"-均值類似的Mean shift演算法，即 似然Mean shift，對於迭代變化的集合，用一定距離內在輸入集中所有點的均值來更新集合裡的點。Mean Shift聚類與"k"-均值聚類相比，有一個優點就是不用指定聚類數目，因為Mean shift傾向於找到儘可能少的聚類數目。然而，Mean shift會比"k"-均值慢得多，並且同樣需要選擇一個“寬度”引數。和"k"-均值一樣，Mean shift演算法有許多變體。主成分分析.有一些研究表明，"k"-均值的放鬆形式解，可由主成分分析中的主成分給出，並且主成分分析由主方向張成的子空間與聚類圖心空間是等價的。不過，主成分分析是"k"-均值聚類的有效放鬆形式並不是一個新的結果(如，見)，並且還有的研究結果直接揭示了關於“聚類圖心子空間是由主成分方向張成的”這一論述的反例獨立成分分析(ICA).有研究表明，在稀疏假設以及輸入資料經過白化的預處理後，"k"-均值得到的解就是獨立成分分析的解。這一結果對於解釋"k"-均值在特徵學習方面的成功應用很有幫助。雙向過濾."k"-均值演算法隱含地假設輸入資料的順序不影響結果。雙向過濾與"k"-均值演算法和Mean shift演算法類似之處在於它同樣維護著一個迭代更新的資料集。然而，雙向過濾限制了均值的計算只包含了在輸入資料中順序相近的點，這使得雙向過濾能夠被應用在影象去噪等資料點的空間安排是非常重要的問題中。相似問題.目標函式是使得聚類平方誤差最小化的演算法還有"k"-中心點演算法，該方法保持聚類的中心在一個真實資料點上，亦即使用中心而非圖心作為均值點。