韋 相

（紅河學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，云南蒙自 661100）

引言

隨著Internet的飛速發(fā)展, 特別是電子商務(wù)的發(fā)展，Web已經(jīng)成為企業(yè)信息發(fā)布，交流和進(jìn)行商業(yè)活動(dòng)的主要工具.如何進(jìn)行Web站點(diǎn)的導(dǎo)航設(shè)計(jì)、Web服務(wù)設(shè)計(jì)、對(duì)電子商務(wù)等活動(dòng)正變得越來(lái)越主要.一個(gè)網(wǎng)站是否能夠吸引訪問(wèn)者，取決于是否可以根據(jù)用戶的訪問(wèn)興趣、 訪問(wèn)頻度、訪問(wèn)序列動(dòng)態(tài)地調(diào)整頁(yè)面結(jié)構(gòu), 改進(jìn)服務(wù),以便更好地滿足訪問(wèn)者的需求.

解決這種需求的就是Web數(shù)據(jù)挖掘.Web數(shù)據(jù)挖掘就是從Web頁(yè)面中挖掘出未知的、隱藏的，對(duì)決策有潛在的知識(shí)或規(guī)則的過(guò)程.它是把數(shù)據(jù)挖掘技術(shù)用于互聯(lián)網(wǎng)資源上，是一種實(shí)用的新技術(shù).Web數(shù)據(jù)挖掘可以分為Web內(nèi)容挖掘,Web結(jié)構(gòu)挖掘,Web 使用挖掘三類(lèi).Web內(nèi)容挖掘是從文檔內(nèi)容或其描述中抽取有用信息的過(guò)程,Web 內(nèi)容挖掘有兩種策略:直接挖掘文檔的內(nèi)容和在其他工具搜索的基礎(chǔ)上進(jìn)行改進(jìn).Web 結(jié)構(gòu)挖掘可以分為Web 文檔內(nèi)部結(jié)構(gòu)挖掘和文檔間的超鏈接結(jié)構(gòu)挖掘.這方面的代表有Page Rank和CLEVER,此外,在多層次Web數(shù)據(jù)倉(cāng)庫(kù)( MLDB ) 中也利用了頁(yè)面的鏈接結(jié)構(gòu).Web使用挖掘是從服務(wù)器端記錄的用戶訪問(wèn)日志或從用戶的瀏覽信息中抽取感興趣的模式,通過(guò)分析這些數(shù)據(jù)可以幫助理解用戶隱藏在數(shù)據(jù)中的行為模式,做出預(yù)測(cè)性分析,從而改進(jìn)站點(diǎn)的結(jié)構(gòu)或?yàn)橛脩籼峁﹤€(gè)性化的服務(wù).

發(fā)現(xiàn)用戶的遷移模式是Web使用挖掘的一個(gè)重要研究領(lǐng)域，當(dāng)用戶訪問(wèn)一個(gè)Web站點(diǎn)時(shí), 實(shí)際上他對(duì)某種東西是感興趣的，帶著一定的目的而來(lái).不同的用戶具有不同的興趣, 所以他們會(huì)按照不同的路徑進(jìn)行訪問(wèn).現(xiàn)有一些的商業(yè)分析軟件用于分析訪問(wèn)日志，如Happy Log、Deep Log Analyzer、Nihuo Web Log Analyzer等.但這些工具僅能產(chǎn)生一些簡(jiǎn)單的統(tǒng)計(jì)結(jié)果, 如頁(yè)面的訪問(wèn)頻度，用戶的訪問(wèn)次數(shù)等，并沒(méi)有挖掘出更深入的知識(shí)..文獻(xiàn)[1]首次定義了Web 挖掘的概念, 并且給出Web 訪問(wèn)信息挖掘的模型.文獻(xiàn)[2]對(duì)Web站點(diǎn)的日志進(jìn)行處理,得到事務(wù)數(shù)據(jù)形式, 然后利用傳統(tǒng)的數(shù)據(jù)挖掘方法(如聚類(lèi)算法[3])進(jìn)行處理.一些研究學(xué)者使用經(jīng)常用來(lái)研究隨機(jī)過(guò)程的經(jīng)典馬爾可夫模型, 對(duì)用戶的瀏覽序列進(jìn)行挖掘.根據(jù)用戶訪問(wèn)的頁(yè)面序列，通過(guò)構(gòu)建馬爾可夫模型預(yù)測(cè)用戶下一個(gè)要訪問(wèn)的頁(yè)面[4].很多學(xué)者從事網(wǎng)頁(yè)數(shù)據(jù)挖掘的研究[5,6,7]，使用了多種技術(shù)，包括使用數(shù)據(jù)挖掘技術(shù)應(yīng)用于Web數(shù)據(jù)挖掘、馬爾可夫鏈和概率模型等.用戶點(diǎn)擊網(wǎng)頁(yè)，蘊(yùn)含著用戶對(duì)網(wǎng)頁(yè)上隱藏的概念感興趣，因此，本文提出一種新的基于隱馬爾可夫模型的興趣發(fā)現(xiàn)方法, 指導(dǎo)網(wǎng)頁(yè)設(shè)計(jì)者設(shè)計(jì)出更吸引用戶的網(wǎng)頁(yè)結(jié)構(gòu).

文中第2節(jié)給出一些定義；第3節(jié)介紹隱馬爾可夫模型.第4節(jié)構(gòu)建web挖掘的隱馬爾可夫模型.第5節(jié)通過(guò)真實(shí)的實(shí)驗(yàn)說(shuō)明這種方法的實(shí)用性.第6節(jié)是總結(jié)以及對(duì)未來(lái)研究方向的展望.

1 相關(guān)定義

定義1 用戶訪問(wèn)概念R: 當(dāng)用戶訪問(wèn)網(wǎng)站時(shí), 他所訪問(wèn)的目標(biāo), 他所感興趣的事物或概念,其用r表示.超鏈接文字說(shuō)明概括了網(wǎng)頁(yè)的內(nèi)容，因此，所有超鏈接當(dāng)中的描述文字就組成了訪問(wèn)概念，某用戶訪問(wèn)的所有概念組成了用戶的概念集R=(r1, r2, …, rn),n表示用戶的概念數(shù).

定義2 網(wǎng)站可以看成是一個(gè)由網(wǎng)頁(yè)為節(jié)點(diǎn)、超鏈接為弧的有向圖,表示為G = ( P , L ).其中,P=（p1，p2，…，pn）為網(wǎng)頁(yè)集, L為超鏈集合，如圖1所示.

定義3 用戶會(huì)話表示為一定時(shí)間內(nèi), 用戶的連續(xù)訪問(wèn)的網(wǎng)頁(yè)序列,定義為S = (s1, s2, …, sm).其中, si 為訪問(wèn)網(wǎng)頁(yè), m為會(huì)話路徑長(zhǎng)度.訪問(wèn)si和si+ 1的時(shí)間間隔小于設(shè)定的閾值τ；對(duì)網(wǎng)頁(yè)a和b,若si= a,si+ 1= b,且1≤i＜ n,則認(rèn)為b跟隨a,表示為a→b.說(shuō)明：用戶訪問(wèn)的概念就蘊(yùn)含在網(wǎng)頁(yè)中.每張網(wǎng)頁(yè)蘊(yùn)含多個(gè)不同的概念；而每一個(gè)概念蘊(yùn)含在不同的網(wǎng)頁(yè)當(dāng)中.

2 隱馬爾可夫模型

馬爾可夫預(yù)測(cè)法就是一種預(yù)測(cè)事件發(fā)生概率的方法，它是基于馬爾可夫模型的，根據(jù)事件的目前狀況預(yù)測(cè)其將來(lái)各個(gè)時(shí)刻或時(shí)期狀況的一種預(yù)測(cè)方法.模型描述為：一個(gè)系統(tǒng)有N個(gè)狀態(tài) S1，S2，???，Sn，隨著時(shí)間推移，系統(tǒng)從某一狀態(tài)轉(zhuǎn)移到另一狀態(tài)，設(shè)qt為時(shí)間t的狀態(tài)，系統(tǒng)在時(shí)間t處于狀態(tài)Sj 的概率取決于其在時(shí)間 1，2，???,t-1的狀態(tài)，該概率為：

如果系統(tǒng)在t時(shí)間的狀態(tài)只與其在時(shí)間 t-1的狀態(tài)相關(guān)，而與其它時(shí)間的狀態(tài)無(wú)關(guān)，則該系統(tǒng)構(gòu)成離散的一階馬爾可夫鏈(馬爾可夫過(guò)程)：

隱馬爾可夫模型 (Hidden Markov Models, HMM)是一個(gè)雙重隨機(jī)過(guò)程, 具有狀態(tài)序列和觀測(cè)序列.具體的狀態(tài)序列不能觀察到, 只知狀態(tài)轉(zhuǎn)移的概率, 即模型的狀態(tài)轉(zhuǎn)換過(guò)程是隱蔽的, 可觀察事件的隨機(jī)過(guò)程是隱蔽的狀態(tài)轉(zhuǎn)換過(guò)程的隨機(jī)函數(shù)[8].HMM由兩個(gè)組成部分:（1）馬爾可夫鏈: 描述狀態(tài)的轉(zhuǎn)移, 用轉(zhuǎn)移概率描述.（2）一般隨機(jī)過(guò)程:描述狀態(tài)與觀察序列間的關(guān)系, 用觀察值概率描述.

圖2是水藻的狀態(tài)與天氣相關(guān)的隱馬爾可夫模型.此時(shí)，圖中就有兩組狀態(tài)：觀察序列（虛線上方：水藻的狀態(tài)）和狀態(tài)序列（虛線下方：天氣狀態(tài)）

圖2 水藻和天氣狀態(tài)關(guān)系的隱馬爾可夫模型

對(duì)于一個(gè)隨機(jī)事件，有一觀察值序列：O=O1,O2,…OT,該事件隱含著一個(gè)狀態(tài)序列：Q=q1,q2,…qT.一個(gè)隱馬爾可夫模型 (HMM) 是由一個(gè)五元組描述的：λ＝（N,M,A,B,π）其中：

N = {q1,...qN}： 隱含狀態(tài)的有限集合

M = {v1,...,vM}：觀察狀態(tài)的有限集合

A = {aij}，aij= P(qt= Sj|qt-1= Si)：隱含狀態(tài)轉(zhuǎn)移概率矩陣

B = {bjk}，bjk= P(Ot= vk| qt= Sj)：觀察狀態(tài)概率分布矩陣

π= {πi}，πi = P(q1 = Si)：初始狀態(tài)概率分布

3 網(wǎng)頁(yè)訪問(wèn)序列模型的構(gòu)建

3.1 獲取用戶會(huì)話集

對(duì)服務(wù)器Log文件處理, 整理成服務(wù)器會(huì)話集.

具體過(guò)程如下：

(1) 刪除Log 文件中訪問(wèn)失敗的記錄，如刪除HTTP協(xié)議狀態(tài)碼中大于或等于400的記錄，刪除訪問(wèn)腳本文件、圖像文件的記錄；

(2) 按用戶的IP 地址,將Log 文件分割成屬于每個(gè)用戶的訪問(wèn)記錄集；

(3) 分別處理每個(gè)用戶的記錄集.將記錄集的訪問(wèn)記錄按時(shí)間先后排序;設(shè)立時(shí)間窗口閾值τ,分割訪問(wèn)記錄集; 對(duì)于時(shí)間間隔小于τ的相鄰訪問(wèn)記錄, 則認(rèn)為它們是同屬于一個(gè)用戶會(huì)話的相鄰訪問(wèn)請(qǐng)求;所有的會(huì)話組成用戶會(huì)話集.

(4) 所有用戶會(huì)話集組成服務(wù)器會(huì)話集.

3.2 構(gòu)建web挖掘的隱馬爾可夫模型

用戶瀏覽網(wǎng)頁(yè)，帶著某種信息需求, 然后跟隨超鏈引導(dǎo)，閱讀網(wǎng)頁(yè).這種信息需求表現(xiàn)為對(duì)某些概念的興趣.若能從用戶瀏覽路徑的分析中挖掘出隱含的信息需求, 就可以挖掘出用戶的興趣，最終可以把網(wǎng)頁(yè)修改成適合用戶的網(wǎng)站結(jié)構(gòu)，提供個(gè)性化的服務(wù).

通過(guò)以上分析，可利用 HMM模型用戶訪問(wèn)路徑.網(wǎng)頁(yè)包含的概念作為觀察狀態(tài)符號(hào)集，模型的觀察序列轉(zhuǎn)變成概念輸出序列，用戶訪問(wèn)路徑途經(jīng)的網(wǎng)頁(yè)集作為的隱含狀態(tài)集.計(jì)算出概念輸出序列的輸出概率，輸出概率越大，表明此概念越可能是訪問(wèn)路徑中用戶的需求概念，蘊(yùn)含該概念的信息量較大的網(wǎng)頁(yè),將被布局在網(wǎng)站中明顯的位置.根據(jù)實(shí)際的web數(shù)據(jù)挖掘，進(jìn)一步定義隱馬爾可夫模型 (HMM)，構(gòu)建是由一個(gè)五元組描述的：λ＝（N,M,A,B,π）

隱含狀態(tài)的有限集合（N = {q1,...qN}）：用戶會(huì)話中所瀏覽的網(wǎng)頁(yè)，作為模型的隱含狀態(tài)集.

觀察狀態(tài)的有限集合（M = {v1,...,vM}）：用戶會(huì)話中，所需求的概念R=(r1, r2, …, rn)，作為模型的觀察狀態(tài)集.

隱含狀態(tài)轉(zhuǎn)移概率矩陣（A = {aij}）：通過(guò)選擇用戶會(huì)話集中的網(wǎng)頁(yè)訪問(wèn)序列，最為訓(xùn)練樣本集，進(jìn)行訓(xùn)練得到.

觀察狀態(tài)概率分布矩陣（B = {bjk}）：以某網(wǎng)頁(yè)pi對(duì)某個(gè)概念ri的蘊(yùn)含程度作為觀察狀態(tài)的概率分布.蘊(yùn)含程度的計(jì)算方式考慮兩方面：一方面是網(wǎng)頁(yè)pi本身對(duì)概念ri的蘊(yùn)含程度；另一方面是從網(wǎng)頁(yè)pi引出的超鏈接所對(duì)應(yīng)的網(wǎng)頁(yè)的蘊(yùn)含程度.本文使用概念ri在網(wǎng)頁(yè)pi中出現(xiàn)的頻率最為計(jì)算依據(jù).

網(wǎng)頁(yè)pi對(duì)概念ri的蘊(yùn)含程度

W= Wpi(rj)+ Wp’(rj) p’（表示所有從網(wǎng)頁(yè)pi引出的網(wǎng)頁(yè)）

初始狀態(tài)概率分布（π= {πi}）：使用網(wǎng)頁(yè)pi在用戶會(huì)話中出現(xiàn)的次數(shù)比上所有網(wǎng)頁(yè)出現(xiàn)的次數(shù)作為此網(wǎng)頁(yè)的初始狀態(tài).

3.3 評(píng)價(jià)頁(yè)面

根據(jù)概念序列，計(jì)算出輸出概率較大的概念，選出幾個(gè)概率的概念，然后從網(wǎng)頁(yè)中選取對(duì)這些概念蘊(yùn)含程度最大的一些網(wǎng)頁(yè)，把這些推薦給用戶.

4 具有真實(shí)背景的實(shí)驗(yàn)

本文選取了Deep Log Analyzer日志分析軟件里自帶的日志文件ex0511.log進(jìn)行分析，日志格式是IIS的W3C日志格式，文件大小36M，該日志文件服務(wù)器網(wǎng)址是，http://www.interactivegt.com/.實(shí)驗(yàn)數(shù)據(jù)包括從2005-11-12 0:01:21 - 2005-11-25 23:59:50用戶對(duì)站點(diǎn)14天的訪問(wèn)數(shù)據(jù).整個(gè)站點(diǎn)包括130個(gè)html 頁(yè)面，有82226個(gè)點(diǎn)擊，過(guò)濾掉圖片、點(diǎn)擊錯(cuò)誤等，剩下32175項(xiàng)正常訪問(wèn)，識(shí)別出4368用戶訪問(wèn)事務(wù), 去掉長(zhǎng)度為1的事務(wù)后，平均訪問(wèn)事務(wù)長(zhǎng)度為4.6, 即用戶平均每次訪問(wèn)4.6個(gè)頁(yè)面.選擇前2000個(gè)會(huì)話作為訓(xùn)練樣本集；使用后面的會(huì)話作為驗(yàn)證數(shù)據(jù)，得到的準(zhǔn)確度是62%，與文獻(xiàn)[9]相比有一定的提高，效果更好.

5 結(jié)論

網(wǎng)頁(yè)個(gè)性化服務(wù)技術(shù)已經(jīng)在許多實(shí)際運(yùn)用中獲得較好的效果,如一些知名的門(mén)戶網(wǎng)站已經(jīng)根據(jù)用戶的訪問(wèn)歷史，向用戶推薦他們將要訪問(wèn)的頁(yè)面，提高了網(wǎng)站的服務(wù)質(zhì)量，從而也提高了用戶的忠誠(chéng)度.本文采用HMM 模型分析用戶的訪問(wèn)路徑, 通過(guò)挖掘用戶信息需求概念, 找出蘊(yùn)含客戶需求信息量較高的網(wǎng)頁(yè),推薦給用戶，最終實(shí)現(xiàn)基于語(yǔ)義的網(wǎng)站可行化服務(wù).測(cè)試結(jié)果表明,該方案具有較高的預(yù)取準(zhǔn)確度.我們進(jìn)一步的工作將使用聚類(lèi)算法對(duì)每個(gè)客戶的訪問(wèn)行為進(jìn)行歸類(lèi)，對(duì)每一類(lèi)的客戶進(jìn)行服務(wù).原因是不需要使用用戶的IP地址進(jìn)行分類(lèi)，這樣可以挖掘出使用動(dòng)態(tài)IP上網(wǎng)客戶的行為；另一個(gè)原因是，使用聚類(lèi)算法進(jìn)行數(shù)據(jù)挖掘得到的客戶類(lèi)別比較少，針對(duì)類(lèi)別進(jìn)行的個(gè)性化服務(wù)效率更高.

[1]Coo ley R,MobasherBetal.GroupingWebpage references in2to t ransact i ons formining Wo rld W ide Web browsing patterns.In:P roc Knowledge and Data Engineering Workshop,New2po rt Beach, CA,1997:245- 253.

[2]Coo ley R,Mobasher Betal.Data Preparation for Mining WorldWide Web Browsing Patterns.Knowledge and Informa tion Systems,1999,1(1):207- 213.

[3]李桂英,李吉桂.基于模糊聚類(lèi)的Web日志挖掘[J].計(jì)算機(jī)科學(xué),2004,31(12):130-132.

[4]Deshpande M,Kary pis G.Selective Markov Models for Predicting Web-pag Eaccesses[A].Proceedings SIAM Int Conference on Data Mining [C].Chicago:[s.n.],2001.

[5]SuYo ung Y, Eunsoo k J, Jungmin S.Prefetching brand-new documents for improving the Web performance[EB/OL].http: //www.isoc.org/inet99/proceedings/posters/106,1999-08-10/2001-11-13.

[6]朱培棟,盧錫城,周興銘.基于客戶行為模式的Web文檔預(yù)送[J].軟件學(xué)報(bào),1999,10(11):1142-1147.

[7]Deshpande M, Karypis G.Selective markov models for predicting Web-page accesses[A].ProceedingsSIAM Int Conference on Data Mining[C].Chicag o:[s.n.],2001.

[8]侯傳宇.馬爾可夫及隱馬爾可夫模型在數(shù)據(jù)挖掘中的應(yīng)用[J].電腦知識(shí)與技術(shù) ,2008,(7).

[9]許歡慶,王永成,孫強(qiáng).基于隱馬爾可夫模型的Web網(wǎng)頁(yè)預(yù)取[J].上海交通大學(xué)學(xué)報(bào),2003,37(3):404-407.