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

蘇蘭　陸濟湘

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）05-0221-03

1 引言

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

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

2 算法描述

2.1 站點拓撲結(jié)構(gòu)圖

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

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

2.2 用戶訪問矩陣

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

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

2.3建立相似度矩陣

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

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

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

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

由2.4節(jié)獲取的基于相似度矩陣的偏愛路徑集，我們可以將這些偏愛路徑集重構(gòu)為新的站點拓撲結(jié)構(gòu)圖，此時的站點拓撲結(jié)構(gòu)圖稱為高相似度站點拓撲結(jié)構(gòu)圖。

定義3 頁面間的最短訪問路徑

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

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

4 結(jié)論

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

5 結(jié)束語

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

參考文獻：

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

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

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

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

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