王 亮，胡琨元，庫 濤，吳俊偉，2

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

0 引 言

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

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

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

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

1 定義及問題描述

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

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

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

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

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

圖1 隨機采樣移動軌跡比較圖示Fig.1 Comparison of moving trajectory by random sampling

2 隨機采樣移動軌跡時空熱點區(qū)域發(fā)現(xiàn)

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

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

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

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

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

圖2 三維時空移動軌跡的一維時間軸投影Fig.2 Projection of spatiotemporal trajectory to timeline

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟4 將TD'中的每一個元素進行初始化，令TD'=DSW;

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

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

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

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

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

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

步驟1 初始化;

步驟2 對每個Wi∈DSW 提取時間戳位于此區(qū)間的所有軌跡點TrPi;

步驟3 對TrPi中屬于同一條軌跡的空間點做去重操作;

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

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

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

3 基于時空熱點區(qū)域的移動模式挖掘

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

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

基于時空熱點區(qū)域的移動軌跡頻繁模式挖掘算法表述如下:

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

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

輸出:移動軌跡頻繁模式集合。

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

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

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

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

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

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

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

所用試驗設(shè)備為個人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。所用編程語言為Matlab 2010 b。

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

圖4 移動軌跡密集時間區(qū)間提取試驗結(jié)果Fig.4 Experiment of extracting intensive time interval

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

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

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

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

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

5 結(jié)束語

對隨機采樣條件下的移動軌跡模式挖掘問題進行了研究，針對隨機采樣移動軌跡數(shù)據(jù)在時間域密集數(shù)據(jù)區(qū)間與稀疏數(shù)據(jù)區(qū)間隨機且并存的特點，通過將三維時空軌跡投影轉(zhuǎn)換為一維時間數(shù)據(jù)，提出了一種基于聚類的密集時間區(qū)間檢測和時空熱點區(qū)域發(fā)現(xiàn)方法，進而以時空熱點區(qū)域為基礎(chǔ)對原始移動軌跡數(shù)據(jù)進行映射轉(zhuǎn)換，最后采用深度優(yōu)先搜索策略對轉(zhuǎn)換序列數(shù)據(jù)中的移動頻繁模式進行挖掘和發(fā)現(xià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］.中國計算機學會通訊，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.