何海洋 北京郵電大學數據科學中心，網絡體系構建與融合北京市重點實驗室

移動網絡中的用戶移動模式預測

何海洋 北京郵電大學數據科學中心，網絡體系構建與融合北京市重點實驗室

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

移動模式；預測準確率；用戶聚類

1 引言

隨著移動互聯網用戶數量和通信數據量的不斷增長，通過移動互聯網上真實流量數據分析用戶行為意義重大。通過移動網絡數據可以進行數據使用、應用使用、移動模式等用戶行為分析。在各類用戶行為分析中，分析用戶移動模式并進行用戶移動性預測有著重要意義。通過研究移動模式，運營商可以達到用戶移動性預測、用戶移動性管理等目的。

用戶移動模式的研究大多根據用戶歷史路徑，通過機器學習算法調整歷史樣本數據調整分類器參數，從而預測某個用戶將來的位置。LZ-Based算法通過路徑樹的不斷更新實現預測。Markov算法沒路徑樹的建立過程，而是直接匹配歷史路徑，并可以改變匹配階數。貝葉斯算法、神經網絡算法、隱式馬爾可夫模型等也可用于移動性預測。

以上算法將空間上下文作為影響用戶移動性預測的主要因素。而近些年，越來越多的研究者們開始考慮時間因素對預測結果的影響。

除了空間和時間因素，希望將一個用戶特定的移動特點對用戶移動性的影響因素加以考慮。例如，對于預測一個用戶在某一段時間的位置這樣的問題，預測一個朝九晚五工作的白領比預測一個天天跑業(yè)務的銷售員更容易，因為白領的移動習慣更規(guī)律。所以，希望進一步地證明對于擁有不同時空移動特點的用戶，應該使用不同方法進行預測。

2 基于時間的Markov預測算法

基礎的Markov預測算法只關心用戶的歷史地理位置而并不關心時間。實際上人們生活中的行為習慣和時間段有緊密的相連性。為了提高預測算法的準確度，本文提出基于時間的馬爾可夫算法（Time Based Markov，TBM）。同時，關聯地理位置與時間，并對基礎Markov處理的相同用戶數據進行計算，得出更高準確率的結果。

基于用戶的歷史軌跡，如果用戶當前所在的時間和地點為已知，TBM可以預測該用戶的下一跳，以及當前時間點與下一跳時間點的時間間隔。算法的主要步驟如下：

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

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

（3）如果沒有歷史路徑點符合以上所述的情況，將返回“No Match”為結果。

（4）如果有個結果滿足以上要求，將他們命名為。然后，為每一個歷史位置尋找下一個位置，并且計算須預測的與下一跳（）的時間間隔。之后，會獲得一系列數據。

（5）選擇出現概率最大的。

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

首先TBM會搜索小明歷史路徑如下：

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

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

3 數據集

希望借助以上提出的兩種基于時間移動性預測算法對不同用戶使用，比較不同方法對不用用戶的適用性和有效性。采用南方某省運營商真實移動網絡采集到的4G移動數據進行試驗，數據包括連續(xù)3周，具體時間為2013.10.10—2013.10.31?？梢詮脑拞螖祿刑崛〕鲇脩鬒D、基站IP、訪問時間、狀態(tài)等信息，具體數據的大體結構可參見表1，其中基站IP可通過IP-經緯度對照表轉化為經緯度信息。

表1 輸入數據形式表

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

4 用戶移動模式預測

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

表2 Markov和TBM的預測準確率

從表2得知，TBM相比于基礎Markov對移動用戶能達到更好的預測效果。當時間閾值Ts設置為1h，TBM的預測準確率從46.9%上升至47.7%；當時間閾值Ts設置為2h，可以得到更高的預測準確率。

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

圖1 時間差與準確率的關系

接下來，進一步通過觀察預測效果較差的結果來改進算法。首先，在圖2中畫出了一些隨機移動類用戶的移動軌跡。在每個子圖中，每個點代表用戶連接的一個基站，兩個點之間的線代表用戶從其中一點移動到另一點。其中，容易預測出錯的一些點已經圈標注出來。

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

圖2 示例用戶移動軌跡

5 結束語

本文提出了TBM算法預測移動類用戶的下一跳和到達時間。和基礎Markov的46.8%的預測準確率相比，TBM通過優(yōu)化的預測準確率可以達到59.2%。試驗結果證明了對于不同移動特點的用戶，使用不同的預測算法進行移動模式發(fā)現會使預測效果更好，這對于網絡服務提供商、位置服務提供商等都有重大的意義。

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）