- 1 -
G-RA：针对最大项相关性推荐问题的推荐算法
宝腾飞，陈恩红
中国科学技术大学计算机科学技术系，合肥 (230027)
摘 要：推荐系统作为一种新的获取信息的技术，自上个世纪 90年代发展至今，已经出现
了很多成熟的算法并成功的应用在商业上。本文阐述了一种新的问题场景：用户指定了一些
项，要求推荐系统推荐与之有最大相关性的项——称这个问题为最大项相关性推荐问题。本
文对这个问题借助于关系图挖掘（Proximity Graph Mining）技术进行了形式化的问题定义，
并提出了一个算法来解决这个问题。
关键词：推荐系统；图挖掘；Proximity Graph；最大相关性推荐问题
中图分类号：TP31
1 引言
网络信息每天都以指数级的速度增长，数据丰富带来的问题是如何在庞大的数据库中寻
找对用户有效的信息。搜索引擎是用户获取信息的必要手段之一，但仅仅是使用搜索引擎，
用户仍然难以快速找到有效的信息。因为当用户搜索一个关键字时，搜索引擎会返回数以万
条的信息，可这其中只有很少一部分才是用户所需要的。
推荐系统的做法同搜索引擎不同，推荐系统是主动对用户提供信息。它先收集用户的行
为数据，然后根据这些数据对用户推荐用户可能会感兴趣的信息。这些信息是搜索引擎可能
无法提供的。比如，在 网站里，当你浏览过几本书的信息或者购买了几本书后，
就会给你提供其他一些你可能会感兴趣的书。相比搜索引擎，推荐系统往往只
是在一个领域进行应用，比如只关注电影、CD 或者书籍领域，建立一个关于这个领域的数
据库，然后根据用户的特征对用户提供信息，一般对这些推荐的信息称之为项（Item）。
当前的推荐系统主要使用了两个性质来设计推荐算法[1]。第一条性质是，如果用户兴
趣相似，那么一个用户感兴趣的事物另一个用户也会感兴趣[2]；第二条性质，如果用户对
某事物感兴趣，那么与这个事物相似的事物用户也会感兴趣[3]。使用第一条性质来设计的
算法称为协同过滤算法，使用第二条性质来设计的算法称为基于内容的推荐算法。同时使用
这两条性质的算法称为混合推荐算法[4]。
搜索引擎的使用方式已经深入人心，如果以使用搜索引擎的方式使用推荐系统将会给推
荐系统带来更广泛的应用。搜索引擎针对用户输入的关键字会返回与这些关键字相关的网页
列表。把这种模式应用到推荐系统上，就是用户可以指定推荐要求，然后推荐系统返回与推
荐要求相关的推荐项。比如说，在一个电影推荐系统中2，用户使用自己已经看过的一些电
影要求系统推荐出与这些电影都相关的其他电影，同时这些推荐出来的电影可能会让用户感
兴趣。在这里，用户要求的形式是用户指定的电影，要求的内容是相关。我们称之为这个问
题最大项相关性推荐问题。
针对项相关性进行推荐的这种方式不同于传统的推荐方式。区别在于，传统的推荐算法
总是尽可能最大限度的使用用户的数据对用户进行建模，并与其他用户和项比较相似度，然
后进行推荐，这是用一种整体性的观点来看待这个问题，并不将用户的数据进行细化分割；
1
2
- 2 -
而对于用户这种针对一部分事物然后进行推荐的方式，会使得用户可以和推荐系统进行互
动，能更精确的要求推荐系统进行推荐，而不用推荐算法去建立各种复杂的模型去猜用户的
兴趣，实际上，用户的兴趣是一直在改变的，任何建模工作都只能部分有效。在传统的算法
中，推荐系统只是会推荐出用户“可能会需要”的项，而在最大相关性推荐问题场景中，我
们应该推荐出用户“真正需要”的项。
针对项相关性推荐是本文主要想解决的问题。从上面的分析中已经提到，解决这个问题
的入口点在于把握推荐系统内各项间的关系。项间存在着相互关系，反映在各种推荐系统中，
比如，书籍推荐系统3，各种书籍通过作者、参考文献、学科等相护关联；音乐推荐系统4，
各种 CD 通过音乐风格、作曲家、语言等相互关联。在获得各项间的关系后，如何使用这些
关系进行推荐也是一个问题。
本文将从图挖掘技术和现有的协同过滤方法来解决这个问题。本文的贡献主要有：
1) 使用图来建立推荐系统内各事物间的联系；
2) 提出最大项相关性推荐问题；
3) 针对项相关性推荐问题提出一个新的推荐算法——G-RA。
2 最大项相关性推荐问题
首先，我们说明普通推荐问题的形式定义，然后在此基础上提出最大项相关性推荐问题
的定义。
普通的推荐问题
推荐系统包含以下元素，首先是用户，用一个集合来表示：用户(User)集合 C
1 2{ , ,..., }mC c c c= ，m 为用户数目。
对于推荐系统内的项也使用一个集合来表示：项（Item）集合 S
1 2{ , ,..., }nS s s s= ，n 为项数目。
在反映用户对某个项的评价程度时，使用一个函数来表示用户的评价：评分函数 u
:u C S R× → ，这里 R 是一个完全有序的集合。
评分函数 u(c, s)反映了用户 c 对项 s 的评价程度，在推荐系统中，用户只能对很小一部
分项进行评分。因此除了用户评分过的项，推荐系统需要合成一种评分函数来对用户未评分
过的项进行评分。一般会把评分函数的值表示成为为一个用户-项评分矩阵。
经过推荐系统的合成处理后，用户的评分矩阵中原本值为空的地方将被推荐算法合成的
评分函数赋以新值。推荐项就是选取这些评分值最大的项。推荐算法的关键就在于如何合成
评分函数来对项进行评分。
推荐项：对于用户 c∈C，选择 s’∈S 作为对用户的推荐，其中 s’要满足：
s
, ' arg max ( , )c Sc C s u c s∈∀ ∈ =
一般来说，推荐系统并不是只推荐一个项给用户，而是推荐评分值在前 N 位的推荐项，
也就是 Top-N 推荐项。
最大项相关性推荐问题
3
4
- 3 -
现在我们定义新的问题——最大项相关性推荐问题：用户指定一些推荐系统内的项，以
此作为输入，要求推荐系统针对这些项推荐与之有最大相关性的项集。下面我们给出的一个
形式化定义：
定义：最大项相关性推荐问题
对于用户 c∈C，以及用户指定的项集 Sc，选取项集 Sc’使得：
（1）Sc’中节点使得 Sc 内节点间有最大的项相关性；
（2）Sc’中的项评分值不低于阀值δ。
第二个要求是为了剔除一些不好的项。在以上定义中，我们必须先说明项相关性，并要有一
种能评价项相关性的机制，在这里，我们直接使用图挖掘领域中关系图挖掘（Proximity Graph
Mining）的评测方法[5]，下面我们简单介绍一下：
使用一个图 G(V, E)来表示项以及项之间的关系，其中图 G 中的节点集 V 表示推荐系统
中的项集，而边集 E 表示项之间的直接关系。关系的来源可以是项之间本来就存在的关系，
比如两部电影如果是同一个导演或者有相同的主角，那么就可以在这两个电影之间建立一条
边。
我们将项相关性指定为节点在图中的关系。那么如何表示这种关系呢？ C. Faloutsos [6]
提出使用连通子图表示节点间的关系，后来 Y. Koren[5 又使用随机游走的理论[7]完善了这
个问题。简单的说，就是多个节点间的关系用一个与它们联系最紧密的其他节点组成一个连
通子图来表示。
为了定量描述这种关系，Y. Koren[5]提出了以下公式来衡量节点间关系的强度：
1
1
1
Pr ( )
deg
i i
i
r
v v
i v
w
ob R +
−
=
=∏ （1）
1
( ) deg Pr ( )vWgt R ob R= ⋅ （2）
Pr ( , ) ( )
R
oximity s t Wgt R
∈
= ∑
�
（3）
公式中符号意义如下，R 指的是一条简单路径，即路径中不包括重复节点，路径中的节
点为 s=v1,v2,…,vi,vi+1,…,vr=t，公式（1）表示的是随机游走者从 s 到 t 经过路径 R 的概率[7]；
wvi,vi+1 为节点 vi,vi+1 间边的权重，degvi定义为节点 vi 出边的所有边权之和；公式（2）Wgt(R)
表示的是路径 R 的权重；公式（3）中� 为节点 s、t 间的路径集。Proximity(s, t)表示节点 s、
t 间的关系强度大小，即路径集中所有路径的权重之和。在实际计算 Proximity(s, t)时，并不
需要将节点 s、t 间的所有路径都提取出来然后计算，只要计算其中前 k 条最短路径即可，
因为路径越长，Prob(R)的值越小，对结果影响越小。
因此，在最大项相关性推荐问题中，节点间最大相关性，就是使得项集 Sc 中任意节点
间的 Proximity 值最大，这需要一个好的连通图，我们称这个连通图为项强关系图（Item
Proximity Graph）。
3 G-RA：基于图结构的推荐算法
下面我们给出解决最大项相关性推荐问题的算法。因为我们的算法主要使用了图
（Graph）结构，也即是一种基于图结构的推荐算法(Recommendation Algorithm)。我们简单
的将其称之为 G-RA。
我们的算法分为三个部分：（1）创建项关系图；（2）从项关系图中抽取连通子图；
- 4 -
（3）过滤。下面我们分别进行阐述。
创建项关系图 (Item Relation Graph Construction)
根据项之间的关联方式创建关系图有很多种方法，但对于推荐系统所使用的数据，又
有一些特殊性。我们提出了一种基于命中（Hit）概念的创建算法,这种方法具有很强的灵活
性，并且对于新加入的项，也能方便的整合到项关系图中。
在创建项关系图时，我们使用向量来表示项：
,1 ,2 ,{ , ,..., }i i i i ts p p p= （4）
上式中，pi,j, 1≤j≤t 为项 si的第 i 个属性。我们观察到，对于推荐系统中大多数推荐项
的表示方法中，以关键词的表示方法居多[3]，尤其是涉及到文本类的推荐系统中。不失一
般性，我们将这种方法扩展，但不规定其关键词个数（但有一个最大个数上限 C）。我们将
属性 pi,j,表示为一个变长向量：
, 1 2{ , ,..., ,...}i j hp k k k= (5)
其中 kh称为一个字（word），代表属性 pi,j,所拥有的属性值。
对这种表示方法，我们现在给出一个例子：在一个电影推荐系统中，每个项（电影），
都有很多属性(p)，比如导演、编剧、演员、电影风格等。而这些属性中，每个属性值都可
能不是单一属性值(k)，比如一个电影可以有两个导演，多个演员，同时具有几种电影风格
等。
给出以上的项定义后，我们现在说明怎样建立项关系图。首先给出命中（HIT）的概念：
HITs(sx, sy, Pj) ：对两个项的属性 sx, sy的第 j 个属性即 pxj, pyj 进行比较，当 pxj, pyj 中有
相同值时，我们称为命中一次，而最终的所有命中次数为命中值。
下面是我们的项关系图建立算法：
算法 创建项关系图 (Item Relation Graph Construction)
输入：s1, s2… sn，项属性向量；priority[t]，项属性优先权数组；
输出：Matrix[n][n], 项关系图；
1 Matrix[n][n] = {-threshold}
2 for item sx from s1 to sn-1
3 for item sy from s2 to sn
4 for property pj from p1 to pt
5 Matrix[x][y] += Hits(sx, sy, pj)×priority[pj]
6 endfor
7 endfor
8 endfor
在算法中出现的 priority 是因为项的属性优先权是不同的，比如对于电影项，作为导演
的那一个属性的优先权将会高于作为电影语言的属性的优先权。因此得到命中值后还要根据
优先权作调整。
算法首先设定一个阀值 threshold，只有当命中值超过阀值时才会在项间建立边。最终得
到的是一个表示图的邻接矩阵，当 Matrix[x][y]>0 时，项 sx, sy 之间会建立一条边，权值为
Matrix[x][y]。HITs(sx, sy, Pj)的时间复杂度为 O(C2)，C 为项属性具有的最多值的个数。整个
建立项关系图算法的时间复杂度为 O(tn2C2)，考虑到在建立这个项关系图后，新加入节点只
要对所有节点再计算一次命中值即可（时间复杂度为 O(tnC2)，这样的效率是可以接受的。
- 5 -
从项关系图中抽取项强关系图 (Extracting Item Proximity Graph From
Item Relation Graph)
在[5]中，求项强关系图转换为求 k 条最短路径的问题。但是，图论中的边长和我们建
立的项关系图的边权是不同的概念，图论中的最短路径，是沿着边长最小的边并经过最少的
节点个数得到的。而在求项强关系图的节点间路径时，由公式（2）知，是沿着边权最高的
边经过最少的节点个数得到。因此必须要在边权和边长间有一个转换，最简单的是使用倒数：
, ,1 /i j i jl w= (6)
然后再求所有输入项所代表的节点间的 k 条最短路径，关于求 k 条最短路径的研究有
很多[8] [9]，最好的时间复杂度是 O(K(|E|+|V|log|V|))[10]。
在求得所有节点间的 k 条最短路径后，还需要把这些路径转换成一个连通图。在转换
连通图时，我们需要评判怎样的连通图才是最具代表性的项强关系图，可以使用以下公式：
1 2Pr ( , ,..., ) / | |k koximity v v v V
α β (7)
|Vk|为项强关系图的节点个数。参数α和β分别用来控制 Proximity 和节点个数的重要性。
使用公式（7）,我们需要把所有的路径转换成一个连通图。这是一个近似于背包问题的
NP-Hard 问题，Y. Koren[5]中提出了一个 PathMerger 的算法。算法的时间复杂度是 2k。
过滤 (Filter)
在得到项强度图后，我们还需要过滤掉那些可能对用户无效的项。我们采用基于用户
相似度的协同过滤方法。
首先使用 Pearson Correlation 相关系数（correlation）来计算用户相似度：
( )
( ) ( )
, ,
2 2
, ,
( )
( , )
u s u v s vs
u s u v s us a
R R R R
sim u v
R R R R
∈Τ
∈Τ ∈Τ
− −=
− −
∑
∑ ∑
（8）
公式中 Ru,s为用户 u 对项 s 的实际打分，Τ为用户 u、v 共同打分项的交集。
根据公式（8）计算出与被推荐用户 u 具有最高相似度的最近邻集合。然后使用合成公
式计算被推荐项的评分值：
� ( )�
�
,
,
( , )
( , )
v s vv C
u s u
v C
R R sim u v
R R
sim u v
∈
∈
−= + ∑ ∑ （9）
我们对项强关系图中的所有项进行评分合成，然后过滤掉低于阀值的项，最终得到所
需要的推荐项。
4 实验
我们选取的是来自 MovieLens 的数据集。MovieLens5是个进行电影推荐的网站，
GroupLens6小组从中整理出了适用于各种推荐场景的一个数据集。在我们使用的数据集中，
总共包含 943 个用户（M=943）对 1，682 部电影（N=1，682）的大约 100，000 个评分。
在实验中，我们使用了 7 个属性，并赋优先权如下：
5
6
- 6 -
表格 1 属性优先权值表
国家(Country)、语言(Language) 1
风格(Genre) 2
情节关键字(Plot_keywords) 3
演员(Cast) 4
导演(Director)、编剧(Writer) 5
阈值设为 50%，最后我们得到一个 112,074 条边的无向图。显然这是一个稀疏图。
下面我们给出一个例子：
我们选择用户 C[46], 他对 27 个项进行了评分，我们找到他评分最高的两部电影作为最
大项相关性推荐问题的输入，这两个项分别是：S[313]和 S[1024]，其中 S[313]是《泰坦尼
克号》(Titanic)，S[1024]为一部由小说改编的电影《达洛卫夫人》（Mrs. Dalloway），这两
项都被 C[46]给了最高评分。
使用我们的算法，设置 k=100,α=10,β=，我们得到的项强关系图包含 11 个节点（包
括输入项）。经过过滤后，得到的推荐项为：
1) S[22]：《勇敢的心》（Brace Heart），第 68 届奥斯卡奖。
2) S[275]：《理智与情感》(Sense and Sensibility)，IMDB7评分 。
3) S[283]：《艾玛》(Emma)，IMDB 评分 。
4) S[517]：《曼哈顿》(Manhattan), IMDB 评分 。
5) S[311]：《三颗翼动的心》(Wings of the Dove, The)，IMDB 评分 。
经过分析，我们得知这些项与输入项都存在着关联，比如 S[1024]与 S[283]都属于小说
改编、描述人物的电影。S[313]与 S[22]都为奥斯卡奖，且都取材于历史事件。并且，我们
通过在 IMDB 网站上的查询，得知这些项的评分还都不差。我们认为这样的推荐能满足用
户的要求。
5 总结和下一步工作
传统推荐算法的出发点建立在如何模拟用户更真实的兴趣，然后从相似用户或者相似
项的角度来进行推荐。在本文中，受关系图挖掘(Proximity Graph Mining)领域[5][6]的启发，
我们分析了一个新的问题场景——最大项相关性推荐问题，然后对这个问题给出了在推荐系
统上的定义，并提出了一个解决方法——G-RA，实验表明算法是有效的。
我们认为新型推荐算法应该更关注用户的需求，并在交互性上有足够好的实时性能。
在解决最大项相关性推荐问题时，当用户提出推荐要求后，系统应该及时的将结果计算出来
并反馈给用户。因此，在下一步工作中，我们将把算法分为离线和在线两个部分，将可以离
线计算的部分分离出来，幸运的是，这方面已经有很多相关工作在开展了。比如在推荐算法
领域引入聚类技术[11]，在图挖掘领域引入索引技术[12]等。
7
- 7 -
参考文献
[1] G. Adomavicus, A. Tuzhilin. Toward the Next Generation of Recommender Systems: A Survey of the
State-of-the-Art and Possible Extensions . IEEE Transactions on Knowledge and Data Engineering, Vol. 17,
No. 6, June 2005, pages 734-749.
[2] R, P., N. lacovou, et al. GroupLens: An Open Architecture for Collaborative Filtering of Netnews.
Proceedings of ACM 1994 Conference on Computer Supported Cooperative Work, ACM: pages 175-186.
[3] S. Debnath, N. Ganguly, P. Mitra. Feature Weighting in Content Based Recommendation System Using
social network analysis . WWW /Poster Paper, pages 1041-1042, April 2008.
[4] Balabanovic, M. and Y. Shoham. Fab: content-based, collaborative recommendation. Communications of the
ACM 40(3): pages 66-72, 1997.
[5] Y. Koren, S. C. North, and C. Volinsky. Measuring and extracting proximity in networks. In KDD '06, pages
245-255, 2006.
[6] C. Faloutsos, K. S. McCurley, and A. Tomkins. Fast discovery of connection subgraphs. In KDD'04, pages
118-127, 2004.
[7] . Doyly and J. L. Snell. Random Walks and Electrical Networks. The Mathematical Association of
America, 1984.
[8] A. Brander and M. Sinclair. A comparative study of K-shortest path algorithms. In Proc. of 11th UK
Performance Enginerring Workshop, pages 370-379, 1995.
[9] E. Martins and M. Pascoal. A new implementation of Yen's ranking loopless paths algorithm. Submited for
publication, Universidade de Coimbra, Portugal, 2005.
[10] E. Hadjiconstantinou and N. Christofides. An efficient implementation of an algorithm for finding k shortest
simple paths. Networks, 34:88-101, 1999.
[11] A. M. Rashid, S. K. Lam, et al. ClustKNN: A Highly Scalable Hybrid Model-& Memory-Based CF Algorithm.
In WebKDD’2006.
[12] M. Rattigan, M. Maier, et al. Using structure indices for efficient approximation of network properties. In
KDD' 2006。
G-RA: An algorithm for maximum item relationship
recommendation problem
Bao Tengfei, Chen Enhong
Department of Computer Science and Technology, University of Science and Technology of
China, Hefei, PRC, (230027)
Abstract
Recommendation system has become a new way to retrieve information since 1990s, and in that have
many mature algorithms applied to business. In this paper, We introduces a new issue of scene that:
users specify a number of items, and require the recommendation system to recommend items which
have maximum item relationship with the items that user has specified - we call it maximum item
relationship recommendation problem. In this paper, we define this problem formally referred through
Proximity Graph Mining, and propose an algorithm to solve it.
Keywords: recommendation system; graph mining; proximity graph; maximum item relationship
recommendation problem
作者简介：
宝腾飞（1985—），男，硕士研究生，主要研究方向为数据挖掘，图挖掘，推荐系统；
陈恩红（1968—），男，博士，教授，博导，IEEE 高级会员（Senior Member），中国科技
大学多媒体计算与通信教育部-微软重点实验室副主任,中国人工智能学会知识工程专委会、
机器学习专委会委员，中国计算机学会人工智能与模式识别专委会委员，担任 20 余个国际
学术会议的程序委员或主席。主要研究方向：语义 Web、 机器学习与数据挖掘、网络信息
处理、约束满足问题 。
