聚類算法綜述

王玉晗 羅鄧三郎

摘 要：在數(shù)據(jù)挖掘中，聚類有著非常重要的地位。本文分別介紹了基于劃分、基于層次、基于密度、基于網(wǎng)格和基于模型的聚類方法。對這五類聚類方法中的典型算法的聚類思想和特點做了相應(yīng)的介紹，并分析了算法的優(yōu)缺點，對聚類算法做了初步的總結(jié)。在具體問題的應(yīng)用中，需多方面考慮算法的特性才能得到最佳聚類結(jié)果。

關(guān)鍵詞：數(shù)據(jù)挖掘 聚類 密度 模型

中圖分類號：G71 文獻標(biāo)識碼：A 文章編號：1672-3791（2018）08（c）-0010-02

隨著科技的發(fā)展，目前已步入大數(shù)據(jù)的時代，數(shù)據(jù)中包含的信息具有很高的價值。通過聚類分析，數(shù)據(jù)對象被劃分為具有現(xiàn)實意義的組（集群），有助于人類分析和描述世界。聚類分析在心理學(xué)研究中、生物學(xué)研究中和模式識別以及數(shù)據(jù)挖掘等領(lǐng)域中都起著重要的作用。

聚類分析僅通過描述對象和其關(guān)系的數(shù)據(jù)信息，期望將對象劃分為多個組，使得組內(nèi)對象相似，組間對象不同。聚類的定義最早由Everitt在1974年提出，要求組內(nèi)對象在空間中相對緊湊，組內(nèi)任意兩對象間的距離小于不同組的任意兩對象間的距離。在實際應(yīng)用中，聚類的定義通常不精確，最優(yōu)的定義取決于聚類對象的性質(zhì)和期望得到的結(jié)果。

根據(jù)聚類算法中對象間相似度的計算方式以及聚類結(jié)果中對象的關(guān)系可以將聚類算法分為劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法[1]。

1 聚類方法

1.1 基于劃分的聚類方法

基于劃分的聚類方法只是將數(shù)據(jù)對象集合劃分為若干個無交集的子集（簇），使得每個對象僅屬于一個子集。主要包括K-Means算法、K-modes算法、PAM算法和CLARA算法等。

K-Means算法是一個基于原型的劃分聚類算法，通過對象間的距離評價對象間的相似度，距離越近，對象間相似度越大，反之則越小。用戶需要預(yù)先指定需要劃分的簇數(shù)k和每簇質(zhì)心的初值，其思想如下：先選取k個數(shù)據(jù)作為k個簇的質(zhì)心，計算數(shù)據(jù)集中每個對象到質(zhì)心的距離，按照距離將其歸類，完成后重新計算每個簇的質(zhì)心，直到聚類結(jié)果不再發(fā)生變化為止。K-Means聚類算法的優(yōu)點主要為算法運算快速且簡單，對于數(shù)據(jù)較多的數(shù)據(jù)集有較高的聚類效率，具有可伸縮性。確定質(zhì)心初值的主要方法有：（1）根據(jù)數(shù)據(jù)對象的性質(zhì)和分布憑主觀經(jīng)驗選取。（2）將數(shù)據(jù)對象隨機分成k類，把每類的重心作為質(zhì)心初值。（3）按密度大小選取質(zhì)心初值。聚類結(jié)果對質(zhì)心初值的選擇敏感，選用不同質(zhì)心初值可能得到不同的結(jié)果。數(shù)據(jù)集中的噪點和孤立點也會影響K-Means算法的聚類結(jié)果。

1.2 基于層次的聚類方法

層次聚類把數(shù)據(jù)對象構(gòu)建成一組具有樹狀結(jié)構(gòu)的嵌套簇，除了葉子節(jié)點的每個簇都是由其子節(jié)點（子簇）的并集構(gòu)成，根節(jié)點包含所有的數(shù)據(jù)對象。根據(jù)層次分解的過程一般分為兩類：（1）凝聚。從僅包含單個數(shù)據(jù)對象的簇開始，每次合并最接近的一對簇，直至簇中包含所有數(shù)據(jù)對象為止。（2）分裂。從一個包含所有數(shù)據(jù)對象的簇開始，每次對簇進行分割，直至簇中僅包含一個數(shù)據(jù)對象為止。樹狀圖是層次聚類結(jié)果常用的表示方式。層次聚類方法主要包括單鏈接聚類、CURE算法、BIRCH算法和ROCK算法等。

單鏈接聚類基于自底向上方式對數(shù)據(jù)對象進行分類，在聚類過程的開始，每個元素都在自己的簇中。然后通過最短距離將這些簇依次組合成較大的簇，直到簇中包含所有的數(shù)據(jù)對象。CURE是針對大小相似的數(shù)據(jù)集和球形數(shù)據(jù)集的一種改進算法，其思想為一個簇由其中多個數(shù)據(jù)對象表示，每個簇對應(yīng)多于一個的對象。這種策略使得CURE算法可以適應(yīng)非球形的幾何形狀，并且能利用簇的收縮或凝聚控制孤立點的影響[2]。BIRCH是一種針對大規(guī)模數(shù)據(jù)集的聚類算法，通過聚類特征和聚類特征樹，利用各個簇之間的距離，通過迭代的方法對數(shù)據(jù)集進行聚類[3]。ROCK算法是一種魯棒的聚類算法，在確認(rèn)兩個數(shù)據(jù)的分類時考慮了它們鄰居的數(shù)量，適用于類別型數(shù)據(jù)，如關(guān)鍵字、布爾值和枚舉值等。

1.3 基于密度的聚類方法

基于密度的聚類方法是根基數(shù)據(jù)集密度的大小將數(shù)據(jù)集分類成簇，密度高的區(qū)域聚類成簇，密度低的區(qū)域作為噪聲和孤立點處理，適用于空間中任意形狀的簇，具有很強的抗噪能力。DBSCAN算法是經(jīng)典的基于密度的聚類算法。其核心思想為：預(yù)先設(shè)置距離閾值和密度閾值，將數(shù)據(jù)對象都標(biāo)記為核心點，任意數(shù)據(jù)對象由距離閾值確定的范圍內(nèi)不存在核心點，則將其視為噪聲點消除。確定出每個距離閾值內(nèi)的所有滿足密度閾值的核心點的邊界點，并把每一組連接的核心點分為一個簇，最后將邊界點分配給相關(guān)核心點的簇。其優(yōu)點有：可以自動確定聚類數(shù)量；對任意形狀的簇都適用；對數(shù)據(jù)異常點不敏感。缺點為需要設(shè)置距離和密度閾值，處理空間分布稀疏的數(shù)據(jù)對象時難以得到滿意的聚類結(jié)果，時間復(fù)雜度比K-Means算法高。

1.4 基于網(wǎng)格的聚類方法

基于網(wǎng)格的聚類方法把原數(shù)據(jù)對象空間劃分成獨立于輸入對象分布的單元。通過構(gòu)建父級子級網(wǎng)格單元關(guān)系形成一種多分辨率的網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)，將連續(xù)空間離散化成有限數(shù)目的單元，利用所形成的網(wǎng)格結(jié)構(gòu)進行聚類。該方法僅依賴于離散化后空間中的每一維的單元數(shù)，處理速度不受原數(shù)據(jù)大小的影響。STING是典型基于網(wǎng)格的聚類算法。在構(gòu)建的層次結(jié)構(gòu)實中，每個上層的結(jié)構(gòu)單元都在下一層被劃分為多個下層的結(jié)構(gòu)單元。在聚類時，每個網(wǎng)格單元的統(tǒng)計信息會被預(yù)先計算和儲存，相連高密度的網(wǎng)格單元判斷為簇。STING算法基于網(wǎng)格結(jié)構(gòu)，其算法效率高有利于增量更新和并行處理[4]，但在構(gòu)建父級單元時沒有考慮子級單元和相鄰單元之間的聯(lián)系，無法得到精確簇間邊界，同時聚類精度會受到網(wǎng)格粒度的影響，聚類精度隨粒度減小而提高，處理時間隨之增加。

1.5 基于模型的聚類方法

基于模型的聚類算法需要為數(shù)據(jù)對象中的可能存在的每一簇構(gòu)建一個分布模型，并假設(shè)數(shù)據(jù)對象均獨立分布，通過數(shù)據(jù)對象的真實分布計算模型參數(shù)，最后利用所得模型完成聚類?；谀Ｐ偷姆椒ㄖ饕ńy(tǒng)計學(xué)和網(wǎng)絡(luò)神經(jīng)方法，其中統(tǒng)計學(xué)方法有COBWEB算法；網(wǎng)絡(luò)神經(jīng)方法有SOM算法[5]?；谀Ｐ偷木垲惙椒ㄍǔＲ愿怕实男问綄Υ剡M行劃分，易于理解，但是算法的執(zhí)行效率并不高，同時假設(shè)條件不一定成立，對聚類結(jié)果也造成一定影響。

2 結(jié)語

本文介紹了基于5種聚類方法，主要介紹了其中具有代表性的算法K-Means、CURE、DBScan、STING算法和基于模型的聚類方法。分析了各類算法的特點和特性，對于不同的問題應(yīng)采用不同的聚類算法。在實際應(yīng)用中，需要結(jié)合算法的優(yōu)缺點選擇合適的算法才能獲得理想的聚類效果。

參考文獻

[1] 陳建嬌.高維數(shù)據(jù)的K-harmonic Means聚類方法及其應(yīng)用研究[D].上海大學(xué)，2012.

[2] 周迎春，駱嘉偉.基于分層的平衡迭代規(guī)約聚類分析算法研究[J].科學(xué)技術(shù)與工程，2008，8（10）：2579-2584.

[3] 陳紹彬，葉飛躍，劉佰強，等.食品HACCP分類的BIRCH算法[J].計算機工程，2008，34（23）：59-61.

[4] 楊靜.分層模糊最小-最大聚類算法及其在圖像聚類中的應(yīng)用研究[D].合肥工業(yè)大學(xué)，2007.

[5] 冉延平，余昭平，賈利新，等.基于混合模型的聚類算法研究[J].河南科學(xué)，2005，23（3）：324-327.