摘 ?要： 通過(guò)給出頁(yè)面層次的概念，充分考慮用戶(hù)在頁(yè)面上的瀏覽時(shí)間以及在路徑選擇上表現(xiàn)出來(lái)的瀏覽偏愛(ài)，結(jié)合Web站點(diǎn)的結(jié)構(gòu)層次特征，提出了一種改進(jìn)的Web用戶(hù)瀏覽偏愛(ài)模式挖掘算法。通過(guò)具體的事例和試驗(yàn)數(shù)據(jù)證明，新的模型能夠更準(zhǔn)確地尋找用戶(hù)瀏覽偏愛(ài)模式，從而發(fā)現(xiàn)用戶(hù)的興趣和愛(ài)好。

關(guān)鍵詞： Web用戶(hù); 瀏覽偏愛(ài); 訪問(wèn)事務(wù)集; 模式挖掘

中圖分類(lèi)號(hào)：TP391 ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? 文章編號(hào)：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 引言

在用戶(hù)的訪問(wèn)過(guò)程中，我們要考察用戶(hù)對(duì)某個(gè)頁(yè)面是否感興趣，感興趣的程度如何，主要是從用戶(hù)對(duì)該頁(yè)面的訪問(wèn)次數(shù)和瀏覽時(shí)間這兩個(gè)方面來(lái)評(píng)價(jià)。在文獻(xiàn)[3]提出的偏愛(ài)模式挖掘算法中，認(rèn)為用戶(hù)對(duì)頁(yè)面的訪問(wèn)次數(shù)和瀏覽時(shí)間同等重要，所以直接相乘，但實(shí)際情況是用戶(hù)訪問(wèn)次數(shù)對(duì)導(dǎo)航頁(yè)面相對(duì)重要，而瀏覽時(shí)間對(duì)內(nèi)容頁(yè)面相對(duì)重要。

1 基于頁(yè)面瀏覽時(shí)間和網(wǎng)站結(jié)構(gòu)的瀏覽偏愛(ài)度量

一般情況下，用戶(hù)對(duì)頁(yè)面越感興趣，瀏覽的時(shí)間就會(huì)越長(zhǎng)，反之，瀏覽的時(shí)間就會(huì)越短，從而可以根據(jù)用戶(hù)的瀏覽時(shí)間進(jìn)行瀏覽興趣度量。

1.1 相關(guān)概念和定義

定義1 時(shí)間離散化技術(shù)[3]

按照用戶(hù)在一個(gè)頁(yè)面上的瀏覽時(shí)間，將用戶(hù)的瀏覽興趣定義為：

定義2 引用

一個(gè)頁(yè)面的引用是指發(fā)出超級(jí)鏈接到該頁(yè)面的頁(yè)面，例如：頁(yè)面A和頁(yè)面B之間存在著超級(jí)鏈接A→B，那么頁(yè)面A就是頁(yè)面B的引用頁(yè)面。

定義3 頁(yè)面層次

頁(yè)面層次指的是網(wǎng)站結(jié)構(gòu)中某網(wǎng)頁(yè)離主頁(yè)所在層次的層次差。首先根據(jù)Web頁(yè)面鏈接的順序?qū)⑺械腤eb頁(yè)面構(gòu)造成一個(gè)樹(shù)狀結(jié)構(gòu)，主頁(yè)的頁(yè)面層次為1;然后遞歸定義所有結(jié)點(diǎn)的頁(yè)面層次，具體算法如下：

Int HightOfTree（page）

{ ?If page是主頁(yè) then Return 1;

Else

Return（min（HightOfTree（page的引用頁(yè)1），

HightOfTree（page的引用頁(yè)2），…，

HightOfTree（page的引用頁(yè)n））+1）;

}

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

定義4 選擇偏愛(ài)度和停留偏愛(ài)度[3]

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

其中Ci表示第i種選擇的支持?jǐn)?shù)，即用戶(hù)通過(guò)第i種選擇進(jìn)入下一頁(yè)面的次數(shù);Ti表示用戶(hù)在第i種選擇所進(jìn)入頁(yè)面的瀏覽時(shí)間。

定義5 綜合偏愛(ài)度[4]

若用戶(hù)瀏覽當(dāng)前頁(yè)面的序列號(hào)為m，由此進(jìn)入下一個(gè)頁(yè)面m+1共有n種不同的選擇，則其中第k（k=1，2，…，n）種選擇的綜合偏愛(ài)度Lk定義為如公式⑶：

Lk=α×Sk+β×Pk ⑶

其中α+β=網(wǎng)站的最大層次+1（α，β>0），α=網(wǎng)站的最大層次-頁(yè)面k所在的層次+1，β=頁(yè)面k所在的層次。

1.2 用戶(hù)瀏覽偏愛(ài)模式挖掘算法

綜合偏愛(ài)度是指用戶(hù)對(duì)某一網(wǎng)頁(yè)的相對(duì)偏愛(ài)程度。文獻(xiàn)[3]在衡量用戶(hù)對(duì)頁(yè)面的偏愛(ài)程度時(shí)，根據(jù)瀏覽時(shí)間和選擇次數(shù)來(lái)定義綜合偏愛(ài)度度量，并且認(rèn)為對(duì)于任何頁(yè)面用戶(hù)訪問(wèn)次數(shù)和訪問(wèn)時(shí)間同等重要。給出的公式為如公式⑷：

該算法在遞歸挖掘用戶(hù)瀏覽偏愛(ài)模式過(guò)程中，對(duì)于每個(gè)瀏覽序列，先計(jì)算其最后一個(gè)頁(yè)面的綜合偏愛(ài)度的值，然后結(jié)合支持度來(lái)進(jìn)行判斷，是否要將當(dāng)前的序列輸出到候選瀏覽偏愛(ài)模式集合中。即為：if（（Sub_Num*Sub_Time）/（（Num*Time）/（NumberOfCandidate）2））>=綜合偏愛(ài)度閾值and Sub_Num>=支持度閾值 then 將Sub_Path輸出到候選瀏覽偏愛(ài)路徑集合中。

1.3 改進(jìn)的用戶(hù)瀏覽偏愛(ài)模式挖掘算法

根據(jù)前面的分析，用戶(hù)訪問(wèn)次數(shù)對(duì)于離主頁(yè)較近的導(dǎo)航頁(yè)面相對(duì)重要，而訪問(wèn)時(shí)間對(duì)于離主頁(yè)較遠(yuǎn)的內(nèi)容頁(yè)面相對(duì)重要[5]，所以我們結(jié)合網(wǎng)站的結(jié)構(gòu)來(lái)度量用戶(hù)對(duì)頁(yè)面的偏愛(ài)程度，提出了改進(jìn)的用戶(hù)瀏覽偏愛(ài)模式挖掘算法。

⑴ 算法1：改進(jìn)的用戶(hù)瀏覽偏愛(ài)模式挖掘算法

輸入：某個(gè)用戶(hù)的事務(wù)集S，前綴Pre;

輸出：該用戶(hù)的瀏覽偏愛(ài)模式。

方法：

Prefered_Navigation_Patterns（S，Pre）

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

將S中前綴為Pre，長(zhǎng)度為|Pre|+1的不同的瀏覽序列寫(xiě)入Candidate;Number_Of_Candidate=Candidate中瀏覽序列的個(gè)數(shù);

For i=1 to Number_Of_Candidate

Sub_Path=Candidate中第i個(gè)瀏覽序列;

Sub_Num=S中前綴為Sub_Path的個(gè)數(shù);

Sub_Time=S中前綴為Sub_Path的第|Sub_Path|個(gè)頁(yè)面

的瀏覽興趣時(shí)間的總和;

If ?Sub_Num<支持度閾值 then

Prefered_Navigation_Patterns（S，Sub_Path）;

Else

根據(jù)站點(diǎn)結(jié)構(gòu)得到第|Sub_Path|位頁(yè)面所在的層次;

根據(jù)定義5計(jì)算得到第|Sub_Path|個(gè)頁(yè)面的綜合偏愛(ài)度;

If ?得到的綜合偏愛(ài)度>=綜合偏愛(ài)度閾值 then

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

Prefered_Navigation_Patterns（S，Sub_Path）

End If

End If

End For

⑵ 本算法的三點(diǎn)改進(jìn)

① 結(jié)合站點(diǎn)結(jié)構(gòu)來(lái)定義用戶(hù)對(duì)頁(yè)面的綜合偏愛(ài)度。因?yàn)橛脩?hù)的訪問(wèn)行為受站點(diǎn)拓?fù)浣Y(jié)構(gòu)的影響，因此我們?cè)诤饬坑脩?hù)對(duì)某個(gè)頁(yè)面是否感興趣時(shí)，必須結(jié)合頁(yè)面的層次結(jié)構(gòu)來(lái)考慮即：如果該頁(yè)面是離主頁(yè)較近的導(dǎo)航頁(yè)面，則要重點(diǎn)考察用戶(hù)對(duì)該頁(yè)面的訪問(wèn)次數(shù);如果該頁(yè)面是離主頁(yè)較遠(yuǎn)的內(nèi)容頁(yè)面，則要重點(diǎn)考察用戶(hù)在該頁(yè)面上的瀏覽時(shí)間。

這樣區(qū)別對(duì)待導(dǎo)航頁(yè)面和內(nèi)容頁(yè)面，能夠更準(zhǔn)確地體現(xiàn)出用戶(hù)的訪問(wèn)興趣和瀏覽偏愛(ài)，可以更好地為用戶(hù)提供個(gè)性化服務(wù)。

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

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

2 具體實(shí)例及分析

以圖1的網(wǎng)站的拓?fù)浣Y(jié)構(gòu)為例描述算法過(guò)程，經(jīng)過(guò)處理Web日志得到的用戶(hù)事務(wù)集合如表1所示。算法中把綜合偏愛(ài)度閾值設(shè)為5，支持度閾值設(shè)為2。

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

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

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

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

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

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

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

Sub_path=ABDE，Sub_Num=1<2，Sub_Time=3，不用計(jì)算E的綜合偏愛(ài)度，取下一個(gè)子串ABDG。Sub_path=ABDG，Sub_Num=1<2，Sub_Time=4，不用計(jì)算G的綜合偏愛(ài)度。

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

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

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

Sub_path=AC，Sub_Num=2，Sub_Time=7，C的層次是2，根據(jù)綜合偏愛(ài)度公式計(jì)算得到的綜合偏愛(ài)度為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，運(yùn)行結(jié)束。

結(jié)合該站點(diǎn)的拓?fù)浣Y(jié)構(gòu)，我們可以發(fā)現(xiàn)：頁(yè)面D所包含的超級(jí)鏈接比較多信息量比較少，頁(yè)面G所包含的超級(jí)鏈接比較少信息量比較多，用戶(hù)訪問(wèn)頁(yè)面D的目的更可能是為了訪問(wèn)頁(yè)面E、F、G;而用戶(hù)訪問(wèn)頁(yè)面G，是因?yàn)橛脩?hù)對(duì)頁(yè)面G的信息更感興趣。所以，改進(jìn)后的算法得到的結(jié)果更為準(zhǔn)確，更能體現(xiàn)出用戶(hù)真正的訪問(wèn)興趣和愛(ài)好，我們可以更好地用戶(hù)提供個(gè)性化服務(wù)。

3 實(shí)驗(yàn)和性能分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集特征

從網(wǎng)上下載了某校園網(wǎng)從2020年5月13至6月13日一個(gè)月的日志，從5月13日的日志中隨機(jī)抽取10個(gè)用戶(hù)，然后將這10個(gè)用戶(hù)在這一個(gè)月里的訪問(wèn)記錄提取出來(lái)，對(duì)這些用戶(hù)的瀏覽日志進(jìn)行預(yù)處理，得到每個(gè)用戶(hù)的訪問(wèn)事務(wù)集合。

3.2 實(shí)驗(yàn)結(jié)果分析

利用改進(jìn)的基于站點(diǎn)結(jié)構(gòu)的用戶(hù)瀏覽偏愛(ài)模式挖掘算法，得到這10個(gè)用戶(hù)的瀏覽偏愛(ài)模式如表2所示。

從表2中，我們可以得到任意一個(gè)用戶(hù)的瀏覽偏愛(ài)模式，從而發(fā)現(xiàn)他的興趣和愛(ài)好。我們也可以得到其他用戶(hù)的興趣和愛(ài)好，并據(jù)此為用戶(hù)提供個(gè)性化的定制服務(wù)，改善服務(wù)質(zhì)量。

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

針對(duì)當(dāng)前的挖掘算法只是簡(jiǎn)單地把頻繁訪問(wèn)路徑作為用戶(hù)瀏覽的興趣路徑的問(wèn)題，本文結(jié)合站點(diǎn)的結(jié)構(gòu)，充分考慮了用戶(hù)在頁(yè)面上的瀏覽時(shí)間和在路徑選擇上表現(xiàn)出來(lái)的瀏覽偏愛(ài)，提出了一種改進(jìn)的瀏覽偏愛(ài)模式挖掘算法。從用戶(hù)對(duì)頁(yè)面的訪問(wèn)次數(shù)及瀏覽時(shí)間定義了選擇偏愛(ài)度和停留偏愛(ài)度，在選擇偏愛(ài)度和停留偏愛(ài)度的基礎(chǔ)上結(jié)合站點(diǎn)結(jié)構(gòu)定義了綜合偏愛(ài)度，能更好地來(lái)理解用戶(hù)的訪問(wèn)行為，更能準(zhǔn)確地體現(xiàn)用戶(hù)的瀏覽興趣和愛(ài)好所在，從而提供更優(yōu)質(zhì)的個(gè)性化服務(wù)。

參考文獻(xiàn)（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] 刑?hào)|山，沈鈞毅，宋擒豹.用戶(hù)瀏覽偏愛(ài)模式挖掘算法的研究[J].西安交通大學(xué)學(xué)報(bào)，2002.4：369-372

[4] 蘇云揮，張瑩，白清源，謝麗聰，謝伙生 基于訪問(wèn)興趣度的用戶(hù)事務(wù)聚類(lèi)方法[J].廣西師范大學(xué)學(xué)報(bào)，2007.25（4）：248-251

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

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

收稿日期：2021-03-26

基金項(xiàng)目：廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金項(xiàng)目（MIMS20-05）

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