簡(jiǎn)單之美 | 聚類算法：K-means http://shiyanjun.cn/archives/539.html
上圖表示的聚類過(guò)程，簡(jiǎn)述如下：
給定一個(gè)數(shù)據(jù)集，包含多個(gè)數(shù)據(jù)點(diǎn)；
隨機(jī)選擇兩個(gè)質(zhì)心；
計(jì)算數(shù)據(jù)集中數(shù)據(jù)點(diǎn)分別屬于哪一個(gè)質(zhì)心所在的組中，將數(shù)據(jù)集中所有數(shù)據(jù)點(diǎn)聚成2個(gè)組；
根據(jù)上一步計(jì)算得到的2組數(shù)據(jù)點(diǎn)沮尿，分別重新計(jì)算出一個(gè)新的質(zhì)心；
重復(fù)步驟3伤极，再進(jìn)行一次聚類過(guò)程蛹找，得到2組數(shù)據(jù)點(diǎn)；
再次計(jì)算新的質(zhì)心哨坪，該次計(jì)算得到的質(zhì)心與上一次計(jì)算得到的質(zhì)心的距離變化很杏辜病（滿足指定閾值，或收斂）当编，則結(jié)果符合期望届慈，停止聚類過(guò)程。
k個(gè)初始類聚類質(zhì)心（Centroid）的選取對(duì)聚類結(jié)果具有較大的影響忿偷，因?yàn)樵谠撍惴ǖ谝徊街惺请S機(jī)的選取任意k個(gè)對(duì)象作為初始聚類的質(zhì)心金顿，初始地代表一個(gè)聚類結(jié)果，當(dāng)然這個(gè)結(jié)果一般情況不是合理的鲤桥，只是隨便地將數(shù)據(jù)集進(jìn)行了一次隨機(jī)的劃分揍拆，具體進(jìn)行修正這個(gè)質(zhì)心還需要進(jìn)行多輪的計(jì)算，來(lái)一步步逼近我們期望的聚類結(jié)果：具有相似性的對(duì)象聚集到一個(gè)組中茶凳，它們都具有共同的一個(gè)質(zhì)心嫂拴。
K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評(píng)價(jià)指標(biāo)贮喧，即認(rèn)為兩個(gè)對(duì)象的距離越近筒狠，其相似度就越大。該算法認(rèn)為簇是由距離靠近的對(duì)象組成的箱沦，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)辩恼。對(duì)于聚類問(wèn)題，我們事先并不知道給定的一個(gè)訓(xùn)練數(shù)據(jù)集到底具有哪些類別（即沒(méi)有指定類標(biāo)簽），而是根據(jù)需要設(shè)置指定個(gè)數(shù)類標(biāo)簽的數(shù)量（但不知道具體的類標(biāo)簽是什么）灶伊，然后通過(guò)K-means算法將具有相同特征疆前，或者基于一定規(guī)則認(rèn)為某一些對(duì)象相似，與其它一些組明顯的不同的數(shù)據(jù)聚集到一起谁帕，自然形成分組峡继。之后，我們可以根據(jù)每一組的數(shù)據(jù)的特點(diǎn)匈挖，給定一個(gè)合適的類標(biāo)簽（當(dāng)然，可能給出類標(biāo)簽對(duì)實(shí)際應(yīng)用沒(méi)有實(shí)際意義康愤，例如可能我們就想看一下聚類得到的各個(gè)數(shù)據(jù)集的相似性）儡循。首先說(shuō)明一個(gè)概念：質(zhì)心（Centroid）。質(zhì)心可以認(rèn)為就是一個(gè)樣本點(diǎn)征冷，或者可以認(rèn)為是數(shù)據(jù)集中的一個(gè)數(shù)據(jù)點(diǎn)P择膝，它是具有相似性的一組數(shù)據(jù)的中心，即該組中每個(gè)數(shù)據(jù)點(diǎn)到P的距離都比到其他質(zhì)心的距離近（與其他質(zhì)心相似性比較低）检激。k個(gè)初始類聚類質(zhì)心（Centroid）的選取對(duì)聚類結(jié)果具有較大的影響肴捉，因?yàn)樵谠撍惴ǖ谝徊街惺请S機(jī)的選取任意k個(gè)對(duì)象作為初始聚類的質(zhì)心，初始地代表一個(gè)聚類結(jié)果叔收，當(dāng)然這個(gè)結(jié)果一般情況不是合理的齿穗，只是隨便地將數(shù)據(jù)集進(jìn)行了一次隨機(jī)的劃分，具體進(jìn)行修正這個(gè)質(zhì)心還需要進(jìn)行多輪的計(jì)算饺律，來(lái)一步步逼近我們期望的聚類結(jié)果：具有相似性的對(duì)象聚集到一個(gè)組中窃页，它們都具有共同的一個(gè)質(zhì)心。另外复濒，因?yàn)槌跏假|(zhì)心選擇的隨機(jī)性脖卖，可能未必使最終的結(jié)果達(dá)到我們的期望，所以我們可以多次迭代巧颈，每次迭代都重新隨機(jī)得到初始質(zhì)心畦木，直到最終的聚類結(jié)果能夠滿足我們的期望為止。下面砸泛，我們描述一下K-means算法的過(guò)程：
首先輸入k的值十籍，即我們希望將數(shù)據(jù)集D = {P1, P2, …, Pn}經(jīng)過(guò)聚類得到k個(gè)分類（分組）。
從數(shù)據(jù)集D中隨機(jī)選擇k個(gè)數(shù)據(jù)點(diǎn)作為質(zhì)心晾嘶，質(zhì)心集合定義為：Centroid = {Cp1, Cp2, …, Cpk}妓雾，排除質(zhì)心以后數(shù)據(jù)集O={O1, O2, …, Om}。
對(duì)集合O中每一個(gè)數(shù)據(jù)點(diǎn)Oi垒迂，計(jì)算Oi與Cpj(j=1, 2, …,k)的距離械姻，得到一組距離Si={si1, si2, …, sik}，計(jì)算Si中距離最小值，則該該數(shù)據(jù)點(diǎn)Oi就屬于該最小距離值對(duì)應(yīng)的質(zhì)心楷拳。
每個(gè)數(shù)據(jù)點(diǎn)Oi都已經(jīng)屬于其中一個(gè)質(zhì)心绣夺，然后根據(jù)每個(gè)質(zhì)心所包含的數(shù)據(jù)點(diǎn)的集合，重新計(jì)算得到一個(gè)新的質(zhì)心欢揖。
如果新計(jì)算的質(zhì)心和原來(lái)的質(zhì)心之間的距離達(dá)到某一個(gè)設(shè)置的閾值（表示重新計(jì)算的質(zhì)心的位置變化不大陶耍，趨于穩(wěn)定，或者說(shuō)收斂）她混，可以認(rèn)為我們進(jìn)行的聚類已經(jīng)達(dá)到期望的結(jié)果烈钞，算法終止。
如果新質(zhì)心和原來(lái)之心距離變化很大坤按，需要迭代2~5步驟毯欣。
上圖表示的聚類過(guò)程砚作，簡(jiǎn)述如下：
給定一個(gè)數(shù)據(jù)集，包含多個(gè)數(shù)據(jù)點(diǎn)嘹锁；
隨機(jī)選擇兩個(gè)質(zhì)心葫录；
計(jì)算數(shù)據(jù)集中數(shù)據(jù)點(diǎn)分別屬于哪一個(gè)質(zhì)心所在的組中，將數(shù)據(jù)集中所有數(shù)據(jù)點(diǎn)聚成2個(gè)組兼耀；
根據(jù)上一步計(jì)算得到的2組數(shù)據(jù)點(diǎn)压昼，分別重新計(jì)算出一個(gè)新的質(zhì)心；
重復(fù)步驟3瘤运，再進(jìn)行一次聚類過(guò)程窍霞，得到2組數(shù)據(jù)點(diǎn)；
再次計(jì)算新的質(zhì)心拯坟，該次計(jì)算得到的質(zhì)心與上一次計(jì)算得到的質(zhì)心的距離變化很械稹（滿足指定閾值，或收斂）郁季，則結(jié)果符合期望冷溃，停止聚類過(guò)程。
K-means算法的優(yōu)點(diǎn)
算法框架清晰梦裂，簡(jiǎn)單似枕，容易理解。
本算法確定的k個(gè)劃分到達(dá)平方誤差最小年柠。當(dāng)聚類是密集的凿歼，且類與類之間區(qū)別明顯時(shí)，效果較好。
對(duì)于處理大數(shù)據(jù)集答憔，這個(gè)算法是相對(duì)可伸縮和高效的味赃，計(jì)算的復(fù)雜度為O(NKt)，其中N是數(shù)據(jù)對(duì)象的數(shù)目虐拓，t是迭代的次數(shù)心俗。一般來(lái)說(shuō)，K<<N蓉驹，t<<N 城榛。
K-means算法的缺點(diǎn)
K-means算法中k是事先給定的，這個(gè)k值的選定是非常難以估計(jì)的态兴。很多時(shí)候吠谢，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適。這也是K-means算法的一個(gè)不足诗茎。有的算法是通過(guò)類的自動(dòng)合并和分裂，得到較為合理的類型數(shù)目k献汗，例如ISODATA算法敢订。關(guān)于K-means算法中聚類數(shù)目k值的確定，有些文獻(xiàn)中罢吃，是根據(jù)方差分析理論楚午，應(yīng)用混合F統(tǒng)計(jì)量來(lái)確定最佳分類數(shù)，并應(yīng)用了模糊劃分熵來(lái)驗(yàn)證最佳分類數(shù)的正確性尿招，它使用了一種結(jié)合全協(xié)方差矩陣的RPCL算法矾柜，并逐步刪除那些只包含少量訓(xùn)練數(shù)據(jù)的類，這是一種稱為次勝者受罰的競(jìng)爭(zhēng)學(xué)習(xí)規(guī)則就谜，來(lái)自動(dòng)決定類的適當(dāng)數(shù)目怪蔑。它的思想是：對(duì)每個(gè)輸入而言，不僅競(jìng)爭(zhēng)獲勝單元的權(quán)值被修正以適應(yīng)輸入值丧荐，而且對(duì)次勝單元采用懲罰的方法使之遠(yuǎn)離輸入值缆瓣。
在K-means算法中，首先需要根據(jù)初始聚類中心來(lái)確定一個(gè)初始劃分虹统，然后對(duì)初始劃分進(jìn)行優(yōu)化弓坞。這個(gè)初始聚類中心的選擇對(duì)聚類結(jié)果有較大的影響车荔，一旦初始值選擇的不好，可能無(wú)法得到有效的聚類結(jié)果忧便，這也成為K-means算法的一個(gè)主要問(wèn)題。對(duì)于該問(wèn)題的解決，許多算法采用遺傳算法（GA）呼奢，以內(nèi)部聚類準(zhǔn)則作為評(píng)價(jià)指標(biāo)。
從K-means算法框架可以看出握础，該算法需要不斷地進(jìn)行樣本分類調(diào)整，不斷地計(jì)算調(diào)整后的新的聚類中心禀综，因此當(dāng)數(shù)據(jù)量非常大時(shí)，算法的時(shí)間開(kāi)銷是非常大的定枷。所以需要對(duì)算法的時(shí)間復(fù)雜度進(jìn)行分析孤澎、改進(jìn)，提高算法應(yīng)用范圍欠窒，例如覆旭，可以從該算法的時(shí)間復(fù)雜度進(jìn)行分析考慮，通過(guò)一定的相似性準(zhǔn)則來(lái)去掉聚類中心的侯選集岖妄。在有些文獻(xiàn)中型将，使用的K-means算法是對(duì)樣本數(shù)據(jù)進(jìn)行聚類，無(wú)論是初始點(diǎn)的選擇還是一次迭代完成時(shí)對(duì)數(shù)據(jù)的調(diào)整荐虐，都是建立在隨機(jī)選取的樣本數(shù)據(jù)的基礎(chǔ)之上七兜，這樣可以提高算法的收斂速度。
K-means算法對(duì)異常數(shù)據(jù)很敏感福扬。在計(jì)算質(zhì)心的過(guò)程中腕铸，如果某個(gè)數(shù)據(jù)很異常，在計(jì)算均值的時(shí)候铛碑，會(huì)對(duì)結(jié)果影響非常大
狠裹。
參考鏈接
http://www.cnblogs.com/zhangchaoyang/archive/2011/09/19/2181869.html
http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html
http://baike.baidu.com/view/3066906.htm
KMeans聚類算法Hadoop實(shí)現(xiàn) - liushaobo的專欄 - 博客頻道 - CSDN.NET http://blog.csdn.net/jdplus/article/details/23960127
//計(jì)算相鄰兩次迭代結(jié)果的聚類中心的距離，判斷是否滿足終止條件
如果不滿足終止條件亚茬，則用本次迭代的聚類中心更新聚類中心
//根據(jù)最終得到的聚類中心對(duì)數(shù)據(jù)集進(jìn)行聚類
Cluster(args);
