1.1 概述

K-means算法是集簡單和經典于一身的基于距離的聚類算法

采用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。

(資料圖片僅供參考)

該算法認為類簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標。

1.2 算法圖示

假設我們的n個樣本點分布在圖中所示的二維空間。

從數據點的大致形狀可以看出它們大致聚為三個cluster，其中兩個緊湊一些，剩下那個松散一些，如圖所示：

我們的目的是為這些數據分組，以便能區分出屬于不同的簇的數據，給它們標上不同的顏色，如圖：

1.3算法要點

1.3.1 核心思想

通過迭代尋找k個類簇的一種劃分方案，使得用這k個類簇的均值來代表相應各類樣本時所得的總體誤差最小。

k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

算法的基礎是最小誤差平方和準則,

其代價函數是：

式中，μc(i)表示第i個聚類的均值。

各類簇內的樣本越相似，其與該類均值間的誤差平方越小，對所有類所得到的誤差平方求和，即可驗證分為k類時，各聚類是否是最優的。

上式的代價函數無法用解析的方法最小化，只能有迭代的方法。

1.3.2 算法步驟圖解

下圖展示了對n個樣本點進行K-means聚類的效果，這里k取2。

1.3.3 算法實現步驟

k-means算法是將樣本聚類成 k個簇（cluster），其中k是用戶給定的，其求解過程非常直觀簡單，具體算法描述如下：

1)隨機選取 k個聚類質心點

2)重復下面過程直到收斂

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

對于每一個類 j，重新計算該類的質心：

其偽代碼如下：

********************************************************************

創建k個點作為初始的質心點（隨機選擇）

當任意一個點的簇分配結果發生改變時

對數據集中的每一個數據點

對每一個質心

計算質心與數據點的距離

將數據點分配到距離最近的簇

對每一個簇，計算簇中所有點的均值，并將均值作為質心

2. Kmeans分類算法Python實戰

2.1 需求

對給定的數據集進行聚類

本案例采用二維數據集，共80個樣本，有4個類。樣例如下：

testSet.txt

1.658985 4.285136

-3.453687 3.424321

4.838138 -1.151539

-5.379713 -3.362104

0.972564 2.924086

-3.567919 1.531611

0.450614 -3.302219

-3.487105 -1.724432

2.668759 1.594842

-3.156485 3.191137

3.165506 -3.999838

-2.786837 -3.099354

4.208187 2.984927

-2.123337 2.943366

0.704199 -0.479481

-0.392370 -3.963704

2.831667 1.574018

-0.790153 3.343144

2.943496 -3.357075

2.2 python代碼實現

2.2.1 利用numpy手動實現

2.2.2 利用scikili庫實現

Scikit-Learn是基于python的機器學習模塊，基于BSD開源許可證。

scikit-learn的基本功能主要被分為六個部分，分類，回歸，聚類，數據降維，模型選擇，數據預處理。包括SVM，決策樹，GBDT，KNN，KMEANS等等

Kmeans在scikit包中即已有實現，只要將數據按照算法要求處理好，傳入相應參數，即可直接調用其kmeans函數進行聚類

2.2.3 運行結果

不同的類用不同的顏色來表示，其中的大菱形是對應類的均值質心點。

3、Kmeans算法補充

3.1 kmeans算法缺點

k-means算法比較簡單，但也有幾個比較大的缺點：

（1）k值的選擇是用戶指定的，不同的k得到的結果會有挺大的不同，如下圖所示，左邊是k=3的結果，這個就太稀疏了，藍色的那個簇其實是可以再劃分成兩個簇的。而右圖是k=5的結果，可以看到紅色菱形和藍色菱形這兩個簇應該是可以合并成一個簇的：

（2）對k個初始質心的選擇比較敏感，容易陷入局部最小值。例如，我們上面的算法運行的時候，有可能會得到不同的結果，如下面這兩種情況。K-means也是收斂了，只是收斂到了局部最小值：

（3）存在局限性，如下面這種非球狀的數據分布就搞不定了：

（4）數據集比較大的時候，收斂會比較慢。

3.2 改良思路

k-means老早就出現在江湖了。所以以上的這些不足也已有了對應方法進行了某種程度上的改良。例如：

問題（1）對k的選擇可以先用一些算法分析數據的分布，如重心和密度等，然后選擇合適的k

問題（2），有人提出了另一個成為二分k均值（bisecting k-means）算法，它對初始的k個質心的選擇就不太敏感