基于关联规则和相似性在社交好友推荐算法的研究

丁瑞 谢志存 卢彪

【摘 要】随着移动互联网技术的飞速发展，通信技术的发展以及社交平台的多样化，通过手机在社交平台上进行人机通信已经成为人们交流的重要手段。在社交平台上进行交流预计会有更多的朋友，但是很難从如此众多的用户中找到志同道合的朋友。如何准确地向用户推荐具有相似兴趣的朋友，是所有社交平台都试图解决的问题，也是社交朋友推荐算法的研究热点。因此，我们想开发一种更准确，更方便的社交好友推荐算法，并进行创新性的改变。

【关键词】关联规则;相似性;社交推荐

以往的推荐算法都没有很好的考虑各方面的问题，而我们想要真正的找到一个志趣相投的好友，我们既要考虑人物关系，也要考虑到用户发布的信息相似性。所以我们在进行好友推荐的时候主要从这来两个方面入手，可以达到更好的推荐效果。因此，我们提出来一种基于关联规则和相似性的好友推荐算法，我们用Pesrson相关系数算法处理用户间发布的信息的相似特征值，相似度到达给定阈值的信息可视为一条交易记录，生成交易数据库D，用关联规则改进算法来处理特征值数据，计算出二阶候选项集，并存入推荐规则数据库R，最后选取支持数最高的前N个用户加入到推荐列表中，将得到推荐列表展现给用户。

一、相似性的测试研究

研究Pearson相关系数算法的原理，并使用Pearson算法计算交易数据集D。需要确定用户发布的信息是否是相同类型的信息，并且没有可供参考的上下文、句子或关键字。相似度用于衡量它们是否相同，同类信息是直接有效的方式。因此，当推荐朋友时，在计算相同的“事物”分段信息的相似度时，计算用户发布的信息的相似度时，采用句子词性语言序列余弦相似度算法。

Pearson相关系数是在余弦相似性的基础上加以改进的，考虑到不同用户的热点关键字不同的问题，即对用户进行去中心化，因此在实验研究算法改进上运用了Pearson相关系数算法来计算出用户间发布的信息的相似特征值。

对Pearson相关系数算法研究可知，句子之间最终可能产生多种相似关系，有线性相关关系、非线性相关关系、周期相关关系和不相关关系。通过Pearson相关系数，除了得到相关函数图像，还有二者之间的相关系数，最后由众多相关系数生成交易数据库D。

二、关联规则算法优化

（一）构建改进后的关联规则Apriori算法

Apriori算法改进核心思想是：改进算法时，将准备k阶Tid表的生成是为了生成k + 1阶候选项目集。生成k阶Tid表的过程中，使用Apriori_gen生成k阶候选项目集进行排序。如果交易项目中包含的所有k个级别的候选项目的所有元素数均小于或等于k，则此交易项目不会生成k + 1个级别的候选项目集，因此由此交易项目候选项集，不必编写K级TID表，生成的k级TID表中的数据量小于上一个TID表中的数据量。通过对Apriori算法步骤流程和数学思想的理解，并实现算法运行，最终得到推荐规则数据库R。表1为交易数据库（Transaction Database）D的所有大项集，取最小支持数为3。

改进后的AprioriTid算法具体分析如下：

1）生成 1 阶候选项集 C[1]，生成 1 阶大项集L[1]，同时生成 1 阶 TID 表 TID[1]。如表2所示。

2）通过改进的Apriori算法以次对各步大项集进行运算，直至最后的大项集为NULL为止。通过算法运算得知，在生成5阶大项集L[5]时为 null，算法结束。最后可得出大项集为：L={{A}，{B}，{C}，{E}，{A，B}，{B，C}，{B，E}，{C，E}，{A，B，E}，{B，C，E}，{A，C，E}，{A，B，C，E}}。

（二）社交网络好友推荐算法

关联规则挖掘中Apriori算法在于挖掘隐含的、未知的、有价值的关联模式，社交平台中寻找志趣相投的好友，就是要在找出隐含的、未知的、有意义的好友关联规则，在社交平台中把Apriori算法用于好友推荐中会取得较好的效果。

本文算法具体步骤如下：

步骤1 通过句子词性语言序列余弦相似度算法生成交易数据库 D。

步骤2 使用改进后的AprioriTid算法计算出二阶大项集。

步骤3 将二阶大项集存入推荐规则数据库R。

步骤4 根据输入的用户ID，在规则库R中检索出含有用户ID 的二阶大项集，选择支持数最高的前N个用户放入推荐集合Ur，并将Ur推荐给用户。

三、实验结果与分析

（一）数据集

为验证本文提出的推荐算法可行性与有效性，利用某网络社交平台中的实际生产数据作为实验数据，主要包含用户发布的65042条动态碎片信息，共有用户1000人。为能准确地反映实验结果，将用户数据集的3/4作为训练集，1/4作为测试集。

（二）算法可行性检测

覆盖率（Coverage），评价一个社交平台好友推荐算法往往从覆盖率（Coverage）和准确率（Precision）两方面进行考量，覆盖率主要用于观察推荐算法推荐的好友集合Ure与实际可推荐好友集合Ureal交集汇总好友数量占实际可推荐的好友比率。

准确率（Precision），准确率主要用来衡量算法的正确性、可行性，反映推荐出的准确好友数所占好友数的百分比，越高越准确性越好。

通过对本文算法和传统的AprioriTid算法的比较，可以看出，本文算法在相同的数据记录处理中，所需的时间更少（如图1）。

四、结束语

如何在社交网络过程中找到一个或多个志趣相投的朋友。在本文关于社交朋友推荐算法的研究中，我们不仅考虑社交角色的关系，而且考虑用户发布的信息的相似性。因此，在推荐朋友时，我们主要从这两个方面入手，并使用改进的关联规则推荐算法向用户展示朋友列表。事实证明，类似于关联规则的朋友推荐算法在用户推荐中具有很大的研究价值，最终可以为用户的社交互动带来更多的便利。