大數(shù)據(jù)經(jīng)典算法Kmeans講解資料

1、The algorithm of Kmeans共三十四頁主要(zhyo)內(nèi)容：Kmeans實戰(zhàn)(shzhn)聚類算法簡介Kmeans算法詳解Kmeans算法的缺陷及若干改進 Kmeans的單機實現(xiàn)與分布式實現(xiàn)策略 共三十四頁聚類算法(sun f)簡介123聚類的目標：將一組向量(xingling)分成若干組，組內(nèi)數(shù)據(jù)是相似的，而組間數(shù)據(jù)是有較明顯差異。與分類區(qū)別：分類與聚類最大的區(qū)別在于分類的目標事先已知，聚類也被稱為無監(jiān)督機器學習聚類手段：傳統(tǒng)聚類算法 劃分法 層次方法 基于密度方法 基于網(wǎng)絡方法 基于模型方法共三十四頁什么(shn me)是Kmeans算法？Q1：K是什么？A1：k是聚類算

2、法(sun f)當中類的個數(shù)。Summary：Kmeans是用均值算法把數(shù)據(jù)分成K個類的算法！ Q2：means是什么？A2：means是均值算法。共三十四頁Kmeans算法(sun f)詳解（1）步驟(bzhu)一：取得k個初始初始中心點共三十四頁Kmeans算法(sun f)詳解（2）Min of threedue to the EuclidDistance步驟(bzhu)二：把每個點劃分進相應的簇共三十四頁Kmeans算法(sun f)詳解（3）Min of threedue to the EuclidDistance步驟(bzhu)三：重新計算中心點共三十四頁Kmeans算法(sun

3、f)詳解（4）步驟(bzhu)四：迭代計算中心點共三十四頁Kmeans算法(sun f)詳解（5）步驟(bzhu)五：收斂共三十四頁Kmeans算法(sun f)流程從數(shù)據(jù)中隨機抽取k個點作為初始聚類的中心(zhngxn)，由這個中心(zhngxn)代表各個聚類計算數(shù)據(jù)中所有的點到這k個點的距離，將點歸到離其最近的聚類里調整聚類中心，即將聚類的中心移動到聚類的幾何中心（即平均值）處，也就是k-means中的mean的含義重復第2步直到聚類的中心不再移動，此時算法收斂最后kmeans算法時間、空間復雜度是：時間復雜度：上限為O(tKmn)，下限為（Kmn）其中，t為迭代次數(shù)，K為簇的數(shù)目，m為記

4、錄數(shù)，n為維數(shù) 空間復雜度：O(m+K)n)，其中，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)共三十四頁決定性因素(yn s)Input & centroidsSelected kMaxIterations & ConvergenceMeassures數(shù)據(jù)的采集和抽象初始(ch sh)的中心選擇最大迭代次數(shù)收斂值 k值的選定 度量距離的手段factors？共三十四頁主要(zhyo)討論初始(ch sh)中心點輸入的數(shù)據(jù)及K值的選擇距離度量我們主要研究的三個方面因素。共三十四頁初始(ch sh)中心點的劃分討論初始中心點意義(yy)何在？下面的例子一目了然吧？初始中心點收斂后你懂的 共三十四頁如何衡量(

5、hng ling)Kmeans算法的精確度？在進一步闡述初始中心點選擇之前，我們應該先確定度量kmeans的算法精確度的方法。一種度量聚類效果的標準是：SSE(Sum of Square Error，誤差平方和)SSE越小表示數(shù)據(jù)點越接近于它們的質心，聚類效果也就越好。因為對誤差取了平方所以更重視那些遠離中心的點。一種可以(ky)肯定降低SSE的方法是增加簇的個數(shù)。但這違背了聚類的目標。因為聚類是在保持目標簇不變的情況下提高聚類的質量?，F(xiàn)在思路明了了我們首先以縮小SSE為目標改進算法。共三十四頁改進(gijn)的算法二分Kmeans算法為了克服k均值算法收斂于局部的問題，提出了二分k均值算法。

6、該算法首先(shuxin)將所有的點作為一個簇，然后將該簇一分為二。之后選擇其中一個簇繼續(xù)劃分，選擇哪個簇進行劃分取決于對其劃分是否可以最大程度降低SSE值。偽代碼如下：將所有的點看成一個簇當簇數(shù)目小于k時對于每一個簇計算總誤差在給定的簇上面進行K均值聚類(K=2)計算將該簇一分為二后的總誤差選擇使得誤差最小的那個簇進行劃分操作共三十四頁二分(r fn)Kmeans算法的效果雙擊此處添加(tin ji)文字內(nèi)容既然是改進算法就要體現(xiàn)改進算法的優(yōu)越性。為此控制變量，在相同的實驗環(huán)境下，取相同的k值取。選取相同的的距離度量標準（歐氏距離）在相同的數(shù)據(jù)集下進行測試。共三十四頁一組實驗(shyn)結果

7、一組不好(b ho)的初始點產(chǎn)生的Kmeans算法結果二分kmeans產(chǎn)生的結果要強調的是盡管只是這一組實驗不得以得出二分kmeans的優(yōu)越性，但是經(jīng)過大量實驗得出的結論卻是在大多數(shù)情況下二分kmeans確實優(yōu)于樸素的kmeans算法。共三十四頁全局(qunj)最小值二分(r fn)kmeans真的能使SSE達到全局最小值嗎？從前面的講解可以看到二分kmeans算法的思想有點類似于貪心思想。但是我們會發(fā)現(xiàn)貪心的過程中有不確定的因素比如：二分一個聚類時選取的兩個中間點是隨機的，這會對我們的策略造成影響。那么如此一來二分kmeans算法會不會達到全局最優(yōu)解呢？答案是：會！盡管你可能驚詫于下面的說法

8、，但全局最小值的定義卻是：可能的最好結果。共三十四頁K值的選擇以及(yj)壞點的剔除 討論k值、剔除壞點的意義(yy)何在？下面以一個例子來說明k值的重要性。有一組關于濕度和溫度的數(shù)據(jù)想把它劃分為冬天和夏天兩部分。（k=2）氣象學家打了個盹不小心把（100,1000%）和（101,1100%）加入了數(shù)據(jù)，并不幸選取（100,1000%）作為其中一個初始點于是得到兩個很不靠譜的聚類結果。共三十四頁為什么會出錯(ch cu)？上面的例子當中出錯的原因很明顯。憑直覺我們很容易知道不可能有這樣的天氣它的氣溫是100，濕度是1100%?？梢妷狞c對kmeans的影響之大。另一方面，季節(jié)有春夏秋冬之分，而我

9、們強行的把它們分為夏冬兩個類也是不太合理的。如果(rgu)分為四個類我們也許可以“中和”掉壞點的影響。究竟哪里錯了！共三十四頁帶canopy預處理的kmeans算法(sun f)（1）將數(shù)據(jù)集向量化得到一個list后放入內(nèi)存，選擇兩個(lin )距離閾值：T1和T2。（2）從list中任取一點P，用低計算成本方法快速計算點P與所有Canopy之間的距離（如果當前不存在Canopy，則把點P作為一個Canopy），如果點P與某個Canopy距離在T1以內(nèi)，則將點P加入到這個Canopy；（3）如果點P曾經(jīng)與某個Canopy的距離在T2以內(nèi)，則需要把點P從list中刪除，這一步是認為點P此時與這個

10、Canopy已經(jīng)夠近了，因此它不可以再做其它Canopy的中心了；（4）重復步驟2、3，直到list為空結束共三十四頁帶canopy預處理的kmeans算法(sun f)的優(yōu)點canopy可以自動幫我我們確定k值。有多少canopy，k值就選取多少。Canopy可以幫我們?nèi)コ皦狞c”。去除離群的canopy共三十四頁帶canopy預處理的kmeans算法(sun f)的新挑戰(zhàn)Canopy預處理這么好，我們(w men)以后就用它好了！我看不見得，它雖然解決kmeans當中的一些問題，但其自身也引進了新的問題：t1、t2的選取。共三十四頁大數(shù)據(jù)下kmeans算法的并行(bngxng)策略 VS單

11、挑OR群毆？！共三十四頁大數(shù)據(jù)下kmeans算法的并行(bngxng)策略 面對海量數(shù)據(jù)時，傳統(tǒng)的聚類算法存在著單位時間內(nèi)處理量小、面對大量的數(shù)據(jù)時處理時間較長、難以達到預期效果的缺陷以上算法都是假設數(shù)據(jù)都是在內(nèi)存(ni cn)中存儲的，隨著數(shù)據(jù)集的增大，基于內(nèi)存的就難以適應是一個為并行處理大量數(shù)據(jù)而設計的編程模型。 Kmeans算法都是假設數(shù)據(jù)都是在內(nèi)存中存儲的，隨著數(shù)據(jù)集的增大，基于內(nèi)存的就難以適應是一個為并行處理大量數(shù)據(jù)而設計的編程模型，它將工作劃分為獨立任務組成的集合。共三十四頁Map-reduce的過程(guchng)簡介共三十四頁Map函數(shù)(hnsh)設計函數(shù)的設計框架中 函數(shù)的輸

12、入為，對，其中：為輸入數(shù)據(jù)記錄的偏移量；為當前樣本的各維坐標值組成的向量首先計算該向量到各個聚簇中心點的距離，然后選擇最小的距離的聚簇作為該樣本所屬的簇，之后(zhhu)輸出，其中是距最近的聚簇的標識符，為表示該樣本的向量共三十四頁Combine函數(shù)(hnsh)設計函數(shù)的設計函數(shù)的輸入為，對，即函數(shù)的輸出首先，從中解析出各個(gg)向量，然后將解析出的向量相加并記錄集合中向量的個數(shù)輸出是，對，其中：是聚簇的標識符；是以上集合中所有的向量相加所得的向量及集合中向量的數(shù)目共三十四頁Reduce函數(shù)(hnsh)設計函數(shù)的輸入是，鍵值對，其中：為聚簇的標識符；為節(jié)點處理的聚簇中含有的樣本的個數(shù)及用向量

13、表示的聚簇的中心點輸出為，對，其中：為聚簇的標識符；為新的聚簇中心函數(shù)首先從函數(shù)的輸入中解析出屬于同一個聚簇的樣本的個數(shù)及各個節(jié)點傳過來的，然后(rnhu)將個數(shù)及各個相加，之后將所得到的向量除以個數(shù)得到新的中心點坐標。共三十四頁一個運行(ynxng)結果共三十四頁一個(y )實驗所有實驗都是在實驗室搭建(d jin)的平臺上運行的平臺有 臺機器，都是四核處理器，內(nèi)存版本，版本每臺機器之間用千兆以太網(wǎng)卡，通過交換機連接實驗所用的數(shù)據(jù)是人工數(shù)據(jù)，維度是維為了測試算法的性能，實驗中構造了分別含有104，105,106，2*106 條記錄的數(shù)據(jù)來進行測試由于算法中有隨機初始化中心點的操作，因此對每一組實驗重復執(zhí)行次，取其平均執(zhí)行時間作為最終實驗結果共三十四頁算法(sun f)改進后的實效可以看出：基于的算法的運行效率(xio l)要遠遠高于傳統(tǒng)的算法共三十四頁Q&A謝謝(xi xie)！共三十四頁內(nèi)容摘要The algorithm of Kmeans。輸入的數(shù)據(jù)及K值的選擇。在進一步闡述初始(ch sh)中心點選擇之前，我們應該先確定度量kmeans的算法精確度的方法。一種可以肯定降低SSE的方法是增加簇的個數(shù)