一.概述
????? 在本篇文章中將對四種聚類算法(K-means,K-means++,ISODATA和Kernel K-means)進行詳細介紹，并利用數(shù)據(jù)集來真實地反映這四種算法之間的區(qū)別。
首先需要明確的是上述四種算法都屬于"硬聚類”算法，即數(shù)據(jù)集中每一個樣本都是被100%確定得分到某一個類別中。與之相對的"軟聚類”可以理解為每個樣本是以一定的概率被分到某一個類別中。
?先簡要闡述下上述四種算法之間的關(guān)系，已經(jīng)了解過經(jīng)典K-means算法的讀者應(yīng)該會有所體會。沒有了解過K-means的讀者可以先看下面的經(jīng)典K-means算法介紹再回來看這部分。
?(1)?K-means與K-means++：原始K-means算法最開始隨機選取數(shù)據(jù)集中K個點作為聚類中心，而K-means++按照如下的思想選取K個聚類中心：假設(shè)已經(jīng)選取了n個初始聚類中心(0<n<k)，則在選取第n+1個聚類中心時：距離當前n個聚類中心越遠的點會有更高的概率被選為第n+1個聚類中心。在選取第一個聚類中心(n=1)時同樣通過隨機的方法。可以說這也符合我們的直覺：聚類中心當然是互相離得越遠越好。這個改進雖然直觀簡單，但是卻非常得有效。
?(2)?K-means與ISODATA：ISODATA的全稱是迭代自組織數(shù)據(jù)分析法。在K-means中，K的值需要預(yù)先人為地確定，并且在整個算法過程中無法更改。而當遇到高維度、海量的數(shù)據(jù)集時，人們往往很難準確地估計出K的大小。ISODATA就是針對這個問題進行了改進，它的思想也很直觀：當屬于某個類別的樣本數(shù)過少時把這個類別去除，當屬于某個類別的樣本數(shù)過多、分散程度較大時把這個類別分為兩個子類別。
(3)?K-means與Kernel K-means：傳統(tǒng)K-means采用歐式距離進行樣本間的相似度度量，顯然并不是所有的數(shù)據(jù)集都適用于這種度量方式。參照支持向量機中核函數(shù)的思想，將所有樣本映射到另外一個特征空間中再進行聚類，就有可能改善聚類效果。本文不對Kernel K-means進行詳細介紹。
可以看到，上述三種針對K-means的改進分別是從不同的角度出發(fā)的，因此都非常具有代表意義。目前應(yīng)用廣泛的應(yīng)該還是K-means++算法（例如2016年底的NIPS上也有針對K-means++的改進，感興趣的讀者可以進一步學(xué)習(xí)）。
二.經(jīng)典K-means算法
算法描述如下，非常清晰易懂。經(jīng)典K-means算法應(yīng)該是每個無監(jiān)督學(xué)習(xí)教程開頭都會講的內(nèi)容，故不再多費口舌說一遍了。
值得一提的是關(guān)于聚類中心數(shù)目（K值）的選取，的確存在一種可行的方法，叫做Elbow Method：通過繪制K-means代價函數(shù)與聚類數(shù)目K的關(guān)系圖，選取直線拐點處的K值作為最佳的聚類中心數(shù)目。但在這邊不做過多的介紹，因為上述方法中的拐點在實際情況中是很少出現(xiàn)的。比較提倡的做法還是從實際問題出發(fā)，人工指定比較合理的K值，通過多次隨機初始化聚類中心選取比較滿意的結(jié)果。
三.K-means++算法
?2007年由D. Arthur等人提出的K-means++針對圖1中的第一步做了改進?？梢灾庇^地將這改進理解成這K個初始聚類中心相互之間應(yīng)該分得越開越好。整個算法的描述如下圖所示：
下面結(jié)合一個簡單的例子說明K-means++是如何選取初始聚類中心的。數(shù)據(jù)集中共有8個樣本，分布以及對應(yīng)序號如下圖所示：
假設(shè)經(jīng)過圖2的步驟一后6號點被選擇為第一個初始聚類中心，那在進行步驟二時每個樣本的D(x)和被選擇為第二個聚類中心的概率如下表所示：
其中的P(x)就是每個樣本被選為下一個聚類中心的概率。最后一行的Sum是概率P(x)的累加和，用于輪盤法選擇出第二個聚類中心。方法是隨機產(chǎn)生出一個0~1之間的隨機數(shù)，判斷它屬于哪個區(qū)間，那么該區(qū)間對應(yīng)的序號就是被選擇出來的第二個聚類中心了。例如1號點的區(qū)間為[0,0.2)，2號點的區(qū)間為[0.2, 0.525)。
從上表可以直觀的看到第二個初始聚類中心是1號，2號，3號，4號中的一個的概率為0.9。而這4個點正好是離第一個初始聚類中心6號點較遠的四個點。這也驗證了K-means的改進思想：即離當前已有聚類中心較遠的點有更大的概率被選為下一個聚類中心?？梢钥吹?，該例的K值取2是比較合適的。當K值大于2時，每個樣本會有多個距離，需要取最小的那個距離作為D(x)。
四.ISODATA算法
放在最后也是最復(fù)雜的就是ISODATA算法。正如之前所述，K-means和K-means++的聚類中心數(shù)K是固定不變的。而ISODATA算法在運行過程中能夠根據(jù)各個類別的實際情況進行兩種操作來調(diào)整聚類中心數(shù)K：(1)分裂操作，對應(yīng)著增加聚類中心數(shù)；(2)合并操作，對應(yīng)著減少聚類中心數(shù)。下面首先給出ISODATA算法的輸入（輸入的數(shù)據(jù)和迭代次數(shù)不再單獨介紹）：
[1] 預(yù)期的聚類中心數(shù)目Ko：雖然在ISODATA運行過程中聚類中心數(shù)目是可變的，但還是需要由用戶指定一個參考標準。事實上，該算法的聚類中心數(shù)目變動范圍也由Ko決定。具體地，最終輸出的聚類中心數(shù)目范圍是 [Ko/2,?2Ko]。
?[2] 每個類所要求的最少樣本數(shù)目Nmin：用于判斷當某個類別所包含樣本分散程度較大時是否可以進行分裂操作。如果分裂后會導(dǎo)致某個子類別所包含樣本數(shù)目小于Nmin，就不會對該類別進行分裂操作。
?[3] 最大方差Sigma：用于衡量某個類別中樣本的分散程度。當樣本的分散程度超過這個值時，則有可能進行分裂操作（注意同時需要滿足[2]中所述的條件）。
?[4] 兩個類別對應(yīng)聚類中心之間所允許最小距離dmin：如果兩個類別靠得非常近（即這兩個類別對應(yīng)聚類中心之間的距離非常?。?，則需要對這兩個類別進行合并操作。是否進行合并的閾值就是由dmin決定。
?相信很多人看完上述輸入的介紹后對ISODATA算法的流程已經(jīng)有所猜測了。的確，ISODATA算法的原理非常直觀，不過由于它和其他兩個方法相比需要額外指定較多的參數(shù)，并且某些參數(shù)同樣很難準確指定出一個較合理的值，因此ISODATA算法在實際過程中并沒有K-means++受歡迎。
首先給出ISODATA算法主體部分的描述，如下圖所示：
上面描述中沒有說明清楚的是第5步中的分裂操作和第6步中的合并操作。下面首先介紹合并操作：
最后是ISODATA算法中的分裂操作。
最后，針對ISODATA算法總結(jié)一下：該算法能夠在聚類過程中根據(jù)各個類所包含樣本的實際情況動態(tài)調(diào)整聚類中心的數(shù)目。如果某個類中樣本分散程度較大（通過方差進行衡量）并且樣本數(shù)量較大，則對其進行分裂操作；如果某兩個類別靠得比較近（通過聚類中心的距離衡量），則對它們進行合并操作。
可能沒有表述清楚的地方是ISODATA-分裂操作的第1步和第2步。同樣地以圖三所示數(shù)據(jù)集為例，假設(shè)最初1，2，3，4，5，6，8號被分到了同一個類中，執(zhí)行第1步和第2步結(jié)果如下所示：
而在正確分類情況下（即1，2，3，4為一類；5，6，7，8為一類），方差為0.33。因此，目前的方差遠大于理想的方差，ISODATA算法就很有可能對其進行分裂操作。
參考：https://www.cnblogs.com/yixuan-xu/p/6272208.html
