基于Web挖掘的关联推荐算法研究

金加和 张泯泯

（浙江省电子政务学会，浙江杭州 310000）

0 引言

Web 技术的研究热点是提供个性化服务给用户，Web个性化的实现采用的是关联规则，使用关联规则挖掘在Web上对用户访问网站的模式进行挖掘，并且对用户在线推荐结合当前访问行为进行。采用的是支持度—信任的约束，在现有的在线推荐算法中减少或消除无用的规则，这种算法能够产生准确的推荐，一定程度上的保证了推荐系统的实时性。本文对用户个性化需求进行探讨分析，用户事务模式的挖掘基于Log 文件，在线方式的智能个性化推荐服务是通过关联规则挖掘算法和Web 挖掘技术来实现的。

1 关于Web数据挖掘技术

1.1 Web数据挖掘技术：指在Web环境下应用数据挖掘技术，在挖掘搜索信息、用户访问日志文件、网络用户登记信息、商品信息、购销信息以等内容中充分利用网络（Internet），在其中找出潜在有用的、有价值并且是隐性的商业信息，然后把这些信息应用到企业管理以及商业决策。从专业技术上，它完美的结合了数据挖掘技术和WWW技术，作为种新兴的网络技术在不同的领域都得到了很好的应用，例如常见的计算机语言和Internet、人工智、、信息学以及统计学等。

1.2 Web数据挖掘具备的特点：一是可以处理大规模的数据量；二是用户“访问模式动态

获取”不会过时；三是用户不用提供主观的评价信息，使用方便；四是Web的优势在于提供了一个巨大、分布广泛、全球性的信息服务中心，这是传统数据库和数据仓库无法比拟的。

2 关联推荐算法思路分析

在离线状态下上传Log文件是通过WEB服务器实现的，把频繁前向访问路径集找出，从而生成频繁访问路径聚集图，导航页和内容页包含在其中；在线状态情况下对用户最新的访问记录进行始终记录由活动窗口来完成，活动窗口的W个网页为记录个数，并且这个网页作为当前访问路径；从离线生成的聚集图上获取W＋1 个网页，作为候选的推荐路径；结合网站的结构删除一些候选推荐路径，这些路径中含有最小偏爱度要求、最小支持度和导航页，最后待推荐集由剩余的网页来形成，推荐给用户推荐度在前TOP_N 个的网页。

3 算法分析

3.1 频繁访问路径图的生成

在服务器端进行数据预处理日志文件Log，这些文件包含用户历史访问信息，建立用户访问事务集；过滤掉不频繁的项使用最小支持度，频繁访问路径聚集图的形成用户访问事务集中进行，为在线阶段计算推荐集打好基础。寻找MFPS即最大前向访问路径集，更新的页面属性值时，对于同一页面的不同MFP，则将曾为内容页的页面更新为内容页；对于同一页面的同一MFP中，只要MFP中的个页面在次访问中是用户感兴趣的，就当作是内容页；通过这些方法对所有兴趣不同的主题页面进行收集，根据后面提出的推荐因子来对与访问的无关的页面进行过滤，生成频繁访问路径聚集图G。

3.2 推荐集的计算

首先从聚集图关联推荐服务算法中发现关联规则，并且这个关联规则匹配用户访问路径，接下确定推荐项，这个过程是根据推荐度因子的大小来实现的，其中推荐度因子是指距离因子乘以关联规则的置信度。对用户的访问路径的获取采用滑窗采样，对用户的访问操作有效实时地跟踪，可以实现在线推荐。滑窗采样是用户访问路径滑窗覆盖为W去匹配聚集图上的子访问路径，从而获取频繁子访问路径，所有长度为 W＋1。

3.3 收集和分析用户信息、进行推荐、产生推荐结果等都属于个性化推荐系统，它们可以分为在线和离线两个部分。

a、在线部分：根据支持数的大小对用户当前的访问页面序列进行排序，关联规则的前项在规则集中去寻找相匹配的规则，推荐给用户推荐度在前TOP_N 个的网页。

b、离线部分：该部分用于对用户信息的收集和分析，进行数据预处理用户之前的访问日志历史，把它转变为纯净的适合挖掘的数据，兴趣访问模式的获取是对该用户访问页面之间的关联规则采用关联规则挖掘算法FP-Mine算法进行挖掘。

Web个性化推荐原型的体系结构图如下：

3.4 FP-Mine挖掘算法使关联规则的挖掘效率得到了很大提高，它不仅能够寻找频繁访问模式集而且给出关联规则的方法。算法描述如下：

作为树形结构Freq-Set-Tree，对(i+1)-size 和i-size和(i=1，2，3…，n)的频繁项集进行存储，分为5个域的树中节点，如下为其具体定义：

struct FSnode

{ unsigned int *id；// 存储项集的名字

unsigned int support；// 项集的支持度

double confidence；// i-size节点中关联规则(p p …p =＞p) 的

置信度

FSnode *left；// 指向比本节点的id长度增1的一个超集对应的

节点

FSnode *right； 指向与本节点的id有相同长度的另一个项集对

应的节点

}；

每个节点在树中的结构：

struct FPnode

{ unsigned int name；// 是1-size项集名称

unsigned int support；// 为其计数域

set＜FPnode＞ *child；//指向其后继节点

FPnode *nodelink；// 指向与其具有相同name的另一个节点

}；

算法、输入、输出方法：

Algorithm FP-Mine()

{ ⒈利用FP-Tree头表，建立1-size节点；

⒉for(i=1；i＜＝n；i++)/*n为生成规则前项的最大长度*/

{ ⑴for each itemin i-size

①P_Insert()；/*生成i-size 和(i+1)-size的Freq-Set-Tree并生成

相应的关联规则*/

⑵从Freq-Set-Tree中释放所有i-size节点；

⑶删除Freq-Set-Tree树中不满足最小支持数的(i+1)-size节

点；

}

4 在商业网站中的应用价值分析

结合商品目录应用多层关联推荐算法，快速自动选择最佳的匹配粒度，在频繁集的基础上进行在线推荐。在实践中得到，这种算法对在线匹配的质量和性能有很大程度的提高，在电子商务中能够成功的应用在个性化服务中。用户在商务网站购买商品、浏览、搜索等方面的信息在Web服务器中都会有记录，商家利用这些数据提供个性化优质的服务给用户，能够留住旧客户，并且提高客户的忠诚度，更多的新客户也能被吸引过来。

5 结束语

通过上述内容分析和探讨了关联规则的挖掘算法，并对FPMine挖掘算法的性能进行了探讨，设计出个性化推荐系统模型，能够个性化对用户进行推荐。采用支持度—信任的约束，在现有的在线推荐算法中减少或消除无用的规则，这种算法能够产生准确的推荐，一定程度上的保证了推荐系统的实时性。

[1]李恒杰，李明.基于本体的Web分类技术研究[J].微计算机信息, 2006，7-3:215-217

[2]薛惠锋,张文宇,寇晓东.智能数据挖掘技术[M].西安:西北工业大学出社,2005:33-35.

[3]闫莹，王大玲.支持个性化推荐的Web页面关联规则挖掘算法[J].计算机科学工程.2005，31(1): 79-81

[4]韩晓莉，李秉智.个性化Web推荐服务研究[J].计算机科学,2006，33(2):135-138

[5]何小东,刘卫国.数据挖掘中关联规则挖掘算法比较研究[J].计算机工程与设计,2005,26(05):1265-1268.

[6]冯珺，孙济庆.基于前项不定长关联规则个性化推荐算法的研究[J].计算机工程与应用, 2006，7(6): 174-177