聚類(lèi)算法課件

主要內(nèi)容：Kmeans實(shí)戰(zhàn)聚類(lèi)算法簡(jiǎn)介Kmeans算法詳解Kmeans算法的缺陷及若干改進(jìn)Kmeans的單機(jī)實(shí)現(xiàn)與分布式實(shí)現(xiàn)策略

聚類(lèi)算法簡(jiǎn)介123聚類(lèi)的目標(biāo)：將一組向量分成若干組，組內(nèi)數(shù)據(jù)是相似的，而組間數(shù)據(jù)是有較明顯差異。與分類(lèi)區(qū)別：分類(lèi)與聚類(lèi)最大的區(qū)別在于分類(lèi)的目標(biāo)事先已知，聚類(lèi)也被稱(chēng)為無(wú)監(jiān)督機(jī)器學(xué)習(xí)聚類(lèi)手段：傳統(tǒng)聚類(lèi)算法①劃分法②層次方法③基于密度方法

④基于網(wǎng)絡(luò)方法

⑤基于模型方法什么是Kmeans算法？Q1：K是什么？A1：k是聚類(lèi)算法當(dāng)中類(lèi)的個(gè)數(shù)。Summary：Kmeans是用均值算法把數(shù)據(jù)分成K個(gè)類(lèi)的算法！Q2：means是什么？A2：means是均值算法。Kmeans算法詳解（1）步驟一：取得k個(gè)初始初始中心點(diǎn)Kmeans算法詳解（2）MinofthreeduetotheEuclidDistance步驟二：把每個(gè)點(diǎn)劃分進(jìn)相應(yīng)的簇Kmeans算法詳解（3）MinofthreeduetotheEuclidDistance步驟三：重新計(jì)算中心點(diǎn)Kmeans算法詳解（4）步驟四：迭代計(jì)算中心點(diǎn)Kmeans算法詳解（5）步驟五：收斂Kmeans算法詳解（5）步驟五：收斂Kmeans算法流程從數(shù)據(jù)中隨機(jī)抽取k個(gè)點(diǎn)作為初始聚類(lèi)的中心，由這個(gè)中心代表各個(gè)聚類(lèi)計(jì)算數(shù)據(jù)中所有的點(diǎn)到這k個(gè)點(diǎn)的距離，將點(diǎn)歸到離其最近的聚類(lèi)里調(diào)整聚類(lèi)中心，即將聚類(lèi)的中心移動(dòng)到聚類(lèi)的幾何中心（即平均值）處，也就是k-means中的mean的含義重復(fù)第2步直到聚類(lèi)的中心不再移動(dòng)，此時(shí)算法收斂最后kmeans算法時(shí)間、空間復(fù)雜度是：時(shí)間復(fù)雜度：上限為O(tKmn)，下限為Ω（Kmn）其中，t為迭代次數(shù)，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)空間復(fù)雜度：O((m+K)n)，其中，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)決定性因素Input¢roidsSelectedkMaxIterations&ConvergenceMeassures①數(shù)據(jù)的采集和抽象②初始的中心選擇①最大迭代次數(shù)②收斂值①k值的選定①度量距離的手段factors？主要討論初始中心點(diǎn)輸入的數(shù)據(jù)及K值的選擇距離度量我們主要研究的三個(gè)方面因素。初始中心點(diǎn)的劃分討論初始中心點(diǎn)意義何在？下面的例子一目了然吧？初始中心點(diǎn)收斂后你懂的…

如何衡量Kmeans算法的精確度？在進(jìn)一步闡述初始中心點(diǎn)選擇之前，我們應(yīng)該先確定度量kmeans的算法精確度的方法。一種度量聚類(lèi)效果的標(biāo)準(zhǔn)是：SSE(SumofSquareError，誤差平方和)SSE越小表示數(shù)據(jù)點(diǎn)越接近于它們的質(zhì)心，聚類(lèi)效果也就越好。因?yàn)閷?duì)誤差取了平方所以更重視那些遠(yuǎn)離中心的點(diǎn)。一種可以肯定降低SSE的方法是增加簇的個(gè)數(shù)。但這違背了聚類(lèi)的目標(biāo)。因?yàn)榫垲?lèi)是在保持目標(biāo)簇不變的情況下提高聚類(lèi)的質(zhì)量?，F(xiàn)在思路明了了我們首先以縮小SSE為目標(biāo)改進(jìn)算法。改進(jìn)的算法——二分Kmeans算法為了克服k均值算法收斂于局部的問(wèn)題，提出了二分k均值算法。該算法首先將所有的點(diǎn)作為一個(gè)簇，然后將該簇一分為二。之后選擇其中一個(gè)簇繼續(xù)劃分，選擇哪個(gè)簇進(jìn)行劃分取決于對(duì)其劃分是否可以最大程度降低SSE值。偽代碼如下：將所有的點(diǎn)看成一個(gè)簇當(dāng)簇?cái)?shù)目小于k時(shí)對(duì)于每一個(gè)簇

計(jì)算總誤差

在給定的簇上面進(jìn)行K均值聚類(lèi)(K=2)

計(jì)算將該簇一分為二后的總誤差選擇使得誤差最小的那個(gè)簇進(jìn)行劃分操作二分Kmeans算法的效果雙擊此處添加文字內(nèi)容既然是改進(jìn)算法就要體現(xiàn)改進(jìn)算法的優(yōu)越性。為此控制變量，在相同的實(shí)驗(yàn)環(huán)境下，①取相同的k值取。②選取相同的的距離度量標(biāo)準(zhǔn)（歐氏距離）③在相同的數(shù)據(jù)集下進(jìn)行測(cè)試。一組實(shí)驗(yàn)結(jié)果一組不好的初始點(diǎn)產(chǎn)生的Kmeans算法結(jié)果二分kmeans產(chǎn)生的結(jié)果要強(qiáng)調(diào)的是盡管只是這一組實(shí)驗(yàn)不得以得出二分kmeans的優(yōu)越性，但是經(jīng)過(guò)大量實(shí)驗(yàn)得出的結(jié)論卻是在大多數(shù)情況下二分kmeans確實(shí)優(yōu)于樸素的kmeans算法。全局最小值二分kmeans真的能使SSE達(dá)到全局最小值嗎？從前面的講解可以看到二分kmeans算法的思想有點(diǎn)類(lèi)似于貪心思想。但是我們會(huì)發(fā)現(xiàn)貪心的過(guò)程中有不確定的因素比如：二分一個(gè)聚類(lèi)時(shí)選取的兩個(gè)中間點(diǎn)是隨機(jī)的，這會(huì)對(duì)我們的策略造成影響。那么如此一來(lái)二分kmeans算法會(huì)不會(huì)達(dá)到全局最優(yōu)解呢？答案是：會(huì)！盡管你可能驚詫于下面的說(shuō)法，但全局最小值的定義卻是：可能的最好結(jié)果。K值的選擇以及壞點(diǎn)的剔除

討論k值、剔除壞點(diǎn)的意義何在？下面以一個(gè)例子來(lái)說(shuō)明k值的重要性。有一組關(guān)于濕度和溫度的數(shù)據(jù)想把它劃分為冬天和夏天兩部分。（k=2）氣象學(xué)家打了個(gè)盹不小心把（100℃,1000%）和（101℃,1100%）加入了數(shù)據(jù)，并不幸選?。?00℃,1000%）作為其中一個(gè)初始點(diǎn)于是得到兩個(gè)很不靠譜的聚類(lèi)結(jié)果。為什么會(huì)出錯(cuò)？上面的例子當(dāng)中出錯(cuò)的原因很明顯。憑直覺(jué)我們很容易知道不可能有這樣的天氣——它的氣溫是100℃，濕度是1100%。可見(jiàn)壞點(diǎn)對(duì)kmeans的影響之大。另一方面，季節(jié)有春夏秋冬之分，而我們強(qiáng)行的把它們分為夏冬兩個(gè)類(lèi)也是不太合理的。如果分為四個(gè)類(lèi)我們也許可以“中和”掉壞點(diǎn)的影響。究竟哪里錯(cuò)了?。?！帶canopy預(yù)處理的kmeans算法（1）將數(shù)據(jù)集向量化得到一個(gè)list后放入內(nèi)存，選擇兩個(gè)距離閾值：T1和T2。

（2）從list中任取一點(diǎn)P，用低計(jì)算成本方法快速計(jì)算點(diǎn)P與所有Canopy之間的距離（如果當(dāng)前不存在Canopy，則把點(diǎn)P作為一個(gè)Canopy），如果點(diǎn)P與某個(gè)Canopy距離在T1以內(nèi)，則將點(diǎn)P加入到這個(gè)Canopy；

（3）如果點(diǎn)P曾經(jīng)與某個(gè)Canopy的距離在T2以內(nèi)，則需要把點(diǎn)P從list中刪除，這一步是認(rèn)為點(diǎn)P此時(shí)與這個(gè)Canopy已經(jīng)夠近了，因此它不可以再做其它Canopy的中心了；

（4）重復(fù)步驟2、3，直到list為空結(jié)束

帶canopy預(yù)處理的kmeans算法的優(yōu)點(diǎn)canopy可以自動(dòng)幫我我們確定k值。有多少canopy，k值就選取多少。Canopy可以幫我們?nèi)コ皦狞c(diǎn)”。去除離群的canopy帶canopy預(yù)處理的kmeans算法的新挑戰(zhàn)Canopy預(yù)處理這么好，我們以后就用它好了！我看不見(jiàn)得，它雖然解決kmeans當(dāng)中的一些問(wèn)題，但其自身也引進(jìn)了新的問(wèn)題：t1、t2的選取。大數(shù)據(jù)下kmeans算法的并行策略

VS單挑OR群毆？！大數(shù)據(jù)下kmeans算法的并行策略

面對(duì)海量數(shù)據(jù)時(shí)，傳統(tǒng)的聚類(lèi)算法存在著單位時(shí)間內(nèi)處理量小、面對(duì)大量的數(shù)據(jù)時(shí)處理時(shí)間較長(zhǎng)、難以達(dá)到預(yù)期效果的缺陷以上算法都是假設(shè)數(shù)據(jù)都是在內(nèi)存中存儲(chǔ)的，隨著數(shù)據(jù)集的增大，基于內(nèi)存的ＫＭｅａｎｓ就難以適應(yīng)．ＭａｐＲｅｄｕｃｅ是一個(gè)為并行處理大量數(shù)據(jù)而設(shè)計(jì)的編程模型。Kmeans算法都是假設(shè)數(shù)據(jù)都是在內(nèi)存中存儲(chǔ)的，隨著數(shù)據(jù)集的增大，基于內(nèi)存的ＫＭｅａｎｓ就難以適應(yīng)．ＭａｐＲｅｄｕｃｅ是一個(gè)為并行處理大量數(shù)據(jù)而設(shè)計(jì)的編程模型，它將工作劃分為獨(dú)立任務(wù)組成的集合。Map-reduce的過(guò)程簡(jiǎn)介Map函數(shù)設(shè)計(jì)１Ｍａｐ函數(shù)的設(shè)計(jì)ＭａｐＲｅｄｕｃｅ框架中Ｍａｐ函數(shù)的輸入為〈ｋｅｙ，ｖａｌｕｅ〉對(duì)，其中：ｋｅｙ為輸入數(shù)據(jù)記錄的偏移量；ｖａｌｕｅ為當(dāng)前樣本的各維坐標(biāo)值組成的向量．首先計(jì)算該向量到各個(gè)聚簇中心點(diǎn)的距離，然后選擇最小的距離的聚簇作為該樣本所屬的簇，之后輸出〈ｋｅｙ′，ｖａｌｕｅ′〉，其中ｋｅｙ′是距最近的聚簇的標(biāo)識(shí)符，ｖａｌｕｅ′為表示該樣本的向量．Combine函數(shù)設(shè)計(jì)Ｃｏｍｂｉｎｅ函數(shù)的設(shè)計(jì)Ｃｏｍｂｉｎｅ函數(shù)的輸入為〈ｋｅｙ′，ｖａｌｕｅ′〉對(duì)，即Ｍａｐ函數(shù)的輸出．首先，從ｖａｌｕｅ中解析出各個(gè)向量，然后將解析出的向量相加并記錄集合中向量的個(gè)數(shù)．輸出是〈ｋｅｙ１′，ｖａｌｕｅ１′〉對(duì)，其中：ｋｅｙ１′是聚簇的標(biāo)識(shí)符；ｖａｌｕｅ１′是以上集合中所有的向量相加所得的向量及集合中向量的數(shù)目Reduce函數(shù)設(shè)計(jì)Ｒｅｄｕｃｅ函數(shù)的輸入是〈ｋｅｙ２，ｖａｌｕｅ２〉鍵值對(duì)，其中：ｋｅｙ２為聚簇的標(biāo)識(shí)符；ｖａｌｕｅ２為ｍａｐ節(jié)點(diǎn)處理的聚簇中含有的樣本的個(gè)數(shù)及用向量表示的聚簇的中心點(diǎn)ｖｅｃｔｏｒｔｅｍｐ．輸出為〈ｋｅｙ２′，ｖａｌｕｅ２′〉對(duì)，其中：ｋｅｙ′為聚簇的標(biāo)識(shí)符；ｖａｌｕｅ′為新的聚簇中心．Ｒｅｄｕｃｅ函數(shù)首先從函數(shù)的輸入中解析出屬于同一個(gè)聚簇的樣本的個(gè)數(shù)及各個(gè)ｍａｐ節(jié)點(diǎn)傳過(guò)來(lái)的ｖｅｃｔｏｒｔｅｍｐ，然后將個(gè)數(shù)及各個(gè)ｖｅｃｔｏｒｔｅｍｐ相加，之后將所得到的向量除以個(gè)數(shù)得到新的中心點(diǎn)坐標(biāo)。一個(gè)運(yùn)行結(jié)果一個(gè)實(shí)驗(yàn)所有實(shí)驗(yàn)都是在實(shí)驗(yàn)室搭建的Ｈａｄｏｏｐ平臺(tái)上運(yùn)行的．平臺(tái)有５臺(tái)機(jī)器，都是四核ＩｎｔｅｌＣｏｒｅｉ３處理器，４ＧＢ內(nèi)存．Ｈａｄｏｏｐ版本０．２０．２，ｊａｖａ版本１．６．２５．每臺(tái)機(jī)器之間用千兆以太網(wǎng)卡，通過(guò)交換機(jī)連接．實(shí)驗(yàn)所用的數(shù)據(jù)是人工數(shù)據(jù)，維度是４８維．為了測(cè)試算法的性能，實(shí)驗(yàn)中構(gòu)造了分別含有10^4，10^5,10^6，2*10^6條記錄的數(shù)據(jù)來(lái)進(jìn)行測(cè)試．由于ＫＭｅａｎｓ算法中有隨機(jī)初始化中心點(diǎn)的操作，因此對(duì)每一組實(shí)驗(yàn)重復(fù)執(zhí)行２５次，取其平均執(zhí)行時(shí)間作為最終實(shí)驗(yàn)結(jié)果Thebestclassroomintheworldisatthefeetofanelderlyperson.世界上最好的課堂在老人的腳下.Havingachildfallasleepinyourarmsisoneofthemostpeacefulfeelingintheworld.讓一個(gè)孩子在你的臂彎入睡,你會(huì)體會(huì)到世間最安寧的感覺(jué).Beingkindismoreimportantthanbeingright.善良比真理更重要.Youshouldneversaynotoagiftfromachild.永遠(yuǎn)不要拒絕孩子送給你的禮物.Sometimesallapersonneedsisahandtoholdandahearttounderstand.有時(shí)候,一個(gè)人想要的只是一只可握的手和一顆感知的心.Love,nottime,healsallwounds.治愈一切創(chuàng)傷的并非時(shí)間,而是愛(ài).Lifeistough,butI'mtougher.生活是艱苦的,但我應(yīng)更堅(jiān)強(qiáng).勵(lì)志名言請(qǐng)您欣賞Kmeans算法詳解（1）步驟一：取得k個(gè)初始初始中心點(diǎn)Kmeans算法詳解（3）MinofthreeduetotheEuclidDistance步驟三：重新計(jì)算中心點(diǎn)Kmeans算法詳解（4）步驟四：迭代計(jì)算中心點(diǎn)Kmeans算法流程從數(shù)據(jù)中隨機(jī)抽取k個(gè)點(diǎn)作為初始聚類(lèi)的中心