研究与探讨922019年第5期收稿日期：2019-02-22基于数据挖掘的移动用户出行轨迹预测Travel Trajectory Prediction of Mobile Users Based on Data Mining为了解决移动用户出行轨迹预测的问题，首先利用用户出行轨迹数据进行语义化建模，然后根据语义位置和访问概率对用户群进行分类，再次，利用关联规则挖掘不同群体的频繁模式，最后，结合实时出行数据动态更新贝叶斯网络实现移动用户出行轨迹的实时预测。经过实验表明，该算法能够在一定程度上反映用户出行的目的和偏好，并具有很好的扩展性。语义化建模；关联规则；贝叶斯网络；轨迹预测In order to solve the problem of trajectory prediction for mobile users, this paper fi rstly uses trajectory data for semantic modeling, and then classifi es user groups according to their semantic location and access probability. The association rules are used to mine frequent patterns of different groups. Finally, the Bayesian network is updated dynamically with real-time travel data to realize real-time travel trajectory prediction for mobile users. Experiments show that the algorithm can reflect users ’travel purposes and preferences to a certain extent, and has good scalability. semantic modeling; association rule; Bayesian network; trajectory prediction（1.广州杰赛通信规划设计院有限公司，广东 广州 510310；2.中国联合网络通信有限公司广州市分公司，广东 广州 510310）(1. Guangzhou GCI Plan & Design Institute of Communication Engineering Co., Ltd., Guangzhou 510310, China;2. China United Network Communications Group Co., Ltd., Guangzhou Branch, Guangzhou 510310, China)【摘 要】【关键词】刘丽娴1，樊学宝2LIU Lixian1, FAN Xuebao2doi:10.3969/j.issn.1006-1010.2019.05.015 中图分类号：TN915.0文献标志码：A 文章编号：1006-1010(2019)05-0092-05引用格式：刘丽娴,樊学宝. 基于数据挖掘的移动用户出行轨迹预测[J]. 移动通信, 2019,43(5): 92-96.OSID：1 引言 移动用户行为具有很强的时空规律性，用户群体间的移动行为具有很高的相似性[1]。基于地理位置的服务与推荐已经成为当前的研究的热点，如：乔岩磊等扫描二维码与作者交流[Abstract] [Key words]人[2]利用高斯混合模型拟合连续时间下地点之间的转移概率推测用户的位置，但没有对不同群体用户的语义位置特点进行区别性对待，不能有效反应不同群体用户的出行特征。廖文芳[3]根据移动用户的出行位置信息进行社交平台的设计，但并没有考虑到利用用户在不同位置的逗留时长来反映用户在特定位置的停留偏好。姚迪等人[4]将用户时空轨迹数据转换成特定的语义

研究与探讨932019年第5期信息，以此推测用户的偏好和需求，但没有区分不同群体用户的停留时长和偏好。邱运芬等人[5]提出一种语义和概率的人群分类方法，根据语义位置分配情况获取用户对语义空间的访问向量，采用聚类的方法对用户进行人群的划分，结果表明，同类用户在语义位置空间的访问概率向量相似。研究者[3-8]从不同的角度研究地理位置的服务和推荐，包括用户的位置推测、用户出行群体特点，但并没有综合采用不同语义位置的停留偏好和停留时长来反映不同群体的出行偏好，同时，研究者并没有根据个体用户的实时出行轨迹来预测个体的未来轨迹。因此，本文在借鉴相关研究的基础上，针对传统用户预测没有考虑到用户群体分类的问题，提出一种基于移动轨迹的用户位置预测方法：在用户轨迹语义化的基础上，结合语义位置的概率向量采用聚类的方法对人群进行划分；在此基础上，采用关联规则挖掘不同群体的频繁模式；最后，结合实时出行数据动态更新贝叶斯网络实现移动用户出行轨迹的实时预测。2 出行轨迹的相关研究2.1 移动用户出行的时空序列模型移动用户出行的时空序列模型，是基于移动用户的时空数据进行数据挖掘的模型，通过对用户移动周期规律和相关参数的估计，能够获得移动用户在不同时间下位置概率分布的信息[6-7]，以此挖掘用户的行为模式与时间的关系。假设移动用户的出行时空序列为：Tri＝｛（L1, t1）, （L2, t2）, …, （Li, ti）, …, （Ln, tn）｝，其中，（Li, ti）表示用户在某个时间内出现在基站位置，那么，用户在不同时间的位置概率分布可表示为：P=(Xt=l|t∈[ti ,ti+△t]) (1)公式(1)表示，在特定的时间段内，用户在不同位置下的分布概率，相比于位置数据，移动用户出行的时空序列模型更能体现用户的出行偏好以及出行规律。2.2 移动用户语义位置模型在获取移动用户出行的时空序列后，能够根据用户在某一个位置的逗留时间，获取用户停留点。但是仅仅以地理轨迹的停留点来分析用户的出行规律似乎意义不大，因此，不少学者采用语义轨迹来反映用户的活动行为模式，通过语义位置对地理位置进行功能性的描述，推测用户在不同时间的不同行为特征以及其周边的环境信息，这些信息能够有效表征用户的语义位置。移动用户停留点的语义位置轨迹可用图1表示：图1 某用户停留点语义位置轨迹表示2.3 移动模式挖掘模型移动用户的行为具有群体的特征，移动用户出行的频繁模式，在一定程度上反映了移动用户出行行为具有一定的相似性[8]。在获取移动用户一段时间的语义位置轨迹的基础上，通过关联规则的相关算法就能挖掘用户在一段时间的出行规律。某一个用户在一段时间的语义位置轨迹如表1、表2所示。从表1、表2可知，<家，公司，餐馆，公园>是一种用户的语义位置轨迹模式，可以预测到用户在一周内去家、公司、餐馆、公园的频率为1/7，也就是一周中用户有一天会先去公司、然后去餐馆、公园。2.4 轨迹预测模型移动用户的出行位置是不断变换的，如果将用户在移动过程中经过的语义位置轨迹视为一个个的状态，那么可以通过状态更新的方式对用户的位置进行预测。语义位置轨迹是从地理位置提取高层的信息，使用语义位置轨迹能够更好预测用户的轨迹。而相似用户的语义位置轨迹，更能够解决位置预测中“新地点”的问题，当一个用户达到一个新的地点，无法通过自己的历史轨迹数据进行预测时，此时可以使用与之相似的用户轨迹数据进行预测。家学校餐馆住宅区学校休闲餐饮区公园家学校餐馆住宅区学校休闲餐饮区公园

研究与探讨942019年第5期3 基于动态贝叶斯网络动态更新的用户 出行轨迹本文提出一种基于动态贝叶斯网络的用户出行轨迹预测方法，其步骤如下：（1）提取移动用户的历史位置并对进行语义位置的挖掘；（2）采用Apriori算法挖掘语义频繁模式；（3）基于用户的语义频繁模式和语义位置概率进行用户分群；（4）利用群体初始语义位置偏好生成初始的贝叶斯网络；（5）利用个体用户的实时语义位置动态更新贝叶斯网络，实现个体的轨迹预测。3.1 移动用户的语义位置轨迹挖掘如表3所示，本文通过提取某个城市3G/4G的10万用户的出行数据，提取的字段包括：用户ID、小区编号、发生业务的时间戳。语义位置是对地理环境的定性描述，在获取用户的小区编号的基础上，采用反向的地理编码服务（百度等提供的编码接口）将基站位置转化为地址信息，再利用POI数据库获取当前基站的语义位置。语义位置示例如表4所示：表4 语义位置示例ID开始日期开始时间结束时间开始站点结束站点逗留时长语义标签12018080121020921203421656202011105家1201808021823421829192230120156383公司...1201808061146351150082310121656213商场3.2 移动用户语义频繁模式挖掘在挖掘用户语义位置的基础上，需要从大量的语义位置数据库中找到满足给定一定条件（满足最小支持度和最小置信度）的用户出行频繁模式。其步骤为：（1）找出所有的频繁项目集；（2）给定最小的支持度和置信度，找出满足特定规则的频繁项集。本文考虑到移动用户出行数据的特点，采用Apriori算法提取用户的语义标签数据集。其结果如表5所示：表5 某用户语义频繁模式挖掘结果语义位置轨迹ID语义位置轨迹模式支持度1<家，公司> 4/9 2<家，公司，餐馆> 3/73<家，商场，公园> 3/84<家，公司，餐馆，商场> 1/45<家，餐馆，商场，公司，公园> 1/17表1 语义位置轨迹示例用户ID语义位置轨迹1<家,公司，餐馆，商场，家>1<家,公司，餐馆，家>1<家,公司，公园，餐馆，家>1<家，餐馆，家>1<家，商场，家>1<家,公司，餐馆，商场，家>1<家,公司，餐馆，家>表2 语义位置轨迹模式示例语义位置轨迹ID语义位置轨迹模式支持度1<家>12<公司>5/73<家，公司>5/74<家，餐馆>6/75<家，商场>3/76<家，公司，餐馆，公园>1/7表3 移动用户位置轨迹表ID开始日期开始时间结束时间开始站点结束站点12018080121020921203421656202011201808021823421829192230120156...1201808061146351150082310121656

研究与探讨952019年第5期3.3 基于语义位置和概率的用户分群相似用户的语义位置轨迹能够更好预测用户的出行轨迹，因此，在获取每一个用户的语义频繁模式的基础上，结合用户在每一个语义位置上出现的概率进行分群。假设语义位置集为{l1, l2, l3, …, ln}，某一个用户在每一个语义位置上出现的概率向量为{p1, p2, p3, …, pn}，且p1+p2+p3+…+pn=1。通过采用k-means算法对全体用户的概率向量进行聚类，得到基于语义位置和概率的用户分群结果。3.4 采用贝叶斯网络动态预测用户出行轨迹贝叶斯网络是基于概率推理的图形化网络[9]，在获取群体的移动用户历史出行数据基础上，网络就会推断同一群体移动用户出行偏好，当实时输入移动用户的实时位置时，贝叶斯网络的概率就会动态调整。某用户群体初始语义位置偏好的贝叶斯网络如图2所示：当移动用户产生新的移动轨迹时，贝叶斯网络的概率会自动更新，运营商会根据当前用户的移动轨迹和逗留时长（如果逗留时长超过设定的阈值，则把将贝叶斯网络的概率实施动态更新；否则不作更新）进行实时的动态更新，预测移动用户去往某一个语义位置的概率。从实验数据得到，用户在语义位置的平均逗留时长阈值为53分钟，也就是说，用户在某一个语义位置的逗留时长超过53分钟时，初始语义位置偏好的贝叶斯网络节点将被激活实现用户实时语义位置的预测。其实验结果与用户真实的逗留偏好比较吻合，随着用户实时轨迹数据的增加，运营商对移动用户的出行轨迹预测将会更加的准确，运营商可以为不同的用户提供更加个性化的地理位置服务，提高位置服务提供商的效率和利润。4 结束语本文提出一种融合语义位置数据的位置预测，结合了用户的出行行为和周边的环境位置来表征用户的语义位置；利用用户语义位置的相似性实现用户的分群，利用分群的出行数据构造贝叶斯网络；最后利用移动用户的实时出行语义位置动态更新贝叶斯网络并实现移动用户出行轨迹的预测。相比传统的地理位置的预测，本文提出的语义轨迹更能反映用户的活动行为模式，能够更好推测用户在不同时间的各种行为模式，更有效表征用户的行为。学校 Yes 50.0 No 50.0 公司 Yes 1.04 No 99.0 餐馆 Yes 50.0 No 50.0 家 Yes 60.0 No 40.0 公园 Yes 55.3 No 44.7 商场 Yes 15.2 No 84.8 学校 Yes 50.0 No 50.0 公司 Yes 50.0 No 50.0 餐馆 Yes 50.0 No 50.0 家 Yes 1.0 No 99.0 公园 Yes 50.0 No 50.0 商场 Yes 50.0 No 50.0 图2 某用户群体初始语义位置偏好的贝叶斯网络图3 某用户实时语义位置动态更新贝叶斯网络参考文献：[1] 崔家祥. 基于移动通信数据的用户移动行为分析与位置预测[D]. 北京: 北京邮电大学, 2018.[2] 乔岩磊,杜永萍,赵东玥. 基于高斯分析的马尔可夫位置预测方法[J]. 计算机技术与发展, 2018,28(1): 41-44.

研究与探讨962019年第5期（上接第91页）刘丽娴（orcid.org/0000-0001-8553-1254）：中级工程师，学士毕业于北京邮电大学，现任职于广州杰赛通信规划设计院有限公司，主要从事移动用户的行为分析、人工智能的应用。樊学宝：高级工程师，硕士毕业于北京邮电大学，现任职于中国联合网络通信有限公司广州市分公司，主要从事移动网络优化规划。作者简介[3] 廖文芳. 基于位置的移动社交网络平台的设计[J]. 山东工业技术, 2018(11): 139.[4] 姚迪,张超,黄建辉,等. 时空数据语义理解:技术与应用[J]. 软件学报, 2018,29(7): 196-223.[5] 邱运芬,张晖,李波,等. 一种基于语义位置和概率的人群分类方法[J]. 数据采集与处理, 2018,149(3): 154-162.[6] 连德富,张富铮,王英子,等. 移动数据挖掘[Ｍ]. 北京: 机械工业出版社, 2017.[7] 钱琨. 基于蜂窝信令数据的移动轨迹清洗和预测方法研究与实现[D]. 成都: 西南交通大学, 2016.[8] 陈少权. 基于改进LCSS的移动用户轨迹相似性查询算法研究[J]. 移动通信, 2017,41(6): 77-82. [9] 张小可,沈文明,杜翠凤. 贝叶斯网络在用户画像构建中的研究[J]. 移动通信, 2016,40(22): 22-26.[10] 付莉莉. 融合语义信息的位置预测技术研究[D]. 北京: 北京邮电大学, 2013. ★陈卓（orcid.org/0000-0001-9574-8676）：硕士研究生在读于宁波大学，研究方向为信息安全、计算机视觉与模式识别。张荣：现任宁波大学副教授、研究生导师，博士，研究方向为数字取证、信息安全。郭立君：现任宁波大学教授、研究生导师，博士，研究方向为计算机视觉与模式识别、移动互联网及其应用。作者简介[9] Krzysztof Kowalczyk. Sumatra PDF[EB/OL]. (2018-10-20)[2019-01-04]. https://www.sumatrapdfreader.org/free-pdf-reader.html.[10] 赵刚,于悦,黄敏桓,等. PDF阅读器字体解析引擎的测试方法[J]. 清华大学学报：自然科学版, 2018,58(3): 266-271.[11] 李强,刘时进. PDF阅读器的设计与实现[J]. 计算机工程与设计, 2010,31(7): 1635-1638.[12] 冯博文,汲如意,于佳耕. Linux中浏览器兼容ActiveX控件机制的设计与实现[J]. 计算机应用与软件, 2017,34(10): 14-19.[13] Lozupone V. Analyze encryption and public key infrastructure (PKI)[J]. International Journal of Information Management, 2018,38(1): 42-44.[14] 赵菁华,冯惠. PKI的互联技术——桥接CA研究[J]. 计算机应用与软件, 2009,26(5): 249-251. ★