馬爾可夫模型在空間數(shù)據(jù)預(yù)取中的應(yīng)用

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

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

馬爾可夫模型在空間數(shù)據(jù)預(yù)取中的應(yīng)用

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

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

在地圖瀏覽空閑時(shí)間,將用戶下一時(shí)刻可能瀏覽的地圖數(shù)據(jù)預(yù)取至本地,可以減少下次瀏覽的等待時(shí)間。使用鄰近區(qū)域預(yù)取,方法簡(jiǎn)單但命中率低且易造成網(wǎng)絡(luò)擁塞。為提高預(yù)取命中率,將瀏覽區(qū)域的中心點(diǎn)視為轉(zhuǎn)移狀態(tài),用Markov鏈表示地圖瀏覽過(guò)程,使用Markov模型預(yù)測(cè)下一時(shí)刻可能瀏覽的數(shù)據(jù)。試驗(yàn)驗(yàn)證表明,Markov模型的應(yīng)用有效地提高了瓦片數(shù)據(jù)的預(yù)取命中率,命中率可達(dá)40%。

預(yù)取;馬爾可夫;服務(wù)式地理信息系統(tǒng)

一、引 言

互聯(lián)網(wǎng)技術(shù)的進(jìn)步推動(dòng)了空間信息服務(wù)的發(fā)展,網(wǎng)絡(luò)成為人們獲取空間信息的主要途徑。然而,由于網(wǎng)絡(luò)帶寬的限制,用戶瀏覽空間數(shù)據(jù)時(shí)仍要長(zhǎng)時(shí)間等待。減少等待時(shí)間常采用兩種方法:緩存 (caching)與預(yù)取 (prefetching)。

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

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

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

二、Markov預(yù)測(cè)模型

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

圖1 地圖瀏覽過(guò)程示意圖

1.基本Markov模型

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

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

用L(t)表示 t時(shí)刻瓦片的概率向量,則 L(t+ 1)=V(t+1)×R。令 t時(shí)刻中心點(diǎn)對(duì)應(yīng)的瓦片集合為 Tt,則預(yù)取的瓦片為不在 Tt中且 L(t+1)取值最大的 topN個(gè)瓦片。

2.高階Markov模型

在網(wǎng)頁(yè)預(yù)取中,采用高階Markov預(yù)測(cè)模型可以有效地提高預(yù)測(cè)準(zhǔn)確率。然而,地圖瀏覽與網(wǎng)頁(yè)瀏覽過(guò)程不同,更高的階數(shù)可能不會(huì)提高預(yù)測(cè)準(zhǔn)確率。以圖 2為例,訓(xùn)練樣本由 2個(gè)瀏覽序列構(gòu)成: A→B→C→D與D→C→B→A,兩個(gè)序列分別表示沿道路正向?yàn)g覽與逆向?yàn)g覽。

圖2 地圖瀏覽過(guò)程舉例

學(xué)習(xí)訓(xùn)練樣本,得到一階與二階轉(zhuǎn)移概率矩陣分別為

采用加權(quán)平均法,令權(quán)值 w=[0.67 0.33],根據(jù)瀏覽序列 B→C計(jì)算下一時(shí)刻的概率向量,計(jì)算結(jié)果為:V=[0 0.582 5 0 0.417 5]。因此,下一時(shí)刻最可能的中心點(diǎn)為B。然而大量的觀察表明,地圖瀏覽具有較強(qiáng)的目的性,用戶沿道路或某一特定方向?yàn)g覽地圖的幾率較大,因此順序?yàn)g覽B、C后,用戶瀏覽 D的概率一般大于 B。使用多階Markov預(yù)測(cè)模型不能提高預(yù)測(cè)準(zhǔn)確率。然而,在網(wǎng)頁(yè)預(yù)取中,類(lèi)似圖 2所示的訓(xùn)練樣本較少出現(xiàn),這主要取決于站點(diǎn)的鏈接結(jié)構(gòu)與網(wǎng)頁(yè)瀏覽的習(xí)慣。首先,多數(shù)站點(diǎn)的結(jié)構(gòu)可以認(rèn)為是一種層次結(jié)構(gòu),瀏覽網(wǎng)頁(yè)一般從高層次到低層次,而較少?gòu)牡蛯哟沃鸺?jí)返回至最上層;另外,當(dāng)前網(wǎng)頁(yè)不一定包含歷史網(wǎng)頁(yè)的鏈接,用戶也較少瀏覽已經(jīng)瀏覽過(guò)的網(wǎng)頁(yè)。

3.其他預(yù)測(cè)模型

高階Markov雖然使用了歷史信息,但由于地圖瀏覽的特殊性,準(zhǔn)確率并未因提高轉(zhuǎn)移矩陣的階數(shù)而上升。另一種利用歷史信息的模型為多序Markov模型,使用連續(xù) k次瀏覽的中心點(diǎn)作為轉(zhuǎn)移狀態(tài)?；镜腗arkov模型屬于多序Markov模型的一種,即 k=1。多序 Markov模型的學(xué)習(xí)類(lèi)似于基本Markov模型的學(xué)習(xí),只是需要事先將訓(xùn)練樣本轉(zhuǎn)換為 k序狀態(tài)的序列。此外,多序Markov模型的狀態(tài)空間較大,歷史信息的匹配幾率較小,即歷史狀態(tài)很可能并未出現(xiàn)在訓(xùn)練樣本中,此時(shí)預(yù)測(cè)失敗。為解決該問(wèn)題,可以使用多序組合模型,對(duì) 1,2,…,k序預(yù)測(cè)結(jié)果加權(quán)平均。為便于討論,以下稱(chēng) 1,2,…,k序預(yù)測(cè)加權(quán)平均模型為 k序Markov模型。

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

4.存儲(chǔ)復(fù)雜度比較

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

三、試驗(yàn)分析

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

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

圖 3 基本Markov模型與鄰近區(qū)域預(yù)取比較

使用與試驗(yàn) 1相同的學(xué)習(xí)序列集與驗(yàn)證序列集,試驗(yàn) 2比較了基本Markov模型、高階Markov模型、多序Markov模型及聚類(lèi)模型四類(lèi)模型的預(yù)測(cè)準(zhǔn)確率,比較結(jié)果如圖 4所示。結(jié)果表明,相對(duì)基本Markov模型而言,增加轉(zhuǎn)移概率矩陣的階數(shù)并沒(méi)有提高命中率;使用多序Markov模型可以提高命中率,且序列越長(zhǎng),命中率越高;使用系統(tǒng)聚類(lèi)后,預(yù)取的命中率有所下降。以 topN=5為例,預(yù)取命中率由低至高排列為:基本聚類(lèi),二階Markov,基本Markov,二序Markov,三序 Markov,二序聚類(lèi),命中率分別為:46.3%,47.5%,49.9%,54.8%,56.7%, 57.3%。試驗(yàn) 2中,基本聚類(lèi)與二序聚類(lèi)使用的類(lèi)別數(shù)等于22。

圖4 四類(lèi)模型的對(duì)比結(jié)果

分類(lèi)的結(jié)果決定了模型的空間復(fù)雜度,試驗(yàn) 2中的訓(xùn)練樣本在聚類(lèi)前具有 1 580個(gè)不同的中心點(diǎn),因此基本模型的存儲(chǔ)開(kāi)銷(xiāo)為 1 5802=2 496 400。采用系統(tǒng)聚類(lèi)后,平均每個(gè)子類(lèi)的狀態(tài)數(shù)小于聚類(lèi)前的狀態(tài)數(shù)。試驗(yàn) 3將訓(xùn)練樣本劃分為 4～30個(gè)子樣本,統(tǒng)計(jì)每種聚類(lèi)情形下所需的存儲(chǔ)空間;此外,試驗(yàn) 3設(shè)定 topN=10,分別統(tǒng)計(jì)各種情形下的預(yù)取命中率,統(tǒng)計(jì)結(jié)果如圖 5所示。試驗(yàn)結(jié)果表明,當(dāng)分類(lèi)數(shù)在 4～30間變化時(shí),分類(lèi)的數(shù)目對(duì)預(yù)取命中率影響較小,波動(dòng)范圍在 2%以?xún)?nèi);隨著分類(lèi)數(shù)目的增加,存儲(chǔ)開(kāi)銷(xiāo)呈下降趨勢(shì)。以類(lèi)別數(shù)等于 20為例,平均每個(gè)子類(lèi)包括 63個(gè)轉(zhuǎn)移狀態(tài),總的存儲(chǔ)開(kāi)銷(xiāo)約為 20×912=165 620,約為基本Markov模型存儲(chǔ)開(kāi)銷(xiāo)的6.6%。這種分類(lèi)方式下,聚類(lèi)模型的預(yù)取命中率為43.5%,使用相同的 topN,基本Markov模型的命中率為44.4%,聚類(lèi)模型的命中率略低。

圖 5 基本聚類(lèi)Markov模型的命中率與存儲(chǔ)開(kāi)銷(xiāo)

四、結(jié) 論

以瀏覽區(qū)域的中心點(diǎn)作為轉(zhuǎn)移狀態(tài),可以建立地圖瀏覽的Markov模型。采用瓦片作為轉(zhuǎn)移狀態(tài),一次地圖操作可能導(dǎo)致多個(gè)瓦片同時(shí)轉(zhuǎn)移,學(xué)習(xí)與預(yù)測(cè)過(guò)程都較本文所述方法復(fù)雜。試驗(yàn)表明,基本Markov模型能有效提高預(yù)取的命中率,與鄰近區(qū)域預(yù)取方法對(duì)比,在同取 22個(gè)瓦片的情形下,兩者命中率分別為 38.9%與 8.3%。使用高階Markov模型,在網(wǎng)頁(yè)預(yù)取中一般能獲得更高的命中率,但在瓦片預(yù)取中命中率可能會(huì)更低,這主要取決于地圖瀏覽與網(wǎng)頁(yè)瀏覽的差異。多序Markov模型有效地利用了歷史信息,試驗(yàn)表明,序列越長(zhǎng),命中率越高。使用空間聚類(lèi),能有效地降低存儲(chǔ)復(fù)雜度,但并沒(méi)有提高命中率,這主要是由于空間聚類(lèi)過(guò)程并未充分利用歷史的訪問(wèn)信息。如何優(yōu)化聚類(lèi)方法,提出更合理的聚類(lèi)準(zhǔn)則,在降低存儲(chǔ)復(fù)雜度的同時(shí)提高預(yù)取命中率,是今后研究的重點(diǎn)。

[1] 陳靜,龔健雅,朱欣焰,等.海量影像數(shù)據(jù)的Web發(fā)布與實(shí)現(xiàn)[J].測(cè)繪通報(bào),2004(1):22-25.

[2] 陳能成,龔健雅,朱欣焰,等.多級(jí)緩沖提升海量影像數(shù)據(jù)在線服務(wù)質(zhì)量[J].測(cè)繪通報(bào),2007(6):19-22.

[3] 李銳,潘少明,喻占武.基于主動(dòng)緩存的 P2P海量地形漫游瓦片調(diào)度算法 [J].測(cè)繪學(xué)報(bào),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鏈用戶瀏覽預(yù)測(cè)模型[J].計(jì)算機(jī)學(xué)報(bào),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

國(guó)家 863計(jì)劃資助項(xiàng)目(2007AA12Z213,2007AA120501)

李云錦(1984—),男,湖北仙桃人,博士生,研究方向?yàn)?Service GIS、空間數(shù)據(jù)的多尺度表達(dá)。