基于用戶多頁面瀏覽模式下的網(wǎng)絡(luò)結(jié)構(gòu)推薦系統(tǒng)的研究

朱立夫 劉向東

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

關(guān)鍵字：訪問路徑樹形；推薦系統(tǒng)；網(wǎng)絡(luò)結(jié)構(gòu)

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

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

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

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

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

如圖1所示，首先搜索第一條記錄，把A節(jié)點作為用戶瀏覽樹的根節(jié)點。繼續(xù)向下搜索記錄，搜索到B頁面所對應(yīng)的記錄?？疾齑擞涗浀囊庙撁?，引用頁面為A頁面，將B頁面作為A頁面的子節(jié)點，繼續(xù)向下搜索。此后將C頁面和D頁面也加入到A頁面所對應(yīng)的節(jié)點下。

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

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

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

綜上可得，整個算法實現(xiàn)流程如圖4所示。

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

2基于用戶多頁面瀏覽模式的網(wǎng)絡(luò)結(jié)構(gòu)推薦系統(tǒng)的實現(xiàn)

2.1 推薦算法實現(xiàn)

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

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

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

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

（1）

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

3結(jié)束語

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

參考文獻

[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]. 計算機技術(shù)與發(fā)展， 2006， 16（4）： 4-6，10.

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

[6] 張建喜.面向Web日志數(shù)據(jù)挖掘的研究與應(yīng)用[D].濟南：山東師范大學(xué)，2006：12-14.

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

[8] 李靜，宋翰濤.創(chuàng)建企業(yè)級數(shù)據(jù)倉庫的關(guān)鍵技術(shù)[J].計算機應(yīng)用研究，2001，22（5）：90-93.

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

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

[11] 劉維娜.Web 日志挖掘相關(guān)技術(shù)[碩士學(xué)位論文].哈爾濱：哈爾濱工程大學(xué)，2006.

[12] 劉培剛.Web 挖掘技術(shù)在電子商務(wù)中的應(yīng)用研究[J].情報學(xué)報，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），男，碩士研究生，高級工程師，主研領(lǐng)域：數(shù)據(jù)挖掘、支持決策，身份證號：430102198708034033，手機：13974864354，單位：湖南省長沙市芙蓉區(qū)人民檢察院，郵編：410016；E-mail：378546859@qq.com

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

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