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

1、攻讀碩士學位研究生試卷（作業(yè)）封面（ 2015 至 2016 學年度第一學期）題 目 論文選讀 科 目 聚類分析中K-means算法綜述 姓 名 王苑茹 專 業(yè) 計算機技術(shù) 入學年月 2015年8月 簡短評語成績：授課教師簽字：聚類分析中K-means算法綜述摘要:聚類分析是數(shù)據(jù)挖掘中一個極其重要的研究方向，是一個將數(shù)據(jù)劃分成簇的方法或手段。聚類分析可廣泛利用在商務(wù)智能，Web搜索，生物學以及圖像模式識別等眾多方面。本文主要敘述聚類分析中的K-means聚類算法，總結(jié)了K-means聚類算法的研究現(xiàn)狀，并針對K-means算法的相關(guā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分別在他們各自研究的不同的科學領(lǐng)域獨立提出的。空間聚類分析方法是空間數(shù)據(jù)挖掘理論中一個重要的領(lǐng)域，是從海量數(shù)據(jù)中發(fā)現(xiàn)知識的一個重要手段。k-means算法是空間聚類算法中應(yīng)用非常廣泛的算法，同時它也在聚類分析中起著重要作用。日益豐富的空間和非空間數(shù)據(jù)收集存儲于空間數(shù)據(jù)庫中，隨著空間數(shù)據(jù)的不斷膨脹，海量的空間數(shù)據(jù)的大小、復(fù)雜性都在快速增長，遠遠超出了人們的解譯能力，從這些空間數(shù)據(jù)中發(fā)現(xiàn)鄰域知識迫切需求產(chǎn)生一個多學科、多鄰域綜合交叉的新興研究鄰域，空間數(shù)據(jù)挖掘技術(shù)應(yīng)運

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

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

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

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

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

10、代價函數(shù)達到最小值時，空間聚類結(jié)果為最優(yōu)，此時對應(yīng)的k 值為最佳聚類數(shù)。 楊善林提出的距離代價函數(shù)作為空間聚類的有效性檢驗函數(shù), 就是當距離代價函數(shù)達到最小值時侯, 以距離代價最小準則實現(xiàn)了k 值優(yōu)化算法，空間聚類結(jié)果為最優(yōu).根據(jù)經(jīng)驗規(guī)則計算和確定最優(yōu)解的上界, 給出了求k值最優(yōu)解kopt及其上界kmax的條件, 并在理論上證明了經(jīng)驗規(guī)則kmax的合理性.吳艷文等提出的通過提供相對較易得到的k 初值( 大于kopt) ,得k 個初始聚類。分析聚類之間相互關(guān)系,判斷那些聚類應(yīng)是同一類,從而得到對k 值的優(yōu)化。 王朔等提出基于非模糊型集群評估指標（DBI）的概念。該指標主要利用幾何原理進行運算，分

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

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

13、由于最初所給的聚類數(shù)k值并非是最佳聚類數(shù)，因此將最初所給種群中具有最大適應(yīng)度值的個體做為最佳聚類數(shù)的榜樣個體，其它個體的長度(即k值)向榜樣個體的長度靠擾。3） 其他方法 孫雪等提出了一種基于半監(jiān)督k-means 的k 值全局尋優(yōu)算法。 設(shè)初始少量數(shù)據(jù)集帶標記的為監(jiān)督信息, 數(shù)據(jù)集無標記的,監(jiān)督信息數(shù)據(jù)集的標記為i和j.設(shè)k =2為初值, 在完整的數(shù)據(jù)集上來進行const rained-k-means 聚類.當k取不同值時, 計算監(jiān)督信息中被錯誤標記的數(shù)據(jù)總數(shù)N，公式如下： （1）其中c 表示聚類后各簇的標號;, 表示在第c簇中標記的數(shù)據(jù)所占的比例為i , j .出現(xiàn)空簇的頻率取決于K值上限,

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

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

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

17、密度參數(shù)，用表示。越大，則說明數(shù)據(jù)對象所處區(qū)域的數(shù)據(jù)密度就越低。反之，越小，說明數(shù)據(jù)對象所處區(qū)域的數(shù)據(jù)密度越高。通過計算每個數(shù)據(jù)對象的密度參數(shù)，就可以發(fā)現(xiàn)處于高密度區(qū)域的點，從而得到一個高密度點集合D。在D中取處于最高密度區(qū)域的數(shù)據(jù)對象作為第1 個聚類中心z；取距離z最遠的一個高密度點作第2個聚類中心z ；計算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個初始聚類中心。秦鈺

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

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

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

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

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

23、初始聚類中心選擇等主要問題進行了綜述。因此k-means聚類算法是一個貪心算法，在多項式時間內(nèi)，僅能獲得局部最優(yōu)，對 k-means聚類算法的研究也將繼續(xù)。參考文獻 ： 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)仿真學報，2006,18( 3) : 573 5764楊善林, 李永森, 胡笑旋, 等.k-means算法中的k值優(yōu)化問題研究 J .系統(tǒng)工程理論與實踐, 2006,(2):97 -101.5吳艷文,胡學鋼.一種K_means算法的k值優(yōu)化方案J.巢湖學院學報.2007,9(6):21-14.6王朔顧,進廣.基于K 值改進的Kmeans 算法在入侵檢測中的應(yīng)用J.工業(yè)控制計算機,2014,27(7):93-97.7Bandyopadhyay S,Maulik U.Genetic Cluste