基于MapReduce的用戶移動軌跡序列模式挖掘算法研究.pdf

1、近年來，移動通信技術和位置感知技術得以快速發(fā)展，具有位置感知功能的智能移動終端已在人們生活中得到普及，此外，各種基于位置服務的移動應用程序，如微博、Facebook、滴滴打車等軟件的流行，使得獲取精準海量的用戶軌跡數(shù)據(jù)成為可能。這些數(shù)以億計的用戶移動軌跡數(shù)據(jù)包括位置、時間、速度等基本信息，能夠真實有效的反映用戶的移動軌跡。而絕大部分用戶的移動行為往往具有一定的習慣和偏好，在時間和空間序列上呈現(xiàn)出一定的規(guī)律性。對這些軌跡數(shù)據(jù)通過特定的算法

2、進行挖掘，可以發(fā)現(xiàn)人們運動過程中存在的規(guī)律，找出那些有意義的、潛在的軌跡序列，即用戶移動軌跡模式。這些模式對于城市規(guī)劃、用戶群體分布研究、商業(yè)活動等領域能夠提供有力決策，具有重要的現(xiàn)實意義。
　　針對上述問題，本文對移動軌跡序列模式挖掘領域相關理論、算法進行了研究，首先，由于用戶移動軌跡原始數(shù)據(jù)具有不完整、含噪音和不一致的特點，對這些含有噪音的原始數(shù)據(jù)進行清洗、變換操作，從原始的GPS序列中提取出停留點序列，然后，提出了一種基于密

3、度的 CP-OPTICS聚類算法，算法首先將數(shù)據(jù)集合劃分為一定數(shù)量的網(wǎng)格單元，對劃分后的網(wǎng)格單元引入加權信息熵的概念，通過計算加權信息熵，自適應的計算每個網(wǎng)格單元的最小密度閾值。對滿足最小密度閾值的網(wǎng)格單元，提出了密集格的概念，用質心點代替網(wǎng)格數(shù)據(jù)點集的方法，對數(shù)據(jù)點進行壓縮。最后，利用原始的OPTICS算法輸出簇排序的可達圖，利用可達圖從停留點序列中提取出用戶重要地點集合。這些用戶重要地點集合將作為移動序列模式挖掘的數(shù)據(jù)來源。

4、　　其次，將原始的用戶移動軌跡序列與用戶重要地點集進行映射，轉化為布爾矩陣，并對傳統(tǒng)的關聯(lián)規(guī)則挖掘算法Apriori算法進行改進，提出了FMA_Mining序列模式挖掘算法，算法在矩陣映射過程中引入Flag標識，對于連續(xù)出現(xiàn)的項用Flag標識標明，簡化矩陣元素的讀取和列向量運算。針對數(shù)據(jù)密集型環(huán)境下數(shù)據(jù)規(guī)模較大的情況，算法引入了矩陣分割和并行化處理思想，利用MapReduce并行處理框架，在Hadoop平臺上實現(xiàn)了移動軌跡序列模式的挖掘