面向稀疏轨迹数据的位置预测方法研究

作     者：贾振美 

作者单位：东北大学 

学位级别：硕士

导师姓名：林树宽

授予年度：2014年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：稀疏轨迹数据 频繁轨迹模式 模式挖掘 位置预测 用户聚类 

摘      要：随着很多基于位置服务的兴起,位置预测发展成了一项必要的任务,比如,通过预测用户的目的地,向用户推荐旅游景点的信息,或者发布一些超市、商场的折扣信息等。位置预测就是根据用户的历史轨迹数据,预测下一个可能的位置。由于受到一些实际因素的影响,比如,传输过程中数据包的丢失、采样时间间隔过长、位置更新不及时等,移动对象的位置更新可能会遗漏部分路径信息,所以GPS等移动设备采集到的数据存在一个问题,即数据稀疏问题。已有的研究方案多数都不适用于稀疏数据上的位置预测,如果直接针对稀疏数据进行挖掘,预测的准确率会很低。所以本文就稀疏数据问题,提出了一个位置预测研究方案。为了提高预测的准确率,本文在挖掘轨迹模式的过程中考虑了时间因素对预测的影响,体现了用户的移动规律偏向于就近时间段的特性;同时,将包含频繁轨迹模式的轨迹id保存起来,避免了重复扫描数据集,提高了挖掘的效率。本文的主要贡献如下：首先,针对稀疏数据,本文提出了处理稀疏轨迹数据的具体方法,缓解了因数据稀疏导致的预测准确率低的问题。其次,鉴于老化的轨迹对预测准确性的影响,本文提出了基于保鲜度的支持度计算方法,在挖掘轨迹模式的过程中考虑了时间因素,提高了预测的准确率。再次,针对模式挖掘问题,将轨迹模式与网络拓扑图联系起来,将覆盖区域用带权有向图表示,提出了轨迹标识列表的概念,减少了候选模式的数量,避免了重复扫描原始数据集,提高了算法的效率。最后,提出了一种相似用户聚类算法,使用同类用户的数据进行预测,缓解了数据稀疏问题,同时,提出了一个匹配策略,既能实现完全匹配,又能实现部分匹配,提高了预测的准确率。通过理论分析和实验评估,验证了本文提出的基于稀疏轨迹数据的位置预测方法在理论上的可行性和操作中的有效性。