王瑩，蘇壯

（1.北京郵電大學(xué)信息與通信工程學(xué)院，北京 100876；2.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100876）

1 引言

隨著移動(dòng)互聯(lián)網(wǎng)以及物聯(lián)網(wǎng)、車聯(lián)網(wǎng)的快速發(fā)展，終端設(shè)備正在急劇增加，無(wú)處不在的傳感設(shè)備和智能設(shè)備產(chǎn)生了海量數(shù)據(jù)，包括天氣狀況、交通狀況、地理位置、社交數(shù)據(jù)等[1]。與此同時(shí)，基于位置的服務(wù)也日益受到關(guān)注，收集用戶的地理位置信息，可以更好地鎖定用戶并推出針對(duì)性服務(wù)。面對(duì)智慧城市帶來(lái)的發(fā)展機(jī)遇，挖掘這些數(shù)據(jù)背后的規(guī)律能夠解決眾多問(wèn)題。例如，在無(wú)線網(wǎng)絡(luò)中，車輛、行人等個(gè)體的移動(dòng)性引起小區(qū)的頻繁切換和資源分配，由此導(dǎo)致的切換時(shí)延嚴(yán)重影響了用戶對(duì)時(shí)延敏感型業(yè)務(wù)的體驗(yàn)。因此，為了更加充分合理地利用無(wú)線資源，學(xué)者們?cè)谝苿?dòng)管理方面進(jìn)行了很多探索。眾所周知，人類傾向于具有相似模式的循環(huán)行為[2-3]，這使從個(gè)體之前的歷史位置信息中預(yù)測(cè)個(gè)體的移動(dòng)成為可能。一旦移動(dòng)被預(yù)測(cè)，就能獲取用戶在特定時(shí)間的位置，進(jìn)而規(guī)劃資源或者提供定制服務(wù)。

目前，移動(dòng)預(yù)測(cè)在眾多場(chǎng)景中被提出，包括旅游導(dǎo)航、交通控制、車聯(lián)網(wǎng)和設(shè)備到設(shè)備（D2D,device-to-device）等。其中，在旅游導(dǎo)航中，通過(guò)預(yù)測(cè)人群的移動(dòng)模式，對(duì)景點(diǎn)進(jìn)行推薦，避免景區(qū)人群分布不均衡，能顯著提高用戶的游覽體驗(yàn)。在交通控制中，預(yù)測(cè)車輛的移動(dòng)規(guī)律，對(duì)車輛行駛路線進(jìn)行規(guī)劃，能夠有效避免交通堵塞。在D2D 通信中，設(shè)備通過(guò)廣播獲取當(dāng)前位置的鄰近設(shè)備，并從中選取某個(gè)設(shè)備作為通信節(jié)點(diǎn)[4]，但由于節(jié)點(diǎn)的移動(dòng)性，網(wǎng)絡(luò)拓?fù)涫欠浅２环€(wěn)定的，雙方脫離通信范圍就會(huì)中斷連接；如果預(yù)測(cè)到每個(gè)設(shè)備的移動(dòng)方向，就能夠選取更穩(wěn)定的拓?fù)涔?jié)點(diǎn)，提高通信連接的頑健性和傳輸速率。在無(wú)線網(wǎng)絡(luò)移動(dòng)管理中，對(duì)終端進(jìn)行移動(dòng)預(yù)測(cè)，并在切換到下一接入節(jié)點(diǎn)前預(yù)留通信資源，能夠降低資源調(diào)度的時(shí)延，提高時(shí)延敏感型業(yè)務(wù)的體驗(yàn)質(zhì)量。

此外，在無(wú)線傳感網(wǎng)絡(luò)（WSN,wireless sensor network）中，移動(dòng)傳感節(jié)點(diǎn)收集數(shù)據(jù)并發(fā)送到基站[5]，當(dāng)基站通過(guò)定向天線與移動(dòng)節(jié)點(diǎn)通信時(shí)，定向傳輸將信號(hào)強(qiáng)度集中在主瓣方向上，形成指向接收機(jī)方向的定向波束，能夠提升通信容量并降低設(shè)備能耗，因此，預(yù)測(cè)移動(dòng)傳感節(jié)點(diǎn)的位置并和基站保持定向傳輸能夠提供更高質(zhì)量的數(shù)據(jù)服務(wù)。在車載網(wǎng)中，預(yù)測(cè)車輛的移動(dòng)，并將車輛請(qǐng)求的內(nèi)容預(yù)先緩存到即將接入的Wi-Fi 節(jié)點(diǎn)，在切換到該接入點(diǎn)后能夠迅速獲取數(shù)據(jù)，有效降低內(nèi)容獲取的時(shí)延[6]?？偠灾?，移動(dòng)預(yù)測(cè)的應(yīng)用場(chǎng)景十分廣泛，因此對(duì)移動(dòng)預(yù)測(cè)的研究是十分有價(jià)值的。

本文著重總結(jié)了移動(dòng)預(yù)測(cè)的特征提取以及目前主流的移動(dòng)預(yù)測(cè)方法，并結(jié)合無(wú)線網(wǎng)絡(luò)場(chǎng)景分析了各類方法在不同場(chǎng)景的適用性。無(wú)線網(wǎng)絡(luò)有多種結(jié)構(gòu)和技術(shù)，包括LTE（long term evolution）、超密集組網(wǎng)（UDN,ultra dense network）、Wi-Fi、車載自組網(wǎng)（VANET,vehicle ad hoc network）等，這些網(wǎng)絡(luò)在覆蓋范圍、規(guī)模、部署密度、穩(wěn)定性等方面存在差異，因此在不同的場(chǎng)景中預(yù)測(cè)算法的適用性不同。最后分析了其他因素對(duì)移動(dòng)預(yù)測(cè)的影響，并指出了未來(lái)的工作和挑戰(zhàn)。

2 移動(dòng)數(shù)據(jù)

移動(dòng)預(yù)測(cè)所需的數(shù)據(jù)主要來(lái)自無(wú)線網(wǎng)絡(luò)（GSM、Wi-Fi）中的日志、GPS 采樣數(shù)據(jù)以及終端APP 簽到信息。GSM 日志記錄了用戶在不同小區(qū)的接入記錄、通話記錄等，通過(guò)蜂窩定位技術(shù)能夠映射為相應(yīng)的位置信息，包括＜基站ID，終端ID，時(shí)間戳＞等信息。Wi-Fi 日志與之類似，記錄了用戶訪問(wèn)節(jié)點(diǎn)的接入歷史、接收信號(hào)強(qiáng)度信息（RSSI,received signal strength information）等，通過(guò)室內(nèi)定位技術(shù)能夠映射為相應(yīng)的位置信息，包括＜AP（access point），終端ID，RSSI，時(shí)間戳＞等信息。GPS 數(shù)據(jù)是目前移動(dòng)預(yù)測(cè)最常用的數(shù)據(jù)，一方面，由于智能移動(dòng)終端能夠方便地獲取GPS 信息，包括終端的經(jīng)緯度和時(shí)間戳；另一方面，GPS 精確地記錄了終端的移動(dòng)軌跡，其軌跡可以由坐標(biāo)點(diǎn)序列精確地描述，因此包含更加豐富的信息，能夠更準(zhǔn)確地提取移動(dòng)模式。但是GPS 數(shù)據(jù)集通常較大，處理復(fù)雜度較高，并且純粹的經(jīng)緯度坐標(biāo)缺乏位置含義，一般根據(jù)預(yù)測(cè)模型的需要，對(duì)數(shù)據(jù)進(jìn)行特征工程處理，才能用于模式提取和移動(dòng)預(yù)測(cè)。APP 簽到數(shù)據(jù)是通過(guò)智能終端的APP 收集的，例如用戶通過(guò)發(fā)布社交動(dòng)態(tài)、團(tuán)購(gòu)、攝影等隱含位置信息的方式，獲取操作APP 時(shí)產(chǎn)生的簽到記錄。

4 種數(shù)據(jù)對(duì)比及部分開(kāi)源數(shù)據(jù)集總結(jié)如表1 所示。其中，通過(guò)GPS 采樣的數(shù)據(jù)集GeoLife Dataset來(lái)自微軟GeoLife 項(xiàng)目。該項(xiàng)目從2007 年4 月到2012 年8 月收集了182 個(gè)用戶的軌跡數(shù)據(jù)。這些數(shù)據(jù)包含了一系列以時(shí)間為序的點(diǎn)，每一個(gè)點(diǎn)包含＜經(jīng)度，緯度，海拔，時(shí)間戳＞等信息，共計(jì)17 621 條移動(dòng)軌跡，總距離120 多萬(wàn)千米，總時(shí)間48 000 多小時(shí)。通過(guò)Wi-Fi 采樣的數(shù)據(jù)集Dartmouth Campus Dataset[7]來(lái)自美國(guó)達(dá)特茅斯學(xué)院數(shù)千用戶為期3 年的校園Wi-Fi 接入記錄，該Wi-Fi 網(wǎng)絡(luò)包含了近450個(gè)接入點(diǎn)，有大量的接入點(diǎn)切換記錄。通過(guò)GSM采樣的數(shù)據(jù)集Rice Context Dataset[8]來(lái)自Ahmad等獲取的基站日志，該日志包含了10 個(gè)手機(jī)用戶為期近2 個(gè)月的基站接入記錄，每條記錄包含基站每30 s 或60 s 采集一次的＜基站ID，信號(hào)強(qiáng)度，信道＞等信息。通過(guò)APP 簽到采樣的數(shù)據(jù)集Gowalla Dataset 來(lái)自Gowalla 的基于位置服務(wù)的社交網(wǎng)絡(luò)簽到數(shù)據(jù)，該數(shù)據(jù)集包含了近20 萬(wàn)用戶近6 個(gè)月的600 多萬(wàn)條簽到記錄，每條記錄包含＜用戶ID，時(shí)間戳，經(jīng)度，緯度，位置ID＞等豐富的信息。此外，研究者也可以根據(jù)條件自主獲取符合研究要求的數(shù)據(jù)樣本。

3 移動(dòng)軌跡處理

移動(dòng)預(yù)測(cè)首先要對(duì)移動(dòng)軌跡進(jìn)行處理。軌跡是由個(gè)體的移動(dòng)形成的按時(shí)間連續(xù)的位置序列。軌跡的2 個(gè)要素分別是空間特征和時(shí)序特征。空間特征是在軌跡序列中元素所代表的位置含義，決定了移動(dòng)預(yù)測(cè)的精度，同時(shí)能夠反映個(gè)體的移動(dòng)模式所具有的實(shí)際意義。通過(guò)對(duì)原始數(shù)據(jù)的處理得到有意義的軌跡序列，再結(jié)合適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)能夠提高預(yù)測(cè)的性能。時(shí)序特征由采樣方式?jīng)Q定，分為3 種：基于時(shí)間的采樣方式、基于位置的采樣方式和基于事件的采樣方式。

3.1 空間特征

原始軌跡序列，如GPS 坐標(biāo)序列，并不建議直接用來(lái)進(jìn)行位置預(yù)測(cè)，因?yàn)轭A(yù)測(cè)的準(zhǔn)確度較低，因此需要通過(guò)聚集、抽象來(lái)提取更高層次的空間特征。本文將空間特征劃分為3 類：偏好區(qū)域的空間特征、偏好語(yǔ)義的空間特征和偏好路徑的空間特征。

1)偏好區(qū)域的空間特征

偏好區(qū)域的空間特征表示區(qū)域性的空間位置，如“時(shí)刻T離開(kāi)區(qū)域A，時(shí)刻T+1 到達(dá)區(qū)域B”，反映了簡(jiǎn)化的移動(dòng)過(guò)程，其區(qū)域的粒度影響預(yù)測(cè)的精度。每個(gè)空間位置的定義往往與場(chǎng)景相關(guān)。常用的有路網(wǎng)模型和小區(qū)模型。

路網(wǎng)模型將平面劃分為N×N個(gè)網(wǎng)格狀區(qū)域，對(duì)每個(gè)網(wǎng)格進(jìn)行編號(hào)，用戶所處的網(wǎng)格就是該時(shí)刻用戶的位置區(qū)域，如圖1(a)所示。一種典型的路網(wǎng)模型——馬里德網(wǎng)格模型，是在城鎮(zhèn)通過(guò)橫縱交錯(cuò)的道路將平面劃分為網(wǎng)格狀[9]，規(guī)定行人和車輛在道路上移動(dòng)。在路網(wǎng)模型中，Wi-Fi 接入點(diǎn)或基站一般通過(guò)泊松分布分散在地圖上。

小區(qū)模型的劃分粒度一般和無(wú)線網(wǎng)絡(luò)的具體類型有關(guān)，LTE 網(wǎng)絡(luò)的基站覆蓋較廣，小區(qū)數(shù)目較少，位置狀態(tài)也少，因此復(fù)雜度較低；而UDN 的微基站和Wi-Fi 的接入點(diǎn)十分密集，狀態(tài)數(shù)多，復(fù)雜度高[10]，如圖1(b)所示。

偏好區(qū)域的空間特征將地圖劃分為有限個(gè)區(qū)域，對(duì)于每一個(gè)用戶，其位置狀態(tài)即為對(duì)應(yīng)的區(qū)域編號(hào)，用戶在下一時(shí)隙將要到達(dá)的區(qū)域就是要預(yù)測(cè)的位置，這個(gè)區(qū)域可能是用戶當(dāng)前的區(qū)域，也可能是其他區(qū)域。 通過(guò)區(qū)域特征構(gòu)造的軌跡序列為{r1,r2,…,ri,…,rn}，其中ri表示第i次采樣用戶所在的區(qū)域ID。

2)偏好語(yǔ)義的空間特征

偏好語(yǔ)義的空間特征表示有地理意義的空間位置，如“時(shí)刻T到達(dá)餐廳，時(shí)刻T+1 到達(dá)學(xué)?！?，反映了個(gè)體的移動(dòng)意圖，是移動(dòng)信息服務(wù)的起始點(diǎn)。每個(gè)地理位置的定義都與生活模式相關(guān)，典型的有興趣點(diǎn)（POI,point of interest）模型和地標(biāo)模型。

POI 模型[11]是個(gè)體在移動(dòng)過(guò)程中有偏好的移動(dòng)行為。在眾多位置中，有一些是個(gè)體頻繁訪問(wèn)的或長(zhǎng)久駐留的，而有一些是偶爾訪問(wèn)的。其中頻繁訪問(wèn)的位置定義為POI，是用戶位置的狀態(tài)，例如家、工作樓以及健身房等。POI 的提取通常通過(guò)GPS數(shù)據(jù)進(jìn)行聚類得到，如圖1(c)所示。以用戶的興趣點(diǎn)為空間特征能提高對(duì)個(gè)體移動(dòng)模式的理解，不過(guò)也存在對(duì)偶爾訪問(wèn)，甚至從未訪問(wèn)的新穎位置的不可達(dá)問(wèn)題，預(yù)測(cè)被局限在少數(shù)高頻訪問(wèn)的位置。

地標(biāo)模型將城市版圖通過(guò)標(biāo)志性地理位置表示，這些地標(biāo)包括個(gè)體已經(jīng)訪問(wèn)或者未曾訪問(wèn)的位置。相比POI 模型，地標(biāo)模型在語(yǔ)義庫(kù)中有更豐富的語(yǔ)料，但同時(shí)預(yù)測(cè)的維度也更高，如圖1(d)所示。通過(guò)區(qū)域特征構(gòu)造的軌跡序列為 {loc1,loc2,…,loci,…,locn}，其中l(wèi)oci表示第i次采樣時(shí)用戶所在的地標(biāo)ID。

表1 4 種常用移動(dòng)預(yù)測(cè)數(shù)據(jù)源對(duì)比

圖1 空間特征示意

3)偏好路徑的空間特征

偏好路徑的空間特征表示移動(dòng)行為中帶有過(guò)程性的特征，表現(xiàn)為相對(duì)穩(wěn)定的周期性重復(fù)的軌跡，如“時(shí)刻T到時(shí)刻T+1 經(jīng)過(guò)學(xué)院路”，可通過(guò)GPS 傳感器獲取軌跡細(xì)節(jié)，反映了個(gè)體移動(dòng)的典型軌跡。

在路網(wǎng)模型、POI 模型等空間特征中，移動(dòng)預(yù)測(cè)將簡(jiǎn)化的位置作為預(yù)測(cè)的原子狀態(tài)，將個(gè)體連續(xù)的移動(dòng)路徑抽象為在不同的位置間的轉(zhuǎn)移，其抽象的粒度影響了預(yù)測(cè)空間的維度，粒度過(guò)大，雖然維度會(huì)降低，但是預(yù)測(cè)的精度也會(huì)降低而失去應(yīng)用價(jià)值。相比而言，通過(guò)路徑將軌跡樸素地表示[12]，能夠近似描述個(gè)體的移動(dòng)過(guò)程，達(dá)到路徑細(xì)節(jié)的存儲(chǔ)和復(fù)現(xiàn)。路徑概率樹(shù)[13]就是基于路徑語(yǔ)義構(gòu)造的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行移動(dòng)模式提取和預(yù)測(cè)。如圖2 所示，移動(dòng)軌跡被分割成多段路徑。用戶甲的軌跡序列為 {p1,p2,p4}，用戶乙的軌跡序列為{p3,p4}。

圖2 路徑特征示意

3 種空間特征各有利弊。路網(wǎng)模型和小區(qū)模型數(shù)據(jù)處理簡(jiǎn)單，原始軌跡數(shù)據(jù)映射到該模型只需簡(jiǎn)單的距離測(cè)量，并且模型粒度容易調(diào)控，只需對(duì)網(wǎng)格數(shù)目調(diào)整即可，但是缺乏對(duì)個(gè)體移動(dòng)規(guī)律的理解；POI 模型和地標(biāo)模型便于理解個(gè)體的移動(dòng)規(guī)律，但是預(yù)處理復(fù)雜，對(duì)駐留點(diǎn)的聚類復(fù)雜度高，并且忽視位置轉(zhuǎn)移之間的具體移動(dòng)過(guò)程；路徑特征的預(yù)處理更加復(fù)雜，不僅要對(duì)駐留點(diǎn)、交叉點(diǎn)進(jìn)行聚類和提取，還要進(jìn)行冗余路徑清洗和相似路徑合并，抽象出典型的路徑特征，但該特征包含豐富的移動(dòng)細(xì)節(jié)，適用于各種需要移動(dòng)預(yù)測(cè)的場(chǎng)景。

采用何種空間特征，需要由具體的應(yīng)用需求決定，例如在蜂窩網(wǎng)小區(qū)切換中，只需要預(yù)測(cè)用戶何時(shí)到達(dá)下一小區(qū)的覆蓋范圍，此時(shí)使用POI空間特征只會(huì)增加復(fù)雜度，而不會(huì)明顯提高準(zhǔn)確性和實(shí)用性。

3.2 時(shí)序特征

通過(guò)定位設(shè)備所收集的移動(dòng)軌跡數(shù)據(jù)并非都是有價(jià)值的，過(guò)于密集或過(guò)于稀疏都會(huì)降低預(yù)測(cè)系統(tǒng)的性能，同時(shí)還要保證位置的特定時(shí)序以適應(yīng)所應(yīng)用的場(chǎng)景。因此要根據(jù)模型需要對(duì)數(shù)據(jù)進(jìn)行采樣構(gòu)成特定時(shí)序的軌跡序列。采樣方式有3 種[14]：基于時(shí)間的軌跡采樣、基于位置的軌跡采樣和基于事件的軌跡采樣。

1)基于時(shí)間的軌跡采樣

軌跡數(shù)據(jù)通過(guò)等時(shí)間間隔采樣收集。例如GPS數(shù)據(jù)，目前移動(dòng)終端大多都有GPS 傳感器，能夠等間隔5 s 獲?。冀?jīng)度，緯度，時(shí)間戳＞等定位信息，研究者也可以設(shè)置更大的時(shí)間間隔。

2)基于位置的軌跡采樣

當(dāng)?shù)乩砦恢冒l(fā)生改變時(shí)，將位置樣本加入軌跡序列。例如Wi-Fi 接入點(diǎn)切換時(shí)和基站切換時(shí)的小區(qū)位置，以及經(jīng)過(guò)數(shù)據(jù)清洗和路徑提取后，路徑發(fā)生轉(zhuǎn)移時(shí)的路徑位置。

3)基于事件的軌跡采樣

當(dāng)事件發(fā)生改變時(shí)，將位置加入軌跡序列，如使用智能終端發(fā)布社交動(dòng)態(tài)、購(gòu)買一張電影票或者餐票、登錄購(gòu)物商城等。通常由智能終端的APP 在使用過(guò)程中產(chǎn)生，常用的有社交網(wǎng)絡(luò)的簽到數(shù)據(jù)?；谑录蓸右蕾囉谥悄芙K端的使用動(dòng)作，且記錄的用戶行為并不完整。

以圖1(a)網(wǎng)格中的移動(dòng)軌跡為例，其采樣的數(shù)據(jù)空間如圖3 所示。

圖3 基于時(shí)間和位置的軌跡采樣

4 移動(dòng)預(yù)測(cè)模型

移動(dòng)預(yù)測(cè)主要解決2 個(gè)問(wèn)題：個(gè)體在何時(shí)到達(dá)下一個(gè)位置以及個(gè)體的下一個(gè)位置是何處。前者要預(yù)測(cè)的是個(gè)體在一個(gè)地點(diǎn)的到達(dá)時(shí)間和駐留時(shí)間，是基于時(shí)間序列的移動(dòng)預(yù)測(cè)；后者要預(yù)測(cè)的是個(gè)體的下一個(gè)駐留地點(diǎn)，是基于位置序列的移動(dòng)預(yù)測(cè)。如果同時(shí)兼顧二者，由于個(gè)體的移動(dòng)在時(shí)間維度和空間維度都有很大的隨機(jī)性，目前還很難做到較高的預(yù)測(cè)準(zhǔn)確度。

隨著人工智能和大數(shù)據(jù)的發(fā)展，一些新的預(yù)測(cè)模型在移動(dòng)預(yù)測(cè)上產(chǎn)生良好的效果。因此本文通過(guò)數(shù)學(xué)方法對(duì)移動(dòng)預(yù)測(cè)模型進(jìn)行分類，將預(yù)測(cè)方法分為3 類：基于概率統(tǒng)計(jì)模型的移動(dòng)預(yù)測(cè)、基于判別模型的移動(dòng)預(yù)測(cè)和基于頻繁模式挖掘的移動(dòng)預(yù)測(cè)。

4.1 基于概率統(tǒng)計(jì)模型的移動(dòng)預(yù)測(cè)

基于概率統(tǒng)計(jì)的機(jī)器學(xué)習(xí)算法在處理大規(guī)模樣本分類和線性系統(tǒng)學(xué)習(xí)中有高效和靈活的優(yōu)點(diǎn)。常用的有馬爾可夫模型（MM,Markov model）、隱馬爾可夫模型（HMM,hidden Markov model）、貝葉斯模型等，通過(guò)計(jì)算聯(lián)合概率預(yù)測(cè)可能的位置。

4.1.1 基于馬爾可夫模型的移動(dòng)預(yù)測(cè)

馬爾可夫模型根據(jù)樣本數(shù)據(jù)計(jì)算各個(gè)狀態(tài)的轉(zhuǎn)移概率，建立馬爾可夫鏈，通過(guò)初始時(shí)刻位置狀態(tài)和狀態(tài)轉(zhuǎn)移概率矩陣，計(jì)算未來(lái)時(shí)刻位置的概率并進(jìn)行預(yù)測(cè)。馬爾可夫鏈?zhǔn)蔷哂旭R爾可夫性的隨機(jī)變量序列，變量的所有取值范圍被稱為狀態(tài)空間，在移動(dòng)預(yù)測(cè)中位置集合就是狀態(tài)空間。而k階馬爾可夫鏈意味著時(shí)刻t所處的狀態(tài)分布與t之前的k個(gè)狀態(tài)有關(guān)，是一種“有限記憶”系統(tǒng)。因此只要求系統(tǒng)中任意2 個(gè)狀態(tài)之間的轉(zhuǎn)移概率就能確定模型。假設(shè)軌跡序列為 {…,st-2,s t-1,st,st+1,st+2,…}，由一階馬爾可夫鏈定義可知，st+1的狀態(tài)只與st有關(guān)，其滿足條件概率

馬爾可夫模型是應(yīng)用最廣泛的位置預(yù)測(cè)方法，但該模型也存在一些缺陷。對(duì)于高階馬爾可夫鏈存在復(fù)雜度太高和零頻率問(wèn)題，而低階馬爾可夫鏈的準(zhǔn)確性不高，因此研究者在馬爾可夫鏈的基礎(chǔ)上提出了改進(jìn)方法，他們分別從引入社交特征、弱預(yù)測(cè)器集成學(xué)習(xí)、變階馬爾可夫的角度對(duì)馬爾可夫預(yù)測(cè)進(jìn)行改進(jìn)。其中，文獻(xiàn)[15]以馬爾可夫模型為基礎(chǔ)對(duì)節(jié)點(diǎn)的移動(dòng)性進(jìn)行初步預(yù)測(cè)，然后利用與其社會(huì)關(guān)系較強(qiáng)的其他節(jié)點(diǎn)的位置對(duì)該節(jié)點(diǎn)的預(yù)測(cè)結(jié)果進(jìn)行修正。文獻(xiàn)[16]將馬爾可夫模型與回歸模型進(jìn)行集成學(xué)習(xí)，通過(guò)投票機(jī)制提升性能。文獻(xiàn)[17]通過(guò)變階馬爾可夫模型的逃逸機(jī)制來(lái)解決零頻率問(wèn)題，并采用樹(shù)結(jié)構(gòu)來(lái)減少高階馬爾可夫模型所需的內(nèi)存。文獻(xiàn)[18]基于個(gè)體的歷史上車和下車記錄，構(gòu)造出行事件的位置序列，預(yù)測(cè)用戶的出行需求并提供給用戶個(gè)性化打車服務(wù)。文獻(xiàn)[19]引入時(shí)間因素對(duì)移動(dòng)的影響，對(duì)馬爾可夫狀態(tài)轉(zhuǎn)移概率引入?yún)?shù)加以修正。文獻(xiàn)[20]通過(guò)非齊次馬爾可夫從駐留時(shí)間序列中預(yù)測(cè)移動(dòng)用戶何時(shí)離開(kāi)當(dāng)前位置以及下一步到達(dá)何處。研究者還針對(duì)軌跡片段缺失、數(shù)據(jù)稀疏等樣本問(wèn)題做出改進(jìn)，引入新的特征或數(shù)據(jù)提高預(yù)測(cè)準(zhǔn)確性。其中，文獻(xiàn)[21]針對(duì)不完全軌跡，放寬模型假設(shè)的馬爾可夫性質(zhì)，對(duì)馬爾可夫鏈的條件轉(zhuǎn)移概率重新定義，使其適用于斷續(xù)軌跡的預(yù)測(cè)。文獻(xiàn)[22]解決在使用單個(gè)用戶的軌跡數(shù)據(jù)建立狀態(tài)轉(zhuǎn)移矩陣時(shí)所產(chǎn)生的數(shù)據(jù)稀疏性問(wèn)題，通過(guò)度量用戶移動(dòng)行為相似性的方法，將用戶進(jìn)行聚類，對(duì)同組用戶建立共享狀態(tài)轉(zhuǎn)移矩陣。文獻(xiàn)[23]采用馬爾可夫模型進(jìn)行位置預(yù)測(cè)，同時(shí)采用概率密度函數(shù)對(duì)離開(kāi)時(shí)間和到達(dá)時(shí)間進(jìn)行預(yù)測(cè)，對(duì)預(yù)測(cè)的結(jié)果進(jìn)行結(jié)合，在一定程度上克服了馬爾可夫模型無(wú)法兼顧時(shí)空特征的缺點(diǎn)。

4.1.2 基于隱馬爾可夫模型的移動(dòng)預(yù)測(cè)

HMM 是一種特殊的貝葉斯網(wǎng)絡(luò)，它有5 個(gè)元素，如圖4 所示，包括有限的隱藏狀態(tài)S、有限的觀察狀態(tài)O、隱藏轉(zhuǎn)移概率矩陣A、觀察轉(zhuǎn)移概率矩陣B和狀態(tài)概率π。其中，S、O都是已知，HMM 可以表示為λ=[A,B,π]，通常利用Baum-Welch 算法學(xué)習(xí)參數(shù)λ。在一些場(chǎng)景中，無(wú)法直接獲取某狀態(tài)空間（隱藏狀態(tài)）的值，但是能夠通過(guò)另外的狀態(tài)空間（觀察狀態(tài)）間接獲取，此時(shí)馬爾可夫模型不再適用。在移動(dòng)預(yù)測(cè)中，將空間特征作為隱藏狀態(tài)，相應(yīng)的時(shí)刻為觀察狀態(tài)，就能夠?qū)r(shí)間特征和空間特征關(guān)聯(lián)，預(yù)測(cè)未來(lái)某個(gè)時(shí)段的位置。

圖4 隱馬爾可夫模型

研究者從應(yīng)用的角度提出HMM 移動(dòng)預(yù)測(cè)，其中，文獻(xiàn)[24]提出一種Wi-Fi 場(chǎng)景AP 選擇方案，通過(guò)預(yù)測(cè)用戶移動(dòng)獲取高質(zhì)量的連接，同時(shí)降低掃描能耗，該場(chǎng)景為室內(nèi)移動(dòng)預(yù)測(cè)，無(wú)法直接觀察到用戶的歷史位置，但通過(guò)歷史的AP 連接記錄作為觀察序列能夠間接預(yù)測(cè)用戶的位置。文獻(xiàn)[25]提出一種自適應(yīng)流媒體（DASH,dynamic adaptive streaming over HTTP）的視頻質(zhì)量智能調(diào)控方案，用戶所在的道路弧段為隱藏狀態(tài)，包含噪聲的GPS 采樣點(diǎn)為觀察狀態(tài)，預(yù)測(cè)將要到達(dá)的路段，結(jié)合用戶位置和速度進(jìn)行帶寬估計(jì)，進(jìn)而自適應(yīng)調(diào)整視頻源的編碼。文獻(xiàn)[11,26]則分別根據(jù)位置熵（位置熵[9]是指根據(jù)用戶訪問(wèn)各個(gè)地點(diǎn)的概率或頻次計(jì)算的信息熵，反映用戶移動(dòng)的規(guī)律性程度）和社交距離對(duì)用戶進(jìn)行分組，并對(duì)各組用戶分別訓(xùn)練隱馬爾可夫模型，同組用戶模型共享，相對(duì)地提高了整體預(yù)測(cè)性能。

2 種模型從統(tǒng)計(jì)的角度出發(fā)，能夠充分利用先驗(yàn)知識(shí)，但也意味著需要豐富的數(shù)據(jù)關(guān)聯(lián)信息。此外，用于移動(dòng)預(yù)測(cè)的概率統(tǒng)計(jì)模型還有多種。文獻(xiàn)[27]利用高斯混合模型進(jìn)行預(yù)測(cè)，每個(gè)高斯分布代表一個(gè)特征的概率分布，對(duì)預(yù)測(cè)的結(jié)果由高斯分量加權(quán)的概率表示，在數(shù)據(jù)樣本不足以及數(shù)據(jù)關(guān)聯(lián)模糊的情況適用。文獻(xiàn)[28-31]利用樸素貝葉斯模型進(jìn)行移動(dòng)預(yù)測(cè)，樸素貝葉斯模型要求各個(gè)特征之間相互獨(dú)立，如果特征之間有很強(qiáng)的關(guān)聯(lián)性，會(huì)導(dǎo)致樸素貝葉斯模型效果不佳，但它是最易實(shí)現(xiàn)的線性分類器。

4.2 基于判別模型的移動(dòng)預(yù)測(cè)

基于概率統(tǒng)計(jì)的模型能夠?qū)€性系統(tǒng)進(jìn)行高效的學(xué)習(xí)，但是對(duì)分類決策存在較高的錯(cuò)誤率，從概率分布的角度考慮，屬于生成模型（馬爾可夫模型除外）。生成模型根據(jù)大量樣本統(tǒng)計(jì)目標(biāo)序列和觀察序列的聯(lián)合概率，產(chǎn)生概率密度模型進(jìn)行預(yù)測(cè)，反映同類數(shù)據(jù)的相似度，不關(guān)心判別邊界，能夠充分地利用先驗(yàn)知識(shí)；判別模型根據(jù)有限樣本生成判別函數(shù)進(jìn)行預(yù)測(cè)，尋找不同類別之間的最優(yōu)判別邊界或分類面，反映的是異類數(shù)據(jù)之間的差異。生成模型的收斂速度更快，但是分類效果往往弱于判別模型，判別模型如支持向量機(jī)（SVM,support vector machine）、人工神經(jīng)網(wǎng)絡(luò)（ANN,artificial neural network）、深度神經(jīng)網(wǎng)絡(luò)能夠逼近任意非線性函數(shù)，有更加強(qiáng)大的學(xué)習(xí)能力。

基于判別模型的機(jī)器學(xué)習(xí)算法如SVM、ANN通常用于分類問(wèn)題。在移動(dòng)預(yù)測(cè)中，通過(guò)原始軌跡處理和空間特征提取，構(gòu)造出樣本長(zhǎng)度為n的軌跡序列 {l1,l2,…,ln}，通過(guò)滑動(dòng)窗口取出長(zhǎng)度為steps的元素，作為分類任務(wù)的特征向量，將滑動(dòng)窗口外的下一個(gè)元素作為分類任務(wù)的標(biāo)簽，從而構(gòu)造出分類數(shù)據(jù)集，滑動(dòng)窗口越大，意味著受越多歷史時(shí)隙的位置影響。數(shù)據(jù)集構(gòu)造方法如圖5 所示，本質(zhì)上是將預(yù)測(cè)問(wèn)題轉(zhuǎn)化成了分類問(wèn)題。

圖5 訓(xùn)練所用的數(shù)據(jù)

4.2.1 基于SVM/ANN 的移動(dòng)預(yù)測(cè)

SVM 適用于解決中小樣本、非線性以及高維問(wèn)題，對(duì)于數(shù)據(jù)噪聲有很強(qiáng)的抗噪能力，能夠降低異常值對(duì)模型的影響。其分類的基本思想是通過(guò)定義適當(dāng)?shù)暮撕瘮?shù)，將輸入空間非線性變換到高維空間，并在此高維空間尋找支持向量來(lái)組成最優(yōu)超平面。由于所預(yù)測(cè)的位置有多種可能，需要利用多值SVM 進(jìn)行預(yù)測(cè)。ANN 在處理隨機(jī)數(shù)據(jù)、非線性數(shù)據(jù)方面具有明顯的優(yōu)勢(shì)，對(duì)數(shù)據(jù)規(guī)模大、信息不明確的系統(tǒng)尤為適用，并且模型結(jié)構(gòu)簡(jiǎn)單，當(dāng)數(shù)據(jù)充足時(shí)，ANN 能有效應(yīng)用于移動(dòng)預(yù)測(cè)，有較強(qiáng)的頑健性和容錯(cuò)能力，但缺點(diǎn)是神經(jīng)網(wǎng)絡(luò)需要大量的參數(shù)，訓(xùn)練時(shí)間較長(zhǎng)。

利用上述2 種算法進(jìn)行移動(dòng)預(yù)測(cè)，很方便引入其他特征，例如天氣特征、交通特征等，通過(guò)特征工程處理后，對(duì)圖5 方式構(gòu)造的特征向量進(jìn)行擴(kuò)充，構(gòu)造新的特征向量，在無(wú)法獲取不同特征內(nèi)在關(guān)聯(lián)情況下能夠簡(jiǎn)單有效地將多種特征結(jié)合。文獻(xiàn)[32-33]利用多值SVM 在異構(gòu)網(wǎng)絡(luò)中對(duì)終端進(jìn)行移動(dòng)預(yù)測(cè)，避免了馬爾可夫模型的維數(shù)災(zāi)難，所輸入特征向量采用圖5 所構(gòu)造的數(shù)據(jù)樣本。其中，文獻(xiàn)[32]為區(qū)別隨機(jī)移動(dòng)模式（移動(dòng)的規(guī)則性和可測(cè)性較低的移動(dòng)模式，只受近期位置影響較大）和規(guī)則移動(dòng)模式，通過(guò)設(shè)定位置熵閾值將用戶進(jìn)行區(qū)分，并對(duì)二者采用不同維度的特征向量進(jìn)行預(yù)測(cè)。文獻(xiàn)[34-35]將ANN 應(yīng)用于車載云計(jì)算，利用ANN 預(yù)測(cè)車輛路線，在路邊單元切換過(guò)程前預(yù)留計(jì)算資源，使計(jì)算任務(wù)快速遷移。

上述傳統(tǒng)機(jī)器學(xué)習(xí)方法在短期的移動(dòng)預(yù)測(cè)中效果良好，但是對(duì)于長(zhǎng)期的預(yù)測(cè)能力不足。例如用戶在工作日每天的行程大多是規(guī)律的，但是每個(gè)周末會(huì)去俱樂(lè)部或游泳館活動(dòng)，以及每個(gè)月初會(huì)去醫(yī)院檢查身體，這種長(zhǎng)期的行為模式是普遍存在的。但是對(duì)于這類移動(dòng)模式，傳統(tǒng)的機(jī)器學(xué)習(xí)方法往往會(huì)當(dāng)作異常值處理，若單純地增大網(wǎng)絡(luò)規(guī)模來(lái)提高訓(xùn)練準(zhǔn)確度，會(huì)產(chǎn)生過(guò)擬合現(xiàn)象。而基于深度學(xué)習(xí)的移動(dòng)預(yù)測(cè)能夠有效解決此問(wèn)題。

4.2.2 基于深度學(xué)習(xí)的移動(dòng)預(yù)測(cè)

基于深度學(xué)習(xí)的預(yù)測(cè)模型如循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN,recurrent neural network）能夠處理大規(guī)模的數(shù)據(jù)集，并從中挖掘出長(zhǎng)期的時(shí)間依賴關(guān)系。RNN因其具有記憶性而被廣泛應(yīng)用于機(jī)器翻譯、自然語(yǔ)言處理等領(lǐng)域，它能保留多個(gè)歷史采樣時(shí)刻的數(shù)據(jù)對(duì)當(dāng)前采樣產(chǎn)生的影響，因此方便用來(lái)提取具有循環(huán)移動(dòng)行為的移動(dòng)模式。實(shí)際應(yīng)用中較少使用原版的RNN，因?yàn)橛?xùn)練過(guò)程會(huì)產(chǎn)生梯度爆炸或者梯度消失，導(dǎo)致記憶能力有限。實(shí)際中為了能夠存儲(chǔ)更長(zhǎng)期的數(shù)據(jù)對(duì)后文的影響，采用RNN 的變體，如長(zhǎng)短期記憶網(wǎng)絡(luò)（LSTM,long short-term memory）、門控循環(huán)單元（GRU,gated recurrent unit）等，相比于RNN 存在梯度指數(shù)衰減而使網(wǎng)絡(luò)后面的樣本對(duì)前面的樣本感知力下降的問(wèn)題，LSTM 等能夠過(guò)濾對(duì)后文有用的樣本特征，從而訓(xùn)練更深層的網(wǎng)絡(luò)。雖然版本不同，但訓(xùn)練和預(yù)測(cè)的過(guò)程是相同的。RNN 結(jié)構(gòu)如圖6 所示。

圖6 多對(duì)一循環(huán)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

圖6 中，x表示輸入層向量，其中xt表示第t（t=1,2,3,…）步的輸入向量；步長(zhǎng)代表循環(huán)周期，即最多能夠通過(guò)隱藏層的連接獲取多少步長(zhǎng)的歷史輸入對(duì)目標(biāo)的影響，例如ot+1能夠獲取x1,…,xt+1對(duì)其產(chǎn)生的影響，s t表示第t步的隱藏層輸出，o t表示第t步的輸出層輸出；U表示輸入層和隱藏層之間的權(quán)重矩陣；W表示連續(xù)2 個(gè)隱藏層間的權(quán)重矩陣；V表示隱藏層和輸出層之間的權(quán)重矩陣。對(duì)于多對(duì)一（多個(gè)輸入一個(gè)輸出）網(wǎng)絡(luò)結(jié)構(gòu)，只保留最后一步的輸出。

RNN 參數(shù)的傳遞式為

其中，f(?)為隱藏層激活函數(shù)，g(?)為輸出層激活函數(shù)。在移動(dòng)預(yù)測(cè)中，通過(guò)圖5 方式構(gòu)造數(shù)據(jù)集，要強(qiáng)調(diào)的是滑動(dòng)窗口的長(zhǎng)度和RNN 的循環(huán)周期保持一致。假設(shè)滑動(dòng)窗口大小為 steps，將樣本{l1,l2,…,lsteps}分 別輸 入RNN 的每步的輸入層，lsteps+1為輸出標(biāo)簽，通過(guò)lsteps+1和ot計(jì)算損失函數(shù)并進(jìn)行穿越時(shí)間的反向傳播算法訓(xùn)練。預(yù)測(cè)時(shí)將目標(biāo)前steps 步的數(shù)據(jù)樣本傳入模型，可直接得到預(yù)測(cè)值。

文獻(xiàn)[36-37]針對(duì)位置劃分維度過(guò)高導(dǎo)致LSTM 維數(shù)災(zāi)難，使用詞向量代替One-Hot 編碼提高學(xué)習(xí)效率。文獻(xiàn)[38-39]通過(guò)引入車輛特征、方向特征、天氣特征或文本特征提高RNN 預(yù)測(cè)準(zhǔn)確性，例如車輛型號(hào)和行駛速度相關(guān)，而天氣也影響車輛的駐留時(shí)間和行駛速度，通過(guò)卷積神經(jīng)網(wǎng)絡(luò)（CNN,convolutional neural network）將這些特征融合并嵌入LSTM 網(wǎng)絡(luò)進(jìn)行聯(lián)合訓(xùn)練，有效地進(jìn)行了車輛位置預(yù)測(cè)。文獻(xiàn)[40]引入RNN 的Attention 機(jī)制，識(shí)別更長(zhǎng)期的以及多種周期層次的移動(dòng)模式，Attention 機(jī)制在模型輸出時(shí)會(huì)選擇性地專注考慮輸入樣本的某些信息，因此能夠顯著提高預(yù)測(cè)性能。

SVM 和ANN 只能進(jìn)行短期預(yù)測(cè)，RNN 因?yàn)橛洃浶阅軌蜻M(jìn)行長(zhǎng)期預(yù)測(cè)，但是復(fù)雜度較高，需要大量的訓(xùn)練樣本，當(dāng)樣本數(shù)目少于某個(gè)閾值時(shí)，性能就會(huì)劇烈下降，產(chǎn)生欠擬合現(xiàn)象。

4.3 基于頻繁模式挖掘的移動(dòng)預(yù)測(cè)

數(shù)據(jù)挖掘常用的方法有分類、聚類、頻繁模式挖掘（即關(guān)聯(lián)分析）等。頻繁模式挖掘建立在大數(shù)據(jù)的基礎(chǔ)上，從海量的、有噪聲的、不完整的、隨機(jī)的數(shù)據(jù)中提取頻繁出現(xiàn)在數(shù)據(jù)中的頻繁項(xiàng)集。頻繁項(xiàng)集能夠發(fā)現(xiàn)大型事物或者數(shù)據(jù)之間的關(guān)聯(lián)或相關(guān)性。頻繁模式挖掘常用FP-Growth算法和Apriori 算法。利用Apriori 算法進(jìn)行移動(dòng)預(yù)測(cè)分為3 步，首先對(duì)用戶原始移動(dòng)軌跡進(jìn)行特征處理，構(gòu)造軌跡序列；然后對(duì)所提取的軌跡序列計(jì)算所有候選頻繁項(xiàng)支持度，超過(guò)支持度閾值的候選頻繁項(xiàng)構(gòu)成頻繁項(xiàng)集；最后通過(guò)置信度計(jì)算與當(dāng)前序列最相關(guān)的頻繁項(xiàng)，從而進(jìn)行預(yù)測(cè)。其中，頻繁項(xiàng)集就是所提取的移動(dòng)模式，對(duì)當(dāng)前軌跡序列和頻繁項(xiàng)進(jìn)行匹配，匹配到置信度最高的頻繁項(xiàng)。

文獻(xiàn)[41-42]分別利用FP-Growth 和Apriori 對(duì)移動(dòng)進(jìn)行預(yù)測(cè)，其中前者結(jié)合最長(zhǎng)公共子序列算法進(jìn)行改進(jìn)，所謂最長(zhǎng)公共子序列算法是通過(guò)發(fā)現(xiàn)和當(dāng)前序列相似的歷史最長(zhǎng)公共子序列進(jìn)行模式匹配；后者將人群移動(dòng)模式應(yīng)用于無(wú)線網(wǎng)絡(luò)規(guī)劃，改進(jìn)基站的部署方案。文獻(xiàn)[43-46]等對(duì)軌跡序列進(jìn)行相似度度量，根據(jù)相似序列進(jìn)行移動(dòng)預(yù)測(cè)。文獻(xiàn)[47-48]針對(duì)軌跡信息缺失、數(shù)據(jù)稀疏、冗余等問(wèn)題做出特征處理及改進(jìn)。文獻(xiàn)[49]在馬爾可夫模型中嵌入Apriori 關(guān)聯(lián)分析來(lái)提高預(yù)測(cè)性能。

FP-Growth 算法將提供頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一棵頻繁模式樹(shù)（FP-tree,frequent pattern tree），但仍保留項(xiàng)集之間的關(guān)聯(lián)信息。頻繁模式樹(shù)是一棵特殊的前綴樹(shù)，它解決了Apriori 算法會(huì)產(chǎn)生大量的候選集的問(wèn)題。Apriori 算法需多次掃描數(shù)據(jù)，每次利用候選頻繁項(xiàng)集產(chǎn)生頻繁項(xiàng)集；FP-growth則利用樹(shù)形結(jié)構(gòu)，不需要產(chǎn)生候選頻繁項(xiàng)集而直接得到頻繁項(xiàng)集，減少了掃描數(shù)據(jù)的次數(shù)，效率更高，但Apriori 的算法擴(kuò)展性較好，可以用于并行計(jì)算領(lǐng)域。

在實(shí)際預(yù)測(cè)中，很多研究者構(gòu)造了其他樹(shù)結(jié)構(gòu)完成序列匹配。文獻(xiàn)[46,50]通過(guò)概率后綴樹(shù)采用單一序列的模式匹配進(jìn)行預(yù)測(cè)。文獻(xiàn)[13]構(gòu)造了基于路徑特征的概率基樹(shù)進(jìn)行決策，能夠應(yīng)用于多序列的模式匹配，如圖7 所示，移動(dòng)終端在路徑a1有概率選擇接連走路徑a2a3，有概率選擇走路徑a4，依次類推，其轉(zhuǎn)移概率是通過(guò)歷史統(tǒng)計(jì)所得的位置轉(zhuǎn)移頻率。文獻(xiàn)[51]綜合考慮了用戶的地理觸發(fā)意圖、時(shí)間觸發(fā)意圖和語(yǔ)義觸發(fā)意圖，與傳統(tǒng)的頻繁模式只能代表3 種意圖中的一種不同，通過(guò)判斷軌跡語(yǔ)義和時(shí)間屬性來(lái)修正候選頻繁項(xiàng)的支持度，生成更接近真實(shí)模式的頻繁項(xiàng)集，有效地提升了預(yù)測(cè)性能。

圖7 基于路徑的概率樹(shù)

以上總結(jié)了幾種被廣泛使用的移動(dòng)預(yù)測(cè)算法，在應(yīng)用中具體采用何種算法，需要根據(jù)數(shù)據(jù)集規(guī)模、移動(dòng)的規(guī)律性、數(shù)據(jù)的連續(xù)性、異常值數(shù)量、時(shí)間復(fù)雜度、特征維度等綜合考慮，每種算法都有各自的利弊，需要研究者合理利用算法的優(yōu)勢(shì)，甚至集成不同算法提升預(yù)測(cè)準(zhǔn)確性。

5 其他因素對(duì)移動(dòng)預(yù)測(cè)的影響

除了時(shí)空維度本身的規(guī)律，還有很多因素影響用戶的移動(dòng)，如天氣特征、交通特征、身體特征等，因此移動(dòng)預(yù)測(cè)是一個(gè)結(jié)合多維環(huán)境因素的復(fù)雜過(guò)程。例如天氣因素，用戶每天晚上都會(huì)去健身房，但是因?yàn)殪F霾而暫停；又如交通因素，因?yàn)楣?jié)日導(dǎo)致的交通擁堵迫使用戶放棄外出活動(dòng)。此外，還有社交因素、健康因素等，這些隨機(jī)事件會(huì)擾亂用戶的慣性行為，但又是時(shí)常發(fā)生的。本文對(duì)其中的社交因素進(jìn)行重點(diǎn)闡述。

社交網(wǎng)絡(luò)是用戶社交關(guān)系的部分體現(xiàn)，相似的用戶或者具有緊密社交關(guān)系的用戶往往具有相似的行為模式，例如，用戶甲和乙是關(guān)系密切的同事，那么在午飯時(shí)間有很大的概率同時(shí)從辦公室到食堂就餐。因此基于位置的社交網(wǎng)絡(luò)被用來(lái)對(duì)個(gè)體的移動(dòng)性進(jìn)行預(yù)測(cè)是有效的。文獻(xiàn)[28,52]將社交關(guān)系作為影響移動(dòng)的特征，對(duì)其他模型預(yù)測(cè)結(jié)果進(jìn)行修正。文獻(xiàn)[53-54]則考慮到移動(dòng)預(yù)測(cè)基于歷史數(shù)據(jù)，無(wú)法預(yù)測(cè)未曾訪問(wèn)的區(qū)域，引入社交關(guān)系協(xié)同濾波擴(kuò)大預(yù)測(cè)候選集，解決部分新穎位置不可達(dá)問(wèn)題。文獻(xiàn)[55-56]應(yīng)用圖像識(shí)別和文本識(shí)別，從用戶社交網(wǎng)絡(luò)的文字圖片中提取文本特征，增加特征維度來(lái)提高預(yù)測(cè)準(zhǔn)確性。

6 無(wú)線網(wǎng)絡(luò)場(chǎng)景中移動(dòng)預(yù)測(cè)總結(jié)

無(wú)線網(wǎng)絡(luò)是移動(dòng)預(yù)測(cè)重要的應(yīng)用場(chǎng)景。在蜂窩網(wǎng)、Wi-Fi 或超密集組網(wǎng)中，由于用戶的移動(dòng)性，基站或接入節(jié)點(diǎn)的資源（通信資源、計(jì)算資源）分配會(huì)隨著時(shí)間變化。文獻(xiàn)[7-8,24,57-59]將移動(dòng)預(yù)測(cè)應(yīng)用在不同的網(wǎng)絡(luò)場(chǎng)景中預(yù)測(cè)即將接入的節(jié)點(diǎn)，在切換前預(yù)留通信資源，實(shí)現(xiàn)無(wú)縫切換服務(wù)，具體使用的預(yù)測(cè)模型因場(chǎng)景而異。文獻(xiàn)[14,38,60]預(yù)測(cè)應(yīng)用在車載自組織網(wǎng)絡(luò)中，車載自組織網(wǎng)絡(luò)相比于移動(dòng)自組網(wǎng)具有車輛移動(dòng)速度快、移動(dòng)路徑受限等特點(diǎn)，當(dāng)車輛換道可能存在危險(xiǎn)時(shí)，并線警告將提醒有意換道的駕駛員。并線警告使用V2V 通信和周邊車輛的路徑預(yù)測(cè)，利用鏈路的通信范圍來(lái)預(yù)測(cè)駕駛員換道可能產(chǎn)生的碰撞。路徑預(yù)測(cè)用于確定在3～5 s 的時(shí)間內(nèi)，駕駛員要到達(dá)的車道區(qū)域是否被占用。如果該車道已被占用，則并線警告將會(huì)提醒駕駛員潛在的危險(xiǎn)。文獻(xiàn)[61]將預(yù)測(cè)應(yīng)用在內(nèi)容中心網(wǎng)絡(luò)的主動(dòng)緩存，預(yù)知用戶移動(dòng)性，在最佳預(yù)取節(jié)點(diǎn)緩存請(qǐng)求的內(nèi)容，提高緩存的命中率。文獻(xiàn)[62]將移動(dòng)預(yù)測(cè)應(yīng)用在移動(dòng)邊緣計(jì)算（MEC,mobile edge computing）的任務(wù)遷移，將應(yīng)用發(fā)布的任務(wù)預(yù)先遷移到下一MEC 服務(wù)節(jié)點(diǎn)，避免任務(wù)遷移導(dǎo)致的長(zhǎng)時(shí)間宕機(jī)而影響用戶體驗(yàn)。以及上文提到的將預(yù)測(cè)應(yīng)用在無(wú)線傳感網(wǎng)絡(luò)定向通信和自適應(yīng)流媒體，實(shí)現(xiàn)智能調(diào)控視頻質(zhì)量。此外，還有更多應(yīng)用值得研究者挖掘。

由于不同場(chǎng)景使用的軌跡序列的數(shù)據(jù)規(guī)模，特征維度以及預(yù)測(cè)目標(biāo)的精度需求有所差異，采用的預(yù)測(cè)方法有所偏向。例如對(duì)于特征維度較高的數(shù)據(jù)，使用SVM 能夠更好地進(jìn)行分類及預(yù)測(cè)；如果所預(yù)測(cè)的位置狀態(tài)較少，高階馬爾可夫模型綜合性能良好且易實(shí)現(xiàn)；如果預(yù)測(cè)用戶長(zhǎng)期的移動(dòng)模式，循環(huán)神經(jīng)網(wǎng)絡(luò)性能更好。

在無(wú)線網(wǎng)絡(luò)中，采用何種算法并非絕對(duì)，影響算法性能的主要是所構(gòu)造的軌跡序列，而軌跡序列是從原始數(shù)據(jù)通過(guò)特征工程得到的。因此，只要針對(duì)原始數(shù)據(jù)進(jìn)行細(xì)致的特征處理，再選擇合適的算法，就能得到針對(duì)該場(chǎng)景相對(duì)較好的預(yù)測(cè)性能。表2總結(jié)了研究較多的移動(dòng)預(yù)測(cè)在無(wú)線網(wǎng)絡(luò)中的應(yīng)用。

表2 移動(dòng)預(yù)測(cè)在無(wú)線網(wǎng)絡(luò)中的應(yīng)用

7 結(jié)束語(yǔ)

移動(dòng)預(yù)測(cè)是智慧旅游、個(gè)性化服務(wù)、城市規(guī)劃等場(chǎng)景重點(diǎn)關(guān)注的問(wèn)題，目前學(xué)者致力于提高移動(dòng)預(yù)測(cè)的準(zhǔn)確性，為此提出了各種有效的模型，但也存在一些難以解決的問(wèn)題。一是預(yù)測(cè)粒度、預(yù)測(cè)復(fù)雜度和預(yù)測(cè)準(zhǔn)確性的權(quán)衡，為了提高預(yù)測(cè)的準(zhǔn)確性，往往做出過(guò)于理想化的假設(shè)，但是其結(jié)果大多失去應(yīng)用價(jià)值，而深度學(xué)習(xí)模型和頻繁模式挖掘往往復(fù)雜度過(guò)高，在一些實(shí)時(shí)的應(yīng)用場(chǎng)景如城市交通調(diào)度會(huì)有較大時(shí)延，難以應(yīng)用。二是位置熵較高的非規(guī)則用戶難以預(yù)測(cè)，位置熵越高概率分布越均勻，意味著用戶移動(dòng)更加隨機(jī)，規(guī)律性不強(qiáng)，這類用戶不遵循固定的行為模式。有學(xué)者嘗試根據(jù)位置熵對(duì)用戶進(jìn)行分類，建立不同分組的預(yù)測(cè)模型，但是對(duì)位置熵高的群體，預(yù)測(cè)結(jié)果仍然不太理想。三是軌跡數(shù)據(jù)的發(fā)布會(huì)產(chǎn)生隱私泄露的風(fēng)險(xiǎn)，若被攻擊者利用，會(huì)對(duì)用戶的安全產(chǎn)生威脅，因此對(duì)軌跡數(shù)據(jù)的隱私保護(hù)尤為重要，目前隱私保護(hù)技術(shù)尚未完善。四是移動(dòng)預(yù)測(cè)要解決的主要問(wèn)題，即實(shí)現(xiàn)時(shí)間依賴與空間依賴結(jié)合的移動(dòng)預(yù)測(cè)，目前的移動(dòng)預(yù)測(cè)大多為2 種，根據(jù)位置序列預(yù)測(cè)用戶的下一個(gè)位置，或根據(jù)時(shí)間序列預(yù)測(cè)用戶駐留時(shí)間或到達(dá)時(shí)間，因?yàn)闀r(shí)間與位置之間的關(guān)聯(lián)不穩(wěn)定，預(yù)測(cè)的準(zhǔn)確性不高，有學(xué)者通過(guò)將時(shí)間簡(jiǎn)單分段與位置建立關(guān)聯(lián)，但所提出的解決方案缺乏準(zhǔn)確性和頑健性。以上正是移動(dòng)預(yù)測(cè)必須要解決的一些問(wèn)題和難點(diǎn)。