基于协同过滤的推荐系统

基于协同过滤的推荐系统

[摘要] 本文先对网站日志文件进行研究并预处理,将用户访问网站形成的日志文件转换成用户访问模式;接着用对用户访问模式进行K-mean聚类分析,提取具有代表性的用户访问模式;最后用协同过滤推荐技术向网站访问者进行推荐,提供个性化服务,从而实现网站的个性化推荐。

[关键词] 协同过滤 web日志挖掘 推荐系统

[Abstract] This article firstly researching and preprocessing the original web log data to website visit pattern. Then, we use the K-mean Clustering algorithm to cluster the website visit patterns, finally, we use collaborative filtering-based recommendation technology to provide the website visitors the personalized services so as to generate personalized recommendation.

[Key words] Collaborative Filtering Web Log Mining Recommendation Systems

1 引言

目前我国互联网快速发展,网络信息量呈爆炸式增长,许多信息以网页的形式存在于互联网中。互联网提供海量网页信息的同时,也对网站访问者从庞杂的网站中快速地获取目标网页造成不小的障碍。为了帮助网站访问者高效获取目标信息,各网站纷纷推出具有个性化的服务。网站设计者可以根据用户访问偏好改变网站的架构,使同一页面对于不同的用户呈现不同的视图内容,从而满足不同用户的个性化需求。而基于 Web日志挖掘技术是实现这种个性化服务的基本手段之一[2]。

目前许多网站采取个性化推荐技术,采用的主流技术一般有关联规则方法、协同过滤方法 [1]和内容过滤方法[3]。其中,协同过滤方法根据相似用户预测当前用户的兴趣并推荐信息,是当前个性化推荐系统中比较成功的方法。但是协同过滤方法每次查找相似用户计算相似度的时候,均必须扫描整个数据库,时间消耗非常大。本文用K-mean算法对数据集进行聚类,查找相似邻居只需在相似度最高的类中进行查找,减少查找邻居的时间。通过K-mean聚类算法构造出用户的兴趣模型,当新的访问者访问网站时,可快速计算当前用户的兴趣模型,然后用协同过滤推荐技术向用户进行推荐。

2 协同过滤推荐技术

协同过滤推荐技术是目前最流行和最成熟的推荐技术,广泛应用于各种推荐系统中。协同过滤思想广泛应用于日常生活中,例如人们往往根据亲朋好友的推荐来做出一些选择。协同过滤系统就是将这一思想运用到网络信息服务中,基于其他用户对某一信息的评价来向某一用户进行推荐。用户获得的推荐是系统从用户购买模式、访问模式或点击行为等隐式获得的,不需要用户努力地找到适合自

己兴趣的推荐信息。

我们用K-mean算法将网站访问者分为 k类,得到 k个访问模式。当一个新用户访问网站时,我们先获取当前访问者的浏览行为,然后分别计算其的访问模式和 k个模式的相似性,最后将相似度最高的访问模式推荐给当前访问者。我们这里采用余弦相似性度量方法。余弦相似性度量方法把当前访问者的访问模式和模式库中的模式当作两个 n维向量。

3 基于协同过滤的推荐流程

3.1 日志文件预处理

我们对日志文件进行预处理和进行会话识别,即对原始Web日志文件中的数据进行提取、分解、合并,最后转化为适合进行数据挖掘的数据格式,并保存到关系型数据库表中。对于一个网站来说,某一段时间的拓扑结构是不变的。我们可以用每个网页的 URL作为用户访问矩阵的列,发起每一个会话的用户作为用户访问矩阵的行。我们以IP作为用户识别的标识,设置timeout为30分钟作为会话识别的时间分割值。每一个会话只记录这一次会话访问的网页的URL和访问次数,对于没有访问到的网页,我们用把它的访问次数设为 0。按照以上的方法我们得到用户的访问矩阵,矩阵中每一行即为一个访问模式。

3.2 构造访问模式库

用K-means算法对历史访问模式库进行聚类分析,就可以得到k个模式。我们采用余弦相似性度量公式计算模式库中任意两个模式的相似度,对于k的选择,根据前人的研究成果,当K>=6的时候,聚类结果变化不是很大,我们对实验数据集进行实验,发现数据集仍然符合这一规律,因此取K=6。

3.3 邻居访问者的确定

由用户访问矩阵计算用户的相似关系群。用户的相似关系群就是与用户的访问模式相似的用户集合,协同过滤推荐算法认为如果两个用户访问模式相近,就意味着这两个用户在访问其他网页时的兴趣也是相近的。用户u和用户v之间的相似性值采用皮尔森相关关系式计算。

3.4为目标用户形成推荐

计算当前访问者产生的部分访问数据并构造一个访问模式,将这个当前访问模式和模式库中的k个中心进行相似度计算,在中心相似度最高的类中再次计算每个模式和当前访问模式的相似度,从而找到相似度最高的模式,最后将相似度最高的模式中用户未访问的网页推荐给用户。

4 实验及实验分析

4.1 实验系统设计流程图

整个设计主要分为两部分:离线部分和在线部分。离线部分对历史数据进行分析、处理,在线部分对当前访问者进行推荐。

离线部分中分为两部分:数据预处理和聚类分析。数据预处理主要对原始数据进行数据清洗、用户识别、格式转换和会话识别,聚类分析对预处理得到的数据进行分析,形成K个访问模式。在线部分利用离线部分得到的K个访问模式和当前访问者的访问模式进行相似性计算,然后向访问者推荐访问者没有访问的而且访问者很有可能感兴趣的网页url。

4.2 数据集

我们采用北京航天航空大学北海学院 2010 年9月4 日全天的网站日志文件,一共得到2800 个用户(相同IP,但是timeout 值超过30 分钟,这样的两个会话认为是不同的用户),453 个网页url,我们保留访问网页数大于5 的会话,一共提取出3300 个会话。整个日志文件70%作为训练集,30%作为测试集。

4.3 实验结果

文中采用平均绝对偏差MAE作为推荐质量的度量标准。在基于协同过滤的推荐系统中,对于查找邻居用户,只需首先查找相似度最高的类中心,再从类中心相似度最高的类中查找邻居;如果在相似度最高的类中没有找全所有邻居,接着从相似度次高的类中进行查找,直到把所有邻居都找到为止。我们和未使用聚类的系统做了相应的推荐精度对比实验,实验结果中,使用K-mean聚类的推荐结果随着K的增大,MAE的值在0.6至0.85之间,K值越大,MAE的值越大;未使用K-mean聚类的推荐结果的MAE保持在0.6左右。

4.4 实验结果分析

查找当前访问模式的邻居只需在中心相似度最高的类中进行,速度相当快。从上述实验结果可以看出,使用K-mean聚类的推荐结果和未进行聚类的推荐结果相比,推荐精度并没有显著下降。

参考文献:

[1]杨武剑,王泽兵,冯雁,武新玲.网站个性化服务的研究.浙江大学学报(工学版).2003年5月,第37卷第3期.

[2]Schafer J B, Konstan J, Riedl J.Recommender Systems in E-commerce[C].Proceedings of the ACM Conference on Electronic Commerce,1999.

[3]Sarwar B, Karypis G, Konstan J.et a1.Analysis of Recommendation Algorithms for E-commerce[C].Proceeding of the ACM Conference on Electronic

Commerce,2000.

[4]郭晔,王浩鸣,杨新安.基于海量数据挖掘的个性化推荐系统.西北大学学报(自然科学版).2006年12月,第36卷第6期.