來源 | Datawhale
作者 | 阿澤
算法
1.1 牧師-村民模型
K-means 有一個著名的解釋：牧師—村民模型：
有四個牧師去郊區佈道，一開始牧師們隨意選了幾個佈道點，並且把這幾個佈道點的情況公告給了郊區所有的村民，於是每個村民到離自己家最近的佈道點去聽課。
聽課之後，大家覺得距離太遠了，於是每個牧師統計了一下自己的課上所有的村民的地址，搬到了所有地址的中心地帶，並且在海報上更新了自己的佈道點的位置。
牧師每一次移動不可能離所有人都更近，有的人發現A牧師移動以後自己還不如去B牧師處聽課更近，於是每個村民又去了離自己最近的佈道點……
就這樣，牧師每個禮拜更新自己的位置，村民根據自己的情況選擇佈道點，最終穩定了下來。
我們可以看到該牧師的目的是為了讓每個村民到其最近中心點的距離和最小。
1.2 算法步驟
所以 K-means 的算法步驟為：
- 選擇初始化的 k 個樣本作為初始聚類中心 ；
- 針對數據集中每個樣本 計算它到 k 個聚類中心的距離並將其分到距離最小的聚類中心所對應的類中；
- 針對每個類別 ，重新計算它的聚類中心 （即屬於該類的所有樣本的質心）；
- 重複上面 2 3 兩步操作，直到達到某個中止條件（迭代次數、最小誤差變化等）。
1.3 複雜度
我們先看下偽代碼：
<code>獲取數據 n 個 m 維的數據隨機生成 K 個 m 維的點while(t)for(int i=0;i < n;i++)for(int j=0;j < k;j++)計算點 i 到類 j 的距離 for(int i=0;i < k;i++) 1. 找出所有屬於自己這一類的所有數據點 2. 把自己的座標修改為這些數據點的中心點座標end/<code>
時間複雜度：，其中，t 為迭代次數，k 為簇的數目，n 為樣本點數，m 為樣本點維度。
空間複雜度：，其中，k 為簇的數目，m 為樣本點維度，n 為樣本點數。
優缺點
2.1 優點
- 容易理解，聚類效果不錯，雖然是局部最優， 但往往局部最優就夠了；
- 處理大數據集的時候，該算法可以保證較好的伸縮性；
- 當簇近似高斯分佈的時候，效果非常不錯；
- 算法複雜度低。
2.2 缺點
- K 值需要人為設定，不同 K 值得到的結果不一樣；
- 對初始的簇中心敏感，不同選取方式會得到不同結果；
- 對異常值敏感；
- 樣本只能歸為一類，不適合多分類任務；
- 不適合太離散的分類、樣本類別不平衡的分類、非凸形狀的分類。
算法調優與改進
針對 K-means 算法的缺點，我們可以有很多種調優方式：如數據預處理（去除異常點），合理選擇 K 值，高維映射等。以下將簡單介紹：
3.1 數據預處理
K-means 的本質是基於歐式距離的數據劃分算法，均值和方差大的維度將對數據的聚類產生決定性影響。所以未做歸一化處理和統一單位的數據是無法直接參與運算和比較的。常見的數據預處理方式有：數據歸一化，數據標準化。
此外，離群點或者噪聲數據會對均值產生較大的影響，導致中心偏移，因此我們還需要對數據進行異常點檢測。
3.2 合理選擇 K 值
K 值的選取對 K-means 影響很大，這也是 K-means 最大的缺點，常見的選取 K 值的方法有：手肘法、Gap statistic 方法。
手肘法：
當 K < 3 時，曲線急速下降；當 K > 3 時，曲線趨於平穩，通過手肘法我們認為拐點 3 為 K 的最佳值。
手肘法的缺點在於需要人工看不夠自動化，所以我們又有了 Gap statistic 方法，這個方法出自斯坦福大學的幾個學者的論文：Estimating the number of clusters in a data set via the gap statistic
其中 為損失函數，這裡 指的是 的期望。這個數值通常通過蒙特卡洛模擬產生，我們在樣本里所在的區域中按照均勻分佈隨機產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本做 K-Means，從而得到一個 。如此往復多次，通常 20 次，我們可以得到 20 個 。對這 20 個數值求平均值，就得到了的近似值。最終可以計算 Gap Statisitc。而 Gap statistic 取得最大值所對應的 K 就是最佳的 K。
由圖可見，當 K=3 時，Gap(K) 取值最大，所以最佳的簇數是 K=3。
Github 上一個項目叫 gap_statistic ，可以更方便的獲取建議的類簇個數。
3.3 採用核函數
基於歐式距離的 K-means 假設了了各個數據簇的數據具有一樣的的先驗概率並呈現球形分佈，但這種分佈在實際生活中並不常見。面對非凸的數據分佈形狀時我們可以引入核函數來優化，這時算法又稱為核 K-means 算法，是核聚類方法的一種。核聚類方法的主要思想是通過一個非線性映射，將輸入空間中的數據點映射到高位的特徵空間中，並在新的特徵空間中進行聚類。非線性映射增加了數據點線性可分的概率，從而在經典的聚類算法失效的情況下，通過引入核函數可以達到更為準確的聚類結果。
3.4 K-means++
我們知道初始值的選取對結果的影響很大，對初始值選擇的改進是很重要的一部分。在所有的改進算法中，K-means++ 最有名。
K-means++ 算法步驟如下所示：
- 隨機選取一箇中心點 ；
- 計算數據到之前 n 個聚類中心最遠的距離 ，並以一定概率 選擇新中心點 ；
- 重複第二步。
簡單的來說，就是 K-means++ 就是選擇離已選中心點最遠的點。這也比較符合常理，聚類中心當然是互相離得越遠越好。
但是這個算法的缺點在於，難以並行化。所以 k-means II 改變取樣策略，並非按照 k-means++ 那樣每次遍歷只取樣一個樣本，而是每次遍歷取樣 k 個，重複該取樣過程 次，則得到 個樣本點組成的集合，然後從這些點中選取 k 個。當然一般也不需要 次取樣，5 次即可。
3.5 ISODATA
ISODATA 的全稱是迭代自組織數據分析法。它解決了 K 的值需要預先人為的確定這一缺點。而當遇到高維度、海量的數據集時，人們往往很難準確地估計出 K 的大小。ISODATA 就是針對這個問題進行了改進，它的思想也很直觀：當屬於某個類別的樣本數過少時把這個類別去除，當屬於某個類別的樣本數過多、分散程度較大時把這個類別分為兩個子類別。
收斂證明
我們先來看一下 K-means 算法的步驟：先隨機選擇初始節點，然後計算每個樣本所屬類別，然後通過類別再跟新初始化節點。這個過程有沒有想到之前介紹的 EM 算法 。
我們需要知道的是 K-means 聚類的迭代算法實際上是 EM 算法。EM 算法解決的是在概率模型中含有無法觀測的隱含變量情況下的參數估計問題。在 K-means 中的隱變量是每個類別所屬類別。K-means 算法迭代步驟中的 每次確認中心點以後重新進行標記 對應 EM 算法中的 E 步 求當前參數條件下的 Expectation 。而 根據標記重新求中心點 對應 EM 算法中的 M 步 求似然函數最大化時（損失函數最小時）對應的參數 。
首先我們看一下損失函數的形式：
其中：
為了求極值，我們令損失函數求偏導數且等於 0：
k 是指第 k 箇中心點，於是我們有：
可以看出，新的中心點就是所有該類的質心。
EM 算法的缺點就是，容易陷入局部極小值，這也是 K-means 有時會得到局部最優解的原因。
參考
[1] 《機器學習》周志華
[2] https://zhuanlan.zhihu.com/p/20463356
[3] http://sofasofa.io/forum_main_post.php?postid=1000282
The End
閱讀更多 AI小白入門 的文章
