基于劃分的聚類算法

1、文獻閱讀報告課程名稱：模式識別課程編號:題目：基于劃分的聚類算法研究生姓名：學號：論文評語:成績：任課教師：評閱日期：Word資料基于劃分的聚類算法2016-11-20摘 要：聚類分析是數(shù)據(jù)挖掘的一個重要研究分支，已經(jīng)提出了許多聚類算法，劃分方法是其中之一?；趧澐值木垲愃惴ň褪怯媒y(tǒng)計分析的方法研究分類問題。本文介紹了聚類的定義以及聚類算法的種類，詳細闡述了K均值聚類算法和 K中心點聚類算法的基本原理并對他們的性能進行分析，對近年來各學者對基于劃分的聚類算法的 研究現(xiàn)狀進行梳理，對其具體應用實例作簡要介紹。關(guān)鍵字：數(shù)據(jù)挖掘；聚類； K均值聚類算法；K中心點聚類算法；K眾數(shù)算法；k多層次聚類算

2、法Partitional clustering algorithmsAbstract:Clustering analysis is an important branch of data mining, many clustering algorithms havebeen proposed, the dividing method is one of them. Based on the clustering algorithm is divided into classification problems using the method of statistical analysis.

3、In this paper, we introduces the definitionof clustering and type of clustering algorithm, the basic principle of k-means clustering algorithm andK-center clustering algorithm are expounded in detail, we also analyze their performance , the scholars inrecent years the study of the clustering algorit

4、hm based on partitioning present situation has carried on the comb , make a brief introduction to its specific application instance.Key words: Data mining ； clustering ； k-means clustering algorithms ； k-medoids clustering algorithms ； k-modes clustering algorithms ;k-prototype clustering algorithms

5、1 .引言把單個的數(shù)據(jù)對象的集合劃分為相類似的樣本組成的多個簇或多個類的過程，這就叫聚類1。在無監(jiān)督的情況下，具有獨立的學習能力，這就是聚類。將數(shù)據(jù)空間中的所有數(shù)據(jù)點分別劃分到不 同的類中，相近距離的劃分到相同類，較遠距離的劃分到不同類，這就是聚類的目的.聚類分析常作為一種數(shù)據(jù)的預處理過程被用于許多應用當中，它是更深一步分析數(shù)據(jù)、處理數(shù)據(jù)的基礎(chǔ)。人們通 過聚類分析這一最有效的手段來認識事物、探索事物之間的內(nèi)在聯(lián)系，而且，關(guān)聯(lián)規(guī)則等分析算法 的預處理步驟也可以用它。現(xiàn)在，在氣象分析中，在圖像處理時，在模式識別領(lǐng)域，在食品檢驗過 程中，都有用到它。隨著現(xiàn)代科技水平的不斷提高、網(wǎng)絡(luò)的迅猛發(fā)展、計算機

6、技術(shù)的不斷改革和創(chuàng) 新，大批量的數(shù)據(jù)不斷涌現(xiàn)。怎樣從這些數(shù)據(jù)中提取有意義的信息成為人們關(guān)注的問題。這對聚類 分析技術(shù)來說無疑是個巨大的挑戰(zhàn)。只有具有處理高維的數(shù)據(jù)的能力的聚類算法才能解決該問題.研究者們開始設(shè)計各種聚類算法，于是，基于劃分的聚類算法便應運而生，而且，取得了很好的效 果。2 .正文1聚類概述1.1 定義聚類的定義為:在已知的數(shù)據(jù)的集合中，尋找數(shù)據(jù)點集的同類的集合.其中，每一個數(shù)據(jù)集合為一個類，還確定了一個區(qū)域，區(qū)域中的對象的密度高于其他區(qū)域中的對象的密度.聚類的實質(zhì)就是“把數(shù)據(jù)集合中的所有數(shù)據(jù)分成許多的類簇，其中必有一個類簇內(nèi)的實體它們都是相似的，而其它不同 類簇的實體它們是不相

7、似的；一個類簇是被測試空間中的點的會聚，而且，同一個類簇的任意兩個 點之間的距離小于不同的類簇的任意兩個點之間的距離；一個包含的密度相對較高的點集的多維空 間中的連通區(qū)域可以被描述為一個類簇，這時，它們可以借助包含的密度相對較低的點集的區(qū)域與 其他的區(qū)域分離開來。”1.2 聚類算法的種類截止目前，經(jīng)典的聚類方法3有基于劃分的方法，也有基于層次的方法，更有基于密度的方法， 還有基于網(wǎng)格的方法及基于模型的方法。1.2.1 戈U分方法(partitioning methods)給定一個數(shù)據(jù)集D,其包含有n個數(shù)據(jù)對象，用一個劃分方法來構(gòu)建數(shù)據(jù)的k個劃分， 每一個劃分表示一個類，且kwn。即它將數(shù)據(jù)對象

8、劃分為個簇，并滿足以下兩點要求：1)每一個組至少包含一個數(shù)據(jù)對象；2)每一個數(shù)據(jù)對象必須屬于某一個組.假定要構(gòu)建的劃分其數(shù)目為k,劃分方法就是:首先，先創(chuàng)建一個初始的劃分，然后，再采用一種迭代的重定位的技術(shù)，通過將數(shù)據(jù)對象在劃分 間來回的移動來改進劃分.一個好劃分的準則為：同一類中的數(shù)據(jù)對象之間要盡可能的“接近”，而不同的類中的數(shù)據(jù)對象之間要盡可能的“遠離”。1.2.2 層次方法(hierarchical methods)對給定的數(shù)據(jù)對象的集合進行層次的分解就是層次的方法.依據(jù)層次分解的形成過程，該方法可分為凝聚的層次聚類和分裂的層次聚類兩類.自底向上進行的層次分解為凝聚的(agglomera

9、tive )層次聚類；自頂向下進行的層次分解為分裂的( divisive )層次聚類.分裂的層次聚類先把全體對 象放在一個類中，再將其漸漸地劃分為越來越小的類，依此進行，一直到每一個對象能夠自成一類.而凝聚的層次聚類則是先將每一個對象作為一個類，再將這些類逐漸地合并起來形成相對較大的類，依此進行，一直到所有的對象都在同一個類中方結(jié)束。1.2.3 密度方法(density-based methods)大多數(shù)的聚類算法都是用距離來描述數(shù)據(jù)間的相似性性質(zhì)的，這些方法只能發(fā)現(xiàn)球狀的類，而 在其他形狀的類上，這些算法都無計可施.鑒于此，就只能用密度(密度實際就是對象或數(shù)據(jù)點的數(shù)目)將其的相似性予以取代，

10、該方法就是基于密度的聚類算法。密度的方法的思想：一旦“領(lǐng)域” 的密度超過某一個閾值，就將給定的簇繼續(xù)的增長.該算法還能有效的去除噪聲。1.2.4 網(wǎng)格的方法(grid-based methods)先把對象空間量化成有限數(shù)目的單元，將其形成一個網(wǎng)格空間，再對該空間進行聚類，這就是 網(wǎng)格的方法.其主要優(yōu)點為處理速度快，因為它的處理速度只與量化空間中的每一維的單元數(shù)目相關(guān)，而與數(shù)據(jù)對象的數(shù)目無關(guān)1.2.5 模型的方法（model-based methods）基于模型的方法就是先給每一個聚類假定一個模型，再去尋找能較好的滿足該模型的數(shù)據(jù)的集 合。此模型也許是數(shù)據(jù)點在空間中的密度分布的函數(shù)，也許是其它.

11、其潛在的假定為：一系列概率的分布決定該目標數(shù)據(jù)的集合 .統(tǒng)計方案、神經(jīng)網(wǎng)絡(luò)方案通常是其研究的兩種方向。2基于劃分的聚類算法給定一個數(shù)據(jù)集D,其包含有n個數(shù)據(jù)對象，用一個劃分方法來構(gòu)建數(shù)據(jù)的k個劃分， 每一個劃分表示一個類，且kwn。根據(jù)D的屬性，使得同一類中的數(shù)據(jù)對象之間盡可能的“接近”，而不同 的類中的數(shù)據(jù)對象之間盡可能的“遠離”。2.1 K-均值聚類算法2.1.1 K均值聚類算法4基本原理隨機選k個點作為初始的聚類的中心點，根據(jù)每個樣本到聚類的中心之間的距離，把樣本歸類到相距它距離最近的聚類中心代表的類中，再計算樣本均值.如若相鄰的兩個聚類中心無變化，調(diào)整立即結(jié)束，如若不然，該過程不斷重復

12、進行。 其特點是：在每次迭代的時候， 均要檢查每一個樣本分類， 看該分類是否正確，不正確的話，就要在全部的樣本中進行調(diào)整，調(diào)整好后，對聚類的中心進行修 改，再進行下一次迭代；如若分類正確，聚類的中心就不再調(diào)整了，標準測度函數(shù)也就收斂了，算 法也就結(jié)束了。2.1.2 K均值聚類算法步驟輸入項為：簇的數(shù)目k及包含有n個對象的數(shù)據(jù)的集合。輸出項為：k個簇。具體的方法：1）在數(shù)據(jù)的對象的集合中，任選k個對象作為初始的簇的中心；2）依據(jù)簇中的對象的平均值，為每一個對象重新予以最相似的簇； 3）更新簇的平均值（即計算每一個簇中的對象的平均值）； 4）重復2） 3）兩個步驟； 5） 一直到不再發(fā)生變化為止。

13、Word資料Assign each objects to most similar centerK=2Arbitrarily choose K otject as indal cluster centerreassignUpdate the cluster meansupdEte the cluster means圖1 K-means算法過程示意圖reass ic nFig 1K-means algorithm process diagram2.1.3 K均值聚類算法性能分析優(yōu)點：該算法的運算速度非?？欤移浣Y(jié)構(gòu)也很簡潔；其類簇之間的區(qū)別也很明顯；最重要的是其時間復雜度為O (nkt),所以

14、，在處理大型數(shù)據(jù)集時，它具有可伸縮性和高效性.其中，n是樣本的數(shù)目，k是類簇的數(shù)目，t是迭代的次數(shù)，通常kwn且twn。缺點:該算法需要事先給定簇類的數(shù) 目k;它不適合非凸形狀的簇，也不適合存在大小差別很大的簇的數(shù)據(jù)的集合；其對數(shù)據(jù)集合內(nèi)的噪 聲和離群點的敏感較高，因為此類數(shù)據(jù)也許會對均值造成一定的影響；因為其對初始中心的選擇的 依賴性較強，所以，產(chǎn)生局部的最優(yōu)解發(fā)生的概率非常大。2.2 K-中心點聚類算法2.2.1 K中心點聚類算法5基本原理首先，針對每個類，先為其隨機的選擇一個實際樣本，將其作為初始的中心點，而數(shù)據(jù)集內(nèi)剩余的其他樣本則依據(jù)其與中心點樣本的相似度，將其分配到最相似的中心點所在

15、的簇類內(nèi)，然后，再選擇新的中心點對象將原來的中心點對象替換掉，以此達到提高聚類質(zhì)量(聚類質(zhì)量是由數(shù)據(jù)集 內(nèi)的各個樣本與所屬簇的中心點間的平均相異度來度量的。)的目的，如此反復的選擇，一直到聚類質(zhì)量不再提高為止.用接近聚類中心的一個數(shù)據(jù)對象來表示K中心點聚類算法的簇， 而在K均值聚類算法中，用該簇中數(shù)據(jù)對象的平均值來表示每個簇。2.2.2 最早提出的K中心點聚類算法PAM 6 ( Partioning around Medoid )是最早提出的K中心點聚類算法.其原理為：先為每個類 任選一個代表對象，而剩下的數(shù)據(jù)對象則根據(jù)其與代表對象的距離遠近而相應的加入到最近的類中， 再嘗試著用非代表數(shù)據(jù)對象

16、將代表數(shù)據(jù)對替換掉，如此反復嘗試，直至收斂。Cjifl = Mi, h) - d(h i)Qa = d(j, i)Cjut = rf(7, h)，(j, t)圖2對象i被對象h替換的4種情況示意圖Fig 2 diagram of 4 cases of object I replaced by object h為了判定一個非代表對象 O h是否是當前一個代表對象 O i的好的替代，對于每一個非中心點對 象Oj,下面的四種情況被考慮：第一種情況：假設(shè) Oi被Oh代替作為新的中心點， Oj當前隸屬于中心點對象 Oi。如果Oj離這個新的中心點 Oh最近，那么Oj被分配給Oh。第二種情況：假設(shè)Oi被Oh

17、代替作為新的中心點， 但是Oj當前隸屬于另一個中心點對象Ot, twi。如果Oj依然離Ot最近，那么對象的隸屬不發(fā)生變化。第三種情況：假設(shè) Oi被Oh代替作為新的中心點， Oj當前隸屬于中心點對象 Oi。如果Oj離某個中心點Ot最近，iwt,那么Oj被重新分配給 Ot。第四種情況：假設(shè)Oi被Oh代替作為新的中心點， 但是Oj當前隸屬于另一個中心點對象Ot, twi。如果Oj離這個新的中心點 Oh最近，那么Oi被重新分配給 Oh。2.2.3 PAM 算法步驟輸入項為：簇的數(shù)目k及包含有n個對象的數(shù)據(jù)的集合。輸出項為：k個簇。具體的方法：1）在數(shù)據(jù)的對象的集合中，任選 k個對象作為初始的簇的中心；

18、2)對每一個由非中心對象 h和中心對象i,計算i被h替代的總代價Tcih= jCjih；3)對每一個有h和i組成的對象對，如果 Tcih<0,i被h替換，然后將每一個非中心點對象根據(jù)與中心點 的距離分配給離它最近的中心點； 4)重復2) 3)兩個步驟；5) 一直到不再發(fā)生變化為止。2.2.4 K中心點聚類算法性能分析K中心點聚類算法有很強的魯棒性，因為它用簇內(nèi)真實樣本作為簇中心，這樣可以降低噪音及離群點對聚類結(jié)果做產(chǎn)生的影響.但缺點是，它不適合于大型的數(shù)據(jù)集，由其初始的中心是隨機選的，仍會存在局部最優(yōu)解，且時間復雜度為O (k(n-k) 2),時間復雜度較大。由此看來，只要確定恰當?shù)木垲?/p>

19、數(shù)目k值及初始的聚類中心點，才能加快聚類過程的收斂的速度，以提高聚類的效率。2.3 K-眾數(shù)聚類算法KModes聚類算法7是通過對KMeans聚類算法的擴展，使其應用于分類屬性數(shù)據(jù)聚類.它采用簡單匹配方法度量同一分類屬性下兩個屬性值之間的距離，用 Mode代替K Means聚類算法 中的Means ,通過基于頻率的方法在聚類過程中不斷更新Modes .相關(guān)性d的計算公式是比較兩記錄之間所有屬性，如果屬性不同則給 d加1,如相同則不加，所以d越大，記錄間的不相關(guān)程度越強。假設(shè) X, Y是數(shù)據(jù)集中的兩個對象，它們用 m維屬性描述，m則這兩個對象之間的相異度為：d(X,Y)=(xj,yj),當xj=

20、yj時，(xj,yj)=0；當Xjyj時，j 1(xj,yj)=1。更新modes ,使用一個簇的每個屬性出現(xiàn)頻率最大的那個屬性值作為代表簇的屬性值(如a,1a,2b,1a,1c,3代表模式為a,1 )。重新調(diào)整記錄所屬的簇，直到不會再產(chǎn)生變化。2.4 K-prototypes聚類算法K-Prototype 算法網(wǎng)是結(jié)合K-Means與K-modes算法，針對混合屬性的。解決兩個核心問題如 下： 度量具有混合屬性的方法是，數(shù)值屬性采用 K-means方法得到P1,分類屬性采用K-modes方法P2 , 那么D=P1+a*P2,a是權(quán)重。如果覺得分類屬性重要，則增加 a,否則減少a,a=0時即只

21、有數(shù)值屬性； 更新一個簇的中心的方法，是結(jié)合K-Means與K-modes的更新。2.5 基于劃分的聚類算法研究現(xiàn)狀近幾年來，人們對于基于劃分的聚類挖掘技術(shù)的研究，研究最多的、發(fā)展較快的也就是對K均值聚類算法的改進.Mac Queen 在1967年提出了 K均值聚類算法的概念，但該算法不能發(fā)現(xiàn)非凸面，而且，對噪聲數(shù)據(jù)的敏感過強.于是，學者們又對其進行改進，在1990年的時候，Rousseeuw等人提出了 PAM 和CLARA (Clustering Large Applications )算法。國內(nèi)外研究者們大都把目光 集中在聚類中心的初始化和聚類數(shù)目k值的確定問題上，但是，聚類中心的初始化和

22、聚類數(shù)目k值并沒有普遍適用的解決的辦法。2.5.1 關(guān)于聚類中心初始化的改進1) Forgy最早提出任選k個數(shù)據(jù)對象，將其作為初始聚類的中心(也有人把隨機的選擇初始聚 類中心的方法稱之為FA ( ForgyApproach ) ) ; 2)根據(jù)最大距離和最小距離的聚類方法來尋找聚 類的中心，以此來確定初始的聚類中心，如BKMishra 等人于2012 年提出的Far Efficient K-Means聚類算法；3)直觀的用將預理數(shù)據(jù)集內(nèi)的混合樣本分成k類的方法，計算出各個類的均值，將其作為初始的聚類中心；4)最具有代表性的基于數(shù)據(jù)采樣的方法就是Bradley 等人提出的RA算法；5)通過“密度

23、法”選擇數(shù)據(jù)樣本，將該樣本作為初始的聚類中心.2008年的時候，Park等人對密度提出了一種全新的定義9,計算的數(shù)據(jù)集中了所有數(shù)據(jù)對象的密度，且選密度最小的k個數(shù)據(jù)對象，將它們作為初始的聚類中心；6)用全局的思想來初始化聚類中心。Likas等學者發(fā)明了全局K均值聚類的算法，該算法是根據(jù)遞增的思想提出的，把 k個簇的聚類問題轉(zhuǎn)變成一系列的子聚類的問題， 先從一個簇的聚類問題開始，每增加一個簇，就用迭代的方法求出k個簇的聚類問題.后來，許多學者對該算法進行研究，并在它白基礎(chǔ)上做了一些改進；7)多次對初始值進行選擇和聚類，將最優(yōu)的聚類結(jié)果找出。2.5.2 關(guān)于聚類數(shù)目k值的確定G.W.Milliga

24、n 10在1985年時就最先提出了通過測試的方法來得到最佳的聚類數(shù)目k值的思想.其思想就是：對一定范圍內(nèi)的所有的聚類數(shù)目進行測試，觀察它們的收斂速度，得出最優(yōu)的k值。緊接著，Xu使用一種被稱之為次勝者受罰的競爭的學習規(guī)則來自動的決定類的適當數(shù)目。其思想 就是:對每個輸入，競爭獲勝的單元的權(quán)值將被修正以適應輸入值，次勝的單元將采用懲罰的方式使其遠離輸入值。后期，S.Ray等人研究出了一種新的確定最優(yōu)k值的方法，它是基于Milligan 而提出的.其思想為：主要考慮類內(nèi)和類間的距離，認定類內(nèi)足夠緊湊且類間足夠分離時，此時的k值是最優(yōu)的.他們還引入了 v (validity )值，v值表示類內(nèi)的距離

25、與類間的距離的比值，在迭代時計算出 k值最小的時候，其對應的 k值，此k值就是最優(yōu)的k值。根據(jù)方差分析的理論，孫才志等人提出 了應用混合F統(tǒng)計量來確定最佳的分類數(shù)，不僅如此，他還應用模糊劃分嫡來驗證最佳的分類數(shù)正確與否。2.6 其他對于K-均值聚類算法的改進針對K-均值聚類算法極易陷入局部最優(yōu)解的問題，劉偉民等研究人員將K-均值算法和模擬退火算法進行結(jié)合，得出一種新的算法，以模擬退火算法的全局尋找最優(yōu)解的能力來解決此問題。為防 止算法陷入到局部極小值，加快收斂的速度，劉韜將一種免疫的計算方法與K-均值聚類算法結(jié)合起來，為每一個抗體的親和度及濃度進行了重新定義，對繁殖率的計算及復制和變異的方法進

26、行了重新的設(shè)計。面對K-均值聚類算法對其它形狀的類簇不敏感或不識別的問題，于是，易云飛又一次對 K-均值聚類算法進行了改進，它用復合形粒子群的算法對聚類的初始中心點進行選取，再通過執(zhí)行 K-均值聚類算法，最終得到聚類的結(jié)果。鄭超等人對粗糙集進行了改進，將其與K-均值聚類算法結(jié)合起來，提出了一種全新的算法.該算法對每個樣本點所在的區(qū)域的密度值進行了考慮，在求均值點過程中加入了權(quán)重的計算，規(guī)避了噪音點數(shù)據(jù)對聚類結(jié)果產(chǎn)生的影響。3基于劃分的聚類分析技術(shù)具體應用多數(shù)學者對基于劃分的聚類算法的研究大都在對算法的改進方面，而將算法應用于具體領(lǐng)域的 很少?，F(xiàn)在該算法的應用方向集中在圖像的分割與識別、文本的聚

27、類、基于聚類的入侵檢測、空間的約束聚類等方面.Cui Xiao-hui 11將PSO、K-means 和混合PSO算法應用于四種不同的文本文 件，并對其數(shù)據(jù)集進行聚類，聚類后，經(jīng)比較分析，混合PSO算法得到的聚簇結(jié)果非常緊致，而且用時非常短。文獻中，學者們把PSO與K-means方法結(jié)合起來，新發(fā)明了一種 PSO-KM的聚類算法，并將該算法應用于無監(jiān)督的異常的入侵檢測當中。其優(yōu)點是與輸入樣本和初始的權(quán)值的選擇無 直接的聯(lián)系，全局搜索能力比 K-means 強。將該算法在KDD Cup 1999 數(shù)據(jù)集上做實驗，結(jié)果顯 示:誤報率2.8%時，檢測率則為86%;此方法對Probe、Dos、U2R攻

28、擊類型的檢測最為有效，正確 度可達到78% (U2R)到94% (Dos) 。 X光圖像中的魚骨檢測技術(shù)就是用基于質(zhì)心劃分的PSO聚類做的。面對X光圖像的灰度值分布的問題，是用高斯分布的工具與形態(tài)學的方法相結(jié)合，結(jié)合后將其應用于圖像的預處理，以此來消減圖像數(shù)據(jù)的規(guī)模，從而得到一個有效的區(qū)域。PSO聚類方法的作用則是將有效的區(qū)域分割成為不同的簇。與傳統(tǒng)的圖像分割技術(shù)Mean Shift比較，改良后的方法更為有效。3.結(jié)語本文在查閱大量文獻、資料、書籍的基礎(chǔ)上，對基于劃分的聚類算法進行了系統(tǒng)的學習和總結(jié)， 主要對聚類的定義及聚類算法的種類進行了介紹，并對K均值聚類算法和K中心點聚類算法的基本原理進

29、行了詳細闡述，還對它們的性能進行了分析，梳理了基于劃分的聚類算法的研究現(xiàn)狀，最后， 對其應用做了簡要介紹.經(jīng)過歸納與總結(jié)，基于劃分的聚類算法主要有以下幾方面研究方向：1)如何解決基于劃分的聚類算法所不能解決的凸型聚類以外的子樣集合問題；2)怎樣選擇值，使基于劃分的聚類算法得以優(yōu)化，性能更佳；3)如何選取初始的中心點，更大程度的增強基于劃分的聚類算法的聚類效果；4)怎樣對算法做出改進，使其能從各種聚類的結(jié)果中，篩選出或確定出最佳的聚類的 分布。參考文獻：1 QIAN Wei-ning , ZHOU Ao-ying. Analyzing Popular Clustering Algorithms from DifferentViewpointsJ.軟件學報,Vol.13,No.8