蘇蘭　陸濟(jì)湘

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

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

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

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

2 算法描述

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

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

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

2.2 用戶訪問矩陣

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

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

2.3建立相似度矩陣

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

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

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

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

由2.4節(jié)獲取的基于相似度矩陣的偏愛路徑集，我們可以將這些偏愛路徑集重構(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 頁面間的最短訪問路徑

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

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

4 結(jié)論

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

5 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

[4] 邢東山，沈鈞毅，宋擒豹.從 Web 日志中挖掘用戶瀏覽偏愛路徑[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.