基于區(qū)域中心點(diǎn)的多層次數(shù)據(jù)集密度聚類算法

魏姁妲， 逄煥利

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)

基于區(qū)域中心點(diǎn)的多層次數(shù)據(jù)集密度聚類算法

魏姁妲， 逄煥利*

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)

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

非均勻密度聚類； DBSCAN； 區(qū)域中心點(diǎn)； K鄰域； DK分析

0 引 言

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

文中提出處理非均勻密度數(shù)據(jù)的改進(jìn)算法。通過k-dist圖和DK分析方法，發(fā)現(xiàn)各密度分區(qū)及其對應(yīng)的初始中心點(diǎn)和半徑，最后分別對各區(qū)域進(jìn)行聚類。同時(shí)，文中提出一種快速聚類算法來提高各密度區(qū)域聚類時(shí)的效率。實(shí)驗(yàn)表明,本算法可以有效地聚類非均勻密度數(shù)據(jù)，時(shí)間效率及準(zhǔn)確率較傳統(tǒng)算法有所提升。

1 DBSCAN算法

1.1 DBSCAN算法

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

1.1.1 Eps鄰域

給定對象半徑Eps內(nèi)的區(qū)域。

1.1.2 核心對象

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

1.1.3 直接密度可達(dá)

在數(shù)據(jù)集D中，存在一點(diǎn)q在點(diǎn)p的鄰域內(nèi)，且p是核心對象，則稱點(diǎn)q是從p出發(fā)的直接密度可達(dá)[4]。

1.1.4 密度可達(dá)

存在點(diǎn)鏈p1,p2,…,pn,其中p1=q,pn=p,使pi+1是從pi直接密度可達(dá)，則稱點(diǎn)p是從點(diǎn)q關(guān)于參數(shù)Eps，MinPts密度可達(dá)的[4]。

1.1.5 密度相連

存在點(diǎn)o，使得點(diǎn)p和q都從點(diǎn)o密度可達(dá)，則稱點(diǎn)p和q是在給定Eps,Minpts參數(shù)下密度相連的。

1.2 DBSCAN算法可改進(jìn)性

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

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

2 改進(jìn)的DBSCAN算法

2.1 相關(guān)概念

2.1.1 密度層次

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

圖1 k-dist示例圖

對比看出,B數(shù)據(jù)集的密度分布不均勻，分為3個(gè)密度層次。

2.1.2 密度水平線

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

2.1.3 密度轉(zhuǎn)折線

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

2.1.4 DK分析圖

在k-dist圖中，取k-dist圖中相鄰兩點(diǎn)的差值，將其繪制成的圖形即為DK分析圖，并將k-dist圖中相鄰兩點(diǎn)的差值記為DK值。DK分析圖中的橫坐標(biāo)為數(shù)據(jù)點(diǎn)序號，縱坐標(biāo)為DK差值。

2.1.5 DK鄰域

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

2.1.6 區(qū)域密度半徑

各密度層次下的聚類半徑。文中取DK上鄰域值對應(yīng)的最近的DK鄰域中的點(diǎn)的k-dist值作為其所在密度分區(qū)的半徑。

2.1.7 初始區(qū)域中心點(diǎn)

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

2.1.8 核心點(diǎn)(Core point)

某點(diǎn)的密度半徑鄰域內(nèi)包含的對象不小于給定參數(shù)，我們稱這樣的點(diǎn)為核心點(diǎn)。文中首先對初始區(qū)域中心點(diǎn)進(jìn)行判斷，如不滿足條件則選擇本密度區(qū)域隊(duì)列中下一對象進(jìn)行判斷，直到滿足條件結(jié)束。

2.1.9 密度相連

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

本算法中對于密度直接可達(dá)、密度可達(dá)等定義與傳統(tǒng)的基于密度算法中的定義相同。

2.2 算法描述

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

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

輸出：聚類結(jié)果集。

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

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

3)確定密度核心點(diǎn)：判斷Oi的Epsi內(nèi)點(diǎn)數(shù)是否不小于MinPts，如果條件成立，則確定Oi為本區(qū)域的核心點(diǎn)，并將其標(biāo)記為Ci；否則，選擇隊(duì)列中的下一點(diǎn)進(jìn)行同樣判斷。

4)根據(jù)確定的核心點(diǎn)Oi，密度區(qū)域半徑Epsi，調(diào)用改進(jìn)后的快速聚類算法，對各密度區(qū)域中的點(diǎn)進(jìn)行聚類。

5)重復(fù)執(zhí)行步驟3)和步驟4)，當(dāng)所有點(diǎn)都被聚類后停止。

2.3 快速聚類算法

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

1)以O(shè)i為起始點(diǎn)，計(jì)算鄰域Epsi內(nèi)的對象數(shù)，如果|Neighbors|≥Minpts，則將Neighbors內(nèi)的所有點(diǎn)均標(biāo)記為與Oi同類，否則標(biāo)記為噪音。

2)尋找密度隊(duì)列Di中未標(biāo)記類別的下一個(gè)核心對象，并按照1)中的方法對鄰域內(nèi)各點(diǎn)進(jìn)行類別標(biāo)注。

3)當(dāng)出現(xiàn)某一個(gè)點(diǎn)qi既屬于Oi的類又屬于Oj的類的情況時(shí)，則檢查該點(diǎn)與兩個(gè)類中的核心點(diǎn)是否是密度相連，如果是則將兩個(gè)類進(jìn)行合并；如果不是，則規(guī)定點(diǎn)qi屬于最初被劃分到的類中。

4)在所有的密度隊(duì)列中執(zhí)行上述方法，直到所有的點(diǎn)都被標(biāo)記為相應(yīng)的類結(jié)束。

具體步驟如下：

輸入：核心點(diǎn)Oi，密度區(qū)域半徑Epsi，MinPts。

輸出：聚成的各個(gè)簇Ci

算法偽代碼：

while(Di.clustered){

// 以O(shè)i為起始點(diǎn)，掃描鄰域Epsi內(nèi)的對象

Neighbors=NeigborScan(Oi,Epsi);

//滿足條件將Neighbors內(nèi)的所有點(diǎn)均標(biāo)記為與Oi同類，否則標(biāo)記為噪音。

if(|Neighbors|>=Minpts){

if(qi.cluster=Oi.cluster){

if(qi.cluster= Oj.cluster){

//某點(diǎn)同屬兩類判斷兩類是否滿足合并條件

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 實(shí)驗(yàn)分析

實(shí)驗(yàn)采用C語言進(jìn)行編程，分別使用了一般數(shù)據(jù)集和UCI數(shù)組庫的Iris數(shù)據(jù)集對算法的有效性進(jìn)行了驗(yàn)證。

3.1 一般數(shù)據(jù)集

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

圖2 數(shù)據(jù)集D的2-dist圖

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

認(rèn)為位于DK鄰域外的點(diǎn)是密度轉(zhuǎn)折線上的點(diǎn)，如圖3所示。

圖3 數(shù)據(jù)集D的DK分析

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

圖4 實(shí)驗(yàn)結(jié)果

3.2 Iris數(shù)據(jù)集

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

(1)

具體實(shí)驗(yàn)結(jié)果見表1。

表1 實(shí)驗(yàn)對比結(jié)果

傳統(tǒng)DBSCAN算法與文中算法的聚類結(jié)果分別如圖5和圖6所示，其中“×”表示噪聲點(diǎn)。

圖5 DBSCAN實(shí)驗(yàn)結(jié)果

圖6 文中算法實(shí)驗(yàn)結(jié)果

4 結(jié) 語

由于傳統(tǒng)密度聚類法在聚類前期會(huì)設(shè)定全局參數(shù)，使其對密度分布不均勻數(shù)據(jù)樣本聚類效果不佳，基于此提出一種基于區(qū)域中心點(diǎn)的密度聚類算法。該算法借助k-dist圖確定密度分類，通過DK分析確定區(qū)域中心點(diǎn)和區(qū)域半徑，并通過改進(jìn)的快速聚類算法分別在兩種數(shù)據(jù)集上進(jìn)行了驗(yàn)證。通過實(shí)驗(yàn)證實(shí)，改進(jìn)后的算法能夠?qū)γ芏确植疾痪鶆驍?shù)據(jù)集進(jìn)行更好地聚類，算法效率及準(zhǔn)確率較傳統(tǒng)DBSCAN算法有所提高。

[1] 周水庚,周傲英,曹晶.基于數(shù)據(jù)分區(qū)的DBSCAN算法[J].計(jì)算機(jī)研究與發(fā)展,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] 熊忠陽,吳林敏,張玉芳.針對非均勻數(shù)據(jù)集的DBSCAN 過濾式改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究,2009,26(10):3721-3723.

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

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

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

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

[8] 李杰,賈瑞玉,張璐璐.一個(gè)改進(jìn)的基于DBSCAN的空間聚類算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,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

吉林省科技廳自然科學(xué)基金資助項(xiàng)目(201215116)

魏姁妲(1991-)，女，漢族，黑龍江綏化人，長春工業(yè)大學(xué)碩士研究生，主要從事人工智能方向研究,E-mail:332507132@qq.com. *通訊作者：逄煥利(1970-)，男，漢族，吉林白山人，長春工業(yè)大學(xué)副教授，碩士，主要從事數(shù)據(jù)挖掘和人工智能方向研究,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