?
目錄
?一、概述
二、經(jīng)典K-means算法
三、K-means++算法
四、ISODATA算法
六、數(shù)據(jù)集測試
?一、概述
????? 在本篇文章中將對四種聚類算法(K-means,K-means++,ISODATA和Kernel K-means)進(jìn)行詳細(xì)介紹，并利用數(shù)據(jù)集來真實(shí)地反映這四種算法之間的區(qū)別。
????? 首先需要明確的是上述四種算法都屬于"硬聚類”算法，即數(shù)據(jù)集中每一個(gè)樣本都是被100%確定得分到某一個(gè)類別中。與之相對的"軟聚類”可以理解為每個(gè)樣本是以一定的概率被分到某一個(gè)類別中。
??????先簡要闡述下上述四種算法之間的關(guān)系，已經(jīng)了解過經(jīng)典K-means算法的讀者應(yīng)該會(huì)有所體會(huì)。沒有了解過K-means的讀者可以先看下面的經(jīng)典K-means算法介紹再回來看這部分。
?????(1)?K-means與K-means++：原始K-means算法最開始隨機(jī)選取數(shù)據(jù)集中K個(gè)點(diǎn)作為聚類中心，而K-means++按照如下的思想選取K個(gè)聚類中心：假設(shè)已經(jīng)選取了n個(gè)初始聚類中心(0<n<K)，則在選取第n+1個(gè)聚類中心時(shí)：距離當(dāng)前n個(gè)聚類中心越遠(yuǎn)的點(diǎn)會(huì)有更高的概率被選為第n+1個(gè)聚類中心。在選取第一個(gè)聚類中心(n=1)時(shí)同樣通過隨機(jī)的方法。可以說這也符合我們的直覺：聚類中心當(dāng)然是互相離得越遠(yuǎn)越好。這個(gè)改進(jìn)雖然直觀簡單，但是卻非常得有效。
??????(2)?K-means與ISODATA：ISODATA的全稱是迭代自組織數(shù)據(jù)分析法。在K-means中，K的值需要預(yù)先人為地確定，并且在整個(gè)算法過程中無法更改。而當(dāng)遇到高維度、海量的數(shù)據(jù)集時(shí)，人們往往很難準(zhǔn)確地估計(jì)出K的大小。ISODATA就是針對這個(gè)問題進(jìn)行了改進(jìn)，它的思想也很直觀：當(dāng)屬于某個(gè)類別的樣本數(shù)過少時(shí)把這個(gè)類別去除，當(dāng)屬于某個(gè)類別的樣本數(shù)過多、分散程度較大時(shí)把這個(gè)類別分為兩個(gè)子類別。
????? (3)?K-means與Kernel K-means：傳統(tǒng)K-means采用歐式距離進(jìn)行樣本間的相似度度量，顯然并不是所有的數(shù)據(jù)集都適用于這種度量方式。參照支持向量機(jī)中核函數(shù)的思想，將所有樣本映射到另外一個(gè)特征空間中再進(jìn)行聚類，就有可能改善聚類效果。本文不對Kernel K-means進(jìn)行詳細(xì)介紹。
????? 可以看到，上述三種針對K-means的改進(jìn)分別是從不同的角度出發(fā)的，因此都非常具有代表意義。目前應(yīng)用廣泛的應(yīng)該還是K-means++算法（例如2016年底的NIPS上也有針對K-means++的改進(jìn)，感興趣的讀者可以進(jìn)一步學(xué)習(xí)https://papers.nips.cc/paper/6478-fast-and-provably-good-seedings-for-k-means）。
二、經(jīng)典K-means算法
????算法描述如下，非常清晰易懂。經(jīng)典K-means算法應(yīng)該是每個(gè)無監(jiān)督學(xué)習(xí)教程開頭都會(huì)講的內(nèi)容，故不再多費(fèi)口舌說一遍了。
圖1. 經(jīng)典K-means算法
????? 值得一提的是關(guān)于聚類中心數(shù)目（K值）的選取，的確存在一種可行的方法，叫做Elbow Method：通過繪制K-means代價(jià)函數(shù)與聚類數(shù)目K的關(guān)系圖，選取直線拐點(diǎn)處的K值作為最佳的聚類中心數(shù)目。但在這邊不做過多的介紹，因?yàn)樯鲜龇椒ㄖ械墓拯c(diǎn)在實(shí)際情況中是很少出現(xiàn)的。比較提倡的做法還是從實(shí)際問題出發(fā)，人工指定比較合理的K值，通過多次隨機(jī)初始化聚類中心選取比較滿意的結(jié)果。
三、K-means++算法
??????2007年由D. Arthur等人提出的K-means++針對圖1中的第一步做了改進(jìn)?？梢灾庇^地將這改進(jìn)理解成這K個(gè)初始聚類中心相互之間應(yīng)該分得越開越好。整個(gè)算法的描述如下圖所示：
????圖2. K-means++算法
????? 下面結(jié)合一個(gè)簡單的例子說明K-means++是如何選取初始聚類中心的。數(shù)據(jù)集中共有8個(gè)樣本，分布以及對應(yīng)序號(hào)如下圖所示：
圖3. K-means++示例
????? 假設(shè)經(jīng)過圖2的步驟一后6號(hào)點(diǎn)被選擇為第一個(gè)初始聚類中心，那在進(jìn)行步驟二時(shí)每個(gè)樣本的D(x)和被選擇為第二個(gè)聚類中心的概率如下表所示：
??? 其中的P(x)就是每個(gè)樣本被選為下一個(gè)聚類中心的概率。最后一行的Sum是概率P(x)的累加和，用于輪盤法選擇出第二個(gè)聚類中心。方法是隨機(jī)產(chǎn)生出一個(gè)0~1之間的隨機(jī)數(shù)，判斷它屬于哪個(gè)區(qū)間，那么該區(qū)間對應(yīng)的序號(hào)就是被選擇出來的第二個(gè)聚類中心了。例如1號(hào)點(diǎn)的區(qū)間為[0,0.2)，2號(hào)點(diǎn)的區(qū)間為[0.2, 0.525)。
????? 從上表可以直觀的看到第二個(gè)初始聚類中心是1號(hào)，2號(hào)，3號(hào)，4號(hào)中的一個(gè)的概率為0.9。而這4個(gè)點(diǎn)正好是離第一個(gè)初始聚類中心6號(hào)點(diǎn)較遠(yuǎn)的四個(gè)點(diǎn)。這也驗(yàn)證了K-means的改進(jìn)思想：即離當(dāng)前已有聚類中心較遠(yuǎn)的點(diǎn)有更大的概率被選為下一個(gè)聚類中心。可以看到，該例的K值取2是比較合適的。當(dāng)K值大于2時(shí)，每個(gè)樣本會(huì)有多個(gè)距離，需要取最小的那個(gè)距離作為D(x)。
四、ISODATA算法
???? 放在最后也是最復(fù)雜的就是ISODATA算法。正如之前所述，K-means和K-means++的聚類中心數(shù)K是固定不變的。而ISODATA算法在運(yùn)行過程中能夠根據(jù)各個(gè)類別的實(shí)際情況進(jìn)行兩種操作來調(diào)整聚類中心數(shù)K：(1)分裂操作，對應(yīng)著增加聚類中心數(shù)；(2)合并操作，對應(yīng)著減少聚類中心數(shù)。
??? 下面首先給出ISODATA算法的輸入（輸入的數(shù)據(jù)和迭代次數(shù)不再單獨(dú)介紹）：
??????[1] 預(yù)期的聚類中心數(shù)目Ko：雖然在ISODATA運(yùn)行過程中聚類中心數(shù)目是可變的，但還是需要由用戶指定一個(gè)參考標(biāo)準(zhǔn)。事實(shí)上，該算法的聚類中心數(shù)目變動(dòng)范圍也由Ko決定。具體地，最終輸出的聚類中心數(shù)目范圍是 [Ko/2,?2Ko]。
??????[2] 每個(gè)類所要求的最少樣本數(shù)目Nmin：用于判斷當(dāng)某個(gè)類別所包含樣本分散程度較大時(shí)是否可以進(jìn)行分裂操作。如果分裂后會(huì)導(dǎo)致某個(gè)子類別所包含樣本數(shù)目小于Nmin，就不會(huì)對該類別進(jìn)行分裂操作。
??????[3] 最大方差Sigma：用于衡量某個(gè)類別中樣本的分散程度。當(dāng)樣本的分散程度超過這個(gè)值時(shí)，則有可能進(jìn)行分裂操作（注意同時(shí)需要滿足[2]中所述的條件）。
??????[4] 兩個(gè)類別對應(yīng)聚類中心之間所允許最小距離dmin：如果兩個(gè)類別靠得非常近（即這兩個(gè)類別對應(yīng)聚類中心之間的距離非常?。瑒t需要對這兩個(gè)類別進(jìn)行合并操作。是否進(jìn)行合并的閾值就是由dmin決定。
????? 相信很多人看完上述輸入的介紹后對ISODATA算法的流程已經(jīng)有所猜測了。的確，ISODATA算法的原理非常直觀，不過由于它和其他兩個(gè)方法相比需要額外指定較多的參數(shù)，并且某些參數(shù)同樣很難準(zhǔn)確指定出一個(gè)較合理的值，因此ISODATA算法在實(shí)際過程中并沒有K-means++受歡迎。
????? 首先給出ISODATA算法主體部分的描述，如下圖所示：
圖4. ISODATA算法的主體部分
???? 上面描述中沒有說明清楚的是第5步中的分裂操作和第6步中的合并操作。下面首先介紹合并操作：
圖5. ISODATA算法的合并操作
???? 最后是ISODATA算法中的分裂操作。
圖6. ISODATA算法的分裂操作
????? 最后，針對ISODATA算法總結(jié)一下：該算法能夠在聚類過程中根據(jù)各個(gè)類所包含樣本的實(shí)際情況動(dòng)態(tài)調(diào)整聚類中心的數(shù)目。如果某個(gè)類中樣本分散程度較大（通過方差進(jìn)行衡量）并且樣本數(shù)量較大，則對其進(jìn)行分裂操作；如果某兩個(gè)類別靠得比較近（通過聚類中心的距離衡量），則對它們進(jìn)行合并操作。
???????可能沒有表述清楚的地方是ISODATA-分裂操作的第1步和第2步。同樣地以圖三所示數(shù)據(jù)集為例，假設(shè)最初1，2，3，4，5，6，8號(hào)被分到了同一個(gè)類中，執(zhí)行第1步和第2步結(jié)果如下所示：
????? 而在正確分類情況下（即1，2，3，4為一類；5，6，7，8為一類），方差為0.33。因此，目前的方差遠(yuǎn)大于理想的方差，ISODATA算法就很有可能對其進(jìn)行分裂操作。
五、聚類算法源代碼
????? 我已經(jīng)將上述三種算法整合成一個(gè)Matlab函數(shù)Clustering.m。讀者可以直接使用該函數(shù)對數(shù)據(jù)集進(jìn)行聚類。由于代碼比較長，而且代碼插件還不怎么會(huì)用，就不在文中介紹了。需要使用的讀者可以點(diǎn)擊下面的鏈接下載使用（歡迎Star和Fork，之后會(huì)不定期補(bǔ)充新的算法和優(yōu)化的）：
GitHub - xuyxu/Clustering: Clustering / Subspace Clustering Algorithms on MATLAB
?????使用方式非常簡單，目前支持三種形式的輸入，分別對應(yīng)著上面的三種算法：
???? [centroid, result] =?Clustering(data, ‘kmeans’, k , iteration);
?????[centroid, result] =?Clustering(data, ‘kmeans++’, k , iteration);
?????[centroid, result] =
???Clustering(data, ‘isodata’, desired_k , iteration, minimum_n, maximum_variance, minimum_d);
????? 其中的輸入data是一個(gè)矩陣，每一行代表數(shù)據(jù)集中的一個(gè)樣本。其他輸入的意義與上面的算法描述中一一對應(yīng)。輸出的centroid是聚類中心的位置，result是每個(gè)樣本所對應(yīng)的類別索引。
六、數(shù)據(jù)集測試
????? 最后以一個(gè)簡單的滿足二維高斯分布的數(shù)據(jù)集為例，展示上述三種算法的聚類結(jié)果，如下圖所示。
圖7. 一個(gè)簡單數(shù)據(jù)集上三種算法的聚類效果（綠色加號(hào)代表聚類中心位置）
引用參考：文章來源：http://www.zghlxwxcb.cn/news/detail-817600.html
K-means聚類算法的三種改進(jìn)(K-means++,ISODATA,Kernel K-means)介紹與對比https://www.cnblogs.com/yixuan-xu/p/6272208.html文章來源地址http://www.zghlxwxcb.cn/news/detail-817600.html
到了這里，關(guān)于K-means聚類算法的三種改進(jìn)(K-means++,ISODATA,Kernel K-means)介紹與對比的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
