聚類算法綜述

王玉晗 羅鄧三郎

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

關鍵詞：數據挖掘 聚類 密度 模型

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

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

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

根據聚類算法中對象間相似度的計算方式以及聚類結果中對象的關系可以將聚類算法分為劃分法、層次法、基于密度的方法、基于網格的方法、基于模型的方法[1]。

1 聚類方法

1.1 基于劃分的聚類方法

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

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

1.2 基于層次的聚類方法

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

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

1.3 基于密度的聚類方法

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

1.4 基于網格的聚類方法

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

1.5 基于模型的聚類方法

基于模型的聚類算法需要為數據對象中的可能存在的每一簇構建一個分布模型，并假設數據對象均獨立分布，通過數據對象的真實分布計算模型參數，最后利用所得模型完成聚類。基于模型的方法主要包括統計學和網絡神經方法，其中統計學方法有COBWEB算法；網絡神經方法有SOM算法[5]。基于模型的聚類方法通常以概率的形式對簇進行劃分，易于理解，但是算法的執行效率并不高，同時假設條件不一定成立，對聚類結果也造成一定影響。

2 結語

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

參考文獻

[1] 陳建嬌.高維數據的K-harmonic Means聚類方法及其應用研究[D].上海大學，2012.

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

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

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

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