摘  要： 介紹了基本的Markov瀏覽預(yù)測模型；討論了擴展的Markov瀏覽預(yù)測模型，包括隱Markov模型、多Markov模型、混合模型、結(jié)構(gòu)相關(guān)性模型;綜述了各個模型的算法及其優(yōu)缺點；分析了Markov瀏覽預(yù)測模型需要深入研究的問題。
關(guān)鍵詞： 數(shù)據(jù)挖掘； Markov模型； 偏愛度； 瀏覽路徑預(yù)測

    建立有效的用戶瀏覽預(yù)測模型，對用戶的瀏覽做出準(zhǔn)確的預(yù)測，是導(dǎo)航工具實現(xiàn)對用戶瀏覽提供有效幫助的關(guān)鍵。
    在瀏覽預(yù)測模型方面，很多學(xué)者都進(jìn)行了卓有成效的研究。AZER[1]提出了基于概率模型的預(yù)取方法，根據(jù)網(wǎng)頁被連續(xù)訪問的概率來預(yù)測用戶的訪問請求。SARUKKAI[2]運用馬爾可夫鏈進(jìn)行訪問路徑分析和鏈接預(yù)測，在此模型中，將用戶訪問的網(wǎng)頁集作為狀態(tài)集，根據(jù)用戶訪問記錄，計算出網(wǎng)頁間的轉(zhuǎn)移概率，作為預(yù)測依據(jù)。SCHECHTER[3]構(gòu)造用戶訪問路徑樹，采用最長匹配方法，尋找與當(dāng)前用戶訪問路徑匹配的歷史路徑，預(yù)測用戶的訪問請求。XU Cheng Zhong等[4]引入神經(jīng)網(wǎng)絡(luò)實現(xiàn)基于語義的網(wǎng)頁預(yù)取。徐寶文等[5]利用客戶端瀏覽器緩沖區(qū)數(shù)據(jù)，挖掘其中蘊含的興趣關(guān)聯(lián)規(guī)則，預(yù)測用戶可能選擇的鏈接。朱培棟等人[6]按語義對用戶會話進(jìn)行分類，根據(jù)會話所屬類別的共同特征，預(yù)測用戶可能訪問的文檔。
    在眾多的瀏覽模型中，Markov模型是一種簡單而有效的模型。Markov模型最早是ZUKERMAN[7]等人于1999年提出的一種用途十分廣泛的統(tǒng)計模型，它將用戶的瀏覽過程抽象為一個特殊的隨機過程——齊次離散Markov模型，用轉(zhuǎn)移概率矩陣描述用戶的瀏覽特征，并基于此對用戶的瀏覽進(jìn)行預(yù)測。之后，BOERGES[8]等采用了多階轉(zhuǎn)移矩陣，進(jìn)一步提高了模型的預(yù)測準(zhǔn)確率。在此基礎(chǔ)上，SARUKKAI建立了一個實驗系統(tǒng)[9],實驗表明，Markov預(yù)測模型很適合作為一個預(yù)測模型來預(yù)測用戶在Web站點上的訪問模式。
1 Markov模型
1.1 Markov模型
    Markov預(yù)測模型[10]對用戶在Web上的瀏覽過程作了如下的假設(shè)。
　假設(shè)1(用戶瀏覽過程假設(shè))：假設(shè)所有用戶在Web上的瀏覽過程是一個特殊的隨機過程——齊次的離散Markov模型。即設(shè)離散隨機變量的值域為Web空間中的所有網(wǎng)頁構(gòu)成的集合，則一個用戶在Web中的瀏覽過程就構(gòu)成一個隨機變量的取值序列，并且該序列滿足Markov性。
　一個離散的Markov預(yù)測模型可以被描述成三元組<S，A，B>，S代表狀態(tài)空間；A是轉(zhuǎn)換矩陣，表示從一個狀態(tài)轉(zhuǎn)換到另一個狀態(tài)的概率；B是S中狀態(tài)的初始概率分布。其中S是一個離散隨機變量，值域為{x1，x2,…xn}，其中每個xi對應(yīng)一個網(wǎng)頁,稱為模型的一個狀態(tài)。
　Markov預(yù)測模型是一個典型的無后效性隨機過程，也就是說模型在時刻t的狀態(tài)只與它的前一個時刻t-1的狀態(tài)條件相關(guān)，與以前的狀態(tài)獨立。即：


    王實[12]等提出一種新的基于隱馬爾可夫模型的興趣遷移模式發(fā)現(xiàn)方法，并利用用戶遷移模式間的關(guān)聯(lián)規(guī)則來發(fā)現(xiàn)興趣遷移模式。而借助隱馬爾可夫模型, 挖掘蘊涵在用戶訪問路徑中的信息需求概念, 以此進(jìn)行預(yù)取頁面的評價, 也可以實現(xiàn)基于語義的網(wǎng)頁預(yù)取[13]。
　隱Markov模型盡管考慮了用戶興趣,但和簡單的Markov模型一樣，存在一定的不足：用戶訪問序列串長是動態(tài)時變的,采用固定階數(shù)的傳統(tǒng)Markov鏈模型并不能準(zhǔn)確地對用戶的訪問行為建模。
2.2 多Markov模型
　雖然用戶在Web空間的瀏覽過程是一個受瀏覽目的、文化背景、興趣愛好等多種因素影響的復(fù)雜過程,有很多差異，然而觀察大量用戶的瀏覽過程可以發(fā)現(xiàn)，某些用戶的瀏覽過程表現(xiàn)出相同或相近的特點，如他們?yōu)g覽的網(wǎng)頁基本相同，瀏覽各個網(wǎng)頁的順序相似等，這一現(xiàn)象引發(fā)了對Web用戶分類的研究。通過對用戶分類，同一類別的用戶用同一個模型來描述它，而不同類別的用戶其瀏覽過程差別較大，用不同的模型來描述他們的特征則更為合理[14]。
　假設(shè)2(用戶分類假設(shè))：假設(shè)根據(jù)用戶在Web空間的瀏覽特點,可以將所有用戶分為K類。如果用C={c1, c2,…,ck}表示用戶的類別，則任意一個用戶屬于類別ck的概率為P(C=ck),而且有：

    上述模型稱為二步Markov模型[15]，它的核心任務(wù)是建立一個與一階Markov模型的轉(zhuǎn)移概率矩陣同規(guī)模的轉(zhuǎn)移概率矩陣。矩陣的行元素代表用戶瀏覽的上一個網(wǎng)頁，列元素代表用戶下一步可能瀏覽的網(wǎng)頁。通過該矩陣可以根據(jù)用戶上一步瀏覽的網(wǎng)頁來預(yù)測下一步要瀏覽的網(wǎng)頁。

    在多Markov模型方面,劉業(yè)政等[16]提出可變多階Markov鏈模型VMOMC。VMOMC將用推薦目標(biāo)網(wǎng)頁概率值度量的可變多階Markov鏈并行組合，組合模型中采用遺傳算法確定各單階Markov鏈模型的最優(yōu)權(quán)重。陳佳[17]提出了基于混合模型的一種挖掘用戶群在頁面上興趣分布程度的模式發(fā)現(xiàn)，計算用戶群從一個頁面到另外一個頁面的導(dǎo)航路徑模式的概率大小，可得到大量的用戶對所訪問Web的興趣及導(dǎo)航模式,從而預(yù)測用戶的瀏覽路徑。
2.4 結(jié)構(gòu)相關(guān)性模型
　有研究表明，用戶在進(jìn)行Web瀏覽的絕大部分時間里都是從當(dāng)前頁面中挑選一個鏈接繼續(xù)瀏覽；在用戶將來訪問的網(wǎng)頁中，46％能在最近3個網(wǎng)頁的鏈接中找到，75％能在所有歷史網(wǎng)頁的鏈接中找到 。因此，可以認(rèn)為用戶將來的可能請求大部分存在于由當(dāng)前頁面上所有鏈接組成的集合中?；诮Y(jié)構(gòu)相關(guān)性的一階Markov模型包括以下三部分[19]：

　通過遍歷用戶訪問序列的節(jié)點，可以得到用戶的狀態(tài)空間和轉(zhuǎn)移情況，并最終建立上述模型。
　結(jié)合頁面內(nèi)容及站點結(jié)構(gòu)來調(diào)整狀態(tài)轉(zhuǎn)移矩陣,以獲得更精確的預(yù)取結(jié)果,提高Web 服務(wù)的質(zhì)量[20]。而利用頻繁訪問模式樹存儲Markov鏈，能夠大幅減小存儲空間[21]。
3 進(jìn)一步研究的問題
　盡管現(xiàn)有的Markov 瀏覽預(yù)測模型在預(yù)測準(zhǔn)確率、覆蓋率方面已取得較滿意的成果,但瀏覽預(yù)測問題的實際應(yīng)用背景中的一些特殊要求使得這一領(lǐng)域仍存在一些需要進(jìn)一步研究的問題。這些問題包括:
　(1)Markov轉(zhuǎn)移概率矩陣的處理。該模型的存儲空間主要用于保存狀態(tài)轉(zhuǎn)移概率矩陣，所以其存儲空間的復(fù)雜度是網(wǎng)頁數(shù)目n的平方，即為0(n)。由于n的值一般都比較大，存儲復(fù)雜率較高。同時為了提高Web預(yù)取的命中率，常常聯(lián)合多個Markov鏈模型，即用到了多階狀態(tài)轉(zhuǎn)移矩陣，使得存儲復(fù)雜率成倍提高。因此如何存儲及處理Markov模型的概率矩陣、降低復(fù)雜度是急需解決的問題。此外，在很多情況下狀態(tài)轉(zhuǎn)移矩陣是稀疏矩陣，采用什么樣的數(shù)據(jù)結(jié)構(gòu)來存儲這樣的矩陣也是需要研究的課題。
　(2)混合Markov模型的求解問題?；旌螹arkov模型在預(yù)測用戶的瀏覽行為方面越來越受到學(xué)者的重視。有效的模型求解方法，能大大提高模型的效率。雖有學(xué)者[15，22]進(jìn)行了有益的探索，但這方面的工作仍需要更多學(xué)者的參與。
　(3)在實際瀏覽預(yù)測問題中,Markov的隨機統(tǒng)計方法與其他方法,如神經(jīng)網(wǎng)絡(luò)、貝葉斯網(wǎng)絡(luò)、聚類、關(guān)聯(lián)規(guī)則、遺傳算法等相結(jié)合能獲得較高的預(yù)測準(zhǔn)確率。
    (4)用戶在Web空間的瀏覽過程是一個受瀏覽目的、
文化背景、興趣愛好等多種因素影響的復(fù)雜動態(tài)過程，如能有效地度量用戶的瀏覽興趣，并及時發(fā)現(xiàn)用戶的興趣遷移[25]，對于提高預(yù)測準(zhǔn)確率非常重要。此外，隨著無線網(wǎng)絡(luò)的普及，怎樣預(yù)測無線網(wǎng)絡(luò)環(huán)境下用戶的瀏覽行為，是研究人員面臨的又一個課題。
    全文概述了基于Markov的各種預(yù)測模型，分析了各個模型的原理及優(yōu)缺點，指出了今后的研究方向。
參考文獻(xiàn)
[1]    BESTRAVROS A. Using speculation to reduce server load and service time on the WWW proceedings of the CIKM′ 95, Baltimore,1995：403-410.
[2]     SARUKKAI R. Link prediction and path analysis using  Markov chains[J]. Computer Networks, 2000,33(1-6):337-386.
[3]     SCHECHTER S, KRISHNAN M, SMITH M D. Using path     profiles to predict HTTP requests[J]. Computer Networks and ISDN Systems,1998，30(1-7):457-467.
[4]    XU C Z, TAMER. Semantics-based personalized prefetching to improve Web performance[C]. Proceedings of the 20th IEEE Conference on Distributed Computing    Systems, 2000:636-643.
[5]     徐寶文，張衛(wèi)豐.數(shù)據(jù)挖掘技術(shù)在Web預(yù)取中的應(yīng)用研究[J].計算機學(xué)報, 2001,24(4)：10-17.
[6]    朱培棟,盧錫城,周興銘.基于客戶行為模式的Web文檔預(yù)送[J]. 軟件學(xué)報,1999,10(11)：1142-1147.
[7]     ZUCKERMAN I D. Albrcht predicting user’s requests on  the WWW[C]. In: Proceedings of the 7th International conference on User Modeling,New York,springer, 1999:275-284.
[8]     BORGES J, LEVENE M. Data mining of user navigation patterns. In: Proceedings of the1999 KDD Workshop on Web Mining, CA: Springer Verlag Press, 1999:92.
[9]     SARUKKAI R. Link prediction and path analysis using Markov chains[C]. Amsterdam, Nether- lands Proceedings of the 9th World Wide Web Conference,2000:234-247.
[10]    林文龍,劉業(yè)政,姜元春.Web瀏覽預(yù)測的Markov模型綜述[J].計算機科學(xué), 2008,35(1):9-14.
[11]    金民鎖,劉紅祥,王佐,基于隱馬爾科夫模型的瀏覽路徑預(yù)測[J].黑龍江科技學(xué)院學(xué)報,2005,15(3):167-170.
[12]    王實,高文,李錦濤,等. 基于隱馬爾可夫模型的興趣遷移模式發(fā)現(xiàn)[J]. 計算機學(xué)報,2001,24(2):152-157.
[13]    許歡慶,王永成,孫強. 基于隱馬爾可夫模型的Web 網(wǎng)頁預(yù)取[J].上海交通大學(xué)學(xué)報, 2003,37(3):404-407.
[14]    刑永康,馬少平. 多Markov鏈用戶瀏覽預(yù)測模型[J].計算機學(xué)報, 2003,26(11):1510-1517.
[15]    余雪崗, 劉衍珩, 魏達(dá),等. 用于移動路徑預(yù)測的混合Markov模型[J]. 通信學(xué)報, 2006,27(12):61-69.
[16]    劉業(yè)政,林文龍.可變多階Markov鏈模型及在WWW個性化推薦中的應(yīng)用[J].情報學(xué)報,2008,27(6):819-824.
[17]    陳佳,吳軍華.基于混合Markov模型的用戶瀏覽預(yù)測[J].計算機工程與設(shè)計,2009,30(4):903-906.
[18]    葉海琴,石磊,王意鋒.基于網(wǎng)絡(luò)訪問行為的混合階Markov 預(yù)測模型[J]. 計算機工程與設(shè)計,2008,29(2):333-336.
[19]    張麗, 郭成城.基于結(jié)構(gòu)相關(guān)性Markov模型的Web網(wǎng)頁預(yù)取方法[J].計算機工程與應(yīng)用,2O04(2):163-167.
[20] 徐燕.基于內(nèi)容和結(jié)構(gòu)的Markov 模型在網(wǎng)頁預(yù)取中的應(yīng)用[J].計算機工程與科學(xué), 2007,29(4):25-27.
[21] 閆永權(quán)，張大方.基于頻繁的Markov鏈預(yù)測模型[J]. 計算機應(yīng)用研究, 2007,24(3):41-43.
[22] 胡必錦.Markov模型的熵與參數(shù)估計[J].重慶交通學(xué)院學(xué)報,2005,25(6):162-164.
[23]    韓真，曹新平. TOP-N選擇Markov預(yù)測模型[J].計算機應(yīng)用,2005,25(3):670-672.
[24]    石磊,古志民,衛(wèi)琳，等．基于Web流行度的選擇Markov預(yù)取模型[J] 計算機工程，2006，32(11):72-74.
[25]    吳晶,張品,羅辛,等.門戶個性化興趣獲取與遷移模式發(fā)現(xiàn)[J].計算機研究與發(fā)展,2007，44(8):1284-1292.