朱立夫 劉向東

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

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

中圖分類號(hào) TP274 文獻(xiàn)標(biāo)識(shí)碼 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)站上的每一次點(diǎn)擊，作為網(wǎng)站后臺(tái)的Web服務(wù)器都會(huì)將這個(gè)動(dòng)作如實(shí)地記錄在日志中，這為分析用戶訪問頻率、用戶訪問路徑、用戶訪問目的等信息提供了數(shù)據(jù)來源。通過分析Web瀏覽日志，發(fā)現(xiàn)用戶的訪問模式，提取用戶的訪問興趣，將得到的各種用戶信息進(jìn)行整合研究，從而生成有效的決策信息，即可為用戶提供個(gè)性化推薦，同時(shí)還能進(jìn)一步優(yōu)化網(wǎng)站的拓?fù)浣Y(jié)構(gòu)。當(dāng)前數(shù)據(jù)挖掘技術(shù)與Web日志分析已經(jīng)實(shí)現(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），然后對(duì)數(shù)據(jù)立方體進(jìn)行數(shù)據(jù)挖掘和聯(lián)機(jī)分析處理（OLAP）。而實(shí)現(xiàn)這些算法的前提是從Web日志中探究會(huì)話識(shí)別，并分離出用戶會(huì)話，進(jìn)而提煉出用戶訪問路徑。針對(duì)用戶普遍使用的多頁面瀏覽器產(chǎn)生樹型結(jié)構(gòu)的瀏覽路徑，Web日志中將會(huì)呈現(xiàn)非時(shí)序的日志記錄?；诖?，本文提出了一種新的自上而下的用戶訪問路徑收集算法，運(yùn)行得出用戶在一次會(huì)話中可能訪問的復(fù)數(shù)目的頁面，由此得出全局目的頁面訪問頻度矩陣，該矩陣的數(shù)據(jù)將可作為實(shí)現(xiàn)基于網(wǎng)絡(luò)結(jié)構(gòu)的推薦系統(tǒng)的核心數(shù)據(jù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）

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

3結(jié)束語

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

參考文獻(xiàn)

[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] 夏明波，王曉川，孫永強(qiáng)，等. 序列模式挖掘算法研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展， 2006， 16（4）： 4-6，10.

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

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

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

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

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

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

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

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

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

通訊地址：湖南省長(zhǎng)沙市芙蓉區(qū)恒達(dá)路87號(hào)，郵編：410016