基于路徑聚類的頁面訪問次序的挖掘

張春娜，李軼然

（遼寧科技大學 軟件學院，遼寧 鞍山114051）

0 引 言

隨著網絡的快速發展，Web站點的體系結構以及服務模式與以往大大不同，用戶訪問模式與傾向自由度也發生了深層次的變化。網站設計人員需盡可能的優化站點吸引用戶，他們也試圖去發現一些隱含性的信息，比如某些Web活動的有用模式或是潛在的行為知識，日志文件中用戶的關聯性、訪問習慣、時序關系等。這樣，通過有效的分析即可了解用戶的行為模式。

一般意義上聚類過程是對某一空間域有限數據集中有限點實施聚類，其最終目的是將有用數據劃分為不同的類，保持異類低相似度，同類高相似度［1］。以一個 Web站點為例，通常頁面間的關系是網狀的，彼此之間通過鏈接相聯系，同一個節點下的子頁面相似度較高，也可理解為用戶的對該類子頁面的興趣度相似。用戶訪問Web站點的時序性與興趣度具有正相關性，對于一個用戶群，興趣相投者往往訪問時序也有一定相似性，體現某種規律。比如，用戶us1依次訪問了網頁UR1，UR2，UR3，...，URn，可以以下列式子來表示該用戶訪問順序與興趣度之間的關系

I（UR1）＞I（UR2）＞I（UR3），...，＞I（URn）

這個式子說明用戶對頁面的訪問次序與興趣度存在一定關系，最先被訪問的頁面往往興趣度較高，因此需要采用一種聚類方法對日志文件中頁面關系予以處理［2］，對相似度較高頁面實施歸類，據此管理者可根據這種規律性調整站點結構，迎合用戶個性化要求。目前，對Web站點日志的分析通常的步驟是對站點信息的預處理［3－4］，用戶訪問行為處理，然后進行路徑聚類。

其中文獻［5］將用戶事務轉化為一個三元組，提出一種基于用戶訪問事務聚類算法。聚類過程中考慮了用戶訪問頁面的先后次序以及時長，但缺乏對訪問頻繁度的分析，這一點與本文考察重點相悖。

文獻［6］所構建的系統基于代理技術，是在線推薦引擎和URL聚類的結合體。提出的推薦規則集生成算法，主要參考關聯規則，算法同時考慮了用戶瀏覽次數和停留時間等因素，考慮因素較為全面，只是沒有涉及頁面的訪問次序。

文獻［7］采用模糊聚類的方法來處理用戶訪問事務。其思想是基于模糊和模糊集理論，提出一種從集群模糊邊界考慮問題的路徑聚類方法，同樣，該方式也沒有考慮用戶訪問頁面的先后次序；文獻［8］另辟蹊徑，從提高路徑搜索性能的角度出發，結合道路建設的相似性，給出預期路徑；而文獻［9］是提出了一種新的頁面預處理方式，是數據整理工作的前提；文獻［10］是關于數據集的聚類簇隸屬關系的討論；文獻［11］則從競爭策略的角度獲取最佳聚類數。

以上文獻中缺少一個共同的聚類分析切合點——網頁訪問次序，也就是同類中不同節點的有序關系，而這正式本文所研究的重點。

1 聚類準備

路徑聚類是找出用戶訪問行為中某種特性，它體現在用戶點擊頁面路徑的相似性所形成的域中。用戶對Web站點的訪問過程用興趣軌跡來描述，即由一組鏈接地址所構成的訪問路徑。用戶群體現出相似路徑時，則可將該群體劃分為一類，并為其定義訪問行為模式，在其域上進行聚類分析，獲取有用信息。

日志文件中存放用戶訪問信息，格式需遵循W3C標準，站點的結構可用有向圖表示，如D＝（V，M），其中V代表頁面集合，M代表頁面鏈接集合。據此可以得到用戶行為訪問模式。

定義1 Web站點日志文件：假定F為用戶訪問信息，令F＝｛（fu.ip，fu.us，fu.url，fu.time）｜1≤u≤n，f∈F｝，其中F代表Web站點日志信息，fu表示實際用戶u的訪問信息，包括用戶本身的IP地址fu.ip、用戶的標識fu.us、用戶訪問頁的地址fu.url、用戶訪問頁面的具體時間fu.time。

下一步工作的重點是日志文件的整理，即剔除非研究對象，包括頁面中的視頻、圖像、聲音等多媒體文件信息，保留文字和HTML格式信息。經過整理后，還需識別出用戶事務信息。

在定義用戶事務時，需提到一點，用戶對某一頁面的訪問稱為會話，不同用戶或是同一用戶對指定頁面的間隔時間訪問理解為不同的會話，因為用戶對頁面的訪問可能會有多次。處理事務過程中，需定義一個時間間隔以區分不同會話。

定義2 用戶訪問事務

其中，m為用戶u訪問的最后一個頁面。用戶在網不同訪問行為用T＝fi.time－fj.time表示，記T為該用戶的時間窗口，1≤i，j≤m。

定義3 用戶訪問子事務：不同用戶不同時間段的訪問行為可進一步劃分為用戶訪問子事務。設用戶訪問事務為UT，則子事務可表示為：.url｜1≤v≤n｝∈ ｛fu.url｜1≤u≤n｝，即用戶訪問事務中任何一個頁面列表長度不超過原始頁面列表長度的子列表。

定義4 頁面鏈接參數：Web站點中頁面不僅僅包括內容信息頁面，也需要功能性頁面，比如導航頁、搜索頁、主題頁等。頁面作用各有不同，數據挖掘中要加以區分，不同類型頁面附應于相應權值，涉及到應用的范圍權值有高低之分，設定是依據經驗，并不失一般性，也可能選取樣本數據實施訓練進行自適應計算。這里，為了方便以及更好的說明頁面的差異性，以經驗量化指標限定，稱作頁面鏈接向量參數

式中：RLk——第k個頁面的頁面鏈接參數，si——該頁面被鏈接的總數，S——頁面間總鏈接數，Q——頁面加權因子。

為了遍歷每個用戶事務，本文試圖找到通用的處理方式，步驟如下：

（1）站點用戶信息篩選；

（2）對經過篩選后的站點日志文件進行預處理；

（3）將日志中每個用戶進行歸類，即將每個IP地址相關內容劃分成集；

（4）確定訪問事務，利用時間窗口T確定每個用戶的訪問內容，每段訪問內容構成一個數據集，稱為用戶訪問事務，進而劃分子事務。

（5）考察訪問次數與停留時間，對于同一用戶同一地址的記錄，在訪問事務中記錄一次，其它訪問只記錄次數且不放入數據集；每次訪問的停留時間則需一一記錄，附于每個事務末端；

（6）數據集整理，按時間對用戶訪問事務進行排序，組成時間序列事務集。

偽代碼如下：

在一個時間窗口內，每一個用戶訪問事務都有一個頁面鏈接列表；同樣，相對于全體用戶訪問事務而言，時間窗口內，新生成的用戶事務代表了一個非重復的訪問路徑，數據集中存放了用戶某一段時間訪問路徑，尋找到路徑的相似性，通過算法即可路徑聚類，最終發現用戶訪問模式。

2 K－PathSearch

本文提出K－PathSearch路徑聚類算法，該方法通過生成的數據集進行特征聚類，同時考慮到用戶的興趣度，對用戶訪問頁面的先后次序進行處理，經過多次迭代聚類，得到真正反映用戶實際情況的訪問序列。本文在充分考慮訪問次序的前提下，剔除了多余的同址訪問記錄，比照其它方法，該算法更加高效可靠，具體算法思想如下：

（1）設定數據集F，設定參數k用來劃分聚類數；

（2）設計聚類中心，并對其初始化。即將數據集中n個事務，以k為單位劃分聚類，注意聚類中每個用戶事務必須保證與聚類中心相似度總和最??；

（3）依據聚類中心模型重新計算聚類中心，并將聚類結果演化成矩陣，整理聚類中心與相關矩陣，組成收斂評價函數Q；

（4）經過有限次循環計算收斂評價函數Q，算法返回值應逐步收斂，直到符合要求止，否則跳轉到（3）繼續迭代。

定義5 興趣度：傳統的聚類分析是對給定的空間散列點有限集的取樣，或是對某一數據體的分析與歸納，最終使零散變為規整；而針對Web站點，因其具有一定的規律性，站點間可組成有序的序列。因此，用戶訪問Web站點對某一頁面的關注度，可表示為Interest（fuurl，RL），用戶訪問地址序列可表示為（f1url，f2url，···，fnurl），不同興趣度決定訪問次序

其中Interest（fkurl，RL）1＜k＜n。

設有群體用戶u1，u2，···，un，訪問 Web站點用數列表示

可見，訪問次序不僅適用于單體，亦適用于群體特征描述。分析數列得到群體用戶訪問路徑url11，url12，url15，url13，url14，相應興趣度可表示為

其中，U代表群體，即個體用戶的訪問次序決

定整個群體的興趣度。

需提出一點，若用戶訪問事務中出現重復出現的url，注意用戶地址興趣度的累計，地址信息只記錄一次即可。

定義6 相似度：相似度與興趣度存在一定因果關系，即在同一鏈接中，兩個用戶對于某一網頁興趣度一致，說明兩個用戶相似度較高；反之較低。設兩個用戶訪問事務分別為Si和Sj，則相似度可表示為

其中，興趣度差值的絕對值越接近于0，表明二者相似度越高。

定義7 聚類中心：基于回歸分析中散點圖，本文假設用戶興趣度為自變量，選擇的鏈接地址為因變量，則不同類型的訪問用戶相關數據點應產生聚合，并最終擬合。通過定義3，得到用戶訪問路徑圖如圖1所示。

圖1 用戶訪問路徑

由上所述，給出如下定義：用戶訪問最長擬合路徑，即，將從初始地址出發，集合成員所有訪問地址最為相似的最長路徑。由此，得到聚類C＝｛ci｜1＜i＜n｝，ci中包括若干個用戶訪問事務，一個類中的事務相似度較高，群體中心，即類中興趣度累加最大的路徑，全路徑可用下式表示

其中，最大路徑表示為

參考定義5中數列，即可得到最長擬合路徑，在這個數列中，我們假定用戶訪問路徑是定長的，為了方便處理，將其轉化為向量形式，表示如下

將用戶訪問事務向量演化成矩陣

式中：m——Web站點日志中所有用戶事務，n——每個用戶事務的長度，即訪問地址數，這里假定長度定長。

本文提出K－PathSearch算法并非傳統的層次聚類方法，而是以相似度為參考條件，對路徑進行分類的方法。算法的核心思想是將事務集合劃分為若干個聚類，cen（ci）表示第i組依據興趣度組成的頁面，需要提出的是，這個路徑可能并不是真實存在，要考慮的問題圍繞式（5）與式（3）展開，定義聚類擬合函數如下所示

式中：vi，j——矩陣中一項，最大值m和n可相等，亦可不等。對擬合函數的求解過程做如下假設：由于W是V的子集，這里的操作分兩個步驟，分別將Q（V，W，C）中除了W之外其它兩個參數分別設為常量，以進行求解。

（1）設C為常量，求解Q（V，W，C）

其中，1≤k≤m。

（2）設W為常量，求解Q（V，W，C）：

1）設定初始常量C0，求解Q（V，W，C），從而得到初始W0；

2）設k＝0，以C0、W0推導C1，依次類推，得到C2，···，Cm，進而得到W1，W2···，Wn。推導過程中，若Q（V，W，Ci）＝Q（V，W，Ci＋1），則輸出相應W，結束算法；否則，執行第三步；

3）以C0、W0推導W1，同樣得到W2，···，Wn，進而得到C1，C2···，Cm。此時，若Q（V，Wj，C）＝Q（V，Wj＋1，C），則輸出相應C，算法結束；否則跳轉到第二步。

依此計算，經過有限次的迭代，算法將收斂并得到一個局部最優解。

3 實驗驗證

本文實驗數據取自于電子商務旅游網站服務器日志，區間為2011年5月至2011年9月，數據經過預處理剔除掉一些不必要的數據，得到多條內容訪問記錄。整個網站包括225個頁面，用戶訪問頁面容量56M，經過算法分析，得到用戶訪問事務3221個，群體用戶平均訪問路徑長度為6.2。本文按時間區間對五組數據進行驗證，算法應用前后對比表見表1。

表1 算法應用前后對比

從實驗數據看出，算法應用后聚類數較之前提高26%，聚類中心平均長度提高38%，提高幅度較大，達到預期效果。二者對站點訪問用戶的細分以及站點內容本身的分類影響較大，其直接對用戶的劃分產生作用，更能有效的反應用戶的個性化特征，故，有助于管理者調整網站結構、細分用戶，條理清晰。因此，算法可認為是有效的。

4 結束語

基于用戶對Web站點的訪問次序，本文提出了KPathSearch算法，它是一種分割聚類方法，用于聚類用戶訪問路徑。文中重點考察用戶的興趣度，在設定用戶訪問事務的基礎上，引入頁面鏈接參數，利用參數因子以區分頁面性質，這樣即可對經過預處理后的頁面實施二次整理，以方便頁面聚類分析。再者，算法應用后聚類數顯著增加，更加便于理解用戶的真實需求，網站管理者可及時調整站點結構以迎合客戶。同時，算法也考慮了頁面之間的關系，比照用戶相似度試圖提供一些個性化較強的服務。

［1］Vassiliki A Koutsonikola，Athena I Vakali.A fuzzy bi－clustering approach to correlate web users and pages［J］.International Journal of Knowledge and Web Intelligence，2009，1（1／2）：3－23.

［2］LIU Yunfeng.A text information extraction algorithm based on tag xpath clustering［J］.Computer Applications and Software，2010，21（11）：199－202（in Chinese）.［劉云峰.一種基于標簽路徑聚類的文本信息抽取算法［J］.計算機應用于軟件，2010：21（11）：199－202.］

［3］Yang S H，Lin H L，Han Y B.Automatic data extraction from template generated Web pages［J］.Joumal of Software，2008，19（2）：209－223.

［4］Ou Jian－Chih，Lee Chang－Hung，Chen Ming－Syan.Efficient algorithms for incremental Web log mining with dynamic thresholds［J］.The VLDB Journal，2008，17（4）：827－845.

［5］LU Qun，ZHANG Zhongneng.Research on path clustering in web sites［J］.Computer Applications and Software，2008，25（8）：205－206（in Chinese）.［盧群，張忠能.Web站點的路徑聚類研究［J］.計算機應用與軟件，2008，25（8）：205－206.］

［6］SONG Jiangchun，SHEN Junyi.An intelligent recommendation system based on web navigation path clustering［J］.Information and Control，2007，36（1）：119－124（in Chinese）.［宋江春，沈鈞毅.一個基于Web訪問路徑聚類的智能推薦系統［J］.信息與控制，2007，36（1）：119－124.］

［7］Hong Yu，Hu Luo，Chu Shuangshuang.Web users access paths clustering based on possibilistic and fuzzy sets theory［C］／／ADMA（1），2010：12－23.

［8］Lee Jae－Min，Hwang Byung－Yeon.Two－Phase path retrieval method for similar XML document retrieval［G］.LNCS 3681：Khosla R，et al.（Eds.）：KES，2005：967－971.

［9］WU Junjie，CHEN Junjie，ZHAO Shuanzhu.Research of path clustering based on the access interest of users［J］.Computer Engineering and Applications，2005，41（36）：170－171（in Chinese）.［吳俊杰，陳俊杰，趙栓柱.基于用戶訪問興趣的路徑聚類研究［J］.計算機工程與應用，2005，41（36）：170－171.］

［10］CHEN Jianmei，LU Hu，SONG Yuqing.A possibility fuzzy clustering algorithm based on the uncertainty membership［J］.Journal of Computer Research and Development，2008，45（9）：1486－1492（in Chinese）.［陳健美，陸虎，宋余慶.一種隸屬關系不確定的可能性模糊聚類方法［J］.計算機研究與發展，2008，45（9）：1486－1492.］

［11］Yu Yijun，Lin Huaizhong，Chen Chun.Personalized web recommendation based on path clustering［C］／／Proceedings of the 10th WSEAS International Conference on Computers，2006：148－153.