基于灰色Markov 模型的移动对象位置预测研究∗

周 冰 李 聪 王铃鑫 郑楚翔

（1.武汉科技大学城市学院信息工程学部 武汉 430083）（2.武汉大学计算机学院 武汉 430000）

1 引言

位置预测则是轨迹数据挖掘的一个重要分支［1～2］，通过位置预测，可以解决基于位置的信息推荐、城市道路交通优化、国家人口迁徙分析等一系列问题［3～4］。

将移动对象位置预测问题抽象为单变量灰色系统［5］构建GM（1，1）模型［6］，模型优点在于所需数据量小，短期预测精确度高，缺点在于对长期预测和波动性较大的数据列的拟合较差。与之相反，Markov 模型［7］能较好地进行长期预测和对随机波动性较大的数据列进行预测。本文尝试将Markov 模型引入到灰色模型中［8］，构建灰色Markov 模型［9～10］。利用GM（1，1）模型揭示移动位置数据列的发展变化总趋势，同时利用Markov 模型来确定状态规律，增强预测的准确性［11］。

2 GM（1，1）模型

灰色系统理论认为，尽管客观表象复杂，但总是有整体功能的，因此必然蕴含某种内在规律。关键在于如何选择适当的方式去挖掘和利用它。一切灰色序列都能通过某种生成弱化其随机性，显现其规律性。数据生成的常用方式有累加生成、累减生成和加权累加生成等。

3 应用

3.1 数据的选取

提取GeoLife 2008 年10 月23 日04：20：07～04：24：07 该段时间内该对象轨迹［12］数据建立灰色模型［13］。

3.2 GM（1，1）灰色模型

由表1 用户移动轨迹经纬度数据分别建立GM（1，1）模型，得到经度的灰色累加序列为

3.3 预测结果及模型检验

由上述计算过程得到未来五分钟内该对象经纬度预测值如表2所示。

表2 GPS移动轨迹数据GM（1，1）模型预测值

原始数据列与GM（1，1）预测值数据列对比图见图1。

图1 实际数据列与预测值数据列比较图

预测数据与实际数据在地图上的路径轨迹见图2，图中实线标记表示GeoLife中与时间对应的实际地理位置，虚线标记表示通过GM（1，1）模型进行预测的得到的地理位置。

图2 预测数据与实际数据移动轨迹图

4 灰色Markov模型及应用

具有Markov 性的随机过程称为Markov 过程。Markov 性定义如下：在已知过程t0时刻所处的状态条件下，过程在时刻t0之后所处的状态的条件分布，与过程在时刻t0之前所处的状态无关［14］。

4.1 确定状态转移概率矩阵

将对象划分为Ei(i=1，2，…，n)等状态后，定义pij表示数据由状态Ei经过一步转为状态Ej的概率，由此可以得到一步状态转移概率矩阵［15］，为结果修正做准备。

状态转移矩阵

4.2 Markov修正结果

图3 中双线标记表示将GM（1，1）得到的预测数据经过Markov修正后的地理位置。

图3 预测、修正、实际移动路径对比图

从图3 可以看出GM（1，1）模型经过Markov 修正后，精度明显提高，预测结果更接近实际值。由此可见，灰色Markov 模型的预测准确度及可靠性要明显优于GM（1，1）模型。

5 结语

灰色Markov 模型应用于移动位置预测比单用灰色模型准确率更高，且该模型算法简单，通过编程在计算机上实现，可移植性强，具有较强的实用性。