基于網格聚類中邊界點的處理

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

0 引言

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

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

1 相關工作

1.1 邊界點的定義

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

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

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

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

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

1.2 邊界點的處理方法

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

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

1.3 在網格中邊界點的處理

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

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

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

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

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

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

以邊界網格中的某點對象為圓心，Step/2為半徑的圓內包含點對象的數目達到值τ：則該點對象定義為該邊界單元的核心點。

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

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

邊界點的處理

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

3 結束語

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

［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］邱保志，劉洋.基于網格熵的邊界點檢測算法[J].成都：計算機應用.2008，28(3):732-734.