障礙空間中基于網(wǎng)格的不確定數(shù)據(jù)聚類算法*

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

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

1 引言

近年來，數(shù)據(jù)挖掘[1]技術(shù)受到越來越多人的關(guān)注，聚類[2]分析也成為了最近幾年研究的熱點(diǎn)。聚類分析是一種分析數(shù)據(jù)間關(guān)系的無監(jiān)督方法，是數(shù)據(jù)挖掘的預(yù)處理步驟，它將數(shù)據(jù)最終劃分成多個聚簇，使每個聚簇內(nèi)的數(shù)據(jù)對象之間的相似性較高，而簇與簇之間的相似性較低。聚類分析應(yīng)用在很多領(lǐng)域，例如圖像模式識別、傳感器網(wǎng)絡(luò)[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]）和基于網(wǎng)格的（如IGrid[8]）等。文獻(xiàn)[9]提出了核聚類算法，通過對樣本特征的優(yōu)化，使得算法收斂速度加快，性能得到了較大的改進(jìn)。文獻(xiàn)[10]提出了一種基于原型的凝聚層次聚類U-AHC（uncertain-agglomerative hierachical clustering）算法，采用了信息論和期望距離來比較不確定數(shù)據(jù)對象。文獻(xiàn)[11]提出了PDBSCAN（paralell density-based spatial clustering of applications with noise）算法，通過定義分層密度、模糊核心距離和模糊可達(dá)距離來解決自適應(yīng)閾值的問題。

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

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

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

2 定義與性質(zhì)

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

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

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

在離散的定義域D中，不確定數(shù)據(jù)用概率質(zhì)量函數(shù)（probability mass function，PMF）表示，離散域下的KL距離表達(dá)式為：

定義2（聚類半徑R[18]）聚簇網(wǎng)格內(nèi)所有不確定數(shù)據(jù)點(diǎn)與代表點(diǎn)Ci的KL距離的均值，即為不確定聚類半徑，聚類半徑R表達(dá)式為：

定義3（密度閾值ε）

其中，n表示不確定數(shù)據(jù)總數(shù)，m表示單元網(wǎng)格總數(shù)。假定單元網(wǎng)格內(nèi)不確定數(shù)據(jù)點(diǎn)的數(shù)目大于ε時為稠密網(wǎng)格；單元網(wǎng)格內(nèi)不確定數(shù)據(jù)點(diǎn)的數(shù)目小于ε時為稀疏網(wǎng)格。

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

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

3 算法描述

由于現(xiàn)實(shí)生活中障礙物的位置、數(shù)量可能會發(fā)生變化，因此根據(jù)障礙集合是否發(fā)生變化分別解決靜態(tài)障礙和動態(tài)障礙空間下的不確定數(shù)據(jù)聚類問題。

3.1 靜態(tài)障礙空間下不確定數(shù)據(jù)聚類算法

本節(jié)研究的靜態(tài)障礙物環(huán)境指的是空間障礙物的位置、點(diǎn)集和邊集都不會發(fā)生改變。

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

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

Fig.2 Example of adjacency grid圖2 鄰接網(wǎng)格的示例

不確定數(shù)據(jù)點(diǎn)Xi所在網(wǎng)格的鄰接網(wǎng)格為A、B、C、D、E、F、G、H。

基于以上的分析和討論，進(jìn)一步提出靜態(tài)障礙環(huán)境下基于網(wǎng)格的不確定數(shù)據(jù)聚類STA_GOBSCAN算法，如算法1所示。

算法1STA_GOBSCAN(X,O,Eps)

3.2 障礙物動態(tài)增加情況下的不確定數(shù)據(jù)聚類算法

算法1解決了靜態(tài)障礙物情況下的不確定數(shù)據(jù)聚類問題，由于現(xiàn)實(shí)生活中的空間障礙物可能會發(fā)生動態(tài)改變，因此提出障礙物動態(tài)變化情況下的不確定數(shù)據(jù)聚類算法。

規(guī)則2首先定位新增障礙的位置，判斷新增障礙的加入是否改變了網(wǎng)格中不確定數(shù)據(jù)點(diǎn)之間的可視性，若沒有改變可視性則調(diào)用算法1；若新增障礙的加入，改變了不確定數(shù)據(jù)點(diǎn)之間的可視性，則只需重新判斷由可視的不確定數(shù)據(jù)點(diǎn)變?yōu)椴豢梢暭现械牟淮_定數(shù)據(jù)點(diǎn)的聚類結(jié)果是否改變。

假定障礙動態(tài)增加之前可視集合為P1，不可視集合為P2；對應(yīng)的障礙物新增加之后的可視集合為P1′，不可視集合為P2′。

Fig.3 Example of dynamic increase of obstacles圖3 障礙物動態(tài)增加的示例

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

基于以上分析，進(jìn)一步提出障礙物動態(tài)增加情況下的不確定數(shù)據(jù)聚類DYN_GOCBSCAN算法，如算法2所示。

算法2DYN_GOCBSCAN(X,O,Oi)

3.3 障礙物動態(tài)減少情況下的不確定數(shù)據(jù)聚類算法

由于空間障礙物的數(shù)量可能發(fā)生變化，空間障礙物的減少可能使得原始的聚類結(jié)果發(fā)生改變。如圖4所示，當(dāng)障礙物減少時，障礙集標(biāo)記為Onew，其中Oi為減少的障礙物。在障礙物動態(tài)減少之前，可視點(diǎn)集合為P1，不可視集合為P2。在障礙物動態(tài)減少之后，可視點(diǎn)集合標(biāo)記為P1′，不可視點(diǎn)集合為P2′。

規(guī)則3首先定位動態(tài)減少的障礙物的位置，得到障礙物動態(tài)減少前的P1和P2，障礙物動態(tài)減少后的P1′和P2′。若動態(tài)減少的障礙物沒有改變網(wǎng)格中不確定數(shù)據(jù)的可視性，則調(diào)用算法1；若動態(tài)減少的障礙物改變了不確定數(shù)據(jù)的可視性，則只需重新判斷障礙減少時由不可視變成可視時集合中的不確定數(shù)據(jù)點(diǎn)的聚類。

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

Fig.4 Example of dynamic reduction of obstacles圖4 障礙物動態(tài)減少的示例

算法的主要思想：障礙物的減少對不確定數(shù)據(jù)聚類的影響是局部的，規(guī)則3對障礙物動態(tài)減少前后的可視集合和不可視集合的變化進(jìn)行分析，并對減少的障礙物不改變聚類結(jié)果的情況調(diào)用算法1。

基于以上分析，本節(jié)提出了障礙物動態(tài)減少時的不確定數(shù)據(jù)聚類算法DYN_GORBSCAN，如算法3所示。

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

3.4 障礙物移動情況下的不確定數(shù)據(jù)聚類

本節(jié)中的障礙物移動指的是障礙物的大小、數(shù)量不發(fā)生改變，只是障礙物的位置發(fā)生改變。

規(guī)則4假設(shè)障礙物由位置A移動到位置B，在位置A時，障礙物標(biāo)記為Oib，障礙物的變化情況相當(dāng)于障礙物動態(tài)減少的情況，因此需要分析障礙物動態(tài)減少的情況；在位置B時，障礙物標(biāo)記為Oia，相當(dāng)于障礙物的動態(tài)增加，因此需要分析障礙物動態(tài)增加的情況。綜上分析，障礙物的移動可以分解成障礙物的動態(tài)減少和障礙物的動態(tài)增加兩部分。

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

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

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

基于以上的分析，進(jìn)一步給出障礙物動態(tài)移動情況下的不確定數(shù)據(jù)聚類DYN_GOMBSCAN算法，如算法4所示。

算法4DYN_GOMBSCAN(X,O,Oi)

3.5 障礙空間中的基于網(wǎng)格的不確定聚類算法

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

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

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

算法5G_OBSCAN(X,O,Onew)

4 實(shí)驗(yàn)比較與分析

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

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

（2）障礙集O≠Onew，并且 Count_O＞Count_Onew時，表示障礙動態(tài)減少，對障礙集為Onew時空間中所有不確定數(shù)據(jù)點(diǎn)調(diào)用OBS_UK_means算法。

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

本章主要通過實(shí)驗(yàn)對本文所提出的算法進(jìn)行性能分析與比較，實(shí)驗(yàn)硬件環(huán)境為8 GB內(nèi)存，Intel?CoreTMi5處理器，Windows 7操作系統(tǒng)，使用eclipse編譯環(huán)境，實(shí)驗(yàn)使用標(biāo)準(zhǔn)的UCI實(shí)驗(yàn)室中的數(shù)據(jù)集，實(shí)驗(yàn)所需數(shù)據(jù)集的詳細(xì)情況如表1所示。

實(shí)驗(yàn)主要對數(shù)據(jù)基數(shù)n、障礙數(shù)、CPU運(yùn)行時間等幾方面進(jìn)行對比。實(shí)驗(yàn)采用Silhouette評測指標(biāo)（S）作為聚類內(nèi)部有效性評測，實(shí)驗(yàn)采用F-measure熵作為聚類外部評測標(biāo)準(zhǔn)。

Table 1 UCI laboratory datasets表1 UCI實(shí)驗(yàn)室數(shù)據(jù)集

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

表2的CPU執(zhí)行時間為執(zhí)行50次算法的平均時間，障礙數(shù)量初始值為100，當(dāng)障礙數(shù)量增加到110時，OBS_UK_means算法的CPU執(zhí)行時間大于DYN_GOCBSCAN算法，說明了DYN_GOCBSCAN算法優(yōu)于OBS_UK_means算法。

Fig.6 Influence ofnon CPU execution time圖6 數(shù)據(jù)量n對CPU執(zhí)行時間的影響

如表3所示，反映了障礙物動態(tài)減少時DYN_GORBSCAN算法與OBS_UK_means算法的CPU執(zhí)行時間比較，其中障礙數(shù)量初始為100，當(dāng)障礙數(shù)量較少到90時，表中算法的CPU執(zhí)行時間都減少，因?yàn)檎系K距離的計(jì)算比可視距離的計(jì)算更復(fù)雜，障礙的減少使得部分障礙距離變?yōu)橹苯泳嚯x，使得總的計(jì)算量減少，所以總的CPU執(zhí)行時間也減少。由于規(guī)則3的提出，判斷了障礙減少的情況，障礙的局部處理代替了OBS_UK_means算法的全局重新聚類，因此DYN_GORBSCAN算法的CPU執(zhí)行時間更少。

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

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

表4展現(xiàn)的是當(dāng)障礙物動態(tài)移動時DYN_GOMBSCAN算法與OBS_UK_means算法的CPU執(zhí)行時間的比較。由于OBS_UK_means算法分別對障礙移動前和障礙移動后重新聚類，因此OBS_UK_means算法的CPU執(zhí)行時間大于DYN_GOMBSCAN算法。

如表5所示，分別對算法進(jìn)行50次獨(dú)立聚類實(shí)驗(yàn)，統(tǒng)計(jì)每次實(shí)驗(yàn)的結(jié)果，并對每種算法求50次實(shí)驗(yàn)結(jié)果的平均值，對比算法的實(shí)驗(yàn)結(jié)果。結(jié)果顯示，對以上4組數(shù)據(jù)集，本文提出的G_OBSCAN算法的F-measure指標(biāo)平均值和S指標(biāo)均值均高于OBS_UK_means算法的評測指標(biāo)。通過實(shí)驗(yàn)可看出，G_OBSCAN算法表現(xiàn)出更好的聚類效果。

通過以上實(shí)驗(yàn)分析可知，本文提出的算法均具有較高的效率和準(zhǔn)確率。

5 結(jié)束語

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

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

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