軌跡模式探勘與應用之研究

Abstract

隨著行動裝置的普及，我們可以由多種的設備及來源收集使用者的軌跡資 料。由於這些軌跡資料中含有使用者的移動資訊，因此由這些資料中可以探勘使 用者的移動行為，此即為本篇論文中所提及之軌跡模式。這些模式在開發新的應 用或是增加既有的位置感知應用上都極具價值。在本篇論文中，我們提出了一連 串有關於軌跡模式探勘相關之演算法。我們首先提出如何大規模地收集使用者的 軌跡資料。緊接著，我們提出兩個探勘軌跡模式的演算法。最後，我們利用使用 者的軌跡模式來判斷使用者間的隱性社群關係。 在本篇論文的第一個主題，我們研究如何在由車輛所構成之感測網路中進行 大規模收集軌跡資料的方式。我們提出了一個架構MDC 來降低資料傳輸量以及 車輛的回報數目。在MDC 中，車輛利用模型來代表其感測到之讀數，並且利用 匯集之方式使得有相類似模型的車輛只需回傳一份至伺服器，因此可以在收集軌 跡資料時的資料傳輸量。 在本篇論文的第二個主題中，我們利用迴歸的方式自通聯記錄中探勘使用者 的軌跡模式。由於通聯記錄只能夠反應使用者部份的行為，因此在本主題中，我 們主要利用迴歸的方式自通聯記錄中復原使用者的軌跡模式。首先，我們先粹取 出具有相同移動行為的通聯記錄，並將具有時間空間相關性的通聯記錄群聚起 來。最後，使用者的移動模式便可以用數條迴歸曲線表示。 在本篇論文的第三個主題中，我們提出了利用軌跡中的線索(Clue) 探勘軌跡 模式的演算法。在實際的軌跡中，有許多因素會造成其無法完整表達使用者的移 動路徑。但是，縱使這些軌跡只能表達使用者部份的移動行為，但是我們依然可 利用這些軌跡所隱含的資訊來進行使用者移動行為之探勘。因此，我們首先提出 一利用兩軌跡中所含線索的多寡來衡量兩個軌跡相似度的方式，並利用這個相似 度將具有相同移動行為的軌跡群聚起來，最後再將每一群中的軌跡之時間空間資 訊匯集，推導出使用者的移動模式。 最後，我們利用使用者的軌跡模式來判斷使用者的隱性社群關係。我們可以 觀察出，有相同移動行為的使用者極有可能在位置感知服務上或是現實生活上有 所互動。因此，在這個主題中我們將判斷並比較使用者的軌跡模式，並將相同軌 跡模式的使用者視為是一社群。首先，我們先將使用者的軌跡模式建成一個樹狀 結構。利用Editing distance 的概念，我們設計出比較使用者軌跡模式的距離函數。利用此距離函數，我們便可以推得出使用者的社群關係。

With the pervasiveness of mobile devices, the location of users can be easily determined by either GPS devices or some positioning techniques. Moreover, wireless communication systems enable users to access various kinds of information from anywhere at any time. Nowadays, through smart phones or some portable devices, people could access location-based services or share their locations to their friends via social web sites, such as Google’s latitude service and Foursquare service. These phenomenons show that there will be an increasing amount of user trajectory data available. It is a challenge and interesting task to discover valuable knowledge. With knowledge mined, we could develop many novel applications from such a huge amount of user trajectory data. In this dissertation, we develop a series of research works for trajectory pattern mining and explore patterns mined for location-based social services. In our study, we present how to collect users’ trajectories first. Then, two kinds of mining algorithms are proposed. Finally, we develop a framework for mining location- based social community structures. We briefly introduce each work as follows: In the first work, we focused on the problem of data collection of trajectory data in a vehicular sensor network where every vehicles are equipped GPS and can communicate with each other in an ad-hoc manner. We proposed a frame-work MDC to reduce the amount of data transmission and the number of vehicles reporting their GPS data points. In MDC, model functions are derived to repre- sent the raw GPS data points such that only some coefficients that describe its movements are reported. An in-network aggregation mechanism determines a set of groups and for each group, only one vehicle needs to report traffic data, thereby further reducing the number of simultaneous connections. In the second work, we proposed a regression-based approach to mine user movement patterns from call detail records in a mobile computing system. Call detail records are viewed as random sample trajectory data, and user movement patterns are represented as movement functions. At first, the call detail records that capture frequent user movement behaviors are extracted. By exploring the spatiotemporal locality of movements, call detail records describing the similar behaviors are clustered. The movement functions can be represented by regression lines to best fit the location and time of call detail records. In the third work, we proposed an algorithm for discovering trajectory patterns by exploiting trajectory clues. In reality, there are many factors, such as sampling method, sampling frequency and device constraints, will affect the capability of original trajectory data capturing the actual movements. Even if trajectories can only reflect partial movements of a user, they reveal some trajectory clues about the moving behaviors hidden in trajectories. We first propose a clue-similarity to measure how much clue between two trajectories. Based on the clue-similarity, a graph-based clustering algorithm is proposed to group trajectories with similar moving behaviors into the same cluster. At last, for each group, the spatial and temporal information are aggregated into trajectory patterns. In the fourth work, we targeted at the problem of mining user communities in a location-based social network, where users in the same community have the similar movement behaviors. At the first, trajectory patterns of each user are orga- nized into a probabilistic suffix tree, which is viewed as a trajectory profile of each user. Inspired by the concept of the edit distance of two sequences, the distance function of two trees is proposed. Finally, in light of the distance of trees, a user communities in a location-based social network are found by clustering users with similar trajectory patterns.