江先偉（福建船政交通職業(yè)學(xué)院 福建 福州 350007）

0 引言

基于網(wǎng)格的聚類方法是運(yùn)用網(wǎng)格技術(shù)，把對(duì)象空間量化為有限數(shù)目的網(wǎng)格單元，形成一個(gè)網(wǎng)格結(jié)構(gòu)，所有的聚類操作都在這個(gè)網(wǎng)格結(jié)構(gòu)上進(jìn)行。一個(gè)網(wǎng)格單元的鄰居是指與其有共同邊界的或有共同點(diǎn)的那些網(wǎng)格單元。一個(gè)網(wǎng)格單元包含對(duì)象的數(shù)目超過(guò)給定的密度閾值MinPts，則認(rèn)為它是高密度單元，否則視其為低密度單元。連接相鄰密集單元的最大區(qū)域就形成一個(gè)“簇”，在這個(gè)區(qū)域內(nèi)的所有對(duì)象屬于這個(gè)簇。對(duì)孤立點(diǎn)，在聚類過(guò)程中應(yīng)該將其丟棄，如果一個(gè)低密度單元的相鄰的網(wǎng)格單元中存在高密度單元，那么該單元中的點(diǎn)可能是簇的邊界點(diǎn)，也可能是噪聲點(diǎn)，為此，可利用邊界處理技術(shù)作進(jìn)一步處理。

聚類的邊界代表了一種潛在的模式，對(duì)數(shù)據(jù)挖掘有著重要的意義。但是目前涉及邊界的算法并不多，對(duì)其研究遠(yuǎn)遠(yuǎn)不夠。另一方面，邊界點(diǎn)處于某些簇的相鄰位置，許多聚類算法（如基于網(wǎng)格的方法）不能準(zhǔn)確地把這些邊界點(diǎn)劃分到對(duì)應(yīng)的簇中，從而降低了聚類結(jié)果的質(zhì)量。

1 相關(guān)工作

1.1 邊界點(diǎn)的定義

在DBSCAN算法中，第一次提出了邊界點(diǎn)的概念。算法是基于密度定義了簇的邊界點(diǎn)，即如果一個(gè)對(duì)象不是核心點(diǎn)（所謂核心點(diǎn)指的是某對(duì)象的ε-鄰域內(nèi)至少包含最小數(shù)目MinPts個(gè)對(duì)象），且它是從某個(gè)核心點(diǎn)直接密度可達(dá)的 （即該對(duì)象落入某核心點(diǎn)的ε-鄰域內(nèi)），則定義該對(duì)象為邊界點(diǎn)。

Chen Xia等提出了聚類邊界點(diǎn)檢測(cè)算法BORDER[1]，其邊界點(diǎn)的定義如下：

定義 邊界點(diǎn)（Boundary point）：一個(gè)邊界點(diǎn)p是指滿足下列兩個(gè)條件的數(shù)據(jù)對(duì)象：

①它位于一個(gè)高密的區(qū)域IR；②p的附近存在一個(gè)區(qū)域IR′，Density（IR）＞＞Density（IR′），或者 Density（IR′）＞＞Density（IR）。

聚類的邊界代表了一種潛在的模式，對(duì)數(shù)據(jù)挖掘有著重要的意義。但是目前涉及邊界的算法并不多，對(duì)其的研究遠(yuǎn)遠(yuǎn)不夠。另一方面，邊界點(diǎn)處于某些簇的相鄰位置，許多聚類算法（如基于網(wǎng)格的方法）不能準(zhǔn)確地把這些邊界點(diǎn)劃分到對(duì)應(yīng)的簇中，從而降低了聚類結(jié)果的質(zhì)量。

1.2 邊界點(diǎn)的處理方法

DBSCAN算法基于密度定義了聚類邊界點(diǎn)，即如果一個(gè)對(duì)象不是核心點(diǎn)，且它是從某個(gè)核心點(diǎn)直接密度可達(dá)的，則定義該對(duì)象為邊界點(diǎn)。提出聚類邊界提取的BORDER算法中，應(yīng)用反向k近鄰可以反映出潛在的數(shù)據(jù)分布特征，并可以利用它識(shí)別位于兩個(gè)或多個(gè)分布之間的邊界點(diǎn)。BORDER算法認(rèn)為邊界點(diǎn)的反向k近鄰個(gè)數(shù)低于聚類內(nèi)部點(diǎn)的反向k近鄰個(gè)數(shù)，如果一數(shù)據(jù)點(diǎn)的k近鄰個(gè)數(shù)低于某閾值則把其作為邊界點(diǎn)輸出。該算法的缺點(diǎn)是：①在含有噪聲的數(shù)據(jù)集中，因?yàn)樵肼朁c(diǎn)的反向k近鄰個(gè)數(shù)往往比聚類邊界點(diǎn)的反向k近鄰個(gè)數(shù)少，因此按照對(duì)象的反向k近鄰值從小到大順序排列整個(gè)數(shù)據(jù)集后，取出的前n個(gè)對(duì)象既包含孤立點(diǎn)又包含邊界點(diǎn)，因此該算法在含有噪聲的數(shù)據(jù)集上不能正確地識(shí)別邊界；②BORDER算法不能正確地提取變化密度、多密度聚類中的邊界，因?yàn)榈兔芏赛c(diǎn)的反向k近鄰值較小，而高密度點(diǎn)的反向k近鄰值較大。

文獻(xiàn)[2]提出了利用正負(fù)半鄰域關(guān)系來(lái)判斷聚類的點(diǎn)檢測(cè)算法，首先提出正負(fù)半鄰域的概念，進(jìn)而計(jì)算出數(shù)據(jù)點(diǎn)的邊界度，根據(jù)邊界度進(jìn)行邊界點(diǎn)的提取。它解決了DORDER算法不能將邊界與噪聲分離的問(wèn)題。

1.3 在網(wǎng)格中邊界點(diǎn)的處理

傳統(tǒng)基于網(wǎng)格的聚類算法只處理高密度單元，低密度單元中的點(diǎn)作為孤立單元被丟棄，一旦聚類的邊界落入低密度單元，就會(huì)降低聚類精度，可能造成小聚類的丟失。并且，算法只能發(fā)現(xiàn)邊界是水平或垂直的簇，而不能檢測(cè)到斜的邊界，在大多數(shù)情況下這是不符合實(shí)際的。如何有效地提取邊界點(diǎn)，是提高聚類結(jié)果的質(zhì)量的關(guān)鍵問(wèn)題之一。

邊界單元和核心單元形成聚類簇的主要輪廓，而邊界點(diǎn)充實(shí)該輪廓，有時(shí)聚類簇的邊界點(diǎn)可能落入聚類結(jié)果網(wǎng)格單元以外的網(wǎng)格單元中，這就需要將聚類的邊界點(diǎn)從這些單元中提取出來(lái)，劃分到對(duì)應(yīng)的簇中，以提高聚類的精度。邊界點(diǎn)提取有兩種方法：一種方法，是對(duì)與邊界單元相鄰而未聚類的網(wǎng)格單元進(jìn)一步細(xì)分，如在每一維上再二等分，則每個(gè)邊界單元被劃分為2d個(gè)子單元，如果在這些子單元中存在與邊界單元相連接的子單元，則子單元中的對(duì)象視為邊界點(diǎn)，提取到相應(yīng)的簇中；另一種方法，是基于這樣一個(gè)事實(shí)：簇中對(duì)象的密度高于簇外部的密度和邊界點(diǎn)的密度，聚類邊界的密度到聚類外部的密度有明顯的跳變，每次聚類都從未聚類中最高密度的網(wǎng)格單元開(kāi)始逐步向外擴(kuò)展，遇到邊界單元時(shí)進(jìn)行邊界處理。對(duì)于一個(gè)與邊界網(wǎng)格單元g1相連的非密集單元g2，在非密集單元g2中取一個(gè)與邊界單元g1最近的點(diǎn)x，使用KNN近鄰關(guān)系法，在x和單元g1內(nèi)的點(diǎn)中觀測(cè)x的密集程度，來(lái)判斷x是否作為邊界點(diǎn)提取。如果是則用同樣的方法對(duì)下一對(duì)象進(jìn)行處理，否則，x不能作為邊界點(diǎn)被提取。

文獻(xiàn)[3]出了基于網(wǎng)格的聚類的邊界處理技術(shù)，該技術(shù)利用限制性k近鄰和相對(duì)密度的概念識(shí)別網(wǎng)格聚類的邊界點(diǎn)，提高聚類的精度。

2 本文提出的邊界處理技術(shù)

受DBSCAN算法的啟發(fā)，本文提出的邊界處理方法是在網(wǎng)格結(jié)構(gòu)中引入邊界網(wǎng)格單元和孤立網(wǎng)格單元的概念，依據(jù)邊界網(wǎng)格單元中包含對(duì)象的數(shù)目，定義該邊界單元的核心點(diǎn)，并依據(jù)核心點(diǎn)的ε-鄰域內(nèi)所有對(duì)象都屬于同一個(gè)簇的原則提取與邊界單元相鄰的孤立網(wǎng)格單元中的對(duì)象。

本文定義的邊界網(wǎng)格單元：屬于某一簇的網(wǎng)格單元g，在它相鄰的網(wǎng)格單元中，存在與單元g屬于不同簇的單元或存在未聚類的單元，則將單元g定義為邊界網(wǎng)格單元，并稱單元g是其所屬簇的邊界網(wǎng)格單元。從與邊界網(wǎng)格單元相鄰的孤立網(wǎng)格單元中提取靠近的點(diǎn)對(duì)象，這種“靠近”的準(zhǔn)則是：待提取點(diǎn)對(duì)象位于邊界網(wǎng)格單元中某一核心點(diǎn)的Step/2-鄰域內(nèi)，則把該點(diǎn)對(duì)象作為邊界點(diǎn)提取到對(duì)應(yīng)的邊界網(wǎng)格單元中。

以邊界網(wǎng)格中的某點(diǎn)對(duì)象為圓心，Step/2為半徑的圓內(nèi)包含點(diǎn)對(duì)象的數(shù)目達(dá)到值τ：則該點(diǎn)對(duì)象定義為該邊界單元的核心點(diǎn)。

其中，n0為該邊界網(wǎng)格單元的密度值。值τ實(shí)際上就是該邊界網(wǎng)格單元密度平均值的1／DCT倍取整。

如圖所示，帶陰影的網(wǎng)格單元（標(biāo)號(hào)為1～6）屬于同一個(gè)簇，標(biāo)號(hào)為7～9的網(wǎng)格單元為孤立網(wǎng)格單元，其中點(diǎn)對(duì)象c是邊界網(wǎng)格單元（標(biāo)號(hào)為5）的核心點(diǎn)，而孤立網(wǎng)格單元（標(biāo)號(hào)為8）中的點(diǎn)對(duì)象o落在核心點(diǎn)c的Step/2-鄰域內(nèi)。則把點(diǎn)對(duì)象o作為邊界點(diǎn)提取到邊界網(wǎng)格單元5中。

邊界點(diǎn)的處理

對(duì)孤立網(wǎng)格單元中點(diǎn)對(duì)象的提取只須判斷其Step/2-鄰域內(nèi)是否存在邊界單元的核心點(diǎn)，如果存在，則把點(diǎn)對(duì)象o提取到該核心點(diǎn)所在的邊界網(wǎng)格單元中。當(dāng)提取點(diǎn)對(duì)象o后，如果點(diǎn)o的Step/2鄰域內(nèi)包含的點(diǎn)數(shù)超過(guò)值τ，則點(diǎn)o也成為邊界網(wǎng)格單元的核心點(diǎn)，這樣邊界點(diǎn)的提取可以逐步向外延伸。

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

基于網(wǎng)絡(luò)聚類算法中，效率與精度總是一對(duì)矛盾。對(duì)孤立點(diǎn)，在聚類過(guò)程中應(yīng)該將其丟棄，如果一個(gè)低密度單元的相鄰的網(wǎng)格單元中存在高密度單元，那么該單元中的點(diǎn)可能是簇的邊界點(diǎn)，也可能是噪聲點(diǎn)，為此，可利用邊界處理技術(shù)作進(jìn)一點(diǎn)的處理。本文提出一種應(yīng)用密度的思想對(duì)邊界點(diǎn)進(jìn)行處理技術(shù)，可一定程度上提高基于網(wǎng)格聚類的精度。

［1］ChenXia,wynne Hsu,Mong Li Lee et al.BORDER:Efficient computation of boundary points[J].IEEE transaction on knowledge and data engineering.2006,18(3):289-303.

［2］Qiu,B Z,Yue F,Shen J Y et al.A efficient boundary points detecting algorithm.Proceedings of Advances in Knowledge Discovery and Data Mining(PAKDD)[M].New York:ACM Press.2007,4426:761-768.

［3］邱保志，劉洋.基于網(wǎng)格熵的邊界點(diǎn)檢測(cè)算法[J].成都：計(jì)算機(jī)應(yīng)用.2008，28(3):732-734.