基于劃分的聚類算法研究綜述

賈璦瑋

（陜西師范大學 計算機科學學院，陜西 西安 710062）

把單個的數據對象的集合劃分為相類似的樣本組成的多個簇或多個類的過程，這就叫聚類[1]。 在無監督的情況下，具有獨立的學習能力，這就是聚類。將數據空間中的所有數據點分別劃分到不同的類中，相近距離的劃分到相同類，較遠距離的劃分到不同類，這就是聚類的目的.聚類分析常作為一種數據的預處理過程被用于許多應用當中，它是更深一步分析數據、處理數據的基礎。人們通過聚類分析這一最有效的手段來認識事物、探索事物之間的內在聯系，而且，關聯規則等分析算法的預處理步驟也可以用它。現在，在氣象分析中，在圖像處理時，在模式識別領域，在食品檢驗過程中，都有用到它。隨著現代科技水平的不斷提高、網絡的迅猛發展、計算機技術的不斷改革和創新，大批量的數據不斷涌現。怎樣從這些數據中提取有意義的信息成為人們關注的問題。這對聚類分析技術來說無疑是個巨大的挑戰。只有具有處理高維的數據的能力的聚類算法才能解決該問題.研究者們開始設計各種聚類算法，于是，基于劃分的聚類算法便應運而生，而且，取得了很好的效果。

1 聚類概述

1.1 定義

聚類的定義為:在已知的數據的集合中，尋找數據點集的同類的集合.其中，每一個數據集合為一個類，還確定了一個區域，區域中的對象的密度高于其他區域中的對象的密度.

聚類的實質就是“把數據集合中的所有數據分成許多的類簇，其中必有一個類簇內的實體它們都是相似的，而其它不同類簇的實體它們是不相似的；一個類簇是被測試空間中的點的會聚，而且，同一個類簇的任意兩個點之間的距離小于不同的類簇的任意兩個點之間的距離；一個包含的密度相對較高的點集的多維空間中的連通區域可以被描述為一個類簇，這時，它們可以借助包含的密度相對較低的點集的區域與其他的區域分離開來?！?/p>

1.2 聚類算法的種類

截止目前，經典的聚類方法有基于劃分的方法，也有基于層次的方法，更有基于密度的方法，還有基于網格的方法及基于模型的方法。

1.2.1 劃分方法（partitioning methods）

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

1.2.2 層次方法（hierarchical methods）

對給定的數據對象的集合進行層次的分解就是層次的方法.依據層次分解的形成過程，該方法可分為凝聚的層次聚類和分裂的層次聚類兩類.自底向上進行的層次分解為凝聚的（agglomerative）層次聚類；自頂向下進行的層次分解為分裂的（divisive）層次聚類.分裂的層次聚類先把全體對象放在一個類中，再將其漸漸地劃分為越來越小的類，依此進行，一直到每一個對象能夠自成一類.而凝聚的層次聚類則是先將每一個對象作為一個類，再將這些類逐漸地合并起來形成相對較大的類，依此進行，一直到所有的對象都在同一個類中方結束。

1.2.3 密度的方法（density-based methods）

大多數的聚類算法都是用距離來描述數據間的相似性性質的，這些方法只能發現球狀的類，而在其他形狀的類上，這些算法都無計可施.鑒于此，就只能用密度（密度實際就是對象或數據點的數目）將其的相似性予以取代，該方法就是基于密度的聚類算法。密度的方法的思想：一旦“領域”的密度超過某一個閾值，就將給定的簇繼續的增長.該算法還能有效的去除噪聲。

1.2.4 網格的方法（grid-based methods）

先把對象空間量化成有限數目的單元，將其形成一個網格空間，再對該空間進行聚類，這就是網格的方法.其主要優點為處理速度快，因為它的處理速度只與量化空間中的每一維的單元數目相關，而與數據對象的數目無關.

1.2.5 模型的方法（model-based methods）

基于模型的方法就是先給每一個聚類假定一個模型，再去尋找能較好的滿足該模型的數據的集合。此模型也許是數據點在空間中的密度分布的函數，也許是其它.其潛在的假定為:一系列概率的分布決定該目標數據的集合.統計方案、神經網絡方案通常是其研究的兩種方向。

2 基于劃分的聚類算法

給定一個數據集D，其包含有n個數據對象，用一個劃分方法來構建數據的k個劃分，每一個劃分表示一個類，且k≤n。根據D的屬性，使得同一類中的數據對象之間盡可能的“接近”，而不同的類中的數據對象之間盡可能的“遠離”。

2.1 K均值聚類算法

2.1.1 K均值聚類算法基本原理

隨機選k個點作為初始的聚類的中心點，根據每個樣本到聚類的中心之間的距離，把樣本歸類到相距它距離最近的聚類中心代表的類中，再計算樣本均值.如若相鄰的兩個聚類中心無變化，調整立即結束，如若不然，該過程不端重復進行。其特點是:在每次迭代的時候，均要檢查每一個樣本分類，看該分類是否正確，不正確的話，就要在全部的樣本中進行調整，調整好后，對聚類的中心進行修改，再進行下一次迭代；如若分類正確，聚類的中心就不再調整了，標準測度函數也就收斂了，算法也就結束了。

2.1.2 K均值聚類算法步驟

輸入項為:簇的數目k及包含有n個對象的數據的集合。

輸出項為:k個簇。

具體的方法:

1）在數據的對象的集合中，任選k個對象作為初始的簇的中心；

2）依據簇中的對象的平均值，為每一個對象重新予以最相似的簇；

3）更新簇的平均值 （即計算每一個簇中的對象的平均值）；

4）重復 2）3）兩個步驟；

5）一直到不再發生變化為止。

2.1.3 K均值聚類算法性能分析

優點:該算法的運算速度非常快，而且其結構也很簡潔；其類簇之間的區別也很明顯；最重要的是其時間復雜度為O（nkt），所以，在處理大型數據集時，它具有可伸縮性和高效性.其中，n是樣本的數目，k是類簇的數目，t是迭代的次數，通常 k≤n 且 t≤n。

缺點:該算法需要事先給定簇類的數目k；它不適合非凸形狀的簇，也不適合存在大小差別很大的簇的數據的集合；其對數據集合內的噪聲和離群點的敏感較高，因為此類數據也許會對均值造成一定的影響；因為其對初始中心的選擇的依賴性較強，所以，產生局部的最優解發生的概率非常大。

2.2 K中心點聚類算法

2.2.1 K中心點聚類算法的基本原理

首先，針對每個類，先為其隨機的選擇一個實際樣本，將其作為初始的中心點，而數據集內剩余的其他樣本則依據其與中心點樣本的相似度，將其分配到最相似的中心點所在的簇類內，然后，再選擇新的中心點對象將原來的中心點對象替換掉，以此達到提高聚類質量（聚類質量是由數據集內的各個樣本與所屬簇的中心點間的平均相異度來度量的。）的目的，如此反復的選擇，一直到聚類質量不再提高為止.用接近聚類中心的一個數據對象來表示K中心點聚類算法的簇，而在K均值聚類算法中，用該簇中數據對象的平均值來表示每個簇。

2.2.2 最早提出的K中心點聚類算法

PAM（Partioning around Medoid）是最早提出的K中心點聚類算法.其原理為:先為每個類任選一個代表對象，而剩下的數據對象則根據其與代表對象的距離遠近而相應的加入到最近的類中，再嘗試著用非代表數據對象將代表數據對象替換掉，如此反復嘗試，直至收斂。

圖1 PAM算法過程示意圖Fig.1 PAM algorithm process diagram

假定Orandom表示非聚類代表對象，Oj表示聚類代表對象，為確定任一Orandom是否可替換當前Oj，需根據以下4種情況來分別對各非聚類代表對象P進行檢查。

1）若P當前屬于Oj所代表的聚類，且若用Orandom替換Oj，將Orandom作為新聚類的代表，而P則更接近于其他Oi，其中（i≠j），那么則將P歸類到Oi所代表的聚類當中。

2）若P當前屬于Oj所代表的聚類，且若用Orandom替換Oj，將Orandom作為新聚類的代表，而 P則更接近 Orandom，那么則將P歸類到Orandom所代表的聚類當中.

3）若 P當前屬于 Oi所代表的聚類，其中（i≠j）， 且若用Orandom替換Oj，將Orandom作為新聚類的代表，而P仍然最接近Oi，那么P的歸類將不發生任何變化.

4）若 P當前屬于 Oi所代表的聚類，其中（i≠j）， 且若用Orandom替換Oj，將Orandom作為新聚類的代表，而P最更接近Orandom，那么則將P歸類到Orandom所代表的聚類當中.

構成成本函數的方差會隨著每次對對象進行重新歸類的時候而發生變化，于是，成本函數可以計算出聚類代表替換前和替換后的方差的變化.成本函數的輸出可以通過替換掉不合適的代表而使距離方差發生變化的累計而構成。整個輸出成本為負值時，用Orandom替換Oj，以達到減少實際方差E的目的。整個輸出成本為正值是，可認為當前Oj可接受，本次循環無需再做變動。

2.2.3 新興進化的K中心點聚類算法

圖2 粒子空間變化示意圖Fig.2 Particles schematic space change

1995年，James Kennedy等人受到鳥群覓食行為的啟發，提出了一種模擬社會行為的進化的計算方法PSO（Particle Swarm Optimization）.該算法先初始化為一群隨機的粒子，通過迭代的方法，找到最優的解。每次迭代，粒子都會通過跟蹤兩個極值以此來更新自己:一個極值為粒子本身找到的最優解，該解被稱為個體極值，而另一極值則是整個種群目前所找到的最優的解，該極值被稱為全局極值.粒子在空間中的速度變化如圖2所示。

粒子將按照以下公式更新自己的速度和位置，以此來尋找到上述兩個最優值:

上述（1）、（2）式中，c1和 c2是加速常數，通常情況下，c1和 c2在[0，4]之間選值，一般情況，取 c1=c2=2；r1和 r2則是[0，1]之間的兩個隨機的數。每一個粒子的位置、速度都會以隨機的方式來初始化，以后，粒子的速度將會朝著全局最優及個體最優的方向而逐步靠近。

2.2.4 K中心點聚類算法性能分析

K中心點聚類算法有很強的魯棒性，因為它用簇內真實樣本作為簇中心，這樣可以降低噪音及離群點對聚類結果做產生的影響.但缺點是，它不適合于大型的數據集，由其初始的中心是隨機選的，仍會存在局部最優解，且時間復雜度為O（k（n-k）2），時間復雜度較大。 由此看來，只要確定恰當的聚類數目k值及初始的聚類中心點，才能加快聚類過程的收斂的速度，以提高聚類的效率。

2.3 基于劃分的聚類算法研究現狀

近幾年來，人們對于基于劃分的聚類挖掘技術的研究，研究最多的、發展較快的也就是對K均值聚類算法的改進.Mac Queen在1967年提出了K均值聚類算法的概念，但該算法不能發現非凸面，而且，對噪聲數據的敏感過強.于是，學者們又對其進行改進，在1990年的時候，Rousseeuw等人提出了PAM和CLARA（Clustering Large Applications）算法。國內外研究者們大都把目光集中在聚類中心的初始化和聚類數目k值的確定問題上，但是，聚類中心的初始化和聚類數目k值并沒有普遍適用的解決的辦法[2]。

2.3.1 關于聚類中心初始化的改進

1）Forgy最早提出任選k個數據對象，將其作為初始聚類的中心（也有人把隨機的選擇初始聚類中心的方法稱之為FA（ForgyApproach））；2）根據最大距離和最小距離的聚類方法來尋找聚類的中心，以此來確定初始的聚類中心，如BK Mishra等人于2012年提出的Far Efficient K-Means聚類算法；3）直觀的用將預理數據集內的混合樣本分成k類的方法，計算出各個類的均值，將其作為初始的聚類中心；4）最具有代表性的基于數據采樣的方法就是Bradley等人提出的RA算法；5）通過“密度法”選擇數據樣本，將該樣本作為初始的聚類中心.2008年的時候，Park等人對密度提出了一種全新的定義[3]，計算的數據集中了所有數據對象的密度，且選密度最小的k個數據對象，將它們作為初始的聚類中心；6）用全局的思想來初始化聚類中心。Likas等學者發明了全局K均值聚類的算法，該算法是根據遞增的思想提出的，把k個簇的聚類問題轉變成一系列的子聚類的問題，先從一個簇的聚類問題開始，每增加一個簇，就用迭代的方法求出k個簇的聚類問題.后來，許多學者對該算法進行研究，并在它的基礎上做了一些改進；7）多次對初始值進行選擇和聚類，將最優的聚類結果找出。

2.3.2 關于聚類數目k值的確定

G.W.Milligan[4]在1985年時就最先提出了通過測試的方法來得到最佳的聚類數目k值的思想.其思想就是:對一定范圍內的所有的聚類數目進行測試，觀察它們的收斂速度，得出最優的k值。緊接著，Xu使用一種被稱之為次勝者受罰的競爭的學習規則來自動的決定類的適當數目。其思想就是:對每個輸入，競爭獲勝的單元的權值將被修正以適應輸入值，次勝的單元將采用懲罰的方式使其遠離輸入值。后期，S.Ray等人研究出了一種新的確定最優k值的方法，它是基于Milligan而提出的.其思想為:主要考慮類內和類間的距離，認定類內足夠緊湊且類間足夠分離時，此時的k值是最優的.他們還引入了v（validity）值，v值表示類內的距離與類間的距離的比值，在迭代時計算出k值最小的時候，其對應的k值，此k值就是最優的k值。根據方差分析的理論，孫才志等人提出了應用混合F統計量來確定最佳的分類數，不僅如此，他還應用模糊劃分嫡來驗證最佳的分類數正確與否。

2.4 其他對于K-均值聚類算法的改進

針對K-均值聚類算法極易陷入局部最優解的問題，劉偉民等研究人員將K-均值算法和模擬退火算法進行結合，得出一種新的算法，以模擬退火算法的全局尋找最優解的能力來解決此問題。為防止算法陷入到局部極小值，加快收斂的速度，劉韜將一種免疫的計算方法與K-均值聚類算法結合起來，為每一個抗體的親和度及濃度進行了重新定義，對繁殖率的計算及復制和變異的方法進行了重新的設計。面對K-均值聚類算法對其它形狀的類簇不敏感或不識別的問題，于是，易云飛又一次對K-均值聚類算法進行了改進，它用復合形粒子群的算法對聚類的初始中心點進行選取，再通過執行K-均值聚類算法，最終得到聚類的結果。鄭超等人對粗糙集進行了改進，將其與K-均值聚類算法結合起來，提出了一種全新的算法.該算法對每個樣本點所在的區域的密度值進行了考慮，在求均值點過程中加入了權重的計算，規避了噪音點數據對聚類結果產生的影響。

3 基于劃分的聚類分析技術具體應用

多數學者對基于劃分的聚類算法的研究大都在對算法的改進方面，而將算法應用于具體領域的很少。現在該算法的應用方向集中在圖像的分割與識別、文本的聚類、基于聚類的入侵檢測、空間的約束聚類等方面.Cui Xiao-hui[5]將PSO、K-means和混合PSO算法應用于四種不同的文本文件，并對其數據集進行聚類，聚類后，經比較分析，混合PSO算法得到的聚簇結果非常緊致，而且用時非常短。文獻[6]中，學者們把PSO與K-means方法結合起來，新發明了一種PSO-KM的聚類算法，并將該算法應用于無監督的異常的入侵檢測當中.其優點是與輸入樣本和初始的權值的選擇無直接的聯系，全局搜索能力比K-means強.將該算法在KDD Cup 1999數據集上做實驗，結果顯示:誤報率2.8%時，檢測率則為86%；此方法對Probe、Dos、U2R攻擊類型的檢測最為有效，正確度可達到 78%（U2R）到 94%（Dos）。X光圖像中的魚骨檢測技術就是用基于質心劃分的PSO聚類做的[7]。面對X光圖像的灰度值分布的問題，是用高斯分布的工具與形態學的方法相結合，結合后將其應用于圖像的預處理，以此來消減圖像數據的規模，從而得到一個有效的區域。PSO聚類方法的作用則是將有效的區域分割成為不同的簇。與傳統的圖像分割技術Mean Shift比較，改良后的方法更為有效。

4 結束語

本文在查閱大量文獻、資料、書籍的基礎上，對基于劃分的聚類算法進行了系統的學習和總結，主要對聚類的定義及聚類算法的種類進行了介紹，并對K均值聚類算法和K中心點聚類算法的基本原理進行了詳細闡述，還對它們的性能進行了分析，梳理了基于劃分的聚類算法的研究現狀，最后，對其應用做了簡要介紹.經過歸納與總結，基于劃分的聚類算法主要有以下幾方面研究方向:1）如何解決基于劃分的聚類算法所不能解決的凸型聚類以外的子樣集合問題；2）怎樣選擇值，使基于劃分的聚類算法得以優化，性能更佳；3）如何選取初始的中心點，更大程度的增強基于劃分的聚類算法的聚類效果；4）怎樣對算法做出改進，使其能從各種聚類的結果中，篩選出或確定出最佳的聚類的分布.

[1]HAN Jia-wei，MICHELINE K.Data mining:concepts and techniques[M].San Francisco:Morgan Kaufmann Pubishers，2001.

[2]Duda R O，Hart P E．Pattem Classification and scene Analysis[M].New York:John Wiley and Sons，1973.

[3]Park H S，Jun C H.A simple and fast algorithm for K-medoids clustering[J].Expert Systems with Applications，2009，36（2）:3336-3341.

[4]Milligan G W，Cooper M C.Methodology Review:Clustering Methods[J].Applied Psychological Measurement，1987，11（4）:329-354.

[5]CUI Xiao-hui，POTOK T E.Document clustering analysis based on hybrid PSO+K-means algorithm [J].Journal of Computer Sciences:Special Issue，2006（4）:27-33.

[6]XIAO Li-zhong，SHAO Zhi-qing，LIU Gang.K-means algotithm based on particle swarm optimization algorithm for anomaly intrusion detection [C]//Proc of the 6th World Congress on Intelligent Control and Automation，2006:5854-5858.

[7]HAN Yan-fang，SHI Peng-fei.An efficient approach for fish bone detection based on image preprocessing and particle swarm clustering [C]//Advanced Intelligent Computing Theories and Applications，with Aspects of Contemporary Intelligent Computing Techniques.Berlin:Springer，2007:940-948.

[8]CUI Xiao-hui，POTOK T E.Document clustering analysis based on hybrid PSO+K-means algorithm [J].Journal of Computer Sciences:Special Issue，2006（4）:27-33.

[9]Huang Z.Extensions to the k-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery，1998：283-304.