陳鋒敏

（湖北經(jīng)濟(jì)學(xué)院 網(wǎng)絡(luò)與教育技術(shù)中心，武漢 430205）

基于云端的Web數(shù)據(jù)挖掘預(yù)取技術(shù)研究

陳鋒敏

（湖北經(jīng)濟(jì)學(xué)院 網(wǎng)絡(luò)與教育技術(shù)中心，武漢 430205）

WWW以其多媒體的傳輸及良好的交互性而倍受青睞。 但由于Web服務(wù)和網(wǎng)絡(luò)固有的延遲，用戶并沒(méi)有得到與帶寬相應(yīng)的服務(wù)體驗(yàn)。為此文章提出了一種基于云端的智能Web預(yù)取技術(shù)，它能夠加快用戶瀏覽Web頁(yè)面時(shí)獲取頁(yè)面的速度。該技術(shù)通過(guò)簡(jiǎn)化的WWW數(shù)據(jù)模型表示用戶瀏覽器緩沖器中的數(shù)據(jù)，在云端利用數(shù)據(jù)挖掘技術(shù)挖掘類聚用戶隱含的興趣關(guān)聯(lián)規(guī)則，并利用類聚用戶的歷史連接記錄創(chuàng)建確定的影射關(guān)系模型，存放在云端興趣關(guān)聯(lián)知識(shí)庫(kù)中，作為對(duì)用戶行為進(jìn)行預(yù)測(cè)的依據(jù)。在用戶端，瀏覽器插件負(fù)責(zé)在用戶帶寬空閑時(shí)根據(jù)用戶興趣進(jìn)行Web預(yù)取，從而對(duì)用戶實(shí)現(xiàn)透明的高速瀏覽。

WWW；互聯(lián)網(wǎng)；數(shù)據(jù)模型；數(shù)據(jù)挖掘；預(yù)??；映射；云端

隨著互聯(lián)網(wǎng)高速普及以及互聯(lián)網(wǎng)基礎(chǔ)設(shè)施的逐步完善，人均享有帶寬也在逐步的增加，但由于Web服務(wù)和網(wǎng)絡(luò)固有的延遲，用戶并沒(méi)有得到與帶寬相應(yīng)的服務(wù)體驗(yàn)。根據(jù)用戶當(dāng)前的請(qǐng)求，預(yù)測(cè)用戶將來(lái)可能發(fā)出的訪問(wèn)請(qǐng)求，在用戶瀏覽當(dāng)前Web頁(yè)面時(shí)將預(yù)測(cè)的內(nèi)容取到本地高速緩存(cache)中，通過(guò)主動(dòng)的高速緩存可以有效提高用戶瀏覽體驗(yàn)。預(yù)取技術(shù)的基礎(chǔ)是預(yù)測(cè)算法。數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中采掘出隱含的、先前未知的、對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則的一種技術(shù)。我們可以根據(jù)用戶訪問(wèn)的歷史數(shù)據(jù)和當(dāng)前訪問(wèn)的數(shù)據(jù)、利用數(shù)據(jù)挖掘技術(shù)來(lái)預(yù)測(cè)用戶將來(lái)的可能行為，從而為用戶預(yù)取一些Web頁(yè)面。

本文首先討論了Web預(yù)取的解決思路，然后通過(guò)簡(jiǎn)化WWW數(shù)據(jù)模型建立興趣關(guān)聯(lián)知識(shí)庫(kù)，最后討論了一個(gè)基于云端和插件的Web預(yù)取原型系統(tǒng)。

1 Web預(yù)取映射關(guān)系研究

1.1 Web預(yù)取面臨的問(wèn)題及解決思路

從根本上說(shuō)，Web預(yù)取面臨的問(wèn)題只有一個(gè)，那就是：從用戶訪問(wèn)的過(guò)的大量歷史鏈接記錄中推測(cè)和判斷出用戶在當(dāng)前頁(yè)面下最有可能點(diǎn)擊的鏈接頁(yè)面并提前將預(yù)測(cè)的內(nèi)容取到本地高速緩存中，從而在很大程度上減小用戶的訪問(wèn)延遲。如下圖所示：

雖然互聯(lián)網(wǎng)中具有海量的數(shù)據(jù)，但對(duì)于具體的某一用戶而言，其所接觸的只是萬(wàn)維網(wǎng)的有限的極小一部分，所以我們可以通過(guò)Web頁(yè)面的向量類型作為有限集合，以類聚用戶的歷史鏈接記錄（包含有用戶的偏好）確定映射關(guān)系。

1.2 預(yù)取映射關(guān)系的構(gòu)建

（1）用戶訪問(wèn)過(guò)的歷史Web頁(yè)面通過(guò)TFIDF向量表示法進(jìn)行聚類。

（2）用戶的鏈接記錄加入到兩集合之間作為確定的映射關(guān)系，同時(shí)記下鏈接次數(shù)作為權(quán)重。

所構(gòu)建的集合之間的映射包含下列二種具體的映射關(guān)系：

第①種映射是一一映射。

第②種映射是一對(duì)多的關(guān)系，我們可以通過(guò)記錄其分別映射的次數(shù)形成權(quán)重來(lái)限制在預(yù)取的過(guò)程中沿著權(quán)重大的目標(biāo)結(jié)點(diǎn)進(jìn)行映射。最終形成一一映射。

1.3 基于確定映射關(guān)系的新的預(yù)取思路

在確定的映射關(guān)系構(gòu)建之后

step1：將當(dāng)前的Web頁(yè)面進(jìn)行詞條切分，應(yīng)用TFIDF向量表示法與知識(shí)庫(kù)中的源Web頁(yè)面類型進(jìn)行匹配，在知識(shí)庫(kù)的源Web頁(yè)面集合中找出對(duì)應(yīng)的源Web頁(yè)面類型；

Step2：沿著知識(shí)庫(kù)中確定的映射關(guān)系找出對(duì)應(yīng)的目標(biāo)Web頁(yè)面類型；

Step3：將當(dāng)前Web頁(yè)面鏈接集合中的Web頁(yè)面與目標(biāo)Web頁(yè)面類型進(jìn)行匹配，并按匹配程度進(jìn)行排序，并按規(guī)定的預(yù)取數(shù)量按順序從前向后進(jìn)行預(yù)取。

該預(yù)取思路的優(yōu)點(diǎn)：

①構(gòu)建了確定的映射關(guān)系，提高了預(yù)取的效率。

②算法的復(fù)雜度為，大大節(jié)省了計(jì)算資源，提高了響應(yīng)速度。

2 簡(jiǎn)化WWW數(shù)據(jù)模型

Web頁(yè)面之間可以通過(guò)超級(jí)鏈接而相互鏈接，從而構(gòu)成一個(gè)相互鏈接的超媒體系統(tǒng)。為了對(duì)用戶行為做出預(yù)測(cè)，必須有一種數(shù)據(jù)模型能夠很好地描述Web頁(yè)面間的興趣關(guān)聯(lián)規(guī)則。為便于本文的討論，我們將定義一種數(shù)據(jù)模型一一簡(jiǎn)化WWW數(shù)據(jù)模型。

定義1 頁(yè)面節(jié)點(diǎn)用三元組(P Id,P,time)表示，其中，P Id唯一標(biāo)記一個(gè)頁(yè)面節(jié)點(diǎn)，time為其最近被訪問(wèn)的時(shí)間，P為屬性集，P={pi|pi為屬性，i=1,2,…}。

定義2 頁(yè)面中的鏈接點(diǎn)用三元組 (L Id，string,target.node.id)表示，L Id唯一標(biāo)記一個(gè)鏈接點(diǎn)，string描述了該鏈接的展示信息，target.node.id是L Id所標(biāo)記的鏈接點(diǎn)所指向的目標(biāo)頁(yè)面節(jié)點(diǎn)的P Id.

定義3 頁(yè)面中的鏈接用三元組(source.node,L,target.node)表示，其中，source.node為源頁(yè)面節(jié)點(diǎn),L為source.node中的鏈接點(diǎn)，target.node為目標(biāo)頁(yè)面節(jié)點(diǎn),L.target.node.id=target.node.

針對(duì)數(shù)據(jù)挖掘的要求及高速緩存的特點(diǎn)，我們通過(guò)頁(yè)面節(jié)點(diǎn)鏈接點(diǎn)和鏈接描述一種簡(jiǎn)化WWW數(shù)據(jù)模型。

定義4 簡(jiǎn)化WWW數(shù)據(jù)模型可以用三元組(Page.node.set,Page.linknode.set,Link.set)表示，其中，Page.node.set為頁(yè)面節(jié)點(diǎn)集合，Page.linknode.set為鏈接點(diǎn)集合，L ink.set為鏈接集合。

如圖2所示，頁(yè)面節(jié)點(diǎn)N1,N2,N3,N4,N5分別表示不同的Web頁(yè)面，這些頁(yè)面節(jié)點(diǎn)之間可以通過(guò)有向邊相互鏈接。這些有向邊直觀地表示了頁(yè)面間的鏈接。

高速緩存中保存的歷史數(shù)據(jù)反映了用戶訪問(wèn)頁(yè)面過(guò)程中的興趣愛(ài)好。利用用戶的興趣間的關(guān)聯(lián)信息可以對(duì)用戶的行為進(jìn)行預(yù)測(cè)。高速緩存中頁(yè)面間的聯(lián)系可以很方便地用圖2中的簡(jiǎn)化WWW數(shù)據(jù)模型來(lái)描述，但是這種數(shù)據(jù)模型不能直觀地表示用戶的興趣間的關(guān)聯(lián)信息.為了對(duì)用戶的行為進(jìn)行預(yù)測(cè)，從而實(shí)現(xiàn)主動(dòng)的緩沖(預(yù)取)，需要通過(guò)某種方法將由簡(jiǎn)化WWW數(shù)據(jù)模型所表示的高速緩存中的數(shù)據(jù)反映到適合于預(yù)測(cè)的數(shù)據(jù)模型中去。

3 云端興趣關(guān)聯(lián)知識(shí)庫(kù)與用戶行為預(yù)測(cè)

一般的用戶都是喜歡訪問(wèn)有限的網(wǎng)站中的感興趣的Web頁(yè)面，受用戶習(xí)慣行為的影響，其點(diǎn)擊頁(yè)面的順序中隱含了該用戶的興趣關(guān)聯(lián)規(guī)則，因此我們可以將用戶曾經(jīng)訪問(wèn)過(guò)的Web頁(yè)面進(jìn)行抽象提取成向量的形式后存入興趣關(guān)聯(lián)知識(shí)庫(kù)（設(shè)有存儲(chǔ)上限和自動(dòng)更新功能），同時(shí)將Web頁(yè)面鏈接順序（L Id—＞target.node.Id）一并存入，則該條記錄就隱含了用戶的興趣關(guān)聯(lián)規(guī)則,例如：用戶訪問(wèn)Web頁(yè)面的順序?yàn)锳—＞B—＞C—＞D,則我們可以將下列記錄存入興趣關(guān)聯(lián)數(shù)據(jù)庫(kù)：

序號(hào)次數(shù)123…….N Source.page P(A)P(B)P(C)…….P(N)L Id L Id(A)L Id(B)L Id(C)…….L Id(N)target.node.Id target.node.Id(B)target.node.Id(C)target.node.Id(D)……target.node.Id()target.page P(B)P(C)P(D)……P（）N1N2 N3 Nn

興趣關(guān)聯(lián)知識(shí)庫(kù)中的記錄隱含了用戶的興趣關(guān)聯(lián)規(guī)則，即用戶從某一詞條(興趣)轉(zhuǎn)向其它詞條(興趣)的可能性。利用它再結(jié)合用戶訪問(wèn)的當(dāng)前頁(yè)面可以預(yù)測(cè)用戶可能訪問(wèn)的鏈接(圖 1)。

興趣關(guān)聯(lián)知識(shí)庫(kù)中的興趣關(guān)聯(lián)規(guī)則記錄建立在對(duì)大量歷史數(shù)據(jù)進(jìn)行統(tǒng)計(jì)的基礎(chǔ)上。用戶在訪問(wèn)頁(yè)面時(shí)，一般是連續(xù)訪問(wèn)多個(gè)頁(yè)面。這些頁(yè)面實(shí)際上表明了用戶當(dāng)前的興趣狀況，它們相對(duì)那些用于構(gòu)造興趣關(guān)聯(lián)知識(shí)庫(kù)的歷史數(shù)據(jù)來(lái)說(shuō)，對(duì)預(yù)測(cè)用戶的行為更有價(jià)值，即它們的新鮮度更高。根據(jù)用戶目前訪問(wèn)軌跡進(jìn)行類聚分析，從而獲取最可能預(yù)取頁(yè)面路徑。

4 基于云端的Web預(yù)送技術(shù)

通過(guò)瀏覽器插件在用戶空閑時(shí)段與云端進(jìn)行交互，云端基于興趣關(guān)聯(lián)知識(shí)庫(kù)預(yù)測(cè)用戶行為算法對(duì)用戶當(dāng)前頁(yè)面進(jìn)行分析，云端根據(jù)用戶興趣，返回最可能興趣頁(yè)面路徑，由插件負(fù)責(zé)預(yù)取Web頁(yè)面并將之存放到本地高速緩存中。同時(shí)云端通過(guò)興趣關(guān)聯(lián)知識(shí)庫(kù)調(diào)整增量算法，對(duì)興趣關(guān)聯(lián)知識(shí)庫(kù)進(jìn)行更新，插件的存在對(duì)用戶是透明的。用戶仍像平時(shí)一樣使用瀏覽器。

5 總結(jié)

本文在給出簡(jiǎn)化WWW數(shù)據(jù)模型的基礎(chǔ)上，利用數(shù)據(jù)挖掘技術(shù)對(duì)用戶瀏覽器高速緩存中的數(shù)據(jù)進(jìn)行挖掘，從中獲取知識(shí)，并將其存放在興趣關(guān)聯(lián)知識(shí)庫(kù)中，用來(lái)預(yù)測(cè)用戶即將訪問(wèn)的鏈接。通過(guò)對(duì)用戶行為興趣分析形成龐大的興趣關(guān)聯(lián)知識(shí)庫(kù)不僅可以為用戶帶來(lái)快速的瀏覽體驗(yàn)，還可以在不泄露用戶隱私的前提下為Web服務(wù)商提供詳實(shí)的服務(wù)報(bào)告以及訪問(wèn)用戶行為分析。

[1]陳康，云計(jì)算.系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報(bào)，2009,(5).

[2]張建勛.云算研究進(jìn)展綜述[J].計(jì)算機(jī)應(yīng)用研究，2010,(2).

[4]朱志國(guó).持久偏愛(ài)的Web用戶訪問(wèn)路徑信息挖掘方法[J].情報(bào)學(xué)報(bào)，2010,(2).

[5]王繼承,潘金貴等.Web文本挖掘技術(shù)研究[J].計(jì)算機(jī)研究與發(fā)展，2000,37(5).

[6]王晗.一種新的增量式關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘方法研究[J].儀器儀表學(xué)報(bào)，2009,(2).

[7]班志杰.Web預(yù)取技術(shù)綜述[J].計(jì)算機(jī)研究與發(fā)展，2009,(2).

TP3

A

1002-6487（2010）22-0161-02

（責(zé)任編輯/易永生）