機器學習實戰ByMatlab（3）：K-means算法

原文出處： Liu_LongPo的專欄（@Liu_LongPo）   

K-means算法屬于無監督學習聚類算法，其計算步驟還是挺簡單的，思想也挺容易理解，而且還可以在思想中體會到EM算法的思想。

K-means 算法的優缺點：

1.優點：容易實現
2.缺點：可能收斂到局部最小值，在大規模數據集上收斂較慢

使用數據類型：數值型數據

以往的回歸算法、樸素貝葉斯、SVM等都是有類別標簽y的，因此屬于有監督學習，而K-means聚類算法只有x，沒有y

在聚類問題中，我們的訓練樣本是

其中每個Xi都是n維實數。

樣本數據中沒有了y，K-means算法是將樣本聚類成k個簇，具體算法如下：
1、隨機選取K個聚類質心點，記為

2、重復以下過程直到收斂

{
對每個樣例 i ，計算其應該屬于的類：

對每個類 j ，重新計算質心：

}

其中K是我們事先給定的聚類數目，Ci 表示樣本 i 與K個聚類中最近的那個類，Ci的值是1到K中的一個，質心uj代表我們對屬于同一個類的樣本中心的猜測。解釋起來就是，

第一步：天空上的我們隨機抽取K個星星作為星團的質心，然后對于每一個星星 i，我們計算它到每一個質心uj的距離，選取其中距離最短的星團作為Ci，這樣第一步每個星星都有了自己所屬于的星團；

第二步：對每個星團Ci，我們重新計算它的質心uj（計算方法為對屬于該星團的所有點的坐標求平均）不斷重復第一步和第二步直到質心變化很小或者是不變。

然后問題來了，怎么樣才算質心變化很小或者是不變？或者說怎么判定？答案就是畸變函數（distortion function），定義如下：

J函數表示每個樣本點到其質心的距離平方和，K-means的收斂就是要將 J 調整到最小，假設當前 J 值沒有達到最小值，那么可以先固定每個類的質心 uj ，調整每個樣例的類別 Ci 來時 J 函數減少。同樣，固定 Ci ，調整每個類的質心 uj也可以是 J 減少。這兩個過程就是內循環中使 J 單調變小的過程。當 J 減小到最小的時候， u 和 c 也同時收斂。（該過程跟EM算法其實還是挺像的）理論上可能出現多組 u 和 c 使 J 取得最小值，但這種情況實際上很少見。

由于畸變函數 J 是非凸函數，所以我們不能保證取得的最小值一定是全局最小值，這說明k-means算法質心的初始位置的選取會影響到最后最小值的獲取。不過一般情況下，k-means算法達到的局部最優已經滿足要求。如果不幸代碼陷入局部最優，我們可以選取不同的初始值跑多幾遍 k-means 算法，然后選取其中最小的 J 對應的 u 和 c 輸出。

另一種收斂判斷：

實際我們編寫代碼的時候，還可以通過判斷“每個點被分配的質心是否改變”這個條件來判斷聚類是否已經收斂

而上面所說的畸變函數則可以用來評估收斂的效果，具體將會在下面的實例中體現。

Matlab 實現

function kMeans
clc
clear
K = 4;
dataSet = load('testSet.txt');
[row,col] = size(dataSet);
% 存儲質心矩陣
centSet = zeros(K,col);
% 隨機初始化質心
for i= 1:col
 minV = min(dataSet(:,i));
 rangV = max(dataSet(:,i)) - minV;
 centSet(:,i) = repmat(minV,[K,1]) + rangV*rand(K,1);
end
% 用于存儲每個點被分配的cluster以及到質心的距離
clusterAssment = zeros(row,2);
clusterChange = true;
while clusterChange
 clusterChange = false;
 % 計算每個點應該被分配的cluster
 for i = 1:row
 % 這部分可能可以優化
 minDist = 10000;
 minIndex = 0;
 for j = 1:K
 distCal = distEclud(dataSet(i,:) , centSet(j,:));
 if (distCal < minDist)
 minDist = distCal;
 minIndex = j;
 end
 end
 if minIndex ~= clusterAssment(i,1) 
 clusterChange = true;
 end
 clusterAssment(i,1) = minIndex;
 clusterAssment(i,2) = minDist;
 end
% 更新每個cluster 的質心
 for j = 1:K
 simpleCluster = find(clusterAssment(:,1) == j);
 centSet(j,:) = mean(dataSet(simpleCluster',:));
 end
end
figure
%scatter(dataSet(:,1),dataSet(:,2),5)
for i = 1:K
 pointCluster = find(clusterAssment(:,1) == i);
 scatter(dataSet(pointCluster,1),dataSet(pointCluster,2),5)
 hold on
end
%hold on
scatter(centSet(:,1),centSet(:,2),300,'+')
hold off
end
% 計算歐式距離
function dist = distEclud(vecA,vecB)
 dist = sqrt(sum(power((vecA-vecB),2)));
end

效果如下：

這是正常分類的情況，很明顯被分為了4個類，不同顏色代表不同的類，cluster的質心為 “ + ”

當然，這只是其中一種情況，很有可能我們會出現下面這種情況：

這就是上面所說的，K-means的缺點之一，隨機初始點的選擇可能會讓算法陷入局部最優解，這時候我們只需重新運行一次程序即可。

至于每一個看似都可以正常聚類的情況呢，我們則利用上面所說的“畸變函數”來衡量聚類的效果，當然是J越小聚類效果越好。

實際使用的時候，我們只需多次運行程序，選取J最小的聚類效果。