聚類分析中K-means算法綜述

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

2、心；相似性度量和距離矩陣Overview of K-means algorithm in clustering analysisAbstract:Clustering is major field in data mining which also is an important method of data partition or grouping. Clustering now has been applied into various ways in business intelligence,Web classification,biology,market and so on.In

3、 this paper, we introduce the spatial clustering rules,At the same time, the classical K-means algorithm is describe,And some related improvements to K-means algorithm are summarized.Key words: K-means clustering algorithm; number of clusters K; cluster initialization; distance metric1、引言K-means聚類算法

4、是1955年由Steinhaus 、1957年 Lloyed、1965年 Ball & Hall、1967年 McQueen分別在他們各自研究的不同的科學(xué)領(lǐng)域獨(dú)立提出的。空間聚類分析方法是空間數(shù)據(jù)挖掘理論中一個(gè)重要的領(lǐng)域，是從海量數(shù)據(jù)中發(fā)現(xiàn)知識的一個(gè)重要手段。k-means算法是空間聚類算法中應(yīng)用非常廣泛的算法，同時(shí)它也在聚類分析中起著重要作用。日益豐富的空間和非空間數(shù)據(jù)收集存儲于空間數(shù)據(jù)庫中，隨著空間數(shù)據(jù)的不斷膨脹，海量的空間數(shù)據(jù)的大小、復(fù)雜性都在快速增長，遠(yuǎn)遠(yuǎn)超出了人們的解譯能力，從這些空間數(shù)據(jù)中發(fā)現(xiàn)鄰域知識迫切需求產(chǎn)生一個(gè)多學(xué)科、多鄰域綜合交叉的新興研究鄰域，空間數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)

5、而生。雖然k-means聚類算法被提出已經(jīng)快60年了，但是目前仍然是應(yīng)用最為廣泛的劃分聚類算法之一。容易實(shí)施、簡單、高效、成功的應(yīng)用案例和經(jīng)驗(yàn)是其仍然流行的主要原因。本文主要敘述聚類分析中的K-means聚類算法，總結(jié)了K-means聚類算法的研究現(xiàn)狀，并針對K-means算法的相關(guān)改進(jìn)做了綜述。2、經(jīng)典K-means算法2.1 K-means算法 k-means 聚類算法是一種基于形心的劃分技術(shù)，是數(shù)據(jù)挖掘領(lǐng)域最為常用的聚類方法之一，最初起源于信號處理領(lǐng)域。它的目標(biāo)是劃分整個(gè)樣本空間為若干個(gè)子空間，每個(gè)子空間中的樣本點(diǎn)距離該空間中心點(diǎn)平均距離最小。因此，k-means是劃分聚類的一種。k-m

6、eans 算法接受輸入量 k ；然后將n個(gè)數(shù)據(jù)對象劃分為 k個(gè)聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個(gè)“中心對象”（引力中心）來進(jìn)行計(jì)算的。大體上說，k-means 算法的工作過程說明如下：首先從n個(gè)數(shù)據(jù)對象任意選擇 k 個(gè)對象作為初始聚類中心；而對于所剩下其它對象，則根據(jù)它們與這些聚類中心的相似度，分別將它們分配給與其最相似的聚類；然后再計(jì)算每個(gè)所獲新聚類的聚類中心；不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測度函數(shù)。 k個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊，而各聚類

7、之間盡可能的分開。假設(shè)數(shù)據(jù)集D包含n個(gè)歐氏空間中的對象。劃分方法把D中的對象分配到K個(gè)簇中，使得對象1i，jk,D且=Ø，一個(gè)目標(biāo)函數(shù)用來評估劃分的質(zhì)量，使得簇內(nèi)對象相互相似，而與其他簇中的對象相異。也就是說，該目標(biāo)函數(shù)以簇內(nèi)高相似性和簇間低相似性為目標(biāo)?；谛涡牡膭澐旨夹g(shù)使用簇的形心代表該簇。對象s與該簇的代表之差用dist（s，）度量，其中dist（x，y）=sqrt( ()2 ) 這里i=1,2.n。簇的質(zhì)量可以用簇內(nèi)變差度量，它是中所有對象和形心之間的誤差的平方和，= （1） 其中，是數(shù)據(jù)集中所有對象的誤差的平方和；s是空間中的點(diǎn)，表示給定的數(shù)據(jù)對象；是簇的形心。2.2 k-

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

9、的選定是非常難以估計(jì)的。很多時(shí)候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適。這也是 k-means 算法的一個(gè)不足。有的算法是通過類的自動(dòng)合并和分裂，得到較為合理的類型數(shù)目 K，例如 ISODATA 算法。1) 解決方法-聚類有效性函數(shù)根據(jù)聚類有效性函數(shù)的方法是非常簡單的一種解決方法，從2，的區(qū)間內(nèi)逐一選取k值，并利用該函數(shù)評價(jià)聚類的效果，最終得到最優(yōu)的k值。中外有許多學(xué)者也是按照這種思想提出了一系列的解決方法。李永森等提出的距離代價(jià)函數(shù)綜合了類際距離和類內(nèi)距離兩項(xiàng)距離函數(shù)，類際距離為所有聚類中心到全域數(shù)據(jù)中心的距離之和。類內(nèi)距離即所有類中對象到其聚類中心的距離之和。作者證明了當(dāng)距離

10、代價(jià)函數(shù)達(dá)到最小值時(shí)，空間聚類結(jié)果為最優(yōu)，此時(shí)對應(yīng)的k 值為最佳聚類數(shù)。 楊善林提出的距離代價(jià)函數(shù)作為空間聚類的有效性檢驗(yàn)函數(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的合理性.吳艷文等提出的通過提供相對較易得到的k 初值( 大于kopt) ,得k 個(gè)初始聚類。分析聚類之間相互關(guān)系,判斷那些聚類應(yīng)是同一類,從而得到對k 值的優(yōu)化。 王朔等提出基于非模糊型集群評估指標(biāo)（DBI）的概念。該指標(biāo)主要利用幾何原理進(jìn)行運(yùn)算，分

11、別以聚類間離散程度及位于同一類內(nèi)數(shù)據(jù)對象的緊密程度為依據(jù)。即不同聚類間的相異性高而同一類內(nèi)數(shù)據(jù)對象的相似性高，并以此來進(jìn)行聚類結(jié)果的評估。當(dāng)類內(nèi)各數(shù)據(jù)對象間距離越小而類間距離越大時(shí)指標(biāo)值則越小，代表各聚類內(nèi)的數(shù)據(jù)對象越緊密且聚類間的差異大。指標(biāo)值越小，表明此聚類數(shù)目下聚類結(jié)果越佳。DBI 值越小代表各聚類內(nèi)數(shù)據(jù)相似度越大而類間的相似度越小，由此得到最佳聚類數(shù)目。2） 解決方案-遺傳算法Bandyopadhyay 等提出了GCUK 算法是基于遺傳算法的。此算法的染色體是運(yùn)用字符串方式來編碼的，也就是將每個(gè)初始的聚類中心坐標(biāo)按照順序來進(jìn)行編碼，符號“#”來表示沒有作為初始聚類中心的數(shù)據(jù)點(diǎn)，編碼完成

12、以后在逐代交叉運(yùn)算中最后得到了最優(yōu)k值。張?jiān)虑俚忍岢隽藘?yōu)化值參數(shù)是基于遺傳算法的。在遺傳算法中, 通過編碼來實(shí)現(xiàn)染色體。依據(jù)k-means算法要找到最佳的k值, 染色體的編碼既是對k值的編碼。在一般情況下，對于某類問題,總是有一聚類的最大類數(shù)MaxClassnum, 這個(gè)值即可由用戶來進(jìn)行輸入，也可以是給定的聚類樣本個(gè)數(shù)。k是介于1和MaxClassnum之間的整數(shù)，可以使用二進(jìn)制串既染色體來表示。 胡彧等提出了由遺傳操作中的變異操作來控制k值的大小。變異操作的本質(zhì)是挖掘群體中個(gè)體的多樣性，同時(shí)提高算法的局部隨機(jī)搜索能力，防止出現(xiàn)未成熟收斂通過對個(gè)體適應(yīng)度函數(shù)的求解，決定聚類數(shù)k值的變化方向。

13、由于最初所給的聚類數(shù)k值并非是最佳聚類數(shù)，因此將最初所給種群中具有最大適應(yīng)度值的個(gè)體做為最佳聚類數(shù)的榜樣個(gè)體，其它個(gè)體的長度(即k值)向榜樣個(gè)體的長度靠擾。3） 其他方法 孫雪等提出了一種基于半監(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)行const rained-k-means 聚類.當(dāng)k取不同值時(shí), 計(jì)算監(jiān)督信息中被錯(cuò)誤標(biāo)記的數(shù)據(jù)總數(shù)N，公式如下： （1）其中c 表示聚類后各簇的標(biāo)號;, 表示在第c簇中標(biāo)記的數(shù)據(jù)所占的比例為i , j .出現(xiàn)空簇的頻率取決于K值上限,

14、 當(dāng)出現(xiàn)空簇的頻率大于50 %時(shí), 則此時(shí)k被認(rèn)為已取得最大值.在k值優(yōu)化的整個(gè)過程中, 如果某一簇內(nèi)的監(jiān)督信息滿足以下條件, 即 閾值 （2）則該次聚類結(jié)果被認(rèn)為是無效,保留有效的簇中心值,再開始新一輪聚類,在中心點(diǎn)選擇上采取了半增量的迭代方式,提高了算法性能。上式閾值選取可采取重復(fù)實(shí)驗(yàn)的方法,一般當(dāng)與的數(shù)量相差較少時(shí),類標(biāo)記為c的簇就為無效的簇.使N取得最小值的k取值就為k-means聚類算法的最佳初值。田森平等提出了根據(jù)所需聚類數(shù)據(jù)的分布的屬性，來計(jì)算他們間的距離，經(jīng)過這一系列變換，得到最終的聚類參數(shù)k值。從需要聚類的數(shù)據(jù)之中抽取出一部分樣本數(shù)據(jù)，來獲取聚類參數(shù)的抽樣數(shù)據(jù)；再計(jì)算抽樣數(shù)據(jù)

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

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

17、密度參數(shù)，用表示。越大，則說明數(shù)據(jù)對象所處區(qū)域的數(shù)據(jù)密度就越低。反之，越小，說明數(shù)據(jù)對象所處區(qū)域的數(shù)據(jù)密度越高。通過計(jì)算每個(gè)數(shù)據(jù)對象的密度參數(shù)，就可以發(fā)現(xiàn)處于高密度區(qū)域的點(diǎn)，從而得到一個(gè)高密度點(diǎn)集合D。在D中取處于最高密度區(qū)域的數(shù)據(jù)對象作為第1 個(gè)聚類中心z；取距離z最遠(yuǎn)的一個(gè)高密度點(diǎn)作第2個(gè)聚類中心z ；計(jì)算D 中各數(shù)據(jù)對象到z,z的距離 d( ,z )，d( ,z )，z為滿足max(min(d( ,z ), d( ,z ) i =1, 2,n的數(shù)據(jù)對象 ；為滿足max(min(d( ,z ), d( ,z ),.,d(,) i =1,2,n的數(shù)據(jù)對象 ,D。依此得到k個(gè)初始聚類中心。秦鈺

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

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

20、點(diǎn)中心 。集合二維數(shù)據(jù)樣本點(diǎn)中心中的個(gè)數(shù)等于k， 初始聚類中心全部找到。 周煒奔等提出了基于密度、中心點(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聚類算法對初始聚類中心敏感的這一特點(diǎn)的改進(jìn)算法。k-means聚類算法中，數(shù)據(jù)對象間的相似性是根據(jù)歐氏距離衡量的，距離越小則說明越相似。用DK圖對k-dist圖進(jìn)行分析，找出對應(yīng)密度水平的平緩曲線。在不同的密度水平上分別選擇一個(gè)k-dist值最小即密度相對最大的點(diǎn)

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

22、中位向量。對于一維數(shù)據(jù)而言，中位數(shù)M比均值x對異常數(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)秀的算法，以其簡單的算法思想、較快的聚類速度和良好的聚類效果得到了廣泛的應(yīng)用。對于該算法在聚類過程中暴露出的若干問題，本文對其中k值確定、

23、初始聚類中心選擇等主要問題進(jìn)行了綜述。因此k-means聚類算法是一個(gè)貪心算法，在多項(xiàng)式時(shí)間內(nèi)，僅能獲得局部最優(yōu)，對 k-means聚類算法的研究也將繼續(xù)。參考文獻(xiàn) ： 1 Anil K J. Data clustering: 50 years beyond K-Means J. Pattern Recognition Letters, 2010, 31(8): 651-666.2Jiawei han;Micheline Kamber;Jian Pei.Data Mining:Concepts and Techniques,Third EditionJ.2015.73李永森，楊善林，馬溪駿等 空間聚類算法中的K 值優(yōu)化問題研究J系統(tǒng)仿真學(xué)報(bào)，2006,18( 3) : 573 5764楊善林, 李永森, 胡笑旋, 等.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 算法在入侵檢測中的應(yīng)用J.工業(yè)控制計(jì)算機(jī),2014,27(7):93-97.7Bandyopadhyay S,Maulik U.Genetic Cluste