一種改進的Web用戶瀏覽偏愛模式挖掘算法

摘 ?要： 通過給出頁面層次的概念，充分考慮用戶在頁面上的瀏覽時間以及在路徑選擇上表現出來的瀏覽偏愛，結合Web站點的結構層次特征，提出了一種改進的Web用戶瀏覽偏愛模式挖掘算法。通過具體的事例和試驗數據證明，新的模型能夠更準確地尋找用戶瀏覽偏愛模式，從而發現用戶的興趣和愛好。

關鍵詞： Web用戶; 瀏覽偏愛; 訪問事務集; 模式挖掘

中圖分類號：TP391 ? ? ? ? ?文獻標識碼：A ? ? 文章編號：1006-8228（2021）08-47-04

An improved algorithm for Web users' browsing preference pattern mining

Ning Jianfei

（Department of Information Engineering， Luoding Polytechnic College， Luoding， Guangdong 527200， China）

Abstract： By giving the concept of page hierarchy， fully considering the user's browsing time on the page and the browsing preference shown in the path selection， combined with the structural hierarchy characteristics of the web site， an improved web user browsing preference pattern mining algorithm is proposed. Through specific examples and experimental data， it is proved that the new model can more accurately find users' browsing preference pattern， so as to find users' interests and hobbies.

Key words： Web user; browsing preference; access transaction set; pattern mining

0 引言

在用戶的訪問過程中，我們要考察用戶對某個頁面是否感興趣，感興趣的程度如何，主要是從用戶對該頁面的訪問次數和瀏覽時間這兩個方面來評價。在文獻[3]提出的偏愛模式挖掘算法中，認為用戶對頁面的訪問次數和瀏覽時間同等重要，所以直接相乘，但實際情況是用戶訪問次數對導航頁面相對重要，而瀏覽時間對內容頁面相對重要。

1 基于頁面瀏覽時間和網站結構的瀏覽偏愛度量

一般情況下，用戶對頁面越感興趣，瀏覽的時間就會越長，反之，瀏覽的時間就會越短，從而可以根據用戶的瀏覽時間進行瀏覽興趣度量。

1.1 相關概念和定義

定義1 時間離散化技術[3]

按照用戶在一個頁面上的瀏覽時間，將用戶的瀏覽興趣定義為：

定義2 引用

一個頁面的引用是指發出超級鏈接到該頁面的頁面，例如：頁面A和頁面B之間存在著超級鏈接A→B，那么頁面A就是頁面B的引用頁面。

定義3 頁面層次

頁面層次指的是網站結構中某網頁離主頁所在層次的層次差。首先根據Web頁面鏈接的順序將所有的Web頁面構造成一個樹狀結構，主頁的頁面層次為1;然后遞歸定義所有結點的頁面層次，具體算法如下：

Int HightOfTree（page）

{ ?If page是主頁 then Return 1;

Else

Return（min（HightOfTree（page的引用頁1），

HightOfTree（page的引用頁2），…，

HightOfTree（page的引用頁n））+1）;

}

在一個站點中，可能存在多條到達某個頁面的路徑，即該頁面有n個（n≥1）引用頁，那么該頁面的層次為所有引用頁中層次的最小值加1。

定義4 選擇偏愛度和停留偏愛度[3]

設U是網站中所有頁面URL的集合，W是所有瀏覽子路徑的集合。組成的瀏覽頁面序列，稱其中第i個瀏覽頁面為第i位），它們的前m位都相同，而m+1位有n種不同的選擇，則其中第k（k=1，2，……，n）種選擇的選擇偏愛度Sk，對第k個頁面的停留偏愛度Pk分別定義為如公式⑴和公式⑵：

其中Ci表示第i種選擇的支持數，即用戶通過第i種選擇進入下一頁面的次數;Ti表示用戶在第i種選擇所進入頁面的瀏覽時間。

定義5 綜合偏愛度[4]

若用戶瀏覽當前頁面的序列號為m，由此進入下一個頁面m+1共有n種不同的選擇，則其中第k（k=1，2，…，n）種選擇的綜合偏愛度Lk定義為如公式⑶：

Lk=α×Sk+β×Pk ⑶

其中α+β=網站的最大層次+1（α，β>0），α=網站的最大層次-頁面k所在的層次+1，β=頁面k所在的層次。

1.2 用戶瀏覽偏愛模式挖掘算法

綜合偏愛度是指用戶對某一網頁的相對偏愛程度。文獻[3]在衡量用戶對頁面的偏愛程度時，根據瀏覽時間和選擇次數來定義綜合偏愛度度量，并且認為對于任何頁面用戶訪問次數和訪問時間同等重要。給出的公式為如公式⑷：

該算法在遞歸挖掘用戶瀏覽偏愛模式過程中，對于每個瀏覽序列，先計算其最后一個頁面的綜合偏愛度的值，然后結合支持度來進行判斷，是否要將當前的序列輸出到候選瀏覽偏愛模式集合中。即為：if（（Sub_Num*Sub_Time）/（（Num*Time）/（NumberOfCandidate）2））>=綜合偏愛度閾值and Sub_Num>=支持度閾值 then 將Sub_Path輸出到候選瀏覽偏愛路徑集合中。

1.3 改進的用戶瀏覽偏愛模式挖掘算法

根據前面的分析，用戶訪問次數對于離主頁較近的導航頁面相對重要，而訪問時間對于離主頁較遠的內容頁面相對重要[5]，所以我們結合網站的結構來度量用戶對頁面的偏愛程度，提出了改進的用戶瀏覽偏愛模式挖掘算法。

⑴ 算法1：改進的用戶瀏覽偏愛模式挖掘算法

輸入：某個用戶的事務集S，前綴Pre;

輸出：該用戶的瀏覽偏愛模式。

方法：

Prefered_Navigation_Patterns（S，Pre）

初始化：Candidate={空集};Num為S中前綴為Pre且長度大于|Pre|的序列個數（|Pre|表示Pre中所包含頁面的數目）;Time為得到的Num個事務中第|Pre|+1個網頁的用戶全部瀏覽興趣時間的總和;

將S中前綴為Pre，長度為|Pre|+1的不同的瀏覽序列寫入Candidate;Number_Of_Candidate=Candidate中瀏覽序列的個數;

For i=1 to Number_Of_Candidate

Sub_Path=Candidate中第i個瀏覽序列;

Sub_Num=S中前綴為Sub_Path的個數;

Sub_Time=S中前綴為Sub_Path的第|Sub_Path|個頁面

的瀏覽興趣時間的總和;

If ?Sub_Num<支持度閾值 then

Prefered_Navigation_Patterns（S，Sub_Path）;

Else

根據站點結構得到第|Sub_Path|位頁面所在的層次;

根據定義5計算得到第|Sub_Path|個頁面的綜合偏愛度;

If ?得到的綜合偏愛度>=綜合偏愛度閾值 then

將Sub_Path輸出到候選瀏覽偏愛模式集合中;

Prefered_Navigation_Patterns（S，Sub_Path）

End If

End If

End For

⑵ 本算法的三點改進

① 結合站點結構來定義用戶對頁面的綜合偏愛度。因為用戶的訪問行為受站點拓撲結構的影響，因此我們在衡量用戶對某個頁面是否感興趣時，必須結合頁面的層次結構來考慮即：如果該頁面是離主頁較近的導航頁面，則要重點考察用戶對該頁面的訪問次數;如果該頁面是離主頁較遠的內容頁面，則要重點考察用戶在該頁面上的瀏覽時間。

這樣區別對待導航頁面和內容頁面，能夠更準確地體現出用戶的訪問興趣和瀏覽偏愛，可以更好地為用戶提供個性化服務。

② 在算法過程中，某一個瀏覽序列能否輸出到候選瀏覽偏愛模式集合中，主要取決于兩個條件：綜合偏愛度的值是否大于所設定的閾值與瀏覽序列中最后一個頁面出現的次數是否大于支持度閾值。只有這兩個條件同時滿足，該瀏覽序列才能夠輸出到候選瀏覽偏愛模式中，否則就能判定該序列肯定不會成為用戶瀏覽偏愛模式[6]。因此，改進的算法中在第三步得到Sub_Num的值后，就判定是否大于等于所設定的支持度閾值，如果小于的話，就可以得出結論：該瀏覽序列不是用戶瀏覽偏愛序列。這樣做的話，就不用再去計算頁面層次和綜合偏愛度的值，可以節省時間，提高算法的效率。

③ 對于存在多個序列長度相等且都不包含在任何其他序列中的情況，我們的處理方法是選擇第一個不相同頁面中綜合偏愛度值最大的那個序列作為用戶瀏覽偏愛模式。這樣能夠更準確地描述和體現用戶真正的瀏覽愛好。

2 具體實例及分析

以圖1的網站的拓撲結構為例描述算法過程，經過處理Web日志得到的用戶事務集合如表1所示。算法中把綜合偏愛度閾值設為5，支持度閾值設為2。

⑴ 開始：Pre={空集}，Num=10，Time=13，Candidate={A，B，C，D}。

Sub_path=A，Sub_Num=7>2，Sub_Time=8，A的層次是1，根據綜合偏愛度公式計算得到綜合偏愛度為13.66>5，將A輸出到候選瀏覽偏愛模式集合中。

⑵ 遞歸調用到下一層，Pre=A，Num=7，Time=16，Candidate={AB，AC}。

Sub_path=AB，Sub_Num=5>2，Sub_Time=9，B的層次是2，根據綜合偏愛度計算公式得到綜合偏愛度為6.54>5，將AB輸出到候選瀏覽偏愛模式集合中。

⑶ 遞歸調用到下一層，Pre=AB，Num=5，Time=9，Candidate={ABD，ABG}。

Sub_path=ABD，Sub_Num=3>2，Sub_Time=4，D的層次是3，根據綜合偏愛度公式計算得到的綜合偏愛度為5.07>5，將ABD輸出到候選瀏覽偏愛模式集合中。

⑷ 遞歸調用到下一層，Pre=ABD，Num=3， Time=4，Candidate={ABDE，ABDG}。

Sub_path=ABDE，Sub_Num=1<2，Sub_Time=3，不用計算E的綜合偏愛度，取下一個子串ABDG。Sub_path=ABDG，Sub_Num=1<2，Sub_Time=4，不用計算G的綜合偏愛度。

⑸ 退回到上一層，取字串ABG。

Sub_path=ABG，Sub_Num=2，Sub_Time=6，G的層次是3，根據綜合偏愛度公式計算得到的綜合偏愛度為5.6<5，將ABG輸出到候選瀏覽偏愛模式集合中。

⑹ 退回到上一層，取字串AC。

Sub_path=AC，Sub_Num=2，Sub_Time=7，C的層次是2，根據綜合偏愛度公式計算得到的綜合偏愛度為3.46<5。

⑺ 退回到上一層，取字串B。Sub_path=B，Sub_Num=1<2，Sub_Time=1，取下一子串C。Sub_path=C，Sub_Num=1<2，Sub_Time=2，取下一子串D。Sub_path=D，Sub_Num=1<2，Sub_Time=2，運行結束。

結合該站點的拓撲結構，我們可以發現：頁面D所包含的超級鏈接比較多信息量比較少，頁面G所包含的超級鏈接比較少信息量比較多，用戶訪問頁面D的目的更可能是為了訪問頁面E、F、G;而用戶訪問頁面G，是因為用戶對頁面G的信息更感興趣。所以，改進后的算法得到的結果更為準確，更能體現出用戶真正的訪問興趣和愛好，我們可以更好地用戶提供個性化服務。

3 實驗和性能分析

3.1 實驗數據集特征

從網上下載了某校園網從2020年5月13至6月13日一個月的日志，從5月13日的日志中隨機抽取10個用戶，然后將這10個用戶在這一個月里的訪問記錄提取出來，對這些用戶的瀏覽日志進行預處理，得到每個用戶的訪問事務集合。

3.2 實驗結果分析

利用改進的基于站點結構的用戶瀏覽偏愛模式挖掘算法，得到這10個用戶的瀏覽偏愛模式如表2所示。

從表2中，我們可以得到任意一個用戶的瀏覽偏愛模式，從而發現他的興趣和愛好。我們也可以得到其他用戶的興趣和愛好，并據此為用戶提供個性化的定制服務，改善服務質量。

4 結束語

針對當前的挖掘算法只是簡單地把頻繁訪問路徑作為用戶瀏覽的興趣路徑的問題，本文結合站點的結構，充分考慮了用戶在頁面上的瀏覽時間和在路徑選擇上表現出來的瀏覽偏愛，提出了一種改進的瀏覽偏愛模式挖掘算法。從用戶對頁面的訪問次數及瀏覽時間定義了選擇偏愛度和停留偏愛度，在選擇偏愛度和停留偏愛度的基礎上結合站點結構定義了綜合偏愛度，能更好地來理解用戶的訪問行為，更能準確地體現用戶的瀏覽興趣和愛好所在，從而提供更優質的個性化服務。

參考文獻（References）：

[1] RJ Krishnapuram，ALYi.A fuzzy relative of the k-medoids

algorithm with application to web document and snippet clustering.Fuzzy Systems Conference Proceedings，1999.3：1281-1286

[2] Myra S，Lukas F.A data miner analyzing the navigational

behaviour of web users[EB/OL].http：//www.wiwi.hu-beilin.de/～myra/w_acai99.ps.gz，1999-07-26/2001-07-28.

[3] 刑東山，沈鈞毅，宋擒豹.用戶瀏覽偏愛模式挖掘算法的研究[J].西安交通大學學報，2002.4：369-372

[4] 蘇云揮，張瑩，白清源，謝麗聰，謝伙生 基于訪問興趣度的用戶事務聚類方法[J].廣西師范大學學報，2007.25（4）：248-251

[5] 邱奕飛，馬力.基于頻繁鏈表-存取樹的Web用戶瀏覽模式挖掘算法[J].電子設計工程，2014.23：24-27

[6] 王剛，郭雪梅.融合用戶行為分析和興趣序列相似性的個性化推薦方法研究[J].情報理論與實踐，2019.7：119-125

收稿日期：2021-03-26

基金項目：廣西多源信息挖掘與安全重點實驗室開放基金項目（MIMS20-05）

作者簡介：寧建飛（1978-），男，江西玉山人，碩士，講師，主要研究方向：大數據挖掘。