李晓静，王树森

（济源职业技术学院，济源 459000）

0 引言

使用Web用户浏览偏爱路径挖掘算法分析Web日志记录，并发现用户访问规律，已成功应用于个性化推荐、系统改进以及商业智能等方面。目前在浏览模式的获取上常用的算法主要有最大频繁序列法、引用长度法和树型拓扑结构法等[1]，但是这些算法其实都是一种改进的关联规则算法，存在以下两方面的问题：一是简单地认为用户的浏览频度就代表了用户的访问兴趣度，这很片面；其次，随着网络的发展，Web日志数据逐渐呈现出分布性、异构性、动态性和海量性等特点[2]，传统的集中式数据挖掘算法就不能满足对拥有海量数据的Web日志进行挖掘处理的需求。

为了解决上述问题，本文将事物聚类算法和W eb用户浏览模式挖掘算法相结合，并对现有算法进行改进，提出将雅克比系数与最长公共路径系数相乘综合考虑的方法，更准确地反应用户之间的相似度，该方法采用一个三元组表示页面兴趣度，综合考虑了用户的访问时间、所访问页面的大小以及访问次数等因素，从而构造出以引用网页的URL地址为行、浏览网页的URL地址为列，以访问兴趣度为元素值的数据矩阵，在此基础上采用改进的挖掘算法对该矩阵进行偏爱度和兴趣度的计算[3]。用户通过选择进入下一个页面时，由于综合考虑了页面的访问次数、访问时间和页面大小，从而可以得到更为准确地偏爱路径。

1 改进的事物聚类算法

1.1 事物聚类算法的基本定义

设n个用户访问路径集合U={C1,C2,…,Cn}，其中一条访问路径为Ci={V1,V2,…,Vi}，其中Vi表示一个被访问过的节点。

定义1：用户访问路径中节点的个数等于路径长度C。

定义2：雅克比系数：

例如有两条W eb用户访问路径C1={V1，V2，V3}，C2={V2，V1，V3}，采用雅克比系数进行计算的结果均为1，但是这两条路径显然是不相同的，这是因为雅克比系数所描述的事务数据不具有先后次序关系，而用户访问Web路径却是有先后顺序的，因此不能单纯用雅克比系数来描述访问路径的相似度。

设定 c omm( ci, cj)表示最长公共路径长度，的最长路径长度，则用户访问路径的相似度系数为：

如有3条W eb访问路径C1={V1，V2，V3}、C2={V2，V3，V4}、C3={V3，V2，V4}，则C1→C2的最长公共路径为V2、V3，长度为2，相似度系数为0.5，而C1→C3的最长公共路径为V2或V3，长度为1，相似度系数为0.25，而C2和C3两条路径中的节点完全相同，节点顺序也大致相同，但是使用该公式计算的相似度仅为0.33，比C1→C2的相似度还低，这显然是不合理的。为此对路径相似度作如下改进：

定义4：路径 Ci→Cj之间的相似度度量记作：

该系数综合考虑了雅克比系数和相似度系数的优点，其中βα,为调节度量的系数，雅克比系数所起的作用随着α值的增大而增大，相似度系数的作用随着β值的增大而增大，顺序性也相应增强。采用该系数进行全部路径之间相似度的计算，得到访问路径的相似度数据矩阵S：

1.2 改进的事物聚类算法

在将访问路径进行两两合并的过程中，最大相似度系数起到了决定性作用，而大部分小于阈值的相似度系数对聚类是不起作用的[5]，因此要解决传统聚类算法在Web日志高维空间数据聚类时的“维数灾难”问题，可以通过过滤较小的相似度系数，从而大大缩小数据规模。

算法1 输出用户访问的相似路径聚类

输入：Web 日志文件，并设定一个阈值θ；

输出：相似路径聚类 C = { Ci}。

算法描述：

C = {φ}；//初始化

While（没有到文件尾）

{

从数据表中读取记录；

While（没有到文件尾）

{

从数据表中读取记录；

计算访问路径的相似度系数 S = ( S')α( S'')β；

If（S>θ）//对S和阈值θ进行大小比较

{保留当前的路径编号；

}

}

得到临时聚类 Ci；

If（ Ci不是类集合C中的一个子集）

{

将 Ci增加到类集合C中；

}

}

计算相交项对各自类的隶属度，并依据隶属度的大小消除重复项；

输出得到的聚类C。

2 改进的偏爱路径挖掘算法

2.1 浏览频度的偏爱度

若用户有m种途径离开某Web页面，则出现次数相对较高的选择是用户较为感兴趣的、偏爱度较高的选择[4]。

定义1：设定Si表示用户通过第i种选择进入下一个页面的频度。根据传统置信度以及公式1的定义，在不考虑所访问站点的结构对传统置信度的限制的情况下，设定用户的第i种选择的置信度为：

定义2：对某一网站，设定其中所有URL集为U，所有子路径集为W，假如Ww⊂，则wx∈∀（x表示由Uu∈∀构成的页面浏览序列，其中第i位表示第i个浏览页面），该浏览序列的前m位是相同的，但第m+1位存在n个不同的页面，表示从m位到m+1位有n种不同的浏览途径，因此，设定第j（j=1,2,…,n）种浏览途径的偏爱度为：

由此可见，在n>1时，由于偏爱度系数P在n种选择中考虑了用户通过第i种途径浏览网页的可能性，因此比传统置信度更能准确地反映出用户的兴趣度。

2.2 浏览兴趣的偏爱度

公式5的算法仅仅考虑了用户浏览页面的频度，这是不全面的[6,7]。因为用户的兴趣度与其访问页面的大小、时间、次数均有关系。页面大则浏览时间长；浏览时间长，则说明用户的浏览兴趣度高；同时，用户的浏览兴趣度还取决于访问次数。

定义3：用户的浏览兴趣度记作I(URL.time,URL.size,URL.num)，设定页面URLi→U RLj的次数为num，在页面 U RLj的访问时间为 U RLi→j.time ，页面URLj的大小为 U RLj.s i ze 。则定义用户的兴趣度为：

2.3 改进的偏爱路径挖掘算法

设定某一网站有n个URL页面，在此构造出一个URL-URL矩阵，其中行元素为URL-Reference，列元素为URL，元素值为用户从一个引用页链接到访问页的兴趣度值；并在行和列中各自增设一个Null空值，如果用户是直接输入网页地址或者是从其他网站链接访问页面，则Null空值就出现在行中；如果用户在所访问的页面上退出网站或者从该网站链接到外部站点，则Null空值就出现在列向量中[8]。另外，任一网页的引用页都不能为自身，因此该矩阵的对角线元素为0。

例1挖掘用户偏爱路径的过程

Null A B C D E F G H 总和Null 0 63 15 2 5 0 0 0 5 90 A 6 0 36 35 0 0 0 0 0 77 B 43 0 0 0 6 40 0 0 8 97 C 3 0 0 0 0 10 30 0 0 43 D 16 0 0 0 0 8 0 35 20 79 E 3 0 0 0 0 0 31 0 0 34 F 5 0 0 23 0 0 0 0 0 28 G 4 45 0 0 0 0 0 0 0 49 H 6 0 0 0 0 0 0 0 0 6

算法2 改进的Web浏览偏爱路径挖掘算法

输入：设定Web浏览矩阵M[n+1][n+1]，Sup表示浏览支持度阈值，Pre表示浏览偏爱度阈值；

输出：Web浏览偏爱路径集合NPS。

3 实验结果分析

设定URL表示站点页面的数目，采用上述算法可以得出挖掘浏览偏爱子路径的时间复杂度是，将相同路径进行合并的时间是，从而得出总时间是

在实验过程中，采用包含25930条记录，35个页面的Web日志作为实验对象，分别使用本文提出的改进偏爱路径挖掘算法与MFP算法在设定的阈值控制下进行路径挖掘，在这两种算法挖掘出相同数量的偏爱子路径和频繁浏览子路径的情况下，与已知的该网站访问偏爱路径进行比较，从而得出各自的准确性。

图1 算法的准确度比较

由此可见，本文提出的改进算法比MFP算法在挖掘偏爱子路径方面有更高的准确性。同时，从图1可以看出随着挖掘路径数的增加这两个算法的准确性都有所降低。这是因为挖掘兴趣度量阈值会随着路径个数的增加而降低，致使挖掘偏爱路径的可信度也随之下降。为了检测两种算法的挖掘时间性能，在实验中，将实验对象分别划分为5000条记录、15000条记录、20000条记录、25000条记录，通过对执行时间进行比较得到图2。从中可以看出改进的用户浏览模式挖掘算法比传统的MFP算法的执行时间增加幅度小，扩展性好。

图2 算法的时间性能比较

4 结束语

本文提出了一种改进的基于事物聚类W eb日志用户偏爱浏览路径的挖掘方法，首先通过对事物聚类算法的改进，消除重复项及相交项，从而更准确地反应出Web用户访问路径相似度，接着以一个三元组模型为基础，对多个相似用户群体相关页面集的偏爱浏览路径进行了挖掘。最后通过与其他算法相比较，本文算法在准确性和时间性能等方面具有一定优越性，能针对不同用户群体的Web浏览偏爱路径进行更加全面、精确地挖掘，可扩展性好。

[1] 李健,徐超,谭守标.一种Web数据挖掘系统的设计和研究[J].计算机技术与发展,2009(02):70-73.

[2] Pierrako S D,Paliouras G.Web Usage M ining as a T00l for Personalization:A survey[J].K luw er A cadem ic Publishers,2003：311-372.

[3] Myra S,Lukaa F. A data m iner analyzing the navigational behaviour of web users [EB/OL].http://www.w iw i.hu_berlin.de/～myra/w_acai99.ps.gz,1999-07-16/2001-07-28.

[4] 付玉.基于W eb日志的频繁浏览路径挖掘技术研究[D].辽宁师范大学,2009,5.

[5] 吴雯雯.基于W eb的用户访问模式挖掘算法及其应用研究[D]. 合肥工业大学,2008,5.

[6] 缪勇,宋斌.基于Web日志的典型匿名用户路径挖掘研究[J].计算机应用,2009,29(10):2774-2777.

[7] 张海玉,刘晓霞.一种挖掘用户浏览模式的新方法[J],计算机应用与软件,2007,24(2):143-150.

[8] 朱志国,邓贵仕.持久偏爱的Web用户访问路径信息挖掘方法[J],情报学报,2010:29(2):208-214.

[9] 富丽娜.关联规则算法研究及其在汽车销售网站的应用[D], 大连理工大学,2007.10.