[科普中國(guó)]-K平均算法

k平均聚類發(fā)明于1956年，是一個(gè)聚類算法，把n的對(duì)象根據(jù)他們的屬性分為k個(gè)分割，k 簡(jiǎn)介

k-平均算法（英文：k-means clustering）源于信號(hào)處理中的一種向量量化方法，現(xiàn)在則更多地作為一種聚類分析方法流行于數(shù)據(jù)挖掘領(lǐng)域。k-平均聚類的目的是：把{\displaystyle n}個(gè)點(diǎn)（可以是樣本的一次觀察或一個(gè)實(shí)例）劃分到k個(gè)聚類中，使得每個(gè)點(diǎn)都屬于離他最近的均值（此即聚類中心）對(duì)應(yīng)的聚類，以之作為聚類的標(biāo)準(zhǔn)。這個(gè)問(wèn)題將歸結(jié)為一個(gè)把數(shù)據(jù)空間劃分為Voronoi cells的問(wèn)題。

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

k-平均聚類與k-近鄰之間沒(méi)有任何關(guān)系（后者是另一流行的機(jī)器學(xué)習(xí)技術(shù)）。1

算法描述已知觀測(cè)集，其中每個(gè)觀測(cè)都是一個(gè){\displaystyle d}-維實(shí)向量，k-平均聚類要把這n個(gè)觀測(cè)劃分到k個(gè)集合中(k≤n),使得組內(nèi)平方和（WCSS within-cluster sum of squares）最小。換句話說(shuō)，它的目標(biāo)是找到使得下式滿足的聚類，

其中是中所有點(diǎn)的均值。1

歷史源流雖然其思想能夠追溯到1957年的Hugo Steinhaus，術(shù)語(yǔ)“k-均值”于1967年才被James MacQueen首次使用。標(biāo)準(zhǔn)算法則是在1957年被Stuart Lloyd作為一種脈沖碼調(diào)制的技術(shù)所提出，但直到1982年才被貝爾實(shí)驗(yàn)室公開(kāi)出版。在1965年，E.W.Forgy發(fā)表了本質(zhì)上相同的方法，所以這一算法有時(shí)被稱為L(zhǎng)loyd-Forgy方法。更高效的版本則被Hartigan and Wong提出（1975/1979）。1

本詞條內(nèi)容貢獻(xiàn)者為:

胡啟洲 - 副教授 - 南京理工大學(xué)