李光興

(成都農(nóng)業(yè)科技職業(yè)學(xué)院基礎(chǔ)部 成都 611130)

?

一種網(wǎng)格k-近鄰集的邊界點(diǎn)識別算法

李光興

(成都農(nóng)業(yè)科技職業(yè)學(xué)院基礎(chǔ)部 成都 611130)

為了高效識別聚類邊界,根據(jù)邊界周圍區(qū)域存在密度差異的特征,提出了一種網(wǎng)格k-近鄰集的邊界識別算法(BGN)。在網(wǎng)格空間中,該算法根據(jù)網(wǎng)格單元和它最近鄰居單元的k-近鄰集的質(zhì)量及其單元間中心距離確定邊界度,由邊界度和邊界閾值判斷每個網(wǎng)格單元是否為邊界單元或噪聲單元。通過從邊界單元中提取更靠邊緣的數(shù)據(jù)作為邊界點(diǎn)的方式,使得邊界更精細(xì)。實(shí)驗(yàn)結(jié)果表明,該算法能有效和快速識別出多密度數(shù)據(jù)集的聚類邊界和噪聲。

網(wǎng)格單元;k-近鄰集; 邊界度; 邊界點(diǎn); 噪聲

Class Number TP311

1 引言

邊界點(diǎn)是指位于不同密度數(shù)據(jù)區(qū)域邊緣的數(shù)據(jù)對象,邊界就是邊界點(diǎn)的集合[1]。邊界反映了數(shù)據(jù)的分布特征和結(jié)構(gòu)信息,同時也提供了一種有用的模式,如果數(shù)據(jù)分布的邊界確定了,那么就可以根據(jù)邊界對數(shù)據(jù)聚類或分類[2～4]。邊界識別研究有助于提高聚類的精度以及分類的準(zhǔn)確度。另外,邊界識別也是圖像處理和數(shù)據(jù)分析的有用手段[5～7]。

DBSCAN是基于密度的聚類算法[8],它定義了聚類的邊界點(diǎn),如果一個對象不是核心對象,且它對某個核心對象是直接密度可達(dá),則該對象為邊界點(diǎn)。由于識別的邊界點(diǎn)與全局參數(shù)密切相關(guān),不能有效識別多密度數(shù)據(jù)集的邊界點(diǎn),算法時間復(fù)雜度較高,為O(nlogn)(n是數(shù)據(jù)規(guī)模的大小)。BORDER算法[1]是基于密度的邊界點(diǎn)識別算法。若一個對象p在某個對象o的k-近鄰中,則稱對象o是對象p的反向k-近鄰。利用邊界點(diǎn)的反向k-近鄰個數(shù)一般小于處于聚類內(nèi)部對象的反向k-近鄰的個數(shù)思想來識別邊界點(diǎn)。數(shù)據(jù)集的所有對象按它的反向k-近鄰數(shù)從小到大排列順序,并把前w個對象作為邊界點(diǎn)。因?yàn)樵肼暫途垲悆?nèi)部的一些點(diǎn)的反向k-近鄰數(shù)可能少于邊界點(diǎn)的反向k-近鄰數(shù),所以該算法不能正確地從多密度和帶噪聲的數(shù)據(jù)集中提取聚類的邊界點(diǎn)。另外,參數(shù)w的多寡取舍比較困難。算法時間代價也較高為O(kn2)。BDKD算法[9]用基于密度的聚類思想,把數(shù)據(jù)對象的k-近鄰距離與其鄰域內(nèi)數(shù)據(jù)對象的平均k-近鄰距離之比定義其k-離群度,對k-離群度超過閾值的數(shù)據(jù)對象規(guī)定為邊界點(diǎn)。但時間復(fù)雜度為O(kn2)消耗不低。

BOURN算法[10]是根據(jù)數(shù)據(jù)分布的統(tǒng)計(jì)信息來識別邊界模式的算法,由數(shù)據(jù)分布的均值和方差定義數(shù)據(jù)對象的邊界度,按邊界度的大小對數(shù)據(jù)集降序排列,選取前w個邊界度最大的對象作為邊界點(diǎn)輸出。雖然該算法在含有噪聲的數(shù)據(jù)集上能有效地識別出邊界點(diǎn),但參數(shù)選擇較困難,算法的執(zhí)行效率不高,時間復(fù)雜度與DBSCAN相當(dāng)。在基于網(wǎng)格聚類的算法中,文獻(xiàn)[11～12]只考慮了識別低密網(wǎng)格聚類的邊界點(diǎn),并沒有給出提取所有聚類邊界點(diǎn)的策略。

BPGG算法[13]是基于網(wǎng)格的邊界識別算法。該算法的思路是:當(dāng)一個網(wǎng)格處在類的邊界區(qū)域時,其梯度會明顯大于那些處在類內(nèi)部的網(wǎng)格的梯度。算法首先通過卷積運(yùn)算定義網(wǎng)格梯度,運(yùn)用梯度算子,近似求出網(wǎng)格所對應(yīng)的每一個維的梯度值,然后從中選取絕對值最大的梯度值與給定閾值比較確定邊界網(wǎng)格,再把邊界網(wǎng)格中的對象標(biāo)記為邊界點(diǎn)。算法的不足是運(yùn)算較復(fù)雜,且把邊界網(wǎng)格中的數(shù)據(jù)點(diǎn)都作為邊界點(diǎn),得到的邊界較粗糙精度不高。文獻(xiàn)[14]提出了一種基于網(wǎng)格的邊界點(diǎn)識別算法,利用相鄰網(wǎng)格單元間的數(shù)據(jù)分布關(guān)系識別邊界單元和邊界點(diǎn)。但由于邊界識別過程中只分析了單元和相鄰單元小范圍內(nèi)的數(shù)據(jù)分布信息,因而結(jié)果受網(wǎng)格劃分方法和劃分?jǐn)?shù)量的影響較大。

為克服現(xiàn)有邊界識別算法難以有效地對帶噪聲的多密度和大數(shù)據(jù)集的聚類進(jìn)行邊界識別,絕對參數(shù)選擇困難以及精度和效率低的缺點(diǎn),減少基于網(wǎng)格的邊界識別算法中網(wǎng)格劃分方法對結(jié)果影響,提出一種網(wǎng)格k-近鄰集的邊界點(diǎn)識別算法(The boundary point recognition algorithm for Gridk-nearest neighbor set,BGN)。

2 相關(guān)概念

2.1 網(wǎng)格單元和k-近鄰集

S=A1×A2×…×Am是一個m維數(shù)據(jù)空間,其中Aj(j=1,2,…,m)是第j個屬性的有界定義域,X={x1,x2,…,xn}是包含n個數(shù)據(jù)點(diǎn)的m維空間中的數(shù)據(jù)集,數(shù)據(jù)點(diǎn)xi=(xi1,xi2,…,xim)(i=1,2,…,n),其中xij∈Aj,每個數(shù)據(jù)點(diǎn)的質(zhì)量規(guī)定為1,一個數(shù)據(jù)集的質(zhì)量就是這個數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)數(shù)。

定義2 給定近鄰距離k,若p和q是非空單元,p與q的幾何中心歐式距離rqp不超過k,除j維外其它各維p與q的劃分區(qū)間相同。

1) 當(dāng)p在j維的劃分區(qū)間的左端點(diǎn)大于或等于q在j維劃分區(qū)間的右端點(diǎn),則稱p是q的j維右鄰居,與q的幾何中心距離最短的j維右鄰居,稱為q的j維最近右鄰居。

2) 當(dāng)p在j維劃分區(qū)間的右端點(diǎn)小于或等于q在j維劃分區(qū)的左端點(diǎn),p與q在其它各維的劃分區(qū)間相同,則稱p是q的j維右鄰居,與q的幾何中心距離最短的j維左鄰居,稱為q的j維最近左鄰居。

從定義可知,若p是q的j維最近左鄰居,則q是p的j維最近右鄰居。一個非空單元在某維不一定有鄰居單元。

定義3 單元q的k-近鄰集k{q}是由單元q和它的各維左右鄰居組成。k{q}的質(zhì)量N(k{q})為它所含的各單元質(zhì)量的和。

圖1 k-近鄰集圖

并不是所有與單元q的幾何中心距離小于k的單元都是k{q}的元素,而只有那些沿維軸正負(fù)方向q的鄰居,才成為k{q}的元素,這樣規(guī)定能減少算法的復(fù)雜度。如圖1,取近鄰距離k為單元劃分區(qū)間長度的三倍,則k{q}={a,q,b,c,d,e,f},單元a,b,e是q單元的最近鄰居,N(k{q})=10。

2.2 邊界度與邊界單元

定義中|N(k{q})-N(k{p})|/N(k{q}∪k{p})為k{q}的質(zhì)量與k{p}的質(zhì)量差的絕對值比k{q}與k{p}并集的質(zhì)量,值越大表明k{q}與k{p}分布密度相對差越大。rqp/k越大表明p與q相距越遠(yuǎn)。邊界度的范圍為[0,1]。

顯然,如果p是q的j維最近左鄰居,q是j維右邊界單元,那么p是j維右邊界單元。如果p的j維無左(右)鄰居,則p是j維左(右)邊界單元。

噪聲單元實(shí)質(zhì)上是一種特殊的邊界單元,它對每一維的左右兩個方向而言都是邊界單元,或者說噪聲單元與它的任意一維的最近左或右鄰居都不是同類,因而噪聲單元又可看成是孤立單元。不是噪聲單元的邊界單元稱為非噪聲邊界單元。

3 BGN邊界點(diǎn)識別算法

3.1 邊界的細(xì)化

3.2 BGN邊界點(diǎn)識別算法步驟

BGN邊界點(diǎn)識別算法包括網(wǎng)格劃分、數(shù)據(jù)映射,確定k-近鄰集和邊界度,判斷邊界單元或噪聲單元,提取邊界點(diǎn)和噪聲等過程。具體步驟如下:

輸入 數(shù)據(jù)集X,每維網(wǎng)格劃分區(qū)間數(shù)t,近鄰距離k,邊界閾值h

輸出 邊界點(diǎn)和噪聲

步驟1 將數(shù)據(jù)空間S劃分為網(wǎng)格單元,確定網(wǎng)格單元的中心,并將數(shù)據(jù)集X映射到網(wǎng)格單元中,統(tǒng)計(jì)和計(jì)算非空網(wǎng)格單元的質(zhì)量和質(zhì)心。

步驟2 查找每個非空單元的k-近鄰集。

步驟3 計(jì)算每個非空單元的每一維的左右邊界度,根據(jù)定義5判斷單元是否是邊界單元。

步驟4 根據(jù)定義6從邊界單元中找出噪聲單元,提取噪聲數(shù)據(jù)。

步驟5 提取非噪聲邊界單元中的初邊界點(diǎn)。

步驟6 按邊界細(xì)化的方法提取非噪聲邊界單元中的細(xì)邊界點(diǎn)。

步驟7 輸出噪聲數(shù)據(jù)、初邊界點(diǎn)和細(xì)邊界點(diǎn),算法結(jié)束。

網(wǎng)格劃分一般可按平均每個網(wǎng)格單元的數(shù)據(jù)不少于一個來確定每維劃分?jǐn)?shù)。近鄰距離k一般取單元劃分區(qū)間長度的倍數(shù)。邊界度是一種相對數(shù),比采用絕對數(shù)來說,更容易確定邊界閾值h,一般取為0

3.3 算法復(fù)雜度分析

m維數(shù)據(jù)空間中有n個數(shù)據(jù),劃分網(wǎng)格并將數(shù)據(jù)投影到網(wǎng)格中,掃描網(wǎng)格空間一次,統(tǒng)計(jì)單元的數(shù)據(jù)數(shù)量,時間復(fù)雜度為O(2n)。一個k-近鄰集最多只有2km個元素,計(jì)算非空單元d(d≤n)的邊界度,時間復(fù)雜度為O(2kmd),對邊界單元進(jìn)行細(xì)化處理,其時間復(fù)雜度為O(md),所以BGN整個算法的時間復(fù)雜度為O(2n+(2k+1)md),算法的時間復(fù)雜度與數(shù)據(jù)規(guī)模呈線性關(guān)系。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 算法性能實(shí)驗(yàn)

比較BGN與BORDER的時間效率。九個數(shù)據(jù)集分布為正六形。BGN邊界閾值h=0.32。BORDER實(shí)驗(yàn)參數(shù)為近鄰居數(shù)10,在相同數(shù)據(jù)規(guī)模情況下,取BORDER邊界點(diǎn)數(shù)量與BGN算法識別的初邊界點(diǎn)數(shù)相同。

不同數(shù)據(jù)規(guī)模的數(shù)據(jù)集的分布結(jié)構(gòu)不一樣,因而識別的邊界點(diǎn)數(shù)也不相同。從表1可見,數(shù)據(jù)量遞增時GAB算法的時間復(fù)雜度呈線性增長,執(zhí)行時間遠(yuǎn)遠(yuǎn)低于BORDER,具有良好的數(shù)據(jù)規(guī)?？蓴U(kuò)展性。

表1 BORDER與BGN數(shù)據(jù)規(guī)模執(zhí)行時間比較

4.2 算法有效性對比實(shí)驗(yàn)

試驗(yàn)1 二維數(shù)據(jù)集呈葉形分布(圖2(a)),共16666個數(shù)據(jù)。BGN每維網(wǎng)格劃分區(qū)間數(shù)為t=129,共劃分成8281單元,邊界閾值0.23。BGN識別出邊界單元838個,共有1066個初邊界點(diǎn)(圖2(c)),經(jīng)過細(xì)化后邊界點(diǎn)精減為745個(圖2(d)),邊界更精致平滑,如葉柄部分邊界更清楚。識別出分布于葉邊緣的10個噪聲點(diǎn)。BORDER參數(shù)為近鄰個數(shù)12,邊界點(diǎn)數(shù)為900。從圖2(b)中可見,BORDER算法的效果沒有BGN好,表現(xiàn)在葉形外圍邊界完整性差,丟失了較多的外圍邊界點(diǎn),因?yàn)槿~內(nèi)部的一些點(diǎn)的反向k-近鄰個數(shù)比聚類邊界點(diǎn)的反向k-近鄰個數(shù)還少,所以葉內(nèi)部的這些點(diǎn)也被當(dāng)作邊界點(diǎn)。

圖2 葉型邊界識別比較

試驗(yàn)2 二維多密度數(shù)據(jù)集包含13885個數(shù)據(jù),分布形成“花”型(圖3(a))。構(gòu)成花(數(shù)據(jù)量13728個)的花瓣、花蕊、葉及枝等部分密度不同,形狀各異。分布在花周圍有157個隨機(jī)離散點(diǎn)。

BORDER參數(shù)為近鄰個數(shù)30,邊界點(diǎn)2200個。BGN每維網(wǎng)格劃分區(qū)間數(shù)為t=117,邊界閾值0.16。BGN識別出邊界單元1778個,共有3028個初邊界點(diǎn)(圖3(c)),經(jīng)過細(xì)化后邊界點(diǎn)精減為1935個(圖3(d))。識別出噪聲數(shù)據(jù)150個(圖3(e))。從圖3可見,BORDER識別出構(gòu)成“花”的花瓣、花蕊、葉及枝等部分外圍邊界完整性較差,沒能把噪聲點(diǎn)與邊界點(diǎn)相區(qū)分。BGN能較完整地識別出構(gòu)成“花”的各部分邊界和分布在“花”周圍的小聚類邊界,有效地去除了噪聲。經(jīng)細(xì)化后的邊界更清晰簡潔。這說明BGN算法邊界點(diǎn)的識別效果比BORDER好。

圖3 花型數(shù)據(jù)集邊界識別效果比較

5 結(jié)語

在充分考慮了局部區(qū)域數(shù)據(jù)分布相對差異能反映不同密度數(shù)據(jù)集邊界分布特征的基礎(chǔ)上,給出了相應(yīng)邊界點(diǎn)識別算法BGN。利用相對參數(shù)來降低參數(shù)選擇的難度。通過按維分析單元k-近鄰集和該單元的左右最近鄰單元的k-近鄰集數(shù)據(jù)分布關(guān)系來識別邊界單元方法,較好地克服網(wǎng)格劃分對邊界單元識別的影響。理論分析和實(shí)驗(yàn)顯示,BGN算法能識別出分布呈任意形狀的多密度數(shù)據(jù)集的聚類邊界點(diǎn)和噪聲,輸入?yún)?shù)少,與數(shù)據(jù)輸入順序和單元順序無關(guān),具有較高的邊界檢測精度和執(zhí)行效率。

[1] Xia C, Hsu W, Lee M L, et al. BORDER: efficient computation of boundary points[J]. Knowledge and Data Engineering, IEEE Transactions on,2006,18(3):289-303.

[2] 張選平,祝興昌,馬琮.一種基于邊界識別的聚類算法[J].西安交通大學(xué)學(xué)報(bào),2007,41(12):1387-1390.

[3] 邱保志,琚長濤.具有聚類功能的邊界檢測技術(shù)的研究[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(20):133-137.

[4] 樓曉俊,孫雨軒,劉海濤.聚類邊界過采樣不平衡數(shù)據(jù)分類方法[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版),2013,47(6):944-949.

[5] 李燦燦,王寶,王靜,等.基于K-means聚類的植物葉片圖像葉脈提取[J].農(nóng)業(yè)工程學(xué)報(bào),2012,28(17):157-161.

[6] 安萌,姜志國,趙丹培.邊界片段模板方法在空間探測識別中的應(yīng)用[J].宇航學(xué)報(bào),2009,30(3):1231-1236.

[7] 邱磊,楊承志,何佃偉.一種新的基于網(wǎng)格聚類的雷達(dá)信號預(yù)分選算法[J].現(xiàn)代防御技術(shù),2013,41(2):167-172.

[8] Ester M, Kriegel H P, Sander J. A density-based algorithm for discovering clusters in large spatial databases with nosise[C]//Proceedigs of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland, Oregon:[s.n.],1996:226-231.

[9] 王桂芝,李井竹,狄志超.支持k-離群度的邊界點(diǎn)檢測方法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(33):140-142.

[10] 邱保志,張楓,岳峰.基于統(tǒng)計(jì)信息的聚類邊界模式檢測算法[J].計(jì)算機(jī)工程,2008,34(3):91-93.

[11] 高亞魯,宋余慶,朱玉全.改進(jìn)的CLIQUE優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(16):3801-3804.

[12] 張鴻雁,劉希玉,付萍.一種網(wǎng)格聚類的邊緣檢測算法[J].控制與決策,2011,26(12):1846-1850.

[13] 邱保志,余田.基于網(wǎng)格梯度的邊界點(diǎn)檢測算法的研究[J].微電子學(xué)與計(jì)算機(jī),2008,25(3):77-80.

[14] Li G, Li B. Boundary Point Recognition Algorithm Based on Grid Adjacency Relation[M]//Recent Advances in Computer Science and Information Engineering. Heidelberg,2012:Springer:211-218.

Boundary Point Recognition Algorithm for Gridk-nearest Neighbor Set

Li Guangxing

(Department of Fundamental Courses, Chengdu Vocational College of Agricultural Science and Technology, Chengdu 611130)

In order to efficiently identify the cluster boundary, based on the existence of density differences in the surrounding area of the boundary, a boundary point recognition algorithm for Gridk-nearest neighbor set(BGN) is proposed. In the grid space, based on the number of elements of grid cell and its nearest neighbor’sk-neighbor set, along with the cell-center distance of the unit grids, the boundary degree is determined by this algorithm. According to boundary degree and boundary threshold, this algorithm determines if each unit grid is boundary unit or noise unit. By extracting the data closer to the edge of the boundary to represent as boundary points, this algorithm is capable to make finer boundary. The experimental results indicate that the algorithm can effectively and quickly identify the cluster boundaries and noise for multi-density datasets.

grid cell,k-nearest neighbor set, boundary degree, boundary point, noise

2015年1月13日,

2015年2月27日 作者簡介:李光興,男,副教授,研究方向:人工智能與計(jì)算數(shù)學(xué)。

TP311

10.3969/j.issn1672-9730.2015.07.035