基于Web日志挖掘用戶偏愛(ài)瀏覽路徑算法

蘇蘭　陸濟(jì)湘

摘要：該文提出一種改進(jìn)的基于Web日志挖掘用戶偏愛(ài)瀏覽路徑算法。通過(guò)引入站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖來(lái)建立用戶的訪問(wèn)矩陣，使用夾角余弦公式求出訪問(wèn)矩陣的相似度矩陣，將相似度高的頁(yè)面歸為一類，稱為基于相似度矩陣的用戶偏愛(ài)瀏覽路徑候選集，引入訪問(wèn)矩陣的權(quán)重矩陣來(lái)降低由于主干路徑訪問(wèn)頻度高而對(duì)挖掘結(jié)果造成的影響，結(jié)合訪問(wèn)權(quán)重利用有效偏愛(ài)度過(guò)濾上述的候選項(xiàng)集，得出基于權(quán)重的用戶偏愛(ài)瀏覽路徑項(xiàng)集，最后通過(guò)合并這些項(xiàng)集得到符合用戶瀏覽習(xí)慣的偏愛(ài)路徑。實(shí)驗(yàn)表明該算法更能反映用戶真實(shí)的瀏覽興趣與意圖。

關(guān)鍵詞： 偏愛(ài)瀏覽路徑；相似度矩陣；權(quán)重矩陣；有效偏愛(ài)度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）05-0221-03

1 引言

隨著互聯(lián)網(wǎng)技術(shù)、儲(chǔ)存技術(shù)和計(jì)算能力的發(fā)展，越來(lái)越多的商業(yè)活動(dòng)通過(guò)網(wǎng)絡(luò)平臺(tái)進(jìn)行，在日常運(yùn)營(yíng)中產(chǎn)生了大量的用戶點(diǎn)擊數(shù)據(jù)流，為我們提供了很好的機(jī)會(huì)去分析和挖掘有價(jià)值的信息。本文通過(guò)分析數(shù)據(jù)并建立模型找出用戶偏愛(ài)的瀏覽路徑，能夠幫助網(wǎng)站設(shè)計(jì)者重構(gòu)站點(diǎn)頁(yè)面間的鏈接關(guān)系，優(yōu)化網(wǎng)站以更適應(yīng)用戶的訪問(wèn)需求，最終取得更好地市場(chǎng)競(jìng)爭(zhēng)力，具有現(xiàn)實(shí)意義。

目前，常用的Web日志挖掘用戶偏愛(ài)瀏覽路徑的算法有最大向前序列法、參考長(zhǎng)度法和樹(shù)形拓?fù)浣Y(jié)構(gòu)圖法[1，2]等。這些算法大部分使用用戶的對(duì)頁(yè)面的瀏覽頻度來(lái)度量用戶的瀏覽興趣，這是很不精確地。文獻(xiàn)[3，4]利用支持-興趣度來(lái)描述用戶瀏覽的興趣，經(jīng)過(guò)分析發(fā)現(xiàn)該方法挖掘出的用戶偏愛(ài)瀏覽路徑是一條主干路徑，并沒(méi)有反映用戶的真實(shí)瀏覽興趣，因此，本文對(duì)該算法做出改進(jìn)，提出了基于權(quán)重的用戶偏愛(ài)瀏覽路徑挖掘算法。

2 算法描述

2.1 站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖

實(shí)際收集到的Web日志中通常會(huì)包含很多與挖掘無(wú)關(guān)的、不一致的甚至錯(cuò)誤的數(shù)據(jù)，需要預(yù)處理[5]這些數(shù)據(jù)使其可用于Web挖掘。目前Web日志預(yù)處理過(guò)程比較成熟，通常包括數(shù)據(jù)清洗，用戶識(shí)別，會(huì)話識(shí)別和路徑補(bǔ)充等過(guò)程，本文只需要對(duì)數(shù)據(jù)進(jìn)行清洗和會(huì)話處理即可。

預(yù)處理完的日志可以表示為[L=]的集合，其中URL代表請(qǐng)求頁(yè)，URL_R代表引用頁(yè)，根據(jù)引用頁(yè)URL_R與訪問(wèn)頁(yè)URL的結(jié)構(gòu)特性可以建立站點(diǎn)的拓?fù)浣Y(jié)構(gòu)圖。

2.2 用戶訪問(wèn)矩陣

將站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖轉(zhuǎn)換為用戶訪問(wèn)矩陣便于對(duì)數(shù)據(jù)進(jìn)行分析挖掘出用戶的偏愛(ài)瀏覽路徑，用戶訪問(wèn)矩陣表示為[M=（Aij）（n+1）（n+1）]。

該矩陣的列為URL，行為URL_R，元素值[Aij]是訪問(wèn)頁(yè)面的頻度。另外，矩陣的行和列都增加一個(gè)NULL值。如果NULL出現(xiàn)在列中，表示用戶鏈接到其他網(wǎng)站或者在此頁(yè)結(jié)束瀏覽，反之，如果NULL值出現(xiàn)在行中，表示用戶從其他網(wǎng)站鏈接進(jìn)入訪問(wèn)頁(yè)。

2.3建立相似度矩陣

通過(guò)對(duì)國(guó)內(nèi)外相關(guān)文獻(xiàn)的研究可知相似度高的頁(yè)面被用戶同時(shí)訪問(wèn)的概率較高，但使用訪問(wèn)矩陣不能直接用于求頁(yè)面間的相似度。因此，我們將用戶的訪問(wèn)矩陣進(jìn)行轉(zhuǎn)換得到轉(zhuǎn)換矩陣來(lái)求得頁(yè)面間的相似度。遍歷訪問(wèn)矩陣M，如果[?Aij>0]，則[Aij=1]，得到轉(zhuǎn)換矩陣[M']。

設(shè)[?]為相似度矩陣的閾值，遍歷相似度矩陣[Mr]，對(duì)任意的[?dij≥?]，則[URLi]和[URLj]列為一類，[]將作為基于相似度矩陣的用戶偏愛(ài)瀏覽路徑候選集。接下來(lái)可以對(duì)于相似度矩陣的偏愛(ài)瀏覽路徑候選集使用有效偏愛(ài)度進(jìn)行過(guò)濾，獲得基于權(quán)重的用戶偏愛(ài)瀏覽路徑項(xiàng)集。

2.5建立權(quán)重矩陣

因?yàn)橥ㄟ^(guò)相似度矩陣與相似度閾值得出的偏愛(ài)路徑集沒(méi)有考慮頁(yè)面間的瀏覽頻度，所以需要再次過(guò)濾上述的偏愛(ài)路徑集。由于用戶訪問(wèn)網(wǎng)站習(xí)慣性的沿著頁(yè)面間的鏈接來(lái)尋找目的頁(yè)面，這就導(dǎo)致了某些頁(yè)面不是用戶喜愛(ài)的頁(yè)面，但是瀏覽頻度有很高，同時(shí)也是站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖中的主干路徑。因而，本文考慮對(duì)站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖進(jìn)行加權(quán)，使得遠(yuǎn)離主干路徑卻被用戶經(jīng)常訪問(wèn)的路徑權(quán)值高，屬于主干路徑的權(quán)值低。

由2.4節(jié)獲取的基于相似度矩陣的偏愛(ài)路徑集，我們可以將這些偏愛(ài)路徑集重構(gòu)為新的站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖，此時(shí)的站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖稱為高相似度站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖。

定義3 頁(yè)面間的最短訪問(wèn)路徑

高相似度站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖中節(jié)點(diǎn)A到節(jié)點(diǎn)B中長(zhǎng)度最短的路徑，稱作從頁(yè)面A訪問(wèn)頁(yè)面B之間的最短訪問(wèn)路徑。即找出節(jié)點(diǎn)A與節(jié)點(diǎn)B之間的所有可能路徑，并計(jì)算出每條路徑的長(zhǎng)度，其中長(zhǎng)度最短的路徑就是需要的路徑。

定義4 頁(yè)面間的訪問(wèn)權(quán)重

4 結(jié)論

將上述訪問(wèn)矩陣使用文獻(xiàn)[3]的方法得到用戶偏愛(ài)瀏覽路徑集為{[]，[]}，對(duì)比可知改進(jìn)后比改進(jìn)前多了[]這條路徑，分析發(fā)現(xiàn)[]訪問(wèn)頻度為1，也是站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖的主干路徑，不屬于用戶偏愛(ài)的瀏覽路徑。通過(guò)該實(shí)例說(shuō)明，改進(jìn)后的算法是有效的，并且得出的用戶偏愛(ài)瀏覽路徑更能反映用戶的真實(shí)興趣與意圖。

5 結(jié)束語(yǔ)

目前，網(wǎng)站的競(jìng)爭(zhēng)日益強(qiáng)烈，越來(lái)越多的網(wǎng)站設(shè)計(jì)者們把重點(diǎn)投入到用戶的感受上，不斷改善網(wǎng)站的結(jié)構(gòu)，使得網(wǎng)站盡力適應(yīng)每個(gè)用戶的瀏覽習(xí)慣。本文引入站點(diǎn)拓?fù)浣Y(jié)構(gòu)圖來(lái)建立用戶的訪問(wèn)矩陣，使用夾角余弦公式求出訪問(wèn)矩陣的相似度矩陣，將相似度高的頁(yè)面歸為一類，稱為基于相似度矩陣的用戶偏愛(ài)瀏覽路徑候選集，引入訪問(wèn)矩陣的權(quán)重矩陣來(lái)降低由于主干路徑訪問(wèn)頻度高而對(duì)挖掘結(jié)果造成的影響，結(jié)合訪問(wèn)權(quán)重利用有效偏愛(ài)度過(guò)濾上述的候選項(xiàng)集，得出基于權(quán)重的用戶偏愛(ài)瀏覽路徑項(xiàng)集，最后通過(guò)合并這些項(xiàng)集得到最符合用戶瀏覽習(xí)慣的偏愛(ài)路徑。

參考文獻(xiàn)：

[1] 施建生，伍衛(wèi)國(guó)，陸麗娜等.Web 日志中挖掘用戶瀏覽模式的研究[J].西安交通大學(xué)學(xué)報(bào)， 2001， 35（6）： 621-624.

[2] 何麗，韓文秀.一種基于后綴樹(shù)的Web訪問(wèn)模式挖掘算法[J].計(jì)算機(jī)應(yīng)用，2004， 24（11）： 68-70.

[3] 王思寶，李銀勝.基于 Web 日志挖掘用戶的瀏覽興趣路徑[J].計(jì)算機(jī)應(yīng)用與軟件，2012， 29（1）： 164.

[4] 邢東山，沈鈞毅，宋擒豹.從 Web 日志中挖掘用戶瀏覽偏愛(ài)路徑[J].計(jì)算機(jī)學(xué)報(bào)，2003，26（11）： 1518-1523.

[5] 張璽，張學(xué)玲，張洪欣.基于 Web 日志的數(shù)據(jù)預(yù)處理方法研究[J].濱州學(xué)院學(xué)報(bào)，2014，30（6）： 98-104.