聚類中K-means算法綜述講解

1、滋血好抽火孳攻讀碩士學(xué)位研究生試卷（作業(yè)）封面（2015至2016學(xué)年度第一學(xué)期）題目論文選讀科目聚類分析中K-means算法綜述姓名王苑茹專業(yè)計(jì)算機(jī)技術(shù)入學(xué)年月2015年8月簡(jiǎn)短評(píng)語成績：授課教師簽字：聚類分析中K-means算法綜述摘要：聚類分析是數(shù)據(jù)挖掘中一個(gè)極其重要的研究方向,是一個(gè)將數(shù)據(jù)劃分成簇的方法或手段。聚類分析可廣泛利用在商務(wù)智能，Wet®索，生物學(xué)以及圖像模式識(shí)別等眾多方面。本文主要敘述聚類分析中的K-means聚類算法，總結(jié)了K-means聚類算法的研究現(xiàn)狀，并針對(duì)K-means算法的相關(guān)改進(jìn)做了綜述。關(guān)鍵詞：K-means聚類算法；數(shù)據(jù)子集；聚類中心；相似性度量

2、和距離矩陣OverviewofK-meansalgorithminclusteringanalysisAbstract：Clusteringismajorfieldindataminingwhichalsoisanimportantmethodofdatapartitionorgrouping.Clusteringnowhasbeenappliedintovariouswaysinbusinessintelligence,Webclassification,biology,marketandsoon.Inthispaper,weintroducethespatialclusteringrule

3、s,Atthesametime,theclassicalK-meansalgorithmisdescribe,AndsomerelatedimprovementstoK-meansalgorithmaresummarized.Keywords:K-meansclusteringalgorithm;numberofclustersK;clusterinitialization;distancemetric1、引言K-means聚類算法是1955年由Steinhaus、1957年Lloyed、1965年Ball&Hall、1967年McQueen分別在他們各自研究的不同的科學(xué)領(lǐng)域獨(dú)立提出的

4、?？諉柧垲惙治龇椒ㄊ强臻g數(shù)據(jù)挖掘理論中一個(gè)重要的領(lǐng)域，是從海量數(shù)據(jù)中發(fā)現(xiàn)知識(shí)的一個(gè)重要手段。k-means算法是空間聚類算法中應(yīng)用非常廣泛的算法，同時(shí)它也在聚類分析中起著重要作用。日益豐富的空間和非空間數(shù)據(jù)收集存儲(chǔ)于空間數(shù)據(jù)庫中，隨著空間數(shù)據(jù)的不斷膨脹，海量的空間數(shù)據(jù)的大小、復(fù)雜性都在快速增長，遠(yuǎn)遠(yuǎn)超出了人們的解譯能力，從這些空間數(shù)據(jù)中發(fā)現(xiàn)鄰域知識(shí)迫切需求產(chǎn)生一個(gè)多學(xué)科、多鄰域綜合交叉的新興研究鄰域，空間數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生。雖然k-means聚類算法被提出已經(jīng)快60年了，但是目前仍然是應(yīng)用最為廣泛的劃分聚類算法之一1o容易實(shí)施、簡(jiǎn)單、高效、成功的應(yīng)用案例和經(jīng)驗(yàn)是其仍然流行的主要原因。本文主要

5、敘述聚類分析中的K-means聚類算法，總結(jié)了K-means聚類算法的研究現(xiàn)狀，并針對(duì)K-means算法的相關(guān)改進(jìn)做了綜述。2、經(jīng)典K-means算法2.1K-means算法k-means聚類算法是一種基于形心的劃分技術(shù)，是數(shù)據(jù)挖掘領(lǐng)域最為常用的聚類方法之一，最初起源于信號(hào)處理領(lǐng)域。它的目標(biāo)是劃分整個(gè)樣本空間為若干個(gè)子空間，每個(gè)子空間中的樣本點(diǎn)距離該空間中心點(diǎn)平均距離最小。因此，k-means是劃分聚類的一種。k-means算法接受輸入量k;然后將n個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)聚類以便使得所獲得的聚類滿足：同一聚類中的對(duì)象相似度較高；而不同聚類中的對(duì)象相似度較小。聚類相似度是利用各聚類中對(duì)象的均值所獲

6、得一個(gè)“中心對(duì)象”（引力中心）來進(jìn)行計(jì)算的。大體上說，k-means算法的工作過程說明如下：首先從n個(gè)數(shù)據(jù)對(duì)象任意選擇k個(gè)對(duì)象作為初始聚類中心；而對(duì)于所剩下其它對(duì)象，則根據(jù)它們與這些聚類中心的相似度，分別將它們分配給與其最相似的聚類；然后再計(jì)算每個(gè)所獲新聚類的聚類中心；不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù)。k個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊,而各聚類之間盡可能的分開。假設(shè)數(shù)據(jù)集而含n個(gè)歐氏空間中的對(duì)象。劃分方法把戲的對(duì)象分配到K個(gè)簇Ci,.£中，使得對(duì)象1三i,j*GuD且Cicg=?,一個(gè)目標(biāo)函數(shù)用來評(píng)估劃分的質(zhì)量，使得簇內(nèi)對(duì)象相

7、互相似，而與其他簇中的對(duì)象相異。也就是說，該目標(biāo)函數(shù)以簇內(nèi)高相似性和簇間低相似性為目標(biāo)?；谛涡牡膭澐諫技術(shù)使用簇的形心代表該簇。對(duì)象s-G與該簇的代表c之差用dist(s,c。度量,其中dist(x,y)=sqrt(E(xii-y；2)A2)這里i=1,2.nc簇Ci的質(zhì)量可以用簇內(nèi)變差度量，它是G中所有對(duì)象和形心g之間的誤差的平方和，ka=Z£dist(s,G)2(1)i4p：zCi其中，慮數(shù)據(jù)集中所有對(duì)象的誤差的平方和；s是空間中的點(diǎn)，表示給定的數(shù)據(jù)對(duì)象；G是簇G的形心。2.2k-means算法流程k-means算法流程，首先，隨機(jī)的選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)聚類的

8、平均值或中心，對(duì)剩下的各個(gè)對(duì)象，根據(jù)其與每個(gè)聚類中心的歐氏距離，將它派發(fā)給最相似的聚類。之后，應(yīng)用更新之后的均值作為新的聚類中心，再重新分配全部對(duì)象。繼續(xù)迭代，一直到分配趨于穩(wěn)定，也就是本輪迭代所形成聚類與前一輪形成的聚類相同。3、K-means聚類算法的參數(shù)及其改進(jìn)k-means聚類算法需要用戶指定3個(gè)參數(shù)：類別個(gè)數(shù)K,初始聚類中心、相似性和距離度量。針對(duì)這3個(gè)參數(shù)，k-means聚類算法出現(xiàn)了不同的改進(jìn)和變種。3.1 基于K值的改進(jìn)在k-means算法中k是事先給定的，這個(gè)k值的選定是非常難以估計(jì)的。很多時(shí)候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適。這也是k-means算法的一

9、個(gè)不足。有的算法是通過類的自動(dòng)合并和分裂，得到較為合理的類型數(shù)目K,例如ISODATA算法。1)解決方法-聚類有效性函數(shù)根據(jù)聚類有效性函數(shù)的方法是非常簡(jiǎn)單的一種解決方法，從2,JN的區(qū)間內(nèi)逐一選取k值，并利用該函數(shù)評(píng)價(jià)聚類的效果，最終得到最優(yōu)的k值。中外有許多學(xué)者也是按照這種思想提出了一系列的解決方法。李永森等3提出的距離代價(jià)函數(shù)綜合了類際距離和類內(nèi)距離兩項(xiàng)距離函數(shù)，類際距離為所有聚類中心到全域數(shù)據(jù)中心的距離之和。類內(nèi)距離即所有類中對(duì)象到其聚類中心的距離之和。作者證明了當(dāng)距離代價(jià)函數(shù)達(dá)到最小值時(shí)，空間聚類結(jié)果為最優(yōu)，此時(shí)對(duì)應(yīng)的k值為最佳聚類數(shù)。楊善林4提出的距離代價(jià)函數(shù)作為空間聚類的有效性檢驗(yàn)

10、函數(shù)，就是當(dāng)距離代價(jià)函數(shù)達(dá)到最小值時(shí)侯，以距離代價(jià)最小準(zhǔn)則實(shí)現(xiàn)了k值優(yōu)化算法，空間聚類結(jié)果為最優(yōu).根據(jù)經(jīng)驗(yàn)規(guī)則計(jì)算和確定最優(yōu)解的上界，給出了求k值最優(yōu)解kopt及其上界kmax的條件,并在理論上證明了經(jīng)驗(yàn)規(guī)則kmax<Vn的合理性.吳艷文等提出的通過提供相對(duì)較易得到的k初值（大于kopt），得k個(gè)初始聚類。分析聚類之間相互關(guān)系，判斷那些聚類應(yīng)是同一類，從而得到對(duì)k值的優(yōu)化。王朔等提出基于非模糊型集群評(píng)估指標(biāo)（DBI）的概念。該指標(biāo)主要利用幾何原理進(jìn)行運(yùn)算，分別以聚類間離散程度及位于同一類內(nèi)數(shù)據(jù)對(duì)象的緊密程度為依據(jù)。即不同聚類間的相異性高而同一類內(nèi)數(shù)據(jù)對(duì)象的相似性高，并以此來進(jìn)行聚類結(jié)果的

11、評(píng)估。當(dāng)類內(nèi)各數(shù)據(jù)對(duì)象間距離越小而類間距離越大時(shí)指標(biāo)值則越小，代表各聚類內(nèi)的數(shù)據(jù)對(duì)象越緊密且聚類間的差異大。指標(biāo)值越小，表明此聚類數(shù)目下聚類結(jié)果越佳。DBI值越小代表各聚類內(nèi)數(shù)據(jù)相似度越大而類間的相似度越小，由此得到最佳聚類數(shù)目。2）解決方案-遺傳算法Bandyopadhyay等提出了GCUK算法是基于遺傳算法的。此算法的染色體是運(yùn)用字符串方式來編碼的，也就是將每個(gè)初始的聚類中心坐標(biāo)按照順序來進(jìn)行編碼，符號(hào)“#”來表示沒有作為初始聚類中心的數(shù)據(jù)點(diǎn)，編碼完成以后在逐代交叉運(yùn)算中最后得到了最優(yōu)k值。張?jiān)虑俚染W(wǎng)提出了優(yōu)化值參數(shù)是基于遺傳算法的。在遺傳算法中，通過編碼來實(shí)現(xiàn)染色體。依據(jù)k-means算

12、法要找到最佳的k值，染色體的編碼既是對(duì)k值的編碼。在一般情況下，對(duì)于某類問題，總是有一聚類的最大類數(shù)MaxClassnum,這個(gè)值即可由用戶來進(jìn)行輸入，也可以是給定的聚類樣本個(gè)數(shù)。k是介于1和MaxClassnum之間的整數(shù)，可以使用二進(jìn)制用既染色體來表示。胡成等提出了由遺傳操作中的變異操作來控制k值的大小。變異操作的本質(zhì)是挖掘群體中個(gè)體的多樣性，同時(shí)提高算法的局部隨機(jī)搜索能力，防止出現(xiàn)未成熟收斂通過對(duì)個(gè)體適應(yīng)度函數(shù)的求解，決定聚類數(shù)k值的變化方向。由于最初所給的聚類數(shù)k值并非是最佳聚類數(shù)，因此將最初所給種群中具有最大適應(yīng)度值的個(gè)體做為最佳聚類數(shù)的榜樣個(gè)體，其它個(gè)體的長度(即k值)向榜樣個(gè)體的

13、長度靠擾。3)其他方法孫雪等10提出了一種基于半監(jiān)督k-means的k值全局尋優(yōu)算法。設(shè)初始少量數(shù)據(jù)集帶標(biāo)記的為監(jiān)督信息，數(shù)據(jù)集無標(biāo)記的，監(jiān)督信息數(shù)據(jù)集的標(biāo)記為i和j.設(shè)k=2為初值,在完整的數(shù)據(jù)集上來進(jìn)行constrained-k-means聚類.當(dāng)k取不同值時(shí)，計(jì)算監(jiān)督信息中被錯(cuò)誤標(biāo)記的數(shù)據(jù)總數(shù)N,公式如下：kN=Lmin(%,njc)(1)c1其中c表示聚類后各簇的標(biāo)號(hào)；nic,njc表示在第c簇中標(biāo)記的數(shù)據(jù)所占的比例為i,j.出現(xiàn)空簇的頻率取決于K值上限，當(dāng)出現(xiàn)空簇的頻率大于50%時(shí)，則此時(shí)k被認(rèn)為已取得最大值.在k值優(yōu)化的整個(gè)過程中，如果某一簇內(nèi)的監(jiān)督信息滿足以下條件，即max(ni

14、c,njc)nic四。<閾侑(2)則該次聚類結(jié)果被認(rèn)為是無效，保留有效的簇中心值，再開始新一輪聚類，在中心點(diǎn)選擇上采取了半增量的迭代方式，提高了算法性能。上式閾值選取可采取重復(fù)實(shí)驗(yàn)的方法，一般當(dāng)與njc的數(shù)量相差較少時(shí)，類標(biāo)記為c的簇就為無效的簇.使N取得最小值的k取值就為k-means聚類算法的最佳初值。田森平等10提出了根據(jù)所需聚類數(shù)據(jù)的分布的屬性，來計(jì)算他們間的距離，經(jīng)過這一系列變換，得到最終的聚類參數(shù)k值。從需要聚類的數(shù)據(jù)之中抽取出一部分樣本數(shù)據(jù)，來獲取聚類參數(shù)的抽樣數(shù)據(jù)；再計(jì)算抽樣數(shù)據(jù)間的距離來得到一沿對(duì)角線對(duì)稱的距離矩陣，從這一距離矩陣之中找出一個(gè)大于零的最小距離即為mind

15、(xi,xj),作為高密度半徑和簇劃分半徑的一個(gè)項(xiàng)，來保證這兩個(gè)半徑不會(huì)太??；對(duì)距離矩陣按列求平均值，再對(duì)這些平均值求R求平均值得到R,根據(jù)|Ri-R|/R的誤差來去掉噪聲點(diǎn)，在噪聲點(diǎn)去除完全后，重新計(jì)算R,根據(jù)R和mind(x,xj),求得了高密度半徑R。再找出minR,依據(jù)，d(xi,xj)<minR的關(guān)系來得到高密度個(gè)數(shù)的參數(shù)Z；最終根據(jù)R和mind(Xi,Xj),獲得簇劃分的半徑r,合并簇的中心點(diǎn)之間距離m,合并簇的邊界點(diǎn)之間距離ho綜上所述的研究可發(fā)現(xiàn)，學(xué)術(shù)界已經(jīng)提出了許多種K值的選取方法，并且分別基于不同的解決方法。3.2 初始聚類中心的選擇k-means算法是貪心算法，在多

16、項(xiàng)式時(shí)間內(nèi)，只能得到局部最優(yōu)。初始聚類中心的選擇是隨機(jī)選取的，不同的初始聚類中心選取方法得到的最終局部最優(yōu)結(jié)果也不同。所以可能造成在同一類別的樣本被強(qiáng)制當(dāng)作兩個(gè)類的初始聚類中心，使得聚類結(jié)果最終只能收斂于局部最優(yōu)解，k-means算法的聚類效果在很大的程度上依賴于初始聚類中心的選擇，因此，大量的初始聚類中心選取方案被提出。袁方等11提出了基于密度的優(yōu)化初始聚類中心的方法，找到一組能反映數(shù)據(jù)分布特征的數(shù)據(jù)對(duì)象作為初始聚類中心首先計(jì)算數(shù)據(jù)對(duì)象x所處區(qū)域的密度，來定義一個(gè)密度參數(shù)：以x為中心，包含了常數(shù)Minpts個(gè)數(shù)據(jù)對(duì)象的半徑稱為對(duì)象為的密度參數(shù)，用e表示。e越大，則說明數(shù)據(jù)對(duì)象所處區(qū)域的數(shù)據(jù)密

17、度就越低。反之，e越小，說明數(shù)據(jù)對(duì)象所處區(qū)域的數(shù)據(jù)密度越高。通過計(jì)算每個(gè)數(shù)據(jù)對(duì)象的密度參數(shù)，就可以發(fā)現(xiàn)處于高密度區(qū)域的點(diǎn)，從而得到一個(gè)高密度點(diǎn)集合D。在D中取處于最高密度區(qū)域的數(shù)據(jù)對(duì)象作為第1個(gè)聚類中心Zi；取距離Zi最遠(yuǎn)的一個(gè)高密度點(diǎn)作第2個(gè)聚類中心Z2;計(jì)算D中各數(shù)據(jù)對(duì)象xi至IZi,Z2的距離d(xi,Zi),d(xi,z2),z3為滿足max(min(d(xi,Zi),d(xi,z2)i=1,2,n,的數(shù)據(jù)對(duì)象X；Zm為滿足max(min(d(x,Zi),d(xi,z2),.,d(xi,Zm"i=1,2,-q的數(shù)據(jù)對(duì)象為，xiCD。依此得到k個(gè)初始聚類中心。秦桂等阿提出了探測(cè)

18、數(shù)據(jù)集中的相對(duì)密集區(qū)域，再利用這些密集區(qū)域生成初始類中心點(diǎn)。該方法能夠很好地排除類邊緣點(diǎn)和噪聲點(diǎn)的影響，并且能夠適應(yīng)數(shù)據(jù)集中各個(gè)實(shí)際類別密度分布不平衡的情況，最終獲得較好的聚類效果。利用UPGMA層次聚類算法初期匯聚效果好的優(yōu)勢(shì)，發(fā)現(xiàn)數(shù)據(jù)集中的密集區(qū)域，避免類邊緣點(diǎn)或噪聲點(diǎn)成為初始類中心點(diǎn)，同時(shí)，著重于考慮區(qū)域的相對(duì)密集程度，改變UGPMA算法的停止條件，使子樹的生成停止在不同的聚類層次上，以適應(yīng)各個(gè)實(shí)際類別密度不平衡的數(shù)據(jù)集。賴玉霞等13提出了根據(jù)數(shù)據(jù)的自然分布來選取初始聚類中心，找出對(duì)象中分布比較密集的區(qū)域，這正是聚類的目的，從而擺脫了隨機(jī)選取聚類中心對(duì)聚類結(jié)果產(chǎn)生的不穩(wěn)定性，以及用質(zhì)心代

19、表一個(gè)簇所帶來的“噪聲”和孤立點(diǎn)數(shù)據(jù)對(duì)聚類結(jié)果的影響。黃敏等14提出了在基于高密度點(diǎn)分布的算法基礎(chǔ)上，解決了當(dāng)高密度點(diǎn)分布不只一個(gè)時(shí)如何選取聚類中心的問題。找到最大者作為聚類中心點(diǎn)，并將與聚類中心的距離小于樣本平均距離的點(diǎn)的密度參數(shù)從密度參數(shù)集合中刪除。周愛武等15提出了的算法的改進(jìn)建立在沒有離群點(diǎn)的數(shù)據(jù)集上，通過求次小距離的樣本點(diǎn)的中心，然后求出此中心與一個(gè)聚類中心之間的距離，與樣本點(diǎn)之間的平均距離進(jìn)行判斷。如果小于樣本點(diǎn)之間的平均距離，則將此樣本點(diǎn)加入初始化集合中，再求第三距離小的樣本點(diǎn)，如果大于樣本點(diǎn)之間的平均距離，則求出此中心存入二維數(shù)據(jù)樣本點(diǎn)中心。集合二維數(shù)據(jù)樣本點(diǎn)中心中的個(gè)數(shù)等于k

20、,初始聚類中心全部找到。周煒奔等16提出了基于密度、中心點(diǎn)的初始化中心算法，首先算出樣本數(shù)據(jù)集之中每個(gè)樣本密度，得到一個(gè)以密度為標(biāo)準(zhǔn)的樣本集合。然后在標(biāo)準(zhǔn)樣本集合基礎(chǔ)上進(jìn)行初始聚類中心的選取和簇的劃分。每劃分出一個(gè)簇，就從標(biāo)準(zhǔn)樣本集合中刪除該簇所包括的數(shù)據(jù)點(diǎn)。鄭丹等仞提出了基于k-means聚類算法對(duì)初始聚類中心敏感的這一特點(diǎn)的改進(jìn)算法。k-means聚類算法中，數(shù)據(jù)對(duì)象間的相似性是根據(jù)歐氏距離衡量的，距離越小則說明越相似。用DK圖對(duì)k-dist圖進(jìn)行分析，找出對(duì)應(yīng)密度水平的平緩曲線。在不同的密度水平上分別選擇一個(gè)k-dist值最小即密度相對(duì)最大的點(diǎn)作為初始聚類中心。根據(jù)上述原理，在總數(shù)為k的

21、數(shù)據(jù)集之中找出q'個(gè)密度相對(duì)與其它點(diǎn)最大的點(diǎn)來作為初始聚類中心。相比確定k值，優(yōu)化算法應(yīng)用于初始聚類中心的選擇更加合適，目前已經(jīng)提出了許多比較成熟的算法，并且已經(jīng)有相關(guān)的專著問世1803.3 相似性度量和距離矩陣k-means聚類算法使用歐式距離作為相似性度量和距離矩陣，計(jì)算各數(shù)據(jù)點(diǎn)到其類別中心的距離平方和。因此，k-means聚類算法劃分出來的類別店鋪是類球形的。實(shí)際上，歐式距離是Minkowski距離在m=2時(shí)的特例，即L2距離。在采用Lm距離進(jìn)行K-means聚類時(shí)，最終類中心應(yīng)是每一類的m中心向量。Kashima等人于2008年使用L1距離，最終聚類中心使每一類的中位向量。對(duì)于

22、一維數(shù)據(jù)X=X1,X2，,Xi,Xn而言，中位數(shù)乂比均值X對(duì)異常數(shù)據(jù)有較強(qiáng)的抗干擾性，聚類結(jié)果受數(shù)據(jù)中異常值的影響較小。Mao&Jain于1996年提出使用Mahalanobis距離，但計(jì)算代價(jià)太大。在應(yīng)用中，Linde等。于1980年提出使用Itakura-Saito距離。Banerjee等人2004年提出，如果使用Bregman差異作為距離度量，有許多突出優(yōu)點(diǎn)，如克服局部最優(yōu)、類別之間的線性分離、線性時(shí)間復(fù)雜度等。4、結(jié)束語k-means聚類算法是一種非常優(yōu)秀的算法，以其簡(jiǎn)單的算法思想、較快的聚類速度和良好的聚類效果得到了廣泛的應(yīng)用。對(duì)于該算法在聚類過程中暴露出的若干問題，本文對(duì)其

23、中k值確定、初始聚類中心選擇等主要問題進(jìn)行了綜述。因此k-means聚類算法是一個(gè)貪心算法，在多項(xiàng)式時(shí)間內(nèi)，僅能獲得局部最優(yōu)，對(duì)k-means聚類算法的研究也將繼續(xù)。參考文獻(xiàn)：1 AnilKJ.Dataclustering:50yearsbeyondK-MeansJ.PatternRecognitionLetters,2010,31(8):651-666.2Jiaweihan;MichelineKamber;JianPei.DataMining:ConceptsandTechniques,ThirdEditionJ.2015.73李永森，楊善林，馬溪駿等.空間聚類算法中的K值優(yōu)化問題研究J.系統(tǒng)仿真學(xué)報(bào)，2006,18(3):573576.4楊善林，李永森，胡笑旋，等.k-means算法中的k值優(yōu)化問題研究J.系統(tǒng)工程理論與實(shí)踐，2006,(2):97-101.5吳艷文，胡學(xué)鋼.一種K_means算法的k值優(yōu)化方案J.巢湖學(xué)院學(xué)報(bào).2007,9(6):21-14.6王朔顧，進(jìn)廣.基于K值改進(jìn)的Kmeans算法在入侵檢測(cè)中的應(yīng)用J.工業(yè)控制計(jì)算機(jī),2014,27(7):93-97.7Bandyo