K-平均演算法

_ k _-平均演算法（英文：_ k _-means clustering）源於訊號處理中的一種向量化方法，這馬是閣較濟的地作為一種聚類分析方法時行佇資料探勘領域。_ k _-聚平均類的目的是：共 $ n $ 個點（會當本的一改觀察抑是講一个實例）畫分著 _ k _ 聚類當中，予每一个點攏屬於離伊上近的均值（這馬聚類中心）對應的聚類，掠準講聚類的標準。這个問題共歸結做一个共資料空間劃做一个 Voronoi cells 的問題。

這个問題佇計算上是 NP 困難的，毋過存在高效的啟發式演算法。一般情形下，攏使用效率較懸的啟發式演算法，𪜶會當快速收縮佇一个局部最佳解。遮的演算法通常類似迵過迵天代最佳化方法處理高斯透濫分布的上大向望演算法（EM 演算法）。而且，𪜶攏用聚類中心來做資料建模；毋過 _ k _-平均聚類行向佇咧會當比較的空間範圍來走揣聚類，期望-上大化技術煞允准聚類有無仝款的形狀。

_ k _-𪜶平均聚類佮 _ k _-近鄰之間無任何的關係（後者是另外一時行的機器學習技術）。

是咧講

就知影觀測集 $ ( x _ { 一 } , x _ { 二 } , . . . , x _ { n } ) $，其中每一个觀測攏是一个 $ d $-維實向量，_ k _-平均聚類欲共這 $ n $ 個觀測劃分到 _ k _ 個集合中 ( k≤n ) , 予組內平方和（WCSS within-cluster sum of squares）上細漢。嘛會使講，伊的目標是揣著予下式滿足的聚類 $ S _ { i } $，

$ { \ underset { \ mathbf { S } } { \ operatorname { arg \ , min } } } \ sum _ { i=一 } ^ { k } \ sum _ { \ mathbf { x } \ in S _ { i } } \ left \ | \ mathbf { x }-{ \ boldsymbol { \ mu } } _ { i } \ right \ | ^ { 二 } $ 其中 $ \ mu _ { i } $ 是 $ S _ { i } $ 中所有一點仔的均值。

歷史源流

雖然其實思想會當追溯到一九五七年的牛牢內・施泰因豪斯，術語「_ k _-平均」佇一九六七年才去予詹姆斯・麥昆（James MacQueen）

頭一遍使用。標準演算法則是佇一九五七年被史都華・勞埃德（Stuart Lloyd）做為一種脈衝碼調製的技術所提出，毋過一直到一九八二年才被貝爾實驗室公開出版

。佇一九六五年，E ・ W ・ oo-lú-mih（E . W . Forgy）有發表著本質上仝款的方法，所以這演算法有時予人號做勞埃德-磯吉方法。閣較高效的版本予人 J ・ A ・哈蒂根（J . A . Hartigan）和 M ・ A ・王（M . A . Wong）提出（一千九百七十九分之一千九百七十五）。

演算法

標準演算法

上捷用的演算法使用迵天代最佳化的技術。伊予人叫做 _ k _-平均演算法而廣為使用，有時也予人號做 Lloyd 演算法（尤其佇電腦科學領域）。已經知初初的 _ k _ 一个均值點 $ m _ { 一 } ^ { ( t ) } , . . . , m _ { k } ^ { ( t ) } $ , 演算法的照下跤兩步驟交替進行

：

分配 ( Assignment )：共每一个觀測分配著聚類內底，予組內平方和（WCSS）達到上細漢。

因為這一平方佮就是平方後的歐氏距離，所以誠直觀地共觀測分配到離伊上近的均值點即可

。（數學上，這个意味依照由遮的均值點生的 Voronoi 圖來劃分上述觀測）。

$ S _ { i } ^ { ( t ) }=\ left \ { x _ { p } : \ left \ | x _ { p }-m _ { i } ^ { ( t ) } \ right \ | ^ { 二 } \ leq \ left \ | x _ { p }-m _ { j } ^ { ( t ) } \ right \ | ^ { 二 } \ forall j , 一 \ leq j \ leq k \ right \ } $ 其中每一个 $ x _ { p } $ 攏干焦予人分配著一个確定的聚類 $ S ^ { t } $ 中，就算講伊佇理論上伊可能予人分配去兩个抑是閣較濟聚類。

更新 ( Update )：對頂一步得著的每一个聚類，以聚類中觀測值的圖心，作為新的均值點。

$ m _ { i } ^ { ( t + 一 ) }={ \ frac { 一 } { \ 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 _-平均演算法會縮一寡特別慢：尤其是已經證明矣存在這个點集（甚至佇二維空間內底），予得 _ k _-平均演算法度沐沐的時間達到指數級（$ 二 ^ { \ Omega ( n ) } $）

。好佇現實中，按呢點集差不多袂出現：因為乎 _ k _-平均演算法的平滑執行時間是多項式時間的

。

註：共「分配」行為「期望」撇步，共「更新」行為「上大化步數」，會當看著，這演算法實際上是廣義向望啦-上大化演算法（GEM）的一个變體。

複雜度

佇咧 $ d $ 維空間內底揣著 _ k _-平均聚類問題的最佳解的計算複雜度：

NP-hard：一般歐式空間內底，就算目標聚類數干焦二
NP 困難喔：平面中，聚類數目 _ k _ 作限制
若是 _ k _ 和 $ d $ 攏有一个固定的，時間複雜度做 $ O ( n ^ { dk + 一 } logn ) $ , 其中 $ n $ 共聚類的觀測點數目相比並之下，Lloyds 演算法的執行時間通常為 $ O ( nkdi ) $ , _ k _ 和 $ d $ 定義如上，$ i $ 為直到覕鬚的時陣迵天天數。若是資料本身就有一定的聚類結構，遐爾仔收斂所需要迵天代數目通常是足少的，而且進行迵天代以後，閣做迵天代的話，對結果的改善效果足細。鑑於上述原因，Lloyds 演算法佇實踐中通常予人認為差不多是線性複雜度的。

下跤有幾个關於著這演算法複雜度的近期研究：

Lloyd's _ k _-平均演算法具有多項式平滑執行時間。對空間誠著 $ [零 , 一] ^ { d } $ 任意的 $ n $ 點集合，若每一个點攏獨立地受一个均值為 $ 零 $，標準差為 $ \ sigma $ 的常態分布所影響，遐爾 _ k _-平均演算法的向望執行時間上界為 $ O ( n ^ { 三十四 } k ^ { 三十四 } d ^ { 八 } log ^ { 四 } ( n ) / \ sigma ^ { 六 } ) $，即對著 $ n , k , i , d $ 和 $ 一 / \ sigma $ 攏是多項式時間的。
佇閣較簡單的情形下，有閣較好的頂懸。比如講，佇整數網格 $ \ left \ { 一 , . . . , M \ right \ } ^ { d } $ 中，_ k _-平均演算法執行時間的頂懸為 $ O ( dn ^ { 四 } M ^ { 二 } ) $。

演算法的變體

閣較濟討論

予得 _ k _-平均演算法效率誠懸的兩个關鍵特徵的同時嘛予定定予人看做是伊上大的缺陷：

聚類數目 _ k _ 是一个輸入參數。選擇無拄好做的 _ k _ 值可能會致使䆀的聚類結果。這嘛是為啥物欲進行特徵檢查來決定資料集的聚類數目矣。
收斂來局部最佳改，可能致使著「反直觀」的錯誤結果。

_ k _-平均演算法的一个重要的局限性即在伊的聚類模型。這模型的基本思想佇咧講：得著相分離的球狀聚類，佇遮的聚類當中，攏值點趨向收斂佇聚類中心。一般會希望得著的聚類大細大致相當，按呢共每一个觀測攏分配甲離伊上近的聚類中心（即均值點）就是較正確的分配方案。

_ k _-平均聚類的結果嘛會當理解做由均值點生成的 Voronoi cells。

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

_ k _-平均聚類，以及伊佮 EM 演算法的聯絡，是高斯混合模型的一个特例。真容易共 _ k _-平均的問題一般化為高斯混合模型。另外一个 _ k _-平均演算法的推廣著是 _ k _-SVD 演算法，後者共資料點看做是「編碼本向量」的稀疏線性組合。而且 _ k _-平均對應使用單編碼本向量的特殊情形（其權重為一）。

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