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