? 本文主要基于Anand Rajaraman和Jeffrey David Ullman合著，王斌翻譯的《大數(shù)據(jù)-互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理》一書。
? KMeans算法是最常用的聚類算法，主要思想是:在給定K值和K個初始類簇中心點的情況下，把每個點(亦即數(shù)據(jù)記錄)分到離其最近的類簇中心點所代表的類簇中，所有點分配完畢之后，根據(jù)一個類簇內(nèi)的所有點重新計算該類簇的中心點(取平均值)，然后再迭代的進(jìn)行分配點和更新類簇中心點的步驟，直至類簇中心點的變化很小，或者達(dá)到指定的迭代次數(shù)。
? KMeans算法本身思想比較簡單，但是合理的確定K值和K個初始類簇中心點對于聚類效果的好壞有很大的影響。
? 1. 確定K個初始類簇中心點
? 最簡單的確定初始類簇中心點的方法是隨機(jī)選擇K個點作為初始的類簇中心點，但是該方法在有些情況下的效果較差，如下(下圖中的數(shù)據(jù)是用五個二元正態(tài)高斯分布生成的，顏色代表聚類效果)：
? 《大數(shù)據(jù)》一書中提到K個初始類簇點的選取還有兩種方法：1)選擇彼此距離盡可能遠(yuǎn)的K個點 2)先對數(shù)據(jù)用層次聚類算法或者Canopy算法進(jìn)行聚類，得到K個簇之后，從每個類簇中選擇一個點，該點可以是該類簇的中心點，或者是距離類簇中心點最近的那個點。
? 1) 選擇批次距離盡可能遠(yuǎn)的K個點
? 首先隨機(jī)選擇一個點作為第一個初始類簇中心點，然后選擇距離該點最遠(yuǎn)的那個點作為第二個初始類簇中心點，然后再選擇距離前兩個點的最近距離最大的點作為第三個初始類簇的中心點，以此類推，直至選出K個初始類簇中心點。
? 該方法經(jīng)過我測試效果很好，用該方法確定初始類簇點之后運(yùn)行KMeans得到的結(jié)果全部都能完美區(qū)分五個類簇：
??
? 2) 選用層次聚類或者Canopy算法進(jìn)行初始聚類，然后利用這些類簇的中心點作為KMeans算法初始類簇中心點。
? 常用的層次聚類算法有BIRCH和ROCK，在此不作介紹，下面簡單介紹一下Canopy算法，主要摘自Mahout的Wiki：
? 首先定義兩個距離T1和T2，T1>T2.從初始的點的集合S中隨機(jī)移除一個點P，然后對于還在S中的每個點I，計算該點I與點P的距離，如果距離小于T1，則將點I加入到點P所代表的Canopy中，如果距離小于T2，則將點I從集合S中移除，并將點I加入到點P所代表的Canopy中。迭代完一次之后，重新從集合S中隨機(jī)選擇一個點作為新的點P，然后重復(fù)執(zhí)行以上步驟。
? Canopy算法執(zhí)行完畢后會得到很多Canopy，可以認(rèn)為每個Canopy都是一個Cluster，與KMeans等硬劃分算法不同，Canopy的聚類結(jié)果中每個點有可能屬于多個Canopy。我們可以選擇距離每個Canopy的中心點最近的那個數(shù)據(jù)點，或者直接選擇每個Canopy的中心點作為KMeans的初始K個類簇中心點。
? 2. K值的確定。
? 《大數(shù)據(jù)》中提到：給定一個合適的類簇指標(biāo)，比如平均半徑或直徑，只要我們假設(shè)的類簇的數(shù)目等于或者高于真實的類簇的數(shù)目時，該指標(biāo)上升會很緩慢，而一旦試圖得到少于真實數(shù)目的類簇時，該指標(biāo)會急劇上升。
? 類簇的直徑是指類簇內(nèi)任意兩點之間的最大距離。
? 類簇的半徑是指類簇內(nèi)所有點到類簇中心距離的最大值。
? 廢話少說，上圖。下圖是當(dāng)K的取值從2到9時，聚類效果和類簇指標(biāo)的效果圖：
? 左圖是K取值從2到7時的聚類效果，右圖是K取值從2到9時的類簇指標(biāo)的變化曲線，此處我選擇類簇指標(biāo)是K個類簇的平均質(zhì)心距離的加權(quán)平均值。從上圖中可以明顯看到，當(dāng)K取值5時，類簇指標(biāo)的下降趨勢最快，所以K的正確取值應(yīng)該是5.為以下是具體數(shù)據(jù)：
1
2
個聚類
2
所有類簇的半徑的加權(quán)平均值 8.51916676443
3
所有類簇的平均質(zhì)心距離的加權(quán)平均值 4.82716260322
4
3
個聚類
5
所有類簇的半徑的加權(quán)平均值 7.58444829472
6
所有類簇的平均質(zhì)心距離的加權(quán)平均值 3.37661824845
7
4
個聚類
8
所有類簇的半徑的加權(quán)平均值 5.65489660064
9
所有類簇的平均質(zhì)心距離的加權(quán)平均值 2.22135360453
10
5
個聚類
11
所有類簇的半徑的加權(quán)平均值 3.67478798553
12
所有類簇的平均質(zhì)心距離的加權(quán)平均值 1.25657641195
13
6
個聚類
14
所有類簇的半徑的加權(quán)平均值 3.44686996398
15
所有類簇的平均質(zhì)心距離的加權(quán)平均值 1.20944264145
16
7
個聚類
17
所有類簇的半徑的加權(quán)平均值 3.3036641135
18
所有類簇的平均質(zhì)心距離的加權(quán)平均值 1.16653919186
19
8
個聚類
20
所有類簇的半徑的加權(quán)平均值 3.30268530308
21
所有類簇的平均質(zhì)心距離的加權(quán)平均值 1.11361639906
22
9
個聚類
23
所有類簇的半徑的加權(quán)平均值 3.17924400582
24
所有類簇的平均質(zhì)心距離的加權(quán)平均值 1.07431888569
? 參考文獻(xiàn)：
? [1] 《大數(shù)據(jù)-互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理》 Anand Rajaraman，Jeffrey David Ullman著，王斌譯。
? [2] ? Mahout Wiki-Canopy
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
