基于區域中心點的多層次數據集密度聚類算法

魏姁妲， 逄煥利

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

基于區域中心點的多層次數據集密度聚類算法

魏姁妲， 逄煥利*

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

通過k-dist圖和DK分析方法對非均勻數據進行密度分區并選擇半徑，確定各密度區域的初始區域中心點，然后調用改進后的快速聚類算法進行聚類。在兩種數據集上進行了算法實驗驗證，有效地聚類多層次數據集，提高了效率和準確率。

非均勻密度聚類； DBSCAN； 區域中心點； K鄰域； DK分析

0 引 言

基于密度的聚類算法因其事先不需要設定聚類的個數，同時能發現各種形狀的簇等優點為人關注，其代表算法有DBSCAN、OPTICS、DENCLUE等。但在解決實際問題中大量存在的密度非均勻數據時，效果常不能令人滿意。目前，研究人員基于這種缺陷也提出了相應的改進算法：文獻[1] 提出了依據數據分區思想的PDBSCAN算法，通過分析多層次密度點的分布特性將其標記為多個局部區域，再分別對各區域做合并操作；文獻[2]提出PACA-DBSCAN算法，該算法采用k-means算法(或蟻群聚類算法)對數據集進行分區，并用k-dist圖確定分區密度參數，實現局部聚類；文獻[3]則采用DBSCAN算法對每個數據集對象的k-dist值進行聚類，通過獲取不同的Eps參數，再用傳統DBSCAN算法進行聚類。

文中提出處理非均勻密度數據的改進算法。通過k-dist圖和DK分析方法，發現各密度分區及其對應的初始中心點和半徑，最后分別對各區域進行聚類。同時，文中提出一種快速聚類算法來提高各密度區域聚類時的效率。實驗表明,本算法可以有效地聚類非均勻密度數據，時間效率及準確率較傳統算法有所提升。

1 DBSCAN算法

1.1 DBSCAN算法

DBSCAN算法是基于密度的典型算法，其主要思想為：尋找所有核心對象的Eps鄰域內直接密度可達的密度相連對象，將這些對象合并成一類。它具有聚類速度快、能夠處理噪聲點并發現各種形狀的簇等優點，該算法通過過濾低密度區域來發現密度較大的樣本點。算法涉及的基本定義如下。

1.1.1 Eps鄰域

給定對象半徑Eps內的區域。

1.1.2 核心對象

在數據集D中，如果對象p的Eps鄰域內包含的對象不少于指定參數MinPts，則稱p為核心對象。

1.1.3 直接密度可達

在數據集D中，存在一點q在點p的鄰域內，且p是核心對象，則稱點q是從p出發的直接密度可達[4]。

1.1.4 密度可達

存在點鏈p1,p2,…,pn,其中p1=q,pn=p,使pi+1是從pi直接密度可達，則稱點p是從點q關于參數Eps，MinPts密度可達的[4]。

1.1.5 密度相連

存在點o，使得點p和q都從點o密度可達，則稱點p和q是在給定Eps,Minpts參數下密度相連的。

1.2 DBSCAN算法可改進性

傳統的DBSCAN算法在聚類前，會對Eps與MinPts設置全局統一的值，依據這兩個參數尋找密度相連的點的最大集合，完成最終聚類。但這種參數設定方式忽略了密度不均勻分布的數據集時的聚類：當全局變量Eps值適用于密度分布稠密的區域聚類時，對于密度分布稀疏的區域易產生大量的孤立點；而當對密度稀疏的區域適用時，對密度稠密的區域會產生大量的噪聲點被聚到相應的簇中。因此可見，這種選擇全局變量的做法并不適用于密度分布不均勻的數據集，會使算法在處理多層次數據集聚類時準確度降低。

另外，傳統的算法在對象鄰域查詢時存在一定的冗余操作：需要對每個樣本點都進行鄰域查詢，來判斷Eps鄰域內的點是否大于MinPts,從而判斷是否為核心點，再根據核心點尋找其密度相連的點，將其聚為一類。然而在多個對象鄰域出現交集時，部分對象就會被重復掃描，如此操作很大程度上降低了算法的時間效率。

2 改進的DBSCAN算法

2.1 相關概念

2.1.1 密度層次

具有密度分布情況相近的點的集合稱為同一密度層次。本算法從小到大排列各對象的第k個最近鄰距離值，根據k-dist圖判斷數據集的密度層次分類。兩種數據集的k-dist示例如圖1所示。

圖1 k-dist示例圖

對比看出,B數據集的密度分布不均勻，分為3個密度層次。

2.1.2 密度水平線

在k-dist圖中，變化較為平緩的曲線稱為密度水平曲線，落在密度水平曲線上的點密度往往比較相近[5]。圖1中，a、b、c即為密度不同的三段密度水平線。

2.1.3 密度轉折線

在k-dist圖中，變化較為陡峭的曲線稱為密度轉折線，多用于分隔兩個密度不同的對象集[6]。圖1中，d、e即為密度轉折曲線。

2.1.4 DK分析圖

在k-dist圖中，取k-dist圖中相鄰兩點的差值，將其繪制成的圖形即為DK分析圖，并將k-dist圖中相鄰兩點的差值記為DK值。DK分析圖中的橫坐標為數據點序號，縱坐標為DK差值。

2.1.5 DK鄰域

為了排除密度轉折線上的點及噪聲點而設定的DK值范圍。主要計算方法為：令DK值升序排列，取一定比例的DK值計算平均值，表示為Ave(x%);為選擇密度水平線上的點，將給定一個閾值δ，DK值鄰域即為[Ave(x%)-δ,Ave(x%)+δ]，并稱Ave(x%)-δ為DK下鄰域值，Ave(x%)+δ為DK上鄰域值。

2.1.6 區域密度半徑

各密度層次下的聚類半徑。文中取DK上鄰域值對應的最近的DK鄰域中的點的k-dist值作為其所在密度分區的半徑。

2.1.7 初始區域中心點

各密度層次用于初次聚類的候選核心點[7]。文中將密度水平曲線上的k-dist最小值作為其所在分區的初始區域中心，各分區的其他對象按照k-dist值升序排列存入隊列。

2.1.8 核心點(Core point)

某點的密度半徑鄰域內包含的對象不小于給定參數，我們稱這樣的點為核心點。文中首先對初始區域中心點進行判斷，如不滿足條件則選擇本密度區域隊列中下一對象進行判斷，直到滿足條件結束。

2.1.9 密度相連

在數據集D中，存在一點q，如果點q既屬于類A1,又屬于類A2，并且點q的區域半徑鄰域內的對象數不小于給定參數，那么A1和A2中的核心對象和q是密度相連的[8]。

本算法中對于密度直接可達、密度可達等定義與傳統的基于密度算法中的定義相同。

2.2 算法描述

本算法主要思想是：將非均勻密度數據集通過k-dist圖分成若干個密度均勻的數據層，在密度均勻的數據層中分別進行聚類，算法的具體步驟如下：

輸入：數據集D，K值，DK分析中的x%和δ值，MinPts。

輸出：聚類結果集。

1) 密度層次劃分。計算數據集D所有對象的k-dist(pi),其中i=1,2,…,n，繪制k-dist分區圖,得到各個分區數據集Di。

2)確定密度半徑和初始區域中心點：根據DKm=k-distm-k-distm-1(m>1)計算DK值，取前x%比例的DKm計算其平均值Avg(x%),繪制DK分析圖。根據2.1.6和2.1.7來確定密度分區的密度半徑Epsi及初始區域中心點Oi。

3)確定密度核心點：判斷Oi的Epsi內點數是否不小于MinPts，如果條件成立，則確定Oi為本區域的核心點，并將其標記為Ci；否則，選擇隊列中的下一點進行同樣判斷。

4)根據確定的核心點Oi，密度區域半徑Epsi，調用改進后的快速聚類算法，對各密度區域中的點進行聚類。

5)重復執行步驟3)和步驟4)，當所有點都被聚類后停止。

2.3 快速聚類算法

DBSCAN算法將簇定義為密度相連的點的最大集合，它需要檢索每一個點及其鄰域來尋找密度相連的簇。然而在多個對象的鄰域出現交集時，部分對象就會被重復掃描，對每個點都進行鄰域查詢顯然是不值得的[8]。文中快速聚類方法的主要思想為：

1)以Oi為起始點，計算鄰域Epsi內的對象數，如果|Neighbors|≥Minpts，則將Neighbors內的所有點均標記為與Oi同類，否則標記為噪音。

2)尋找密度隊列Di中未標記類別的下一個核心對象，并按照1)中的方法對鄰域內各點進行類別標注。

3)當出現某一個點qi既屬于Oi的類又屬于Oj的類的情況時，則檢查該點與兩個類中的核心點是否是密度相連，如果是則將兩個類進行合并；如果不是，則規定點qi屬于最初被劃分到的類中。

4)在所有的密度隊列中執行上述方法，直到所有的點都被標記為相應的類結束。

具體步驟如下：

輸入：核心點Oi，密度區域半徑Epsi，MinPts。

輸出：聚成的各個簇Ci

算法偽代碼：

while(Di.clustered){

// 以Oi為起始點，掃描鄰域Epsi內的對象

Neighbors=NeigborScan(Oi,Epsi);

//滿足條件將Neighbors內的所有點均標記為與Oi同類，否則標記為噪音。

if(|Neighbors|>=Minpts){

if(qi.cluster=Oi.cluster){

if(qi.cluster= Oj.cluster){

//某點同屬兩類判斷兩類是否滿足合并條件

Neigborsi=NeigborScan(qi,Epsi);

if(|Neigborsi|>=Minpts)

Oi.cluster=merge(Oi.cluster,Oj.cluster);

else qi.cluster=Oi.cluster;

}

qi.cluster=Oi.cluster;

}

Neighbors.cluster=Oi.cluster;

}

else Oi.cluster=noise;

Oi= Di.nextUnclusteredCore;

}

3 實驗分析

實驗采用C語言進行編程，分別使用了一般數據集和UCI數組庫的Iris數據集對算法的有效性進行了驗證。

3.1 一般數據集

利用人工方法構造了數據集D，包涵30個數據，并按照改進算法的步驟對數據進行聚類：實驗首先指定參數k=2,來計算距離各個數據點的距離第二大的值，并升序排列所有k-dist值。通過繪制的2-dist圖將數據集D分為三個密度區域,如圖2所示。

圖2 數據集D的2-dist圖

通過計算相鄰點的k-dist差值得到該數據集的DK分析圖。這里對DK值進行升序排列，并取x=80，即取前80%的DK值來做平均計算。經過計算可得Avg(80%)=0.05。為去除密度轉折點及噪聲點，令δ=0.12，因此可以得到DK鄰域為[-0.07,0.17]。又因為k-dist圖是從小到大排列的，所以計算出的相鄰兩點的DK值是非負的，繼而得到真實的DK鄰域為[0,0.17]。

認為位于DK鄰域外的點是密度轉折線上的點，如圖3所示。

圖3 數據集D的DK分析

圖中17～19點、24～27點處在DK鄰域外，所以認為這些點落在密度轉折線上。位于DK鄰域內部的點可認為他是在密度水平線上的點，根據2.1.7可以確定該數據集的各個初始區域中心點分別為：點1，點20，點28。根據2.1.6，我們看出該數據集的DK上鄰域值為0.17，所以各個區域的密度半徑分別為：點16的k-dist值0.81，點23的k-dist值1.35；點29的k-dist值1.96。文中取MinPts=3，對于一般密度不均勻的數據集聚類情況如圖4所示。

圖4 實驗結果

3.2 Iris數據集

Iris數據集來自UCI數據庫，主要包含了150個關于3種鳶尾花的生物統計數據[9]，每種花具有四個屬性。為將數據映射在二維坐標上，在實驗之前，先對數據進行預處理，取萼片的長寬比(Sepallength/Sepalwidth)作為橫軸，花瓣的長寬比作為縱軸(Petallength/Petalwidth)。通過多次試驗取平均值，與傳統的DBSCAN算法在執行時間、準確率上的對比，其中準確率的計算方法如下：

(1)

具體實驗結果見表1。

表1 實驗對比結果

傳統DBSCAN算法與文中算法的聚類結果分別如圖5和圖6所示，其中“×”表示噪聲點。

圖5 DBSCAN實驗結果

圖6 文中算法實驗結果

4 結 語

由于傳統密度聚類法在聚類前期會設定全局參數，使其對密度分布不均勻數據樣本聚類效果不佳，基于此提出一種基于區域中心點的密度聚類算法。該算法借助k-dist圖確定密度分類，通過DK分析確定區域中心點和區域半徑，并通過改進的快速聚類算法分別在兩種數據集上進行了驗證。通過實驗證實，改進后的算法能夠對密度分布不均勻數據集進行更好地聚類，算法效率及準確率較傳統DBSCAN算法有所提高。

[1] 周水庚,周傲英,曹晶.基于數據分區的DBSCAN算法[J].計算機研究與發展,2000,37(10):1153-1159.

[2] Hua Jiang, Jing Li, Shenghe Yi, et al. 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].計算機應用研究,2009,26(10):3721-3723.

[4] 范明,孟小峰.數據挖掘：概念與技術[M].3版.北京:機械工業出版社,2012.

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

[6] 鄭丹,王潛平.K-means初始聚類中心的選擇算法[J].計算機應用,2012,32(8):2186-2188,2192.

[7] 范敏,李澤明,石欣.一種基于區域中心點的聚類算法[J].計算機工程與科學,2014,36(9)：1611-1616.

[8] 李杰,賈瑞玉,張璐璐.一個改進的基于DBSCAN的空間聚類算法研究[J].計算機技術與發展,2007,17(1)：114-116.

[9] Iris Data Set(UCI)[DB/OL]. (2012-09-10)[2016-03-20]. http://www.datatang.com/data/551.

Multi-level data set density clustering algorithm based on local center object

WEI Xuda, PANG Huanli*

(School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012， China)

Withk-dist plot and DK Analysis, the non-uniform data is classfied and selected for local radius based on different densities to determine the initial local core object. The improved fast clustering algorithm is used for clustering and verified to be efficient in multi-level data set clustering in two data sets experiment.

nonuniform density clustering; DBSCAN; local core object; k-nearest neighbors; DK analysis.

2016-03-20

吉林省科技廳自然科學基金資助項目(201215116)

魏姁妲(1991-)，女，漢族，黑龍江綏化人，長春工業大學碩士研究生，主要從事人工智能方向研究,E-mail:332507132@qq.com. *通訊作者：逄煥利(1970-)，男，漢族，吉林白山人，長春工業大學副教授，碩士，主要從事數據挖掘和人工智能方向研究,E-mail:panghuanli@ccut.edu.cn.

10.15923/j.cnki.cn22-1382/t.2016.6.12

TP 301.6

A

1674-1374(2016)06-0576-05