一个基于Web访问路径聚类的智能推荐系统

文章编号 : 100220411 (2007) 0120119206 一个基于 W eb访问路径聚类的智能推荐系统 宋江春 , 沈钧毅 (西安交通大学电子与信息工程学院 , 陕西 西安　710049) 摘 　要 : 提出了一个基于 W eb用户访问路径聚类的智能推荐系统. 系统使用基于代理技术的结构 ,由离 线的数据预处理和基于用户访问路径的 URL聚类以及在线推荐引擎两部分组成. 提出了一个基于用户浏览 兴趣的推荐规则集生成算法 ,在度量用户浏览兴趣时综合考虑了用户浏览时间和对该页面的访问次数. 提出 了一个基于推荐规则集和站点 URL路径长度的 URL推荐算法. 实验表明 ,该算法比使用基于关联规则和基 于用户事务的推荐算法的精确性有较大幅度的提高 . 3 关键词 : 路径聚类 ; 智能推荐系统 ; 用户浏览兴趣 ;推荐规则集 ; 推荐引擎 中图分类号 : TP391　　　　　　文献标识码 : A An In telligen t Recomm enda tion System Ba sed on W eb Nav iga tion Pa th C luster ing SONG J iang2chun, SHEN Jun2yi ( School of E lectronic and Inform ation Engineering, X ipian J iaotong U niversity, X ipian 710049, China) Abstract: An intelligent recommendation system is p roposed based on clustering ofW eb userpis navigation path. The system uses an architecture based on p roxy techniques, and consists of two subsystem s, i. e. , the offline subsys2 tem , including data p reparation and URL clustering based on userpis browsing paths, and the online subsystem, inclu2 ding a recommendation engine and a W eb HTTP server. A algorithm for generating recommendation rule set is p ro2 posed based on the userpis browsing interest, which is measured by considering synthetically both the userpis browsing time and the number of hits on the W eb page. A recommendation algorithm is p resented based on recommendation rule set and the length ofW eb site URL s. The experiments show that, comparing with the recommendation algorithm s based on association rule or on user transaction, the algorithm p recision is imp roved greatly. Keywords: navigation path clustering; intelligent recommendation system; userpis browsing interest; recommen2 dation rule set; recommendation engine 1　引言 ( In troduction) 用户浏览页面的预测和推荐是目前 W eb挖掘 的一个重要研究方向. 找到一个准确预测浏览行为 的模型并据此推荐相关页面 [ 1, 2 ] ,可以改进搜索引 擎 [ 3 ]和进行个性化用户访问服务 [ 4 ]等. 　　目前的基于协作过滤的推荐系统主要使用神经 网络 [ 5 ]、关联规则 [ 6 ]和聚类 [ 7 ]等 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ,其中关联规 则和聚类方法具有较好的推荐效果. 关联规则是由 Fu和 Hammond首先提出来的 ,它利用 Ap riori算法 通过挖掘用户浏览历史记录的关联来进行推荐 ,这 种方法如果支持度和置信度选取不恰当 ,会造成计 算时间太长或推荐性能变差. Mobasher于 2000年提 出用事务聚类的方法来构建推荐系统 [ 8 ] ,并取得了 较好的效果. 但是这种方法在聚类时只采取用户访 问页面的布尔量. 显然 ,这种方法不能准确反映用户 对某个网页的访问时间和点击次数. 　　本文在分析目前推荐系统存在问题的基础上 , 构造了一个基于代理结构的智能推荐系统 PC IRS ( Path Clusteringpis Intelligent Recommendation Sys2 tem) ,提出了一个基于用户访问路径聚类的推荐规 则集生成算法 ,算法同时考虑了用户浏览时间和对 该页面的访问次数 ,然后将具有相似用户浏览兴趣 的页面进行实时推荐. 给出了基于推荐规则集和站 第 36卷第 1期 2007年 2月 　信息与控制 Information and Control Vol. 36, No. 1　 　 Feb. , 2007　 3 收稿日期 : 2006 - 03 - 04 　基金项目 : 国家自然科学基金资助项目 (60173058) © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 点 URL路径长度的推荐算法. 最后对系统的性能进 行了验证. 2　PC IRS结构 ( Arch itecture of PC IRS) 智能推荐系统 PC IRS由离线和在线两个模块 组成 ,系统结构如图 1所示. 图 1　PC IRS结构图 Fig. 1　A rchitecure of PC IRS 　　离线模块由两部分组成 :第一部分是对原始日 志数据预处理 ,获得用户浏览路径事务文件 ,一个用 户浏览路径是一个用户在一段时间内的一组有某种 意义的浏览页面的集合 ;第二部分是使用关联规则 和路径聚类技术发现相似 URL,形成推荐规则集. 　　在线模块为用户提供推荐页面链接 ,由推荐引 擎和 HTTP服务器组成. 推荐引擎将用户当前的浏 览兴趣与推荐规则集的 URL簇结合起来考虑 ,根据 推荐算法生成相应推荐页面集. 在用户最新请求的 页面上添加推荐集的页面链接 ,再通过 HTTP服务 器传递到客户端的浏览器. 　　为了提高系统的通用性和效率 ,在线的推荐引 擎和离线模块的 W eb挖掘部分放在一起构成推荐 代理服务器. 3　推荐规则集生成算法 ( A lgor ithm for ge2 nera ting recomm enda tion rule set) 推荐规则集生成算法是智能推荐系统的核心部 分. 本节首先构造用户访问路径和用户浏览兴趣矩 阵 ,利用关联规则和基于路径的 URL聚类算法相结 合的方法给出推荐规则集生成算法 ,算法同时考虑 了用户对页面的浏览时间和点击次数 ,使算法有较 好的精度和效率. 3. 1　用户浏览路径 　　经过数据清洗后的 W eb日志可以看成是一个 用户访问表 V,它由一组属性来定义 V = { v1 , v2 , ⋯, vm }. 一般的属性包括上面所介绍的用户访问的 IP 地址、时间、请求的网页、状态、传送的文件字节数 等. 　　定义 1　 (用户访问路径事务 )将一段时间用户 的访问日志组织成用户访问路径事务数据. 访问路 径事务被定义为 : psi = ( vi1. u rl, vi1. view tim e, vi1. h itnum ) , ⋯, ( vim . u rl, vim . view tim e, vim . h itnum ) 〉 (1) 其中 , vik ∈V,表示第 i个用户的第 k个属性 , vik. ip = ipi、vik. u id = u idi ,表示第 i个用户的 ip地址和用户 id, vik. view tim e表示到目前为止用户 u idi 在页面 v i k. u rl上的浏览时间 , vik. h itnum 表示浏览次数. v i k. view tim e - v i k - 1. view tim e≤A. 这里 A是一个固定的 时间窗. 访问路径事务 psi 被简写为 : psi =〈vi1. u rl, vi2. u rl, ⋯, vip. u rl〉 (2) 　　找到用户访问路径事务集之后 ,就可以据此建 立用户浏览兴趣矩阵并在其上进行相似 URL聚类. 　　算法 1:从 W eb日志中生成用户访问路径事务. 　　输入 :经过清洗的 W eb日志文件 V. 　　输出 :用户访问路径事务. begin for each IP address in weblog do 　sort data by viewtime to increase order; 　for each record in weblog do 　　create a new access path session psi ; 　　if vik. view tim e - vik - 1. view tim e≤A then 　　　add record to psi; 　　else 　　　create a new access path session in V; 　　endif 　endfor endfor end 3. 2　用户浏览兴趣矩阵 　　聚类时 ,首先考虑用户浏览兴趣 ,我们根据用户 在站点 URL上的浏览时间来定义用户的浏览兴趣 , 将离散化技术应用到用户浏览兴趣表示上 ,将时间 属性划分为区间 ,用区间的标号来代替实际的时间 值. 　　定义 2　 (用户浏览兴趣度 )按照用户在一个页 面上的浏览时间 ,将用户浏览兴趣度定义为 : 021 　信 　息 　与 　控 　制 36卷 © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net T = 0　 view tim e≤ 5 s 1 15 s < view tim e≤ 60 s 2 60 s < view tim e≤ 180 s 3 view tim e > 180 s (3) 其中 , view tim e表示浏览时间 , s表示秒. 　　定义 3　 (用户浏览兴趣矩阵 )根据定义 1、定 义 2建立 W eb站点的用户浏览兴趣矩阵 ,即 : M m ×n = T11 T12 ⋯ T1 j ⋯ T1n T21 T22 ⋯ T2 j ⋯ T2n ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ Ti1 Ti2 ⋯ Ti j ⋯ Tin ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ Tm 1 Tm 2 ⋯ Tm j ⋯ Tm n (4) 其中 , m 为站点 URL的个数 , n为用户访问路径事 务数 ; Ti j是第 j个用户对第 i个 URL的浏览兴趣度 之和. 　　从上面的定义看出 ,每一列向量表示用户的一 条访问路径 ,每一行向量表示用户对该站点中所有 的 URL的访问情况. 因此 ,度量行向量的相似性 ,就 能得到相似 URL. 3. 3　推荐规则集生成算法 　　根据上面已经建立的用户访问兴趣矩阵 ,我们 就可以对 URL页面进行聚类了. 本节首先利用经典 的快速频集发现算法来发现相关 URL集 ,然后再根 据用户对用户访问路径中的 URL的点击次数对发 现的频集进行再聚类 ,得到在线推荐的规则集. 3. 3. 1　生成初始推荐规则集 　　在用户访问兴趣矩阵中 ,将行向量看作事务项 , 根据关联规则挖掘算法得到频集 ,也就是相似 URL 集 ,并将其作为初步的 URL分类结果. 为此 ,对支持 度 ———行向量在整个 URL事务集中出现的频度 ,作 如下的定义 : 　　定义 4　设 U 是站点 URL的集合 ,任意 P < U , 其支持度定义为 : s ( P ) = 1 P ∑ m i =1 ∑ P j =1 Ti j (5) 其中 , P 是 P中 URL的个数 , Ti j是一段时间内第 j 个用户对第 i个 URL的浏览兴趣度之和. 　　该定义将 P的支持度定义为用户对 P中 URL 兴趣度的平均值. 基于所定义的支持度 s ( P ) ,可以 利用 Agrawal等人提出的频集发现快速算法 [ 9 ]获得 URL频集 ,然后扫描整个数据库就可以得到对应的 URL集. 设得到的初始聚类为 R = { R i } ,我们称为 初始推荐规则集. 3. 3. 2　推荐规则集生成算法 　　我们根据类的相似度对得到的关联规则组成的 类进行层次合并 ,以得到更好的聚类结果. 根据用户 对浏览路径中 URL页面的点击次数 ,用夹角余弦法 来定义类的相似度. 　　定义 5　 (规则相似度 )设 R为初始规则集 , R i , R j < R , R i、R j的相似度定义为 : sim (R i , R j ) = ∑ n k =1 hik hjk ∑ n k =1 h2ik ∑ n k =1 h2jk (6) 其中 , hik表示第 k个用户对第 i个 URL的点击次数 , n表示网站用户访问路径条数. 　　根据上述的相似度定义 ,应用合并层次聚类思 想 ,我们给出对初始规则集的层次聚类算法如下 : 　　算法 2:规则集生成算法. 　　输入 :初始规则集 R;最小相似度阈值Γ. 　　输出 :推荐规则集 C. 　　　　begin 　　C = R; 　　Cnum = C ; 　　while Cnum < C + 1 　　　for each Ci ∈C do 　　　　for each Cj∈C do 　　　　　computing sim (Ci , Cj ) according to (6) ; 　　　　endfor 　　　　si j = 0; 　　　　if sim (Ci , Cj )≥Γ then 　　　　　si j = sim (Ci , Cj ) ; 　　　endif 　　　　endfor 　　　　if si j < > 0 　　　　　select max{ si j } ; 　　　　　Ci = Ci ∪Cj; 　　　　　delete Cj from C; 　　　　　Cnum22; 　　　else 　　　　　break; 　　　endif 　endwhile; 　end 　　该合并型层次聚类算法首先在每次聚类之前判 断类的数量是否有减少 ,如果类的数量没有减少则 表示该算法没有产生新的聚类集合 ,算法将结束. 聚 1211期 　　宋江春等 : 一个基于 W eb访问路径聚类的智能推荐系统 © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 类过程首先在当前的聚类集合中找出具有最大相似 度的两个类 ,如果它们的相似度满足输入的最小相 似度阈值 ,则将它们进行合并产生新的聚类集合 ,同 时将当前聚类集合中类的数量减 1,然后再重新判 断. 我们将聚类的结果用于在线推荐的规则集. 4　推荐算法 ( Recomm enda tion a lgor ithm ) 推荐引擎是 PC IRS系统在线推荐子系统中的 一个核心功能模块. 推荐引擎通过 W eb服务器获得 用户当前访问路径 ,并应用离线挖掘子系统得到推 荐规则集 ,根据访问 URL的相似性推测用户可能需 要的页面链接 ,调用适当的推荐算法来得到推荐信 息. 然后 ,再将该推荐信息传给推荐页面生成器生成 最终发送给用户的推荐页面. 本节根据上节 URL页 面聚类的结果得到推荐规则集 ,给出了一个新的基 于协作过滤的 W eb页面推荐算法. 4. 1　相关定义 　　为了给出推荐算法 ,我们先给出相关定义. 　　定义 6　 (用户当前活动会话 )一个用户活动事 务可以表示为一个矢量 : s = ( s1 , s2 , ⋯, sp ) ,矢量的元 素表示网站的 URL,而矢量的值表示在该活动用户 事务中访问该 URL的总的兴趣度. 　　定义 7　 (匹配度 )设 U 是 URL的集合 ,任意 s< U , c< U , s和 c的匹配度由下式计算 : m ( s, c) = 1 c ∑j∈c ∑ n k =1 sk Tjk s Tjk (7) 其中 , Tjk∈M m ×n表示 j用户在一段时间内对第 k个 URL的兴趣度 ,由定义 4, Tjk 表示用户浏览兴趣矩 阵 M m ×n的第 j行的长度 , c 表示 URL集 c中 URL 的个数. 　　从定义可以看出 ,活动用户事务 s和类 c的匹 配度就是 s和 c中 URL事务相似度的平均值. 　　我们知道 , W eb站点可以表示成一个有向图 : G = (U , E ) 其中 , U 是站点 URL的集合 , E是有向边集合. 　　有向图中的每一个节点代表了站点中相应的一 个 W eb页的 URL. 如果 W eb页 X到 W eb页 Y存在 一条物理链接 ,则相应的节点 X到节点 Y存在一条 有向边. 两个 W eb页面 u1 和 u2 之间的物理链接路 径距离定义为在站点有向图中从 u1 到 u2 的最小访 问路径长度. 　　定义 8[ 9 ] 　 (链接距离因子 )设 s为当前用户的 浏览路径 , u∈U; d ( u, s, G )表示 u到 s中的 URL之 间的最小物理链接路径距离 , u关于 s链接距离因 子定义为 : idf ( u, s, G ) = log2 d ( u, s, G ) + 1 (8) 　　对距离取对数计算 ,目的是在下面讨论计算推 荐度时 ,不要过度影响匹配度对推荐度因子的贡献. 　　在生成推荐集时 ,需考虑以下几方面的因素 : 　　 (1) 当前活动会话与每个聚类的匹配度大小. 匹配度反映了相似程度的大小 ,相似度大的应该优 先考虑 ; 　　 (2) 候选 URL与当前用户访问操作的物理距 离. 从新颖性的角度看 ,推荐一个物理链接上远离当 前用户访问操作的 W eb页是优先考虑的对象 ; 　　 (3) 候选的推荐页面是否已经被当前用户访问 过. 　　我们综合匹配度 m 和距离因子 ,给出下面的推 荐因子的定义. 　　定义 9　 (页面推荐因子 )设 s = { s1 , s2 , ⋯, sp } 为一个活动会话 , C = < uc1 , uc2 , ⋯, ucn >∈C 为一个 类 , c中一个页面 u的推荐因子为 : rec ( s, u ) =m ( s, c) ·idf ( ( s, u ) (9) 　　设最小推荐阈为ρ,每个簇中所有推荐值大于 或等于ρ值的页面构成当前活动会话的推荐集 : R ecomm end ( s) = { uci ︳c∈ C , rec ( s, uci ) ≥ρ} (10) 　　对于来源于多个簇的页面 ,其最大值为推荐值. 4. 2　相关算法 　　算法 3:基于路径聚类的推荐集生成算法. 　　输入 :推荐规则集 C ,当前用户活动路径 s.τ:匹 配阈值 ,ρ:推荐因子阈值. 　　输出 :推荐集 R ecomm end ( s) . 　　begin 　　R ecomm end ( s) = Ф; 　　for each ci ∈C do 　　　computing m ( s, ci ) according to (7) ; 　　　if m ( s, ci )≥τ then 　　　　for each uij ∈ci do computing idf ( s, uij ) according to (8) ; computing rec ( s, uij ) according to (9) ; if rec ( s, uij )≥ρ then if uij | s add uij to R ecomm end ( s) ; endif endif endfor 221 　信 　息 　与 　控 　制 36卷 © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net i + +; endfor sort Recomm end ( s) byρ to increase order; end 5　系统性能评价 ( System performance eva lu2 a tion) 在对推荐系统的推荐效率进行评价时 ,我们使 用目前国际上采用较多的准确率和覆盖率概念 [ 9 ]. 所谓覆盖率 ( coverage)是指在推荐的内容中用户得 到的推荐数和用户总的推荐请求数的比值 ,而准确 率 (p recision)是指准确的推荐数和总的推荐数的比 值. 测试时一般将测试集中每个会话记录的前 n个 页面作为推荐的输入参数 (用户访问模式 ) ,将从推 荐系统得到的推荐结果页面集合作为推荐项集 RS , 而将测试集的会话记录中前 n个页面后的若干个页 面做为项集 U S. 根据覆盖率和准确率的定义 ,推荐 算法的覆盖率和准确率可以分别采用式 ( 11)、( 12 ) 进行计算. coverage = U S ∩ RS U S (11) precision = U S ∩ RS RS (12) 　　用 Java语言在 W indows NT平台上实现了本文 算法和文 [ 6 ]、[ 7 ]的相关算法. 利用某远程教学网 站日志信息进行了实验. 站点 URL的数目为 667, weblog的日期为 0: 00 /10 /01 /2005223: 59 /12 /31 / 2005,用户路径事务数 (识别后 )为 3573. 选择其中 前 500个 URL的访问记录 ,剔除访问时间小于 2 s、 长度小于 4的会话记录. 　　将本文算法、文 [ 6 ]的关联规则算法和文 [ 7 ]的 聚类算法的推荐性能进行了比较. 　　首先对准确性进行比较. 测试时对 W eb日志上 的历史访问记录进行分割以形成大小为 100k、 300k、500k、700k、900k和 1100k的 6个训练样本. 从 W eb日志中生成 1000条用户路径事务作为测试 集. 然后依次采用文 [ 6 ]算法、文 [ 7 ]算法和本文算 法生成的推荐集进行准确性比较 ,得到图 2所示的 曲线图. 可以看到 :对于任何一个训练样本 ,本文算 法生成的推荐集都具有较高的准确性. 　　然后对覆盖率进行了比较. 测试时同样对 W eb 日志上的历史访问记录进行分割以形成大小为 100k、300k、500k、700k、900k和 1100k的 6个训练 样本. 从 W eb日志中生成 1000条用户事务作为测 试集. 然后依次采用文 [ 6 ]、[ 7 ]的算法和本文算法 生成最佳推荐进行覆盖率的比较 ,得到图 3所示的 曲线图. 可以看到 :文 [ 6 ]关联规则的推荐算法有最 高的覆盖率 ,文 [ 7 ]聚类分析的推荐算法次之 ,我们 的推荐算法的覆盖率和文 [ 7 ]接近. 从此可以看出 , 算法在大幅提高准确性的同时覆盖性有一定程度的 下降. 图 2　不同推荐算法准确性比较 Fig. 2　Comparison of the p recision among the different recommendation algorithm s 图 3　不同推荐算法覆盖率比较 Fig. 3　Comparison of the coverage rate among the different recommendation algorithm s 6　结论 ( Conclusion) 本文构建了一个基于 W eb用户访问路径聚类 的智能推荐系统 ,它使用了代理服务器的方法 ,使系 统有较好的通用性和推荐效率 ;根据用户访问路径 事务和用户浏览兴趣 ,提出了一个推荐规则集生成 算法. 由于使用了关联规则和 W eb访问路径聚类技 术相结合的方法 ,使算法的准确度有较大幅度的提 高 ;利用用户对 URL页的兴趣度重新定义了推荐页 面和推荐规则集的匹配度 ,给出了相应的推荐算法. 实验结果表明 ,我们提出的基于用户访问路径的智 3211期 　　宋江春等 : 一个基于 W eb访问路径聚类的智能推荐系统 © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 能推荐系统有较高的推荐准确性. 参 　考 　文 　献 ( References) [ 1 ]　 Srivastava J, Cooley R, Deshpande M, et a l. W eb usage m i2 ning: D iscovery and app lications of usage patterns from web data [ J ]. SIGKDD Exp lorations, 2000, 1 (2) : 12～23. [ 2 ]　 Sarwar B, Karyp is G, Konstan J, et a l. Analysis of recommenda2 tion algorithm for E2commerce [A ]. Proceedings of the 2nd ACM Conference on Electronic Commerce [ C ]. New York: ACM Press, 2000. 158～167. [ 3 ] 　 B rin S, Page L. The anatomy of large2scale hypertextual web search engine [ J ]. Computer Networks and ISDN System s, 1998, 30 (1 - 7) : 107～117. [ 4 ]　 Pirolli P, Pitkow J E. D istribution of surferspipaths through the world wide web: Emp irical characterization [ J ]. World W ide W eb, 1999, 2 (1 - 2) : 29～45. [ 5 ]　 B illsus D, PazzaniM J. Learning collaborative information filters [A ]. Proceedings of the Fifteenth International Conference on Machine Learning [ C ]. San Francisco, CA, USA: Morgan Kaufmann Publishers, 1998. 46～54. [ 6 ]　 Fu X, Budzik J, Hammond K J. M ining navigation history for recommendation [A ]. Proceedings of the 2000 International Con2 ference on Intelligent U ser Interfaces [ C ]. New York, USA: ACM Press, 2000. 106～112. [ 7 ]　 Mobasher B, Dai H H, Luo T, et a l. D iscovery of aggregate usage p rofiles for W eb personalization [ A ]. Proceedings of the W eb M ining for E2Commerce Workshop [ C ]. New York, USA: ACM Press, 2000. 255～264. [ 8 ] 　 Agrawal R, Strikant R. Fast algorithm for m ining association rules [A ]. Proceedings of the 20 th International Conference on Very Large Data [ C ]. New York, USA: ACM Press, 1994. 487 ～499. [ 9 ]　 Mobasher B , Dai H, Luo T, et a l. Imp roving the effectiveness of collaborative filtering on anonymous W eb usage data [ A ]. Pro2 ceedings of IJCA I201 Workshop on Intelligent Techniques forW eb Personalization [ C ]. Heidelberg, Germany: Sp ringer2Verlag, 2001. 53～60. 作者简介 宋江春 (1962 - ) ,男 ,副教授 ,博士生. 研究领域为智能 信息控制与数据挖掘. 沈钧毅 (1939 - ) ,男 ,教授 ,博士生导师. 研究领域为智 能信息控制 ,数据挖掘 ,工作流等. (上接第 118页 ) 作者简介 王国胜 (1975 - ) ,男 ,博士 ,讲师. 研究领域为线性系统 理论 ,鲁棒控制理论及应用. 汤霞清 (1965 - ) ,男 ,博士 ,副教授. 研究领域为坦克火 控与指控系统智能控制技术 ,导航与定位技术. 段广仁 (1962 - ) ,男 ,博士 ,特聘教授. 研究领域为线性 系统理论、鲁棒控制理论及其在航天中的应用. 421 　信 　息 　与 　控 　制 36卷 © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net