基于用戶訪問序列挖掘的站點路徑優(yōu)化分析

[摘要]由于網(wǎng)站的結(jié)構(gòu)設(shè)計，對特定用戶而言信息獲取的代價與所經(jīng)過的瀏覽路徑長度成正比，這些位于路徑中間的不必要的文檔就無疑增加了用戶獲取信息的代價。本文利用Web挖掘的方法和技術(shù)對用戶所訪問的頁面序列進行挖掘，構(gòu)建路徑優(yōu)化的模型，實現(xiàn)對當前站點排序方式的優(yōu)化，從而最大限度地優(yōu)化用戶訪問體驗，提高當前站點信息獲取的整體效率。

[關(guān)鍵詞]站點路徑優(yōu)化；Web挖掘；訪問序列

傳統(tǒng)的Web網(wǎng)站以系統(tǒng)自身為中心，為了容納大量的信息，以圖結(jié)構(gòu)組織網(wǎng)站，頁面之間存在著比較復雜的層次關(guān)系。這些預先設(shè)計好的瀏覽路徑(網(wǎng)站的結(jié)構(gòu))嚴格按照設(shè)計者編輯好的層次返回頁面，因此，為了獲取特定的信息，從同一頁面出發(fā)的所有用戶都不得不重復地經(jīng)過很多與自己毫無關(guān)系的、不希望看到的中間鏈接頁面，使得用戶為了獲取少量的信息付出較大的代價[1]。如果在確保網(wǎng)頁內(nèi)容的前提下，實現(xiàn)網(wǎng)站物理結(jié)構(gòu)的調(diào)整和再組織，就可以避免混亂。站點路徑優(yōu)化實際上就是站點管理者優(yōu)化其站點結(jié)構(gòu)，它的出現(xiàn)就是為了提高用戶的訪問效率以及用戶對站點的忠誠度。

1站點個性化與路徑優(yōu)化

Web站點結(jié)構(gòu)設(shè)計好壞的衡量標準之一是用戶為獲取所需信息所付出的平均代價，而這種代價則可以理解為所經(jīng)過的超鏈數(shù)目和選擇這些超鏈的困難程度的函數(shù)。用戶的瀏覽路徑優(yōu)化就是在盡量不破壞Web系統(tǒng)原有結(jié)構(gòu)，即不刪除系統(tǒng)原有文檔和超鏈的前提下，通過增加新的超鏈或文檔來減少用戶獲取信息所需付出的平均代價。

所謂站點個性化實質(zhì)上就是為站點用戶提供個性化的站點訪問體驗。對于一般站點而言，站點管理者進行路徑優(yōu)化的直接目的就是提高用戶點擊行為的效用度，最終目的是提高用戶滿意度與忠誠度。站點路徑的優(yōu)化實際上就是優(yōu)化站點結(jié)構(gòu)，消除站點實際安排與用戶期望之間差異的過程，它為站點個性化提供了一種思路，即用戶一系列的瀏覽行為所遍及的頁面序列就是用戶針對目標頁面的尋找過程，此時站點設(shè)計可以考慮調(diào)整網(wǎng)站的結(jié)構(gòu)、在頻繁訪問路徑處添加指向目標頁面的鏈接，或者是將常見瀏覽路徑加入緩存，如圖1所示。

圖1網(wǎng)狀結(jié)構(gòu)中的路徑優(yōu)化

網(wǎng)站的頻繁瀏覽路徑體現(xiàn)了特定的用戶在特定時期內(nèi)的活動規(guī)律，是站點路徑優(yōu)化的依據(jù)。它包括兩個方面的內(nèi)容：首先是個體用戶在其瀏覽歷史區(qū)域中多次重復出現(xiàn)的瀏覽路徑，另一方面即用戶群體在一定時期中瀏覽歷史區(qū)域內(nèi)出現(xiàn)的瀏覽重復行為，即瀏覽模式。

個體用戶的一條瀏覽路徑對應于用戶的一段信息探求過程。根據(jù)個體用戶的重復瀏覽路徑，就可以形成用戶興趣視圖，并依據(jù)用戶興趣視圖完成個性化推薦，為用戶提供定制的訪問體驗。而用戶群體在較長時期內(nèi)穩(wěn)定的行為模式則為網(wǎng)站結(jié)構(gòu)的改進和路徑的優(yōu)化提供了參考依據(jù)。如果在一定時期內(nèi)大多數(shù)用戶都表現(xiàn)出訪問路徑的相似性，此時Web站點就要做相應的訪問路徑優(yōu)化。

前者可以為用戶提供“一對一”的具備自適應性的在線動態(tài)智能個性化服務，這種智能個性化服務可大大縮短用戶在網(wǎng)絡上的訪問延遲，使得提供給用戶的網(wǎng)絡信息服務質(zhì)量得到最大限度的提高。后者則通過離線修改實施改進，用以優(yōu)化用戶瀏覽體驗，提高當前站點信息獲取的整體效率，同時提高用戶滿意度和忠誠度。2基于Web挖掘的路徑優(yōu)化模型

Web挖掘從數(shù)據(jù)挖掘發(fā)展而來，但Web挖掘與傳統(tǒng)的數(shù)據(jù)挖掘相比有許多獨特之處。首先，Web挖掘的對象是大量、不同和分散型的Web文件；其次，Web文件本身是半結(jié)構(gòu)化或無結(jié)構(gòu)的，因此Web挖掘所得到的模式可能是關(guān)于內(nèi)容的，也可能是關(guān)于結(jié)構(gòu)的；最后，有些數(shù)據(jù)挖掘技術(shù)并不適用于Web挖掘，即使可以用也需要建立在對Web文件進行預先處理的基礎(chǔ)之上。

訪問序列挖掘?qū)崿F(xiàn)過程的理論分析

為了跟蹤用戶以往瀏覽的網(wǎng)頁，對網(wǎng)頁訪問數(shù)據(jù)進行挖掘，Web挖掘技術(shù)以Web日志為數(shù)據(jù)源。因為每當用戶在點擊鏈接向站點發(fā)出頁面瀏覽請求時，該用戶的IP地址、瀏覽日期和時間、瀏覽頁面URL及引用頁面等信息會被記錄在Web日志中，用戶瀏覽點擊頁面就按照時間順序以頁面URL序列的形式隱藏在Web日志中。用戶訪問序列挖掘即通過對Web日志進行系統(tǒng)的分析和預處理，將用戶以往的瀏覽序列從日志中提取及表示出來，并采用各種Web挖掘方法和算法從不同的角度獲得各類用戶可能的網(wǎng)頁瀏覽順序，探索總結(jié)出用戶瀏覽網(wǎng)頁的規(guī)則和模式。在獲得用戶瀏覽規(guī)律之后，通過模式分析識別用戶需求的鏈接，確定用戶瀏覽行為的目標就可以提高用戶瀏覽的總體性能，幫助改進網(wǎng)頁的設(shè)計和網(wǎng)站的鏈接結(jié)構(gòu)，同時確定可以用于緩存的瀏覽網(wǎng)頁信息。

從服務器的角度分析，挖掘發(fā)現(xiàn)的是提供服務的網(wǎng)站的信息，挖掘結(jié)果可以幫助改善網(wǎng)站的設(shè)計。從用戶的點擊序列分析，可以發(fā)現(xiàn)一個(或者一組)用戶的信息，可幫助實現(xiàn)網(wǎng)頁的預存取和緩存。

站點路徑優(yōu)化的模型構(gòu)建

以Web日志為數(shù)據(jù)源進行的站點路徑優(yōu)化的挖掘模型，采用了數(shù)據(jù)挖掘及Web日志挖掘的相關(guān)技術(shù)和算法獲取用戶瀏覽規(guī)則與模式，為網(wǎng)絡結(jié)構(gòu)優(yōu)化、站點重構(gòu)提供參考及個性化服務推薦設(shè)計提供了依據(jù)。據(jù)此站點路徑優(yōu)化的模型可分為數(shù)據(jù)預處理和站點路徑優(yōu)化實現(xiàn)兩個部分，站點路徑優(yōu)化部分可從兩個方面來考慮：一是通過對Web日志的挖掘，發(fā)現(xiàn)用戶的期望位置。如果在期望位置的訪問頻率高于實際位置的訪問頻率，可考慮在期望位置和實際位置之間建立導航鏈接，從而實現(xiàn)對Web站點的優(yōu)化。二是通過對Web日志的挖掘，發(fā)現(xiàn)用戶訪問頁面的相關(guān)性，從而對密切聯(lián)系的頁面之間增加鏈接，方便用戶使用。如圖2所示。

圖2利用Web挖掘技術(shù)的路徑優(yōu)化模型

3站點路徑優(yōu)化的實現(xiàn)

Web日志數(shù)據(jù)收集

Web服務系統(tǒng)是一個多層次的邏輯結(jié)構(gòu)，包括客戶端、代理服務器端、Web服務器端。本文挖掘的是本站點用戶的頻繁訪問路徑、用戶聚類等，因此適合采用Web服務器端的用戶訪問模式挖掘。Web服務器日志由三部分組成：訪問日志、引用日志和代理日志，包括用戶訪問Web站點時，所訪問的頁面、時間、用戶ID等信息。

站點數(shù)據(jù)預處理

Web站點及訪問數(shù)據(jù)預處理部分主要包括站點結(jié)構(gòu)數(shù)據(jù)預處理、內(nèi)容數(shù)據(jù)預處理和Web日志數(shù)據(jù)預處理。其中，結(jié)構(gòu)數(shù)據(jù)預處理的任務是描述站點的拓撲結(jié)構(gòu)圖、站點頁面文件鏈接有向圖，并明確站點各個頁面文件鏈接的請求(Request)方法，如GET、POST、HEAD等。站點內(nèi)容數(shù)據(jù)預處理包括將文本、圖片、腳本和其他多媒體文件轉(zhuǎn)變?yōu)橛脩魧φ军c瀏覽模式記錄信息的開發(fā)與利用有用的格式。

用戶訪問序列挖掘的Web日志數(shù)據(jù)源預處理包括數(shù)據(jù)過濾、格式轉(zhuǎn)換、用戶識別、會話識別、路徑補全和事務識別，預處理過程是保證后繼挖掘質(zhì)量的關(guān)鍵。

基于Web日志挖掘的路徑優(yōu)化實現(xiàn)

在數(shù)據(jù)預處理之后，對所形成的用戶會話文件，利用數(shù)據(jù)挖掘的一些有效算法(如關(guān)聯(lián)規(guī)則、聚類、分類、序列模式等)來發(fā)現(xiàn)隱藏的模式規(guī)則。由于傳統(tǒng)的手工決策規(guī)則系統(tǒng)方法、基于內(nèi)容的過濾代理系統(tǒng)方法、協(xié)作過濾系統(tǒng)方法的種種不足，并且就分析和建立模型的技術(shù)而言站點路徑挖掘和傳統(tǒng)的數(shù)據(jù)挖掘差別并不是特別大，所以路徑優(yōu)化模式除了可以運用Web數(shù)據(jù)挖掘的很多方法和算法思想，也可以采用一般的統(tǒng)計方法和在線分析處理方法，如聚類分析方法、關(guān)聯(lián)規(guī)則分析方法和序列模式分析方法等[10]。

站點路徑優(yōu)化可以分為兩類：用戶群訪問模式挖掘的路徑優(yōu)化和個性化挖掘的路徑優(yōu)化。一般訪問模式挖掘的路徑優(yōu)化通過分析在特定時間點的特定用戶群的訪問記錄來了解用戶的瀏覽模式和傾向，以改進站點的組織結(jié)構(gòu)；而個性化挖掘的路徑優(yōu)化則傾向于分析個別用戶的偏好，其目的是根據(jù)用戶的訪問模式，為其提供定制服務。

個性化的瀏覽路徑優(yōu)化。Web站點的鏈接結(jié)構(gòu)是Web設(shè)計者根據(jù)一定的策略建立起來的，可能與用戶期望的鏈接結(jié)構(gòu)之間存在一定的差距。如圖所示，目標頁面X放在頁面B1下，但是用戶瀏覽路徑是F→A2→B2，因此用戶期望頁面X的位置在A2或B2下。如果事先能了解用戶的期望位置，從而在A2(或B2)和頁面X之間建立導航鏈接，自然就方便了用戶，提高了網(wǎng)站的訪問效率[1]。

(1)發(fā)現(xiàn)用戶期望位置。

設(shè){P1，P2，...，Pn}為用戶訪問過的頁面，Pn是一個目標頁面，B=Ф；∥B為回溯點的集合；

圖3用戶訪問站點路徑

For(i=2；i=n-2；i++)

{if(Pi-1=Pi+1)or(nolinkfromPitoPi+1)addPitoB}∥Pi是一個回溯點；

If(Bnotempty)addtable；

通過該算法，就可以找到用戶的返回點，這個位置可能是期望位置，也可能是目標頁面，但可以通過確定時間閾值來解決這個問題。當用戶在返回點停留的時間較長，超過指定的閾值，則認為該頁面是目標頁面，否則可以認為該頁面是期望位置。通常用戶在瀏覽Web站點時，在第一期望位置找不到目標頁面，就會在第二期望位置找，如果還找不到，會在第三期望位置找……，其中最受關(guān)心的是第一期望位置，而且是那些被第一期望且發(fā)生頻率高于系統(tǒng)設(shè)計者指定值的所有頁面。因此，尋找第一期望位置便成了我們關(guān)注的焦點[12]。

(2)目標位置和期望位置的判定。設(shè)Ei表示第一期望位置，算法先以用戶的ID為主關(guān)鍵字，時間為次關(guān)鍵字，對Web日志文件建立索引，掃描Web日志索引文件，對每一個用戶ID，摘取出頁面序列。

For(I=1；I=1；I++)∥n為Web日志中的記錄數(shù)

{統(tǒng)計Ei中所有頁面支持數(shù)；

Sortpagebysupport；

Ifsupport(P)=SI∥SI為Web設(shè)計者制定的閾值；

則P為被第一期望且發(fā)生頻率高于系統(tǒng)設(shè)計者指定值的頁面}

經(jīng)過提取目標頁面與期望位置之后，將形成如表1的目標頁面與期望位置匹配集[13]。

(3)調(diào)整站點結(jié)構(gòu)。根據(jù)該算法的挖掘結(jié)果，很多內(nèi)容頁面(目標頁面)的實際位置與用戶所期望的位置不一致，可以考慮依據(jù)這些目標頁面的用戶期望位置來調(diào)整目標頁面的實際位置。第一期望位置、第二期望位置……這些頁面從某種角度看是圍繞同一主題展開的，訪問了其中部分頁面的用戶往往也會訪問其他頁面，因此可以在這些頁面之間設(shè)置推薦鏈接。

用戶群訪問模式的路徑優(yōu)化。對用戶群訪問模式的問題，采用挖掘頻繁訪問的最大序列的方法可以挖掘出更有普遍意義的模式，算法包括有Apriori算法，最大向前序列法，參考長度法和樹形拓撲結(jié)構(gòu)法等。它們先將日志中的用戶瀏覽歷史記錄轉(zhuǎn)換成一個瀏覽子序列集：最大向前序列法根據(jù)用戶折返的特性形成若干瀏覽子序列；參考長度法根據(jù)用戶在網(wǎng)頁上停留的時間形成若干個瀏覽子序列；樹形拓撲結(jié)構(gòu)法則把整個日志當作瀏覽子序列。然后利用關(guān)聯(lián)規(guī)則法對瀏覽子序列進行挖掘找出頻繁訪問路徑。頻繁瀏覽路徑就是指按照一定順序組成的網(wǎng)頁序列集，用戶依照此序列訪問網(wǎng)站的頻度很高。

根據(jù)頻繁訪問路徑算法得到頻繁訪問路徑FP，對應記錄為X(fp，np)，其中fp表示URL組成的序列，np表示瀏覽路徑集合中FP出現(xiàn)的次數(shù)[14]。

forallX∈FP

forallY∈FPandY≠X

ifX.fp∈Y.fp.subthen=

∥檢查X.fp是否為另一記錄Y.fp的子序列

IfX.npn

∥n為預先設(shè)定的次數(shù)閾值

setSuplnik(X.fp)

∥設(shè)計新的從X.fp起點指向終點的超鏈。

該方法可以用于重構(gòu)Web站點的頁面之間的鏈接關(guān)系，及重構(gòu)Web站點的拓撲結(jié)構(gòu)、發(fā)現(xiàn)相似的客戶群體，開展個性化的信息服務和有針對性的電子商務活動，應用信息推拉技術(shù)構(gòu)建智能化Web站點。

4結(jié)語

站點路徑優(yōu)化就是通過Web挖掘技術(shù)來收集和統(tǒng)計用戶訪問過的歷史數(shù)據(jù)，挖掘當前用戶頻繁訪問的頁面序列，對個體用戶獲取其興趣模型，以便在用戶以后的訪問過程中根據(jù)興趣模型自動向用戶推薦內(nèi)容，指導用戶的瀏覽行為，提高瀏覽信息效率。對群體用戶獲取其訪問路徑規(guī)則與模式，通過增加超鏈改進站點結(jié)構(gòu)，將頁面加入緩存提高訪問速度，提高用戶對站點訪問的滿意度[15]。訪問規(guī)律的獲取對算法提出了較高的要求，可以借鑒現(xiàn)有模式發(fā)現(xiàn)算法實現(xiàn)瀏覽結(jié)構(gòu)的優(yōu)化。

[參考文獻]

[1]程舒通，徐從富，但紅衛(wèi).基于改進頻繁模式聚類算法的網(wǎng)站結(jié)構(gòu)優(yōu)化[J].計算機應用研究，2008(4)：268—269.

陽小華，周龍鑲.基于用戶訪問模式的WWW瀏覽路徑優(yōu)化[J].軟件學報，2001(6)：847—850.

繆勇.匿名用戶瀏覽路徑挖掘研究與實現(xiàn)[D].南京理工大學，2006.

阮備軍.Web使用挖掘若干關(guān)鍵問題研究[D].復旦大學，2004.

張素蘭，楊炳儒，范艷梅.一種基于圖結(jié)構(gòu)挖掘WEB用戶訪問模式的方法[J].計算機工程與應用，2004(12)：37—39.

易明，張揚.基于全信息的“點擊流”信息資源開發(fā)利用研究[J].情報科學，2007(12)：198—203.

杜文華.基于點擊流技術(shù)的