基于关联规则与标签的好友推荐算法＊

胡文江，胡大伟，高永兵，郝 斌

（内蒙古科技大学信息工程学院，内蒙古 包头 014010）

1 引言

在当前的网络社会，大多数用户的朋友来自那些在现实生活中的社会关系，如学校、队友、同事等[1]。但事实上，用户往往想通过社交网络认识一些新朋友。对于一个用户，特别是新加入的用户，添加哪些用户为自己的好友成了一个困难的问题。社交网站中好友推荐算法就是针对这一难题而提出的。

目前，针对社会网络的好友推荐算法，研究人员已经提出一些解决方案。Spertuse等[2]根据现在社区的用户来推荐在线社区给用户，并在一个社交网络Orkut的大型研究中比较了几种不同的相似性度量。Geye[3]利用社交网站的信息建立了一个系统来推荐自我描述的主题，指出基于社交网络的推荐优于简单的内容匹配推荐。

实验结果通过与三种常用的好友推荐算法对比得出。第一种是简单的频率算法，它将好友最多的用户推荐出来；第二种是关联规则算法，通过关联用户间的好友关系推荐与目标用户共同好友最多的用户；第三种是协同过滤算法，通过计算用户间的相似性进行推荐。第一种算法简单、高效，但是忽略了社交网络中需要推荐兴趣爱好最相近的好友；第二种算法仅仅采取共同好友个数来推荐，不能利用社交网络中更多的用户信息去推荐；第三种算法虽然能计算出最相近的好友，但是效率值比较低。本文在已有研究工作的基础上，综合考虑以上算法的优缺点，提出了改进的推荐算法。首先介绍关联规则和协同过滤算法，以及它们的优缺点，然后介绍改进的推荐算法，最后通过实验对该方法进行评价。

2 相关算法分析

2.1 关联规则

关联规则挖掘[4]是搜索寻找项目与项目之间的关系，在数据库中出现的频率比较高。例如，如果项目B 在项目A 中出现，那么关联规则表示为A＝＞B（如果A，那么B）。支持度和置信度是关联规则的两个评价措施，反映了关联规则的实用性和确定性。支持度是指规则中所出现模式的频率，如果事务数据库D 有s%的事务包含AB，则称关联规则AB 在D 中的支持度为s%，实际上，可以表示为概率P（AB），即support（AB）＝P（AB）。信任度是指蕴含的强度，即事务D 中c%的包含A的交易同时包含AB。若X 的支持度是support（A），规则的信任度即为：support（AB）／support（A），这是一个条件概率P（B｜A），即confidence（AB）＝P（B｜A）。关联规则就是支持度和信任度分别满足用户给定阈值的规则。

在好友推荐的应用中，关联规则推荐技术存在着自身的问题。（1）数据稀疏，如果数据量很大，则较难发现强关联规则。社交网络中的用户数据是庞大的，如果用户的好友数量比较小，算法要找到用户间的好友关系是困难的，从而影响了推荐系统的推荐效果。（2）静态的关联规则。关联规则算法一般都认为所发现的关联规则在数据库中是永恒有效的，没有考虑到关联规则的变化，它得到的是一种静态的关联规则。但是，在好友推荐中，用户可以随时添加好友或者解除好友关系，关联规则是随时间变化而变化的。静态的关联规则在某种程度上不能反映用户好友关系发生变化或更新，从而导致推荐系统可能会向用户推荐没有好友关系的用户。

2.2 协同过滤算法

协同过滤算法是基于这样一个假设：如果用户对一些项目的评分比较相似，则他们对其它项目的评分也比较相似；如果大部分用户对一些项的评分比较相似，则当前用户对这些项的评分也比较相似。协同过滤算法主要分为两种：基于项目的算法和基于用户的算法。

（1）基于项目的方法[5]：此算法建立在项目具有一些确定的特点，而这些特点可以用标签具体地表现出来，通过用户对标签的喜欢程度，反映用户对项目的喜好程度。例如，用户的所有标签可以模拟在TF-IDF模型[6]中，它能够告诉这个用户不同词语的重要性。具体来说，设置所有标签B，W 是所有独特的字出现在B 中，BJ∈B 是用户uj感兴趣的标签，而用户Ok，J感兴趣的字Wk恰好出现在BJ中。参考TF-IDFk，j模型，计算公式如公式（1）：

取得感兴趣的标签后，就可以知道一个用户可能是对“足球”、“世界杯”有兴趣，而另一个用户可能对“电影”、“奥斯卡”更感兴趣。

（2）基于用户的算法：依靠计算用户之间的相似度，找到与目标用户具有相似兴趣度的用户，并称这些用户为目标用户的邻居；然后认定邻居感兴趣的项目，则目标用户对这些项目也是感兴趣的。而计算用户之间的相似度是一个研究重点。例如，Halpin[7]通常用来计算“标签相似性”：

其中，Iu（Iv）是用户u（v）最喜爱的项目集。通过余弦相似性来度量两个向量之间的相似程度：

其中，u、v是u、v的矢量，Iu，j表示用户u 对 第j 个项目感兴趣。最大相似性Similarity（u，v）表示用户u和用户v 也有类似的兴趣。

随着社交网络规模的扩大，用户数目和标签的信息数据急剧增加，使得用户-标签的矩阵数据稀缺，导致用户相似性和标签相似性准确率下降，使推荐质量急剧下降。

综合以上两种算法的问题，本文提出的改进推荐算法包含三个关键的创新：（1）用户间的好友关系。每位用户都有好友，社交网络中共同好友的个数越多，说明他们相似性越强，这使得好友推荐更实用、更准确。（2）标签的相似性。每位用户都有自己的标签来显示用户的喜好、特点，比较两位用户的标签相似性，提高推荐效率，增加推荐的权重。（3）结合上述两种算法，得出改进算法的公式。

3 改进的好友推荐算法

本文提出的改进推荐算法描述如下。首先利用关联规则的算法，即通过用户之间的好友用户之间共同好友的个数，建立矩阵，计算并输出排序结果。设P 是n 个用户之间的偏好矩阵。在这个矩阵里，如果用户i和用户j 是好友关系，则Pi，j是1，否则为0。图1表示的是P 矩阵图。

关联矩阵A 是一个n×n 的矩阵，含n 个用户彼此关联规则的置信度，如图2 所示。其中，n 为用户的数量，ai，j是关联规则i⇒j的置信度。ai，j表示既是用户i的好友、又是用户j的好友在所有用户N 中的比例。矩阵A 是从矩阵P 计算得出的。

Figure 1 P matrix图1 P 矩阵图

Figure 2 A matrix图2 A 矩阵图

目标用户K 的偏好向量u 是一个1×n 的矩阵，uk，j表示目标用户k 和用户j 的共同好友关系，它是矩阵P 的行向量。为目标用户推荐的矢量r，可以通过关联矩阵A 和目标用户的偏好向量u 的乘积得出：

然后，计算目标用户标签和推荐出的top-N用户的标签的相似度。算法的核心是计算出和目标用户标签最相近的用户集，即用户u要产生一个根据其标签的相似度大小排列的“邻居”集Nu＝｛N1，N2，…，Nk｝，sim（u，N1）＞sim（u，N2）＞…＞sim（u，Nk），sim（i，j）表示两个用户之间的相似性。在社会网络中标签不是特定的词语，用户可以根据自己的爱好来设定喜好标签。因此，本文采用语义标签相似度算法计算标签与标签之间的相似性，进而通过得分的高低来评价相似度的高低。单个词的相似度得分计算公式为：

其中，n 为tagRefVector 中的参照标签个数，key为单个标签词，tagRefi为第i个参照标签。

组合词的相似度得分计算公式为：

最后，对得出的r 和得到的相似度V 进行权重的赋值：

其中，α 是改进的好友推荐算法的参数，本文实验中假定在社会网络的好友关系中，共同好友的权重要强于标签相似度的权重，实验中采取经验估值，设α＝0.6。

算法 改进的好友推荐算法

输入 用户-用户ID 表，用户-用户好友关系表，标签-标签ID 表，用户-标签表。

输出 好友列表。

步骤1 设矩阵P，如果用户i和用户j 是好友关系，则Pi，j是1，否则为0。

步骤2 偏好向量u 是1×n 的矩阵，是P 向量的行向量。

步骤3 矩阵A 是n×n 矩阵，n 为用户的数量，ai，j表示既是用户i 的好友、又是用户j的好友在所有用户N 中的比例。

步骤4 利用公式（4）计算r的值。

步骤5 根据r值输出好友列表Top-N。

步骤6 计算Top-N 好友和目标好友标签相似度。

步骤7 利用公式（5）和公式（6）计算V 的值。

步骤8 输入r值、α值和V 值。

步骤9 利用公式（7）得到最终W 值。

步骤10 输出推荐的好友列表。

4 实验结果与分析

4.1 实验数据集与环境

实验数据是从一个音乐社交网站last.fm[8]、通过网站提供的开放API抓取下来的。为了提高实验的准确性，选取1 111个用户，包含3 114个好友关系。数据集存储在mySQL 数据库中，建立四个数据库表，分别是用户-用户ID 表、用户-用户好友关系表、标签-标签ID 表和用户-标签表。图3显示的是数据库中各个数据库表，分别只截取了前10个数据。

Figure 3 实验数据库表图3 Experimental database tables

实验硬件平台为Intel（R）Core（TM）2Duo CPUE 7400，主频为2.8GHz，2GB内存，160GB硬盘。操作系统为Windows professional SP3，所有算法用Java语言实现。

4.2 实验方法和度量

数据集分为80%的训练集和20%的测试集，平均分为5种不同的测试集（5倍交叉验证）用来测试[9]。为了确保推荐的准确性，在测试中隐藏每个用户的一个好友数据，并推荐预测偏好最高的N 项偏好信息，计算预测的精度比例。如果隐藏的好友实际上包含在Top-N 推荐名单中，就是所谓的命中。采用准确率（Precision）和召回率（Recall）两个指标对简单的频率方法（SF）、单层次关联规则方法（AR＋）、协同过滤方法（CF）和改进的推荐方法（GR）四种算法进行评价，定义如下：

准确率（Precision）＝推荐出的已经成为好友的用户／推荐出的好友用户

查全率（Recall）＝推荐出的已经成为好友的用户／好友总个数

在本实验中，使用推荐好友个数N＝10，2.，30，40，50五种情况分别对每个N 测量的准确率和召回率进行计算。

4.3 实验结果

图4显示了四个不同的推荐算法准确率（Precision）的比较结果。图4结果显示，与AR＋相比GR 算法对Top-N 的每个值都优化，达到2.5%、1.2%、1.3%、1.8%和2.0%，准确率（Precision）得以提高。这一结果表明，改进的算法是有效的。GR 算法在N＜20的时候，推荐的准确率要比CF的差，但是当N≥30时，GR 算法的推荐率要明显强于CF。

Figure 4 Precision图4 准确率

图5显示了四个不同的推荐算法召回率（Recall）的比较结果。当N＜20 时，与CF 相比，GR性能稍差，但当N＞30 时，表现出较高的召回率（5.4%、1.5%和8.6%）。随着N 的增加，CF的性能变得相对低下，由于数据稀疏，CF方法不能预测许多项目的偏好。

Figure 5 Recall图5 召回率

5 结束语

本文提出一种基于好友之间的关系推荐和喜好标签的相似度推荐相结合的推荐方法。通过Last.fm 数据集的实验表明，改进的推荐算法能够提高推荐的准确性。和简单的频率方法（SF）、单层次关联规则的方法（AR＋）、协同过滤方法（CF）相比，改进的算法显示了更好的性能。

[1]Gou Liang，You Fang，Guo Jun，et al.SFViz：Interest-based friends exploration and recommendation in social networks[C]∥Proc of 2011Visual Information Communication-International Symposium，2011：15-24.

[2]Spertus E，Sahami M，Buyukkokten.Evaluating similarity measures：Large seale study in the Orkut social network[C]∥Proc of SIGKDD'05，2.05：678-684.

[3]Geyer W，Dugan C，Millen D，et al.Recommending topic for self-descriptions in online user profiles[C]∥Proc of 2008 ACM Conference on Recommender Systems，2008：1.

[4]Aljandal W，Bahirwani V，Caragea D，et al.Ontology-aware classification and association rule mining for interest and link prediction in social networks[C]∥Proc of AAAI Spring Symposia 2006on Social Semantic Web，2009：1.

[5]Linden G，Smith B，York J，et al.Recommendations：Itemto-item collaborative filtering[J].IEEE Transactions on Internet Computing，2003，7（1）：76-80.

[6]Caragea D，Bahirwani V，Alj W，et al.Ontology-based link prediction in the livejournal social network[C]∥Proc of 2009 Association for the Advancement of Artificial Intelligence，2009：1.

[7]Halpin H，Robu V，Shepherd H.The complex dynamics of collaborative tagging[C]∥Proc of WWW'07，2.07：211-220.

[8]Last.fm[EB／OL].[2009-08-01].http：／／www.lastfm.com.

[9]Hsu W H，King A L，Paradesi M S R，et al.Collaborative and structural recommendation of friends using weblog-based social network analysis[C]∥Proc of AAAI Spring Symposia 2006on Computational Approaches to Analysing Weblogs，2006：1-16.