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

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

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

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

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