障礙空間中基于網格的不確定數據聚類算法*

崔美玉，萬 靜，何云斌，李 松

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

1 引言

近年來，數據挖掘[1]技術受到越來越多人的關注，聚類[2]分析也成為了最近幾年研究的熱點。聚類分析是一種分析數據間關系的無監督方法，是數據挖掘的預處理步驟，它將數據最終劃分成多個聚簇，使每個聚簇內的數據對象之間的相似性較高，而簇與簇之間的相似性較低。聚類分析應用在很多領域，例如圖像模式識別、傳感器網絡[3]等。

聚類分析算法主要有基于劃分的（如K-means、UK-means[4]）、基于密度的（如DBSCAN（density-based spatial clustering of applications with noise）[5]、FDBSCAN（fast density-based spatial clustering of applications with noise）[6]）、基于層次的（如 HDCA（hierarchy distance computing based clustering algorithm）[7]）和基于網格的（如IGrid[8]）等。文獻[9]提出了核聚類算法，通過對樣本特征的優化，使得算法收斂速度加快，性能得到了較大的改進。文獻[10]提出了一種基于原型的凝聚層次聚類U-AHC（uncertain-agglomerative hierachical clustering）算法，采用了信息論和期望距離來比較不確定數據對象。文獻[11]提出了PDBSCAN（paralell density-based spatial clustering of applications with noise）算法，通過定義分層密度、模糊核心距離和模糊可達距離來解決自適應閾值的問題。

由于現實生活中，存在一些地理條件的限制（如湖泊、建筑、車輛等），因此在進行相似性度量時，需要考慮障礙的存在，以上算法并沒有考慮到障礙的存在。文獻[12]提出的帶障礙約束的聚類算法實用價值更高。

由于在采集時數據會受到周圍環境的影響，因此數據具有不確定性[13]，不確定數據的聚類[14-16]研究也成為了熱點?，F實生活中的障礙物也不可能一直靜止不變，空間障礙物可能會發生動態改變，如建筑物的拆遷、樓盤的新建或者車輛的移動等，這些障礙物的改變可能使得原有聚類結果發生改變，因此靜態障礙空間和動態障礙空間下的不確定數據聚類的研究有著重大的意義。

現有的數據聚類研究成果大多都是針對確定數據的聚類問題，因此本文解決的是障礙空間中的不確定數據聚類問題，利用網格對數據進行劃分。根據障礙集合是否變化提出了靜態障礙環境下的不確定數據聚類算法和動態障礙環境下的不確定數據聚類算法，其中動態障礙環境分為障礙動態增加、障礙動態減少、障礙動態移動三種情況。

2 定義與性質

不確定數據點集用X={X1,X2,…,Xn}表示，其中pi為概率值；網格空間由S={S1,S2,…,Sm}組成；障礙集用O={O1,O2,…,Om}表示。文獻[17]對數據空間進行了均勻網格劃分；文獻[18]給出了聚簇代表點質心Ci的定義；文獻[19]給出了數據點之間可視性的定義?；谝陨隙x，本文進一步給出如下定義。

定義1（KL距離[18]）KL距離衡量的是空間里的兩個概率分布的差異情況，KL距離函數表達式為：

在連續的定義域D中，不確定數據用概率密度函數(probability density function，PDF)表示，連續域下的KL距離表達式為：

在離散的定義域D中，不確定數據用概率質量函數（probability mass function，PMF）表示，離散域下的KL距離表達式為：

定義2（聚類半徑R[18]）聚簇網格內所有不確定數據點與代表點Ci的KL距離的均值，即為不確定聚類半徑，聚類半徑R表達式為：

定義3（密度閾值ε）

其中，n表示不確定數據總數，m表示單元網格總數。假定單元網格內不確定數據點的數目大于ε時為稠密網格；單元網格內不確定數據點的數目小于ε時為稀疏網格。

定義4（不確定數據點之間的障礙距離）給定障礙集O，數據點Xi和Ci,Xi和Ci之間互為可視時，表示為D(Xi||Ci)。當Xi和Ci之間不可視時，表示為dist(Xi,Ci),兩個數據點之間的障礙距離是繞過障礙的路徑最小距離，障礙距離如圖1所示。

Fig.1 Example of definition 4圖1 定義4的示例

3 算法描述

由于現實生活中障礙物的位置、數量可能會發生變化，因此根據障礙集合是否發生變化分別解決靜態障礙和動態障礙空間下的不確定數據聚類問題。

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

本節研究的靜態障礙物環境指的是空間障礙物的位置、點集和邊集都不會發生改變。

規則1假定稠密網格內可視集合為P1，不可視集合為P2。若Count_P1≥ε,說明稠密網格內的數據在進行相似性度量時大多計算的是直接距離，障礙對數據可視性影響較小。若Count_P2≥ε并且Count_P1＜ε,說明稠密網格內的數據在進行相似性度量時計算的是障礙距離，網格內的障礙對數據可視性影響較大，由于障礙距離必然大于可視時的直接距離，因此將此時的稠密網格加入到備選集T2中。

算法的主要步驟：首先根據文獻[17]，計算步長t，然后計算每個網格的密度ρ，假定可視集合為P1，不可視集合為P2，對集合P1中的不確定數據利用式（2）或者式（3），集合P2中的不確定數據利用式（6）計算；最后根據網格的鄰接特性，最終實現不確定數據的聚類，鄰接網格的示例如圖2所示。

Fig.2 Example of adjacency grid圖2 鄰接網格的示例

不確定數據點Xi所在網格的鄰接網格為A、B、C、D、E、F、G、H。

基于以上的分析和討論，進一步提出靜態障礙環境下基于網格的不確定數據聚類STA_GOBSCAN算法，如算法1所示。

算法1STA_GOBSCAN(X,O,Eps)

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

算法1解決了靜態障礙物情況下的不確定數據聚類問題，由于現實生活中的空間障礙物可能會發生動態改變，因此提出障礙物動態變化情況下的不確定數據聚類算法。

規則2首先定位新增障礙的位置，判斷新增障礙的加入是否改變了網格中不確定數據點之間的可視性，若沒有改變可視性則調用算法1；若新增障礙的加入，改變了不確定數據點之間的可視性，則只需重新判斷由可視的不確定數據點變為不可視集合中的不確定數據點的聚類結果是否改變。

假定障礙動態增加之前可視集合為P1，不可視集合為P2；對應的障礙物新增加之后的可視集合為P1′，不可視集合為P2′。

Fig.3 Example of dynamic increase of obstacles圖3 障礙物動態增加的示例

如圖3所示，不確定數據Xi所在的鄰接網格中，原始障礙集合為O={O1,O2,O3}，新增障礙O4和O5之后，Onew={O1,O2,O3,O4,O5}。障礙O4的動態加入，使得網格H中部分數據變得不可視，P1＞P1′并且P2＜P2′,因此障礙O4的動態加入對聚類結果產生了影響。障礙O5的動態加入，不確定數據點之間依然是互為可視的，P1=P1′并且P2=P2′。綜上分析，新增加的障礙可能對聚類結果產生影響，也可能對聚類結果沒有影響。規則2通過判斷新增障礙所在的局部網格空間中的不確定數據點來代替全體數據點的重新聚類，減少了大量的障礙距離的判斷，使得算法的效率提高。

基于以上分析，進一步提出障礙物動態增加情況下的不確定數據聚類DYN_GOCBSCAN算法，如算法2所示。

算法2DYN_GOCBSCAN(X,O,Oi)

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

由于空間障礙物的數量可能發生變化，空間障礙物的減少可能使得原始的聚類結果發生改變。如圖4所示，當障礙物減少時，障礙集標記為Onew，其中Oi為減少的障礙物。在障礙物動態減少之前，可視點集合為P1，不可視集合為P2。在障礙物動態減少之后，可視點集合標記為P1′，不可視點集合為P2′。

規則3首先定位動態減少的障礙物的位置，得到障礙物動態減少前的P1和P2，障礙物動態減少后的P1′和P2′。若動態減少的障礙物沒有改變網格中不確定數據的可視性，則調用算法1；若動態減少的障礙物改變了不確定數據的可視性，則只需重新判斷障礙減少時由不可視變成可視時集合中的不確定數據點的聚類。

如圖4所示，動態減少的障礙用虛線表示，假設原始障礙集合O={O1,O2,O3,O4,O5}，動態減少的障礙為O4和O2，Onew={O1,O3,O5}。障礙O2的動態減少，并沒有改變網格H中的數據間的可視性，P1=P1′并且P2=P2′，聚類結果沒有改變。障礙O4的動態減少，使得P1＜P1′并且P2＞P2′，因此聚類的結果發生改變，判斷障礙動態減少的位置是有必要的。

Fig.4 Example of dynamic reduction of obstacles圖4 障礙物動態減少的示例

算法的主要思想：障礙物的減少對不確定數據聚類的影響是局部的，規則3對障礙物動態減少前后的可視集合和不可視集合的變化進行分析，并對減少的障礙物不改變聚類結果的情況調用算法1。

基于以上分析，本節提出了障礙物動態減少時的不確定數據聚類算法DYN_GORBSCAN，如算法3所示。

算法 3DYN_GORBSCAN(X,O,Oi′)

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

本節中的障礙物移動指的是障礙物的大小、數量不發生改變，只是障礙物的位置發生改變。

規則4假設障礙物由位置A移動到位置B，在位置A時，障礙物標記為Oib，障礙物的變化情況相當于障礙物動態減少的情況，因此需要分析障礙物動態減少的情況；在位置B時，障礙物標記為Oia，相當于障礙物的動態增加，因此需要分析障礙物動態增加的情況。綜上分析，障礙物的移動可以分解成障礙物的動態減少和障礙物的動態增加兩部分。

如圖5所示，用帶箭頭的虛線表示障礙移動的前后位置變化情況，障礙物移動之前標記為Oib，障礙物移動之后標記為Oia。

Fig.5 Example of dynamic movement of obstacles圖5 障礙物移動的示例

根據障礙物動態移動的前后位置，可以分為以下4種情況：（1）在以網格質心Ci為中心，聚類半徑R為半徑的覆蓋圓內，障礙物Oi在覆蓋圓內移動，動態移動后的障礙集為Onew=O-Oib+Oia，如圖5障礙O4移動到O6的情況。（2）障礙物Oi由覆蓋圓內移動到覆蓋圓外，則Onew=O-Oib，如圖5障礙O4移動到O7的情況。（3）障礙物Oi由覆蓋圓外移動到覆蓋圓內，則Onew=O-Oib+Oia，如圖5障礙O8移動到O9的情況。（4）障礙物Oi在覆蓋圓外移動則Onew=O-Oib，如圖5障礙O8移動到O10的情況。

基于以上的分析，進一步給出障礙物動態移動情況下的不確定數據聚類DYN_GOMBSCAN算法，如算法4所示。

算法4DYN_GOMBSCAN(X,O,Oi)

3.5 障礙空間中的基于網格的不確定聚類算法

本節研究的G_OBSCAN算法主要整合了前四節的算法，使得最終的算法可以高效地解決靜態障礙空間和動態障礙空間中的不確定數據的聚類問題。

算法的主要思想：首先判斷障礙集合的變化情況，若滿足O=Onew，則表示障礙是靜止不變的，調用算法1；如果滿足O≠Onew，則表示障礙物是動態變化的，需進一步判斷是障礙的數量發生改變還是障礙的位置發生改變。若只是障礙的位置發生改變，則表示障礙物是移動狀態，需要調用算法4來解決，若是障礙的數量發生變化，則需要調用對應的算法2或者算法3來解決。

基于以上分析，給出障礙空間中基于網格的不確定聚類算法G_OBSCAN，如算法5所示。

算法5G_OBSCAN(X,O,Onew)

4 實驗比較與分析

由于現有的研究成果大多處理的是靜態障礙空間中的不確定數據聚類問題，而沒有研究障礙動態變化時的不確定數據聚類問題。為了驗證本文方法的有效性和準確性，根據障礙集合是否發生改變，對文獻[19]所提的OBS_UK_means算法進行處理。若障礙集合不發生任何改變，則不需要對OBS_UK_means算法進行任何處理，并與本文提出的STA_GOBSCAN方法進行實驗對比；若障礙集合發生了改變，可以分為以下障礙動態增加、障礙動態減少和障礙移動3種情況。

（1）障礙集O≠Onew，并且 Count_O＜Count_Onew時，表示障礙物動態增加，對障礙集為Onew時調用OBS_UK_means算法。

（2）障礙集O≠Onew，并且 Count_O＞Count_Onew時，表示障礙動態減少，對障礙集為Onew時空間中所有不確定數據點調用OBS_UK_means算法。

（3）障礙集O≠Onew，并且 Count_O=Count_Onew時，表示障礙物移動的情況。對移動后的障礙集合Onew重新調用OBS_UK_means算法來實現聚類。

本章主要通過實驗對本文所提出的算法進行性能分析與比較，實驗硬件環境為8 GB內存，Intel?CoreTMi5處理器，Windows 7操作系統，使用eclipse編譯環境，實驗使用標準的UCI實驗室中的數據集，實驗所需數據集的詳細情況如表1所示。

實驗主要對數據基數n、障礙數、CPU運行時間等幾方面進行對比。實驗采用Silhouette評測指標（S）作為聚類內部有效性評測，實驗采用F-measure熵作為聚類外部評測標準。

Table 1 UCI laboratory datasets表1 UCI實驗室數據集

圖6給出了不確定數據點規模的增加對CPU執行時間的影響。實驗的障礙物數量為100，由圖可知，隨著不確定數據點規模不斷增加，OBS_UK_means算法的CPU執行時間呈急劇上升趨勢，而算法STA_GOBSCAN的執行時間上升較緩慢并且執行時間始終少于OBS_UK_means算法。

表2的CPU執行時間為執行50次算法的平均時間，障礙數量初始值為100，當障礙數量增加到110時，OBS_UK_means算法的CPU執行時間大于DYN_GOCBSCAN算法，說明了DYN_GOCBSCAN算法優于OBS_UK_means算法。

Fig.6 Influence ofnon CPU execution time圖6 數據量n對CPU執行時間的影響

如表3所示，反映了障礙物動態減少時DYN_GORBSCAN算法與OBS_UK_means算法的CPU執行時間比較，其中障礙數量初始為100，當障礙數量較少到90時，表中算法的CPU執行時間都減少，因為障礙距離的計算比可視距離的計算更復雜，障礙的減少使得部分障礙距離變為直接距離，使得總的計算量減少，所以總的CPU執行時間也減少。由于規則3的提出，判斷了障礙減少的情況，障礙的局部處理代替了OBS_UK_means算法的全局重新聚類，因此DYN_GORBSCAN算法的CPU執行時間更少。

Table 2 Comparison of algorithms of obstacles dynamic increase表2 障礙動態增加時的算法比較

Table 3 Comparison of algorithms of obstacles dynamic reduction表3 障礙動態減少時的算法比較

表4展現的是當障礙物動態移動時DYN_GOMBSCAN算法與OBS_UK_means算法的CPU執行時間的比較。由于OBS_UK_means算法分別對障礙移動前和障礙移動后重新聚類，因此OBS_UK_means算法的CPU執行時間大于DYN_GOMBSCAN算法。

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

通過以上實驗分析可知，本文提出的算法均具有較高的效率和準確率。

5 結束語

根據國內外研究發現，傳統的聚類算法大多利用歐式距離進行相似性度量，本文主要利用網格對數據空間劃分并使用KL散度進行相似性度量。由于現實生活中的障礙可能是動態變化的，因此本文研究了靜態障礙空間中和動態障礙空間中的不確定數據聚類問題，通過判斷障礙集合的前后變化，提出了G_OBSCAN算法，理論研究和實驗分析表明，本文所提算法均具有較高的效率。

Table 4 Comparison of algorithms of obstacles dynamic movement表4 障礙動態移動時的算法比較

Table 5 Comparison of algorithm effectiveness表5 算法有效性的比較