障礙空間中基于Voronoi圖的不確定數據聚類算法

萬 靜 崔美玉 何云斌 李 松

(哈爾濱理工大學計算機科學與技術學院 哈爾濱 150080)

近年來，隨著人們對信息技術的不斷了解，數據的聚類[1]問題在許多應用中不斷出現，如基于傳感器網絡、基于位置的服務等領域.由于在數據采集過程中，受周圍環境的影響，或者是采集儀器精度的限制，因此數據具有不確定性.不確定數據[2-3]的分析與挖掘技術已成為最近幾年的研究熱點，不確定數據的聚類問題，就是如何將不確定數據集合劃分成若干個簇，使最終的結果簇內元組間相似性較大，簇與簇之間元組相似性較小.

現有的聚類算法大多解決的是確定數據的聚類問題，對于不確定數據的聚類算法研究中，主要的研究方法是對傳統的面向確定數據的聚類方法進行擴展，即在傳統的聚類算法[4-5]如基于劃分的聚類、基于密度的聚類、基于網格的聚類以及基于層次和模型的聚類方法等基礎上對不確定數據進行建模，使用合適的相似性度量方法，進而提出不確定數據聚類算法.

國內外學者研究了基于劃分的不確定聚類算法UK-means[6-7]，算法是用最小邊界矩形(minimum bounding rectangle, MBR)來表示數據的不確定性，MBR描述了數據點可能出現的區域位置，但UK-means算法只能發現球狀簇，并且易受參數k的影響.為了解決大多數聚類劃分算法發現簇形狀單一的缺陷，Hao等人提出采用基于密度[8]的聚類算法.Kriegel等人根據經典DBSCAN(density-based spatial clustering of applications with noise)算法提出了FDBSCAN(a fast DBSCAN algorithm)[9]算法,Han等人根據OPTICS(ordering points to identify the clustering structure)算法提出了FOPTICS[10]算法，FDBSCAN算法采用距離分布函數作為數據間相似性度量的標準，而FOPTICS算法在處理大型數據集方面更有效.文獻[11]提出了FDBSCAN算法的改進算法，多核M-FDBSCAN(multicore-FDBSCAN)方法是通過半聚類發生分裂和合并來構造最終的簇.基于密度的聚類算法大多需要依賴Eps和Minpts這2個參數，陸億紅等人[12]提出了OLUC(optimalk-nearest neighbors and local density-based clustering algorithm for uncertain data)算法，采用動態自適應的最近k近鄰結構，計算局部相對密度，降低了參數的選擇和密度等級的敏感性.由于網格結構能夠提高聚類速度，因此韓利釗等人[13]提出基于區域劃分的DBSCAN多密度聚類算法，利用網格相對密度差把數據空間劃分成密度不同的區域，使用網格與密度相結合的方法，提高了聚類效率.Kao 等人[14]利用Voronoi圖和R樹的性質，提出剪枝策略來減少期望距離的計算.以上算法僅考慮了確定元組間的距離，沒有考慮元組間的不確定因素和數據間的概率分布，因此采用KL距離作為數據對象間的相似性度量標準.

選址問題在物流、生產生活方面有著廣泛的應用，如工廠、垃圾處理中心、物流中心的選址等.隨著電商的發展，網上購物的人越來越多，物流發展迅速，物流中心選址的好壞直接影響到服務質量、服務的效率和成本，從而影響到利潤和市場競爭力，合適的選址會給人民生活帶來便利.由于現實生活中存在一些地理條件的限制(如江河、湖泊、建筑、車輛等)，使得聚類分析不可能都在理想的歐氏空間中進行，因此在進行相似性度量時，需要考慮障礙[15]的存在.然而現實生活中的障礙物不可能一直靜止不變，空間障礙物往往會發生動態改變，障礙物的改變可能使得原有聚類結果發生改變，因此研究靜態障礙空間和動態障礙空間中的不確定數據聚類問題有較大的意義.

近幾年來，帶有障礙的空間聚類問題受到越來越多國內外研究者的關注，曹科研等人[16]提出了一種障礙空間中的不確定數據聚類算法，分別基于R樹、最近距離區域和Voronoi圖的性質，設計了高效的剪枝策略，并較高程度地實現了不確定數據的聚類算法.文獻[17]提出的帶障礙約束空間聚類算法比遺傳K-Medoids[18]具有較高的收斂速度.在聚類分析時，考慮障礙的約束，實用價值更高.

在障礙空間中，現有的數據聚類研究成果大多都是針對確定數據的聚類問題.為了解決障礙空間中的不確定數據聚類問題，利用Voronoi圖對數據空間進行劃分.根據障礙集合是否發生變化，提出了靜態障礙環境下的不確定數據聚類算法和動態障礙環境下的不確定數據聚類算法，其中動態障礙物分3種情況處理，分別是障礙物動態增加時的不確定聚類算法DYNOC_VUBSCAN、障礙物動態減少時的不確定聚類算法DYNOR_VUBSCAN和障礙物動態移動情況下的不確定數據聚類算法DYNOM_VUBSCAN.理論研究和實驗表明：所提算法具有較高的準確性.

1 定義與性質

定義1.不確定數據點集[19].不確定數據集為X={X1,X2,…,Xn},Xi表示一個不確定數據點.Xi={(x1,p1),(x2,p2),…,(xd,pd)}，每個xi表示Xi的屬性值，d為維度數.為每一條數據的每一維屬性值生成[0,1]區間內的概率值pi，以元組的形式表示，元組由數據值和概率組成.

定義2.障礙集.一個障礙用一個多邊形表示，記為Oi，其中障礙的頂點集用V={v1,v2,…,vk}表示，障礙的邊集用E={e1,e2,…,ek}表示，記為Oi(V,E).障礙集用O={O1,O2,…,Om}表示.

定義3.Voronoi圖[20].給定一組生成點X={X1,X2,…,Xn}?R2，其中2

定義4.鄰接多邊形[21].共享相同邊的Voronoi多邊形稱為鄰接多邊形，它們的生成點被稱為鄰接生成點.Voronoi單元中存在幾條邊，則就會有幾個鄰接多邊形.如圖1所示，X11的Voronoi單元中有5條邊，對應的鄰接生成點為X1，X2，X10，X12，X13.X11的鄰接多邊形為以上5個鄰接生成點所在的Voronoi單元.

Fig. 1 An example of obstacle distance圖1 障礙距離的示例

根據Voronoi圖的結構和定義可以得出2個基本性質.

性質1.任意2個多邊形不存在公共區域[18].Voronoi圖將不確定數據對象集合中的數據按照其最近鄰特性將空間進行劃分，生成互不重疊的區域.

性質2.臨近特性[20].生成點Xi與鄰接多邊形中的鄰接生成點距離最近.

定義5.Voronoi圖的k級鄰接生成點[20].給定一組生成點X={X1,X2,…,Xn}?R2.Xi的k級鄰接生成點定義如下：

1) 一級鄰接生成.AG1(Xi)={Xj|VX(Xi)和VX(Xj)有公共邊}.

2)k(k≥2)級鄰接生成點.AGk(Xi)={Xj|VX(X)和VX(Xj)有公共邊，X∈AGk-1(Xi)}.

定義6.覆蓋圓半徑Rc.半徑Rc的選取，需要考慮的是整個不確定數據空間，半徑Rc過小，覆蓋圓內包含的不確定數據點的個數就越少，相應的點的密度就越小，使聚類迭代次數增加.半徑Rc過大，容易將孤立點包含在覆蓋圓中，因此Rc的確定是重要的.

定義7.KL距離[22].KL距離也叫作相對熵，KL距離衡量的是相同事件空間里的2個概率分布的差異情況，KL距離函數表達式為

(1)

在定義域D中，將不確定對象作為一個服從一定概率分布的隨機變量.在連續的定義域中，不確定數據用概率密度函數(probability density function, PDF)[23]表示，概率密度函數用高斯核密度估計：

(2)

在離散的情況下，不確定數據用概率質量函數(probability mass function, pmf)表示.根據文獻[22]，KL距離表達式為

(3)

KL距離有2個基本性質：

性質3.非對稱性[22].KL距離從直觀上是個度量或距離函數，但它并不是一個真正的度量或者距離，因為它不具有對稱性，一般從分布P到分布Q的距離通常不一定等于分布Q到分布P的距離.即D(P‖Q)≠D(Q‖P).

性質4.非負性[22].KL距離值非負，即D(P‖Q)≥0.當且僅當2個分布相同時，D(P‖Q)=0.

定義8.聚類半徑R[22].聚簇網格內所有不確定數據點與代表點Ci的KL距離的均值，即為不確定聚類半徑，其中聚簇網格內所有不確定數據點集合為X={X1,X2,…,Xr}.聚類半徑R表達式為

(4)

其中，r表示聚簇內不確定數據點的總個數.

定義9.不確定數據點之間的可視性[16].給定障礙集O和數據點Xi和Xj，不確定數據點Xi和Xj是可視的當且僅當Xi和Xj之間的連線不會穿過障礙集O中任何障礙的內部，也不會與任何邊集相交.數據點Xi和Xj是不可視時，Xi和Xj之間的連線會穿過障礙集O的內部或有邊集相交.將存在障礙的Voronoi單元標記為阻塞Voronoi單元VX′.

定義10.不確定數據點之間的障礙距離[16].給定障礙集O和數據點Xi和Xj，當Xi與Xj之間互為可視時，Xi與Xj的障礙距離為KL距離，表示為D(Xi‖Xj).當Xi與Xj之間不可視時，Xi與Xj的障礙距離表示為dist(Xi,Xj)，數據點之間的障礙距離是繞過障礙的路徑最小距離.Xi與Xj之間的障礙距離:

dist(Xi,Xj)=min{D(Xi‖vi)+
D(vi‖Xj),D(Xi‖vj)+D(vj‖Xj)}.

(5)

圖1給出了不確定數據點之間的障礙距離，其中圖1中的虛線表示障礙距離，粗實線表示無障礙時的直接距離.

如圖1所示，根據式(5)障礙距離的計算，不確定數據點X15與X16之間的障礙距離為

dist(X15,X16)=min{D(X15‖v1)+D(v1‖X16),
D(X15‖v4)+D(v4‖X16)}.

定義11.不確定數據點的密度[24].空間中的任意一個不確定數據點Xi，1≤i≤n.以不確定數據點Xi為中心，Rc為半徑的覆蓋圓區域內的不確定數據生成點個數，稱為不確定數據點的密度，記作ρ(Xi).

定義12.核心對象.根據給定閾值ε，最大覆蓋圓半徑Rc，若不確定數據對象Xi的最大覆蓋圓中包含的不確定數據對象個數ρ≥ε時，則稱Xi為核心對象.

2 障礙空間中的不確定數據聚類

隨著數據規模越來越大，使用基于密度的聚類算法能發現任意形狀的聚簇，并且對孤立點數據不敏感.使用Voronoi圖將數據空間劃分成若干個空間單元，根據Voronoi圖的鄰接特性和所提出的規則對不確定數據進行聚類，使最終的聚類結果有較高的執行效率和準確性.

2.1 靜態障礙空間下不確定數據聚類算法

靜態障礙環境指的是空間障礙物集合不會發生改變，包括障礙的位置、障礙的點集和邊集都不發生變化.對此時的空間不確定數據實現聚類算法，并提出了STAO_VUBSCAN算法.

STAO_VUBSCAN算法的主要思想：在一定距離內，可根據Voronoi單元與其鄰接的Voronoi的級數大小，判定局部密度大小.找出核心對象，以不確定數據點Xi為中心，以Rc為半徑形成一個覆蓋圓，計算覆蓋圓內所含的不確定數據點的個數ρ.若ρ>ε，則說明不確定數據點的數量較多，表示Xi所在覆蓋圓內的局部密度越大.根據局部密度的中心進而判斷鄰接Voronoi單元的聚類情況，最終實現靜態障礙環境下的不確定數據聚類.

定理1.若不確定數據點Xi在Voronoi圖中的所有一級鄰接生成點都被當作孤立點，則此時的不確定數據點Xi也同樣的視為孤立點.

證明. 設Xj為Xi的所有一級鄰接生成點，1≤j≤6[20].若Xj為孤立點，說明所有Xj所在覆蓋圓的數據密度都較小，不能視為核心對象.則以Xi為中心，Rc為半徑的覆蓋圓內的數據密度也較小.由于Xj為孤立點被剪枝，此時所有Xj的中心Xi也必定被視為孤立點處理.

圖2中，不確定數據點X1為圓心的覆蓋圓中，覆蓋圓內的X1最大有2級生成點，所以在進行相似性度量時，只考慮2級生成點以內的不確定數據和障礙情況，2級以外的鄰接生成點和障礙物可先不作考慮，這會簡化KL距離的計算以及障礙的判斷.判斷每個核心對象所在的覆蓋圓內數據點聚類情況，使得聚類過程更加簡便有效.

Fig. 2 An example based on Theorem 1圖2 基于定理1的示例

算法STAO_VUBSCAN的主要步驟：首先選擇任一未劃分的不確定數據對象，根據不確定數據點密度大小，先對密度大的生成點設置為核心對象.將核心對象根據密度從大到小降序排序，存放在Hash表L中，L={X1,X2,…,Xt}，1≤i≤t.根據核心對象在Hash表中的順序來依次聚類，將判斷過的不確定數據從Hash表中刪除，直到Hash表為空為止.使用KL距離作為相似性度量標準，尋找所有可能被聚到此類的不確定數據點，并將這些數據點標記為一類，并根據定理1進行部分孤立點的處理.重復以上步驟，直到所有不確定數據對象劃分完畢.

基于以上討論，進一步提出靜態障礙環境下的不確定數據聚類算法STAO_VUBSCAN，如算法1所示.

算法1.STAO_VUBSCAN(X,O,ε,Rc).

輸入：不確定數據點集X、障礙集合O、覆蓋圓半徑Rc,ε,R；

輸出：障礙空間下的不確定數據聚類結果W.

① fori=1 tondo

②Calculate_den(Xi);

③ end for

④ ifρ≥ε

⑤L←Quick_Sort(Xi);*降序排序*

⑥ end if

⑦ for (i=1 tot)且L≠? do

⑧ ifXi與Xj可視

⑨Calculate_KL();*式(2)或式(3)*

⑩ ifD(Xi‖Xj)≤R

首先算法1在創建Voronoi時，構建所需的時間復雜度為O(nlgn).算法執行第1個for循環，遍歷不確定數據點所需的時間復雜度是O(n).由于n的個數是有限的，所以此步驟是可終止的.在對核心對象進行快速排序時所需的時間復雜度為(mlgm)，其中m表示的是核心對象的個數，m?n.算法執行第2個for循環所需的時間復雜度為O(t)，因為覆蓋圓內核心對象t的數量有限，所以此步驟也是可終止的.由以上算法的核心步驟的時間復雜度分析可知，算法總的時間復雜度為O(nlgn).算法1的計算代價主要受空間數據集的規模、計算無障礙情況下距離度量的計算量和存在障礙時的障礙距離計算量的影響.

2.2 靜態障礙空間中不確定數據精煉算法

算法1已經解決了靜態障礙空間中的不確定數據聚類問題.但是算法1只考慮覆蓋圓內不確定數據點密度，根據覆蓋圓內不確定數據點密度大小，定義核心對象，而沒有考慮到核心對象所在覆蓋圓內的障礙的多少.針對覆蓋圓內靜態障礙物的分布情況，進一步提出STAO_RVUBSCAN算法，算法利用Voronoi圖的鄰接特性和提出的規則，設計了高效的聚類方法.

規則1.如果最大覆蓋圓內不確定數據點密度較大，并且滿足ρ≥ε，但存在的障礙較多時，則對應的不可視集合S2中的不確定數據點就會較多，在進行相似性度量時，計算的是障礙距離.若dist(Xi,Xj)>R，則Xi所在覆蓋圓內的不確定數據點Xj不能加入到Xi所在的簇中.

只考慮核心對象的密度是不夠的，還需要考慮核心對象最大覆蓋圓內靜態障礙的密度，障礙密度越大，說明不可視集合S2內的不確定數據個數就越多，判斷集合S1中可視數據密度是否滿足ρ≥ε.如果滿足，執行過程跟算法1一致.否則，說明了核心對象周圍的障礙較多，不可視集合S2內的不確定個數較多.在進行相似性度量時計算的是障礙距離，因為每個障礙距離都大于沒有障礙時的可視距離，因此需要考慮核心對象是否被當作孤立點處理.

如圖3所示，以不確定數據點X1為圓心，Rc為半徑的最大覆蓋圓內不確定數據集合S為{X1,X2,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13}，此時不確定數據點密度較大.覆蓋圓內存在O1,O2,O3,O4，O5共5個障礙，障礙將不確定數據分為2個集合，分別為可視集合S1和不可視集合S2.根據分析得出，可視集合S1={X7,X8,X10,X13}，不可視集合S2={X2,X4,X5,X6,X9,X11,X12}.

Fig. 3 An example based on regulation 1圖3 基于規則1的示例

若S1中不確定數據密度遠小于ε，或者S2中不確定數據密度≥ε，說明覆蓋圓內不確定數據點Xi的周圍存在較多的障礙，此時Xi不能作為核心對象處理.連續域環境下，可視集合內的距離使用式(2).離散域環境下，可視集合內的距離公式使用式(3)，不可視集合內的障礙距離用式(5)度量.規則1的提出，減少了障礙距離的判斷，使得算法的效率較大程度地提高.

首先判斷核心對象所在覆蓋圓內障礙的情況，如果核心對象內的靜態障礙不影響聚類結果，則聚類結果跟算法1相同.如果核心對象所在覆蓋圓內障礙的密度較大，只需判斷不可視集合S2中數據的聚類情況.最后根據相似性度量標準，將覆蓋圓內的不確定數據劃分到合適的聚簇中.基于以上分析，進一步提出了靜態障礙環境下的不確定數據聚類精煉算法STAO_RVUBSCAN，如算法2所示.

算法2.STAO_RVUBSCAN(X,O,ε,Rc,L).

輸入：X,O,Rc,ε,R,L；

輸出：聚類結果W.

① for (i=1 tot)且L≠? do*規則1*

②S←Count_ρ(Xi);

③ ifCircle_R(Xi)?Oi*覆蓋圓中存在障礙時*

④S1←Visiable_X(Xi,Xj);*1≤j≤S*

⑤S2←NVisiable_X(Xi,Xj);

⑥ end if

⑦ ifCount_S1≥ε

⑧Calculate_KL();*式(2)或式(3)*

⑨ ifD(Xi‖Xj)≤R

⑩W←Xi,Xj;

算法2在創建Voronoi時，構建所需的時間復雜度為O(nlgn).算法執行只有一個for循環，所需的時間復雜度為O(t)，因為覆蓋圓內核心對象t的數量有限，所以此步驟也是可終止的.由以上時間復雜度分析可知，算法2總的時間復雜度為O(nlgn).

算法2的聚類效率優于算法1，由于規則1的提出，過濾了大量的不確定數據點的判斷，減少了大量的計算，也使得最終的聚類結果更準確.

2.3 動態障礙增加情況下不確定數據聚類算法

算法1和算法2研究的是靜態障礙物環境下的不確定數據聚類算法，但是現實生活中的空間障礙物往往會發生動態改變，如空間障礙物的位置發生改變，障礙物的點集和邊集發生改變，因此提出動態障礙情況下的不確定數據聚類算法.根據障礙物動態變化的不同情況，分別提出障礙物動態增加、障礙物動態減少和障礙物動態移動3種情況的不確定數據的聚類算法.

Fig. 4 An example of dynamic increase in obstacles圖4 障礙動態增加的示例

根據新增加的障礙物的位置分析，障礙物增加對聚類可能沒有影響，也可能有影響.

規則2.首先判斷新增加障礙的位置，然后計算障礙所在Voronoi圖中不確定數據點的最大覆蓋圓范圍.如果新增加的障礙對聚類結果無影響，覆蓋圓范圍內不影響聚類的結果，則聚類結果與算法2 的結果相同.若新增障礙對不確定結果有影響，覆蓋圓范圍內的新增障礙影響了Voronoi圖中不確定數據點的聚類，則對此覆蓋圓內的不確定數據點重新聚類.重新聚類可能引起其他類的聚類，因此根據Voronoi圖的鄰接特性，需將可視性改變的不確定數據點加入到離其最近的鄰接核心對象所在的聚簇中.

由以上分析可知，障礙物的增加對不確定數據聚類的影響是局部的，分情況判定處理會避免較多不必要的距離計算，因此提出規則2對動態增加的障礙進行具體分析，進一步提出了障礙物動態增加時的不確定數據聚類算法DYNOC_VUBSCAN，如算法3所示.

算法3.DYNOC_VUBSCAN(X,O,ε,Rc).

輸出：聚類結果W.

② fori=1 tondo

④Calculate_R(Xi);

⑦W←STAO_RVUBSCAN();*調用算法2*

⑩ ifdist(Xi,Xj)≤R

首先算法3在創建Voronoi時，構建所需的時間復雜度為O(nlgn).算法3只有一個for循環，遍歷不確定數據點所需的時間復雜度是O(n).n代表的是不確定數據的總數量，并且數量是有限的，所以算法是可終止的.當算法3滿足步驟⑥所需的條件時，調用算法2.算法2的時間復雜度已經分析得出是O(nlgn).由以上分析可知，算法3總的時間復雜度為O(nlgn).

2.4 動態障礙減少情況下不確定數據聚類算法

數據空間的障礙物可根據實際情況動態變化，當障礙物減少時也很有可能對原來的聚類結果產生影響.

規則3.當減少障礙物時，沒有改變最后的聚類結果，此情況的聚類結果跟靜態障礙環境下的不確定聚類算法結果相同，使用算法2完成聚類即可.當減少的障礙物能夠引發最終的聚類結果改變，則對減少的障礙所在的Voronoi單元的最大覆蓋圓內的不確定數據重新進行相似性度量計算.重新聚類可能引起其他類的聚類，因此根據Voronoi圖的鄰接特性，需將不可視變成可視時集合中的不確定數據點加入到離其最近的鄰接核心對象所在的聚簇中.

Fig. 5 An example of dynamic reduction in obstacles圖5 障礙動態減少的示例

根據減少的障礙物的具體位置，減少的障礙可能對聚類影響，也可能對聚類結果沒有影響，因此需要分析討論.算法的主要思想：首先得到新的障礙集合Onew，判斷減少的障礙物的位置.然后根據規則3分析減少的障礙對聚類是否有影響，最后得到障礙動態減少情況下的不確定數據聚類結果.

基于以上討論，具體地給出動態障礙減少情況下的不確定數據聚類算法DYNOR_VUBSCAN，如算法4所示.

算法4.DYNOR_VUBSCAN(X,O,ε,Rc).

輸出：聚類結果W.

② fori=1 tondo

④Calculate_R(Xi);

⑦q←Count_S′();

⑧ ifS′=?或q=0

⑨W←STAO_RVUBSCAN();*調用算法2*

⑩ else ifS′≠ ?

首先算法4在創建Voronoi時，構建所需的時間復雜度為O(nlgn).算法執行最外層的for循環，遍歷不確定數據點所需的時間復雜度是O(qn).n代表的是不確定數據的總數量，并且數量是有限的，q是障礙減少時，由不可視變成可視的數據點個數，數量也是有限的，所以算法是可終止的.當算法4滿足步驟⑧所需的條件時，調用算法2.算法2的時間復雜度已經分析得出是O(nlgn).由以上分析可知，算法4總的時間復雜度為O(nlgn).

由于算法根據障礙將數據劃分成可視集合與不可視集合，只需重新判斷障礙減少時，由不可視變成可視的不確定數據點聚類情況.此方法大大減少了計算量，使得局部的進行相似性度量比重新劃分聚類更有效.

2.5 障礙物動態移動情況下的不確定數據聚類

本節研究的是障礙物動態移動情況下的不確定數據聚類，其中障礙物的動態移動指的是障礙物的點集和邊集不發生改變，只是障礙物的位置發生改變.

規則4.障礙物的動態移動可以分解成障礙物動態減少和障礙物動態增加2部分，障礙物動態移動之前標記為Oi beg，障礙物移動之后標記為Oi end.假設障礙物由位置P動態移動到位置Q，在位置P時，相當于障礙物Oi beg動態減少，因此需要分析障礙物動態減少時，由不可視集合移動到可視集合中的不確定數據點的聚類情況.在位置Q時，相當于障礙物Oi end的動態增加，因此需要分析障礙物動態增加時，由可視集合移動到不可視集合的不確定數據點的聚類情況.

如圖6所示，虛線箭頭表示的是障礙物動態移動前后位置的變化情況，根據障礙物動態移動的前后位置，移動后的障礙可能對聚類結果有影響，也可能對聚類結果沒有影響，因此可以分為4種情況分析討論：

1) 障礙物Oi由覆蓋圓內部移動到覆蓋圓內部，如圖6障礙物O3移動到O2的情況.

2) 障礙物Oi在核心對象Xi所在的覆蓋圓內部移動到覆蓋圓外部，如圖6障礙物O3移動到O4的情況.

3) 障礙物Oi在核心對象Xi所在的覆蓋圓外部移動到覆蓋圓內部，如圖6障礙物O1移動到O3的情況.

4) 障礙物Oi在覆蓋圓外移動，如圖6障礙O1移動到O4的情況.

Fig. 6 An example of dynamic movement of obstacles圖6 障礙物動態移動的示例

由于覆蓋圓的圓心都為核心對象，因此不確定數據的分布是密集的.情況1中的障礙Oi在覆蓋圓內移動，動態移動后的障礙集為Onew=O-Oi beg+Oi end；情況2中的障礙Oi由覆蓋圓內移動到覆蓋圓外，表明障礙Oi end所在區域的不確定數據較稀疏，障礙移動后的位置不影響核心對象的聚類結果，因此Onew=O-Oi beg；情況3中的障礙Oi由覆蓋圓外移動到覆蓋圓內，表明障礙Oi end所在區域的不確定數據分布是密集的，障礙Oi end移動后的位置會影響核心對象的聚類結果，所以Onew=O-Oi beg+Oi end；情況4中的障礙Oi在覆蓋圓外移動，表明障礙Oi beg和障礙Oi end所在區域的不確定數據分布是稀疏的，障礙動態移動之后的位置不影響核心對象的聚類結果，因此Onew=O-Oi beg.

首先標記動態移動的障礙物在移動之前的位置和移動之后的位置，并判斷符合以上哪種情況，進而得到Onew.根據規則4，通過調用DYNOR_VUBSCAN算法和DYNOC_VUBSCAN算法，最終實現對動態障礙物移動時的不確定數據進行聚類.

基于以上的分析，給出障礙物動態移動情況下的不確定數據聚類DYNOM_VUBSCAN算法，如算法5所示.

算法5.DYNOM_VUBSCAN(X,O,Oi).

輸入：不確定數據集X、障礙集O、移動障礙Oi；

輸出：聚類結果W.

①Judge_O(Oi beg,Oi end);

② ifOi beg,Oi endinCircle_R()

③Onew←O-Oi beg+Oi end;

④W1←DYNOR_VUBSCAN();

⑤W2←DYNOC_VUBSCAN();

⑥W←W1∪W2;

⑦ end if

⑧ ifOi endinCircle_R()且Oi begnot in

Circle_R()

⑨Onew←O-Oi beg+Oi end;

⑩W←DYNOC_VUBSCAN();

Circle_R()

算法5主要通過調用算法2、算法3和算法4來實現，由于以上算法是可終止的，并且時間復雜度已經分析得出為O(nlgn)，進而得出算法5的時間復雜度為O(nlgn).

2.6 障礙空間下的不確定數據聚類算法

通過分析定義域的情況，分別根據離散區域或者連續域對不確定數據進行聚類，離散域下的不確定數據用概率質量函數表示，連續域下的不確定數據用概率密度函數表示.采用核密度估計[20]方法得出概率密度函數，該方法不需要輸入參數，它僅從數據本身對概率密度函數作出估計，并且可以估計任意形狀的密度函數.由于概率質量函數在進行相似性度量計算時，比使用概率密度函數更簡單，所以對數據域的情況分開處理是有意義的.對于障礙情況的判斷，可以根據障礙集合是否變化，判斷障礙物是靜態的還是動態變化的，最終提出總算法.

根據前面提出的靜態障礙物環境下和動態障礙物環境下的不確定數據聚類算法，本節提出RO_VUBSCAN算法，使得最終的算法可以高效地解決靜態障礙空間環境下的不確定聚類、動態障礙物增加、減少和移動情況下的不確定聚類問題.

首先判斷障礙集合是否變化，如果障礙集合不發生改變，說明解決的是靜態障礙環境下的不確定數據聚類問題，可調用算法2完成聚類.若障礙集合發生變化，可根據障礙數量變化判斷是障礙物動態增加、障礙物動態減少還是障礙物動態移動的，如果是障礙動態增加時，則調用算法3完成聚類.如果是障礙動態減少時，則調用算法4完成聚類.如果是障礙動態移動時，則調用算法5完成聚類.基于以上分析，進一步提出障礙空間下的不確定聚類算法RO_VUBSCAN，如算法6所示.

算法6.RO_VUBSCAN(X,O,ε,Rc).

輸入：不確定數據集X、障礙集O,ε,Rc；

輸出：障礙空間下的不確定數據聚類結果集W.

①Create_Vor(X);

②Add_O(O);

③ fori=1 tondo

④Calculate_den(Xi);*計算ρ(Xi)*

⑤Judge_O(O);

⑥ ifO=Onew

⑦W←STAO_RVUBSCAN();

⑧ else ifO≠Onew

⑨ ifCount_O

如果定義域是連續的，則不確定數據用概率密度函數表示，KL距離的計算使用式(2)，如果定義域是離散的，則不確定數據用概率質量函數表示，相似性度量計算使用式(3).在計算障礙距離時，則使用式(5)進行相似性度量.

算法6在創建Voronoi圖所需的時間復雜度為O(nlgn).算法執行for循環時，遍歷不確定數據點所需的時間復雜度是O(n).n代表的是不確定數據的總數量，并且數量是有限的，所以算法是可終止的.當算法滿足步驟⑥所需的條件時，調用算法2.算法2的時間復雜度已經分析得出是O(nlgn).當算法滿足步驟⑧所需的條件時，調用算法3、算法4或者算法5，以上算法的時間復雜度都為O(nlgn).由以上分析可得出，算法6總的時間復雜度為O(nlgn).

3 實驗比較與分析

本節主要通過實驗對所提出的算法進行性能分析與比較.根據已有的研究成果發現，在相似性度量方面，大多集中在幾何距離的度量上，沒有考慮數據間的概率分布.針對這些問題提出了STAO_RVUBSCAN，DYNOC_VUBSCAN，DYNOR_VUBSCAN，DYNOM_VUBSCAN等算法.由于現有的研究成果無法直接有效地處理動態障礙空間中的不確定數據的聚類問題，因此對文獻[16]中提出的OBS_UK_means算法中動態添加障礙和動態減少障礙，進而分別與所提算法DYNOC_VUBSCAN，DYNOR_VUBSCAN，DYNOM_VUBSCAN進行實驗比較與分析.

根據障礙情況，需要對OBS_UK_means算法做4種處理：

1) 障礙集O=Onew時，則與所提的靜態障礙物環境下的聚類情況相同，可利用OBS_UK_means算法與STAO_RVUBSCAN算法做實驗對比.

2) 障礙集O≠Onew，并且Count_O

3) 障礙集O≠Onew，并且Count_O>Count_Onew時，表示障礙動態減少，則對障礙集為Onew時的空間中所有不確定數據點重新聚類.將這種障礙動態減少時調用OBS_UK_means的算法與提出的DYNOR_ VUBSCA的方法做實驗對比.

4) 障礙集O≠Onew，并且Count_O=Count_Onew時，表示障礙物動態移動.對障礙集為Onew時的所有不確定數據點重新聚類，將這種障礙動態移動時調用OBS_UK_means的算法與提出的DYNOM_ VUBSCA的方法做實驗對比.

實驗環境：Windows7的64位操作系統，采用Java編程.實驗中計算機的硬件配置：8 GB內存，500 GB硬盤，處理器：Intel?CoreTMi3處理器(主頻為2.30 GHz).

實驗使用標準的UCI實驗室數據集[25]，詳細情況如表1所示：

Table 1 UCI Laboratory Datasets表1 UCI實驗室數據集

UCI實驗室數據集中的數據表示的是確定的數據，為便于實驗，在實驗過程中對實驗數據集進行了適當調整，生成不確定數據的過程具體有5個步驟：1)讀取原始數據集的屬性；2)遍歷數據集的每條數據的每個屬性；3)為每一條數據的每一維的屬性值隨機生成一個概率值，概率值在[0,1]范圍之內，最終表達的形式為：Xi={(x1,p1),(x2,p2),…,(xd,pd)}，其中每個xi表示Xi的屬性值，d為維度，Xi表示一個不確定數據點；4)得到每條數據概率屬性值；5)輸出不確定數據集.

實驗主要考慮6個方面因素：數據維度d、數據基數n、障礙物數量、障礙物分布、CPU運行時間、聚類質量.利用以上6方面作為衡量算法的指標.

常用的聚類有效性評測有內部評價法、外部評價法和相關性測試評價.它們能對聚類結果進行評價，得出聚類結果是否最優.實驗采用評測指標(silhouette)作為聚類內部有效性評測，實驗采用F-measure熵[26]作為聚類外部評測標準.

分別對各個算法進行50次獨立聚類實驗，統計每次實驗的結果，然后對每種算法求50次實驗結果的平均值，對比算法的實驗結果如表2所示.結果顯示，對于以上4組數據集，RO_VUBSCAN算法的F-measure指標平均值和S指標均值均高于OBS_UK_means算法和FOPTICS算法的評測指標.通過實驗可看出，RO_VUBSCAN算法表現出更好的聚類效果.

Table 2 Comparison of Effectiveness of Algorithms表2 算法評測有效性對比

圖7中OBS_UK_means，RO_VUBSCAN，FOPTICS這3個算法的CPU執行時間隨著維度d的增加而增加，其中RO_VUBSCAN算法的CPU執行時間上升趨勢較平緩.從實驗結果看出，使用KL距離相似性度量方法比其他的距離度量更高效.由于考慮障礙的存在，隨著維度的增加，OBS_UK_means算法需要考慮障礙的存在，因此CPU執行時間大于FOPTICS算法.

Fig. 7 The effect of dimension d for CPU execution time圖7 維度d對CPU執行時間的影響

如圖8所示，隨著維度d的不斷增加，算法的有效性的變化曲線也呈下降趨勢.通過實驗，得出在維度大于10之后的曲線，算法的有效性變化曲線下降明顯，但STAO_RVUBSCAN算法的有效性依然較高.由于DYNOR_VUBSCAN算法和DYNOR_VUBSCAN算法處理的是動態障礙的情況，因此有效性較靜態障礙空間下STAO_RVUBSCAN算法的有效性略低一些.

Fig. 8 The effect of dimension d on algorithmeffectiveness圖8 維度d對算法有效性的影響

圖9給出了3個算法的CPU執行時間隨著不確定數據樣本數變化的對比結果.隨著不確定數據樣本數的不斷增大，FOPTICS算法在數據量增大時，CPU的執行時間急劇上升.但在數據量較小的時刻，因為FOPTICS算法沒有障礙的約束，FOPTICS算法的CPU執行時間比RO_VUBSCAN算法的執行時間少.在相同不確定數據樣本數的情況下，RO_VUBSCAN的CPU執行時間一直小于OBS_UK_means算法，因此通過實驗得知RO_VUBSCAN算法更有效.

Fig. 9 The effect of sample number on CPUexecution time圖9 樣本數對CPU執行時間的影響

圖10給出了數據量從5 000增加到30 000的過程中，3個算法對應的CPU執行時間的變化情況.通過實驗得出，RO_VUBSCAN算法的CPU執行時間相對于OBS_UK_means，FOPTICS更少.因此得出算法RO_VUBSCAN算法更有效.

Fig. 10 The effect of data size on CPU execution time圖10 數據量對CPU執行時間的影響

如圖11所示，分析了數據量從5 000增加到30 000期間，隨著數據量的增加，3個聚類算法的有效性.通過實驗結果可看出，FOPTICS算法的曲線平穩，并且效率一直較高.相比于RO_VUBSCAN算法，由于障礙的存在，聚類的過程中，存在著一定的誤差，在數據量增加到20 000期間有效性比FOPTICS略低，隨著數據量的繼續增加，算法的有效性比FOPTICS高.相比于OBS_UK_means算法，RO_VUBSCAN算法更有效.

Fig. 11 The effect of data size on the effectivenessof algorithm圖11 數據量對算法有效性的影響

表3給出了障礙物動態減少時DYNOR_VUBSCAN算法與對比算法的CPU執行時間的比較情況.結果顯示，DYNOR_VUBSCAN算法的CPU執行時間均小于對比算法，當障礙物動態減少時，由于對比算法需要計算全部數據，因此CPU執行時間遠大于DYNOR_VUBSCAN算法.

Table 3 The Effect of the Dynamic Reduction of Obstacles on the Execution Time of CPU表3 障礙物動態減少對CPU執行時間的影響

表4給出了障礙物動態增加時DYNOC_VUBSCAN算法與對比算法的CPU執行時間的比較情況，在障礙物數量動態增加時，DYNOC_VUBSCAN算法的CPU執行時間變化不大，而對比算法的CPU執行時間變化則較大.結果表明:所提算法優于對比算法.

Table 4 The Effect of the Dynamic Increase of Obstacles on the Execution Time of CPU表4 障礙物動態增加對CPU執行時間的影響

表5給出了障礙物動態移動時DYNOM_VUBSCAN算法與對比算法的CPU執行時間的比較情況.結果顯示DYNOM_VUBSCAN算法的CPU執行時間遠小于對比算法的CPU執行時間.

Table 5 The Effect of the Dynamic Movement of Obstacles on the Execution Time of CPU表5 障礙物動態移動對CPU執行時間的影響

表6顯示了障礙物數量增加時STAO_RVUBSCAN算法與對比算法的CPU執行時間的比較情況，在障礙物數量不斷增加時，STAO_RVUBSCAN算法的CPU執行時間增加的趨勢較緩慢，而對比算法的CPU執行時間變化較大.

表7給出了障礙物分布不同時RO_VUBSCAN算法與對比算法的CPU執行時間比較情況，障礙物的分布是隨機的，結果顯示RO_VUBSCAN算法的CPU執行時間變化不大，并且執行時間均小于對比算法.

Table 6 The Effect of the Different Number of Obstacles on the Execution Time of CPU表6 不同數量的障礙物對CPU執行時間的影響

Table 7 The Effect of Different Location Distribution of Obstacles on the Execution Time of CPU表7 障礙物不同位置分布對CPU執行時間的影響

通過以上實驗分析可知，提出的靜態障礙物環境下的不確定數據聚類算法STAO_RVUBSCAN與動態障礙物環境下的DYNOC_VUBSCAN，DYNOR_VUBSCAN，DYNOM_VUBSCAN不確定聚類算法均具有較高的效率.

4 結束語

傳統的聚類算法大多是在歐氏空間進行，沒有考慮障礙的存在.由于現實生活中，不確定數據點之間可能存在障礙，因此本文根據障礙物集合是否發生變化，把障礙大致分成2種情況，分別對靜態障礙空間下和動態障礙空間下的不確定數據進行聚類分析.靜態障礙空間中，提出了STAO_VUBSCAN算法和精煉算法STAO_RVUBSCAN.精煉算法的提出，使得聚類結果更準確和高效.對于動態障礙，考慮了障礙物動態增加、障礙物動態減少和障礙物動態移動3種情況，分別對這3種情況進行分析，提出了DYNOC_VUBSCAN算法、DYNOR_VUBSCAN算法和DYNOM_VUBSCAN算法.理論研究和實驗分析驗證表明，提出的算法具有較高的性能.由于沒有對確定數據進行聚類分析，未來研究的重點主要是障礙物動態情況下的確定數據聚類問題.