許賢澤, 譚盛煌, 劉 靜, 施 元

(武漢大學(xué) 電子信息學(xué)院， 湖北 武漢 430072)

隨著移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展，智能手機(jī)已成為大眾的必備工具.數(shù)據(jù)顯示，2017年1～7月，我國(guó)智能手機(jī)的出貨量達(dá)2.66億部，智能手機(jī)用戶(hù)規(guī)模也已達(dá)到6.55億人，這些移動(dòng)設(shè)備每天產(chǎn)生海量的位置數(shù)據(jù)，通過(guò)這些位置數(shù)據(jù)對(duì)移動(dòng)用戶(hù)的軌跡預(yù)測(cè)已成為近年來(lái)的研究熱點(diǎn)之一.準(zhǔn)確的軌跡預(yù)測(cè)在導(dǎo)航[1]、疾病預(yù)防[2]和城市規(guī)劃[3-4]等諸多領(lǐng)域有著廣泛應(yīng)用.

當(dāng)前軌跡預(yù)測(cè)方法主要分為以下三種:

1) 基于時(shí)間序列模型的位置預(yù)測(cè)方法[5].這類(lèi)方法是通過(guò)對(duì)原有時(shí)間序列構(gòu)建線(xiàn)性或非線(xiàn)性數(shù)學(xué)模型，該方法假設(shè)移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡較為平穩(wěn)，移動(dòng)速度、方向不會(huì)產(chǎn)生較大變化.在真實(shí)的城市交通中路況較為復(fù)雜，移動(dòng)用戶(hù)并不能產(chǎn)生時(shí)間序列模型所要求的平穩(wěn)軌跡.

2) 基于機(jī)器學(xué)習(xí)的位置預(yù)測(cè)方法.該方法在目前位置預(yù)測(cè)中應(yīng)用最為廣泛，主要有Markov模型[6]、卡爾曼濾波模型[7]、貝葉斯模型[8]，其中以Markov模型應(yīng)用最多.Markov模型主要是根據(jù)歷史數(shù)據(jù)構(gòu)建狀態(tài)轉(zhuǎn)移矩陣，當(dāng)出現(xiàn)新用戶(hù)或出現(xiàn)數(shù)據(jù)缺失時(shí)，位置預(yù)測(cè)準(zhǔn)確性較低.

3) 基于頻繁模式挖掘FP-GROWTH算法挖掘運(yùn)動(dòng)對(duì)象運(yùn)動(dòng)模式的方法[9].該方法從歷史軌跡數(shù)據(jù)集中挖掘頻繁軌跡模式，然后與當(dāng)前路徑進(jìn)行匹配實(shí)現(xiàn)位置預(yù)測(cè).由于傳統(tǒng)的FP-GROWTH算法復(fù)雜度較高，無(wú)法處理大量的歷史軌跡數(shù)據(jù)集.本文采用了一種并行FP-GROWTH算法與相斥度計(jì)算結(jié)合展開(kāi)移動(dòng)用戶(hù)軌跡預(yù)測(cè)的方法，將傳統(tǒng)的FP-GROWTH算法分布到Spark并行計(jì)算框架上，從而解決了大量數(shù)據(jù)的挖掘，同時(shí)改進(jìn)了相似度計(jì)算方法，對(duì)缺失軌跡有更好的適用性.

1 問(wèn)題描述

現(xiàn)有一移動(dòng)用戶(hù)軌跡數(shù)據(jù)集和某移動(dòng)用戶(hù)的當(dāng)前軌跡，預(yù)測(cè)該用戶(hù)的短期軌跡.設(shè)數(shù)據(jù)集X={X1,X2,…,Xw}其中:Xi=(ui,ti,pi)，i=1,2,…,w.ui是用戶(hù)ID，ti是用戶(hù)在該位置的時(shí)間，pi為用戶(hù)所在位置的經(jīng)緯度.假設(shè)有一個(gè)移動(dòng)用戶(hù)的位置數(shù)據(jù)集，該數(shù)據(jù)集是一個(gè)時(shí)間序列，包含了用戶(hù)在一定時(shí)間段內(nèi)的位置數(shù)據(jù).首先對(duì)位置數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理，然后提取出用戶(hù)的軌跡集Tui={(ti,li),i=1,2,…,x}，時(shí)間序列tui=t1,t2,…,tx，位置序列Lui=l1,l2,…,lx，其中ui表示任意移動(dòng)用戶(hù).移動(dòng)用戶(hù)的位置預(yù)測(cè)問(wèn)題可以描述如下:設(shè)ui是某一研究用戶(hù)，已知該用戶(hù)的移動(dòng)軌跡集為T(mén)，預(yù)測(cè)出該用戶(hù)下一步地點(diǎn)lx+1.

2 基于Spark的FP-GROWTH算法

使用傳統(tǒng)的FP-GROWTH算法需要將所有的數(shù)據(jù)加載到單機(jī)內(nèi)存，隨著數(shù)據(jù)量的增大，F(xiàn)P-GROWHT算法構(gòu)建的FP-Tree的廣度、深度都會(huì)增大[10]，同時(shí)遞歸次數(shù)增加，導(dǎo)致挖掘效率變低.因此需要對(duì)原始的FP-GROWTH算法進(jìn)行改進(jìn)，利用分布式集群實(shí)現(xiàn)頻繁項(xiàng)挖掘[11].

2.1 基本概念

設(shè)A=(a1,a2,…,an)為一個(gè)集合，集合A中的元素稱(chēng)為項(xiàng)，集合A稱(chēng)為項(xiàng)集A或事務(wù)A.在本文中，集合A表示一條軌跡，ai表示軌跡A上的采樣點(diǎn).

1) 支持度:事務(wù)A在事務(wù)集合中出現(xiàn)的次數(shù)與事務(wù)集合的大小的比值.

2)k-項(xiàng)集:長(zhǎng)度為k的項(xiàng)集.

3) 1-項(xiàng)集的條件模式基:選擇其中一個(gè)1-項(xiàng)集ai，對(duì)FP-Tree中每個(gè)ai節(jié)點(diǎn)向上回溯至根節(jié)點(diǎn)所得到的路徑的集合，條件模式基可看成一個(gè)新的事務(wù)集合.

2.2 基于Spark的FP-GROWTH算法

首先對(duì)數(shù)據(jù)集進(jìn)行劃分，將分割數(shù)據(jù)集分布到集群的各個(gè)節(jié)點(diǎn)上分別進(jìn)行頻繁項(xiàng)集挖掘，最終將挖掘結(jié)果聚合到主節(jié)點(diǎn)上.

算法的實(shí)現(xiàn)主要包括四個(gè)部分:

1) 將數(shù)據(jù)集部署到分布式文件系統(tǒng)(Hadoop distributed file system，HDFS)上，掃描HDFS，并行計(jì)算各1-項(xiàng)集的支持度，將1-項(xiàng)集支持度計(jì)算結(jié)果聚合到主節(jié)點(diǎn)上，并根據(jù)支持度排序[11].

2) 修剪上述1-項(xiàng)集集合，刪除支持度小于所設(shè)閾值的1-項(xiàng)集，記該1-項(xiàng)集集合為H_list.

3) 依據(jù)H_list對(duì)數(shù)據(jù)集進(jìn)行劃分，由于條件模式基大小并不一致，為了在分布式集群上提高計(jì)算速度，需要進(jìn)行負(fù)載均衡處理[11].對(duì)于H_list中的一個(gè)1-項(xiàng)集H_list，i越小，H_list[i]所對(duì)應(yīng)的條件模式基所含事務(wù)更少，事務(wù)長(zhǎng)度更短，因此使用FP-GROWTH算法挖掘頻繁項(xiàng)時(shí)速度更高.對(duì)條件模式基的頻繁項(xiàng)集挖掘過(guò)程是一個(gè)對(duì)樹(shù)的遞歸操作，因此本文采用H_list[i]的序號(hào)與支持度的乘積估算條件模式基的負(fù)載.以負(fù)載為權(quán)重將劃分后的數(shù)據(jù)集分配到各個(gè)節(jié)點(diǎn)上.

4) 在各個(gè)節(jié)點(diǎn)上進(jìn)行頻繁模式挖掘[11]，最后將結(jié)果聚合到主節(jié)點(diǎn)上.

3 相斥度計(jì)算

本文針對(duì)基于同位序軌跡點(diǎn)歐式距離的軌跡相似度算法的不足[12]，提出一種基于計(jì)算當(dāng)前點(diǎn)到歷史軌跡距離加權(quán)和的相斥度(即兩條軌跡的相離程度)計(jì)算方法.

3.1 點(diǎn)到軌跡的距離

定義1點(diǎn)到軌跡的距離:已知某條軌跡數(shù)據(jù)序列l(wèi)={p1,p2,…,pm}和軌跡點(diǎn)qi，軌跡點(diǎn)qi到軌跡l的距離定義如下:

D(qi,l)=min(distance(qi,pjpj+1)).

其中distance(qi,pjpj+1)表示軌跡點(diǎn)qi到線(xiàn)段pjpj+1的距離，且1≤j≤m-1.

設(shè)存在軌跡序列l(wèi)1={p1,p2,…,pm}和l2={q1,q2,…,qn}，計(jì)算軌跡l2的上各點(diǎn)到軌跡l1的最小距離.計(jì)算l2上各軌跡點(diǎn)到軌跡序列l(wèi)1最短距離的過(guò)程中，精確求解需要計(jì)算qi到l2各軌跡段的距離.考慮到運(yùn)動(dòng)軌跡的漸變性，在計(jì)算上進(jìn)行一定改進(jìn).

通過(guò)數(shù)據(jù)預(yù)處理后，若軌跡l1與l2相似，l2上起始點(diǎn)q1到l1各軌跡段距離先減小后增大，取其中極小值為q1點(diǎn)到軌跡l1最小值.若求解得l2上一軌跡點(diǎn)qi到l1的距離為qi到軌跡段(pj,pj+1)的距離，計(jì)算l2中qi的下一個(gè)軌跡點(diǎn)qi+1到軌跡l1的距離，計(jì)算過(guò)程如下.

嘗試計(jì)算qi+1到(pk,pp+1),j≤k

3.2 軌跡相斥度

在用于預(yù)測(cè)的相似路徑中，越靠近當(dāng)前軌跡末端的點(diǎn)與預(yù)測(cè)點(diǎn)位擁有更高的相關(guān)性，對(duì)最終的預(yù)測(cè)結(jié)果影響越大[13]，因此對(duì)這些軌跡點(diǎn)賦予更高的權(quán)重，對(duì)相斥度作如下定義.

定義2軌跡相斥度:已知某條軌跡數(shù)據(jù)序列l(wèi)1={p1,p2,…,pm}和軌跡數(shù)據(jù)序列l(wèi)2={q1,q2,…,qn}，l1，l2軌跡相斥度定義為

其中wi表示軌跡點(diǎn)qi的權(quán)重.在相斥度計(jì)算中，設(shè)定一相斥度閾值threashold，當(dāng)計(jì)算過(guò)程中相斥度大于threashold，認(rèn)為l1和l2相斥，終止計(jì)算.

采用與被預(yù)測(cè)路徑相斥度最低的頻繁軌跡與被預(yù)測(cè)路徑匹配，完成用戶(hù)位置預(yù)測(cè).

4 實(shí)驗(yàn)結(jié)果及算法性能分析

4.1 實(shí)驗(yàn)數(shù)據(jù)及其預(yù)處理

本文選用了由微軟亞洲研究院發(fā)布的GeoLife GPS Trajectories數(shù)據(jù)集，該數(shù)據(jù)集由智能手機(jī)和其他包含有GPS的設(shè)備記錄而成，從2007年4月到2012年8月期間182個(gè)用戶(hù)的軌跡數(shù)據(jù)，包括經(jīng)度、緯度和海拔.該數(shù)據(jù)集總共包含17 621條軌跡數(shù)據(jù)，記錄總時(shí)長(zhǎng)超過(guò)48 000 h，總距離超過(guò)120萬(wàn)km.

由于采樣間隔比較密集，測(cè)量誤差對(duì)相鄰兩點(diǎn)之間的相對(duì)位置影響很大，因此本文根據(jù)原數(shù)據(jù)集的特點(diǎn)，對(duì)原始數(shù)據(jù)集進(jìn)行采樣，采樣頻率為10.結(jié)合百度地圖對(duì)數(shù)據(jù)進(jìn)行基于POI點(diǎn)的停留點(diǎn)檢測(cè)，用折中方法分割軌跡[14]，得到便于模式挖掘和相斥度計(jì)算的短序列.

式(7)中：ui為各面單元的軸向速度;為截面軸向平均速度;Ai為各面單元的面積。為便于與試驗(yàn)結(jié)果相對(duì)比，對(duì)0.15 m <0.45 m和0.15 m

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 Spark和MapReduce運(yùn)行效率對(duì)比

為驗(yàn)證基于Spark的FP-GROWTH 算法在大量數(shù)據(jù)下的可用性，本實(shí)驗(yàn)選取了不同的數(shù)據(jù)集，分別在5個(gè)節(jié)點(diǎn)的MapReduce以及Spark運(yùn)算框架上以FP-GROWTH算法進(jìn)行頻繁項(xiàng)挖掘，比較兩種運(yùn)算框架的運(yùn)算效率.

FP-GROWTH算法計(jì)算內(nèi)存開(kāi)銷(xiāo)較大，對(duì)于大型數(shù)據(jù)集，單機(jī)受內(nèi)存限制無(wú)法運(yùn)行.實(shí)驗(yàn)選取不同規(guī)模的數(shù)據(jù)集，通過(guò)合理的數(shù)據(jù)集分割，可以在不影響模式挖掘效果的前提下進(jìn)行分布式運(yùn)算[11].分別在Spark和MapReduce并行計(jì)算框架上進(jìn)行頻繁模式挖掘，實(shí)驗(yàn)結(jié)果如圖1所示.

圖1 Spark和MapReduce運(yùn)算框架下運(yùn)行時(shí)間對(duì)比

由圖1可知，Spark運(yùn)算框架相比MapReduce在不同的數(shù)據(jù)集大小下，運(yùn)行時(shí)間更短，MapReduce框架比Spark運(yùn)行時(shí)間增長(zhǎng)更快.這是因?yàn)镸apReduce從硬盤(pán)讀寫(xiě)數(shù)據(jù)，計(jì)算時(shí)在內(nèi)存中進(jìn)行存儲(chǔ)和運(yùn)算.Spark直接基于內(nèi)存處理，避免了與硬盤(pán)的IO傳輸.因此Spark運(yùn)算框架上的FP-GROWTH算法擁有更高的運(yùn)算效率.

4.2.2 軌跡預(yù)測(cè)算法性能對(duì)比

為驗(yàn)證模型的預(yù)測(cè)準(zhǔn)確性，對(duì)馬爾可夫模型、卡爾曼濾波模型及本文提出的基于模式挖掘與路徑匹配的方法進(jìn)行對(duì)比.將數(shù)據(jù)集隨機(jī)分成20份，其中一份作為測(cè)試數(shù)據(jù)集用于軌跡預(yù)測(cè)，另外19份用于訓(xùn)練模型，每個(gè)實(shí)驗(yàn)采用交叉驗(yàn)證的方式進(jìn)行20次，取平均結(jié)果作為最終預(yù)測(cè)值.

定義3預(yù)測(cè)精度[13]:在軌跡預(yù)測(cè)過(guò)程中，預(yù)測(cè)結(jié)果正確的概率.例如，對(duì)于n個(gè)需要預(yù)測(cè)位置，設(shè)定一個(gè)預(yù)測(cè)誤差閾值，預(yù)測(cè)誤差在閾值以?xún)?nèi)認(rèn)為預(yù)測(cè)正確，有t個(gè)位置預(yù)測(cè)正確，則該預(yù)測(cè)結(jié)果的預(yù)測(cè)精度為Pa=t/n.

本文采用預(yù)測(cè)精度作為軌跡預(yù)測(cè)準(zhǔn)確性的評(píng)價(jià)標(biāo)準(zhǔn).分別采用馬爾可夫模型、卡爾曼濾波模型以及本文的相斥度預(yù)測(cè)算法進(jìn)行預(yù)測(cè)精度對(duì)比.

實(shí)驗(yàn)采用馬爾可夫模型、卡爾曼濾波模型以及本文的相斥度預(yù)測(cè)算法進(jìn)行不同長(zhǎng)度軌跡的單步位置預(yù)測(cè)，即預(yù)測(cè)用戶(hù)的下一個(gè)感興趣的位置.圖2為3種預(yù)測(cè)方法對(duì)不同長(zhǎng)度軌跡單步預(yù)測(cè)結(jié)果.橫軸表示當(dāng)前軌跡長(zhǎng)度，縱軸表示預(yù)測(cè)精度.

圖2 不同長(zhǎng)度軌跡單步位置預(yù)測(cè)精度對(duì)比

從圖2可以看出，隨著軌跡長(zhǎng)度增加，三種預(yù)測(cè)方法預(yù)測(cè)精度保持上升，在軌跡長(zhǎng)度為5時(shí)逐漸平穩(wěn).保持平穩(wěn)之后，基于相斥度的軌跡預(yù)測(cè)算法相比于馬爾可夫模型和卡爾曼濾波模型預(yù)測(cè)精度分別提升6.93%和6.98%.

在進(jìn)行位置預(yù)測(cè)時(shí)，多步預(yù)測(cè)也是檢驗(yàn)?zāi)Ｐ皖A(yù)測(cè)性能的指標(biāo)之一，多步預(yù)測(cè)即連續(xù)預(yù)測(cè)多個(gè)點(diǎn)的位置.本文根據(jù)不同長(zhǎng)度軌跡的單步預(yù)測(cè)實(shí)驗(yàn)的結(jié)果，設(shè)置待預(yù)測(cè)軌跡長(zhǎng)度為5.采用三種方法對(duì)測(cè)試集中6個(gè)連續(xù)位置進(jìn)行預(yù)測(cè)，計(jì)算不同位置平均預(yù)測(cè)精度，如圖3所示.

圖3 不同點(diǎn)位的預(yù)測(cè)精度對(duì)比

從圖3可以看出，三種方法在步長(zhǎng)增加時(shí)，預(yù)測(cè)精度有明顯下降.相比于馬爾可夫模型和卡爾曼濾波模型，本文使用的相斥度預(yù)測(cè)算法對(duì)不同步長(zhǎng)的預(yù)測(cè)精度在各點(diǎn)平均預(yù)測(cè)精度提升分別為7.03%和7.35%.

從上面兩個(gè)實(shí)驗(yàn)可以看出，本文采用的相斥度預(yù)測(cè)算法預(yù)測(cè)精度優(yōu)于馬爾可夫模型和卡爾曼濾波模型.原因在于馬爾可夫模型是概率統(tǒng)計(jì)模型，對(duì)于運(yùn)動(dòng)狀態(tài)不確定性較高的對(duì)象預(yù)測(cè)精度不高.卡爾曼濾波主要適用于線(xiàn)性離散系統(tǒng)，對(duì)軌跡點(diǎn)數(shù)據(jù)缺失情況適應(yīng)性不佳.

5 結(jié) 論

1) 本文提出了一種基于并行模式挖掘和路徑匹配的移動(dòng)用戶(hù)位置預(yù)測(cè)方法.對(duì)FP-GROWTH算法作了并行化處理，實(shí)現(xiàn)了對(duì)大量用戶(hù)的移動(dòng)模式提取.采用基于相斥度的軌跡預(yù)測(cè)算法進(jìn)行用戶(hù)位置預(yù)測(cè)，并與馬爾可夫模型和卡爾曼濾波模型進(jìn)行比較分析.

2) 使用分布式平臺(tái)可以完成大規(guī)模的模式挖掘，且Spark平臺(tái)相比MapReduce計(jì)算效率更高.

3) 相比于馬爾可夫模型和卡爾曼濾波模型，相斥度預(yù)測(cè)算法在單步預(yù)測(cè)和多步預(yù)測(cè)中預(yù)測(cè)更為精準(zhǔn).