基于改进LCSS的移动用户轨迹相似性查询算法研究

陈少权

【摘 要】为了解决由于移动用户轨迹数据具有随机性和繁杂性导致算法效率和精度低的问题，首先抽取用户轨迹时间位置序列，然后基于用户的逗留时长采用加权FP树挖掘移动用户的常驻区域以解决用户轨迹的随机性，最后提出结合用户出行的时间和地理因素的LCSS算法衡量用户轨迹相似性。实验证明，该算法具有一定的有效性和扩展性。

【关键词】轨迹相似性 FP树 最长公共子序列 时间相似性系数

1 引言

随着移动通信和移动应用的快速发展，用户对手机的使用率及依赖性不断提高，移动运营商积累了大量移动用户实时记录的定位数据。分析移动用户位置的相似性，提取移动用户的相似路径在出行路径预测、兴趣区域发现、轨迹聚类、个性化路径推荐等领域具有广泛的应用。如何利用丰富的移动用户定位数据找到合适轨迹的表示方法，如何高效计算移动用户轨迹间的相似性已经成为工业界和学术界的研究热点[1]。贾振美针对移动对象的稀疏数据处理的问题，提出了稀疏数据处理的具体方法，并结合时间因素挖掘用户的频繁轨迹模式，利用相似用户聚类方法实现同类用户位置的预测[2]。张用川通过对手机用户移动轨迹数据的语义环境信息进行研究，创新性提出地理位置语义化的方法，挖掘用户出行模[3]。罗家顺通过预先对用户位置进行定义建立用户-位置信息模型，然后结合时间效应利用协同过滤的算法找到区域性相似的用户，实现实时的多维动态用户兴趣推荐[4]。……