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

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

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

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

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

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

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

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

中文引用格式：周治平，王杰鋒，朱書偉，等.一種改進(jìn)的自適應(yīng)快速AF-DBSCAN聚類算法[J]. 智能系統(tǒng)學(xué)報(bào)， 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)任意形狀的簇，并有效識(shí)別離群點(diǎn)，但聚類之前需要人工選擇Eps和minPts 2個(gè)參數(shù)。當(dāng)數(shù)據(jù)量增大時(shí)，要求較大的內(nèi)存支持，I/O消耗也很大；當(dāng)空間聚類的密度不均勻，聚類間距離相差很大時(shí)，聚類質(zhì)量較差[1-3]。針對(duì)DBSCAN算法在大型數(shù)據(jù)庫與多密度數(shù)據(jù)集聚類精度低，計(jì)算復(fù)雜度高，全局參數(shù)人工選取等問題，已有很多學(xué)者進(jìn)行了相關(guān)研究：S. Mimaroglu等[4]提出對(duì)位向量使用裁剪技術(shù)，H. Jiang等[5]提出一種基于劃分的DBSCAN算法，B. Borah等[6]提出一種改進(jìn)的基于抽樣的DBSCAN算法，D. Kellner[7]提出基于格點(diǎn)的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)計(jì)特性，確定全局參數(shù)；B. Liu[13]提出一種基于密度的快速聚類方法，按照特定維的坐標(biāo)排序，選擇有序的未被標(biāo)記的在核心對(duì)象鄰域以外的點(diǎn)作為種子擴(kuò)展簇。綜上所述，基于密度聚類算法的改進(jìn)點(diǎn)主要集中在全局參數(shù)的選擇以及提高密度聚類效率等。DBSCAN全局參數(shù)選擇根據(jù)k-dist曲線人工確定，過程繁瑣，實(shí)用性不高。其他基于統(tǒng)計(jì)分析的方法，部分以特定數(shù)據(jù)分布確定全局參數(shù)，而數(shù)據(jù)分布存在不確定性，以特定分布規(guī)定不能準(zhǔn)確反映數(shù)據(jù)的分布特性，使計(jì)算出的全局參數(shù)不準(zhǔn)確；提高密度聚類效率主要集中在區(qū)域查詢中的代表對(duì)象的選擇，但是選擇的代表對(duì)象進(jìn)行區(qū)域查詢時(shí)存在丟失對(duì)象現(xiàn)象，對(duì)丟失對(duì)象進(jìn)行查漏操作，一定程度上增加了區(qū)域查詢的復(fù)雜度。

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

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

(1)

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

(2)

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

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

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

2AF-DBSCAN聚類算法

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

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

式中：n為數(shù)據(jù)集D的對(duì)象數(shù)目；DISTn×n是一個(gè)n行和n列的實(shí)對(duì)稱矩陣，其中每個(gè)元素表示數(shù)據(jù)集D中對(duì)象i和對(duì)象j之間的距離。計(jì)算DISTn×n中的每個(gè)元素的值，然后逐行按照升序排列。用DISTn×i表示DISTn×n中第i列的的值,對(duì)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)計(jì)分析，dist4的概率分布圖2所示。

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

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

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

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

其中，高斯曲線擬合方法的效果最佳，但是由于概率分布的擬合精度過低，不可用于全局參數(shù)Eps的估計(jì)。擬合結(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，對(duì)dist4曲線進(jìn)行擬合。對(duì)于升序排列得到KNN分布數(shù)據(jù)，采用3種擬合方法進(jìn)行曲線擬合。實(shí)驗(yàn)發(fā)現(xiàn)高斯擬合精度高，但擬合階數(shù)高，計(jì)算復(fù)雜度高；傅里葉擬合精度不高；而多項(xiàng)式擬合不僅擬合階數(shù)低，而且擬合精度高，計(jì)算復(fù)雜度低，擬合結(jié)果為SSE：0.046 36，R-square：0.988 3，調(diào)整 R-square：0.988，RMSE：0.017 88，如圖4所示。多項(xiàng)式曲線擬合如式(5)所示。

(5)

圖4　多項(xiàng)式擬合曲線Fig.4　Polynomial fitting curves

(6)

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

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

2.2種子代表對(duì)象的選擇

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

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

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

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

3實(shí)驗(yàn)與分析

本文算法采用了Java語言，在Windows XP系統(tǒng)和eclipse環(huán)境下運(yùn)行，PC機(jī)硬件配置：Pentium(R) CPU，3 GB內(nèi)存, 300 GB硬盤。為了驗(yàn)證本文改進(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)確度和時(shí)間特性分析2項(xiàng)指標(biāo)對(duì)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中平緩變化后急劇上升處對(duì)應(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)計(jì)算出的全局參數(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ù)符合泊松分布，對(duì)于不同數(shù)據(jù)集F-Measure值不穩(wěn)定，不能適應(yīng)不同統(tǒng)計(jì)特性的數(shù)據(jù)集。由于密度衡量指標(biāo)單一，AF-DBSCAN算法適用于簇密度差異不明顯的數(shù)據(jù)集。經(jīng)過區(qū)域查詢改進(jìn)后的AF-DBSCAN算法，運(yùn)行速度明顯比DBSCAN和I-DBSCAN算法快，有效減少了密度聚類的時(shí)間。

表1　實(shí)驗(yàn)比較

4結(jié)束語

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

參考文獻(xiàn):

[1]吉根林, 姚瑤. 一種分布式隱私保護(hù)的密度聚類算法[J]. 智能系統(tǒng)學(xué)報(bào), 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é)報(bào), 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ì)算機(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.

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

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

中圖分類號(hào)：TP181

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

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

作者簡介：

周治平，男，1962年生，教授，博士，主要研究方向?yàn)闄z測技術(shù)與自動(dòng)化裝置、信息安全等。

王杰鋒，男，1989年生，碩士研究生，主要研究方向?yàn)橹悄苄畔⑻幚怼?/p>

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

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