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

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

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

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

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