隨機(jī)采樣移動(dòng)軌跡時(shí)空熱點(diǎn)區(qū)域發(fā)現(xiàn)及模式挖掘

王 亮，胡琨元，庫(kù) 濤，吳俊偉，2

(1.中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所，沈陽(yáng)110016;2.中國(guó)科學(xué)院大學(xué)，北京100039;3.西安科技大學(xué) 電氣與控制工程學(xué)院，西安710054)

0 引 言

隨著GPS、RFID，傳感器網(wǎng)絡(luò)和無線通信等技術(shù)的不斷發(fā)展和普及，越來越多的移動(dòng)軌跡數(shù)據(jù)被采集和存儲(chǔ)在應(yīng)用服務(wù)器中。對(duì)移動(dòng)軌跡數(shù)據(jù)進(jìn)行分析，從中發(fā)現(xiàn)所蘊(yùn)含的有效知識(shí)信息，對(duì)于交通管理、氣象監(jiān)測(cè)、商業(yè)推廣等領(lǐng)域都具有非常重要的作用［1-2］。在實(shí)際的應(yīng)用中，由于存儲(chǔ)空間、網(wǎng)絡(luò)傳輸以及計(jì)算能力等因素的限制，對(duì)于移動(dòng)對(duì)象定位數(shù)據(jù)的采集往往具有隨機(jī)采樣的特征，即前后軌跡位置數(shù)據(jù)之間的時(shí)間間隔不是固定值，而是某一范圍內(nèi)的隨機(jī)數(shù)值。這種隨機(jī)采樣移動(dòng)軌跡數(shù)據(jù)在時(shí)間維度分布上不均勻，存在數(shù)據(jù)分布的密集區(qū)間與稀疏區(qū)間。密集區(qū)間所包含的信息足以刻畫移動(dòng)對(duì)象在相應(yīng)時(shí)間段內(nèi)的移動(dòng)行為特征，但可能存在一定數(shù)量的冗余數(shù)據(jù);而稀疏區(qū)間的信息由于信息缺失往往難以準(zhǔn)確描述移動(dòng)對(duì)象的移動(dòng)歷史軌跡。這種數(shù)據(jù)空間分布的不均勻特性給移動(dòng)軌跡的特征聚類及模式挖掘帶來了新的難題。

目前對(duì)于移動(dòng)軌跡模式挖掘問題已有較多的方法，大致可分為基于移動(dòng)軌跡形狀的方法［3-6］和基于符號(hào)序列的方法［7-10］?；谝苿?dòng)軌跡形狀的分析方法通常利用線性插值將移動(dòng)軌跡在二維平面或三維時(shí)空內(nèi)連接成完整的曲線，進(jìn)而利用不同移動(dòng)軌跡曲線之間的距離計(jì)算對(duì)移動(dòng)軌跡進(jìn)行聚類分析和模式發(fā)現(xiàn)?；诜?hào)序列的方法將移動(dòng)軌跡表示為包含移動(dòng)位置點(diǎn)的空間區(qū)域符號(hào)序列，通過將原始三元軌跡數(shù)據(jù)轉(zhuǎn)換成二元數(shù)據(jù)表示的序列數(shù)據(jù)，從而利于傳統(tǒng)的序列模式挖掘算法對(duì)移動(dòng)軌跡模式進(jìn)行發(fā)現(xiàn)與分析。然而，上述兩種移動(dòng)模式挖掘方法均無法有效解決隨機(jī)采樣移動(dòng)軌跡數(shù)據(jù)所帶來的問題。同時(shí)，現(xiàn)有的文獻(xiàn)對(duì)于隨機(jī)采樣移動(dòng)軌跡的模式挖掘問題研究較少，大多集中在數(shù)據(jù)丟失或是低數(shù)據(jù)采樣率而引起的移動(dòng)路徑重構(gòu)和地圖匹配等方面的問題［11-13］。

對(duì)于隨機(jī)采樣移動(dòng)軌跡數(shù)據(jù)而言，如何有效檢測(cè)其密集數(shù)據(jù)分布的時(shí)間區(qū)間，尤其是群體軌跡的普遍密集數(shù)據(jù)分布時(shí)間區(qū)間，進(jìn)而以相應(yīng)時(shí)間區(qū)間內(nèi)的移動(dòng)軌跡特征來發(fā)現(xiàn)群體意義上的熱點(diǎn)區(qū)域是當(dāng)前所面臨的主要問題。Giannotti 等［7］基于密度度量的方式定義了空間興趣區(qū)域(Region of interesting，ROI)，分別以靜態(tài)和動(dòng)態(tài)的方式對(duì)ROI 區(qū)域進(jìn)行了探測(cè)與發(fā)現(xiàn)，進(jìn)而對(duì)以ROI 表示的帶時(shí)間注釋的移動(dòng)序列數(shù)據(jù)進(jìn)行了頻繁模式的挖掘。Wang 等［9］對(duì)固定采樣間隔的移動(dòng)軌跡數(shù)據(jù)進(jìn)行了閉合頻繁模式的挖掘，基于等間隔的離散時(shí)間切片，以等規(guī)則空間網(wǎng)格劃分的方法對(duì)不同時(shí)間切片層的熱點(diǎn)時(shí)空區(qū)域進(jìn)行了探測(cè)。

在上述研究的基礎(chǔ)上，本文首先將隨機(jī)采樣移動(dòng)軌跡數(shù)據(jù)在一維時(shí)間軸上進(jìn)行投影轉(zhuǎn)換得到對(duì)應(yīng)的時(shí)間投影數(shù)據(jù)集;然后采用自底向上和滑動(dòng)時(shí)間窗口相結(jié)合的策略以提取密集時(shí)間區(qū)間;進(jìn)而基于密集時(shí)間區(qū)間以發(fā)現(xiàn)相應(yīng)時(shí)段上的時(shí)空熱點(diǎn)區(qū)域，利用時(shí)空熱點(diǎn)區(qū)域集合對(duì)原始軌跡數(shù)據(jù)集合進(jìn)行軌跡簡(jiǎn)約和數(shù)據(jù)序列轉(zhuǎn)換;最后基于序列模式挖掘的方法對(duì)移動(dòng)軌跡頻繁模式進(jìn)行挖掘和發(fā)現(xiàn)。

1 定義及問題描述

定義1 移動(dòng)軌跡是由移動(dòng)對(duì)象在空間上的移動(dòng)而產(chǎn)生的連續(xù)運(yùn)動(dòng)軌跡。在三維時(shí)空域中，移動(dòng)軌跡Tr={(xi，yi，ti)，1 ≤i ≤N}是由空間元素和時(shí)間元素所表示的三元數(shù)據(jù)組，其中(xi，yi)為移動(dòng)對(duì)象對(duì)應(yīng)于瞬時(shí)時(shí)間ti的空間位置;N為移動(dòng)軌跡的長(zhǎng)度。

定義2 移動(dòng)時(shí)間間隔是移動(dòng)軌跡中前后相鄰的兩個(gè)數(shù)據(jù)(xi，yi，ti)與(xi+1，yi+1，ti+1)之間的時(shí)間差值，其公式為:TimeInterval =ti+1－ti。時(shí)間間隔長(zhǎng)度表征的是移動(dòng)軌跡的數(shù)據(jù)采集周期，在固定采樣間隔條件下，相鄰時(shí)間間隔為一個(gè)恒等值;而在隨機(jī)采用情況下其為某一取值范圍內(nèi)的任意值。

定義3 移動(dòng)頻繁模式是移動(dòng)軌跡數(shù)據(jù)庫(kù)中其支持度不小于用戶所給定的最小支持度閾值min_sup 的移動(dòng)模式，其具有如下的形式:(Ri，TIki)→(Rj，TIkj)，其中Ri為空間中的某一區(qū)域;TIki為移動(dòng)時(shí)間周期中的某一段時(shí)間區(qū)間。

隨機(jī)采樣移動(dòng)軌跡數(shù)據(jù)可以用圖1 進(jìn)行描述:Tr1和Tr2分別為兩個(gè)隨機(jī)采樣的移動(dòng)軌跡，其中箭頭所標(biāo)注的位置點(diǎn)為其采樣時(shí)刻所在的空間位置;Constant Sample 為固定采樣率下等時(shí)間間隔移動(dòng)軌跡;Ra和Rb分別為空間區(qū)域。由圖可見，在固定采樣率下Tr1和Tr2有著相近的移動(dòng)軌跡Constant Sample。而在隨機(jī)采樣條件下，由于二者密集數(shù)據(jù)區(qū)間與稀疏數(shù)據(jù)區(qū)間互不重合，軌跡Tr1和Tr2具有完全不同的形狀。

由上可知在隨機(jī)采樣條件下，具有相近行為特征的移動(dòng)軌跡其近似度在很大程度上被弱化。同時(shí)，密集數(shù)據(jù)區(qū)間信息冗余與稀疏數(shù)據(jù)區(qū)間信息缺失并存，這對(duì)于數(shù)據(jù)特征的抽取以及移動(dòng)模式的挖掘都帶來了困難和挑戰(zhàn)。因此，本文所研究的問題就是在上述隨機(jī)采樣條件下，對(duì)于群體移動(dòng)軌跡下的熱點(diǎn)時(shí)空區(qū)域(Spatiotemporal hot spot region，STHSR)進(jìn)行檢測(cè)和發(fā)現(xiàn)，同時(shí)挖掘其中所蘊(yùn)含的頻繁移動(dòng)行為模式。

圖1 隨機(jī)采樣移動(dòng)軌跡比較圖示Fig.1 Comparison of moving trajectory by random sampling

2 隨機(jī)采樣移動(dòng)軌跡時(shí)空熱點(diǎn)區(qū)域發(fā)現(xiàn)

首先對(duì)移動(dòng)軌跡在時(shí)間軸做一維投影，基于滑動(dòng)時(shí)間窗對(duì)一維時(shí)間投影數(shù)據(jù)進(jìn)行自動(dòng)聚類，以實(shí)現(xiàn)對(duì)移動(dòng)軌跡密集時(shí)間區(qū)間的提取和發(fā)現(xiàn)，進(jìn)而采用密度統(tǒng)計(jì)的方法對(duì)滑動(dòng)時(shí)間窗內(nèi)的移動(dòng)時(shí)空軌跡點(diǎn)進(jìn)行二維平面投影，以發(fā)現(xiàn)相應(yīng)時(shí)間段上的時(shí)空熱點(diǎn)區(qū)域STHSR。

2.1 基于滑動(dòng)時(shí)間窗的移動(dòng)軌跡密集時(shí)間區(qū)間提取

對(duì)于隨機(jī)采樣移動(dòng)軌跡而言，其數(shù)據(jù)點(diǎn)在時(shí)間維度上的分布隨機(jī)而無規(guī)律，其前后相鄰軌跡點(diǎn)之間的時(shí)間間隔長(zhǎng)度長(zhǎng)短不一。由于采樣時(shí)間間隔過大或數(shù)據(jù)丟失將使得部分時(shí)間區(qū)間內(nèi)的數(shù)據(jù)分布稀疏;另一方面，由于頻繁采樣或是傳輸延時(shí)等原因，部分時(shí)間區(qū)間內(nèi)的數(shù)據(jù)可能分布密集。稀疏時(shí)段的數(shù)據(jù)可能存在信息缺失的問題，而密集時(shí)段的數(shù)據(jù)可能存在數(shù)據(jù)冗余的問題。這種數(shù)據(jù)空間分布狀態(tài)的不均衡將對(duì)移動(dòng)行為特征提取和移動(dòng)軌跡的聚類帶來困難。

另一方面，隨機(jī)采樣移動(dòng)軌跡數(shù)據(jù)在時(shí)間維度上的連續(xù)性分布特征，使得其無法像固定采樣間隔的軌跡數(shù)據(jù)一樣內(nèi)在地實(shí)現(xiàn)對(duì)時(shí)間域的離散化劃分，因而在時(shí)間域上將存在近似化表示的問題。基于此，考慮對(duì)移動(dòng)軌跡數(shù)據(jù)在一維時(shí)間軸上進(jìn)行投影轉(zhuǎn)換，以形成一維時(shí)間投影數(shù)據(jù)。進(jìn)而對(duì)該時(shí)間投影數(shù)據(jù)進(jìn)行基于滑動(dòng)時(shí)間窗的聚類劃分，以動(dòng)態(tài)區(qū)分和發(fā)現(xiàn)移動(dòng)軌跡密集時(shí)間區(qū)間和稀疏時(shí)間區(qū)間，最終實(shí)現(xiàn)依據(jù)移動(dòng)軌跡時(shí)間域上的分布特征對(duì)其進(jìn)行近似化劃分的目的。

將三維移動(dòng)時(shí)空軌跡在時(shí)間軸上進(jìn)行投影，對(duì)應(yīng)地軌跡點(diǎn)(xi，yi，ti)在時(shí)間軸上的投影值為其時(shí)間戳ti。如圖2 所示，從移動(dòng)軌跡點(diǎn)(xi，yi，ti)出發(fā)的平行于X-Y 平面的虛線與時(shí)間T 軸相交于ti點(diǎn)位置，也即實(shí)現(xiàn)了從三維時(shí)空數(shù)據(jù)向一維時(shí)間投影數(shù)據(jù)的轉(zhuǎn)換:(xi，yi，ti)→(ti)。

圖2 三維時(shí)空移動(dòng)軌跡的一維時(shí)間軸投影Fig.2 Projection of spatiotemporal trajectory to timeline

構(gòu)建了移動(dòng)軌跡的時(shí)間軸投影之后，可得到相應(yīng)的一維時(shí)間投影數(shù)據(jù)。投影數(shù)據(jù)在連續(xù)時(shí)間域上呈不規(guī)則分布，密集分布時(shí)間區(qū)間包含較多的移動(dòng)軌跡點(diǎn)，稀疏分布時(shí)間區(qū)間則包含較少的移動(dòng)軌跡點(diǎn)。軌跡點(diǎn)密集的區(qū)間包含有豐富的移動(dòng)行為信息，而稀疏區(qū)間則由于數(shù)據(jù)丟失或是采樣間隔過大而信息量很少。顯而易見，軌跡點(diǎn)密集的時(shí)間區(qū)間對(duì)于移動(dòng)行為模式識(shí)別、移動(dòng)熱點(diǎn)空間區(qū)域發(fā)現(xiàn)、移動(dòng)軌跡聚類等具有重要的作用。因此，如何從移動(dòng)軌跡的一維時(shí)間投影數(shù)據(jù)中辨識(shí)出分布密集的區(qū)域，從而為后續(xù)的熱點(diǎn)區(qū)域發(fā)現(xiàn)提供支持是需要解決的首要問題。

考慮采用滑動(dòng)時(shí)間窗對(duì)一維時(shí)間投影數(shù)據(jù)進(jìn)行分割聚類，以實(shí)現(xiàn)對(duì)軌跡點(diǎn)分布密集時(shí)間區(qū)間的提取和發(fā)現(xiàn)。

定義4 滑動(dòng)時(shí)間窗SW(Sliding window)為時(shí)間域上的一個(gè)寬度大小可變的有限區(qū)間，寬度用ΔT 表示，ΔT=Tend－Tstart，Tstart為SW 的起始時(shí)間，Tend為終止時(shí)間。當(dāng)ΔT=0 時(shí)，意味著起始時(shí)間與終止時(shí)間一致，則滑動(dòng)時(shí)間窗退化為移動(dòng)軌跡在瞬時(shí)時(shí)間上的移動(dòng)信息。

移動(dòng)軌跡Tr 在滑動(dòng)時(shí)間窗SW 內(nèi)的軌跡點(diǎn)的個(gè)數(shù)記為Num(Tr，SW)。需要注意的是，對(duì)于隨機(jī)采樣間隔數(shù)據(jù)而言，在滑動(dòng)時(shí)間窗SW 內(nèi)可能包含同一個(gè)移動(dòng)軌跡Tr 的多個(gè)軌跡點(diǎn)，也可能不包含Tr 的任一軌跡點(diǎn)。對(duì)于多移動(dòng)軌跡而言，滑動(dòng)時(shí)間窗SW 內(nèi)的軌跡點(diǎn)數(shù)記為Num(SW)。

定義 5 密集時(shí)間區(qū)間為滿足條件Num(SW)≥φ·Mean_Num(SW)的滑動(dòng)時(shí)間窗SW，其中φ 為自定義系數(shù)，Mean_Num(SW)為寬度大小為SW 的滑動(dòng)窗內(nèi)的平均移動(dòng)軌跡點(diǎn)的個(gè)數(shù)。

通過原始三維移動(dòng)軌跡數(shù)據(jù)的一維時(shí)間投影，發(fā)現(xiàn)變長(zhǎng)滑動(dòng)窗密集時(shí)間區(qū)間問題可簡(jiǎn)化為一維數(shù)據(jù)的聚類劃分問題，如圖3 所示，其中左側(cè)為三維立體圖，右側(cè)為一維時(shí)間軸圖。由圖3 可知，移動(dòng)軌跡點(diǎn)p1與p2落在寬度為ΔT 的滑動(dòng)時(shí)間窗SW 內(nèi)，因此，Num(SW)的取值為2。

圖3 移動(dòng)軌跡密集時(shí)間區(qū)間提取Fig.3 Extraction of intensive time interval

由于最終聚類的個(gè)數(shù)等相關(guān)信息未知，因此必須設(shè)計(jì)出適應(yīng)于此類問題的聚類算法?？紤]采用自底向上的聚類思想，通過最近鄰數(shù)據(jù)的窗體合并和閾值判定相結(jié)合的策略，實(shí)現(xiàn)對(duì)一維時(shí)間投影數(shù)據(jù)的動(dòng)態(tài)聚類。其中閾值判定參數(shù)包含時(shí)間窗寬度上限ε 與滑動(dòng)窗體SW 的平均移動(dòng)軌跡點(diǎn)數(shù)Mean_Num(SW)。設(shè)定時(shí)間窗寬度上限ε的目的在于:過大的時(shí)間間隔上即使其具有足夠多的移動(dòng)軌跡點(diǎn)數(shù)量分布，但其所定義熱點(diǎn)區(qū)域的群體特征不明顯，也難以有效刻畫有限時(shí)間窗體上的移動(dòng)區(qū)域熱點(diǎn)程度。而平均移動(dòng)軌跡點(diǎn)數(shù)Mean_Num(SW)參數(shù)的目的在于保證時(shí)間窗體SW 內(nèi)有足夠多的移動(dòng)軌跡點(diǎn)，因?yàn)橄∈钑r(shí)間區(qū)間內(nèi)移動(dòng)軌跡點(diǎn)數(shù)量有限，無法利用較少的移動(dòng)軌跡點(diǎn)進(jìn)行熱點(diǎn)時(shí)空區(qū)域的發(fā)現(xiàn)。所得到的密集時(shí)間窗體其寬度可以為0，即為一個(gè)瞬時(shí)時(shí)間切片，其中為密集時(shí)間區(qū)間SW 的寬度，則合并SWi與SWj以形成新的密集時(shí)間區(qū)間;同時(shí)更新信息表List;

步驟6 重復(fù)執(zhí)行步驟5 直到集合DSW 不再進(jìn)行更新操作為止;

步驟7 逐次計(jì)算集合DSW 中的每一個(gè)元素所包含的軌跡點(diǎn)數(shù)，對(duì)于滿足閾值條件Num(SW)≥φ·Mean_Num(SW)的元素保留，反之，則刪除。

2.2 基于密度統(tǒng)計(jì)的時(shí)空熱點(diǎn)區(qū)域發(fā)現(xiàn)

定義6 時(shí)空熱點(diǎn)區(qū)域R=(Cellm，Wn)是某一時(shí)間段［Tstart，Tend］內(nèi)基于移動(dòng)軌跡分布特征的熱點(diǎn)空間區(qū)域。

由于空間區(qū)域的不同功能定位和移動(dòng)群體的行為周期性特點(diǎn)，移動(dòng)群體意義上的熱點(diǎn)空間區(qū)域具有顯著的時(shí)變特征。也就是說，在不同的時(shí)間段上熱點(diǎn)區(qū)域具有不同的空間分布特征。因此，對(duì)不同時(shí)間內(nèi)的時(shí)空熱點(diǎn)區(qū)域進(jìn)行發(fā)現(xiàn)和提取，可以分析連續(xù)時(shí)間周期內(nèi)熱點(diǎn)區(qū)域的變化和遷移規(guī)律，從而間接得出移動(dòng)群體在相應(yīng)時(shí)間上的行為模式。需要注意的是，本文所定義的時(shí)空熱點(diǎn)區(qū)域是具有明確時(shí)間區(qū)間標(biāo)注的，即某一特定時(shí)間段之內(nèi)的空間熱點(diǎn)區(qū)域，這與傳統(tǒng)的在整ΔT=0，也可為一個(gè)小于寬度上限ε 的滑動(dòng)時(shí)間窗體0 ＜ΔT ≤ε。最終基于該密集時(shí)間窗構(gòu)造高度為ΔT，且覆蓋整個(gè)移動(dòng)平面區(qū)域的時(shí)空箱體，進(jìn)而探測(cè)時(shí)空熱點(diǎn)區(qū)域STHSR 集合。

基于以上描述，移動(dòng)軌跡密集時(shí)間區(qū)間提取算法的基本步驟如下:

算法1 DTIE(Density time interval extracting algorithm from moving trajectory)

輸入:D={Tr1，Tr2，…，Trn}，最大時(shí)間窗體寬度閾值ε;自定義系數(shù)φ。

輸出:密集時(shí)間區(qū)間集合DSW={SW1，SW2，…，SWm}。

步驟1 初始化所有的軌跡;

步驟2 將移動(dòng)軌跡在時(shí)間T 軸上進(jìn)行投影，得到時(shí)間分布投影數(shù)據(jù)集TD;

步驟3 對(duì)TD 中的數(shù)據(jù)進(jìn)行去重計(jì)算，得到無重復(fù)數(shù)據(jù)集TD';

步驟4 將TD'中的每一個(gè)元素進(jìn)行初始化，令TD'=DSW;

步驟5 對(duì)于集合DSW 中的元素SWi計(jì)算與最近鄰元素SWj的距離，若滿足條件Dist(SWi，個(gè)時(shí)間周期內(nèi)發(fā)現(xiàn)熱點(diǎn)區(qū)域的方法相比具有更為豐富的時(shí)間語(yǔ)義信息，同時(shí)可動(dòng)態(tài)揭示移動(dòng)群體的行為模式。

當(dāng)提取出移動(dòng)軌跡時(shí)間軸分布密集區(qū)間DSW={W1，W2，…，Wm}之后，則可以分別對(duì)Wi∈DSW 滑動(dòng)時(shí)間窗體內(nèi)的軌跡點(diǎn)進(jìn)行聚類劃分，以發(fā)現(xiàn)時(shí)空熱點(diǎn)區(qū)域集合STHSR。需要注意的是在密集時(shí)間區(qū)間Wi，若移動(dòng)軌跡Tr 在同一個(gè)網(wǎng)格單元Cellj內(nèi)存在多個(gè)軌跡點(diǎn)，則只累計(jì)計(jì)算一次，這樣做的目的是為了有效剔除密集時(shí)間區(qū)間內(nèi)的冗余軌跡數(shù)據(jù)。

移動(dòng)軌跡時(shí)空熱點(diǎn)區(qū)域發(fā)現(xiàn)算法的基本步驟如下:

算法2 STHSRD(Spatio-tempaoral hot spot region discovering algorithm)

輸入:移動(dòng)軌跡數(shù)據(jù)集D = {Tr1，Tr2，…，Trn}，密集時(shí)間區(qū)間集合DSW = {W1，W2，…，Wm}，最小支持度閾值min_sup。

輸出:時(shí)空熱點(diǎn)區(qū)域集合STHSR={R1，R2，…，Rl}。

步驟1 初始化;

步驟2 對(duì)每個(gè)Wi∈DSW 提取時(shí)間戳位于此區(qū)間的所有軌跡點(diǎn)TrPi;

步驟3 對(duì)TrPi中屬于同一條軌跡的空間點(diǎn)做去重操作;

步驟4 將處理后的TrPi軌跡點(diǎn)平面投影，同時(shí)對(duì)平面做規(guī)則網(wǎng)格粒度劃分，生成規(guī)模為G 的離散空間網(wǎng)格單元Grid={Celli，i=G};

步驟5 對(duì)每個(gè)網(wǎng)格單元內(nèi)的軌跡位置點(diǎn)進(jìn)行統(tǒng)計(jì)計(jì)算，若有Celli_Num ≥min_sup，即Celli內(nèi)的軌跡點(diǎn)數(shù)大于或等于最小支持度閾值min_sup，則STHSR=STHSR ∪Celli。

這樣，就可得到已知時(shí)間區(qū)間段內(nèi)的時(shí)空熱點(diǎn)區(qū)域集合STHSR。

3 基于時(shí)空熱點(diǎn)區(qū)域的移動(dòng)模式挖掘

在得到了移動(dòng)軌跡的時(shí)空熱點(diǎn)區(qū)域之后，即可通過時(shí)空熱點(diǎn)區(qū)域集合STHSR 對(duì)原始移動(dòng)軌跡進(jìn)行軌跡簡(jiǎn)約。具體過程為將原始軌跡數(shù)據(jù)中的時(shí)空軌跡點(diǎn)(xi，yi，ti)與STHSR 集合中的時(shí)空熱點(diǎn)區(qū)域元素Ri進(jìn)行匹配計(jì)算，只有當(dāng)同時(shí)滿足如下兩個(gè)條件:①時(shí)間戳ti屬于Ri所對(duì)應(yīng)的密集時(shí)間窗SWi=［T'start，T'end］，即T'start≤ti≤T'end;②空間軌跡位置點(diǎn)(xi，yi)位于Ri所屬網(wǎng)格空間單元內(nèi)，即(xi，yi)∈Ri，則軌跡點(diǎn)(xi，yi，ti)可轉(zhuǎn)換為時(shí)空熱點(diǎn)區(qū)域Ri元素。反之，則認(rèn)為時(shí)空軌跡點(diǎn)(xi，yi，ti)或是位于移動(dòng)軌跡稀疏時(shí)間區(qū)間或是位于非時(shí)空熱點(diǎn)區(qū)域而予以剔除。

通過上述移動(dòng)軌跡數(shù)據(jù)向時(shí)空熱點(diǎn)區(qū)域的轉(zhuǎn)換過程，可得到以時(shí)空熱點(diǎn)區(qū)域STHSR 為元素的序列數(shù)據(jù)集，一方面實(shí)現(xiàn)了對(duì)原始移動(dòng)軌跡的簡(jiǎn)約，另一方面也實(shí)現(xiàn)了軌跡的時(shí)空語(yǔ)義近似化表示。對(duì)轉(zhuǎn)換后的STHSR 序列數(shù)據(jù)進(jìn)行頻繁模式挖掘，所得到的移動(dòng)模式形式如:Ri→Rj，其表示移動(dòng)對(duì)象順序通過時(shí)空熱點(diǎn)區(qū)域Ri與Rj。需要注意的是，Ri→Rj的模式表示不僅具有空間域上的移動(dòng)遷移信息，同時(shí)具有時(shí)間域上的對(duì)應(yīng)區(qū)間信息。本文采用深度優(yōu)先搜索策略，基于經(jīng)典的序列模式挖掘算法PrefixSpan 進(jìn)行相關(guān)改進(jìn)，以對(duì)STHSR 序列數(shù)據(jù)集進(jìn)行頻繁模式的挖掘。

基于時(shí)空熱點(diǎn)區(qū)域的移動(dòng)軌跡頻繁模式挖掘算法表述如下:

算法3 FMTPM(Frequent moving trajectory pattern mining algorithm based on STHSR)

輸入:移動(dòng)軌跡數(shù)據(jù)集D = {Tr1，Tr2，…，Trn}，最小支持度min_sup，時(shí)空熱點(diǎn)區(qū)域集合STHSR={R1，R2，…，Rl}。

輸出:移動(dòng)軌跡頻繁模式集合。

步驟1 將原始移動(dòng)軌跡數(shù)據(jù)庫(kù)D 轉(zhuǎn)換為STHSR 序列數(shù)據(jù)庫(kù);

步驟2 對(duì)STHSR 序列數(shù)據(jù)庫(kù)進(jìn)行掃描，得到長(zhǎng)度為1 的頻繁序列模式L1;

步驟3 對(duì)每個(gè)頻繁序列模式L1構(gòu)建投影數(shù)據(jù)庫(kù)，探測(cè)所有頻繁項(xiàng)，生成長(zhǎng)度為2 的頻繁序列模式L2;

步驟4 對(duì)所產(chǎn)生的長(zhǎng)度為k 的序列模式Lk構(gòu)建投影庫(kù)，探測(cè)所有頻繁項(xiàng)，生成長(zhǎng)度為(k+1)的頻繁序列模式Lk+1;

步驟5 循環(huán)步驟4 以產(chǎn)生頻繁移動(dòng)軌跡模式集PatternSet。

4 試驗(yàn)及結(jié)果分析

為了驗(yàn)證本文所提出方法的有效性，采用GSTD 時(shí)空軌跡數(shù)據(jù)產(chǎn)生算法［14-15］生成仿真數(shù)據(jù)，其可虛擬生成時(shí)空三維特征屬性表示下的移動(dòng)軌跡數(shù)據(jù)集合。本文在GSTD 算法的基礎(chǔ)之上，針對(duì)隨機(jī)采樣移動(dòng)軌跡的條件要求，通過算法的相關(guān)調(diào)整和修改產(chǎn)生了試驗(yàn)部分所需要的仿真測(cè)試移動(dòng)軌跡數(shù)據(jù)。其中數(shù)據(jù)規(guī)模為2000 ～5000條，數(shù)據(jù)采樣周期為600 ～1200 s，對(duì)應(yīng)的數(shù)據(jù)平均長(zhǎng)度為86 ～172，自定義系數(shù)φ 設(shè)置為1.1。

所用試驗(yàn)設(shè)備為個(gè)人PC，中央處理器為Pentium(R)Dual-Core CPU T4400@2.20 GHz，內(nèi)存為2.00 GB(1.99 GB usable)，操作系統(tǒng)為Windows XP 32 b。所用編程語(yǔ)言為Matlab 2010 b。

圖4 為隨機(jī)采樣移動(dòng)軌跡數(shù)據(jù)密集時(shí)間區(qū)間比較結(jié)果。其中圖4(a)為在等時(shí)間滑動(dòng)窗ΔT=20 上統(tǒng)計(jì)得出的分段移動(dòng)軌跡數(shù)據(jù)點(diǎn)與整個(gè)采樣周期平均移動(dòng)軌跡點(diǎn)的差值，由圖可見，以等寬度劃分的時(shí)間間隔內(nèi)的移動(dòng)軌跡點(diǎn)分布極不均勻，部分區(qū)間與平均點(diǎn)數(shù)相近，而部分區(qū)間與平均點(diǎn)數(shù)相差較大。對(duì)應(yīng)的差值為正數(shù)的時(shí)間區(qū)間為密集數(shù)據(jù)區(qū)間;差值為負(fù)數(shù)的時(shí)間區(qū)間為稀疏時(shí)間區(qū)間。

圖4 移動(dòng)軌跡密集時(shí)間區(qū)間提取試驗(yàn)結(jié)果Fig.4 Experiment of extracting intensive time interval

隨機(jī)移動(dòng)軌跡數(shù)據(jù)的密集時(shí)間窗提取問題，其在一定程度上屬于聚類劃分問題，即都是將具有相同分布特征的數(shù)據(jù)劃分為同一類別，且不同聚類簇之間的差別越大越好。然而其與聚類問題所不同之處在于，密集時(shí)間窗提取只關(guān)注數(shù)據(jù)分布密集的時(shí)間區(qū)間。由于隨機(jī)采樣移動(dòng)軌跡數(shù)據(jù)時(shí)間維分布疏密不均的特點(diǎn)，其既不可以通過等尺度劃分的方法進(jìn)行提取，亦也不可以直接通過聚類的方法進(jìn)行區(qū)間提取。本文將所提出的DTIE 算法與模糊C 均值聚類算法進(jìn)行試驗(yàn)仿真比較，以驗(yàn)證DTIE 算法的有效性。圖4(b)為本文所提出的密集時(shí)間窗提取方法與模糊C 均值聚類方法對(duì)上述試驗(yàn)數(shù)據(jù)處理后的結(jié)果，其分別為聚類中心點(diǎn)與密集時(shí)間區(qū)間中心點(diǎn)。為了在同一標(biāo)準(zhǔn)下對(duì)兩種方法進(jìn)行比對(duì)，模糊C 均值聚類的聚類數(shù)與DTIE 算法的密集時(shí)間區(qū)間數(shù)目取相同設(shè)置。由圖可見，模糊C 均值聚類所得出的時(shí)間區(qū)間分布均勻，且包含稀疏數(shù)據(jù)區(qū)間，顯然難以有效抽取隨機(jī)移動(dòng)軌跡數(shù)據(jù)中的密集時(shí)間區(qū)間;而DTIE 算法所得出的密集時(shí)間區(qū)間與圖4(a)所示的數(shù)據(jù)分布具有相近的分布特征，在剔除掉稀疏數(shù)據(jù)區(qū)間的同時(shí)可以有效發(fā)現(xiàn)密集時(shí)間區(qū)間。同時(shí)DTIE 算法所得出的密集時(shí)間區(qū)間平均寬度為10.23，而模糊C 均值聚類所得出的時(shí)間區(qū)間平均寬度為25.27，這是因?yàn)镈TIE 算法剔除了稀疏時(shí)間區(qū)間，而模糊C 均值聚類方法無法剔除稀疏時(shí)間區(qū)間。因而DTIE 算法在密集時(shí)間區(qū)間的檢測(cè)方面具有良好的性能。

圖5 為移動(dòng)軌跡時(shí)空熱點(diǎn)區(qū)域發(fā)現(xiàn)算法STHSRD 檢測(cè)到的熱點(diǎn)時(shí)空區(qū)域集合STHSR，其中圖5(a)為連續(xù)7 個(gè)密集時(shí)間區(qū)間所對(duì)應(yīng)的熱點(diǎn)時(shí)空區(qū)域;圖5(b)為所發(fā)現(xiàn)的所有時(shí)空熱點(diǎn)區(qū)域集合。注意由于采用的網(wǎng)格單元顏色數(shù)為7個(gè)，故而后續(xù)的密集時(shí)間區(qū)間所對(duì)應(yīng)的時(shí)空熱點(diǎn)區(qū)域的網(wǎng)格單元顏色按照?qǐng)D5(c)所示的順序循環(huán)往復(fù)。由圖可見，隨著時(shí)間的推移，移動(dòng)熱點(diǎn)區(qū)域具有隨時(shí)間變化的特點(diǎn)，這同時(shí)也反映出移動(dòng)群體在不同的時(shí)段具有不同的區(qū)域停留與偏好。

圖6 為算法3 基于時(shí)空熱點(diǎn)區(qū)域移動(dòng)模式挖掘的結(jié)果。圖6(a)為不同移動(dòng)軌跡規(guī)模下，算法所挖掘的頻繁模式結(jié)果與最小支持度的關(guān)系比較，其中移動(dòng)軌跡規(guī)模分別為3000 條，4000 條及5000 條?？梢钥闯觯S著最小支持度閾值的不斷增大，所挖掘的頻繁移動(dòng)軌跡模式數(shù)量不斷減小。同時(shí)隨著軌跡規(guī)模的增大，所挖掘的移動(dòng)頻繁模式數(shù)目不斷增加。圖6(b)為不同移動(dòng)軌跡平均長(zhǎng)度下，算法所挖掘的頻繁模式結(jié)果與最小支持度的關(guān)系比較，其中移動(dòng)軌跡的平均長(zhǎng)度分別為86，115 及144?？梢钥闯觯S著最小支持度閾值的不斷增大，所挖掘的頻繁移動(dòng)軌跡模式數(shù)量不斷減小。同時(shí)隨著移動(dòng)軌跡平均長(zhǎng)度的增大，所挖掘的移動(dòng)頻繁模式數(shù)目也不斷增加。

圖5 時(shí)空熱點(diǎn)區(qū)域發(fā)現(xiàn)試驗(yàn)結(jié)果圖示Fig.5 Experiment of discovering STHSRs

圖6 移動(dòng)頻繁模式挖掘試驗(yàn)結(jié)果Fig.6 Experiment results of mining frequent moving patterns

5 結(jié)束語(yǔ)

對(duì)隨機(jī)采樣條件下的移動(dòng)軌跡模式挖掘問題進(jìn)行了研究，針對(duì)隨機(jī)采樣移動(dòng)軌跡數(shù)據(jù)在時(shí)間域密集數(shù)據(jù)區(qū)間與稀疏數(shù)據(jù)區(qū)間隨機(jī)且并存的特點(diǎn)，通過將三維時(shí)空軌跡投影轉(zhuǎn)換為一維時(shí)間數(shù)據(jù)，提出了一種基于聚類的密集時(shí)間區(qū)間檢測(cè)和時(shí)空熱點(diǎn)區(qū)域發(fā)現(xiàn)方法，進(jìn)而以時(shí)空熱點(diǎn)區(qū)域?yàn)榛A(chǔ)對(duì)原始移動(dòng)軌跡數(shù)據(jù)進(jìn)行映射轉(zhuǎn)換，最后采用深度優(yōu)先搜索策略對(duì)轉(zhuǎn)換序列數(shù)據(jù)中的移動(dòng)頻繁模式進(jìn)行挖掘和發(fā)現(xiàn)。試驗(yàn)結(jié)果證明，本文所提出的方法具有良好的性能。

［1］Lee J W，Paek O H，Ryu K H.Temporal moving pattern mining for location-based service［J］.Journal of Systems and Software，2004，73(3):481-490.

［2］鄭宇，謝幸.基于用戶軌跡挖掘的智能位置服務(wù)［J］.中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊，2010，6(6):23-30.Zheng Yu，Xie Xing.Enable smart location-based services by mining user trajectories［J］.Communications of the CCF，2010，6(6):23-30.

［3］Cao H P，Mamoulis N，Cheung D W.Mining frequent spatio-temporal sequential patterns［C］∥Fifth IEEE International Conference on Data Mining，2005:82-89.

［4］Lee J G，Han J W，Whang K Y.Trajectory clustering:a partition-and-group framework［C］∥Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data，Beijing，China，2007:593-604.

［5］De Lucca Siqueira F，Bogorny V.Discovering chasing behavior in moving object trajectories［J］.Transactions in GIS，2011，15(5):667-688.

［6］Yanagisawa Y，Akahani J，Satoh T.Shape-based similarity query for trajectory of mobile objects［C］∥Mobile Data Management，Berlin，Germany，2003:63-77.

［7］Giannotti F，Nanni M，Pinelli F，et al.Trajectory pattern mining［C］∥Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，New York，2007:330-339.

［8］Kang J，Yong H S.Mining spatio-temporal patterns in trajectory data［J］.JIPS，2010，6(4):521-536.

［9］Wang L，Hu K，Ku T，et al.Discovering closed frequent patterns in moving trajectory database［C］∥14th International Conference on Communication Technology，Chengdu，2012:567-572.

［10］Lee A J T，Chen Y A，Ip W C.Mining frequent trajectory patterns in spatial—temporal databases［J］.Information Sciences，2009，179(13):2218-2231.

［11］Zheng Y，Lou Y，Zhang C，et al.Map-matching for low-sampling-rate GPS Trajectories［P］.U.S.Patent:12/712，857，2010-02-25.

［12］Pfoser D，Jensen C S.Capturing the uncertainty of moving-object representations［C］∥Advances in Spatial Databases，Berlin，Germany，1999:111-131.

［13］Miwa T，Kiuchi D，Yamamoto T，et al.Development of map matching algorithm for low frequency probe data［J］. Transportation Research Part C:Emerging Technologies，2012，22:132-145.

［14］Theodoridis Y，Nascimento M A.Generating spatiotemporal datasets on the WWW［J］.ACM SIGMOD Record，2000，29(3):39-43.

［15］Theodoridis Y，Silva J R O，Nascimento M A.On the generation of spatiotemporal datasets［C］∥In Proceedings of the 6th Int＇l Symposium on Large Spatial Databases，Hong Kong，China，1999:147-164.