存在物理約束下的基于密度的空間聚類算法
2009-01-01 00:00:00孫志偉
計算機應用研究 2009年3期
（ 天津科技大學 計算機科學與信息工程學院， 天津 300222）
摘 要：在現有的基于空間約束的空間聚類算法DBCluC和DBRS+等的研究和比較基礎上，提出了一種新的處理物理約束的基于密度的空間聚類算法——DBCluC+。該算法在DBCluC算法基礎上，采用網絡拓撲結構建模通達對象，并增加通達對象訪問點的寬度屬性，從而采用約束距離（constrained distance）代替簡單的歐幾里德距離或障礙距離(obstacle distance)作為相異度的度量標準。理論分析和實驗結果表明，DBCluC+算法不僅具有密度聚類算法的優點，而且聚類結果比傳統的處理通達約束的聚類算法更合理，也更加符合實際情況的需要。
關鍵詞：聚類； 約束距離； 網絡拓撲； 障礙距離; 無向圖
中圖分類號：TP301.6 文獻標志碼：A
文章編號：10013695(2009)03087303
Clustering spatial data in presence of physical constraints:
densitybased approach
SUN Zhiwei
(College of Computer Science Information Engineering， Tianjin University of Science Technology， Tianjin 300222， China)
Abstract:Based on learning the current spatial clustering algorithms in the presence of constrains， such as DBCluC， DBRS+ and so on， this paper proposed a new method of densitybased spatial clustering called DBCluC+ which could handle the spatial constrains in a new way. In DBCluC+， the algorithm used network topology to model the facilitator and added a attribute named width of access point， so it used the constraint distance to replace the Euclidean distance or obstacle distance in DBCluC to as the criterion of the dissimilarly. Both theory analysis and experimental results confirm that the experiments show that the new proposed approach not only has the advantages of densitybased clustering algorithms， but also takes advantage of the constraint distance to make the results more reasonable than traditional ways， and the model of algorithm is according to the need of application.
Key words：clustering; constraint distance; network topology; obstacle distance; indirect graph
空間聚類是空間數據挖掘中一個重要的研究領域，能夠發現空間數據庫中隱含的知識、空間關系或其他有意義的模式。在現實生活中，存在很多約束條件，包括障礙物約束和通達約束。其中障礙物約束包括山川、湖泊、河流，而通達約束包括高速公路、山川中的隧道以及河流上的橋梁。這些因素嚴重影響地理數據的聚類結果。目前有一些能夠處理障礙約束的算法，但是幾乎沒有合適的算法能夠較好地處理公路、河流等通達約束對象并滿足實際應用的需要。為了使得空間聚類算法能對現實情況更實用，本文提出了一種基于密度的空間聚類算法來更好地處理通達約束存在下的聚類問題。
1 相關工作
目前為止，比較典型的可以處理空間約束的聚類算法主要包括CODCLARANS[1]、DBCluC[2]、AutoClust[3]、DBRS+[4]，每種算法都有各自的優勢和不足。
對于最早的處理空間約束對象COD_CLARANS來說，由于算法采用全局所有障礙頂點的可視圖算法，算法效率很差。
DBCluC算法是在DBSCAN[5]算法基礎上的擴展。DBSCAN算法是第一個基于密度的聚類算法，給出了密度可達、直接密度可達、密度相連、聚類、噪聲等在非障礙存在情況下的密度聚類的定義，使用空間索引[6]的情況下具有近似線性的運算效率。DBCluC在DBSCAN基礎上加入了對物理約束的處理，給出了障礙物的定義和可見性，可見空間的定義是第一個既處理障礙因素又處理通達約束的方法。算法通過障礙線[5] 來決定可見性，障礙線在預處理中建立。為了達到對溝通因素的處理，要識別通達實體的點和邊，忽略溝通對象的長度[2]。
DBRS+在DBRS的基礎之上，提出了“Chop and Conquer”的方法來處理障礙對象。當溝通對象存在時，DBRS+中采用特殊定義的多邊形，并且在多邊形上定義一些點稱為訪問點。同時把訪問點區分為主要入口點、入口點和出口點。這些點位于多邊形上。但是，這種特殊定義的多邊形在處理點和點關系時比較復雜，而且在處理時需要首先區分一般入口點和主要入口點，實際算法中只處理了主要入口點。更重要的是，DBRS算法由于采用了隨機鄰域覆蓋的方法，可能造成相同數據集出現不同聚類結果的情況。其在處理通達對象時采用的特殊多邊形的處理在計算時較為復雜，而且在處理時也沒有考慮多邊形的寬度。
綜合考慮各算法的特點，本文在基于密度的聚類算法DBCluC基礎上改善了對通達對象的處理方法，提出了DBCluC+算法，使之能夠更好地處理空間聚類中的物理約束問題。
2 DBCluC+算法
分析公路、河流等通達約束對象，最關心的是經過通達對象的通達距離以及從通達對象外部進入通達對象的位置。河流、公路等通達對象形狀復雜，整個結構中其寬度的變化與長度相比可以忽略，而且河流、道路本身屬于一種網狀結構，采用其他的線或特殊的簡單多邊形都不能夠準確地反映這種對象本身，只能反映簡單的隧道、橋梁等簡單通達對象。因此在本文中不采用多邊形而采用網狀拓撲的結構來處理，網絡拓撲采用無向圖表示。下面在DBCluC算法基礎上給出擴展的定義和處理方法。
定義1 通達約束對象(facilitor，fac對象)。Fac對象上的入口或出口稱為訪問點，負責數據集內的對象經過通達對象擴展鄰域的一個對象，即只有通過訪問點才能進入和離開通達對象。
一個fac對象用網絡拓撲建模，采用無向圖表示拓撲結構，無向圖的頂點表示約束對象方向變化的位置，即表示節點；邊表示約束對象，即無向圖的頂點和邊表示約束對象的形狀，同時在模型中加入訪問點，因此，模型在無向圖基礎上表示為T={V，E，G，A}。 其中：V={v1，v2，v3，…，vk}表示F的頂點集；E={e1，e2，e3，…，ek}是連接頂點的線段集，G={g1，g2，…，gl}表示每個頂點所連接的邊，表示邊與頂點的關系。A={a1，a2，…，am}表示訪問點。
定義2 約束距離（constrained distance）。實際處理每個對象的訪問點時，由于每個數據集內的對象的鄰域是不同的，重新定義出點和入點。對于數據集內的對象來說，很難或沒有辦法定義誰是主要入口點定義之前首先定義點到通達對象的距離dist(p，fac)，表示為
dist(p，fac)=min(dist(p，aci)，dist(p，acj)+weight×dist(aci，acj))
其中：i，j∈1…n，i≠j，n是通達對象fac的訪問點的數量；weight是通達對象上距離相對于空間歐幾里德距離的比率，后面采用w表示。
入口點指在鄰域范圍內距離中心點p的距離等于dist(p，fac)的訪問點。
鄰域內存在通達對象時的約束距離使用distfac(p，q)表示，定義為
distfac(p，q)=
dist′(p，q) p，q在一連通區域內
minf（dist(p，fac)+w×dist(ace，acei)+dist(acei，q) 其他情況下
其中：dist′(p，q)表示在同一連通區域內的兩點之間的歐幾里德距離或障礙距離；ace表示入口點；acei表示每個出口點；dist(ace，acei)表示從訪問點ace到acei在通達路徑的距離；dist(acei，q)表示距q最近的出口點到點q的距離。
出口點是在鄰域外的所有在distfac(p，q)內可以到達的訪問點。
定義3 鄰域。點p的鄰域使用N′eps(p)表示，定義為N′eps(p)={q∈D｜distfac(p，q)＜eps}，并且鄰域的大小表示為｜N′eps(p)｜。
通過前面的定義可以看出，經過通達對象后，數據對象的鄰域發生了變化，由于參數eps的使用，數據點之間的距離的最大值是eps，那么經過通達對象可達的距離應該是eps-dist(p，fac)+w×dist(ace，acei)。由于通達對象的存在，點p的eps鄰域發生的變化，如圖1所示。
在圖1中使用折線（網絡拓撲）表示通達對象，可以看出，最左邊的圓是點p在不考慮通達對象時的鄰域；而由于考慮了通達對象，在每個出口點的位置又有新的鄰域。對應新的鄰域半徑為eps-dist(p，fac)+w×dist(ace，acei)（此處0＜w≤1），由此可見，通達對象極大地擴展了對象的鄰域空間。
那么緊接著就應該得到通達對象存在下的鄰域N′eps(p)，每個出口點都可能需要執行范圍查詢以得到鄰域內的數據。
當使用網狀拓撲表示通達對象時，在實際應用中，如果通達對象的寬度相對于鄰域半徑來說不能忽略，此時需要對每個訪問點設置寬度ACwidth，這樣，在得到新的鄰域時，需要進一步減去該寬度ACwidth。詳細處理過程在下面的getExpNeigh函數的功能流程中給出。
定義4 在物理約束存在情況下的密度可達。如果(a)p∈N′eps(q);(b)q∈N′eps(p)且｜N′eps(p)｜≥minPts，那么認為p、q是密度可達的，使用D(p，q)表示。
定義5 基于物理約束的聚類。給定數據點集D，C，D={d1，d2，d3，…，dn}，C={c1，c2，c3，…，cc}，CD是關于eps鄰域和minPts的非空子集，滿足下列條件：
a)最大性。對于任意的di，dj∈D；i≠j，若di∈C，并且是dj從di出發關于eps和minPts的密度可達，那么dj∈C。
b)連通性。對于任意的ci，cj∈C，ci和cj是關于eps和minPts的密度相連的。
對于任意的ci，cj∈C和cj是相互可見的。
那么C是基于eps和minPts的一個簇。
3 DBCluC+算法的實現
3.1 DBCluC+的流程
當完成對通達約束對象的建模后，DBCluC+開始從數據集中的任意一點開始進行聚類，算法與數據集的處理順序無關。算法中expandCluster()函數具有按照密度可達的條件擴展聚類的功能。與DBCluC算法不同的是，此處expandCluster需要考慮通達約束對象的存在，即表示兩點之間的聚類不是兩點之間直線的歐幾里德距離，而是約束距離distfac(p，q)。ExpandCluster()函數流程如下：
輸入：數據集D，點point，聚類標志clusterId，鄰域半徑eps，密度閾值minPts，障礙對象Os，通達約束對象Fs
輸出：true or 1
SEED=retrieveNeighbour(point，eps，Os，Fs);
if SEED.SIZE<=minPts then 點point是噪聲Noise;
return 1;
endif
改變SEED中的所有元素的聚類標志為clusterID;
從SEED中刪除point;
while SEED.SIZE>0 do
currentPoint=SEED.first();
childSEED= retrieveNeighbour(point，eps，Os，Fs);
if childSEED.SIZE >=minPts then
for each curPoint in childSEED do
if curPoint is UNClassified then
把該點加入SEED；
設置該點的聚類標志為clusterId
else if curPoint is noise then
設置該點的聚類標志為clusterId
end if
end for
end if
從SEED中刪除currentPoint
end while
return true
RetrieveNeighbour函數流程如下：
輸入：數據集D，點point，聚類標志clusterId，鄰域半徑eps，密度閾值minPts，障礙物Os，通達對象Fs
輸出：數據集D的一個子集
result=getDireNeigh(point，eps);
//得到通達對象存在而產生的擴展鄰域
result.add(getExpNeigh(point，eps，Fs));
for each pnt in Result do
if checkVisibility(pnt，point，Os) then
VGSeed.add(pnt);
result.delete(pnt);
end if
end for
GetExpNeight函數流程如下:
輸入：點point，eps，Fs
輸出：點的集合
/*得到點鄰域eps內所有通達對象的訪問點的集合，并得到距離鄰域邊界最近的直接可見的訪問點，設為入口點；width為入口點寬度*/
enterPnt＝getEnterPoint（point，eps，Fs，out width）;
//F對象寬度不能忽略時按照得到反映寬度的距離的兩個端點
accessVetricS＝getAccessVetric (enterPnt，Fs)
//得到與point在同一側的訪問點端點
accessVetric=getSameDirectionAccess(accessVetricS，point)
//獲得到同側穿越對象頂點的距離
accessPntDist=getDist(point，accessVetric);
//得到直接鄰域外的最大擴展鄰域半徑
enterPntDist=getMaxExpandEps(acessPntDist，eps，width);
//得到鄰域外部內enterPntDist可到達的所有訪問點，即出口點
exitPntS=getExitPoint(enterPnt，enterPntDist，Fs);
for int i=0 to exitPntS.count-1 do
//得到相應的擴展鄰域半徑
expandEps＝getExpandEps(exitPntS[i]，eps， enterPntDist)
//對每個出口點根據expandEps得到擴展鄰域內的對象
for i=0 to exitPnt.SIZE-1 do
result.add(getDireNeigh(exitPntS[i]，epsexpandEps ));
end for
end for
在函數expandCluster中，檢索鄰域對象的功能是由retrieveNeighbour函數來完成的。在retrieveNeighbour函數中，函數getDireNeighbour()表示在得到直接鄰域的對象集合。函數getExpNeigh()表示得到由于通達對象的存在而產生的擴展鄰域內的對象集合。RetrieveNeighbour函數中的checkVisibility()表示判斷兩點之間的可見性，即兩點之間的連線是否與表示障礙物的障礙線相交或表示障礙通達的圖的邊相交。在函數getExpNeigh中，為了加快檢索訪問點的效率，采用R樹對所有訪問點建立空間索引。
3.2 DBCluC+的復雜度分析
設數據集的大小為n，障礙物的數量為o，所有障礙物的頂點數量為v1，障礙多邊形約簡后障礙線的數量是vol；通達對象的數量為f，節點的數量為v2，邊的數量是e2，訪問點的數量是av2。
算法的復雜性分析主要包含以下幾個方面：a)測試多邊形的頂點類型，它的復雜度為O(v1)；b)將多邊形約簡為障礙線的時間復雜度為O(v1×log v1)；c)getDireNeigh在采用空間索引時的復雜度為O(log n)；d)checkVisibility的復雜度為O(vo1)；e)getExpNeigh()的復雜度為O(av2×(v2+av2))。其中a)b)與DBCluC一樣是預處理過程，因此在使用空間索引的情況下算法的復雜度為O(n×(log n+vo1+av2×(v2+av2)))。可以看出，算法的復雜度與數據集大小n為對數關系，即近似線性關系；而與障礙物的頂點數、通達對象的節點數為線性關系，與訪問點數量為平方關系，一般來說av2< 4 仿真實驗 為了驗證本文提出的DBCluC+ 算法在處理約束時的效果，本文設計了一個虛擬數據集（圖2）。其中兩個障礙物、兩個通達對象；障礙物由圖中的實多邊形表示，而通達對象是圖中的兩個線性拓撲結構，通達對象上的五個圓表示訪問點，訪問點的寬度默認為0。 4.1 聚類效果及說明 本文用DBCluC算法和DBCLuC+算法分別對圖2所示的樣本數據集進行聚類，在鄰域半徑eps=5，密度閾值minPts=15，并且通達對象的權值設為0.1的條件下得到如圖3所示的聚類結果（以不同的灰度來區分不同的類別）。 對比圖3的聚類結果可以看到，圖3(a)不考慮約束對象，則得到的聚類結果為7個，明顯不符合實際情況；對于(b)的DBCluC算法的聚類，考慮了障礙約束，因此左上和下面的障礙物將周圍的數據分成了多個聚類，共10個，如果忽略通達對象長度，則所有由通達對象相連的聚類合并，最終只有5個聚類；從（c）中可以看出，由于通達對象和通達對象上的訪問點的存在，由通達對象連接的數據形成了一個數據聚類，而沒有訪問點存在的數據即使在通達對象周圍，也不能與其他數據形成聚類，共7個。 4.2 算法比較 為了進一步說明DBCluC+算法與DBCluC算法的區別，改變算法中通達對象的權值。在圖2中，將兩個通達對象中位于下面的通達對象上的三個訪問點分別標為A、B和C，如圖4所示。當權值為0.1時，聚類結果為圖3(c)中的聚類結果；當權值為0.2和0.3時，則聚類結果分別為圖4(a)和(b)。其中當權值為0.2時，由于通達速度降低，訪問點A周圍的對象被獨立出來；當權值進一步增大時，訪問點B周圍的數據也進一步形成了一個新的聚類。可以看出算法不但考慮了通達對象的長度，而且考慮了通達對象的通達程度，即通達對象上傳輸時間比普通歐幾里德距離傳輸時間的比率，因此算法更有利于進一步的應用。 5 結束語 本文通過對目前存在的處理空間約束
