陳小輝, 奚慶港

(淮陰師范學院 計算機科學與技術學院, 江蘇 淮安 223300)

0 引言

聚類算法是數(shù)據(jù)挖掘中的一種技術，而數(shù)據(jù)挖掘是從一堆數(shù)據(jù)中挖掘知識[1].聚類分析目前已經(jīng)被廣泛地應用于圖像識別、生物學等領域.DBSCAN算法(Density-Based Spatial Clustering of Applicotions with Noise)的優(yōu)點在于不僅可以發(fā)現(xiàn)任意形狀的簇，還可以發(fā)現(xiàn)噪音點和離群點.由于該算法使用兩個全局的參數(shù)，使得針對變密度數(shù)據(jù)集時聚類的效果并不出色，其原因在于DBSCAN算法對兩個參數(shù)過于敏感且兩個參數(shù)全局通用，而全局通用的參數(shù)較多時候需要人工判別.因此，一些學者針對自適應參數(shù)的 DBSCAN 算法進行了研究.Yue等[2]提出一種基于數(shù)據(jù)統(tǒng)計信息確定Eps參數(shù)的算法，通過該算法可以在更廣的范圍內搜索Eps參數(shù)，但是該算法中MinPts參數(shù)恒定設置為4的時候，也不能較準確地反映數(shù)據(jù)集的分布特性. 周紅芳等[3]提出了I-DBSCAN(Improved Density-Based spatial Clustering of Applicotions with Noise)自適應聚類算法，利用聚類個數(shù)和噪聲點個數(shù)的趨勢作為聚類結果判別，尋找趨勢穩(wěn)定點處所對應的Eps和MinPts參數(shù).但I-DBSCAN自適應聚類算法不足之處還需要人為進行判別.

本文針對DBSCAN算法對密度不同的數(shù)據(jù)集、符號型數(shù)據(jù)集聚類效果較差的不足，引入了對象密度的概念和統(tǒng)計學分析方法，得出Eps與MinPts的關系，通過最小二乘法進行函數(shù)擬合得到一條曲線，由曲線找到和核心點相近的對象，將其納入簇內，隨后進行不斷遍歷，最后實現(xiàn)聚類.實驗結果表明，改進后的算法與DBSCAN算法及K-MEANS算法相比，對符號型數(shù)據(jù)集和數(shù)值型密度不均勻數(shù)據(jù)集聚類的效果更優(yōu).

1 DBSCAN算法概述

1.1 算法介紹

DBSCAN算法是典型的基于密度聚類算法，不僅能夠判定各種形狀的簇，還能通過兩個參數(shù)識別數(shù)據(jù)集中的各個類以及判別噪聲點.

1.2 算法的定義

DBSCAN算法需要用戶輸入兩個參數(shù)Eps(半徑)和MinPts(最少樣本數(shù)目)[4].DBSCAN對于核對象的定義是在給定的Eps內包含MinPts個或以上個對象，即在該對象一定的鄰域內的樣本要超過一定的閾值.相關定義如下：

定義1(核對象) 一個樣本p以Eps為半徑的圓內的有超過一定數(shù)目(≥MinPts)的樣本，則樣本p稱為核對象.

定義2(鄰域ε) 領域內的點定義為NEps(p)={q∈D,dist(p,q)≤Eps},其中D代表數(shù)據(jù)集中所有對象，dist(p,q)代表樣本p與樣本q兩者之間的距離.

定義3(直接密度可達) 在數(shù)據(jù)集D中，對象q在另一個對象p的Eps鄰域內，且對象p為核對象的情況下，則稱對象q從對象p直接密度可達.

定義4(密度可達) 在數(shù)據(jù)集D中，存在p1,p2,p3,…,pn,1≤i≤n,對于pi∈D,且pi是從pi-1的直接密度直達，則點pn從p1密度可達.

定義5(密度相連) 若存在一個對象o,使得對象p和q都從o密度可達，則稱對象p和對象q密度相連.

1.3 算法的實現(xiàn)

DBSCAN算法流程[5]如下：

輸入：數(shù)據(jù)集U，MinPts，Eps，

輸出：各個不相交的簇.

Step 1: 從任一未訪問過的樣本開始并以這個樣本為中心，判斷是否為核心對象.若是核心對象則創(chuàng)建一個新類C，并將其鄰域內的樣本納入到類C內；

Step 2: 在C內尋找其他未被訪問的樣本，若該樣本為核對象,則將其鄰域內所有樣本納入簇中；

Step 3: 重復Step 2直到簇C中不再增加新樣本；

Step 4: 重復Step 1,2,3,直到所有對象都被歸類.

1.4 相似度衡量

在聚類分析中，樣本之間的相似度衡量是一個重要的研究點[6]，對數(shù)據(jù)集采用合適的度量方法至關重要.相似度衡量常用距離度量，主要有歐氏距離、閔可夫斯基距離、曼哈頓距離、切比雪夫距離等.

1) 歐氏距離

在二維或三維空間中歐氏距離就是指兩點之間的實際距離.在N維空間中，計算公式為

(1)

2) 閔可夫斯基距離

閔可夫斯基距離是一組距離的定義，計算公式為

(2)

當p=1時，該距離轉化為曼哈頓距離.當p=2時，計算結果轉化為歐氏距離.當p趨向于無窮時，即為切比雪夫距離.

1.5 評價指標

聚類算法的評價指標[7]又被稱作“有效性指標”(validity index).為了對聚類的結果進行分析，需要借助聚類有效性評價法評估其聚類質量的優(yōu)劣.

1) 調整蘭德指數(shù)[8]

調整蘭德指數(shù)(ARI)是用來衡量聚類效果的一個指標，該指標不會隨著聚類標簽的變化而變化，當真實標簽為[0,0,1,1,2,2]，預測標簽為[0,0,2,2,1,1]或者[1,1,2,2,0,0]時，ARI的值是不變的. ARI取值為-1～1.蘭德指數(shù)和調整蘭德指數(shù)(R)定義分別如下：

(3)

其中n為樣本總數(shù).

(4)

2)V-Measure

V-Measure是同質性和完整性兩者的調和平均.同質性和完整性的計算公式分別為

(5)

(6)

兩者的調和平均V-Measure公式為

(7)

3) AMI(Adjust Mutual information)

調整互信息主要是用來衡量兩個數(shù)據(jù)的分布程度.AMI的取值范圍介于-1與1之間.AMI越大，說明結果和真實情況吻合度越高.互信息和調整互信息的定義為

(8)

(9)

2 改進的IDBSCAN算法

2.1 符號屬性數(shù)據(jù)集的距離度量標準

在傳統(tǒng)數(shù)值型的聚類算法中，兩個樣本之間的距離度量通常采用歐氏距離.針對符號屬性的數(shù)據(jù)集使用式(10)作為距離計算方法.設數(shù)據(jù)集X有n個樣本x1,x2,x3,…,xn.每個樣本有A個特征，分別記為a1,a2,…,aA且這些特征均為符號屬性.

每個樣本之間的距離度量定義為

(10)

其中

(11)

通過該定義易得兩個樣本之間的距離.假設樣本x1(a,b,c,d),樣本x2(a,a,c,d),則x1和x2之間的距離為1.

2.2 樣本的對象密度概念

當樣本對象密度越大，該樣本周邊聚集的點就越多，反之該樣本周邊聚集的點就越少.

1) 數(shù)值型數(shù)據(jù)集的對象密度概念

假設數(shù)據(jù)集X是一個數(shù)值型數(shù)據(jù)集.對于數(shù)據(jù)集中的每個樣本的對象密度可以定義為

(12)

其中A為屬性集合.

2) 符號數(shù)據(jù)集的對象密度概念[9].

假設數(shù)據(jù)集U是符號數(shù)據(jù)集.定義數(shù)據(jù)集中的每個樣本的對象密度為

(13)

顯然，上述定義對象密度值最大值為0，最小值為-A，即

-|A|≤Dens(x)≤0

(14)

2.3 通過統(tǒng)計學概念尋找相似樣本的方法

通過式(10)～(13)可得到樣本間距離和樣本的對象密度.對于每一個樣本引入統(tǒng)計學的方法來尋找與相似樣本.對于某一個樣本xp，當取定樣本有關的MinPts值時，其相應的Eps值可得，即該樣本有關的Eps與MinPts.依照數(shù)據(jù)集的統(tǒng)計特性可以繪制出Eps與MinPts之間關系的圖像.

數(shù)據(jù)集中樣本的Eps與MinPts之間的變化關系如圖1所示.從圖1中可以看出Eps與MinPts之間存在某種變化關系，此時引入最小二乘法[10]進行曲線擬合,通過最小化誤差平方和的方法來尋找與原始數(shù)據(jù)分布最為匹配的函數(shù). 最小二乘法的計算公式為

圖1 MinPts與Eps變化圖 圖2 三次函數(shù)進行擬合

(15)

對圖1中數(shù)據(jù)引入最小二乘法進行多項式的擬合.使用三次函數(shù)進行擬合的情況如圖2所示；使用高次函數(shù)進行擬合的情況如圖3所示. 由圖2可知，在MinPts與Eps兩者數(shù)據(jù)的擬合中，當函數(shù)次數(shù)過低時，擬合效果一般.因此將采用高次函數(shù)進行擬合.圖2和圖3的函數(shù)擬合曲線中存在拐點，通過擬合的曲線可找到了Eps與MinPts之間的函數(shù)關系.由圖2和圖3可知，使用高次函數(shù)進行函數(shù)擬合出現(xiàn)有多個拐點的情況，與數(shù)據(jù)集存在多個不同密度簇的情況一致.

圖3 高次函數(shù)進行擬合

經(jīng)過實驗可知，選擇三次函數(shù)進行擬合的結果比較符合數(shù)據(jù)分布規(guī)律，同時較容易找到三次函數(shù)擬合曲線第1個拐點及該拐點處的對應Eps與MinPts的值.與數(shù)據(jù)統(tǒng)計特性相對應，在第1個拐點的左側樣本與核心目標對象更為相近，左側目標與核心目標對象可以被分為一類.拐點右側的樣本與核心目標對象相對較遠，不歸屬于核心目標對象所在類.

2.4 算法改進

依照上述內容，設計改進Improved DBSCAN算法，其實現(xiàn)流程如下：

1) 對于符號屬性的數(shù)據(jù)集，通過式(10)計算樣本之間的距離.針對數(shù)值型數(shù)據(jù)集，通過歐氏距離計算樣本間的距離；

2) 通過式(12)和式(13)計算數(shù)據(jù)集中各個樣本的對象密度，按各個樣本的對象密度從大到小進行排序并將所有樣本標記為未訪問；

3) 開始依照樣本的密度從大到小開始訪問.首先訪問密度最高的樣本，將該樣本作為核心對象，設置該樣本為當前樣本.接著從當前樣本出發(fā)，分析樣本的分布規(guī)律，通過最小二乘法進行函數(shù)擬合Eps與MinPts的關系，進而在曲線拐點處獲得對應位置的Eps與MinPts的值.由此得到與該核心點相近的對象，將其納入簇內，并將簇內的樣本均標記為已訪問；

4) 依照密度排序，查找下一個未被訪問的樣本，不斷重復上述過程直到所有點樣本均被訪問.然后，找到兩個具有公共點的簇進行合并，得到一個新的簇.最后得到若干個無公共交點的簇，即聚類結果.

給出的改進型DBSCAN算法流程如下：

輸入： 數(shù)據(jù)集U，

輸出： 各個不相交的簇.

Step 1: 計算各個樣本的對象密度；

Step 2: 將各個樣本以對象密度從大到小排序，并標記為未訪問；

Step 3: 依據(jù)對象密度依次訪問未訪問過的樣本，通過文中方法獲取與當前樣本有關的Eps與Minpts的值作為參數(shù)，并將該樣本周邊的樣本納入到簇內，將簇內的樣本標記為已訪問；

Step 4: 不斷重復Step 3直到所有樣本均已為訪問；

Step 5: 進行相交簇的合并.

3 實驗結果與分析

為了驗證改進后的算法進行聚類的有效性，將其與兩種經(jīng)典的K-means、DBSCAN算法的聚類算法進行比較.使用若干個不同密度的仿真數(shù)據(jù)集和真實數(shù)據(jù)集對此3種算法進行比較.K-means算法只需要1個參數(shù)K，該參數(shù)K代表了聚類結果的簇的個數(shù). DBSCAN算法需要兩個參數(shù)，分別為Eps與MinPts. 在本實驗中，Eps取值通常根據(jù)數(shù)據(jù)集本身的情況進行分配，MinPts的取值通常為數(shù)據(jù)集個數(shù)除以25.對于改進算法IDBSCAN，是自適應算法的不需要參數(shù).

實驗環(huán)境：macOS Mojave 版本10.14.3； 處理器2.6 GHz Intel Core i7； 內存16GB 2400 MHzDDR4； 圖形卡RadeonPro 560X 4096MB.開發(fā)語言：Python.Python作為一種高級語言有跨平臺性等優(yōu)點.集成開發(fā)環(huán)境：PyCharm.

3.1 數(shù)值型數(shù)據(jù)集的實驗分析

密度分布不均勻的數(shù)值型仿真數(shù)據(jù)集實驗情況如圖4所示. 從圖4和表1～3可以看出，數(shù)據(jù)集由1個高密度簇和1個低密度簇組成.由于DBSCAN算法對兩個參數(shù)的選擇較敏感，而且不能對密度不均勻的數(shù)據(jù)集進行有效聚類.究其原因在于DBSCAN使用一組全局的Eps和MinPts參數(shù)進行聚類分析，因此聚類效果較差.K-means算法輸入正確的簇數(shù)后，該算法對于邊角的數(shù)據(jù)點未能夠進行有效的分類.而對于基于DBSCAN改進后的算法IDBSCAN能夠根據(jù)簇的密度進行自適應聚類.因此，針對密度不均的數(shù)據(jù)集時表現(xiàn)較好.

表1 數(shù)據(jù)集屬性

表2 算法參數(shù)

表3 算法性能

表4 數(shù)據(jù)集屬性

3.2 符號型數(shù)據(jù)集的實驗分析

該數(shù)據(jù)集是符號型真實數(shù)據(jù)集Soybean(大豆)，共有46個樣本，35個特征，4個簇.該數(shù)據(jù)集的特征值均為符號屬性.通過表5和表6可知，DBSCAN對該數(shù)據(jù)集聚類的效果較差，K-means算法在某些重疊相似的樣本上聚類效果也較差，而改進后的算法對大豆數(shù)據(jù)集聚類效果較好.

表5 算法參數(shù)

表6 算法性能

4 結論

DBSCAN算法作為一種經(jīng)典的基于密度的聚類算法，通過兩個全局的參數(shù)Eps與MinPts進行聚類. 由于DBSCAN使用全局的參數(shù)進行聚類分析，導致在處理非均勻密度數(shù)值型和符號型數(shù)據(jù)集時效果并不理想.因此，本文針對這種情況提出了一種基于DBSCAN的自適應聚類算法.該算法先引入了一個對象密度的概念，通過密度概念計算出每個樣本的密度，提出一種基于統(tǒng)計學自適應尋找Eps與MinPts兩個參數(shù)的方法.該方法通過引入最小二乘法的概念，對某一樣本的Eps與MinPts的關系進行函數(shù)擬合，再通過計算這個函數(shù)的拐點來尋找Eps與MinPts兩個參數(shù).改進后的算法能夠自適應的進行聚類. 為了評估改進后算法的性能，采用了若干個仿真和真實數(shù)據(jù)集進行聚類分析.實驗結果表明，改進后的算法在處理非均勻密度數(shù)值型數(shù)據(jù)集和符號型數(shù)據(jù)集進行聚類分析時效果較好.