陳鋒敏

（湖北經(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ò)固有的延遲，用戶并沒有得到與帶寬相應(yīng)的服務(wù)體驗(yàn)。為此文章提出了一種基于云端的智能Web預(yù)取技術(shù)，它能夠加快用戶瀏覽Web頁面時(shí)獲取頁面的速度。該技術(shù)通過簡化的WWW數(shù)據(jù)模型表示用戶瀏覽器緩沖器中的數(shù)據(jù)，在云端利用數(shù)據(jù)挖掘技術(shù)挖掘類聚用戶隱含的興趣關(guān)聯(lián)規(guī)則，并利用類聚用戶的歷史連接記錄創(chuàng)建確定的影射關(guān)系模型，存放在云端興趣關(guān)聯(lián)知識庫中，作為對用戶行為進(jìn)行預(yù)測的依據(jù)。在用戶端，瀏覽器插件負(fù)責(zé)在用戶帶寬空閑時(shí)根據(jù)用戶興趣進(jìn)行Web預(yù)取，從而對用戶實(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ò)固有的延遲，用戶并沒有得到與帶寬相應(yīng)的服務(wù)體驗(yàn)。根據(jù)用戶當(dāng)前的請求，預(yù)測用戶將來可能發(fā)出的訪問請求，在用戶瀏覽當(dāng)前Web頁面時(shí)將預(yù)測的內(nèi)容取到本地高速緩存(cache)中，通過主動(dòng)的高速緩存可以有效提高用戶瀏覽體驗(yàn)。預(yù)取技術(shù)的基礎(chǔ)是預(yù)測算法。數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中采掘出隱含的、先前未知的、對決策有潛在價(jià)值的知識和規(guī)則的一種技術(shù)。我們可以根據(jù)用戶訪問的歷史數(shù)據(jù)和當(dāng)前訪問的數(shù)據(jù)、利用數(shù)據(jù)挖掘技術(shù)來預(yù)測用戶將來的可能行為，從而為用戶預(yù)取一些Web頁面。

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

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

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

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

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

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

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

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

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

第①種映射是一一映射。

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

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

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

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

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

Step3：將當(dāng)前Web頁面鏈接集合中的Web頁面與目標(biāo)Web頁面類型進(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 簡化WWW數(shù)據(jù)模型

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

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

定義2 頁面中的鏈接點(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)頁面節(jié)點(diǎn)的P Id.

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

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

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

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

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

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

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

序號次數(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)知識庫中的記錄隱含了用戶的興趣關(guān)聯(lián)規(guī)則，即用戶從某一詞條(興趣)轉(zhuǎn)向其它詞條(興趣)的可能性。利用它再結(jié)合用戶訪問的當(dāng)前頁面可以預(yù)測用戶可能訪問的鏈接(圖 1)。

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

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

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

5 總結(jié)

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

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

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

[4]朱志國.持久偏愛的Web用戶訪問路徑信息挖掘方法[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é)任編輯/易永生）