一種結合蟻群聚類算法的DBSCAN算法

許芳芳

（池州學院 數學與計算機科學系，安徽 池州247000）

1 引言

聚類分析是一種重要的知識發現方法，總體上可以分為五類：基于劃分、層次、密度、模型和網格的方法。DBSCAN算法是一種基于密度的經典方法，它能發現任意形狀的簇，且不需要預先確定數據集將被聚類的簇數，也不受噪聲影響。但是當數據集的密度不均勻時，由于采用統一的全局參數Eps，導致聚類效果差；并且對于高維數據的處理能力也較差。針對DBSCAN存在的不足，目前有很多學者做出了大量的改進研究。為了簡化參數輸入，李霞等提出了一種新的動態密度定義方法，并在此定義的基礎上給出一種動態密度聚類算法DDBCA，該算法只需一個簡單輸入參數（即最近鄰個數k）就能動態識別出密度不均勻的聚類簇[1]。文獻[2]提出一種將蟻群優化算法與DBSCAN算法相結合的PACA-DBSCAN算法，此算法能減小輸入參數對聚類結果質量的影響，且能有效處理不同密度的數據集。楊靜等則借鑒數據場思想，引入平均勢差的概念，動態確定每個類的Eps，避免了人工確定Eps的缺點，有效實現了對變密度數據集的聚類[3]。文獻[4]則根據數據集自身特點尋找最大聚類效果指數(CEI)以確定minPts，并通過高斯分布中的參數估計來確定每個Eps，從而實現自適應確定閾值。為了實現聚類無參數化且對任意形狀、任意密度聚類的目標，文獻[5]借助投影分析和分散度計算，并結合一維高斯核密度估計方法來確定密度參數(Eps和minPts)。DBSCAN的改進算法還有周董等提出的VDBSCAN算法[6]、馬帥等提出的CURD算法[7]、潘玲玲等提出的核DBSCAN算法[8]等。

在上述研究基礎上，結合蟻群聚類算法將高維數據隨機投影到二維網格以實現對高維數據的有效處理，且具有自組織聚類性質、易于與其他算法結合的優點，本文提出一種改進的DBSCAN算法LF-DBSCAN，即利用蟻群聚類算法將密度不均的高維數據集劃分為若干個子數據集，并以此獲得不同密度的Eps值組，然后采用這些不同值的Eps參數對數據集進行聚類，使得DBSCAN算法能在一定程度上對密度分布不均的高維數據集進行有效地聚類。實驗結果也驗證了LF-DBSCAN算法的有效性。

2 改進的基于蟻群聚類的DBSCAN算法

由于經典DBSCAN算法對于數據集只選取全局參數，使得該算法難以同時聚類不同密度的簇。而真實的數據集往往是高維的，并且是分布不均的，全局參數不能刻畫其內在的聚類結構。為了實現對非均勻密度數據集的有效聚類，本文提出一種改進的DBSCAN算法LF-DBSCAN算法。

2.1 DBSCAN算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法[9]是一個基于高密度連接區域的聚類算法，它將簇定義為密度相連的點的最大集合，能把具有足夠高密度的區域劃分為簇。為了識別一個簇，該算法需要輸入兩個全局參數：對象鄰域半徑Eps和鄰域內最少對象數MinPts。DBSCAN算法的基本思想是：從數據集中任選一對象p，若p在半徑為Eps的區域內包含的對象數目大于等于MinPts個，則p為核心對象并建立新簇，找出所有從p密度可達的對象，將這些對象標注為同一簇；否則，沒有其他對象從p密度可達，p被暫時標注為噪聲。然后，DBSCAN對數據集中其他未被處理的對象均做上述處理。

2.2 蟻群聚類算法

根據自然界真實蟻群的覓食行為，意大利學者Dorigo M等人于1991年最早提出了蟻群算法的基本模型。將蟻群算法用于聚類分析，源于螞蟻堆積蟻尸和分類幼體的行為。Deneubourg J L[10]等基于蟻群聚類現象建立了一種基本模型 （Basic Model,BM）,Lumer E和Faieta B將該模型擴展，推廣到數據分析范疇，設計了用于數據聚類的LF算法[11]。其主要思想是將待聚類的高維數據對象隨機投影到一個二維平面上，同時放置若干只人工螞蟻到該平面內，每只螞蟻隨機選擇一個數據對象，根據該數據對象在局部區域的鄰域相似度，得到螞蟻拾起或放下該對象的概率，從而指導螞蟻的下一步動作。經過有限次迭代后，平面上的數據對象按其鄰域相似性而聚集在一起，從而實現自組織的聚類過程。

鄰域相似度f(i)表示螞蟻在地點r發現的一個數據對象i與其鄰域對象間的平均相似度，f(i)可由公式(1)來計算

式中，α∈[0,1]為相似度調節因子；Neighs×s(r)表示地點r周圍的以s為邊長的正方形局部區域；d(i,j)表示對象i和j在屬性空間中的距離，通常采用歐式距離或余弦距離函數。

螞蟻在二維平面內不斷移動并反復根據鄰域相似度來計算拾起或放下對象的概率，鄰域相似度越高，則放下對象的概率越高，拾起對象的概率越低；反之亦然。若螞蟻負載數據對象，則按公式(2)計算螞蟻的放下概率Pd；若螞蟻無負載，則按公式(3)計算螞蟻的拾起概率Pp。其中，kp和kd均為閾值常數。

LF算法可以發現任意形狀的簇，能有效處理高維數據，且易于與其他算法結合；但存在計算時間較長，算法效率不高等問題。在LF算法中，螞蟻的移動都是隨機的，這使得螞蟻尋找樣本對象需要耗費大量的時間。因此本文采用文獻[12]提出的LF改進算法，將人工螞蟻與數據綁定，消除空載螞蟻的存在，以減少算法時間成本。

2.3 LF-DBSCAN算法描述

LF-DBSCAN的核心思想為：首先利用LF算法將高維的數據集映射到一個二維的網格上，并將人工螞蟻和數據綁定以自由移動數據對象，實現對數據集的初始劃分；再對每個數據子集提取中心點（該點到當前聚類中的其他所有點的距離之和最小），將每個中心點的k個近鄰距離的平均距離作為該類的鄰域閾值Epsi；然后對所有鄰域閾值Epsi進行升序排序，依次用Epsi作為參數調用DBSCAN算法；每次調用后，對所有已聚類的數據點進行標記，且標記過的點將不再參與以后的DBSCAN調用；直到所有的Epsi都使用完畢，剩下的沒有被處理過的數據點即是噪聲點。通過以上方式最終實現對密度不均的數據集的有效聚類。

LF-DBSCAN算法的描述如下：

For所有子簇i do

計算所有對象的距離矩陣Mi；

計算距離矩陣Mi的每一列數字之和，找出距離和最小的點，此點記為該簇中心點Midi；

對距離矩陣Mi的每一列升序排序并轉置得到矩陣KMi，計算KMi中Midi點所對應的行向量的前k+1個分量的和的平均值，此值即定義為該簇的鄰域閾值Epsi；

3 實驗分析

為了測試對比LF-DBSCAN算法的有效性，本文采用了4個數據集，分別對每個數據集同時進行DBSCAN算法和LF-DBSCAN算法聚類。實驗采用matlab實現，在CPU 2.1GHZ+2G RAM+Windows XP平臺上進行。

實驗中所有數據集的詳細信息如表1所示。其中數據集Dataset1和Dataset2是人工數據集，數據對象的分布情況如圖1和圖2所示；Iris和Wine是來自UCI機器學習數據庫中的標準數據挖掘數據集。

表1 數據集特征

圖1 人工數據集Dataset1

圖2 人工數據集Dataset2

為了避免出現聚類結果完全由某個很大變化范圍的屬性主導的情況，減少數據中不同屬性絕對數值大小對計算的影響，實驗中采用公式(4)對所有數據集進行數據標準化處理；并使用F-Measure度量[13]對比DBSCAN算法和LF-DBSCAN的有效性。F-Measure度量是一種綜合考慮了準確率和召回率的性能分析方法，其定義為公式(5)：

對于樣本數為m的數據集，定義公式(6)：

上面3式中，xif表示第i個數據點的第f個屬性值，rg(xif)表示xif的新值，min(f)和max(f)分別表示屬性f可取的最小值和最大值；p(i,j)為準確率，r(i,j)為召回率；maxF(i,j)在所有簇i上取，mj是類j中對象的個數。F-Measure的值越大，表明算法的有效性越好。

表2 DBSCAN和LF-DBSCAN算法在數據集上的聚類結果

圖3 數據集Dataset1上運行DBSCAN結果

圖4 數據集Dataset2上運行DBSCAN結果

圖5 數據集Dataset1上運行LF-DBSCAN結果

圖6 數據集Dataset2上運行LF-DBSCAN結果

4 結束語

針對傳統的DBSCAN算法使用全局參數導致對非均勻密度數據集聚類效果差，以及對高維數據處理效果不理想的不足，本文提出一種LFDBSCAN算法來實現對非均勻數據集的有效聚類。通過實驗對比四組性質不同的數據集的聚類效果，結果證明了LF-DBSCAN算法的有效性。但LF-DBSCAN算法仍有待改進之處，如需要主觀確定參數MinPts和k。通過實驗發現k的取值影響聚類效果，如何進一步減小k的影響是下一步待研究的問題。

[1]LI Xia,JIANG Shengyi,ZHANG Qiansheng,etc.ADynamic Density-Based Clustering Algorithm Appropriate to Large-Scale Text Processing[J].Acta Scientiarum Naturalium Universitatis Pekinensis,2013,49(1):133-139.

[2]Hua Jiang,Jing Li,Shenghe Yi,etc.A new hybrid method based on partitioning-based DBSCAN and ant clustering[J].Expert Systems With Applications,2011,38(8):9373-9381.

[3]楊靜,高嘉偉,梁吉業,等.基于數據場的改進DBSCAN聚類算法[J].計算機科學與探索,2012,6(10):903-911.

[4]陳剛,劉秉權,吳巖.一種基于高斯分布的自適應DBSCAN算法[J].微電子學與計算機,2013,30(3):27-30.

[5]錢美旋,葉東毅.利用一維投影分析的無參數多密度聚類算法[J].小型微型計算機系統,2013,34(8):1866-1871.

[6]周董,劉鵬.VDBSCAN:變密度聚類算法[J].計算機工程與應用,2009,45(11):137-141.

[7]馬帥,王騰蛟,唐世渭,等.一種基于參考點和密度的快速聚類算法[J].軟件學報,2003,14(6):1089-1095.

[8]潘玲玲,張育平,徐濤.核DBSCAN算法在民航客戶細分中的應用[J].計算機工程,2012,38(10):70-73.

[9]Ester M,Kriegel H P,Sander J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedingsofthe 2nd InternationalConference on Knowledge Discovery and Data Mining,1996:226-231.

[10]Deneubourg J L,Goss S,Franks N,etc.The dynamics of collective sorting:robot-like ants and ant-like robots[C]//Proceedings of the 1st International Conference on Simulation of Adaptive Behavior:From Animal to Animals,1991:356-365.

[11]Lumer E,Faieta B.Diversity and adaptation in populations of clustering ants[C]//Proceedings of the 3rd International Conference on Simulation of Adaptive Behavior:From Animals to Animals.Cambridge,MIT Press,1994:501-508.

[12]趙燁,黃澤君.蟻群K-medoids融合的聚類算法[J].電子測量與儀器學報,2012,26(9):800-804.

[13]Steinbach M,Karypis G,Kumar V.A comparison of document clustering techniques:technicalreport [R].Minnesota:University of Minnesota Computer Science and Engineering,2000.

[14]劉強，鄧磊，賈振紅，等.基于劃分DBSCAN算法的小區載頻配置優化[J].計算機工程與應用,2012(8):85-89.

[15]閆保權.蟻群聚類LF算法在MATLAB中的實現[J].信息技術,2013(3):143-145.