建立有效的用戶瀏覽預(yù)測(cè)模型，對(duì)用戶的瀏覽做出準(zhǔn)確的預(yù)測(cè)，是導(dǎo)航工具實(shí)現(xiàn)對(duì)用戶瀏覽提供有效幫助的關(guān)鍵。

在瀏覽預(yù)測(cè)模型方面，很多學(xué)者都進(jìn)行了卓有成效的研究。AZER提出了基于概率模型的預(yù)取方法，根據(jù)網(wǎng)頁(yè)被連續(xù)訪問(wèn)的概率來(lái)預(yù)測(cè)用戶的訪問(wèn)請(qǐng)求。SARUKKAI運(yùn)用馬爾可夫鏈進(jìn)行訪問(wèn)路徑分析和鏈接預(yù)測(cè)，在此模型中，將用戶訪問(wèn)的網(wǎng)頁(yè)集作為狀態(tài)集，根據(jù)用戶訪問(wèn)記錄，計(jì)算出網(wǎng)頁(yè)間的轉(zhuǎn)移概率，作為預(yù)測(cè)依據(jù)。SCHECHTER構(gòu)造用戶訪問(wèn)路徑樹，采用最長(zhǎng)匹配方法，尋找與當(dāng)前用戶訪問(wèn)路徑匹配的歷史路徑，預(yù)測(cè)用戶的訪問(wèn)請(qǐng)求。XU Cheng Zhong等引入神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)基于語(yǔ)義的網(wǎng)頁(yè)預(yù)取。徐寶文等利用客戶端瀏覽器緩沖區(qū)數(shù)據(jù)，挖掘其中蘊(yùn)含的興趣關(guān)聯(lián)規(guī)則，預(yù)測(cè)用戶可能選擇的鏈接。朱培棟等人按語(yǔ)義對(duì)用戶會(huì)話進(jìn)行分類，根據(jù)會(huì)話所屬類別的共同特征，預(yù)測(cè)用戶可能訪問(wèn)的文檔。

在眾多的瀏覽模型中，Markov模型是一種簡(jiǎn)單而有效的模型。Markov模型最早是ZUKERMAN等人于1999年提出的一種用途十分廣泛的統(tǒng)計(jì)模型，它將用戶的瀏覽過(guò)程抽象為一個(gè)特殊的隨機(jī)過(guò)程——齊次離散Markov模型，用轉(zhuǎn)移概率矩陣描述用戶的瀏覽特征，并基于此對(duì)用戶的瀏覽進(jìn)行預(yù)測(cè)。之后，BOERGES等采用了多階轉(zhuǎn)移矩陣，進(jìn)一步提高了模型的預(yù)測(cè)準(zhǔn)確率。在此基礎(chǔ)上，SARUKKAI建立了一個(gè)實(shí)驗(yàn)系統(tǒng)[9],實(shí)驗(yàn)表明，Markov預(yù)測(cè)模型很適合作為一個(gè)預(yù)測(cè)模型來(lái)預(yù)測(cè)用戶在Web站點(diǎn)上的訪問(wèn)模式。

1 Markov模型

1.1 Markov模型

Markov預(yù)測(cè)模型對(duì)用戶在Web上的瀏覽過(guò)程作了如下的假設(shè)。

假設(shè)1（用戶瀏覽過(guò)程假設(shè)）：假設(shè)所有用戶在Web上的瀏覽過(guò)程是一個(gè)特殊的隨機(jī)過(guò)程——齊次的離散Markov模型。即設(shè)離散隨機(jī)變量的值域?yàn)閃eb空間中的所有網(wǎng)頁(yè)構(gòu)成的集合，則一個(gè)用戶在Web中的瀏覽過(guò)程就構(gòu)成一個(gè)隨機(jī)變量的取值序列，并且該序列滿足Markov性。

一個(gè)離散的Markov預(yù)測(cè)模型可以被描述成三元組，S代表狀態(tài)空間；A是轉(zhuǎn)換矩陣，表示從一個(gè)狀態(tài)轉(zhuǎn)換到另一個(gè)狀態(tài)的概率；B是S中狀態(tài)的初始概率分布。其中S是一個(gè)離散隨機(jī)變量，值域?yàn)閧x1，x2,…xn}，其中每個(gè)xi對(duì)應(yīng)一個(gè)網(wǎng)頁(yè)，稱為模型的一個(gè)狀態(tài)。

Markov預(yù)測(cè)模型是一個(gè)典型的無(wú)后效性隨機(jī)過(guò)程，也就是說(shuō)模型在時(shí)刻t的狀態(tài)只與它的前一個(gè)時(shí)刻t-1的狀態(tài)條件相關(guān)，與以前的狀態(tài)獨(dú)立。即：

王實(shí)等提出一種新的基于隱馬爾可夫模型的興趣遷移模式發(fā)現(xiàn)方法，并利用用戶遷移模式間的關(guān)聯(lián)規(guī)則來(lái)發(fā)現(xiàn)興趣遷移模式。而借助隱馬爾可夫模型， 挖掘蘊(yùn)涵在用戶訪問(wèn)路徑中的信息需求概念， 以此進(jìn)行預(yù)取頁(yè)面的評(píng)價(jià)， 也可以實(shí)現(xiàn)基于語(yǔ)義的網(wǎng)頁(yè)預(yù)取。

隱Markov模型盡管考慮了用戶興趣，但和簡(jiǎn)單的Markov模型一樣，存在一定的不足：用戶訪問(wèn)序列串長(zhǎng)是動(dòng)態(tài)時(shí)變的，采用固定階數(shù)的傳統(tǒng)Markov鏈模型并不能準(zhǔn)確地對(duì)用戶的訪問(wèn)行為建模。

2.2 多Markov模型

雖然用戶在Web空間的瀏覽過(guò)程是一個(gè)受瀏覽目的、文化背景、興趣愛(ài)好等多種因素影響的復(fù)雜過(guò)程，有很多差異，然而觀察大量用戶的瀏覽過(guò)程可以發(fā)現(xiàn)，某些用戶的瀏覽過(guò)程表現(xiàn)出相同或相近的特點(diǎn)，如他們?yōu)g覽的網(wǎng)頁(yè)基本相同，瀏覽各個(gè)網(wǎng)頁(yè)的順序相似等，這一現(xiàn)象引發(fā)了對(duì)Web用戶分類的研究。通過(guò)對(duì)用戶分類，同一類別的用戶用同一個(gè)模型來(lái)描述它，而不同類別的用戶其瀏覽過(guò)程差別較大，用不同的模型來(lái)描述他們的特征則更為合理。

假設(shè)2（用戶分類假設(shè)）：假設(shè)根據(jù)用戶在Web空間的瀏覽特點(diǎn)，可以將所有用戶分為K類。如果用C={c1, c2,…，ck}表示用戶的類別，則任意一個(gè)用戶屬于類別ck的概率為P（C=ck），而且有：

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

在多Markov模型方面，劉業(yè)政等提出可變多階Markov鏈模型VMOMC。VMOMC將用推薦目標(biāo)網(wǎng)頁(yè)概率值度量的可變多階Markov鏈并行組合，組合模型中采用遺傳算法確定各單階Markov鏈模型的最優(yōu)權(quán)重。陳佳提出了基于混合模型的一種挖掘用戶群在頁(yè)面上興趣分布程度的模式發(fā)現(xiàn)，計(jì)算用戶群從一個(gè)頁(yè)面到另外一個(gè)頁(yè)面的導(dǎo)航路徑模式的概率大小，可得到大量的用戶對(duì)所訪問(wèn)Web的興趣及導(dǎo)航模式，從而預(yù)測(cè)用戶的瀏覽路徑。

2.4 結(jié)構(gòu)相關(guān)性模型

有研究表明，用戶在進(jìn)行Web瀏覽的絕大部分時(shí)間里都是從當(dāng)前頁(yè)面中挑選一個(gè)鏈接繼續(xù)瀏覽；在用戶將來(lái)訪問(wèn)的網(wǎng)頁(yè)中，46％能在最近3個(gè)網(wǎng)頁(yè)的鏈接中找到，75％能在所有歷史網(wǎng)頁(yè)的鏈接中找到 。因此，可以認(rèn)為用戶將來(lái)的可能請(qǐng)求大部分存在于由當(dāng)前頁(yè)面上所有鏈接組成的集合中?；诮Y(jié)構(gòu)相關(guān)性的一階Markov模型包括以下三部分：

通過(guò)遍歷用戶訪問(wèn)序列的節(jié)點(diǎn)，可以得到用戶的狀態(tài)空間和轉(zhuǎn)移情況，并最終建立上述模型。

結(jié)合頁(yè)面內(nèi)容及站點(diǎn)結(jié)構(gòu)來(lái)調(diào)整狀態(tài)轉(zhuǎn)移矩陣，以獲得更精確的預(yù)取結(jié)果，提高Web 服務(wù)的質(zhì)量。而利用頻繁訪問(wèn)模式樹存儲(chǔ)Markov鏈，能夠大幅減小存儲(chǔ)空間。

3 進(jìn)一步研究的問(wèn)題

盡管現(xiàn)有的Markov 瀏覽預(yù)測(cè)模型在預(yù)測(cè)準(zhǔn)確率、覆蓋率方面已取得較滿意的成果，但瀏覽預(yù)測(cè)問(wèn)題的實(shí)際應(yīng)用背景中的一些特殊要求使得這一領(lǐng)域仍存在一些需要進(jìn)一步研究的問(wèn)題。這些問(wèn)題包括：

（1）Markov轉(zhuǎn)移概率矩陣的處理。該模型的存儲(chǔ)空間主要用于保存狀態(tài)轉(zhuǎn)移概率矩陣，所以其存儲(chǔ)空間的復(fù)雜度是網(wǎng)頁(yè)數(shù)目n的平方，即為0（n）。由于n的值一般都比較大，存儲(chǔ)復(fù)雜率較高。同時(shí)為了提高Web預(yù)取的命中率，常常聯(lián)合多個(gè)Markov鏈模型，即用到了多階狀態(tài)轉(zhuǎn)移矩陣，使得存儲(chǔ)復(fù)雜率成倍提高。因此如何存儲(chǔ)及處理Markov模型的概率矩陣、降低復(fù)雜度是急需解決的問(wèn)題。此外，在很多情況下?tīng)顟B(tài)轉(zhuǎn)移矩陣是稀疏矩陣，采用什么樣的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)這樣的矩陣也是需要研究的課題。

（2）混合Markov模型的求解問(wèn)題。混合Markov模型在預(yù)測(cè)用戶的瀏覽行為方面越來(lái)越受到學(xué)者的重視。有效的模型求解方法，能大大提高模型的效率。雖有學(xué)者進(jìn)行了有益的探索，但這方面的工作仍需要更多學(xué)者的參與。

（3）在實(shí)際瀏覽預(yù)測(cè)問(wèn)題中，Markov的隨機(jī)統(tǒng)計(jì)方法與其他方法，如神經(jīng)網(wǎng)絡(luò)、貝葉斯網(wǎng)絡(luò)、聚類、關(guān)聯(lián)規(guī)則、遺傳算法等相結(jié)合能獲得較高的預(yù)測(cè)準(zhǔn)確率。

（4）用戶在Web空間的瀏覽過(guò)程是一個(gè)受瀏覽目的、

文化背景、興趣愛(ài)好等多種因素影響的復(fù)雜動(dòng)態(tài)過(guò)程，如能有效地度量用戶的瀏覽興趣，并及時(shí)發(fā)現(xiàn)用戶的興趣遷移，對(duì)于提高預(yù)測(cè)準(zhǔn)確率非常重要。此外，隨著無(wú)線網(wǎng)絡(luò)的普及，怎樣預(yù)測(cè)無(wú)線網(wǎng)絡(luò)環(huán)境下用戶的瀏覽行為，是研究人員面臨的又一個(gè)課題。

全文概述了基于Markov的各種預(yù)測(cè)模型，分析了各個(gè)模型的原理及優(yōu)缺點(diǎn)，指出了今后的研究方向。