一种改进的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-），男，江西玉山人，硕士，讲师，主要研究方向：大数据挖掘。