周治平，王杰鋒，朱書偉，孫子文

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

一種改進(jìn)的自適應(yīng)快速AF-DBSCAN聚類算法

周治平，王杰鋒，朱書偉，孫子文

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

摘要：基于密度的DBSCAN聚類算法可以識別任意形狀簇，但存在全局參數(shù)Eps與MinPts的選擇需人工干預(yù)，采用的區(qū)域查詢方式過程復(fù)雜且易丟失對象等問題，提出了一種改進(jìn)的參數(shù)自適應(yīng)以及區(qū)域快速查詢的密度聚類算法。根據(jù)KNN分布與數(shù)學(xué)統(tǒng)計分析自適應(yīng)計算出最優(yōu)全局參數(shù)Eps與MinPts，避免聚類過程中的人工干預(yù)，實現(xiàn)了聚類過程的全自動化。通過改進(jìn)種子代表對象選取方式進(jìn)行區(qū)域查詢，無需漏檢操作，有效提高了聚類的效率。對4種典型數(shù)據(jù)集的密度聚類實驗結(jié)果表明，本文算法使得聚類精度提高了8.825%，聚類的平均時間減少了0.92 s。

關(guān)鍵詞：密度聚類；DBSCAN；區(qū)域查詢；全局參數(shù)；KNN分布；數(shù)學(xué)統(tǒng)計分析

中文引用格式：周治平，王杰鋒，朱書偉，等.一種改進(jìn)的自適應(yīng)快速AF-DBSCAN聚類算法[J]. 智能系統(tǒng)學(xué)報， 2016, 11(1): 93-98.

英文引用格式：ZHOU Zhiping，WANG Jiefeng，ZHU Shuwei，et al. An improved adaptive and fast AF-DBSCAN clustering algorithm[J]. CAAI Transactions on Intelligent Systems, 2016,11(1):93-98.

數(shù)據(jù)挖掘是一種從大量數(shù)據(jù)中發(fā)現(xiàn)感興趣信息的技術(shù)，聚類算法在數(shù)據(jù)挖掘應(yīng)用中日益廣泛。其中，基于密度的聚類算法可以發(fā)現(xiàn)任意形狀的簇且能夠較好地處理噪聲數(shù)據(jù)，越來越受到廣泛的關(guān)注。DBSCAN算法能夠發(fā)現(xiàn)任意形狀的簇，并有效識別離群點，但聚類之前需要人工選擇Eps和minPts 2個參數(shù)。當(dāng)數(shù)據(jù)量增大時，要求較大的內(nèi)存支持，I/O消耗也很大；當(dāng)空間聚類的密度不均勻，聚類間距離相差很大時，聚類質(zhì)量較差[1-3]。針對DBSCAN算法在大型數(shù)據(jù)庫與多密度數(shù)據(jù)集聚類精度低，計算復(fù)雜度高，全局參數(shù)人工選取等問題，已有很多學(xué)者進(jìn)行了相關(guān)研究：S. Mimaroglu等[4]提出對位向量使用裁剪技術(shù)，H. Jiang等[5]提出一種基于劃分的DBSCAN算法，B. Borah等[6]提出一種改進(jìn)的基于抽樣的DBSCAN算法，D. Kellner[7]提出基于格點的DBSCAN算法，旨在解決DBSCAN算法在內(nèi)存占用，處理高維數(shù)據(jù)和密度分布不均數(shù)據(jù)聚類效果不好等問題；H. F. Zhou、S. H. Yue、Y.Ma、S.JAHIRABAPKAR和Z. Y. Xiong等[8-12]基于數(shù)據(jù)的數(shù)學(xué)統(tǒng)計特性，確定全局參數(shù)；B. Liu[13]提出一種基于密度的快速聚類方法，按照特定維的坐標(biāo)排序，選擇有序的未被標(biāo)記的在核心對象鄰域以外的點作為種子擴(kuò)展簇。綜上所述，基于密度聚類算法的改進(jìn)點主要集中在全局參數(shù)的選擇以及提高密度聚類效率等。DBSCAN全局參數(shù)選擇根據(jù)k-dist曲線人工確定，過程繁瑣，實用性不高。其他基于統(tǒng)計分析的方法，部分以特定數(shù)據(jù)分布確定全局參數(shù)，而數(shù)據(jù)分布存在不確定性，以特定分布規(guī)定不能準(zhǔn)確反映數(shù)據(jù)的分布特性，使計算出的全局參數(shù)不準(zhǔn)確；提高密度聚類效率主要集中在區(qū)域查詢中的代表對象的選擇，但是選擇的代表對象進(jìn)行區(qū)域查詢時存在丟失對象現(xiàn)象，對丟失對象進(jìn)行查漏操作，一定程度上增加了區(qū)域查詢的復(fù)雜度。

1DBSCAN算法及改進(jìn)算法

DBSCAN是一種經(jīng)典的基于密度聚類算法[8]，可以自動確定簇的數(shù)量，并能夠發(fā)現(xiàn)任意形狀的簇。Eps近鄰表示一個給定對象的Eps半徑內(nèi)的近鄰稱為該對象的Eps近鄰，表示為NEps(p)：

(1)

直接密度可達(dá)是指對于給定的MinPts和Eps，從對象q可以直接密度可達(dá)p，需要滿足的條件為

(2)

DBSCAN算法的全局參數(shù)MinPts和Eps的選取依賴于人工干預(yù)，對密度分布均勻的數(shù)據(jù)根據(jù)k-dist曲線升序排列后，人為選擇曲線變化幅度開始陡升的點作為Eps參數(shù)，并且確定MinPts參數(shù)為固定常量4，實施過程繁瑣，依賴于人工干預(yù)。本文提出一種全局參數(shù)自適應(yīng)選擇的方法，根據(jù)數(shù)據(jù)距離空間的統(tǒng)計分布特性，統(tǒng)計出k-dist值的分布情況，曲線擬合出分布曲線，通過計算擬合曲線拐點處對應(yīng)的值，自適應(yīng)確定出Eps參數(shù)，并根據(jù)數(shù)據(jù)中每個點Eps領(lǐng)域內(nèi)點數(shù)的分布情況，計算出參數(shù)MinPts。

DBSCAN以核心對象P來拓展一個簇，通過對包含在P鄰域內(nèi)的點進(jìn)行區(qū)域查詢擴(kuò)展簇。包含在P鄰域的對象相互交叉，Q是P的鄰域內(nèi)的一個對象，如果它的鄰域被P中其他對象的鄰域所覆蓋，那么Q的區(qū)域查詢操作就可以省略，Q不需要作為種子對象用于類的擴(kuò)展。因此，用于Q的區(qū)域查詢時間和Q作為核心對象的內(nèi)存占用都可以被省去。而一個核心對象邊界的對象更有利于作為候選對象被選為種子，因為內(nèi)部對象鄰域往往會被外部對象的鄰域覆蓋。因此，抽樣種子實際上是選擇的代表對象能夠準(zhǔn)確描繪出核心對象鄰域形狀的問題。實際上，對于密度聚類，在核心對象鄰域內(nèi)相當(dāng)一部分種子對象可以被忽略，選擇核心對象邊界的部分代表對象進(jìn)行類的擴(kuò)展，從而達(dá)到減少區(qū)域查詢頻度的目的。

為了自適應(yīng)確定合適的全局參數(shù)MinPts和Eps，減少內(nèi)存占用量和I/O消耗，提高DBSCAN的計算效率， 基于這些分析，本文提出一種改進(jìn)的自適應(yīng)快速算法(adaptive and fast density-based spatial clustering of applications with noise，AF-DBSCAN)，旨在以自適應(yīng)方式確定合理的全局參數(shù)MinPts和Eps，以及區(qū)域查詢時選擇部分具有代表性的對象作為種子對象進(jìn)行類擴(kuò)展。改進(jìn)算法描述如下：1)自適應(yīng)確定全局參數(shù)Eps和MinPts；2)將所有點分類，分別標(biāo)記為核心點、邊界點和噪聲點；3)刪除標(biāo)記處的噪聲點；4)連接距離在Eps距離內(nèi)的所有核心點，并歸入到同一簇中；5)各個簇中的核心點對應(yīng)種子代表對象的選擇；6)遍歷數(shù)據(jù)集，根據(jù)選擇的代表對象進(jìn)行區(qū)域查詢，將邊界點分入與之對應(yīng)核心點的簇中。如果數(shù)據(jù)集中所有點都被處理，算法結(jié)束。

2AF-DBSCAN聚類算法

2.1參數(shù)Eps與參數(shù)MinPts的確定

由于密度衡量指標(biāo)單一，本文算法數(shù)據(jù)集主要針對簇密度差異不明顯的數(shù)據(jù)。根據(jù)輸入數(shù)據(jù)集D計算出距離分布矩陣DISTn×n，如式(3)所示：

式中：n為數(shù)據(jù)集D的對象數(shù)目；DISTn×n是一個n行和n列的實對稱矩陣，其中每個元素表示數(shù)據(jù)集D中對象i和對象j之間的距離。計算DISTn×n中的每個元素的值，然后逐行按照升序排列。用DISTn×i表示DISTn×n中第i列的的值,對DISTn×i中每一列進(jìn)行升序排列得到KNN分布，如圖1所示。

圖1　KNN分布Fig.1　KNN distribution

圖1中，k=1,2,…,45，根據(jù)k-dist分布曲線可以看出，k=4的dist4曲線可以反映出其他distk曲線的形狀。本文選擇k=4的distk(k-最近鄰距離)的數(shù)據(jù)進(jìn)行統(tǒng)計分析，dist4的概率分布圖2所示。

圖2　distk(k=4)概率分布Fig.2　Probability distribution of distk(k=4)

從圖1可以看出，任何一條曲線都是在平緩變化后急劇上升，distk中大部分值落在一個比較密集的區(qū)域內(nèi)，因此可以判斷distk中大部分值應(yīng)落在一個比較密集的區(qū)域內(nèi)(曲線平緩段)。如果可以通過數(shù)學(xué)方法找出distk中平緩變化到急劇上升處的點，或者distk概率分布最為密集的區(qū)域，則可確定掃描半徑參數(shù)Eps，所以本文選擇圖1中distk拐點處的值為Eps。由圖2可以得到distk的概率分布情況，假如能夠通過數(shù)學(xué)方法找到分布曲線的峰值，也可以用峰值點所對應(yīng)的k-最近鄰距離值(橫坐標(biāo)刻度)作為Eps。

對于概率分布數(shù)據(jù)，通過分析數(shù)據(jù)集的統(tǒng)計特性，建立統(tǒng)計模型對數(shù)據(jù)集進(jìn)行曲線擬合[14]。本文通過實驗對概率分布使用傅里葉、高斯和多項式3種典型曲線擬合方法，如圖3所示。

圖3　歸一化KNN分布擬合曲線Fig.3　Fitting curves of normalized KNN distribution

其中，高斯曲線擬合方法的效果最佳，但是由于概率分布的擬合精度過低，不可用于全局參數(shù)Eps的估計。擬合結(jié)果為SSE：312.7，R-square：0.675 5，調(diào)整R-square：0.651 4，RMSE：3.403，參數(shù)SSE和RMSE越接近0擬合越準(zhǔn)確；R-square和調(diào)整后的R-square越接近于1越準(zhǔn)確；高斯擬合曲線如式(4)所示：

(4)

根據(jù)KNN升序排列曲線確定Eps，對dist4曲線進(jìn)行擬合。對于升序排列得到KNN分布數(shù)據(jù)，采用3種擬合方法進(jìn)行曲線擬合。實驗發(fā)現(xiàn)高斯擬合精度高，但擬合階數(shù)高，計算復(fù)雜度高；傅里葉擬合精度不高；而多項式擬合不僅擬合階數(shù)低，而且擬合精度高，計算復(fù)雜度低，擬合結(jié)果為SSE：0.046 36，R-square：0.988 3，調(diào)整 R-square：0.988，RMSE：0.017 88，如圖4所示。多項式曲線擬合如式(5)所示。

(5)

圖4　多項式擬合曲線Fig.4　Polynomial fitting curves

(6)

式中：Pi表示在點i的Eps鄰域的點數(shù)。

本文將密度聚類算法與基于統(tǒng)計模型相結(jié)合，基于數(shù)理統(tǒng)計理論，假定數(shù)據(jù)集由統(tǒng)計過程產(chǎn)生，并通過找出最佳擬合模型來描述數(shù)據(jù)集，自適應(yīng)計算出最優(yōu)全局參數(shù)Eps和Minpts。

2.2種子代表對象的選擇

本文提出一種改進(jìn)的基于DBSCAN的快速聚類算法，在通過選用核心對象附近區(qū)域包含的所有對象的代表對象作為種子對象擴(kuò)展類，減少了區(qū)域查詢的次數(shù)，減低了聚類時間和I/O開銷。

對于一個給出Eps和MinPts的核心對象P，為了便于闡述，僅考慮二維對象，算法可用于其他大于二維的高維對象。代表對象選擇過多則難以發(fā)揮算法效率，選擇過少則容易造成對象丟失，影響算法聚類質(zhì)量。FDBSCAN[15]算法在區(qū)域查詢后，在第1輪核心點區(qū)域查詢時無丟失對象現(xiàn)象，而在以種子對象進(jìn)行類擴(kuò)展時，產(chǎn)生丟失對象，因此需要選擇足夠多的代表對象；而I-DBSCAN[6]在二維數(shù)據(jù)中采用至多8個代表對象，不存在對象丟失的情況。本文結(jié)合FDBSCAN與I-DBSCAN，第1輪區(qū)域查詢時采用4個代表對象進(jìn)行類擴(kuò)展，繼續(xù)擴(kuò)展類時，選擇8個代表對象進(jìn)行類擴(kuò)展。本算法在提高查詢效率的基礎(chǔ)上，解決了類擴(kuò)展時丟失對象的問題。

本文提出的代表對象選擇方式如下：以核心對象p為中心，Eps為半徑畫圓，以對象p為原點畫坐標(biāo)系交圓周于A、C、E和G4點，再畫2條分別與x軸成45°和135°角的直徑交圓周于B、D、F和H4點。第1輪選擇代表對象時，以核心點邊界的A、C、E和G點為參照，在p的Eps區(qū)域中分別選擇離A、C、E和G點最近的點作為代表對象。當(dāng)對于不同參照點存在離其距離最近的點為同一點時，此點只能被選擇1次，且屬于第1個參考點的代表對象。如果對象是n維數(shù)據(jù)，則至多可以選擇2n個代表對象。

在繼續(xù)擴(kuò)展類選擇代表對象時，以核心點邊界的A、B、C、D、E、F、G和H點為參照點選擇代表對象，其原則為p的Eps區(qū)域中選擇離參考點對象最近的點作為代表對象，即使1個代表對象到2個以上的參考點都是最近的，它也只被選1次，且歸入第1個參考點的代表對象。因此，在二維空間范圍內(nèi)，對任一對象的被選代表對象數(shù)最多為8個。一般情況下，對n維空間，由于有3n-1個參考點和2n個象限，因此被選種子數(shù)最多為3n-1個，按照以上方式實現(xiàn)區(qū)域查詢，有效提高聚類效率以及解決對象丟失的問題。

3實驗與分析

本文算法采用了Java語言，在Windows XP系統(tǒng)和eclipse環(huán)境下運(yùn)行，PC機(jī)硬件配置：Pentium(R) CPU，3 GB內(nèi)存, 300 GB硬盤。為了驗證本文改進(jìn)算法的有效性，根據(jù)數(shù)據(jù)集的維度、數(shù)據(jù)量和密度分布3種標(biāo)準(zhǔn)進(jìn)行數(shù)據(jù)庫的選擇，選取UCI數(shù)據(jù)庫中的4種典型數(shù)據(jù)集Iris、Wine、Glass和cmc。根據(jù)聚類準(zhǔn)確度和時間特性分析2項指標(biāo)對DBSCAN、I-DBSCAN[8]和AF-DBSCAN算法性能進(jìn)行比較分析，其中聚類準(zhǔn)確度采用F-Measure[13]。DBSCAN中根據(jù)k-dist曲線，選取dist4曲線圖進(jìn)行參數(shù)Eps值的確定，如圖5所示。

根據(jù)圖5中平緩變化后急劇上升處對應(yīng)的k-dist值作為全局參數(shù)Eps的值，且Minpts值設(shè)為4。得到4種數(shù)據(jù)集Iris、Wine、Glass和cmc的(Minpts，Eps)分別為(4，0.436)、(4，27.330)、(4，3.700)和(4，1.732)。

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

(b)Glass數(shù)據(jù)集

(c)cmc數(shù)據(jù)集

(d)Wine數(shù)據(jù)集圖5　dist4曲線Fig.5　Curve of dist4

本文提出的AF-DBSCAN算法的(Minpts，Eps)分別為(7，0.389)、(6，29.870)、(4，2.695)和(5，1.646)。4種數(shù)據(jù)集聚類結(jié)果如表1所示。由表1可以看出，本文提出的AF-DBSCAN算法自適應(yīng)計算出的全局參數(shù)減少了人為根據(jù)k-dist曲線確定全局參數(shù)Eps的誤差及工作量，以及設(shè)定MinPts為固定值4，而使聚類結(jié)果達(dá)不到全局最優(yōu)的效果。通過比較分析4種數(shù)據(jù)集的聚類結(jié)果，AF-DBSCAN的F-Measure值均優(yōu)于其他2種典型算法，尤其在Iris和Glass數(shù)據(jù)集上，聚類精度比DBSCAN算法分別高12.55%和13.18%。而I-DBSCAN算法規(guī)定數(shù)據(jù)符合泊松分布，對于不同數(shù)據(jù)集F-Measure值不穩(wěn)定，不能適應(yīng)不同統(tǒng)計特性的數(shù)據(jù)集。由于密度衡量指標(biāo)單一，AF-DBSCAN算法適用于簇密度差異不明顯的數(shù)據(jù)集。經(jīng)過區(qū)域查詢改進(jìn)后的AF-DBSCAN算法，運(yùn)行速度明顯比DBSCAN和I-DBSCAN算法快，有效減少了密度聚類的時間。

表1　實驗比較

4結(jié)束語

本文針對DBSCAN算法的參數(shù)選取困難，計算效率低以及區(qū)域查詢中代表對象選擇后類擴(kuò)展易丟失對象點等問題，提出一種改進(jìn)的自適應(yīng)快速AF-DBSCAN聚類算法，通過分析數(shù)據(jù)的KNN的數(shù)學(xué)統(tǒng)計規(guī)律，輔助用戶自適應(yīng)確定全局參數(shù)Eps與MinPts。通過改進(jìn)的區(qū)域查詢方法，有效提高類擴(kuò)展的效率，AF-DBSCAN算法解決了DBSCAN算法人工干預(yù)，給定全局參數(shù)導(dǎo)致聚類質(zhì)量惡化以及大數(shù)據(jù)集計算效率低的問題。

參考文獻(xiàn):

[1]吉根林, 姚瑤. 一種分布式隱私保護(hù)的密度聚類算法[J]. 智能系統(tǒng)學(xué)報, 2009, 4(2): 137-141.

JI Genlin, YAO Yao. Density-based privacy preserving distributed clustering algorithm[J]. CAAI transactions on intelligent systems, 2009, 4(2): 137-141.

[2]SMITI A, ELOUEDI Z. DBSCAN-GM: An improved clustering method based on Gaussian means and DBSCAN techniques[C]//2012 IEEE 16th International Conference on Intelligent Engineering Systems (INES). Lisbon, 2012: 573-578.

[3]ZHANG Jiashu, KEREKES J. An adaptive density-based model for extracting surface returns from photon-counting laser altimeter data[J]. Geoscience and remote sensing letters, 2015, 12(4): 726-730.

[4]MIMAROGLU S, AKSEHIRLI E. Improving DBSCAN’s execution time by using a pruning technique on bit vectors[J]. Pattern Recognition Letters, 2011, 32(13): 1572-1580.

[5]JIANG Hua, LI Jing, YI Shenghe, et al. A new hybrid method based on partitioning-based DBSCAN and ant clustering[J]. Expert systems with applications, 2011, 38(8): 9373-9381.

[6]BORAH B, BHATTACHARYYA D K. An improved sampling-based DBSCAN for large spatial databases[C]//Proceedings of International Conference on Intelligent Sensing and Information Processing(ICISIP). Chennai, India, 2004: 92-96.

[7]KELLNER D, KLAPPSTEIN J, DIETMAYER K. Grid-based DBSCAN for clustering extended objects in radar data[C]//2012 IEEE Intelligent Vehicles Symposium. Alcal de Henares, Madrid, Spain, 2012: 365-370.

[8]ZHOU Hongfang, Wang Peng, LI Hongyan. Research on adaptive parameters determination in DBSCAN algorithm[J]. Journal of information & computational science, 2012, 9(7): 1967-1973.

[9]YUE Shihong, LI Ping, GUO Jidong, et al. A statistical information-based clustering approach in distance space[J]. Journal of Zhejiang university science, 2005, 6A(1):71-78.

[10]MA Yu, GAO Yuling, SONG Shaoyun. The algorithm of DBSCAN based on probability distribution[C]//5th International Symposium on IT in Medicine and Education. Xining, China, 2014: 2785-2792.

[11]JAHIRABADKAR S, KULKARNI P. Algorithm to determine ε-distance parameter in density based clustering[J]. Expert systems with applications, 2014, 41(6): 2939-2946.

[12]XIONG Zhongyang, CHEN Ruotian, ZHANG Yufang, et al. Multi-density DBSCAN algorithm based on density levels partitioning[J]. Journal of information and computational science, 2012, 9(10): 2739-2749.

[13]LIU Bing. A fast density-based clustering algorithm for large databases[C]//2006 International Conference on Machine Learning and Cybernetics. Dalian, China, 2006: 996-1000.

[14]夏魯寧.SA-DBSCAN:一種自適應(yīng)基于密度聚類算法[J]. 中國科學(xué)院研究生院學(xué)報, 2009, 26(4): 530-538.

XIA Luning. SA-DBSCAN: A self-adaptive density-based clustering algorithm[J]. Journal of the graduate school of the Chinese academy of sciences, 2009, 26(4): 530-538.

[15]周水庚, 周傲英, 曹晶, 等. 一種基于密度的快速聚類算法[J]. 計算機(jī)研究與發(fā)展, 2000, 37(11): 1287-1292.

ZHOU Shuigeng, ZHOU Aoying, CAO Jing, et al. A fast density-based clustering algorithm[J]. Journal of computer research & development, 2000, 37(11): 1287-1292.

An improved adaptive and fast AF-DBSCAN clustering algorithm

ZHOU Zhiping， WANG Jiefeng， ZHU Shuwei， SUN Ziwen

(School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, China)

Abstract：The density-based DBSCAN clustering algorithm can identify clusters with arbitrary shape, however, the choice of the global parameters Eps and MinPts requires manual intervention, the process of regional query is complex and loses objects easily. Therefore, an improved density clustering algorithm with adaptive parameter for fast regional queries is proposed. Using KNN distribution and mathematical statistical analysis, the optimal global parameters Eps and MinPts are adaptively calculated, so as to avoid manual intervention and enable full automation of the clustering process. The regional query is conducted by improving the selection manner of the object, which is represented by a seed and thus avoiding manual intervention, and so the clustering efficiency is effectively increased. The experiment results looking at density clustering of four typical data sets show that the proposed method effectively improves clustering accuracy by 8.825% and reduces the average time of clustering by 0.92 s.

Keywords：density clustering; DBSCAN; region query; global parameters; KNN distribution; mathematical statistics and analysis

DOI:10.11992.tis.201410021

收稿日期：2014-10-13.網(wǎng)絡(luò)出版日期：2015-09-30.

基金項目：國家自然科學(xué)基金資助項目(61373126);江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金-前瞻性聯(lián)合研究基金資助項目(BY2013015-33).

通信作者：王杰鋒. E-mail：18352513420@163.com.

中圖分類號：TP181

文獻(xiàn)標(biāo)志碼：A

文章編號：1673-4785(2016)01-0093-06

作者簡介：

周治平，男，1962年生，教授，博士，主要研究方向為檢測技術(shù)與自動化裝置、信息安全等。

王杰鋒，男，1989年生，碩士研究生，主要研究方向為智能信息處理。

朱書偉，男，1990年生，碩士研究生，主要研究方向為數(shù)據(jù)挖掘與人工智能。

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150930.1557.028.html