賈璦瑋

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

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

1 聚類概述

1.1 定義

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

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

1.2 聚類算法的種類

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

1.2.1 劃分方法（partitioning methods）

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

1.2.2 層次方法（hierarchical methods）

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

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

大多數(shù)的聚類算法都是用距離來描述數(shù)據(jù)間的相似性性質(zhì)的，這些方法只能發(fā)現(xiàn)球狀的類，而在其他形狀的類上，這些算法都無計可施.鑒于此，就只能用密度（密度實際就是對象或數(shù)據(jù)點的數(shù)目）將其的相似性予以取代，該方法就是基于密度的聚類算法。密度的方法的思想：一旦“領(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ù)，也許是其它.其潛在的假定為:一系列概率的分布決定該目標(biāo)數(shù)據(jù)的集合.統(tǒng)計方案、神經(jīng)網(wǎng)絡(luò)方案通常是其研究的兩種方向。

2 基于劃分的聚類算法

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

2.1 K均值聚類算法

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

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

2.1.2 K均值聚類算法步驟

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

輸出項為:k個簇。

具體的方法:

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

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

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

4）重復(fù) 2）3）兩個步驟；

5）一直到不再發(fā)生變化為止。

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

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

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

2.2 K中心點聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 基于劃分的聚類算法研究現(xiàn)狀

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

2.3.1 關(guān)于聚類中心初始化的改進

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

2.3.2 關(guān)于聚類數(shù)目k值的確定

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

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

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

3 基于劃分的聚類分析技術(shù)具體應(yīng)用

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

4 結(jié)束語

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

[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.