大數據經典算法Kmeans講解第1頁，課件共30頁，創作于2023年2月主要內容：Kmeans實戰聚類算法簡介Kmeans算法詳解Kmeans算法的缺陷及若干改進Kmeans的單機實現與分布式實現策略

第2頁，課件共30頁，創作于2023年2月聚類算法簡介123聚類的目標：將一組向量分成若干組，組內數據是相似的，而組間數據是有較明顯差異。與分類區別：分類與聚類最大的區別在于分類的目標事先已知，聚類也被稱為無監督機器學習聚類手段：傳統聚類算法①劃分法②層次方法③基于密度方法

④基于網絡方法

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

第13頁，課件共30頁，創作于2023年2月如何衡量Kmeans算法的精確度？在進一步闡述初始中心點選擇之前，我們應該先確定度量kmeans的算法精確度的方法。一種度量聚類效果的標準是：SSE(SumofSquareError，誤差平方和)SSE越小表示數據點越接近于它們的質心，聚類效果也就越好。因為對誤差取了平方所以更重視那些遠離中心的點。一種可以肯定降低SSE的方法是增加簇的個數。但這違背了聚類的目標。因為聚類是在保持目標簇不變的情況下提高聚類的質量。現在思路明了了我們首先以縮小SSE為目標改進算法。第14頁，課件共30頁，創作于2023年2月改進的算法——二分Kmeans算法為了克服k均值算法收斂于局部的問題，提出了二分k均值算法。該算法首先將所有的點作為一個簇，然后將該簇一分為二。之后選擇其中一個簇繼續劃分，選擇哪個簇進行劃分取決于對其劃分是否可以最大程度降低SSE值。偽代碼如下：將所有的點看成一個簇當簇數目小于k時對于每一個簇

計算總誤差

在給定的簇上面進行K均值聚類(K=2)

計算將該簇一分為二后的總誤差選擇使得誤差最小的那個簇進行劃分操作第15頁，課件共30頁，創作于2023年2月二分Kmeans算法的效果雙擊此處添加文字內容既然是改進算法就要體現改進算法的優越性。為此控制變量，在相同的實驗環境下，①取相同的k值取。②選取相同的的距離度量標準（歐氏距離）③在相同的數據集下進行測試。第16頁，課件共30頁，創作于2023年2月一組實驗結果一組不好的初始點產生的Kmeans算法結果二分kmeans產生的結果要強調的是盡管只是這一組實驗不得以得出二分kmeans的優越性，但是經過大量實驗得出的結論卻是在大多數情況下二分kmeans確實優于樸素的kmeans算法。第17頁，課件共30頁，創作于2023年2月全局最小值二分kmeans真的能使SSE達到全局最小值嗎？從前面的講解可以看到二分kmeans算法的思想有點類似于貪心思想。但是我們會發現貪心的過程中有不確定的因素比如：二分一個聚類時選取的兩個中間點是隨機的，這會對我們的策略造成影響。那么如此一來二分kmeans算法會不會達到全局最優解呢？答案是：會！盡管你可能驚詫于下面的說法，但全局最小值的定義卻是：可能的最好結果。第18頁，課件共30頁，創作于2023年2月K值的選擇以及壞點的剔除

討論k值、剔除壞點的意義何在？下面以一個例子來說明k值的重要性。第19頁，課件共30頁，創作于2023年2月為什么會出錯？上面的例子當中出錯的原因很明顯。憑直覺我們很容易知道不可能有這樣的天氣——它的氣溫是100℃，濕度是1100%。可見壞點對kmeans的影響之大。另一方面，季節有春夏秋冬之分，而我們強行的把它們分為夏冬兩個類也是不太合理的。如果分為四個類我們也許可以“中和”掉壞點的影響。究竟哪里錯了！！！第20頁，課件共30頁，創作于2023年2月帶canopy預處理的kmeans算法（1）將數據集向量化得到一個list后放入內存，選擇兩個距離閾值：T1和T2。

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

（3）如果點P曾經與某個Canopy的距離在T2以內，則需要把點P從list中刪除，這一步是認為點P此時與這個Canopy已經夠近了，因此它不可以再做其它Canopy的中心了；

（4）重復步驟2、3，直到list為空結束

第21頁，課件共30頁，創作于2023年2月帶canopy預處理的kmeans算法的優點第22頁，課件共30頁，創作于2023年2月帶canopy預處理的kmeans算法的新挑戰Canopy預處理這么好，我們以后就用它好了！我看不見得，它雖然解決kmeans當中的一些問題，但其自身也引進了新的問題：t1、t2的選取。第23頁，課件共30頁，創作于2023年2月大數據下kmeans算法的并行策略

VS單挑OR群毆？！第24頁，課件共30頁，創作于2023年2月大數據下kmeans算法的并行策略

面對海量數據時，傳統的聚類算法存在著單位時間內處理量小、面對大量的數據時處理時間較長、難以達到預期效果的缺陷以上算法都是假設數據都是在內存中存儲的，隨著數據集的增大，基于內存的ＫＭｅａｎｓ就難以適應．ＭａｐＲｅｄｕｃｅ是一個為并行處理大量數據而設計的編程模型。Kmeans算法都是假設數據都是在內存中存儲的，隨著數據集的增大，基于內存的ＫＭｅａｎｓ就難以適應．ＭａｐＲｅｄｕｃｅ是一個為并行處理大量數據而設計的編程模型，它將工作劃分為獨立任務組成的集合。第25頁，課件共30頁，創作于2023年2月Map-reduce的過程簡介第26頁，課件共30頁，創作于2023年2月Map函數設計１Ｍａｐ函數的設計ＭａｐＲｅｄｕｃｅ框架中Ｍａｐ函數的輸入為〈ｋｅｙ，ｖａｌｕｅ〉對，其中：ｋｅｙ為輸入數據記錄的偏移量；ｖａｌｕｅ為當前樣本的各維坐標值組成的向量．首先計算該向量到各個聚簇中心點的距離，然后選擇最小的距離的聚簇作為該樣本所屬的簇，之后輸出〈ｋｅｙ′，ｖａｌｕｅ′〉，其中ｋｅｙ′是距最近的聚簇的標識符，ｖａｌｕｅ′為表示該樣本的向量．第27頁，課件共30頁，創作于2023年2月Combine函數設計Ｃｏｍｂｉｎｅ函數的設計Ｃｏｍｂｉｎｅ函數的輸入為〈ｋｅｙ′，ｖａｌｕｅ′〉對，即Ｍａｐ函數的輸出．首先，從ｖａｌｕｅ中解析出各個向量，然后將解析出的向量相加并記錄集合中向量的個數．輸出是〈ｋｅｙ１′，ｖａｌｕｅ１′〉對，其中：ｋｅｙ１′是聚簇的標識符；ｖａｌｕｅ１′是以上集合中所有的向量相加所得的向量及集合中向量的數目第28頁，課件共30頁，創作于2023年2月Reduce函數設計Ｒｅｄｕｃｅ函數的輸入是〈ｋｅｙ２，ｖａｌｕｅ２〉鍵值對，其中：ｋｅｙ２為聚簇的標識符；ｖａｌｕｅ２為ｍａｐ節點處理的聚簇中含有的樣本的個數及用向量表示的聚簇的中心點ｖｅ