移动网络中的用户移动模式预测

何海洋 北京邮电大学数据科学中心，网络体系构建与融合北京市重点实验室

移动网络中的用户移动模式预测

何海洋 北京邮电大学数据科学中心，网络体系构建与融合北京市重点实验室

随着移动互联网的快速发展，利用移动数据分析移动用户的移动性成为移动互联网研究的一大热点。本文提出了基于时间的Markov（Time-Based Markov，TBM）算法，并利用南方某省运营商3周的连续数据，使用TBM算法对移动类用户进行位置预测。通过试验，证明了所提出的方法比基础Markov方法有更高的预测准确率，这对运营商和位置服务提供商有重要意义。

移动模式；预测准确率；用户聚类

1 引言

随着移动互联网用户数量和通信数据量的不断增长，通过移动互联网上真实流量数据分析用户行为意义重大。通过移动网络数据可以进行数据使用、应用使用、移动模式等用户行为分析。在各类用户行为分析中，分析用户移动模式并进行用户移动性预测有着重要意义。通过研究移动模式，运营商可以达到用户移动性预测、用户移动性管理等目的。

用户移动模式的研究大多根据用户历史路径，通过机器学习算法调整历史样本数据调整分类器参数，从而预测某个用户将来的位置。LZ-Based算法通过路径树的不断更新实现预测。Markov算法没路径树的建立过程，而是直接匹配历史路径，并可以改变匹配阶数。贝叶斯算法、神经网络算法、隐式马尔可夫模型等也可用于移动性预测。

以上算法将空间上下文作为影响用户移动性预测的主要因素。而近些年，越来越多的研究者们开始考虑时间因素对预测结果的影响。

除了空间和时间因素，希望将一个用户特定的移动特点对用户移动性的影响因素加以考虑。例如，对于预测一个用户在某一段时间的位置这样的问题，预测一个朝九晚五工作的白领比预测一个天天跑业务的销售员更容易，因为白领的移动习惯更规律。所以，希望进一步地证明对于拥有不同时空移动特点的用户，应该使用不同方法进行预测。

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移动数据进行试验，数据包括连续3周，具体时间为2013.10.10—2013.10.31。可以从话单数据中提取出用户ID、基站IP、访问时间、状态等信息，具体数据的大体结构可参见表1，其中基站IP可通过IP-经纬度对照表转化为经纬度信息。

表1 输入数据形式表

所有数据包含3474个用户和729个eNodeBs（4G基站），考虑到某些用户在数据集中有非常少的记录，使得很难分析这些用户的移动性。在试验中为了让每个用户有足够多的记录来分析，首先将连接基站数少于10个和连接次数少于500次的用户过滤掉；由于TBM本质为预测用户下一跳，更适合预测移动性较强的用户，于是又通过基于熵值的用户聚类算法将用户聚类为固定类用户和移动类用户，两类用户数量分别为1409和795。对于固定类用户，可以使用基于空间概率分布的方法预测用户在某一段时间的位置。后续的试验中将针对795个移动类用户进行移动模式预测。处于数据安全原因，已经将用户的隐私信息通过Hash处理。

4 用户移动模式预测

基于TBM算法，将在本节预测移动用户的下一跳，如果一个用户在一段时间内一直连着相同的小区基站，将这些记录点全部合并为一个记录，同时到达时间也设置为第一个记录的时间。用前两周的数据做训练，然后如果一个用户在第三周总共移动了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算法的影响，设置时间阈值在区间［0.5h，5h］的变化，以0.5h为步长，对移动用户针对每一个不同的时间阈值使用TBM进行预测。得到如图1所示的结果，以时间阈值Ts为横坐标，以准确率为纵坐标。从图1中可以知道时间阈值的最好选择是2.5～3h。如果想要找到一个移动用户在某个时间点如早上10∶00的轨迹，那么最好是观察该用户每天从早晨7∶30—12∶30的移动轨迹。

图1 时间差与准确率的关系

接下来，进一步通过观察预测效果较差的结果来改进算法。首先，在图2中画出了一些随机移动类用户的移动轨迹。在每个子图中，每个点代表用户连接的一个基站，两个点之间的线代表用户从其中一点移动到另一点。其中，容易预测出错的一些点已经圈标注出来。

通过观察，发现用户在容易预测出错的区域通常有这样的移动轨迹：假设该用户当前在，通过观察他的历史路径，该用户移动到和的概率几乎是相同的。这暗示可以考虑提高TBM的阶数，即考虑的前一位置：如果前一位置是，则他更可能去；如果前一位置是，则更可能去。基于此，改变了TBM算法中的第5步：定义作为的前一位置，如果选择最大概率的和是同一位置，则选择拥有第二大概率的。通过这种方式改进TBM算法，移动类用户的平均预测准确率达到了59.2%。

图2 示例用户移动轨迹

5 结束语

本文提出了TBM算法预测移动类用户的下一跳和到达时间。和基础Markov的46.8%的预测准确率相比，TBM通过优化的预测准确率可以达到59.2%。试验结果证明了对于不同移动特点的用户，使用不同的预测算法进行移动模式发现会使预测效果更好，这对于网络服务提供商、位置服务提供商等都有重大的意义。

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）