基于網(wǎng)格聚類中邊界點的處理

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

0 引言

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

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

1 相關工作

1.1 邊界點的定義

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

Chen Xia等提出了聚類邊界點檢測算法BORDER[1]，其邊界點的定義如下：

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

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

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

1.2 邊界點的處理方法

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

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

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

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

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

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

2 本文提出的邊界處理技術

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

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

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

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

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

邊界點的處理

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

3 結束語

基于網(wǎng)絡聚類算法中，效率與精度總是一對矛盾。對孤立點，在聚類過程中應該將其丟棄，如果一個低密度單元的相鄰的網(wǎng)格單元中存在高密度單元，那么該單元中的點可能是簇的邊界點，也可能是噪聲點，為此，可利用邊界處理技術作進一點的處理。本文提出一種應用密度的思想對邊界點進行處理技術，可一定程度上提高基于網(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)格熵的邊界點檢測算法[J].成都：計算機應用.2008，28(3):732-734.