基于用戶多頁面瀏覽模式下的網絡結構推薦系統的研究

朱立夫 劉向東

摘要：針對用戶普遍使用的多頁面瀏覽器產生樹型結構的瀏覽路徑，web日志中將會呈現非時序的日志記錄。本文提出了一種新的自上而下的用戶訪問路徑收集算法，進而得出的用戶在一次會話中可能訪問的復數目的頁面，由此得出全局目的頁面訪問頻度矩陣，此矩陣的數據作為實現基于網絡結構的推薦系統的核心數據。

關鍵字：訪問路徑樹形；推薦系統；網絡結構

中圖分類號 TP274 文獻標識碼 A

Research on network structure recommendation system based on multi page browsing mode

ZHU Lifu1， LIU Xiangdong1

1（Changsha Furong Region People's ProcuratorateTechnical Department， Changsha 410016， China）

Abstract： Browsing path for the tree structure of multi page browser which is widely used by users， the web log will show non sequential log records. This paper presents a new top-down user access path collection algorithm， and then come to the complex page a user in a session may visit ， resulting in a global page access frequency matrix. This matrix data could be used as core data based on the recommendation system from the network structure.

Key words： access path tree； recommended system； network structure

0 引言

在Internet電子商務網站中，客戶在網站上的每一次點擊，作為網站后臺的Web服務器都會將這個動作如實地記錄在日志中，這為分析用戶訪問頻率、用戶訪問路徑、用戶訪問目的等信息提供了數據來源。通過分析Web瀏覽日志，發現用戶的訪問模式，提取用戶的訪問興趣，將得到的各種用戶信息進行整合研究，從而生成有效的決策信息，即可為用戶提供個性化推薦，同時還能進一步優化網站的拓撲結構。當前數據挖掘技術與Web日志分析已經實現了優質緊密結合。其中，Chen等人在1996年提出了可以將數據挖掘技術應用到Web領域中的思想，并且探討基于Web事務的Web日志挖掘過程，用以發現用戶的訪問模式，由此又定義了最向前引用算法MF的概念。Zaiane等人則將Web服務器日志保存為數據立方體（Data Cube），然后對數據立方體進行數據挖掘和聯機分析處理（OLAP）。而實現這些算法的前提是從Web日志中探究會話識別，并分離出用戶會話，進而提煉出用戶訪問路徑。針對用戶普遍使用的多頁面瀏覽器產生樹型結構的瀏覽路徑，Web日志中將會呈現非時序的日志記錄。基于此，本文提出了一種新的自上而下的用戶訪問路徑收集算法，運行得出用戶在一次會話中可能訪問的復數目的頁面，由此得出全局目的頁面訪問頻度矩陣，該矩陣的數據將可作為實現基于網絡結構的推薦系統的核心數據。

1基于多頁面瀏覽模式的用戶訪問路徑的收集算法

用戶訪問路徑樹，指用戶通過多頁面瀏覽器訪問模式瀏覽網頁形成的網頁訪問路徑。其中定義用戶瀏覽網頁的記錄集，屬性包括會話編號、用戶編號、用戶訪問資源、用戶引用頁面、以及其他相關信息。具體來說，集合中就是經過數據預處理中的會話識別后得到的結果記錄，其他信息則是根據需要添加的不同信息，比如頁面大小，訪問時間等等。此外，還需定義樹的節點，內容包括用戶編號、用戶訪問資源、孩子集合等。

在對Web日志數據進行去除冗余信息，用戶識別、會話識別的預處理后，算法將自上而下地搜索用戶會話記錄，重點關注了記錄中的用戶訪問資源、引用頁面和用戶信息等屬性。該主題算法的基本思想為：首先從單個會話記錄的頂部發起搜索，通常第一條記錄為用戶訪問的初始頁面或者是從其他網站跳轉過來的頁面，此頁面就會作為新建用戶瀏覽樹的根節點。繼續向下展開記錄搜索過程，對記錄進行分析，考察記錄的引用頁面，是否為先前已建立的樹的節點。如果是，則加入樹模型中；如果不是，即以此記錄的訪問頁面為根節點，再建一棵用戶瀏覽路徑樹。直到將此會話記錄全部搜索完畢，算法執行結束。

以圖1所示的用戶瀏覽情況為例算法的識別過程如下。

如圖1所示，首先搜索第一條記錄，把A節點作為用戶瀏覽樹的根節點。繼續向下搜索記錄，搜索到B頁面所對應的記錄。考察此記錄的引用頁面，引用頁面為A頁面，將B頁面作為A頁面的子節點，繼續向下搜索。此后將C頁面和D頁面也加入到A頁面所對應的節點下。

在子節點搜索父節點的過程中，此算法遵從就近搜索原則。具體過程如圖2所示。

由圖2可知在搜索到訪問E頁面的記錄時，E記錄是從最后添加的D節點開始搜索的，然后搜索C節點，在搜索B節點時發現與記錄的引用頁面相符合，所以將E頁面添加到B的孩子節點中去。在用戶有多棵用戶瀏覽樹的情況下，搜索情況也與上面相似，先搜索最近生成的用戶瀏覽樹。在搜索會話記錄的過程中可能會出現重復數據，即在不同的時間訪問了相同的資源并且引用頁面也相同，可能是用戶使用同一種方式即點擊了同一超鏈接反復訪問了同一資源，遇到這樣的情況需要合并記錄。這一做法的處理實現過程如圖3所示。

解析圖3可知，如果在搜索會話記錄過程中，搜索到了第2個關于D頁面的記錄，向上搜索父節點的過程中遇到了一個與自己相同的頁面，需考察此頁面的父節點，如果與自身的引用頁面相同則合并記錄。

綜上可得，整個算法實現流程如圖4所示。

實驗數據是某商業網站日志中分離出來的711個用戶，使用一般用戶訪問路徑識別算法，最終獲得了1 352個路徑，其中的1 076個路徑均屬長度為2的短路徑。而使用本文算法則總共得出839棵用戶訪問路徑樹，但可標識為2個節點的樹卻僅有517棵。這一結果說明本算法在收集用戶訪問路徑上，把現有算法中并未收集到的大量短的訪問路徑均已成功合并到了用戶訪問路徑樹上，從而減少了短路徑的生成數目。

2基于用戶多頁面瀏覽模式的網絡結構推薦系統的實現

2.1 推薦算法實現

基于網絡結構的推薦算法并不考慮用戶和對象的內容特征，而只是將其視作圖結構中的一個個單元節點，算法所利用的信息是用戶和對象之間的選擇關系。在基于網絡結構的推薦系統中通常會構建一個二部分網絡，其中用戶和對象分別構成2個節點集。定義用戶集合U，表示為： 。定義對象集合C，表示為： 。通過用戶選擇對象構成一個 的鄰接矩陣。在該矩陣中如果用戶j選擇了對象i，則元素 的值為1，否則該元素的值為0。算法的目的就是對于任意的用戶k，對其還未經歷選擇的所有對象可依照k的瀏覽行為、興趣愛好等方面的因素進行打分，預測k關于這些對象的喜愛程度，并將其提供有效排序，最后再將排名前若干位的對象推薦給用戶k。

研究假設用戶i選擇了若干對象，這里可以看成用戶將可調度精力或者金錢平均施付于這若干個對象上。在此，給出演示實例如圖5所示。

由圖5可見， X、Y、Z分別代表3個用戶， 則為可供其選擇的對象。諸如，用戶X選擇了對象a、b。在沒有預設加權的情況下，說明用戶X將自己的資源平均分配到了所選擇的2個對象上。綜合其他2位用戶，最終分配結果可如圖6所示。

綜上結果可知，此次分配之后每個對象都得到了用戶一定量的資源，這取決于資源選擇的用戶個數以及用戶選擇的對象個數。研究過程推理得到對象所產生的資源量可以表述為：

（1）

式中， 表示用戶i所選擇的對象C。并且：

3結束語

針對用戶普遍使用的多頁面瀏覽器產生樹型結構的瀏覽路徑，本文提出了一種新的自上而下的用戶訪問路徑收集算法。此算法能夠收集到的用戶訪問路徑樹，合并短路徑到用戶瀏覽樹上，減少了短路徑的綜合實際生成。由此得出全局用戶瀏覽目的頁面訪問頻度矩陣，此矩陣的內容作為實現基于網絡結構的推薦系統的核心數據，實驗表明建立交叉頁面訪問頻度矩陣在實現基于網絡結構的推薦上具有可行性。

參考文獻

[1] BüCHNER A G， ANAND S S， MULVENNA M D， et al. Discovering Internet marketing intelligence through Web Log Mining[J]. Sigmod Record，1999，27：54-61.

[2]

Cooley R ，Mobasher B， Srivastava J. Grouping Web Page References into Transactions for MiningWorld Wide Web Browsing Patterns[R]. Minneapolis： University of Minnesota，1997.

[3] CHEN M S， PARK J S， YU P S. Data mining for path traversal patterns in a web enviroment[C]//16th International Conference on Distributed Computing Systems. Hongkong： IEEE Computer Society， 1996： 385-392.

[4] 夏明波，王曉川，孫永強，等. 序列模式挖掘算法研究[J]. 計算機技術與發展， 2006， 16（4）： 4-6，10.

[5] 韓家煒，孟小峰，王靜，等.Web挖掘研究[J].計算機研究與發展，2001，38（4）：405-414.

[6] 張建喜.面向Web日志數據挖掘的研究與應用[D].濟南：山東師范大學，2006：12-14.

[7] 喬良.基于馬爾科夫模型的用戶瀏覽路徑預測研究[D].秦皇島：燕山大學，2007.

[8] 李靜，宋翰濤.創建企業級數據倉庫的關鍵技術[J].計算機應用研究，2001，22（5）：90-93.

[9] 紀良浩，王國胤，楊勇.基于協作過濾的Web日志數據預處理研究[J].重慶郵電學院學報（自然科學版），2006，18（5）：646-649.

[10] 鄧英，李明.用戶訪問模式挖掘中數據預處理問題的研究[J]. 計算機工程與應用，2002，38（1）：188-190.

[11] 劉維娜.Web 日志挖掘相關技術[碩士學位論文].哈爾濱：哈爾濱工程大學，2006.

[12] 劉培剛.Web 挖掘技術在電子商務中的應用研究[J].情報學報，2002，21（6）：680-685

[13] YAN T W， JACOBSEN M， GARCIA-MOLINA H， et al. From user access patterns to dynamic hypertext linking [J]. Computer Networks & Isdn Systems， 1996， 28（7-11）：1007-1014.

[14] SHAHABI C， ZARKESH A， ADIBI J ， et al. Knowledge discovery from users web-page navigation[C]//Proceedings of the 7th International Workshop on Research Issues in Data Engineering （RIDE '97） High Performance Database Management for Large-Scale Applications. Washington，DC，USA，IEEE Computer Society，1997：20-31.

[15] FU Y， SANDHU K， SHIH M Y. Clustering of Web users based on access patterns[C]//Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Workshop on Web Mining. SanDiego，CA：ACM， 1999：560-567

朱立夫（出生年1987），男，碩士研究生，高級工程師，主研領域：數據挖掘、支持決策，身份證號：430102198708034033，手機：13974864354，單位：湖南省長沙市芙蓉區人民檢察院，郵編：410016；E-mail：378546859@qq.com

劉向東（出生年1986），碩士研究生，高級工程師，主研領域：數據挖掘、數據庫，身份證號：43122419860119543x，手機：13755050784，單位：湖南省長沙市芙蓉區人民檢察院，郵編：410016；E-mail：lxd-nan@163.com

通訊地址：湖南省長沙市芙蓉區恒達路87號，郵編：410016