-1-
个性化搜索引擎协同过滤研究1
陈 华，李仁发，刘钰峰，练琪
湖南大学计算机与通信学院，长沙（410082）
摘 要：将个性化引入搜索引擎出现了一些新问题，本文在利用矩阵相关技术以及扩大影响
的基础上，提出了一种高效的推荐算法，将用户潜在感兴趣的资源推荐给用户，并较好地解
决了以上存在的稀疏性，精确性，扩展性问题等，实验表明，该算法相对于协作过滤而言，
可有效显著提高个性化系统的推荐质量．
关键词：推荐系统；协同过滤；单值分解；相似性
中图分类号：
1. 引言
以Google,baidu代表的搜索引擎已为人们熟知。具有基于关键字，通用性等特点。而对
于不同兴趣，背景的用户如何提供更高效率更专业的服务，使得个性化搜索引擎技术成为目
前的研究热点之一。
个性化搜索引擎就是针对用户的不同需求在查询关键字相同时，根据用户背景和其用户
群喜好主动为用户推荐满足用户潜在兴趣的资源。如果用户1喜欢去关于探险的地方去旅游，
而用户2则喜欢去浪漫的地方旅游，则两者的需求不同，而现有的搜索引擎在输入相同关键
字“旅游”时，返回的结果是没有区别的，而我们的研究则是针对需求的不同，为用户提供不
同的更专业的服务。
目前存在许多不同的推荐系统，个性化搜索引擎使用的最主要的技术是推荐技术，根据
所采用的技术不同，分别有基于规则的，基于项目的，基于用户的推荐等等，但是最主要的
还是基于用户的推荐。
2. 相关工作
现有的推荐大都采用基于项目推荐、基于用户推荐。项目推荐简单、有效，但是只能发
现和用户已有兴趣相似的信息，用户推荐可以为用户发现新的潜在感兴趣的资源，但是具有
稀疏性和扩展性等缺点。本文是在考虑如何利用现有技术，解决稀疏性和扩展性而展开的。
用户与资源描述
用户与资源的关系[1]，建模如下，用 m*n 阶矩阵表示.
如表 1 所示：m 个用户，n 个项目，Ri,j代表用户 i 对项目 j 的评分。
表 1 用户项目评分表
Item
User item1 … itemj … itemn
User1 R1,1 … R1,j … R1,n
… … … …… … …
Useri Ri,1 Ri,j Ri,n
… … … …… … …
Userm Rm,1 … Rm,j … Rm,n
1本课题得到教育部科学技术研究重点项目（项目编号：108168）的资助。
-2-
推荐算法
信息过滤技术可分为基于规则过滤，基于内容过滤的技术(content-based filtering)和协作
过滤技术(collaborative filtering).
（1）基于规则过滤
规则其实是用一些 If-else 语句，可以利用用户静态属性或者动态信息来建立。可以由
用户定制规则,也可以利用关联规则挖掘规则[2]，根据当前用户感兴趣的内容,通过规则推出
用户还没有阅读过的感兴趣的内容。
规则推荐依赖规则的质量和数量,基于规则的缺点是随着规则的数量增多,系统将变得难
以管理。
（2）基于内容过滤
基于内容的推荐[3]，基本思想是根据用户以前的兴趣来推测用户以后的兴趣，基于内容
过滤的系统其优点是简单、有效,缺点是难以区分资源内容的品质和风格,而且不能为用户发
现新的感兴趣的资源,只能发现和用户已有兴趣相似的资源.
首先找到对两个项目共同评分的用户，把用户评分形成向量，然后利用相似度公式进行
计算。然后，系统就可以根据用户先前的兴趣来预测用户对目标项目的兴趣程度了，可以用
下式(1)来计算。
∑
∑
=
== n
j
n
j
ju
ju
jisim
Rjisim
P
1
1
,
,
),(
*),(
(1)
其中 Ru,j是用户 u 对资源项目 j 的评分；sim(i,j)是项目 i 和 j 的相似度。
（3）协作过滤
基于协同的推荐(CF) [4]，又称为合作过滤或社会过滤(Social Filtering)。协作推荐实现的
基本思想是找到目标用户的若干最近邻居(与目标用户有相似兴趣的用户)，然后根据最近邻
居对目标项目的评分，产生推荐。这种推荐方法可以为用户发现新的感兴趣的资源。
基于协作过滤系统的优点是能为用户发现新的感兴趣的信息，缺点是存在两个很难解决
的问题,一个是稀疏性,亦即在系统使用初期,由于系统资源还未获得足够多的评价,系统很难
利用这些评价来发现相似的用户.另一个是可扩展性,亦即随着系统用户和资源的增多,系统
的性能会越来越低.
计算目标用户对未评分项目的评分时，根据最近邻居对项目的评分产生推荐。
计算用户 u 对项目 j 的评分：
∑
∑
=
== n
m
n
m
jm
ju
musim
Rmusim
P
1
1
,
,
),(
*),(
(2)
其中 Rm,i 是用户 m 对项目 i 的评分； sim(u,m)是用户 u 和 m 的相似度。
计算相似用户
度量用户之间的兴趣相似性实际上就是计算向量之间的相似性，一般有 3 种方法[1]：余
弦相似性、相关相似性和修正的余弦相似性。
-3-
余弦相似性：把用户评分看作是 n 维项目空间上的向量。如果用户对某个项目没有评分，
则将此评分假设为 0。通过计算两个向量之间的夹角余弦来度量两个用户之间的相似性。计
算公式如式(3)所示：
∑ ∑
∑
= =
==
n
k
n
k
kjki
n
k
kjki
RR
RR
jisim
1 1
2
,
2
,
1
,,
*
*
),(
(3)
其中，Ri,k，Rj,k 是用户 i，j 对项目 k 的评分。
相关相似性：通过 Peason 相关系数来度量两个用户的相似性。计算时，首先找到两个
用户共同评分过的项目集，然后计算这两个向量的相关系数。计算公式如式(4)所示：
∑∑
∑
∈∈
∈
−−
−−
=
jiji
ji
Ic jciIc ici
Ic jcjici
RRRR
RRRR
jisim
,,
,
2
,
2
,
,,
)(*)(
))((
),(
(4)
其中 Ii,j是用户 i 和 j 共同评分过的项目集；Ri,c 是用户 i 对项目 c 的评分； iR 是用户 i
对资源的平均评分。
修正的余弦相似性：在余弦相似性中没有考虑不同用户的评分尺度问题。修正的余弦相
似性通过减去项目的平均评分来弥补这种不足，计算公式如式(5)所示：
∑∑
∑
∈∈
∈
−−
−−
=
jiji
ji
Ic cciIc cci
Ic ccjcci
RRRR
RRRR
jisim
,,
,
2
,
2
,
,,
)(*)(
))((
),(
(5)
其中， cR 是项目 c 的平均评分
3. 推荐算法优化
在现有的搜索引擎技术基础上，结合当前个性化服务思想，考虑到推荐系统的扩展性[5]
和稀疏性[6]等问题，从影响集的概念中出发，采用 svd，kNN 和 RkNN 等技术，提出一种基
于用户过滤的推荐算法，提高推荐系统的推荐质量。把用户潜在感兴趣的资源推荐给用户，
以达到对于不同需求的用户提供不同的高效的专业服务效果。
Svd 矩阵简化
推荐技术在个性化系统中已经取得了巨大的成功，但同时它的一些技术包括协同过滤的
缺点暴露无疑，面临有稀疏性，扩展性等问题，初步可以使用 SVD 处理。
SVD，又叫单值分解[7][8]，一种矩阵分解技术，它可将一个 m×n 的矩阵 R 分解为 3 个矩
阵．
R0=T0S0D0，S0= diag( 1α , ⋯, rα )，
其中， T0和 D0分别是 m×r 和 r×n 的正交矩阵，r 是矩阵 R0的秩．S0是一个 r×r 的对角
矩阵， 1α ≥ ⋯ ≥ rα ≥0，称为单值(singular value)．
算法 1．基于单值分解的的推荐算法
输人:矩阵 R0
输出:相关矩阵 T，S，D
-4-
(1)将矩阵 R 中评估值为 0 的项用相关列的平均值 ri (相关列的项平均评估值)代替；
(2)用 rij-ri 代替原来的 rij．得到矩阵 R1；R1经过单值分解，得到 T1，S1，D1；
(3)将 S1简化，将对角线上小于 1 的值用 0 代替，将相应的全为 0 的列或行删除，得到
S，即维数为 s 的对角矩阵；
(4)根据 S，简化 T1，D1，得到 T，D，则有 R=TSD，且 R≈R0；
(5)计算 S 的平方根得到 2
1
S ；计算两个相关矩阵 2
1
TS ， DS 2
1
。
采用向量空间方法计算相似性，这里分析的对象是经过 SVD 分解后的 m×s 矩阵 2
1
TS ，
它描述的是用户在 k 维空间中的关系，因为经过单值分解，大大降低了它的数据稀疏性，可
以产生比较精确的最近邻居集和相应的 top-N 推荐集．基于维数简化的算法 1 较好地解决
了数据稀疏性的问题.
kNN 与 RkNN
评分矩阵经过矩阵简化以后，寻找相似用户或者相似项目应该来说更加简单精确，但是
如果原来矩阵是稀疏的，即相似用户或者相似项目本来就很少，在经过矩阵简化以后，相似
用户就会变得更少，对于这样的情况，我们引入 kNN 与 RkNN，增加用户的影响集，来为
其进行预测评分。
最近邻及其检索算法是计算机科学的主要核心问题之一。近年来，k-最近邻的逆问题逐
渐得到人们广泛的关注．所谓逆 k 最近邻[9][10]，就是在给定的数据集 S 中，查询特定点 q 被
其它哪些点视为最近邻，并从中选取有重要影响的点，可以通过 kNN 算法的逆算法
RkNN(reverse k nearest neighbor)算法来解决。
给定数据集 S， D(p,q)表示 p，q 两点间的距离．
RkNN(q)={ q∈kNN(p) | p∈S }．
值得注意的是，kNN 和 RkNN 不是对称的，即 p∈kNN(q)不能推出 q∈RkNN(p)。
算法 2．基于 kNN 和 RkNN 的协作过滤推荐算法．
输入:用户项目评分矩阵 A(m，n)，用户 i，预测项目 j；
输出:用户 i 在项目 j 上的预测评分
(1)在 A(m，n)中计算用户间的相似度，存入距离矩阵；
(2)对于每个用户 i∈I，根据距离矩阵，找到 i 的最近邻序列，并按相似度从高到低进行
排序，得到的最近邻-相似性列表 TkNN 并保存；
(3)扫描 TRkNN，为每个项目 i∈I，寻求逆最近邻序列，同样按相似度从高到低进行排
序，得到逆最近邻-相似性列表并保存．
(4)在最近邻-相似性列表 TkNN 中找到用户 i 所对应的行，顺序取出前 k 个项{i1，i2， ik}；
(5)在逆最近邻-相似性列表 TRkNN 中找到用户 i 所对应的行中，顺序取出前 k’个项；
(6)根据推荐产生式（2），选择适当的参数值，计算用户 i 在项目 j 上的预测评分，并输
出．
最近邻一相似性列表和逆最近邻-相似性列表只需要定期离线计算一次并保留下来即
可，并不影响在线推荐产生的速度．
预测评分
-5-
考虑到用户给资源打分时，用户具有苛刻程度不等的情况，将具体预测评分修改为如下
公式(6)：
∑
∑
=
== n
i
n
i i
ji
uju
iusim
iusim
R
R
RP
1
1
,
,
),(
),(*)(
* (6)
iR 是用户 i 对其浏览过的项目平均评分， uR 是用户 u 对项目的平均评分， ),( iusim 是
用户 u 和用户 i 的相似度。
'
, juP 是通过用户 U 的 KNN 来计算的评分. 如公式(7)
∑
∑
∈
∈
= n
ukNNi
ukNNi
i
ji
uju
iusim
iusim
R
R
RP
)(
)(
,
'
,
),(
),(*)(
*
（7）
''
, juP 是通过用户 U 的 RKNN 来计算的评分。如公式(8)
∑
∑
∈
∈= n
uRkNNi
n
uRkNNi i
ji
uju
iusim
iusim
R
R
RP
)(
)(
,
''
,
),(
),(*)(
*
（8）
在算法 2 中，综合 kNN 和 RkNN 的评分，则有按照推荐项目的评分结合思想，则用户
U 对项目 j 最终预测评分,如公式
''
,
'
,, )1( jujuju PPP αα −+= (9)
其中α 是 kNN 和 RkNN 分别控制影响最终评分的影响因子。
基于 svd 影响集的协作过滤推荐算法
利用矩阵简化,扩大 kNN 或 RkNN 影响集等技术的基础上 ，解决矩阵稀疏和相似用户
难以确定等问题。
算法 3.基于 svd 影响集的协作过滤推荐算法．
输入:用户-项目评分矩阵 R(m，n)；
输出:推荐给用户的项目序列
(1)将矩阵 R 单值分解，得到简化 T，S，D；
(2) 计算用户相关矩阵 2
1
TS （m,k）,记为 A；
(3) 在 A(m，n)中计算用户间相似度，并存入距离矩阵；
(4) 对于用户 i∈I，找到 i 的 TkNN 和 TRkNN 并保存；
(5) 在列表 TkNN 中找到用户 i 所对应的行，顺序取出前 k 个项{i1，i2， ik}，以及和
TRkNN 的前 k’个项；
(6) 分别根据推荐产生式(7)(8)(9)并选取适当参数，计算用户 i 对项目 j 上的预测评分，
-6-
并计算产生用户的项目推荐序列；
4. 实验结果和分析
我们实验数据采用 MovieLens Data Sets，GroupLens 是一个在 Minnesota 大学计算机科
学与工程系的研究实验室。其研究领域包括：推荐系统，在线社区，移动技术，数字图书馆，
当地地理信息系统。MovieLens 是一个研究推荐系统，我们使用的具体实验的数据是 6040
个用户对 3900 个电影的 1 百万的评价记录的原始数据，这个是极其稀疏的。
推荐质量的评价标准采用平均绝对偏差 MAE[11][12]，如公式(10),值越小，推荐效果越
好。 ip 是评测分数， iq 用户实际评分.
N
qp ii
N
i
||
MAE 1
−
=
∑
=
(10)
本文采用修正的余弦相似性。这里 k 去 200，α 取 ，进行实验：
图 1.本文算法与协同算法的 MAE 比较
如图 1 所示，基于 svd 和影响集的协作过滤算法比最近邻集合的协作过滤算法取得了较
低的 MAE，取得了更好的推荐效果．本实验证明，基于 svd 和影响集的协作过滤算法，不
但能够解决稀疏性和扩展性，而且能够提高推荐的准确率．使用 svd 处理稀疏矩阵，解决好
了稀疏性问题，处理后的矩阵 S 的秩 r<<n，即对于扩展性问题同样有效；但是如果原来矩
阵是稀疏的，即相似用户或者相似项目本来就很少，在经过矩阵简化以后，相似用户就会变
得更少，而在扩大 kNN 或 RkNN 后的影响集，使推荐的结果更加精确，即提高了精确性。
图 2.不同α 值的 MAE 比较
算法 3 中存在影响因子α ，邻居集 k 的动态参数， 如图 1 所示，在 k>200 的时候，
MAE 基本没有变化，k 取 200。如图 2 所示，当α 取值 时，推荐效果达到最优。
0 1
α
MAE
1
20 40 60 80 100 120 140 160 180 200
k 值
MAE
协同
本文
-7-
5. 结论和未来工作
个性化系统越来越多的应用在各个领域中，随之原有的推荐算法就会暴露出一些问题，
本文从矩阵的先缩后放角度较好地解决了稀疏性扩展性问题。然而将个性化引入搜索引擎，
将出现需要维护一个庞大的用户资源矩阵，而且也是要考虑计算时间成本；本文仅考虑了协
同过滤，但是基于项目过滤同样也有它的优点。下一步工作就是考虑如何处理好一个庞大的
矩阵，以及如何利用基于项目过滤和协同过滤两者优点共同提高推荐效果。
-8-
参考文献
[1] 曾春, 邢春晓, 周立柱.个性化服务技术综述[J] .软件学报, 2002, 13(10):1953-1955.
[2] Adomavicius, G., Tuzhilin, A. User profiling in personalization applications through rule discovery and
validation[C]. In: Lee, D.,Schkolnick, M., Provost, F., et al., eds. Proceedings of the 5th International
Conference on Data Mining and Knowledge York: ACM Press, 1999:377-381.
[3] Jin X，Zhou Y，M obasher B．A unified approach to personalization based on probabilistic latent semantic
models of Web usage and content[J]． In：Proc．of the AAAI 2004 Workshop on Semantic Web
Personalization(SWP 2004)．San Jose：AAAI，2004:26-34．
[4] Herlocker J,Konstan J,Riedl collaborative filtering recommendations[C].In：Proc．of the ACM
2000 Conf．on Computer Supported Cooperative Work．2000:241-250.
[5] Sarwar B，Karypis G，Konstan J，Riedl J．Application of dimensionality reduction in recommender systems-
A case study[C]．In：Proc．of the WebKDD 2000 Workshop at the ACM-SIGKDD Knowledge
Discovery in Databases (KDD 2000).2000.
[6] Deng AL,Zhu YY,Shi BL．A collaborative filtering recommendation algorithm based on item rating
prediction[J]．Journ al of Software，2003，l4(9)：1621-1628.
[7] Deerwester S by Latent Semantic Analysis[J].New York;John Wiley Press,1990
[8] 赵亮,胡乃静,张守志.个性化推荐算法设计[J].计算机研究与发展, 2002, 39(8): 988.
[9] Korn F,M uthukrishnan S．Influence sets based on reverse nearest neighbor queries．In：Naughton JF，
Bernstein PA，eds[C]．Proc．of the ACM SIGMOD Int’l Conf．on Management of Data．New York：ACM
Press，2000．201-2l2．
[10] 陈健,印鉴,基于影响集的协作过滤推荐算法[J]. 软件学报，2007, 13(7): 1685—1694.
[11] Herlocker J,Konstan J,Terveen L,Riedl J．Evaluating collaborative filtering recommender systems[J]．ACM
Trans．on Inform Systems(TOIS)，2004:22(1)：5-53．
[12] B Sarwar , G Karypis , J Konstan , et al1 Item-based collaborative filtering recommendation algorithms[C].In :
Proc of the 10th Int’l World Wide Web Conf. New York : ACM Press , -295.
Personalized Search Engine Research on Collaborative
Filtering
Chen Hua, LI Ren-fa, LiuYu-feng,LianQi
School of Computer and Communication, Hunan University, Changsha (410082)
Abstract
The propose of personalized search engine, some new questions have emerged. A recommendation
algorithm,proposed in this article bases of matrix-related technology and expanding its influence, meet
user's potential interest, and can solve these problems such as sparsity, accuracy ,scalability. The
experiment show that the algorithm,comparing with collaborative filtering, can effectively improve
quality of the recommend system.
Keywords: Recommend systems; collaborative filtering; single value decomposition; the similarity
作者简介：
陈华，男，1981 年生，硕士，主要研究领域为信息网络；
李仁发，男，1957 年生，教授、博士生导师，主要研究领域为无线网络、嵌入式计算
和嵌入式软件、数字媒体；
刘钰峰男，1974 年生，博士，主要研究领域为分布式实时操作系统、信息网络；
练琪，女，1982 年生，硕士，主要研究领域为计算机网络.
