周 冰 李 聰 王鈴鑫 鄭楚翔

（1.武漢科技大學城市學院信息工程學部 武漢 430083）（2.武漢大學計算機學院 武漢 430000）

1 引言

位置預測則是軌跡數(shù)據(jù)挖掘的一個重要分支［1～2］，通過位置預測，可以解決基于位置的信息推薦、城市道路交通優(yōu)化、國家人口遷徙分析等一系列問題［3～4］。

將移動對象位置預測問題抽象為單變量灰色系統(tǒng)［5］構(gòu)建GM（1，1）模型［6］，模型優(yōu)點在于所需數(shù)據(jù)量小，短期預測精確度高，缺點在于對長期預測和波動性較大的數(shù)據(jù)列的擬合較差。與之相反，Markov 模型［7］能較好地進行長期預測和對隨機波動性較大的數(shù)據(jù)列進行預測。本文嘗試將Markov 模型引入到灰色模型中［8］，構(gòu)建灰色Markov 模型［9～10］。利用GM（1，1）模型揭示移動位置數(shù)據(jù)列的發(fā)展變化總趨勢，同時利用Markov 模型來確定狀態(tài)規(guī)律，增強預測的準確性［11］。

2 GM（1，1）模型

灰色系統(tǒng)理論認為，盡管客觀表象復雜，但總是有整體功能的，因此必然蘊含某種內(nèi)在規(guī)律。關(guān)鍵在于如何選擇適當?shù)姆绞饺ネ诰蚝屠盟?。一切灰色序列都能通過某種生成弱化其隨機性，顯現(xiàn)其規(guī)律性。數(shù)據(jù)生成的常用方式有累加生成、累減生成和加權(quán)累加生成等。

3 應用

3.1 數(shù)據(jù)的選取

提取GeoLife 2008 年10 月23 日04：20：07～04：24：07 該段時間內(nèi)該對象軌跡［12］數(shù)據(jù)建立灰色模型［13］。

3.2 GM（1，1）灰色模型

由表1 用戶移動軌跡經(jīng)緯度數(shù)據(jù)分別建立GM（1，1）模型，得到經(jīng)度的灰色累加序列為

3.3 預測結(jié)果及模型檢驗

由上述計算過程得到未來五分鐘內(nèi)該對象經(jīng)緯度預測值如表2所示。

表2 GPS移動軌跡數(shù)據(jù)GM（1，1）模型預測值

原始數(shù)據(jù)列與GM（1，1）預測值數(shù)據(jù)列對比圖見圖1。

圖1 實際數(shù)據(jù)列與預測值數(shù)據(jù)列比較圖

預測數(shù)據(jù)與實際數(shù)據(jù)在地圖上的路徑軌跡見圖2，圖中實線標記表示GeoLife中與時間對應的實際地理位置，虛線標記表示通過GM（1，1）模型進行預測的得到的地理位置。

圖2 預測數(shù)據(jù)與實際數(shù)據(jù)移動軌跡圖

4 灰色Markov模型及應用

具有Markov 性的隨機過程稱為Markov 過程。Markov 性定義如下：在已知過程t0時刻所處的狀態(tài)條件下，過程在時刻t0之后所處的狀態(tài)的條件分布，與過程在時刻t0之前所處的狀態(tài)無關(guān)［14］。

4.1 確定狀態(tài)轉(zhuǎn)移概率矩陣

將對象劃分為Ei(i=1，2，…，n)等狀態(tài)后，定義pij表示數(shù)據(jù)由狀態(tài)Ei經(jīng)過一步轉(zhuǎn)為狀態(tài)Ej的概率，由此可以得到一步狀態(tài)轉(zhuǎn)移概率矩陣［15］，為結(jié)果修正做準備。

狀態(tài)轉(zhuǎn)移矩陣

4.2 Markov修正結(jié)果

圖3 中雙線標記表示將GM（1，1）得到的預測數(shù)據(jù)經(jīng)過Markov修正后的地理位置。

圖3 預測、修正、實際移動路徑對比圖

從圖3 可以看出GM（1，1）模型經(jīng)過Markov 修正后，精度明顯提高，預測結(jié)果更接近實際值。由此可見，灰色Markov 模型的預測準確度及可靠性要明顯優(yōu)于GM（1，1）模型。

5 結(jié)語

灰色Markov 模型應用于移動位置預測比單用灰色模型準確率更高，且該模型算法簡單，通過編程在計算機上實現(xiàn)，可移植性強，具有較強的實用性。