聚類算法綜述

宋坤

（重慶交通大學 信息科學與工程學院，重慶 400074）

聚類算法綜述

宋坤

（重慶交通大學 信息科學與工程學院，重慶 400074）

聚類是將物理或抽象對象的集合組成為由類似的對象組成的多個類的過程，是研究數據間邏輯上或物理上的相互關系的技術，是數據挖掘技術中的重要組成部分。結合國內研究現狀，論文介紹各類主要的聚類算法及其應用領域。

數據挖掘；相互關系；聚類

1　背景及意義

數據挖掘中聚類算法的應用很廣泛。在商務上，聚類能幫助市場分析人員從客戶基本庫中發現不同的客戶群。 在生物學上，聚類能用于基因和蛋白質的分類，獲得對種群中固定結構的認識［1］。聚類在地球觀測數據中相似地區的確定發揮作用。聚類也能用來對web上的文檔進行分類，以發現有用的信息。聚類分析能作為一種獨立的工具來獲得數據分布的情況，觀察每個簇的特點，并對某些特定的節點進一步分析。此外，聚類還可以作為其他方法的預處理步驟。

作為統計學的一個分支，聚類分析已經被廣泛地研究若干年，主要集中在基于距離的聚類分析。

2　聚類算法簡介

聚類是一個將數據集劃分為若干組或簇的過程，使得同一類的數據對象之間的相似度較高，而不同類的數據對象之間的相似度較低。聚類問題的關鍵是把相似的事物聚集在一起。

2.1傳統聚類算法

2.1.1層次方法

層次法對給定的數據對象集合進行層次似的分解。按層次分解的形成方式，層次法可分為凝聚和分裂兩大類。凝聚的方法，也稱為自底向上的方法，一開始將每個對象作為單獨的一個類，然后相繼地合并相近的類，直到所有的類合并為一個（層次的最上層），或者達到一個終止條件為止。層次方法 （Hierarchical Method）中代表算法BIRCH、CURE、ROCK、CHAMELEON 算法等［2］。

2.1.2劃分方法

給定一個包含n個數據對象的數據集，劃分法構建數據的k個劃分，每個劃分表示一個類，并且k ≤ n。同時滿足如下的要求：①每個組至少包含一個對象；②每個對象屬于且僅屬于一個組。其代表算法有K-MEANS、K-MEDOIDS、大型數據庫劃分方法（CLARANS）等。

2.1.3密度方法

該方法主要思想是：只要鄰近區域的密度（對象或數據點的數目）超過某個閾值，就繼續聚類。也就是說，對給定類中的每個數據點，在一個給定范圍的區域內必須至少包含某個數目的點。其代表算法有DBSCAN、OPTICS和DE NCLUE等［3］。

2.2新發展的聚類算法

2.2.1基于模糊的聚類方法

基于目標函數的模糊聚類方法，該方法把聚類歸結成一個帶約束的非線性規劃問題，通過優化求解獲得數據集的模糊劃分和聚類。該方法設計簡單，解決問題的范圍廣，還可以轉化為優化問題而借助經典數學的非線性規劃理論求解，并易于在計算機上實現。因此，隨著計算機的應用和發展，基于目標函數的模糊聚類算法成為新的研究熱點。在基于目標函數的聚類算法中，FCM 類型算法的理論最為完善、應用最為廣泛。

2.2.2基于粒度的聚類方法

如果從信息粒度的角度來看，就會發現聚類和分類的相通之處：聚類操作實際上是在一個統一粒度下進行計算的；分類操作是在不同粒度下進行計算的。在粒度原理下，聚類和分類的相通使得很多分類的方法也可以用在聚類方法中。作為一個新的研究方向，雖然目前粒度計算還不成熟，尤其是對粒度計算語義的研究還相當少，但是相信隨著粒度計算理論本身的不斷完善和發展。

2.2.3量子聚類

該方法把聚類問題看作一個物理系統，其很好的例子就是基于相關點的 Pott 自旋和統計機理提出的量子聚類模型。并且許多算例表明，對于傳統聚類算法無能為力的幾種聚類問題，該算法都得到了比較滿意的結果［4］。

2.2.4譜聚類

為了能在任意形狀的樣本空間上聚類，且收斂于全局最優解，學者們開始研究一類新型的聚類算法，稱為譜聚類算法（Spectral Clustering Algorithm）。譜聚類算法最初用于計算機視覺、VLSI設計等領域，最近才開始用于機器學習中，并迅速成為國際上機器學習領域的研究熱點［5］。

3　結語

數據聚類正在蓬勃的發展，有貢獻的領域包括數據挖掘，統計學，機器學習，空間數據庫技術，生物學以及市場營銷。現在數據聚類分析已經成為一個非常活躍的研究課題。

［1］田野，劉大有，楊博. 復雜網絡聚類算法在生物網絡中的應用［J］. 計算機科學與探索，2010，04:330-337.

［2］Amineh Amini，Teh Ying Wah，Hadi Saboohi. On Density-Based Data Streams Clustering Algorithms: A Survey［J］. Journal of Computer Science & Technology，2014，01:116-141.

［3］Local and global approaches of affinity propagation clustering for large scale data［J］. Journal of Zhejiang University（Science A:An International Applied Physics & Engineering Journal），2008，10:1373-1381.

［4］王玉瑛. 量子聚類及其在社團檢測中的應用［D］.西安電子科技大學，2014.

［5］蔡曉妍，戴冠中，楊黎斌. 譜聚類算法綜述［J］. 計算機科學，2008，07:14-18.

TP311.13

A

1003-5168（2015）11-254-01

宋坤（1989.07- ），男，河南新鄉人，重慶交通大學信息科學與工程學院2013級碩士研究生，軟件工程專業，研究方向：數據挖掘。