移動(dòng)網(wǎng)絡(luò)中的用戶移動(dòng)模式預(yù)測(cè)

何海洋 北京郵電大學(xué)數(shù)據(jù)科學(xué)中心，網(wǎng)絡(luò)體系構(gòu)建與融合北京市重點(diǎn)實(shí)驗(yàn)室

移動(dòng)網(wǎng)絡(luò)中的用戶移動(dòng)模式預(yù)測(cè)

何海洋 北京郵電大學(xué)數(shù)據(jù)科學(xué)中心，網(wǎng)絡(luò)體系構(gòu)建與融合北京市重點(diǎn)實(shí)驗(yàn)室

隨著移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展，利用移動(dòng)數(shù)據(jù)分析移動(dòng)用戶的移動(dòng)性成為移動(dòng)互聯(lián)網(wǎng)研究的一大熱點(diǎn)。本文提出了基于時(shí)間的Markov（Time-Based Markov，TBM）算法，并利用南方某省運(yùn)營(yíng)商3周的連續(xù)數(shù)據(jù)，使用TBM算法對(duì)移動(dòng)類(lèi)用戶進(jìn)行位置預(yù)測(cè)。通過(guò)試驗(yàn)，證明了所提出的方法比基礎(chǔ)Markov方法有更高的預(yù)測(cè)準(zhǔn)確率，這對(duì)運(yùn)營(yíng)商和位置服務(wù)提供商有重要意義。

移動(dòng)模式；預(yù)測(cè)準(zhǔn)確率；用戶聚類(lèi)

1 引言

隨著移動(dòng)互聯(lián)網(wǎng)用戶數(shù)量和通信數(shù)據(jù)量的不斷增長(zhǎng)，通過(guò)移動(dòng)互聯(lián)網(wǎng)上真實(shí)流量數(shù)據(jù)分析用戶行為意義重大。通過(guò)移動(dòng)網(wǎng)絡(luò)數(shù)據(jù)可以進(jìn)行數(shù)據(jù)使用、應(yīng)用使用、移動(dòng)模式等用戶行為分析。在各類(lèi)用戶行為分析中，分析用戶移動(dòng)模式并進(jìn)行用戶移動(dòng)性預(yù)測(cè)有著重要意義。通過(guò)研究移動(dòng)模式，運(yùn)營(yíng)商可以達(dá)到用戶移動(dòng)性預(yù)測(cè)、用戶移動(dòng)性管理等目的。

用戶移動(dòng)模式的研究大多根據(jù)用戶歷史路徑，通過(guò)機(jī)器學(xué)習(xí)算法調(diào)整歷史樣本數(shù)據(jù)調(diào)整分類(lèi)器參數(shù)，從而預(yù)測(cè)某個(gè)用戶將來(lái)的位置。LZ-Based算法通過(guò)路徑樹(shù)的不斷更新實(shí)現(xiàn)預(yù)測(cè)。Markov算法沒(méi)路徑樹(shù)的建立過(guò)程，而是直接匹配歷史路徑，并可以改變匹配階數(shù)。貝葉斯算法、神經(jīng)網(wǎng)絡(luò)算法、隱式馬爾可夫模型等也可用于移動(dòng)性預(yù)測(cè)。

以上算法將空間上下文作為影響用戶移動(dòng)性預(yù)測(cè)的主要因素。而近些年，越來(lái)越多的研究者們開(kāi)始考慮時(shí)間因素對(duì)預(yù)測(cè)結(jié)果的影響。

除了空間和時(shí)間因素，希望將一個(gè)用戶特定的移動(dòng)特點(diǎn)對(duì)用戶移動(dòng)性的影響因素加以考慮。例如，對(duì)于預(yù)測(cè)一個(gè)用戶在某一段時(shí)間的位置這樣的問(wèn)題，預(yù)測(cè)一個(gè)朝九晚五工作的白領(lǐng)比預(yù)測(cè)一個(gè)天天跑業(yè)務(wù)的銷(xiāo)售員更容易，因?yàn)榘最I(lǐng)的移動(dòng)習(xí)慣更規(guī)律。所以，希望進(jìn)一步地證明對(duì)于擁有不同時(shí)空移動(dòng)特點(diǎn)的用戶，應(yīng)該使用不同方法進(jìn)行預(yù)測(cè)。

2 基于時(shí)間的Markov預(yù)測(cè)算法

基礎(chǔ)的Markov預(yù)測(cè)算法只關(guān)心用戶的歷史地理位置而并不關(guān)心時(shí)間。實(shí)際上人們生活中的行為習(xí)慣和時(shí)間段有緊密的相連性。為了提高預(yù)測(cè)算法的準(zhǔn)確度，本文提出基于時(shí)間的馬爾可夫算法（Time Based Markov，TBM）。同時(shí)，關(guān)聯(lián)地理位置與時(shí)間，并對(duì)基礎(chǔ)Markov處理的相同用戶數(shù)據(jù)進(jìn)行計(jì)算，得出更高準(zhǔn)確率的結(jié)果。

基于用戶的歷史軌跡，如果用戶當(dāng)前所在的時(shí)間和地點(diǎn)為已知，TBM可以預(yù)測(cè)該用戶的下一跳，以及當(dāng)前時(shí)間點(diǎn)與下一跳時(shí)間點(diǎn)的時(shí)間間隔。算法的主要步驟如下：

（1）首先建立用戶的時(shí)間和位置歷史路徑序列。

（2）給定一個(gè)當(dāng)前時(shí)間和位置，以及一個(gè)時(shí)間閾值，在整個(gè)歷史路徑（T，LOC）中尋找某記錄點(diǎn)（t，loc），與（tr，locr）滿足地理位置相同（即），確定路徑時(shí)間點(diǎn)在歷史路徑時(shí)間點(diǎn)前后時(shí)間閾值范圍內(nèi)（即）。

（3）如果沒(méi)有歷史路徑點(diǎn)符合以上所述的情況，將返回“No Match”為結(jié)果。

（4）如果有個(gè)結(jié)果滿足以上要求，將他們命名為。然后，為每一個(gè)歷史位置尋找下一個(gè)位置，并且計(jì)算須預(yù)測(cè)的與下一跳（）的時(shí)間間隔。之后，會(huì)獲得一系列數(shù)據(jù)。

（5）選擇出現(xiàn)概率最大的。

為了更好地解釋這個(gè)算法，下面給出一個(gè)例子。如果現(xiàn)在是早上9∶00，某人處于地理位置c點(diǎn)，同時(shí)設(shè)置時(shí)間閾值為一個(gè)小時(shí)（Ts=1h）。

首先TBM會(huì)搜索小明歷史路徑如下：

之后，TBM在歷史路徑中尋找符合匹配關(guān)系的記錄點(diǎn)，即地理位置為滿足loc=c并且前后時(shí)間間隔在時(shí)間閾值范圍內(nèi)（8∶00＜t＜10∶00）的記錄點(diǎn)。從給出的路徑中可以看出，有6個(gè)這樣的記錄點(diǎn)被加粗標(biāo)出。接下來(lái)，算法找出這些記錄的點(diǎn)的下一個(gè)記錄點(diǎn)（被下劃線標(biāo)出）。列出下一跳記錄點(diǎn)們的地理位置與當(dāng)前需預(yù)測(cè)路徑點(diǎn)的時(shí)間間隔，如（d，0），（e，0），（d，0），（e，0），（d，2），（d，0）。其中，可以算出（d，0）出現(xiàn)的概率最大為50%。因此，基于時(shí)間的Markov算法則預(yù)測(cè)接下來(lái)將會(huì)在一個(gè)小時(shí)之內(nèi)移動(dòng)到地點(diǎn)d。

該算法背后的主要思想是基于用戶行為強(qiáng)烈地決定于歷史移動(dòng)模式，而這種模式不僅僅依賴于他們經(jīng)過(guò)的地點(diǎn)，還包括他們經(jīng)過(guò)這些地點(diǎn)的時(shí)間。例如，一個(gè)用戶剛剛在公司食堂吃過(guò)飯，如果吃的午餐，他更可能回辦公室，但如果是晚餐，則更可能直接回家。因此，提出的算法既考慮了空間因素，又考慮了時(shí)間因素，這樣相比只考慮空間因素的算法可以更加準(zhǔn)確地預(yù)測(cè)用戶移動(dòng)模式。

3 數(shù)據(jù)集

希望借助以上提出的兩種基于時(shí)間移動(dòng)性預(yù)測(cè)算法對(duì)不同用戶使用，比較不同方法對(duì)不用用戶的適用性和有效性。采用南方某省運(yùn)營(yíng)商真實(shí)移動(dòng)網(wǎng)絡(luò)采集到的4G移動(dòng)數(shù)據(jù)進(jìn)行試驗(yàn)，數(shù)據(jù)包括連續(xù)3周，具體時(shí)間為2013.10.10—2013.10.31?？梢詮脑拞螖?shù)據(jù)中提取出用戶ID、基站IP、訪問(wèn)時(shí)間、狀態(tài)等信息，具體數(shù)據(jù)的大體結(jié)構(gòu)可參見(jiàn)表1，其中基站IP可通過(guò)IP-經(jīng)緯度對(duì)照表轉(zhuǎn)化為經(jīng)緯度信息。

表1 輸入數(shù)據(jù)形式表

所有數(shù)據(jù)包含3474個(gè)用戶和729個(gè)eNodeBs（4G基站），考慮到某些用戶在數(shù)據(jù)集中有非常少的記錄，使得很難分析這些用戶的移動(dòng)性。在試驗(yàn)中為了讓每個(gè)用戶有足夠多的記錄來(lái)分析，首先將連接基站數(shù)少于10個(gè)和連接次數(shù)少于500次的用戶過(guò)濾掉；由于TBM本質(zhì)為預(yù)測(cè)用戶下一跳，更適合預(yù)測(cè)移動(dòng)性較強(qiáng)的用戶，于是又通過(guò)基于熵值的用戶聚類(lèi)算法將用戶聚類(lèi)為固定類(lèi)用戶和移動(dòng)類(lèi)用戶，兩類(lèi)用戶數(shù)量分別為1409和795。對(duì)于固定類(lèi)用戶，可以使用基于空間概率分布的方法預(yù)測(cè)用戶在某一段時(shí)間的位置。后續(xù)的試驗(yàn)中將針對(duì)795個(gè)移動(dòng)類(lèi)用戶進(jìn)行移動(dòng)模式預(yù)測(cè)。處于數(shù)據(jù)安全原因，已經(jīng)將用戶的隱私信息通過(guò)Hash處理。

4 用戶移動(dòng)模式預(yù)測(cè)

基于TBM算法，將在本節(jié)預(yù)測(cè)移動(dòng)用戶的下一跳，如果一個(gè)用戶在一段時(shí)間內(nèi)一直連著相同的小區(qū)基站，將這些記錄點(diǎn)全部合并為一個(gè)記錄，同時(shí)到達(dá)時(shí)間也設(shè)置為第一個(gè)記錄的時(shí)間。用前兩周的數(shù)據(jù)做訓(xùn)練，然后如果一個(gè)用戶在第三周總共移動(dòng)了n次，而后有m個(gè)移動(dòng)軌跡被預(yù)測(cè)正確，則認(rèn)為準(zhǔn)確率為m/n。每個(gè)用戶的準(zhǔn)確率最后取平均值得到最終準(zhǔn)確率。分別使用Markov和TBM對(duì)預(yù)測(cè)準(zhǔn)確率進(jìn)行試驗(yàn)，其中TBM的Ts參數(shù)分別設(shè)置為1和2h。同時(shí)，算法在移動(dòng)類(lèi)用戶和所有用戶分別進(jìn)行了試驗(yàn)，最終的試驗(yàn)結(jié)果如表2所示。

表2 Markov和TBM的預(yù)測(cè)準(zhǔn)確率

從表2得知，TBM相比于基礎(chǔ)Markov對(duì)移動(dòng)用戶能達(dá)到更好的預(yù)測(cè)效果。當(dāng)時(shí)間閾值Ts設(shè)置為1h，TBM的預(yù)測(cè)準(zhǔn)確率從46.9%上升至47.7%；當(dāng)時(shí)間閾值Ts設(shè)置為2h，可以得到更高的預(yù)測(cè)準(zhǔn)確率。

為了研究時(shí)間閾值Ts對(duì)TBM算法的影響，設(shè)置時(shí)間閾值在區(qū)間［0.5h，5h］的變化，以0.5h為步長(zhǎng)，對(duì)移動(dòng)用戶針對(duì)每一個(gè)不同的時(shí)間閾值使用TBM進(jìn)行預(yù)測(cè)。得到如圖1所示的結(jié)果，以時(shí)間閾值Ts為橫坐標(biāo)，以準(zhǔn)確率為縱坐標(biāo)。從圖1中可以知道時(shí)間閾值的最好選擇是2.5～3h。如果想要找到一個(gè)移動(dòng)用戶在某個(gè)時(shí)間點(diǎn)如早上10∶00的軌跡，那么最好是觀察該用戶每天從早晨7∶30—12∶30的移動(dòng)軌跡。

圖1 時(shí)間差與準(zhǔn)確率的關(guān)系

接下來(lái)，進(jìn)一步通過(guò)觀察預(yù)測(cè)效果較差的結(jié)果來(lái)改進(jìn)算法。首先，在圖2中畫(huà)出了一些隨機(jī)移動(dòng)類(lèi)用戶的移動(dòng)軌跡。在每個(gè)子圖中，每個(gè)點(diǎn)代表用戶連接的一個(gè)基站，兩個(gè)點(diǎn)之間的線代表用戶從其中一點(diǎn)移動(dòng)到另一點(diǎn)。其中，容易預(yù)測(cè)出錯(cuò)的一些點(diǎn)已經(jīng)圈標(biāo)注出來(lái)。

通過(guò)觀察，發(fā)現(xiàn)用戶在容易預(yù)測(cè)出錯(cuò)的區(qū)域通常有這樣的移動(dòng)軌跡：假設(shè)該用戶當(dāng)前在，通過(guò)觀察他的歷史路徑，該用戶移動(dòng)到和的概率幾乎是相同的。這暗示可以考慮提高TBM的階數(shù)，即考慮的前一位置：如果前一位置是，則他更可能去；如果前一位置是，則更可能去?；诖耍淖兞薚BM算法中的第5步：定義作為的前一位置，如果選擇最大概率的和是同一位置，則選擇擁有第二大概率的。通過(guò)這種方式改進(jìn)TBM算法，移動(dòng)類(lèi)用戶的平均預(yù)測(cè)準(zhǔn)確率達(dá)到了59.2%。

圖2 示例用戶移動(dòng)軌跡

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

本文提出了TBM算法預(yù)測(cè)移動(dòng)類(lèi)用戶的下一跳和到達(dá)時(shí)間。和基礎(chǔ)Markov的46.8%的預(yù)測(cè)準(zhǔn)確率相比，TBM通過(guò)優(yōu)化的預(yù)測(cè)準(zhǔn)確率可以達(dá)到59.2%。試驗(yàn)結(jié)果證明了對(duì)于不同移動(dòng)特點(diǎn)的用戶，使用不同的預(yù)測(cè)算法進(jìn)行移動(dòng)模式發(fā)現(xiàn)會(huì)使預(yù)測(cè)效果更好，這對(duì)于網(wǎng)絡(luò)服務(wù)提供商、位置服務(wù)提供商等都有重大的意義。

Prediction of user mobility pattern in mobile internet

HE Haiyang

The mobile Internet in recent years has been developing rapidly. Using mobile traffic data to analyze user mobility has become a hot topic in the area of mobile Internet research. In this paper， we present the Time- Based Markov （TBM） predictor for the location prediction of mobile users.With three-consecutive-week data collected from Long Term Evolution （LTE） mobile network， we use TBM predictor on mobile users. Experiments demonstrate the effectiveness and better performance of our proposed methods compared with the baselines， which is of great importance for iSPs or location based service Providers.

mobility pattern；prediction accuracy；user clustering

2016-06-20）