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

1、Kmeans實(shí)戰(zhàn)實(shí)戰(zhàn)聚類算法簡介聚類算法簡介Kmeans算法詳解算法詳解Kmeans算法的缺陷及若干改進(jìn)算法的缺陷及若干改進(jìn) Kmeans的單機(jī)實(shí)現(xiàn)與分布式實(shí)現(xiàn)策略的單機(jī)實(shí)現(xiàn)與分布式實(shí)現(xiàn)策略 123聚類的目標(biāo)：聚類的目標(biāo)：將一組向量分成若干組，組內(nèi)數(shù)據(jù)是相似的，將一組向量分成若干組，組內(nèi)數(shù)據(jù)是相似的，而組間數(shù)據(jù)是有較明顯差異而組間數(shù)據(jù)是有較明顯差異。與分類區(qū)別：與分類區(qū)別：分類與聚類最大的區(qū)別在于分類的目標(biāo)事先已分類與聚類最大的區(qū)別在于分類的目標(biāo)事先已知，聚類也被稱為無監(jiān)督機(jī)器學(xué)習(xí)知，聚類也被稱為無監(jiān)督機(jī)器學(xué)習(xí)聚類手段：傳統(tǒng)聚類算法聚類手段：傳統(tǒng)聚類算法 劃分法劃分法 層次方法層次方法 基于密

2、度基于密度方法方法 基于網(wǎng)絡(luò)方法基于網(wǎng)絡(luò)方法 基于模型方法基于模型方法Q1：K是什么？是什么？A1：k是聚類算法當(dāng)中類的個數(shù)。是聚類算法當(dāng)中類的個數(shù)。Summary：Kmeans是用均值算法把數(shù)是用均值算法把數(shù)據(jù)分成據(jù)分成K個類的算法！個類的算法！ Q2：means是什么？是什么？A2：means是均值算法。是均值算法。步驟一：取得步驟一：取得k個初始初始中心點(diǎn)個初始初始中心點(diǎn)Min of threedue to the EuclidDistance步驟二：把每個點(diǎn)劃分進(jìn)相應(yīng)的簇步驟二：把每個點(diǎn)劃分進(jìn)相應(yīng)的簇Min of threedue to the EuclidDistance步驟三：重新

3、計算中心點(diǎn)步驟三：重新計算中心點(diǎn)步驟四：迭代計算中心點(diǎn)步驟四：迭代計算中心點(diǎn)步驟五：收斂步驟五：收斂從數(shù)據(jù)中隨機(jī)抽取從數(shù)據(jù)中隨機(jī)抽取k個點(diǎn)作為初始聚類的個點(diǎn)作為初始聚類的中心，由這個中心代表各個聚類中心，由這個中心代表各個聚類計算數(shù)據(jù)中所有的點(diǎn)到這計算數(shù)據(jù)中所有的點(diǎn)到這k個點(diǎn)的距離，個點(diǎn)的距離，將點(diǎn)歸到離其最近的聚類里將點(diǎn)歸到離其最近的聚類里調(diào)整聚類中心，即將聚類的中心移動到調(diào)整聚類中心，即將聚類的中心移動到聚類的幾何中心（即平均值）處，也就是聚類的幾何中心（即平均值）處，也就是k-means中的中的mean的含義的含義重復(fù)第重復(fù)第2步直到聚類的中心不再移動，此步直到聚類的中心不再移動，此時算

4、法收斂時算法收斂最后最后kmeans算法時間、空間復(fù)雜度是：算法時間、空間復(fù)雜度是：時間復(fù)雜度：上限為時間復(fù)雜度：上限為O(tKmn)，下限為，下限為（Kmn）其中，）其中，t為迭代次數(shù)，為迭代次數(shù)，K為簇的數(shù)為簇的數(shù)目，目，m為記錄數(shù)，為記錄數(shù)，n為維數(shù)為維數(shù) 空間復(fù)雜度：空間復(fù)雜度：O(m+K)n)，其中，其中，K為簇為簇的數(shù)目，的數(shù)目，m為記錄數(shù)，為記錄數(shù)，n為維數(shù)為維數(shù)Input & centroidsSelected kMaxIterations & ConvergenceMeassures數(shù)據(jù)的采集和抽象初始的中心選擇最大迭代次數(shù)收斂值 k值的選定 度量距離的手段f

5、actors？初始中初始中心點(diǎn)心點(diǎn)輸入的數(shù)輸入的數(shù)據(jù)及據(jù)及K值值的選擇的選擇距離度距離度量量我們主要研究的三個方面因素。我們主要研究的三個方面因素。討論初始中心點(diǎn)意義何在？下面的例子一目了然吧？討論初始中心點(diǎn)意義何在？下面的例子一目了然吧？初始中心點(diǎn)初始中心點(diǎn)收斂后收斂后你你懂懂的的 在進(jìn)一步闡述初始中心點(diǎn)選擇在進(jìn)一步闡述初始中心點(diǎn)選擇之前，我們應(yīng)該先確定度量之前，我們應(yīng)該先確定度量kmeans的算法精確度的方法。的算法精確度的方法。一種度量聚類效果的標(biāo)準(zhǔn)是：一種度量聚類效果的標(biāo)準(zhǔn)是：SSE(Sum of Square Error，誤差平方和誤差平方和)SSE越小表示數(shù)據(jù)點(diǎn)越接近于越小表示數(shù)據(jù)

6、點(diǎn)越接近于它們的質(zhì)心，聚類效果也就越它們的質(zhì)心，聚類效果也就越好。因為對誤差取了平方所以好。因為對誤差取了平方所以更重視那些遠(yuǎn)離中心的點(diǎn)。更重視那些遠(yuǎn)離中心的點(diǎn)。一種可以肯定降低一種可以肯定降低SSE的方法的方法是增加簇的個數(shù)。但這違背了是增加簇的個數(shù)。但這違背了聚類的目標(biāo)。因為聚類是在保聚類的目標(biāo)。因為聚類是在保持目標(biāo)簇不變的情況下提高聚持目標(biāo)簇不變的情況下提高聚類的質(zhì)量。類的質(zhì)量?，F(xiàn)在思路明了了我們首先以縮現(xiàn)在思路明了了我們首先以縮小小SSE為目標(biāo)改進(jìn)算法。為目標(biāo)改進(jìn)算法。為了克服為了克服k均值算法收斂于局部的問題，提出了二分均值算法收斂于局部的問題，提出了二分k均值算法。該算法首先將所有

7、的點(diǎn)作為一個簇，然后均值算法。該算法首先將所有的點(diǎn)作為一個簇，然后將該簇一分為二。之后選擇其中一個簇繼續(xù)劃分，選將該簇一分為二。之后選擇其中一個簇繼續(xù)劃分，選擇哪個簇進(jìn)行劃分取決于對其劃分是否可以最大程度擇哪個簇進(jìn)行劃分取決于對其劃分是否可以最大程度降低降低SSE值。值。偽代碼如下：偽代碼如下：將所有的點(diǎn)看成一個簇將所有的點(diǎn)看成一個簇當(dāng)簇數(shù)目小于當(dāng)簇數(shù)目小于k時時對于每一個簇對于每一個簇計算總誤差計算總誤差在給定的簇上面進(jìn)行在給定的簇上面進(jìn)行K均值聚類均值聚類(K=2)計算將該簇一分為二后的總誤差計算將該簇一分為二后的總誤差選擇使得誤差最小的那個簇進(jìn)行劃分操作選擇使得誤差最小的那個簇進(jìn)行劃分操

8、作既然是改進(jìn)算法就要體現(xiàn)改既然是改進(jìn)算法就要體現(xiàn)改進(jìn)算法的優(yōu)越性。為此控制進(jìn)算法的優(yōu)越性。為此控制變量，在相同的實(shí)驗環(huán)境下，變量，在相同的實(shí)驗環(huán)境下，取相同的取相同的k值取。值取。選取相同的的距離度量標(biāo)選取相同的的距離度量標(biāo)準(zhǔn)（歐氏距離）準(zhǔn)（歐氏距離）在相同的數(shù)據(jù)集下進(jìn)行測在相同的數(shù)據(jù)集下進(jìn)行測試。試。一組不好的初始點(diǎn)產(chǎn)生的一組不好的初始點(diǎn)產(chǎn)生的Kmeans算法結(jié)果算法結(jié)果二分二分kmeans產(chǎn)生的結(jié)果產(chǎn)生的結(jié)果要強(qiáng)調(diào)的是盡管只是這一組實(shí)驗不得以得出二分要強(qiáng)調(diào)的是盡管只是這一組實(shí)驗不得以得出二分kmeans的的優(yōu)越性，優(yōu)越性，但是但是經(jīng)過大量實(shí)驗得出的結(jié)論卻是在大多數(shù)情況下經(jīng)過大量實(shí)驗得出的結(jié)

9、論卻是在大多數(shù)情況下二分二分kmeans確實(shí)優(yōu)于樸素的確實(shí)優(yōu)于樸素的kmeans算法。算法。二分二分kmeans真真的能使的能使SSE達(dá)達(dá)到全局最小值到全局最小值嗎？嗎？從前面的講解可以看到二分從前面的講解可以看到二分kmeans算法的思想有點(diǎn)類算法的思想有點(diǎn)類似于貪心思想。但是我們會似于貪心思想。但是我們會發(fā)現(xiàn)貪心的過程中有不確定發(fā)現(xiàn)貪心的過程中有不確定的因素比如：二分一個聚類的因素比如：二分一個聚類時選取的兩個中間點(diǎn)是隨機(jī)時選取的兩個中間點(diǎn)是隨機(jī)的，這會對我們的策略造成的，這會對我們的策略造成影響。那么如此一來二分影響。那么如此一來二分kmeans算法會不會達(dá)到全算法會不會達(dá)到全局最優(yōu)解呢

10、？答案是：會！局最優(yōu)解呢？答案是：會！盡管你可能驚詫于下面的說盡管你可能驚詫于下面的說法，但全局最小值的定義卻法，但全局最小值的定義卻是：是：可能可能的最好結(jié)果。的最好結(jié)果。 討論討論k值、剔除壞點(diǎn)的意義何在？下面以一個例值、剔除壞點(diǎn)的意義何在？下面以一個例子來說明子來說明k值的重要性。值的重要性。上面的例子當(dāng)中出錯的原因上面的例子當(dāng)中出錯的原因很明顯。憑直覺我們很容易很明顯。憑直覺我們很容易知道不可能有這樣的天氣知道不可能有這樣的天氣它的氣溫是它的氣溫是100，濕度，濕度是是1100%?？梢妷狞c(diǎn)對?？梢妷狞c(diǎn)對kmeans的影響之大。另一的影響之大。另一方面，季節(jié)有春夏秋冬之分，方面，季節(jié)有春

11、夏秋冬之分，而我們強(qiáng)行的把它們分為夏而我們強(qiáng)行的把它們分為夏冬兩個類也是不太合理的。冬兩個類也是不太合理的。如果分為四個類我們也許可如果分為四個類我們也許可以以“中和中和”掉壞點(diǎn)的影響。掉壞點(diǎn)的影響。究竟哪里錯究竟哪里錯了！了！（1）將數(shù)據(jù)集向量化得到一個）將數(shù)據(jù)集向量化得到一個list后放后放入內(nèi)存，選擇兩個距離閾值：入內(nèi)存，選擇兩個距離閾值：T1和和T2。 （2）從）從list中任取一點(diǎn)中任取一點(diǎn)P，用低計算成，用低計算成本方法快速計算點(diǎn)本方法快速計算點(diǎn)P與所有與所有Canopy之之間的距離（如果當(dāng)前不存在間的距離（如果當(dāng)前不存在Canopy，則把點(diǎn)則把點(diǎn)P作為一個作為一個Canopy），

12、如果點(diǎn)），如果點(diǎn)P與某個與某個Canopy距離在距離在T1以內(nèi)，則將點(diǎn)以內(nèi)，則將點(diǎn)P加入到這個加入到這個Canopy； （3）如果點(diǎn)）如果點(diǎn)P曾經(jīng)與某個曾經(jīng)與某個Canopy的距的距離在離在T2以內(nèi)，則需要把點(diǎn)以內(nèi)，則需要把點(diǎn)P從從list中刪中刪除，這一步是認(rèn)為點(diǎn)除，這一步是認(rèn)為點(diǎn)P此時與這個此時與這個Canopy已經(jīng)夠近了，因此它不可以再已經(jīng)夠近了，因此它不可以再做其它做其它Canopy的中心了；的中心了； （4）重復(fù)步驟）重復(fù)步驟2、3，直到，直到list為空結(jié)為空結(jié)束束 Canopy預(yù)處理這么好，預(yù)處理這么好，我們以后就用它好了！我們以后就用它好了！我看不見得，它雖然解決我看不見得，它

13、雖然解決kmeans當(dāng)中的一些問題，當(dāng)中的一些問題，但其自身也引進(jìn)了新的問題：但其自身也引進(jìn)了新的問題：t1、t2的選取。的選取。 VS單挑單挑OR群毆群毆？！？！ 面對海量數(shù)據(jù)時，傳統(tǒng)的聚類算法存在著單位時面對海量數(shù)據(jù)時，傳統(tǒng)的聚類算法存在著單位時間內(nèi)處理量小、面對大量的數(shù)據(jù)時處理時間較長、間內(nèi)處理量小、面對大量的數(shù)據(jù)時處理時間較長、難以達(dá)到預(yù)期效果的缺陷以上算法都是假設(shè)數(shù)據(jù)都難以達(dá)到預(yù)期效果的缺陷以上算法都是假設(shè)數(shù)據(jù)都是在內(nèi)存中存儲的，是在內(nèi)存中存儲的，隨著數(shù)據(jù)集的增大，基于內(nèi)存隨著數(shù)據(jù)集的增大，基于內(nèi)存的就難以適應(yīng)的就難以適應(yīng)是一個為并行處理大量數(shù)據(jù)而設(shè)計的編程模型。是一個為并行處理大量

14、數(shù)據(jù)而設(shè)計的編程模型。 Kmeans算法都是假設(shè)數(shù)據(jù)都是在內(nèi)存中存儲的，算法都是假設(shè)數(shù)據(jù)都是在內(nèi)存中存儲的，隨著數(shù)據(jù)集的增大，基于內(nèi)存的就難隨著數(shù)據(jù)集的增大，基于內(nèi)存的就難以適應(yīng)是一個為并行處理大以適應(yīng)是一個為并行處理大量數(shù)據(jù)而設(shè)計的編程模型，它將工作劃分為獨(dú)立任量數(shù)據(jù)而設(shè)計的編程模型，它將工作劃分為獨(dú)立任務(wù)組成的集合。務(wù)組成的集合。函數(shù)的設(shè)計函數(shù)的設(shè)計框架中框架中 函數(shù)函數(shù)的輸入為的輸入為，對，其對，其中：為輸入數(shù)據(jù)記錄的偏移量；中：為輸入數(shù)據(jù)記錄的偏移量；為當(dāng)前樣本的各維坐標(biāo)值組成的為當(dāng)前樣本的各維坐標(biāo)值組成的向量向量首先計算該向量到各個聚簇中心點(diǎn)的距離，首先計算該向量到各個聚簇中心點(diǎn)的距

15、離，然后選擇最小的距離的聚簇作為該樣本所然后選擇最小的距離的聚簇作為該樣本所屬的簇，之后輸出屬的簇，之后輸出，其中，其中是距最近的聚簇的標(biāo)是距最近的聚簇的標(biāo)識符，識符，為表示該樣本的向為表示該樣本的向量量函數(shù)的設(shè)計函數(shù)的設(shè)計函數(shù)的輸入為函數(shù)的輸入為，對，即函數(shù)的輸出首先，對，即函數(shù)的輸出首先，從中解析出各個向量，然后從中解析出各個向量，然后將解析出的向量相加并記錄集合中向量將解析出的向量相加并記錄集合中向量的個數(shù)輸出是的個數(shù)輸出是，對，其中：對，其中：是聚簇的標(biāo)是聚簇的標(biāo)識符；識符；是以上集合中所有是以上集合中所有的向量相加所得的向量及集合中向量的的向量相加所得的向量及集合中向量的數(shù)目數(shù)目函數(shù)

16、的輸入是函數(shù)的輸入是，鍵值對，其中：為聚簇的鍵值對，其中：為聚簇的標(biāo)識符；為節(jié)點(diǎn)處理的聚標(biāo)識符；為節(jié)點(diǎn)處理的聚簇中含有的樣本的個數(shù)及用向量表示的聚簇的簇中含有的樣本的個數(shù)及用向量表示的聚簇的中心點(diǎn)輸出為中心點(diǎn)輸出為，對，其中：對，其中：為為聚簇的標(biāo)識符；聚簇的標(biāo)識符；為新的聚簇中為新的聚簇中心函數(shù)首先從函數(shù)的輸入中解心函數(shù)首先從函數(shù)的輸入中解析出屬于同一個聚簇的樣本的個數(shù)及各個析出屬于同一個聚簇的樣本的個數(shù)及各個節(jié)點(diǎn)傳過來的，然后節(jié)點(diǎn)傳過來的，然后將個數(shù)及各個相加，之將個數(shù)及各個相加，之后將所得到的向量除以個數(shù)得到新的中心點(diǎn)坐后將所得到的向量除以個數(shù)得到新的中心點(diǎn)坐標(biāo)。標(biāo)。所有實(shí)驗都是在實(shí)驗室搭建的平臺所有實(shí)驗都是在實(shí)驗室搭建的平臺上運(yùn)行的平臺有上運(yùn)行的平臺有 臺機(jī)器，都是四核臺機(jī)器，都是四核處理器，內(nèi)存處理器，內(nèi)存版本，版本，版本每臺機(jī)器之間用千版本每臺機(jī)器之間用千兆以太網(wǎng)兆以太網(wǎng)卡，通過交換機(jī)連接實(shí)驗所用的數(shù)據(jù)是人工數(shù)