基于MCL與Chameleon的混合聚類算法

楊連群，劉樹發，溫晉英，劉功申

（1.天津市濱海新區公安局 天津300450；2.天津市公安局 天津300020；3.上海交通大學 上海200240）

基于MCL與Chameleon的混合聚類算法

楊連群1，劉樹發2，溫晉英1，劉功申3

（1.天津市濱海新區公安局 天津300450；2.天津市公安局 天津300020；3.上海交通大學 上海200240）

馬爾科夫聚類算法（Markov Cluster Algorithm，MCL）是一種快速且可擴展的無監督圖聚類算法，Chameleon是一種新的層次聚類算法。但MCL由于過擬合會產生很多小聚類，Chameleon由于時間復雜度為O（N2）不利于處理大規模數據集。針對這兩個問題，提出了一種基于MCL與Chameleon相結合的混合聚類算法。該算法第一階段采用MCL算法對原始數據進行初步聚類，第二階段利用GPU加速的Chameleon算法將第一階段產生的小聚類進行歸并，從而得到質量更高的聚類。實驗表明，與傳統的MCL算法和MCL與KNN的混合聚類算法，提出的方法聚類質量更好、計算速度更快。

MCL；Chameleon；聚類算法；圖分割算法

聚類分析是探測數據分析的關鍵步驟，在許多領域都得到了較為成功的應用，如數據分析[1]、Web文檔分類[2]、異常檢測[3]等。圖聚類算法是聚類分析中研究較為廣泛的一個分支，目前已有很多關于圖聚類的算法被提出，比如譜聚類算法[4-5]，多層聚類算法（METIS）[6-7]等。但在實際運用中仍然有很多不足之處，如：1）譜聚類算法由于需要計算相似矩陣的特征值和特征向量，導致計算時間太長；2）METIS將圖的權重進行均等劃分，不適合長尾分布的數據；3）譜聚類算法和METIS都不具備智能識別圖類別數目的能力等。因此探討一種計算時間較快、分割質量高且無需事先規定聚類數目的圖分割算法是很有必要的。……