馮 玲，劉克劍*，唐福喜, 孟慶瑞

(1.西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都 610039;2.西藏飛躍智能科技有限公司，西藏 拉薩 850000)

?

·計(jì)算機(jī)軟件理論、技術(shù)與應(yīng)用·

一種基于網(wǎng)格查詢(xún)的改進(jìn)DBSCAN算法

馮 玲1，劉克劍1*，唐福喜1, 孟慶瑞2

(1.西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都 610039;2.西藏飛躍智能科技有限公司，西藏 拉薩 850000)

針對(duì)DBSCAN算法聚類(lèi)時(shí)時(shí)間復(fù)雜度較高、當(dāng)邊界點(diǎn)同時(shí)屬于多個(gè)類(lèi)時(shí)其聚類(lèi)準(zhǔn)確率較低的問(wèn)題，在網(wǎng)格查詢(xún)思想和OPTICS算法的基礎(chǔ)上，提出一種改進(jìn)的DBSCAN算法(GO-DBSCAN算法)。進(jìn)行聚類(lèi)操作前，為降低聚類(lèi)的時(shí)間復(fù)雜度，先基于網(wǎng)格查詢(xún)的思想將數(shù)據(jù)集劃分成不同的網(wǎng)格，在進(jìn)行項(xiàng)目鄰域查詢(xún)時(shí)，只須遍歷項(xiàng)目附近網(wǎng)格數(shù)據(jù)而不必遍歷整個(gè)數(shù)據(jù)集；在進(jìn)行項(xiàng)目聚類(lèi)時(shí)，主要考慮該項(xiàng)目與其附近核心項(xiàng)目的最小可達(dá)距離，因此，將OPTICS算法中的最小可達(dá)距離引入到DBSCAN算法中，以提高算法對(duì)邊界點(diǎn)處理的準(zhǔn)確度。仿真實(shí)驗(yàn)結(jié)果表明，GO-DBSCAN在邊界點(diǎn)處理的準(zhǔn)確率和運(yùn)行效率方面較DBSCAN都有所提高。

聚類(lèi)算法；DBSCAN算法；OPTICS算法；網(wǎng)格聚類(lèi)；邊界點(diǎn)

傳統(tǒng)的聚類(lèi)算法[1-12]分5類(lèi)：基于劃分的聚類(lèi)、基于層次的聚類(lèi)、基于網(wǎng)格的聚類(lèi)、基于模型的聚類(lèi)、基于密度的聚類(lèi)。基于密度的聚類(lèi)的代表算法是DBSCAN[7]、OPTICS[10]等。DBSCAN算法是一種使用范圍最廣的基于密度的聚類(lèi)算法。與傳統(tǒng)方法相比，DBSCAN算法的優(yōu)勢(shì)是可以發(fā)現(xiàn)任何形狀的數(shù)據(jù)集，能夠有效地處理噪聲點(diǎn)，不需要設(shè)定聚類(lèi)后的簇個(gè)數(shù)[7]；然而，DBSCAN是直接對(duì)數(shù)據(jù)集進(jìn)行處理，數(shù)據(jù)集越大，數(shù)據(jù)預(yù)處理的消耗時(shí)間過(guò)長(zhǎng)。該算法時(shí)間復(fù)雜度為O(n2)，在數(shù)據(jù)集較大的情況下，其效率會(huì)受到明顯的影響[8]。該算法對(duì)參數(shù)敏感性太強(qiáng)，初始參數(shù)的設(shè)置直接影響算法的質(zhì)量和效果[9]。如果某一邊界點(diǎn)同時(shí)屬于多個(gè)類(lèi)，也會(huì)影響該算法的質(zhì)量和效果[13]。

在DBSCAN算法的時(shí)間復(fù)雜度方面，研究者提出基于網(wǎng)格思想的改進(jìn)。劉淑芬等將數(shù)據(jù)空間進(jìn)行網(wǎng)格劃分，在數(shù)據(jù)對(duì)象ε-鄰域中只遍歷k-鄰接網(wǎng)格集合所構(gòu)成的區(qū)域，從而降低DBSCAN 的時(shí)間復(fù)雜度[14]；Huang等將DBSCAN與CLIQUE算法相結(jié)合，把DBSCAN中的核心對(duì)象轉(zhuǎn)化為核心網(wǎng)格處理，以網(wǎng)格為最小處理對(duì)象[15]； Amineh Amini等[16]提出一種將基于密度的聚類(lèi)算法和基于網(wǎng)格的聚類(lèi)算法相結(jié)合的方法；周水庚等提出在進(jìn)行類(lèi)擴(kuò)展的時(shí)候利用核心點(diǎn)鄰域中部分鄰域點(diǎn)進(jìn)行擴(kuò)展，提出一種基于數(shù)據(jù)取樣的DBSCAN算法[7]和一種基于數(shù)據(jù)分區(qū)的DBSCAN算法[8]。

本文對(duì)DBSCAN算法的2點(diǎn)不足進(jìn)行改進(jìn)： 1)為解決邊界點(diǎn)同時(shí)屬于2個(gè)及2個(gè)以上類(lèi)會(huì)影響DBSCAN算法質(zhì)量和效果的問(wèn)題，將OPTICS算法中最小可達(dá)距離引入到DBSCAN算法中；2)為解決DBSCAN算法效率問(wèn)題，將基于網(wǎng)格查詢(xún)的思想應(yīng)用于DBSCAN算法[15]，在每次迭代的時(shí)候不用遍歷所有數(shù)據(jù)點(diǎn)，只須遍歷鄰近網(wǎng)格中的數(shù)據(jù)點(diǎn)。本文將這2種思想相結(jié)合提出一種基于網(wǎng)格的改進(jìn)DBSCAN算法。由于改進(jìn)算法參考了OPTICS算法及基于網(wǎng)格(Grid)查詢(xún)思想，所以改進(jìn)算法叫GO-DBSCAN。

1 DBSCAN算法和OPTICS算法

DBSCAN是一種典型的基于密度的聚類(lèi)算法，利用密度的連通性可以發(fā)現(xiàn)任何形狀的簇[7]。OPTICS是DBSCAN算法的一種改進(jìn)。這2種算法不僅能根據(jù)密度發(fā)現(xiàn)任何形狀的類(lèi)，而且能有效地處理噪聲點(diǎn)。

1.1 基本概念

定義1 某一對(duì)象在ε為半徑的鄰域至少包含minpts個(gè)對(duì)象，則該對(duì)象稱(chēng)為核心對(duì)象。

定義2 某一對(duì)象的鄰域包含的對(duì)象數(shù)少于minpts[8]，則該對(duì)象稱(chēng)為邊界點(diǎn)。

定義3 某一對(duì)象的鄰域包含的對(duì)象數(shù)為0，則該對(duì)象稱(chēng)為噪聲點(diǎn)。

定義4 若對(duì)象p是核心對(duì)象，對(duì)象q在p的鄰域內(nèi)，則對(duì)象q與p直接密度可達(dá)。

定義5 存在一個(gè)數(shù)據(jù)鏈p1,p2,…，pn,其中p1=p,pn=q,若對(duì)象pi與對(duì)象pi+1是直接密度可達(dá)，則對(duì)象p與對(duì)象q是密度可達(dá)，如圖1所示。

圖1 p與q密度可達(dá)

定義6 若數(shù)據(jù)集中存在一對(duì)象o，使得對(duì)象p與對(duì)象q對(duì)對(duì)象o是密度可達(dá)的，則對(duì)象p和對(duì)象q是密度相連，如圖2所示。

圖2 p與q密度相連

定義7 使某對(duì)象成為核心對(duì)象的最小鄰域半徑ε'稱(chēng)為核心距離，若p不是核心對(duì)象即不存在核心距離之說(shuō)。

定義8 對(duì)象q到核心對(duì)象p的可達(dá)距離是指對(duì)象q到對(duì)象p的歐幾里得距離，若p不是核心對(duì)象，則不存在q到p的可達(dá)距離的定義。

1.2 DBSCAN算法思想

遍歷數(shù)據(jù)集，得到任意一個(gè)核心對(duì)象p，將p的ε-鄰域中的沒(méi)被處理的對(duì)象歸屬到與p同一類(lèi)，然后把p的ε-鄰域中的對(duì)象作為即將遍歷的對(duì)象(種子對(duì)象)，再對(duì)種子對(duì)象進(jìn)行同對(duì)象p操作，直到種子對(duì)象遍歷完成，得到一個(gè)完整的類(lèi)。重復(fù)以上操作，發(fā)現(xiàn)其他類(lèi)。當(dāng)所有數(shù)據(jù)點(diǎn)遍歷完成后，不屬于任何類(lèi)的數(shù)據(jù)對(duì)象即為噪聲點(diǎn)[17]。

1.3 OPTICS算法思想

遍歷數(shù)據(jù)集，得到任意一個(gè)核心對(duì)象p，計(jì)算p的核心距離和p的ε鄰域中的對(duì)象到p的可達(dá)距離，然后把p放入結(jié)果隊(duì)列，p的ε-鄰域中的對(duì)象放入有序隊(duì)列中，并通過(guò)可達(dá)距離排序，把有序隊(duì)列中可達(dá)距離最小的對(duì)象取出，重復(fù)對(duì)象p的操作，直到可達(dá)隊(duì)列中的對(duì)象操作完成，都放入結(jié)果隊(duì)列中。重復(fù)以上全部操作，當(dāng)所有數(shù)據(jù)對(duì)象操作完成后，得到一個(gè)以可達(dá)距離排序的結(jié)果序列。

OPTICS算法雖有ε和minpts 2個(gè)參數(shù)，但是OPTICS對(duì)參數(shù)的敏感度較DBSCAN算法已大大減小。OPTICS算法聚類(lèi)得到的有序序列通過(guò)處理可以得到DBSCAN算法在任何參數(shù)下的聚類(lèi)結(jié)果。

2 GO-DBSCAN算法

本文針對(duì)DBSCAN算法的時(shí)間復(fù)雜度較高和邊界點(diǎn)同時(shí)屬于多個(gè)類(lèi)時(shí)聚類(lèi)準(zhǔn)確率較低的問(wèn)題，提出一種改進(jìn)算法(GO-DBSCAN)。GO-DBSCAN實(shí)現(xiàn)思想主要分2步：1)在進(jìn)行聚類(lèi)操作之前，基于網(wǎng)格查詢(xún)思想對(duì)數(shù)據(jù)集進(jìn)行劃分，將數(shù)據(jù)集劃分成不同的網(wǎng)格；2)用改進(jìn)的聚類(lèi)算法對(duì)劃分后的數(shù)據(jù)集進(jìn)行聚類(lèi)。

2.1 GO-DBSCAN對(duì)數(shù)據(jù)集進(jìn)行網(wǎng)格劃分

本文提出的GO-DBSCAN結(jié)合網(wǎng)格查詢(xún)思想，在進(jìn)行聚類(lèi)之前將數(shù)據(jù)集劃分成不同的網(wǎng)格單元，在計(jì)算對(duì)象ε-鄰域時(shí)就無(wú)須遍歷整個(gè)數(shù)據(jù)集，只須遍歷其鄰近網(wǎng)格即可，這樣大大提高算法的運(yùn)行效率。

本文對(duì)網(wǎng)格單元的定義為：選取網(wǎng)格單元的長(zhǎng)度為算法的鄰域半徑ε的2倍，即2ε，將數(shù)據(jù)在每個(gè)維度上以長(zhǎng)度為2ε進(jìn)行相同的劃分[18]，從而將整個(gè)數(shù)據(jù)空間劃分成不同的網(wǎng)格；網(wǎng)格單元表示為(d1,d2,…，dn),其中n為數(shù)據(jù)維度，di表示網(wǎng)格在不同維度上的序號(hào)，1≤i≤n。

數(shù)據(jù)對(duì)象p所屬網(wǎng)格定義為：(x1,x2,…,xn)表示n維數(shù)據(jù)對(duì)象p每個(gè)維度上的坐標(biāo)；p第i維對(duì)應(yīng)網(wǎng)格序號(hào)di應(yīng)滿(mǎn)足xi/2ε≤di≤(xi+2ε)/2ε且di為整數(shù)。

設(shè)定網(wǎng)格單元后，在計(jì)算對(duì)象ε-鄰域時(shí)，在每個(gè)維度上最多遍歷9個(gè)網(wǎng)格單元，以二維數(shù)據(jù)為例，數(shù)據(jù)對(duì)象p(x,y)所屬網(wǎng)格為(d1,d2),則其在計(jì)算ε-鄰域所須遍歷的范圍如圖3所示。

(d1-1，d2+1)(d1，d2+1)(d1+1，d2+1)(d1-1，d2)(d1，d2)?(x，y)(d1+1，d2)(d1-1，d2-1)(d1，d2-1)(d1+1，d2-1)d1d1+1d1-1

圖3 二維空間的鄰域網(wǎng)格

2.2 GO-DBSCAN對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)

DBSCAN算法在運(yùn)行過(guò)程中每個(gè)數(shù)據(jù)對(duì)象只會(huì)被處理一次，運(yùn)行完后，每個(gè)數(shù)據(jù)對(duì)象的類(lèi)標(biāo)簽屬性被確定，而且類(lèi)標(biāo)簽是唯一的、不能更改的，這樣同時(shí)屬于2個(gè)類(lèi)的邊界點(diǎn)在聚類(lèi)過(guò)程中出現(xiàn)錯(cuò)誤也是無(wú)法更改的。GO-DBSCAN算法把OPTICS算法中的關(guān)鍵因素——最小可達(dá)距離(MAD)，融入其中，利用每個(gè)數(shù)據(jù)點(diǎn)的MAD來(lái)確定該數(shù)據(jù)點(diǎn)屬于哪類(lèi)。在這個(gè)過(guò)程中，不僅每個(gè)數(shù)據(jù)點(diǎn)被處理一次，而且在ε-鄰域核心數(shù)據(jù)點(diǎn)改變的情況下數(shù)據(jù)點(diǎn)的MAD會(huì)不斷更新。類(lèi)標(biāo)簽隨著MAD的改變而改變，就是說(shuō)數(shù)據(jù)點(diǎn)的類(lèi)標(biāo)簽始終跟離該數(shù)據(jù)點(diǎn)最近的核心對(duì)象的類(lèi)標(biāo)簽一樣。在GO-DBSCAN中，這樣的改進(jìn)會(huì)更精確地處理同時(shí)屬于多個(gè)類(lèi)的邊界點(diǎn)，也在一定程度上減小了算法對(duì)初始參數(shù)的依賴(lài)。

當(dāng)聚類(lèi)數(shù)據(jù)集每個(gè)類(lèi)之間分布較為稠密，而且邊界點(diǎn)也比較多時(shí)，邊界點(diǎn)同時(shí)屬于多個(gè)類(lèi)的情況很常見(jiàn)，如圖4所示的數(shù)據(jù)集，其中，綠色表示核心點(diǎn)，黑色表示邊界點(diǎn)，紅色表示噪聲點(diǎn)。DBSCAN處理時(shí)容易出現(xiàn)誤差，然而，GO-DBSCAN可以很好地處理這樣的數(shù)據(jù)集。GO-DBSCAN偽代碼實(shí)現(xiàn)如圖5所示。

圖4 每個(gè)類(lèi)分布較為稠密的聚類(lèi)

為比較邊界點(diǎn)的準(zhǔn)確度，本文提出邊界點(diǎn)聚類(lèi)準(zhǔn)確率(rate)的概念。

rate=correct_num/all_num。

(1)

式中：correct_num表示邊界點(diǎn)聚類(lèi)正確點(diǎn)數(shù)；all_num表示所有邊界點(diǎn)的個(gè)數(shù)。

本文判斷邊界點(diǎn)聚類(lèi)正確與否是根據(jù)對(duì)象與確定對(duì)象所屬簇的核心點(diǎn)的可達(dá)距離(acceptable-distance ，AD)來(lái)確定。若2種聚類(lèi)方法中，一些邊界點(diǎn)的聚類(lèi)結(jié)果不同，則比較這些邊界點(diǎn)在不同方法中的AD，AD較小的類(lèi)則為聚類(lèi)正確，反之則聚類(lèi)錯(cuò)誤。

距離采用歐式距離，其計(jì)算公式為

(2)

式中：n表示數(shù)據(jù)對(duì)象維數(shù)；x1i表示第1個(gè)點(diǎn)第i維坐標(biāo)；x2i表示第2個(gè)點(diǎn)第i維坐標(biāo)。

輸入：D：樣本數(shù)據(jù)集ε：鄰域半徑Minpts：鄰域密度閾值輸出：聚類(lèi)完成的數(shù)據(jù)集方法：對(duì)樣本數(shù)據(jù)集進(jìn)行網(wǎng)格劃分，并標(biāo)記數(shù)據(jù)對(duì)象所屬網(wǎng)格編號(hào)將所有對(duì)象標(biāo)記為unvisitedfor數(shù)據(jù)集中每一個(gè)對(duì)象p將p標(biāo)記為visitedifp的ε鄰域E中對(duì)象數(shù)>=Minpts新建一個(gè)簇C，將p添加到C；forE中的每個(gè)對(duì)象qifq是unvisited標(biāo)記q為visited；令MAD為q的最小可達(dá)距離；令q的MAD等于q到p的歐式距離；將q添加到C；ifq的ε鄰域中對(duì)象數(shù)>=Minpts將其鄰域中所有對(duì)象添加到E；endifelse令d為q到p的歐式距離ifdistance=Minpts將其鄰域中所有對(duì)象添加到E；并將其鄰域中的所有對(duì)象從原屬類(lèi)中刪除；endifendifendifend forendifendfor

圖5 GO-DBSCAN偽代碼

3 實(shí)驗(yàn)與結(jié)果

本文參照T. N. Tran等[13]對(duì)DBSCAN算法在MATLAB上的實(shí)現(xiàn)思路，分析GO-DBSCAN算法，把它與DBSCAN算法的聚類(lèi)質(zhì)量進(jìn)行比較，并將GO-DBSCAN、DBSCAN和OPTICS算法的運(yùn)行時(shí)間進(jìn)行比較。其中GO-DBSCAN對(duì)數(shù)據(jù)進(jìn)行劃分網(wǎng)格預(yù)處理所需時(shí)間不算在運(yùn)行時(shí)間內(nèi)。

首先對(duì)聚類(lèi)質(zhì)量進(jìn)行比較。表1是DBSCAN和GO-DBSCAN算法對(duì)圖4的模擬數(shù)據(jù)庫(kù)進(jìn)行聚類(lèi)的結(jié)果，實(shí)驗(yàn)參數(shù)minpts統(tǒng)一為5。從表1看出：DBSCAN在處理邊界點(diǎn)時(shí)會(huì)存在誤差；當(dāng)初始參數(shù)設(shè)置較大時(shí)，GO-DBSCAN可以減小DBSCAN對(duì)初始參數(shù)的依賴(lài)。

表1 DBSCAN算法與GO-DBSCAN算法聚類(lèi)質(zhì)量比較

實(shí)驗(yàn)結(jié)果表明：DBSCAN算法對(duì)模擬數(shù)據(jù)庫(kù)進(jìn)行聚類(lèi)的最佳參數(shù)ε=6；當(dāng)ε發(fā)生變化時(shí)，DBSCAN算法的聚類(lèi)結(jié)果受到明顯的影響，GO-DBSCAN算法的聚類(lèi)結(jié)果受到的影響較小。圖6和圖7分別示出DBSCAN算法和GO-DBSCAN算法在ε=7時(shí)得到的聚類(lèi)結(jié)果?？梢钥闯?，當(dāng)ε設(shè)置較大時(shí)，DBSCAN算法的聚類(lèi)結(jié)果受到參數(shù)變化的影響明顯，比GO-DBSCAN算法受到的影響大，這說(shuō)明GO-DBSCAN算法在一定程度上減小了DBSCAN算法對(duì)參數(shù)的敏感度。

圖6 DBSCAN在ε=7的聚類(lèi)結(jié)果

圖7 GO-DBSCAN在ε=7的聚類(lèi)結(jié)果

圖8示出GO-DBSCAN與DBSCAN和OPTICS的運(yùn)行時(shí)間的比較結(jié)果。由于主機(jī)內(nèi)存問(wèn)題，本測(cè)試最大數(shù)據(jù)量為1萬(wàn)?？梢钥闯?，隨著數(shù)據(jù)量逐漸增大，GO-DBSCAN的時(shí)間耗費(fèi)明顯比DBSCAN小。

圖8 3種算法的運(yùn)行時(shí)間對(duì)比

4 結(jié)束語(yǔ)

DBSCAN算法是傳統(tǒng)的基于密度的聚類(lèi)算法中最常用的一種。本文主要就DBSCAN算法的時(shí)間復(fù)雜高，對(duì)邊界點(diǎn)同時(shí)屬于多個(gè)類(lèi)從而使聚類(lèi)質(zhì)量低的問(wèn)題進(jìn)行分析，提出一種改進(jìn)算法(GO-DBSCAN算法)。GO-DBSCAN算法首先對(duì)數(shù)據(jù)集進(jìn)行網(wǎng)格劃分，以提高算法的運(yùn)行效率，接著在對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)時(shí)，采用最小可達(dá)距離，有效地解決了邊界點(diǎn)聚類(lèi)準(zhǔn)確率不高的問(wèn)題，同時(shí)在一定程度上減小了初始參數(shù)對(duì)聚類(lèi)質(zhì)量的影響。實(shí)驗(yàn)結(jié)果表明，GO-DBSCAN算法對(duì)類(lèi)之間分布稠密的數(shù)據(jù)集的聚類(lèi)準(zhǔn)確率比DBSCAN算法高，運(yùn)行效率也比DBSCAN算法高。

[1]孫吉貴,劉杰,趙連宇.聚類(lèi)算法研究[J].Journal of Software,2008,19(1):48.

[2]周濤,陸惠玲.數(shù)據(jù)挖掘中聚類(lèi)算法研究進(jìn)展[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(12):100.

[3]王千,王成，馮振元，等.K-means聚類(lèi)算法研究綜述[J].電子設(shè)計(jì)工程，201,20(7):21.

[4]陳旭玲,樓佩煌.改進(jìn)層次聚類(lèi)算法在文獻(xiàn)分析中應(yīng)用[J].數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用,2009,30(4):277.

[5]WANG Wei， YANG Jiong, MUNTZ Richard. STING:A Statistical Information Grid Approach to Spatial Data Mining[C]//Athens Proceedings of the 23rd Conference on CLDB.[S.l.]:IEEE,1997:186-195.

[6]宋浩遠(yuǎn).基于模型的聚類(lèi)方法研究[J].重慶科技學(xué)院學(xué)報(bào)(自然科學(xué)版),2008,10(3):71.

[7]周水庚,范曄,周傲英.基于數(shù)據(jù)取樣的DBSCAN算法[J].小型微型計(jì)算機(jī)系統(tǒng),2000,21(12):1270.

[8]周水庚,周傲英,曹英.基于數(shù)據(jù)分區(qū)的DBSCAN算法[J].計(jì)算機(jī)研究與發(fā)展,2000,37(10):1153.

[9]于亞飛,周愛(ài)武.一種改進(jìn)的DBSCAN密度算法[J].計(jì)算機(jī)研究與發(fā)展,2011,21(2):30.

[10]曾依靈,許洪波,白碩.改進(jìn)的OPTICS算法及其在文本聚類(lèi)中的應(yīng)用[J].中文信息報(bào),2008,22(1):51.

[11]杜紅樂(lè),張燕.密度不均衡數(shù)據(jù)分類(lèi)算法[J].西華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，34(5)：16.

[12]金珠，馬小平.基于蟻群聚類(lèi)算法的SVM監(jiān)督式訓(xùn)練方法[J].西華大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,30(1):56.

[13]Tran T N, Drab K,Daszykowski M. Revised DBSCAN Algorithm to Cluster Data with Dense Adjacent Clusters[J]. Chemometrics & Intelligent Laboratory Systems, 2013, 120(2):92.

[14]劉淑芬,孟冬雪,王曉燕.基于網(wǎng)格單元的DBSCAN算法[J].吉林大學(xué)學(xué)報(bào)(工學(xué)版),2014,44(4):1135.

[15]HUANGDarong,WANG Peng.Grid-based DBSCAN Algorithm with Referential Parameters[J].Pthysics Procedia,2012：24：1166.

[16]Amineh Amini, The Ying Wah, Mahmoud Reza Saybani, et al. A Study of Density-grid Based Clustering Algorithms on Data Streams[C]// Eighth International Conference on Fuzzy Systems and Knowledge Discovery. [S.l.]:IEEE, 2011:1652-1656.

[17]SELIM Mimariglu, EMIN Aksehirli.Improving DBSCAN’s Execution Time by Using a Pruning Technique on Bit Vector[J].Pattern Recognition Letters,2011,32:1572.

[18]陳燕俐,洪龍,金達(dá)文,等.一種簡(jiǎn)單有效的基于密度的聚類(lèi)分析[J].南京郵電學(xué)院學(xué)報(bào),2005,25(4):24.

(編校：饒莉)

Improvements of DBSCAN Algorithm Based on Grid

FENG Ling1, LIU Kejian1*, TANG Fuxi1，MENG Qingrui2

(1.School of Computer and Software Engineering,Xihua University, Chengdu 610039 China;2.TibetFeiyueIntelligentTechnologyCO.,Ltd.,Lasa850000China)

In view of the low accuracy of boundary point clustered and the excessively high time complexity of DBSCAN algorithm, a DBSCAN algorithm is proposed based on GO-DBSCAN algorithm and OPTICS algorithm. The algorithm introduced the minimum reachable distance of OPTICS algorithm into the DBSCAN algorithm. Generally, the minimum distance between object and the near core object is a mainly considered factor for the clustering based on DBSCAN algorithm. Therefore, the introduce improves the clustering accuracy. The idea of grid query is proposed to reduce the size of traversal data of objects and this results in the decrease of DBSCAN algorithm’s time complexity. Before clustering, data set is divided into different grid based on grid query rules to reduce clustering time complexity. When project neighborhood is to be queried, it is necessary to traverse only the project near grid data other than the entire data set. The theoretical analysis and simulation results show that GO-DBSCAN can effectively improve the accuracy of boundary point clustered and reduce the time complexity.

clustering algorithm; DBSCAN algorithm；OPTICS algorithm; grid clustering; boundary point

2016-03-31

西華大學(xué)重點(diǎn)科研基金項(xiàng)目(Z1320607)；國(guó)家科技支撐計(jì)劃項(xiàng)目西藏自然科學(xué)博物館數(shù)字館關(guān)鍵技術(shù)研究及集成示范(2011BAH26B01)；國(guó)家自然科學(xué)基金(61271413、61472329、61532009)；數(shù)字空間安全保障四川省高校重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金課題資助(szjj2015-055)；四川省教育廳重點(diǎn)項(xiàng)目資助(16ZA0165)；西華大學(xué)研究生創(chuàng)新基金(YCJJ2015187；YCJJ2016169)；西華大學(xué)校重點(diǎn)項(xiàng)目(Z1222625)。

TP181；TP301.6

A

1673-159X(2016)05-0025-5

10.3969/j.issn.1673-159X.2016.05.005

*通信作者：劉克劍(1974—)，男，副教授，碩士，CCF會(huì)員，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)和無(wú)線網(wǎng)絡(luò)技術(shù)、智能信息處理技術(shù)、高性能計(jì)算技術(shù)。E-mail:liukejian@gmail.com