數據挖掘是一個熱門的專業，而時空軌跡的挖掘作為其中一個重要的分支有著舉足輕重的地位。時空軌跡是移動對象的位置和時間的記錄序列。作為一種重要的時空對象數據類型，時空軌跡的套用涵蓋了人類行為、交通物流等諸多方面。通過對各種時空軌跡數據進行分析，可以得到時空軌跡數據中的相似性異常特徵，有助於發現其中有意義的軌跡模式。伴隨模式是時空軌跡模式中的一種，在交通管理，資源分配等領域有著重要的套用。
基本介紹
- 中文名：時空軌跡伴隨模式
- 性質：專業術語
- 所屬領域：天體學、數據科學
- 基本釋義：移動對象的位置和時間的記錄序列
時空軌跡的定義,伴隨模式的定義,研究發展,展望,
時空軌跡的定義
時空軌跡是移動對象的位置和時間的記錄序列。簡單來說，時空軌跡是時間到空間的映射，假設由一個以時間為自變數的連續函式o表示，當給定某一個時刻t(t∈R)時，通過該函式可以得到t時刻該對象所處的d維空間R (一般是二維或者三維空間)中的位置。
從定義中可以看出時空軌跡是連續的，但由於硬體的限制及其他原因，通常時空軌跡的採樣點是離散的，因而通常時空軌跡也是以離散的方式表示。在二維空間中，以T={(x1,y1,t1), (x2,y2,t2)… (xn,yn,tn)}為例，式中T代表一條軌跡，序列中每個(d+1)元組(xn,yn,tn)表示對象在tn時刻一個採樣點，(xn,yn)表示對象在2維空間中的位置。
伴隨模式的定義
直觀地講，時空軌跡的伴隨模式指一群移動(moving objects)在一個限定的範圍內，一起移動至少w時長，這樣的一種運動模式就叫伴隨模式。例如，從同一個學校放學後回到同一個小區的學生，一起上下班的同事等，這些都是伴隨模式在現實中的一些例子。
定義：至少m個密度相連的移動對象，在一起運動至少w時長，其中m和w是用戶自定義的，且w>1,m>1，這群對象形成的軌跡模式就叫時空軌跡的伴隨模式。
研究發展
2002年【AnalyzingRelative Motion within Groups of Trackable Moving Point Objects】這篇文章中提出了Group Concurrence的概念，這可以認為是軌跡伴隨模式的第一次提出。文中給出了group concurrence的定義：一群移動對象，在一段時間上有相同的或者相似的運動屬性（運動方向）。
從2003年到2005年，在2002年這篇文章提出的REMO的概念基礎上，【Finding REMO—detecting relative motion patterns in geospatial lifelines】和【Discovering relative motion patterns in groups of moving point objects】等文章在多種場景之下對REMO模式進行了挖掘。該階段可以看作是伴隨模式發展的起步階段。不過在2005年【On discovering moving clusters in spatio-temporal data】這篇文章中moving cluster的提出引入了密度相連的概念，為挖掘伴隨模式提供了新的方法。
2006年到2007年學術界提出了一些新的算法來挖掘伴隨模式，但並沒有對伴隨模式的發展起到很好的推動作用，主要是算法效率比較低等原因。
2008年到2010年是伴隨模式的大發展時期，韓家煒 、周曉方、鄭宇、鄭凱以及國外的一些人士，在這段時期提出了convoy（參見【Convoy queries in spatio-temporal databases】），dynamic convoy，evolving convoy（參見【Discovery of evolving convoys】）以及swarm（參見【Swarm: Mining relaxed temporal moving object clusters】）等模式的概念，極大地豐富了伴隨模式的研究內容。這個時期提出的很多算法都考慮了實際情況中採樣點丟失以及降低計算量等因素，為更快地挖掘汽車流，人群移動以及動物遷徙等伴隨模式。
2012年，在【On Discovery of Traveling Companions from Streaming Trajectories】這篇文章中，Lu-An Tang, Yu Zheng, Jing Yuan, Jiawei Han等人提出了發現travelling companion模式，文章中伴隨模式的定義並沒有發生新的變化，不過他們開創性地提出了travelling buddy這一新的數據結構。以往的時空軌跡研究時都要保存每個採樣點的坐標信息，採樣時間等信息，但travelling buddy數據結構只是存儲各對象之間的關係，比如是否屬於同一個cluster等，極大地減少了計算量，為伴隨模式的發展注入了新的血液。
展望
上文中提出的各種挖掘時空軌跡伴隨模式的主要是對離線數據進行挖掘，在大數據，雲計算的時代，不僅要應對大數據，更要能實時處理數據輸出結果。同時，如果能將算法進行並行化那將是如虎添翼。希望各位做時空軌跡挖掘的同行再接再厲！
