馬爾可夫模型在空間數據預取中的應用

李云錦,鐘耳順,王爾琪,黃躍峰

(中國科學院地理科學與資源研究所,北京 100101)

馬爾可夫模型在空間數據預取中的應用

李云錦,鐘耳順,王爾琪,黃躍峰

(中國科學院地理科學與資源研究所,北京 100101)

在地圖瀏覽空閑時間,將用戶下一時刻可能瀏覽的地圖數據預取至本地,可以減少下次瀏覽的等待時間。使用鄰近區域預取,方法簡單但命中率低且易造成網絡擁塞。為提高預取命中率,將瀏覽區域的中心點視為轉移狀態,用Markov鏈表示地圖瀏覽過程,使用Markov模型預測下一時刻可能瀏覽的數據。試驗驗證表明,Markov模型的應用有效地提高了瓦片數據的預取命中率,命中率可達40%。

預取;馬爾可夫;服務式地理信息系統

一、引 言

互聯網技術的進步推動了空間信息服務的發展,網絡成為人們獲取空間信息的主要途徑。然而,由于網絡帶寬的限制,用戶瀏覽空間數據時仍要長時間等待。減少等待時間常采用兩種方法:緩存 (caching)與預取 (prefetching)。

大多數 GIS服務器都采用了分層分塊緩存技術[1-3],預先將矢量或柵格數據輸出為大小固定的瓦片(tile)。在這種模式下,客戶端向服務器發送數據請求,服務器根據范圍參數返回已緩存的瓦片。用戶執行放大、縮小、漫游等操作后,瀏覽的范圍改變,客戶端向服務器發送新的請求。下一時刻可能瀏覽的瓦片與當前的瀏覽范圍及下一步的操作相關,因此,可以在空閑時猜測下一時刻可能瀏覽的數據并下載至本地。最為常用的方法為鄰近區域預取,即在空閑時下載與當前瀏覽區域相鄰的瓦片。如果下一步用戶執行平移操作,本地緩存可能已包括全部或部分所需的瓦片數據。鄰近區域預取只考慮了平移操作,準確率低且容易導致網絡擁塞。本文將重點討論分層分塊緩存模式下瓦片的預取,試圖借鑒網頁預取的研究成果,應用Markov模型提高預測的準確性。

在網頁預取中,Markov模型的應用已有較多的研究。Bestavros最早使用轉移概率矩陣描述用戶的瀏覽特征[4],模型簡單、有效。Sarukkai在 EPA服務器日志文件上的試驗表明[5],采用基本Markov鏈模型對用戶的瀏覽進行預測,其準確率可以達到70%左右。上述模型均采用一個Markov鏈描述所有用戶的瀏覽特征,存儲轉移概率矩陣的復雜度是網頁數量的平方,而且采用高階轉移矩陣所需的存儲空間還會成倍增加。為減少存儲空間、提高預測準確率,邢永康等人提出了多Markov鏈[6],將用戶分為不同類別并用不同的Markov鏈表示不同類別用戶的瀏覽特征。

空間數據瀏覽(包括矢量與柵格,以下統稱為地圖瀏覽)與網頁瀏覽具有相似性,可將任意時刻窗口中的地圖視為網頁,將地圖操作視為網頁中的超鏈接。不使用分層分塊,這樣的地圖有無窮多個,不能應用Markov預測模型。一種可能的方式是,使用分層分塊技術將數據劃分為有限個瓦片,用瓦片作為轉移狀態。然而,與網頁瀏覽不同,用戶可以同時瀏覽多個瓦片但只能瀏覽一個網頁。文獻[7-8]用前 k次瓦片移動方向作為轉移狀態,假定所有瓦片具有相同的轉移概率,提出了鄰近選擇Markov鏈(neighbor selection markov chain,NS MC)。該模型簡單,存儲開銷小,但是模型沒有充分考慮空間數據組織形式,適合于僅有一個比例尺的情形。此外,空間地物重要性不同,被訪問的幾率差別較大,NS MC模型不能體現這一差異特征。本文將結合服務器緩存技術與客戶端顯示技術,探討適用于地圖瀏覽的Markov預測模型。

二、Markov預測模型

在分層分塊緩存模式下,客戶端向服務器發送數據請求,服務器根據空間范圍返回相應的瓦片。僅就客戶端而言,地圖瀏覽過程表現為瓦片的位移與替換。如圖 1所示,Ti、Ti+1分別代表 i與 i+1時刻返回給同一客戶端的瓦片集合,Ti與 Ti+1大小相同,都包括 r×c個瓦片;xi、xi+1分別代表瓦片集合Ti與 Ti+1的中心。當前比例尺下,用戶的瀏覽過程可以表示為{x0,x1,…,xi|r×c},其中 xi∈X,X為當前比例尺下所有可能中心點的集合。因此,平移過程可以表示為相同比例尺的中心點轉移;放大、縮小等操作則可以表示為不同比例尺的中心點轉移。

圖1 地圖瀏覽過程示意圖

1.基本Markov模型

假設在地圖瀏覽過程中,中心點轉移是一個Markov過程。用隨機變量 X表示中心點集合,則中心點轉移過程構成一個隨機變量 X的取值序列,并且該序列滿足Markov性。一階Markov模型可以用三元組MC=〈X,A,λ〉表示,其中A表示轉移概率矩陣,λ為初始狀態分布。采用文獻[6]所述的學習方法,可以獲得基本模型 (為便于論述,本文將一階Markov模型稱為基本Markov模型)的各參數。模型不能直接預測可能訪問的瓦片數據,需要將中心點的概率向量轉換為瓦片的概率向量。

用V(t+1)表示下一時刻中心點的概率向量,取值最大的維對應的狀態 xi就是下一時刻最可能的中心點。用 n×m維矩陣 R=(rij)表示中心點與瓦片的映射關系,n為中心點個數,即狀態個數,m為瓦片的個數,rij∈{0,1}。根據中心點 xi、地圖窗口大小與瓦片大小,可以求得 xi對應的瓦片集合,若該集合中包含第 j個瓦片,則 rij取值為 1,否則取值為 0。

用L(t)表示 t時刻瓦片的概率向量,則 L(t+ 1)=V(t+1)×R。令 t時刻中心點對應的瓦片集合為 Tt,則預取的瓦片為不在 Tt中且 L(t+1)取值最大的 topN個瓦片。

2.高階Markov模型

在網頁預取中,采用高階Markov預測模型可以有效地提高預測準確率。然而,地圖瀏覽與網頁瀏覽過程不同,更高的階數可能不會提高預測準確率。以圖 2為例,訓練樣本由 2個瀏覽序列構成: A→B→C→D與D→C→B→A,兩個序列分別表示沿道路正向瀏覽與逆向瀏覽。

圖2 地圖瀏覽過程舉例

學習訓練樣本,得到一階與二階轉移概率矩陣分別為

采用加權平均法,令權值 w=[0.67 0.33],根據瀏覽序列 B→C計算下一時刻的概率向量,計算結果為:V=[0 0.582 5 0 0.417 5]。因此,下一時刻最可能的中心點為B。然而大量的觀察表明,地圖瀏覽具有較強的目的性,用戶沿道路或某一特定方向瀏覽地圖的幾率較大,因此順序瀏覽B、C后,用戶瀏覽 D的概率一般大于 B。使用多階Markov預測模型不能提高預測準確率。然而,在網頁預取中,類似圖 2所示的訓練樣本較少出現,這主要取決于站點的鏈接結構與網頁瀏覽的習慣。首先,多數站點的結構可以認為是一種層次結構,瀏覽網頁一般從高層次到低層次,而較少從低層次逐級返回至最上層;另外,當前網頁不一定包含歷史網頁的鏈接,用戶也較少瀏覽已經瀏覽過的網頁。

3.其他預測模型

高階Markov雖然使用了歷史信息,但由于地圖瀏覽的特殊性,準確率并未因提高轉移矩陣的階數而上升。另一種利用歷史信息的模型為多序Markov模型,使用連續 k次瀏覽的中心點作為轉移狀態。基本的Markov模型屬于多序Markov模型的一種,即 k=1。多序 Markov模型的學習類似于基本Markov模型的學習,只是需要事先將訓練樣本轉換為 k序狀態的序列。此外,多序Markov模型的狀態空間較大,歷史信息的匹配幾率較小,即歷史狀態很可能并未出現在訓練樣本中,此時預測失敗。為解決該問題,可以使用多序組合模型,對 1,2,…,k序預測結果加權平均。為便于討論,以下稱 1,2,…,k序預測加權平均模型為 k序Markov模型。

此外,為了降低存儲復雜度,還可以對Markov鏈聚類。首先采用加權平均法計算瀏覽序列的平均中心,用 dai表示 di的平均中心。di={xj|xj∈X},其中,wi為中心 xi對應的權值,且中心xi的比例尺越大,其權值wi越大。然后,根據序列的平均中心將樣本劃分為 k類,并建立每個類別的Markov模型,判別準則為空間距離。

4.存儲復雜度比較

令訓練樣本中中心點個數為 n,則基本Markov模型的存儲復雜度為 O(n2)。h階Markov模型需要存儲 1,2,…,h階轉移概率矩陣,因此存儲開銷是基本模型的 h倍,復雜度可表示為O(h×n2)。k序Markov模型需要存儲 1,2,…,k序的轉移概率矩陣,其中 1序概率矩陣的開銷為 n2,而 2,…,k序的狀態個數不等于 n。粗略計算,可以認為各序狀態均為 n,則存儲復雜度可表示為O(k×n2)。就基本聚類Markov模型而言,設平均每個類別的狀態數為n′,分類數目為 c,則每個子類的存儲復雜度約為O(n′2),總的存儲復雜度為 O(c×n′2)。

三、試驗分析

為建立Markov預測模型,我們使用了緩存服務器的 26 437條日志信息,信息包括:請求時間、IP地址、中心點坐標、當前比例尺與地圖窗口大小。對數據進行預處理,將日志文件整理為瀏覽序列集。預處理步驟為:①根據 IP地址將日志文件分解成獨立的請求記錄集;②將每個請求記錄集按時間排序,設立時間窗口閾值 tw,分割請求記錄集,時間間隔小于 tw的相鄰操作屬于同一瀏覽序列,然后所有序列組成用戶瀏覽序列集;③所有用戶的瀏覽序列集組成服務器瀏覽序列集,即訓練樣本。設 tw= 10m,記錄集被轉換為 2 011條請求序列,平均每個序列的長度為 26 437/2 011≈13。定義預取命中率為預取的瓦片恰好在下一時刻被訪問的幾率。

試驗 1比較了基本Markov模型與鄰近預取方法,對比結果如圖 3所示。從瀏覽序列集合中隨機選取了 80%的序列用于建立基本Markov模型,并將其余 20%序列用于驗證模型的有效性。試驗記錄了預取瓦片數(topN)在 1～60變化時,基本預測模型的預測準確率。隨著預取瓦片數的增加,雖然平均每次預測命中瓦片數呈上升趨勢,但預測的命中率呈下降趨勢。例如,topN=22時,平均每次預測命中的瓦片數為 6.19,預測準確率為 38.9%; topN=52時,平均每次預測命中的瓦片數為 8.34,預測準確率為 28.9%。試驗 1還記錄了Buffer大小分別為 1與 2時,鄰近預取的準確率。使用鄰近預取方法,預取的瓦片數目取決于客戶端窗口大小及Buffer大小。以 4×5客戶端為例,若 Buffer大小為1,則預取的瓦片數目為 (4+2)×(5+2)-4×5= 22,此時預取命中率為 8.28%;Buffer大小為 2時,預取的瓦片數目為 52,預取命中率為 3.79%。

圖 3 基本Markov模型與鄰近區域預取比較

使用與試驗 1相同的學習序列集與驗證序列集,試驗 2比較了基本Markov模型、高階Markov模型、多序Markov模型及聚類模型四類模型的預測準確率,比較結果如圖 4所示。結果表明,相對基本Markov模型而言,增加轉移概率矩陣的階數并沒有提高命中率;使用多序Markov模型可以提高命中率,且序列越長,命中率越高;使用系統聚類后,預取的命中率有所下降。以 topN=5為例,預取命中率由低至高排列為:基本聚類,二階Markov,基本Markov,二序Markov,三序 Markov,二序聚類,命中率分別為:46.3%,47.5%,49.9%,54.8%,56.7%, 57.3%。試驗 2中,基本聚類與二序聚類使用的類別數等于22。

圖4 四類模型的對比結果

分類的結果決定了模型的空間復雜度,試驗 2中的訓練樣本在聚類前具有 1 580個不同的中心點,因此基本模型的存儲開銷為 1 5802=2 496 400。采用系統聚類后,平均每個子類的狀態數小于聚類前的狀態數。試驗 3將訓練樣本劃分為 4～30個子樣本,統計每種聚類情形下所需的存儲空間;此外,試驗 3設定 topN=10,分別統計各種情形下的預取命中率,統計結果如圖 5所示。試驗結果表明,當分類數在 4～30間變化時,分類的數目對預取命中率影響較小,波動范圍在 2%以內;隨著分類數目的增加,存儲開銷呈下降趨勢。以類別數等于 20為例,平均每個子類包括 63個轉移狀態,總的存儲開銷約為 20×912=165 620,約為基本Markov模型存儲開銷的6.6%。這種分類方式下,聚類模型的預取命中率為43.5%,使用相同的 topN,基本Markov模型的命中率為44.4%,聚類模型的命中率略低。

圖 5 基本聚類Markov模型的命中率與存儲開銷

四、結 論

以瀏覽區域的中心點作為轉移狀態,可以建立地圖瀏覽的Markov模型。采用瓦片作為轉移狀態,一次地圖操作可能導致多個瓦片同時轉移,學習與預測過程都較本文所述方法復雜。試驗表明,基本Markov模型能有效提高預取的命中率,與鄰近區域預取方法對比,在同取 22個瓦片的情形下,兩者命中率分別為 38.9%與 8.3%。使用高階Markov模型,在網頁預取中一般能獲得更高的命中率,但在瓦片預取中命中率可能會更低,這主要取決于地圖瀏覽與網頁瀏覽的差異。多序Markov模型有效地利用了歷史信息,試驗表明,序列越長,命中率越高。使用空間聚類,能有效地降低存儲復雜度,但并沒有提高命中率,這主要是由于空間聚類過程并未充分利用歷史的訪問信息。如何優化聚類方法,提出更合理的聚類準則,在降低存儲復雜度的同時提高預取命中率,是今后研究的重點。

[1] 陳靜,龔健雅,朱欣焰,等.海量影像數據的Web發布與實現[J].測繪通報,2004(1):22-25.

[2] 陳能成,龔健雅,朱欣焰,等.多級緩沖提升海量影像數據在線服務質量[J].測繪通報,2007(6):19-22.

[3] 李銳,潘少明,喻占武.基于主動緩存的 P2P海量地形漫游瓦片調度算法 [J].測繪學報,2009,38(3): 236-249.

[4] BEST AVROSA.Using Speculation to Reduce ServerLoad and Service Time on theWWW[C]∥Proceedings of the Fourth InternationalConference on Information and Knowledge Management.Baltimore,Maryland,United States:ACM Press,1995:403-410.

[5] SARUKKA I R R.Link Prediction and Path Analysis U-singMarkov Chains[C]∥Proceedings of the 9th International World W ide Web Conference on Computer Networks. Amsterdam, The Netherlands:North-Holland Publishing Co,2000:377-386.

[6] 邢永康,馬少平.多 Markov鏈用戶瀏覽預測模型[J].計算機學報,2003,26(11):1510-1517.

[7] K IM Y S,K IM K C,K IM SD.Prefetching Tiled Internet Data Using a Neighbor SelectionMarkov Chain[J].Lecture Notes in Computer Science,2001,2060:103-115.

[8] LEE D H,K IM J S,K IM S D,et al.Adaptation of a Neighbor Selection Markov Chain for Prefetching Tiled Web GIS Data[J].Lecture Notes in Computer Science, 2002,2457:213-222.

MarkovM odel in Prefetching SpatialData

L I Yunjin,ZHONG Ershun,WANG Erqi,HUANG Yuefeng

0494-0911(2010)07-0001-04

P208

B

2009-09-01

國家 863計劃資助項目(2007AA12Z213,2007AA120501)

李云錦(1984—),男,湖北仙桃人,博士生,研究方向為 Service GIS、空間數據的多尺度表達。