个性化服务中基于用户聚类的协同过滤推荐_王辉

收稿日期:2006-11-30;修订日期:2007-02-07　　基金项目:国家自然科学基金资助项目(60203018);教育部科学研究重点项目资助

(200202);河南省高校杰出科研人才创新基金资助项目(2006KYCX004);河南省青年骨干教师基金资助项目(134)　　作者简介:王辉(1966-),女,河北安平人,副教授,主要研究方向:计算机网络、人工智能;　高利军(1981-)男,山西吕梁人,硕士研究生,主要研究方向:人工智能;　王听忠(1973-),男,河南洛阳人,讲师,主要研究方向:数据挖掘.

文章编号:1001-9081(2007)05-1225-03

个性化服务中基于用户聚类的协同过滤推荐

王　辉1

,高利军1

,王听忠

2

(1.河南科技大学电子信息工程学院,河南洛阳471003;2.洛阳师范学院计算机科学系,河南洛阳471022)

(glj@mail .haust .edu .cn )

摘　要:协同过滤技术被成功地应用于个性化推荐系统中,但随着系统规模扩大,它的效能逐渐降低。针对此缺点,使用了基于用户聚类的协同过滤推荐,根据用户评分的相似性对用户聚类,在此基础上搜索目标用户的最近邻居,从而缩小用户的搜索范围。本文还提出将协同过滤推荐分为类内相似系数计算和产生推荐两个阶段,把相似系数的计算放在离线部分,减少在线推荐的计算量,提高实时响应速度。另对聚类算法初始聚类中心的选取也做了改进。

关键词:协同过滤;推荐系统;聚类中图分类号:TP391　　文献标识码:A

Coll abora ti ve f ilter i n g recomm enda ti on

ba sed on user cluster i n g i n persona li za ti on serv i ce

WANG Hui 1

,G AO L i 2jun 1

,WANG Ting 2zhong

2

(1.College of Electronic Infor m ation Engineering,Henan U niversity of Science and Technology,L uoyang Henan 471003,China ;

2.D epart m ent of Co m puter Science,L uoyang N or m al U niversity,L uoyang Henan 471022,China )

Abstract:Collaborative filtering is the most successful technol ogy for building recommendati on system s .Unf ortunately,the efficiency of this method declines linearly with the nu mber of users and ite m s .A collaborative filtering recommendati on algorith m based on user clustering was e mp l oyed t o s olve this p r oble m.U sers were clustered based on users πratings on ite m s,then the nearest neighbors of target user can be found in the user clusters most si m ilar t o the target user .Based on the algorith m,this paper p r oposed that the collaborative filtering algorith m should be divided int o t w o stages:t o compute the si m ilar coefficient and t o p r oduce recommendati on .The first stage was done in the off 2line phase and thus the computati on in the on 2line recommendati on phase was reduced and the s peed of on 2line recommendati on syste m was increased .And this paper als o i m p r oved the initial center point πs selecti on of K 2M eans clustering algorith m.

Key words:collaborative filtering;recommendati on syste m s;clustering

0　引言

个性化推荐系统被用来帮助用户在大量的信息中寻找感兴趣的内容,它体现的“个性化”服务目前越来越为大型网站、电子图书馆等众多领域所接受,成为它们的一个重要的功能

[1]

。在个性化推荐系统中,最近邻协同过滤技术是当前应

用最成功的技术。其基本思想是基于评分相似的最近邻居的评分数据向目标用户产生推荐。由于最近邻居对项目的评分与目标用户对该项目的评分非常相似,因此目标用户对未评分项目的评分可以通过最近邻居对该项目评分的加权平均值逼近[2]。

最近邻协同过滤推荐需要在整个用户空间上搜索目标用户的最近邻居,随着系统规模的扩大,用户和项目数量急剧增加,在整个用户空间上搜索目标用户的最近邻居比较耗时,难以满足推荐系统的实时性要求。针对上述问题,本文提出了基于用户聚类的协同过滤推荐算法,通过用户对项目评分的相似性对用户进行聚类,将具有相似兴趣的用户放入同一个

聚类中。当目标用户到达时,判断用户所属聚类,再在对应聚类中搜索目标用户的最近邻居,从而在尽量小的用户空间上搜索目标用户的最近邻居,最后根据最近邻居对项目的评分预测目标用户对项目的评分并产生推荐列表。对项目进行聚类比较耗时,但可以离线进行。协同过滤推荐需要对一个聚类内的所有用户进行相似系数的计算,在研究中发现,其所需计算量随用户数目的增长急剧增加,严重影响了在线推荐的效率,为此,本文提出将协同过滤分为类内相似系数计算和产生推荐两个阶段。把相似系数的计算放在离线数据处理部分,减少了在线推荐的计算量,从而提高了在线推荐的实时响应速度。

1　协同过滤技术

协同过滤技术通过分析历史数据,生成与当前用户行为兴趣最相近的用户集,将他们感兴趣的项作为当前用户的推荐结果,即t op 2N 推荐。基于协同过滤技术的推荐过程可分为3个阶段:数据表述;发现最近邻居;产生推荐数据集。

第27卷第5期

2007年5月

计算机应用

Computer App licati ons

Vol .27No .5May 2007

在一个典型的基于协同过滤技术的推荐系统中,输入数据通常可以表述为一个m×n的用户2项评估矩阵R,m是用户数,n是项数,r

ij

是第i个用户对第j项的评估数值。本文中, r ij表示用户对页面的兴趣度。

基于协同过滤技术的推荐系统的核心是为一个需要推荐服务的用户寻找其最相似的“最近邻居”集合,即:对一个用户u,要产生一个依相似度的大小排列的“邻居”集合N= {N1,N2,…,N t},u不属于N,从N1,到N t,si m(u,N t)从大到小排列。

度量用户相似性的方法主要包括如下两种:余弦相似性和相关相似性。

余弦相似性:设用户u1和用户u2在n维项目空间上的评分分别表示为向量u1,u2,则用户u1和用户u2之间的相似性si m(u1,u2)为:

si m(u1,u2)=cos(u1,u2)=

u1?u2

‖u1‖×‖u2‖

(1)

相关相似性:设经用户i和用户j共同评分的项目集合用I

ij

表示,则用户i和用户j之间的相似性si m(i,j)通过Pea rson 相关系数度量:

si m(i,j)=

∑

c∈I ij

(R i,c-R i)(R j,c-R j)

∑c∈I ij (R

i

,c-R

i

)2∑

c∈I ij

(R

j

,c-R

j

)2

　(2)

协同过滤技术在个性化推荐系统中获得了极大的成功,但随着系统规模的扩大,逐渐暴露出来一些缺点:评估矩阵数据稀疏、可扩展性差、推荐的可信度低等。

为了解决协同过滤技术存在的问题,学者提出了基于评分预测的协作过滤方法[3,5]、维数简化算法[2]等技术。但是这些算法都增加了在线处理的计算复杂度,不能很好的对用户做出响应。本文提出基于用户聚类的方法,通过用户对项目评分的相似性对用户进行聚类,将具有相似兴趣的用户放入同一类中,当目标用户到达时,首先判断用户所属聚类,再在这个聚类中搜索目标用户的最近邻居,从而在尽量少的用户空间上搜索目标用户的最近邻居。

2　基于用户聚类的协同过滤推荐系统

2.1　基于用户聚类的协同过滤推荐算法

K2M eans聚类算法,也被称为K2均值算法,是一种得到广泛使用的算法。

设k是k2M eans算法的输入参数,代表该算法在数据集上分割并计算后输出的数量。数据集是由n个数据点组成的,在初始化时,根据输入参数从n个数据点中找出k个聚类中心。通过K2M eans聚类算法对用户进行聚类的具体算法如下[6]:输入:聚类数目k和用户评分数据表

输出:k个聚类

方法:

1)从用户评分数据表中检索所有n个项目,记为集合I={i1,i2,…,i n};

2)从用户评分数据表中检索所有m个用户,记为集合U={u1,u2,…,u m};

3)从m个用户中选择访问量最高的k个用户作为初始的聚类中心,记为{W

1

,W2,…,W k},其中W j3=i l,j∈{1,2,

…,k},l∈{1,2,…,n},使每一个聚类c

j 与聚类中心相对应;

4)Repeat

For每一个输入向量i l,其中l∈{1,2,…,n}do

将i

l

分配给最近的聚类中心W

j

3所属的聚类c

j

3

For每一个聚类c j,其中j∈{1,2,…,k}do

将聚类中心更新为当前的c

j

中所有样本的质心点,

即w

j

=∑

i∈c j

i l/|c j|

计算误差函数:E=∑

k

j=1i∈c j

i l-w j2

5)Until E不再明显的改变或者聚类的成员不再变化。

传统的K2Means聚类算法的初始聚类中心是随机选取

的,在实验过程中发现,聚类后会出现较多孤立点。因为协同

过滤算法是在搜索最近邻居的基础上进行推荐的,无法对孤

立点进行个性化推荐。研究发现,访问量高的用户可以代表

一部分用户,这些用户作为聚类中心具有很好的代表性。因

此,本文选择访问量高的k个用户作为初始聚类中心,经实验

验证能较好的减少孤立点。

2.2　基于用户聚类的最近邻居查询和产生推荐

2.2.1　基于用户聚类的最近邻居查询

研究中发现,用户相似系数的计算所需计算量很大,严重

影响实时推荐的速度,由此会延长用户的等待时间,导致用户

对网站的忠诚度降低,甚至导致客户流失。

为了减少实时推荐的计算量,本文提出将用户相似度的

计算离线进行,并将其保存在数据库中。具体实现如下:建立

相似度计算表Si m i Coefficient,该表包括四个字段:

Si m ilar Coefficient,U ser1I d,U ser2I d,CenterI d,分别表示相似

度值、用户1标识、用户2标识和所属聚类标识,该表用来保

存用户之间的相似度数据。表结构如下:

CREATE T ABLE[dbo].[Si m i Coefficient](

[Si m ilar Coefficient][real]NULL,

[U ser1I D][bigint]NULL,

[U ser2I D][bigint]NULL,

[CenterI D][bigint]NULL)

当目标用户到达时,首先判断出他所属的聚类,然后在该

聚类中查询与目标用户的相似系数最大的若干个用户。

2.2.2　产生推荐

“最近邻居”产生后,就可以计算用户对任意项的兴趣度

和t op2N推荐集。设用户u和相应的已选项集I

u

,则其对任意

项t(t|Iu)的兴趣度如式(3)所示:

pred iction= u+

∑n

i=1

(corr

i

)×(ra ting

i

)- i

∑n

i=1

(corr

i

)

(3)

式(3)中 u是用户u对项的平均评估值,i是“最近邻居”

集的用户,corr

i

是用户u和用户i之间的Pea rson系数,ra ting

i

是用户i对项t的评估值, i是用户i对项的平均评估值。通过

上述方法预测用户对未浏览资源的兴趣度,然后选择预测兴

趣度最高的若干项推荐给用户。

2.3　推荐系统体系结构

在本文提出的推荐系统中,采用基于用户聚类的协同过

滤推荐技术向用户推荐可能感兴趣的资源,在网站上以链接

的形式发送给用户,该推荐系统的结构如图1所示,分为两个

部分:第一个是离线处理部分,主要完成W eb日志的预处理

以及对用户进行聚类和相似系数的计算;第二部分为在线推

荐部分,利用离线阶段的处理结果,通过公式(3)预测目标用

6221　　　　计算机应用2007年

户对未访问项的兴趣度,把兴趣度高的前N 项作为推荐结果推荐给用户

。

图1　个性化推荐系统体系结构

3　实验结果及其分析

3.1　数据集

本文采用河南科技大学校园文化网的日志数据,对数据进行预处理后从中选择16653条评分数据作为试验数据集,该数据集中包括1055个用户和1839个项目。

3.2　度量标准

本文采用统计精度度量方法中被广泛采用的平均绝对偏差MA E 作为推荐精度度量标准。平均绝对偏差MA E 通过计算预测的用户评分与实际的用户评分之间的偏差度量预测的准确性,MA E 越小,推荐质量越高。设预测的用户评分集合表示为{p 1,p 2,…,p n },对应的实际用户评分集合为{q 1,q 2,…,

q n },则平均绝对偏差MA E

定义为

[5]

:

MA E =

∑

N

i =1

p i -q i N

(5)

3.3　推荐精度试验

试验过程中,分别指定用户聚类的数目为30,40,目标用户的最近邻居个数从10增加到40,间隔为10,分别计算本文提出的算法与传统的协同过滤推荐算法的MA E,试验结果如图2和图3所示。

图2　聚类数目k =30

图3　聚类数目k =40

由图

2和图3可以看出,在聚类数目分别为30和40时,本

文提出的基于用户聚类的协同过滤推荐算法均具有最小的MA E 。由聚类的性质可知,目标用户的最近邻居大部分分布在与目标用户相似性最高的聚类中,因此不需要在整个用户空间上查询目标用户的最近邻居,而只需要在与目标用户相似性最高的聚类中就能查询到目标用户的大部分最近邻居。由于传统的协同过滤算法是在所有的用户空间上进行最近邻居

的搜索,而本文提出的算法是在聚类后的用户空间上进行搜索,因此推荐的精度大大提高。由此可知,与传统的最近邻协同过滤推荐算法比较,本文提出的算法可以显著提高推荐系统的推荐质量。

3.4　实时性效果检验

为了检验算法的实时性效果,将传统的在线计算相似系数与本文提出的离线计算相似系数作比较,分别进行在线推

荐,实验结果如图4所示。

图4　实时推荐所用时间比较

图4中用横轴表示聚类的数目k,用纵轴表示进行实时推荐所需耗费的时间t 。可以看出,采用离线计算相似系数后,实时推荐所需时间明显少于在线计算相似系数所需时间。特

别是当聚类的数目比较小的时候,两者的效率几乎相差一倍。这是因为聚类中的数目小的时候,聚类中的项目数相对较大,计算相似系数所需时间长,采用离线计算相似系数就可以大大提高推荐的效率。而随着聚类数目的增大,聚类中项目的平均数目会变小,此时需要在线计算相似系数的项目相对较少,离线和在线计算所需时间相差不大,但本文提出的算法效率仍优于改进前的算法执行效率。

4　结语

随着推荐系统规模越来越大,用户数目和项目数目急剧增加,推荐系统的实时性要求越来越难以满足,针对上述问题,本文提出了一种基于用户聚类的协同过滤算法,首先根据用户的兴趣度对用户进行离线聚类,然后离线计算用户间的

相似度,最后利用协同过滤算法在线进行推荐。实验表明,本文提出的算法可以显著提高推荐系统的在线响应速度,从而有效解决推荐系统面临的实时性问题。参考文献:

[1]　邓爱林,左子叶,朱扬勇.基于项目聚类的协同过滤推荐算法

[J ].小型微型计算机系统,2004,25(9):1665-1670.

[2]　赵亮,胡乃静,张守志.个性化推荐算法设计[J ].计算机研究与

发展,2002,39(8):986-991.

[3]　邓爱林,朱扬勇,施伯乐.基于项目评分预测的协同过滤推荐算

法[J ].软件学报,2003,14(9):1621-1628.

[4]　周军锋汤显郭景峰.一种优化的协同过滤推荐算法[J ].计算

机研究与发展,2004,41(10):1843-1847.

[5]　S ARWAR B,K ARYP I S G,K ONST AN J,et al .Ite m 2based collab 2

orative filtering recommendati on algorithm s [A ].Pr oceeding of the 10th internati onal World W ide W eb Conference [C ].Ne w York:AC M Press,2001.285-295.

[6]　毛国君.数据挖掘原理与算法[M ].北京:清华大学出版社,

2005.164-166.

7221第5期王辉等:个性化服务中基于用户聚类的协同过滤推荐　　　　

本文来源：https://www.bwwdw.com/article/0suq.html