国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2019-04-18 02:24:26崔美玉何云斌
計算機與生活 2019年3期
關(guān)鍵詞:障礙物聚類障礙

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

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

1 引言

近年來,數(shù)據(jù)挖掘[1]技術(shù)受到越來越多人的關(guān)注,聚類[2]分析也成為了最近幾年研究的熱點。聚類分析是一種分析數(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])等。文獻[9]提出了核聚類算法,通過對樣本特征的優(yōu)化,使得算法收斂速度加快,性能得到了較大的改進。文獻[10]提出了一種基于原型的凝聚層次聚類U-AHC(uncertain-agglomerative hierachical clustering)算法,采用了信息論和期望距離來比較不確定數(shù)據(jù)對象。文獻[11]提出了PDBSCAN(paralell density-based spatial clustering of applications with noise)算法,通過定義分層密度、模糊核心距離和模糊可達距離來解決自適應(yīng)閾值的問題。

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

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

現(xiàn)有的數(shù)據(jù)聚類研究成果大多都是針對確定數(shù)據(jù)的聚類問題,因此本文解決的是障礙空間中的不確定數(shù)據(jù)聚類問題,利用網(wǎng)格對數(shù)據(jù)進行劃分。根據(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ù)點集用X={X1,X2,…,Xn}表示,其中pi為概率值;網(wǎng)格空間由S={S1,S2,…,Sm}組成;障礙集用O={O1,O2,…,Om}表示。文獻[17]對數(shù)據(jù)空間進行了均勻網(wǎng)格劃分;文獻[18]給出了聚簇代表點質(zhì)心Ci的定義;文獻[19]給出了數(shù)據(jù)點之間可視性的定義?;谝陨隙x,本文進一步給出如下定義。

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

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

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

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

定義3(密度閾值ε)

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

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

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

3 算法描述

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

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

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

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

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

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

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

基于以上的分析和討論,進一步提出靜態(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)實生活中的空間障礙物可能會發(fā)生動態(tài)改變,因此提出障礙物動態(tài)變化情況下的不確定數(shù)據(jù)聚類算法。

規(guī)則2首先定位新增障礙的位置,判斷新增障礙的加入是否改變了網(wǎng)格中不確定數(shù)據(jù)點之間的可視性,若沒有改變可視性則調(diào)用算法1;若新增障礙的加入,改變了不確定數(shù)據(jù)點之間的可視性,則只需重新判斷由可視的不確定數(shù)據(jù)點變?yōu)椴豢梢暭现械牟淮_定數(shù)據(jù)點的聚類結(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中部分數(shù)據(jù)變得不可視,P1>P1′并且P2<P2′,因此障礙O4的動態(tài)加入對聚類結(jié)果產(chǎn)生了影響。障礙O5的動態(tài)加入,不確定數(shù)據(jù)點之間依然是互為可視的,P1=P1′并且P2=P2′。綜上分析,新增加的障礙可能對聚類結(jié)果產(chǎn)生影響,也可能對聚類結(jié)果沒有影響。規(guī)則2通過判斷新增障礙所在的局部網(wǎng)格空間中的不確定數(shù)據(jù)點來代替全體數(shù)據(jù)點的重新聚類,減少了大量的障礙距離的判斷,使得算法的效率提高。

基于以上分析,進一步提出障礙物動態(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)減少之前,可視點集合為P1,不可視集合為P2。在障礙物動態(tài)減少之后,可視點集合標(biāo)記為P1′,不可視點集合為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ù)點的聚類。

如圖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)減少前后的可視集合和不可視集合的變化進行分析,并對減少的障礙物不改變聚類結(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的情況。

基于以上的分析,進一步給出障礙物動態(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)變化的,需進一步判斷是障礙的數(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 實驗比較與分析

由于現(xiàn)有的研究成果大多處理的是靜態(tài)障礙空間中的不確定數(shù)據(jù)聚類問題,而沒有研究障礙動態(tài)變化時的不確定數(shù)據(jù)聚類問題。為了驗證本文方法的有效性和準(zhǔn)確性,根據(jù)障礙集合是否發(fā)生改變,對文獻[19]所提的OBS_UK_means算法進行處理。若障礙集合不發(fā)生任何改變,則不需要對OBS_UK_means算法進行任何處理,并與本文提出的STA_GOBSCAN方法進行實驗對比;若障礙集合發(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ào)用OBS_UK_means算法。

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

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

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

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

圖6給出了不確定數(shù)據(jù)點規(guī)模的增加對CPU執(zhí)行時間的影響。實驗的障礙物數(shù)量為100,由圖可知,隨著不確定數(shù)據(jù)點規(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í)行時間都減少,因為障礙距離的計算比可視距離的計算更復(fù)雜,障礙的減少使得部分障礙距離變?yōu)橹苯泳嚯x,使得總的計算量減少,所以總的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所示,分別對算法進行50次獨立聚類實驗,統(tǒng)計每次實驗的結(jié)果,并對每種算法求50次實驗結(jié)果的平均值,對比算法的實驗結(jié)果。結(jié)果顯示,對以上4組數(shù)據(jù)集,本文提出的G_OBSCAN算法的F-measure指標(biāo)平均值和S指標(biāo)均值均高于OBS_UK_means算法的評測指標(biāo)。通過實驗可看出,G_OBSCAN算法表現(xiàn)出更好的聚類效果。

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

5 結(jié)束語

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

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

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

猜你喜歡
障礙物聚類障礙
睡眠障礙,遠不是失眠那么簡單
高低翻越
SelTrac?CBTC系統(tǒng)中非通信障礙物的設(shè)計和處理
基于DBSACN聚類算法的XML文檔聚類
電子測試(2017年15期)2017-12-18 07:19:27
跨越障礙
多導(dǎo)睡眠圖在睡眠障礙診斷中的應(yīng)用
基于改進的遺傳算法的模糊聚類算法
一種層次初始的聚類個數(shù)自適應(yīng)的聚類方法研究
“換頭術(shù)”存在四大障礙
自適應(yīng)確定K-means算法的聚類數(shù):以遙感圖像聚類為例
阿荣旗| 莫力| 盐津县| 久治县| 高雄县| 璧山县| 林州市| 文登市| 鱼台县| 溧阳市| 元阳县| 新野县| 乐山市| 静海县| 上蔡县| 宜良县| 抚宁县| 阜城县| 门源| 宜春市| 淅川县| 天全县| 沁阳市| 洪泽县| 宁强县| 嘉黎县| 松滋市| 读书| 永兴县| 鲜城| 无为县| 山西省| 尤溪县| 六盘水市| 苏尼特左旗| 读书| 高唐县| 阿瓦提县| 郑州市| 宿州市| 大同县|