江先偉(福建船政交通職業(yè)學院 福建 福州 350007)
基于網(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ì)量。
在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ì)量。
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算法不能將邊界與噪聲分離的問題。
傳統(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)格聚類的邊界點,提高聚類的精度。
受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)格單元的核心點,這樣邊界點的提取可以逐步向外延伸。
基于網(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.