今天圖圖來聊聊K-平均算法（k-means clustering）——一種流行于數(shù)據(jù)挖掘領域的聚類分析方法。

1. 聚類與K-means

1.1 分類與聚類

分類問題是機器學習中最常見的一類問題（還有回歸與聚類等問題），其目標為確定一個事物所屬的類別。例如，當我們要判定一個水果是西瓜、蘋果，還是橘子時，可以先給一些各種類型的水果（貼好標簽的訓練集）讓算法學習，然后根據(jù)學習得到的經(jīng)驗（模型）對一個水果的類型（測試集）做出判定。這就像圖圖剛剛上幼兒園時，老師告訴俺每種水果是什么樣子的，接下來俺就會認這些類型的水果了。這種做法稱為有監(jiān)督學習，它有訓練和預測兩個過程，在訓練階段，使用大量的樣本進行學習，得到一個判定水果類型的模型。接下來，在預測階段，給一個水果，就可以用這個模型預測出它的類別。

聚類也是要確定一個事物的類別，但和分類問題不同的是，這里沒有事先定義好的標簽，聚類算法要自己想辦法把一批樣本分開，分成多個類，保證每一個類中的樣本之間是差異性盡可能小，而不同類的樣本之間差異盡可能大。在這里，類被稱為“簇”（cluster）。以圖圖的表情包庫為例，里面有很多圖片，我可以按照某種方式對其聚類，比如：

?動圖和靜圖（2個簇）?貓咪、狗頭和其它小動物（3個簇）

至于怎么分是合理的，那應該以斗圖效率最大化為優(yōu)化目標，至于多少個簇是無法事先確定的。事實上，在真正進行聚類的時候多少個簇確實也是比較難以確定的，大多數(shù)是根據(jù)經(jīng)驗。

聚類算法沒有訓練過程，這是和分類算法最本質(zhì)的區(qū)別，算法要根據(jù)自己定義的規(guī)則，將相似的樣本劃分在一起，不相似的樣本分成不同的類。

1.2 k-means

常見的聚類方式有如下幾種，其中K-均值聚類是比較容易上手的一種。

?K-均值聚類

?Mean-Shift聚類算法

?基于密度的噪聲應用空間聚類（DBSCAN）?使用高斯混合模型（GMM）的期望最大化（EM）聚類

?凝聚層次聚類

k-means的目的是：把N個點（事先并不知道它們之間的類別關系，也沒有給這些點貼上標簽）劃分到k個分類中，使得每個點都屬于離它最近的均值（聚類中心）對應的聚類，以之作為聚類的標準。這個問題將歸結為一個把數(shù)據(jù)空間劃分為沃羅諾伊圖（Voronoi Diagram)的問題。

可能聽著有些抽象，貼心的圖圖編了一個小故事。

1.3 k-means小故事引入

現(xiàn)在有A~G?7名同學想學MATLAB，他們的家分別在地圖上標出；還有通道、圖圖和道哥三位老師，他們不太清楚七位同學的家到底在哪。

?第一天，三位老師各自隨機地選擇了一個位置作為教室，并且發(fā)布了公告；

?第二天，同學們選擇最近的老師去上課；以A同學為例，他選擇了圖圖老師；老師們都記錄了來自己教室上課的學生家的位置。

?第三天，三位老師將各自的教室設置在自己學生們的家的中間位置（幾何中心），方便學生來上課，并將新的教室的位置發(fā)了公告；

?第四天，同學們依舊選擇最近的老師去上課；注意，此時有同學換了老師；

?繼續(xù)重復這一過程，直至老師的教室位置不再變，學生選擇的老師也不再變。

以上就完成了一個聚類的過程，將7名同學分成了3簇，可以稱為3-means。老師所在的位置就體現(xiàn)了每一簇的mean。

2. K-平均算法流程

2.1 算法簡述

已知觀測集{x_1,x_2,...,x_n}，

其中每個觀測都是一個d-維實向量，

k-平均聚類要把這n個觀測劃分到k個集合中(k≤n),使得組內(nèi)平方和（WCSS?within-cluster sum of squares）最小。換句話說，它的目標是找到使得下式滿足的聚類S_i:

其中mu _i是S_i中所有點的均值。

(在計算機科學領域有時也被稱為Lloyd算法)

2.2 一般流程

已知初始的k個均值點,算法的按照下面兩個步驟交替進行：

因為算術平均是最小二乘估計，所以這一步同樣減小了目標函數(shù)組內(nèi)平方和（WCSS）的值。

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

這一算法經(jīng)常被描述為“把觀測按照距離分配到最近的聚類”。

算法的目標函數(shù)是組內(nèi)平方和（WCSS），而且按照“最小二乘和”來分配觀測，確實是等價于按照最小歐氏距離來分配觀測的。如果使用不同的距離函數(shù)來代替（平方）歐氏距離，可能使得算法無法收斂。

2.3 其它補充

選擇K

分幾類主要取決于個人的經(jīng)驗與感覺，通常的做法是多嘗試幾個K值，看分成幾類的結果更好解釋，更符合分析目的等?；蛘呖梢园迅鞣NK值算出的SSE做比較，取最小的SSE的K值。

選擇初始聚類中心

最常用的方法是隨機選，初始質(zhì)心的選取對最終聚類結果有影響，因此算法一定要多執(zhí)行幾次。當然也有一些優(yōu)化的方法，或者根據(jù)其他聚類算法（如層次聚類）得到聚類結果，從結果中每個分類選一個點。

注意數(shù)據(jù)的歸一化處理！注意離群值！

3. K-means的MATLA實現(xiàn)

3.1 隨機生成了數(shù)百個二維數(shù)據(jù)進行聚類

3.2 使用 k 均值聚類將圖像分割成三個區(qū)域

[L,Centers] = imsegkmeans(I,3);

B = labeloverlay(I,L);

imshow(B)title('Labeled Image')

關注微信公眾號“圖通道”回復“KM”下載完整代碼

MATLAB交流群：1129425848；