English  |  正體中文  |  简体中文  |  Items with full text/Total items : 49521/84656 (58%)
Visitors : 7584291      Online Users : 53
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/106873


    Title: 軌跡模式探勘及應用之研究
    A study on trajectory pattern mining and applications
    Authors: 洪智傑
    Contributors: 國立交通大學
    彭文志
    Date: 2011-07
    Issue Date: 2016-06-02 09:09:51 (UTC+8)
    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.
    Appears in Collections:[資訊工程學系暨研究所] 學位論文

    Files in This Item:

    File Description SizeFormat
    摘要.pdf3937KbAdobe PDF61View/Open
    目錄.pdf1410KbAdobe PDF20View/Open

    All items in 機構典藏 are protected by copyright, with all rights reserved.


    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback