基于灰色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 模型應用于移動位置預測比單用灰色模型準確率更高，且該模型算法簡單，通過編程在計算機上實現，可移植性強，具有較強的實用性。