1、文獻閱讀報告課程名稱 ：模式識別 課程編號 ：題目 :基于劃分的聚類算法研究生姓名 :學 號:論文評語 :成 績:任課教師 :評閱日期 :.專業整理 .學習幫手 .專業整理 .基于劃分的聚類算法2016-11-20摘要 :聚類分析是數據挖掘的一個重要研究分支，已經提出了許多聚類算法，劃分方法是其中之一。基于劃分的聚類算法就是用統計分析的方法研究分類問題。本文介紹了聚類的定義以及聚類算法的種類，詳細闡述了K均值聚類算法和K 中心點聚類算法的基本原理并對他們的性能進行分析，對近年來各學者對基于劃分的聚類算法的研究現狀進行梳理，對其具體應用實例作簡要介紹。關鍵字 ： 數據挖掘 ；聚類； K 均值聚類

2、算法； K 中心點聚類算法； K眾數算法 ； k多層次聚類算法Partitional clustering algorithmsAbstract:Clustering analysis is an important branch of data mining, many clustering algorithms have beenproposed, the dividing method is one of them. Based on the clustering algorithm is divided into classificationproblems using the met

3、hod of statistical analysis. In this paper， we introduces the definition of clustering andtype of clustering algorithm，the basic principle of k-means clustering algorithm and K-center clusteringalgorithm are expounded in detail，we also analyze their performance， the scholars in recent years the stud

4、y ofthe clustering algorithm based on partitioning present situation has carried on the comb， make a briefintroduction to its specific application instance.Keywords:Datamining ； clustering ； k-meansclusteringalgorithms； k-medoidsclusteringalgorithms；k-modes clustering algorithms ;k-prototype cluster

5、ing algorithms1. 引言把單個的數據對象的集合劃分為相類似的樣本組成的多個簇或多個類的過程，這就叫聚類 1 。在無監督的情況下，具有獨立的學習能力，這就是聚類 。將數據空間中的所有數據點分別劃分到不同的類中 ，相近距離的劃分到相同類，較遠距離的劃分到不同類，這就是聚類的目的.聚類分析常作為一種數據的預處理過程被用于許多應用當中，它是更深一步分析數據、處理數據的基礎。人們通過聚類分析這一最有效的手段來認識事物、探索事物之間的內在聯系，而且，關聯規則等分析算.學習幫手 .專業整理 .法的預處理步驟也可以用它。現在 ，在氣象分析中 ，在圖像處理時 ，在模式識別領域，在食品檢驗過程中 ，

6、都有用到它 。 隨著現代科技水平的不斷提高、網絡的迅猛發展、計算機技術的不斷改革和創新 ，大批量的數據不斷涌現。怎樣從這些數據中提取有意義的信息成為人們關注的問題。這對聚類分析技術來說無疑是個巨大的挑戰。 只有具有處理高維的數據的能力的聚類算法才能解決該問題.研究者們開始設計各種聚類算法，于是，基于劃分的聚類算法便應運而生，而且 ，取得了很好的效果。2. 正文1 聚類概述1.1 定義聚類的定義 2 為 :在已知的數據的集合中，尋找數據點集的同類的集合.其中，每一個數據集合為一個類 ，還確定了一個區域，區域中的對象的密度高于其他區域中的對象的密度.聚類的實質就是 “把數據集合中的所有數據分成許多

7、的類簇，其中必有一個類簇內的實體它們都是相似的，而其它不同類簇的實體它們是不相似的；一個類簇是被測試空間中的點的會聚，而且 ，同一個類簇的任意兩個點之間的距離小于不同的類簇的任意兩個點之間的距離；一個包含的密度相對較高的點集的多維空間中的連通區域可以被描述為一個類簇，這時 ，它們可以借助包含的密度相對較低的點集的區域與其他的區域分離開來。”1.2 聚類算法的種類截止目前 ，經典的聚類方法3 有基于劃分的方法 ，也有基于層次的方法，更有基于密度的方法，還有基于網格的方法及基于模型的方法。1.2.1 劃分方法 (partitioning methods).學習幫手 .專業整理 .給定一個數據集D

8、，其包含有 n 個數據對象 ，用一個劃分方法來構建數據的k 個劃分 ， 每一個劃分表示一個類，且 kn。 即它將數據對象劃分為個簇，并滿足以下兩點要求:1）每一個組至少包含一個數據對象；2 ）每一個數據對象必須屬于某一個組.假定要構建的劃分其數目為k，劃分方法就是 :首先 ，先創建一個初始的劃分，然后，再采用一種迭代的重定位的技術，通過將數據對象在劃分間來回的移動來改進劃分.一個好劃分的準則為:同一類中的數據對象之間要盡可能的“接近 ”，而不同的類中的數據對象之間要盡可能的“遠離 ”。1.2.2 層次方法 (hierarchical methods)對給定的數據對象的集合進行層次的分解就是層次

9、的方法.依據層次分解的形成過程，該方法可分為凝聚的層次聚類和分裂的層次聚類兩類. 自底向上進行的層次分解為凝聚的（ agglomerative）層次聚類 ；自頂向下進行的層次分解為分裂的（ divisive ） 層次聚類 . 分裂的層次聚類先把全體對象放在一個類中，再將其漸漸地劃分為越來越小的類，依此進行 ，一直到每一個對象能夠自成一類.而凝聚的層次聚類則是先將每一個對象作為一個類， 再將這些類逐漸地合并起來形成相對較大的類，依此進行 ，一直到所有的對象都在同一個類中方結束。1.2.3 密度方法 (density-based methods)大多數的聚類算法都是用距離來描述數據間的相似性性質的

10、，這些方法只能發現球狀的類，而在其他形狀的類上，這些算法都無計可施.鑒于此 ，就只能用密度 （密度實際就是對象或數據點的數目 ）將其的相似性予以取代，該方法就是基于密度的聚類算法。密度的方法的思想：一旦 “領域 ”的密度超過某一個閾值，就將給定的簇繼續的增長.該算法還能有效的去除噪聲。1.2.4 網格的方法 (grid-based methods)先把對象空間量化成有限數目的單元，將其形成一個網格空間，再對該空間進行聚類，這就是網格的方法 .其主要優點為處理速度快，因為它的處理速度只與量化空間中的每一維的單元數目相.學習幫手 .專業整理 .關，而與數據對象的數目無關.1.2.5 模型的方法 (

11、model-based methods)基于模型的方法就是先給每一個聚類假定一個模型，再去尋找能較好的滿足該模型的數據的集合 。 此模型也許是數據點在空間中的密度分布的函數，也許是其它 .其潛在的假定為: 一系列概率的分布決定該目標數據的集合. 統計方案 、神經網絡方案通常是其研究的兩種方向。2基于劃分的聚類算法給定一個數據集D ，其包含有 n個數據對象 ，用一個劃分方法來構建數據的k個劃分 ， 每一個劃分表示一個類，且kn。 根據 D 的屬性 ，使得同一類中的數據對象之間盡可能的“接近 ”，而不同的類中的數據對象之間盡可能的“遠離 ”。2.1 K- 均值聚類算法2.1.1K 均值聚類算法 4

12、 基本原理隨機選 k個點作為初始的聚類的中心點，根據每個樣本到聚類的中心之間的距離，把樣本歸類到相距它距離最近的聚類中心代表的類中，再計算樣本均值.如若相鄰的兩個聚類中心無變化，調整立即結束 ，如若不然 ，該過程不斷重復進行。其特點是 :在每次迭代的時候，均要檢查每一個樣本分類 ，看該分類是否正確，不正確的話 ，就要在全部的樣本中進行調整，調整好后 ，對聚類的中心進行修改 ，再進行下一次迭代；如若分類正確 ，聚類的中心就不再調整了，標準測度函數也就收斂了 ，算法也就結束了。2.1.2K 均值聚類算法步驟輸入項為 :簇的數目 k及包含有 n個對象的數據的集合。輸出項為 :k個簇 。具體的方法 :

13、1）在數據的對象的集合中，任選 k個對象作為初始的簇的中心；.學習幫手 .專業整理 .2）依據簇中的對象的平均值，為每一個對象重新予以最相似的簇；3）更新簇的平均值（即計算每一個簇中的對象的平均值）；4）重復 2） 3）兩個步驟 ；5）一直到不再發生變化為止。圖 1 K-means 算法過程示意圖Fig 1K-means algorithm process diagram2.1.3K 均值聚類算法性能分析優點 :該算法的運算速度非常快，而且其結構也很簡潔；其類簇之間的區別也很明顯；最重要的是其時間復雜度為O（ nkt ），所以 ，在處理大型數據集時，它具有可伸縮性和高效性.其中， n 是樣本的

14、數目 ， k是類簇的數目，t 是迭代的次數 ，通常 k n 且 t n 。 缺點 :該算法需要事先給定簇類的數目 k；它不適合非凸形狀的簇，也不適合存在大小差別很大的簇的數據的集合；其對數據集合內的噪聲和離群點的敏感較高，因為此類數據也許會對均值造成一定的影響；因為其對初始中心的選擇的依賴性較強，所以，產生局部的最優解發生的概率非常大。2.2 K- 中心點聚類算法.學習幫手 .專業整理 .2.2.1K 中心點聚類算法 5 基本原理首先 ，針對每個類 ，先為其隨機的選擇一個實際樣本，將其作為初始的中心點，而數據集內剩余的其他樣本則依據其與中心點樣本的相似度，將其分配到最相似的中心點所在的簇類內，

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

16、表數據對替換掉，如此反復嘗試 ，直至收斂 。.學習幫手 .專業整理 .圖 2 對象 i被對象 h替換的 4種情況示意圖Fig 2 diagram of 4 cases of object I replaced by object h為了判定一個非代表對象Oh 是否是當前一個代表對象Oi 的好的替代 ，對于每一個非中心點對象 Oj，下面的四種情況被考慮：第一種情況 ：假設 Oi 被 Oh 代替作為新的中心點， Oj 當前隸屬于中心點對象 Oi。如果 Oj 離這個新的中心點 Oh 最近，那么 O j 被分配給 Oh。第二種情況 ：假設 Oi 被 Oh 代替作為新的中心點，但是 Oj 當前隸屬于另一

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

18、，任選 k個對象作為初始的簇的中心；2）對每一個由非中心對象h 和中心對象 i,計算 i 被 h替代的總代價 Tcih =jCjih；3）對每一個有 h 和 i組成的對象對，如果 Tcih 0,i 被 h替換 ，然后將每一個非中心點對象根據與中心點的距離分配給離它最近的中心點；4）重復 2） 3）兩個步驟 ；5） 一直到不再發生變化為止。2.2.4 K 中心點聚類算法性能分析K中心點聚類算法有很強的魯棒性，因為它用簇內真實樣本作為簇中心，這樣可以降低噪音及.學習幫手 .專業整理 .離群點對聚類結果做產生的影響.但缺點是 ，它不適合于大型的數據集，由其初始的中心是隨機選的，仍會存在局部最優解，且

19、時間復雜度為O（ k(n-k) 2），時間復雜度較大。由此看來 ，只要確定恰當的聚類數目k 值及初始的聚類中心點，才能加快聚類過程的收斂的速度，以提高聚類的效率。2.3 K- 眾數聚類算法K Modes 聚類算法 7 是通過對 K Means 聚類算法的擴展，使其應用于分類屬性數據聚類它采用簡單匹配方法度量同一分類屬性下兩個屬性值之間的距離，用Mode 代替 K Means 聚類算法中的 Means ，通過基于頻率的方法在聚類過程中不斷更新Modes 相關性 d 的計算公式是比較兩記錄之間所有屬性，如果屬性不同則給d 加 1,如相同則不加 ，所以 d 越大 ，記錄間的不相關程度越強 。 假設

20、X， Y 是數據集中的兩個對象，它們用 m 維屬性描述 ，： d(X,Y)=mjj 時， （ xj ,y j ）=0 ；當 xj則這兩個對象之間的相異度為jj當yj 時，(x, y ) ,x =yj 1（ xj ,y j ）=1 。 更新 modes ，使用一個簇的每個屬性出現頻率最大的那個屬性值作為代表簇的屬性值（如 a,1a,2b,1a,1c,3代表模式為 a,1 ）。 重新調整記錄所屬的簇，直到不會再產生變化。2.4 K-prototypes聚類算法K-Prototype算法 8 是結合 K-Means 與 K-modes 算法 ，針對混合屬性的。解決兩個核心問題如下 :度量具有混合屬性

21、的方法是，數值屬性采用K-means 方法得到 P1，分類屬性采用 K-modes 方法P2，那么 D=P1+a*P2,a 是權重 。 如果覺得分類屬性重要，則增加 a，否則減少 a,a=0 時即只有數值屬性 ；更新一個簇的中心的方法，是結合 K-Means 與 K-modes 的更新 。2.5 基于劃分的聚類算法研究現狀近幾年來 ，人們對于基于劃分的聚類挖掘技術的研究，研究最多的 、發展較快的也就是對K 均.學習幫手 .專業整理 .值聚類算法的改進.Mac Queen在 1967年提出了 K 均值聚類算法的概念， 但該算法不能發現非凸面，而且 ，對噪聲數據的敏感過強.于是 ，學者們又對其進行

22、改進，在 1990年的時候 ，Rousseeuw等人提出了 PAM和 CLARA （ Clustering Large Applications）算法。 國內外研究者們大都把目光集中在聚類中心的初始化和聚類數目k 值的確定問題上，但是 ，聚類中心的初始化和聚類數目 k 值并沒有普遍適用的解決的辦法。2.5.1 關于聚類中心初始化的改進1 ）Forgy最早提出任選k個數據對象 ，將其作為初始聚類的中心（也有人把隨機的選擇初始聚類中心的方法稱之為FA（ ForgyApproach）； 2）根據最大距離和最小距離的聚類方法來尋找聚類的中心 ，以此來確定初始的聚類中心， 如 BKMishra 等人于

23、2012 年提出的 Far EfficientK-Means 聚類算法 ； 3）直觀的用將預理數據集內的混合樣本分成k類的方法 ，計算出各個類的均值，將其作為初始的聚類中心 ； 4 ）最具有代表性的基于數據采樣的方法就是Bradley 等人提出的RA 算法 ； 5）通過 “密度法 ”選擇數據樣本 ，將該樣本作為初始的聚類中心.2008 年的時候 ， Park等人對密度提出了一種全新的定義9 ，計算的數據集中了所有數據對象的密度，且選密度最小的 k個數據對象 ，將它們作為初始的聚類中心； 6）用全局的思想來初始化聚類中心。 Likas 等學者發明了全局 K均值聚類的算法 ，該算法是根據遞增的思想

24、提出的，把 k 個簇的聚類問題轉變成一系列的子聚類的問題 ，先從一個簇的聚類問題開始，每增加一個簇 ，就用迭代的方法求出 k 個簇的聚類問題 .后來 ，許多學者對該算法進行研究，并在它的基礎上做了一些改進； 7）多次對初始值進行選擇和聚類 ，將最優的聚類結果找出。2.5.2 關于聚類數目 k 值的確定G.W.Milligan 10 在1985 年時就最先提出了通過測試的方法來得到最佳的聚類數目k 值的思想 .其思想就是 :對一定范圍內的所有的聚類數目進行測試， 觀察它們的收斂速度 ，得出最優的 k 值 。.學習幫手 .專業整理 .緊接著 ， Xu 使用一種被稱之為次勝者受罰的競爭的學習規則來自

25、動的決定類的適當數目。其思想就是 :對每個輸入 ， 競爭獲勝的單元的權值將被修正以適應輸入值，次勝的單元將采用懲罰的方式使其遠離輸入值。后期， S.Ray等人研究出了一種新的確定最優k 值的方法 ， 它是基于 Milligan而提出的 .其思想為 :主要考慮類內和類間的距離，認定類內足夠緊湊且類間足夠分離時，此時的 k 值是最優的 .他們還引入了 v（ validity ）值，v 值表示類內的距離與類間的距離的比值，在迭代時計算出 k 值最小的時候 ，其對應的 k 值，此k 值就是最優的 k 值。根據方差分析的理論 ，孫才志等人提出了應用混合 F 統計量來確定最佳的分類數 ， 不僅如此 ，他還

26、應用模糊劃分嫡來驗證最佳的分類數正確與否 。2.6 其他對于 K-均值聚類算法的改進針對 K- 均值聚類算法極易陷入局部最優解的問題，劉偉民等研究人員將K- 均值算法和模擬退火算法進行結合 ，得出一種新的算法 ，以模擬退火算法的全局尋找最優解的能力來解決此問題。為防止算法陷入到局部極小值 ，加快收斂的速度 ， 劉韜將一種免疫的計算方法與K- 均值聚類算法結合起來 ， 為每一個抗體的親和度及濃度進行了重新定義，對繁殖率的計算及復制和變異的方法進行了重新的設計 。 面對 K- 均值聚類算法對其它形狀的類簇不敏感或不識別的問題，于是 ，易云飛又一次對 K- 均值聚類算法進行了改進，它用復合形粒子群的

27、算法對聚類的初始中心點進行選取，再通過執行 K- 均值聚類算法 ，最終得到聚類的結果 。 鄭超等人對粗糙集進行了改進，將其與 K-均值聚類算法結合起來 ，提出了一種全新的算法 .該算法對每個樣本點所在的區域的密度值進行了考慮，在求均值點過程中加入了權重的計算，規避了噪音點數據對聚類結果產生的影響。3基于劃分的聚類分析技術具體應用多數學者對基于劃分的聚類算法的研究大都在對算法的改進方面，而將算法應用于具體領域的很少 。 現在該算法的應用方向集中在圖像的分割與識別、文本的聚類 、基于聚類的入侵檢測、空間.學習幫手 .專業整理 .的約束聚類等方面.Cui Xiao-hui11 將 PSO、 K-me

28、ans和混合 PSO 算法應用于四種不同的文本文件，并對其數據集進行聚類，聚類后 ，經比較分析 ，混合 PSO算法得到的聚簇結果非常緊致，而且用時非常短 。 文獻中 ，學者們把 PSO 與 K-means 方法結合起來 ，新發明了一種PSO-KM的聚類算法，并將該算法應用于無監督的異常的入侵檢測當中。其優點是與輸入樣本和初始的權值的選擇無直接的聯系 ，全局搜索能力比K-means強。 將該算法在 KDD Cup 1999數據集上做實驗，結果顯示 :誤報率 2.8% 時，檢測率則為 86% ；此方法對 Probe 、 Dos 、U2R 攻擊類型的檢測最為有效，正確度可達到 78% （ U2R）到

29、 94% （ Dos ）。 X 光圖像中的魚骨檢測技術就是用基于質心劃分的PSO 聚類做的 。 面對 X光圖像的灰度值分布的問題，是用高斯分布的工具與形態學的方法相結合，結合后將其應用于圖像的預處理，以此來消減圖像數據的規模，從而得到一個有效的區域。 PSO 聚類方法的作用則是將有效的區域分割成為不同的簇。與傳統的圖像分割技術 Mean Shift比較，改良后的方法更為有效 。3結語本文在查閱大量文獻、資料、書籍的基礎上 ，對基于劃分的聚類算法進行了系統的學習和總結，主要對聚類的定義及聚類算法的種類進行了介紹， 并對 K 均值聚類算法和 K 中心點聚類算法的基本原理進行了詳細闡述，還對它們的性

30、能進行了分析 ，梳理了基于劃分的聚類算法的研究現狀，最后 ，對其應用做了簡要介紹.經過歸納與總結 ，基于劃分的聚類算法主要有以下幾方面研究方向 :1）如何解決基于劃分的聚類算法所不能解決的凸型聚類以外的子樣集合問題； 2）怎樣選擇值，使基于劃分的聚類算法得以優化，性能更佳 ； 3 ）如何選取初始的中心點 ，更大程度的增強基于劃分的聚類算法的聚類效果； 4 ）怎樣對算法做出改進 ，使其能從各種聚類的結果中，篩選出或確定出最佳的聚類的分布。.學習幫手 .專業整理 .參考文獻 ：1 QIAN Wei-ning , ZHOU Ao-ying. Analyzing Popular Clustering Algorithms from DifferentViewpointsJ