基于置信度传播的协同过滤推荐算法

潘燕梅

随着大数据和人工智能的发展，个性化推荐系统已在人们的日常生活中得到广泛应用［1］.然而，现有个性化推荐系统的精确度与现实要求仍有一定的差距［2-3］.在个性化推荐系统中，推荐算法决定精确度的大小，是系统的核心.协同过滤推荐算法作为目前应用的主流算法，可利用相似用户（相似购买喜好）的评分对目标用户进行推荐［4-6］.

传统协同过滤推荐算法复杂度较低，但精度不高.本文首先分析了传统协同过滤推荐算法精度不高的原因，然后引入用户重要性程度因子和项目重要性程度因子，并提出置信度传播算法对重要性程度因子进行迭代更新，最终实现评分预测.最后，利用MovieLens数据集，在Matlab 仿真平台上对所提算法进行了性能仿真.仿真结果表明，基于置信度传播的协同过滤推荐算法相较于传统算法精确度可提升5.09%.

1 传统协同过滤推荐算法

传统协同过滤算法主要过程为：首先确定一个用户ID（目前活跃用户）和评分数据集作为原始参考数据，找出存在相似爱好的用户集合，这些用户有时也被称为对等用户或近邻.然后，算法利用近邻对当前用户未评分产品p 的评分进行预测.这种方法的潜在假设是：①若近邻用户过去存在类似的喜好，他们以后也存在类似的喜好；②用户喜好不会改变.

如表1 所示，目前五个用户按1～5 分的标准评出的分值.分值越大表示用户对该物品项目的兴趣越大.

表1 协同推荐的评分数据库

系统在得到这样的一个评分矩阵后，就会预测特定用户对未知产品的喜好程度.在这里，系统的任务就是要预测用户Alice 对物品5 的评分情况，进而确定是否要把物品5 列入Alice 的推荐列表.

为方便表述，约定下述符号含义：U={u1,…,un}表 示 用 户 集，P= {p1,…,pm}表 示 产品 集，Rn×m表 示n行m列 的 评 分 矩 阵，其 中，Rn×m中 的 元 素 为rij，i∈1,…,n;j∈1,…,m表示用户i对产品j的评分值.如果某个用户i对产品j没有评分，那么对应的矩阵项rij为空.从而，传统协同过滤推荐算法根据以下两个步骤，预测目标用户对产品的喜好程度.

确定相似用户集.在当前推荐系统中，Pearson 相关系数法为确定相似用户集的一般方法.由评分矩阵Rn×m，用户a和用户b的相似度sim(a,b)可以表示为：

其 中：分 别 表 示 用 户a和 用 户b的 平 均 评分.Pearson 相关系数取值从+1（强正相关）到-1（强负相关）.例如根据式（1）可以计算得到Alice 和其他用户的相似度分别为0.85、0.70、0.00 和-0.79.如果指定Alice 的近邻有两个，则Alice 的近邻为Bob 和Carey.

评分预测.根据式（1）的相似度测量，参照用户相似度越大评分决定作用越大的原则，可以定义如下预测值公式：

其中：pred(a,p)表示用户a对产品p的评分.

2 基于置信度传播的协同过滤推荐算法

2.1 重要性程度因子的引入

根据上述分析可知，协同过滤推荐算法的关键在于对相似度和预测评分的计算.在传统协同过滤推荐算法中，所有用户和项目都是视为等效的，即没有考虑不同用户和项目的重要性在实际应用中的影响.实际生活中，用户—项目评分矩阵中，不同的用户u和项目p在这个评分矩阵中代表的重要性程度是不一样的.比如网上书店的推荐系统中，用户ui一共买了1 000 本不同的书，而用户uj一共买了10 本不同的书，那么用户ui在推荐过程中的作用要大于uj，即用户ui的评分更具有权威性.因此在ui和uj与目标用户u具有同样相似度时，用户ui对目标项目的评分作用要大于uj的评分作用.同样，如果同一本书被更多的用户购买过，这本书的影响性也就更大.在现实生活中，假设两个用户对一本很盛行的书有相同的评分，并不能说明这两个用户有相同的兴趣爱好.反之，如果两个用户对两本不是很流行的书有相同的评分，那么这两个用户就很大可能有相同的品味，因此项目（物品）的重要性程度同样会对用户的相似性程度产生一定的作用［7］.

为此，系统通过引入项目重要性程度因子和用户重要性程度因子来进一步提高用户对目标项目的评分精确度.

定义用户u的重要性程度因子为UR( )u，项目i的重要性程度因子为IR( )i.在越重要的用户对推测评分结果的影响程度越大，越重要的项目对用户相似度影响程度越小的原则下，用户u和v的相似度计算，以及用户u对项目i的评分预测可改进为：

其中：为用户u的平均评分，α、β为自由参数.

公式（3）和公式（4）为改进的预测评分方法，从公式可知，要得到用户u对项目i的评分，必须首先计算出用户u的重要性程度因子UR(u)和项目i的重要性程度因子IR(i).

为此，需要构建计算UR(u)和IR(i)的算法模型.该模型中，所有的用户和项目都将视作一个节点，且每个节点都有一定的重要性程度.那么，可利用一个二分图（图1）描述用户和项目之间的作用联系，其中a、b、c分别代表对应项目的初始重要性程度值.该二分图也可用式（5）所示的二元稀疏矩阵表示：

其中：行对应用户节点，列对应项目节点，1 表示用户对项目有评分，而0 表示用户对项目无评分.

图1 中的二分图以及个性化推荐过程中用户—项目评分矩阵的稀疏性，与通信纠错码领域的低密度奇偶校验码（LDPC 码）十分类似.借鉴并改进LDPC 码中的置信传播译码算法，可对用户和项目的重要性程度因子进行计算.为完整性起见，先对LDPC 码和置信度传播译码算法作简要介绍.

图1 初始重要性程度

2.2 LDPC 码

1948 年，香农（Shannon）提出信道编码定理，该定理指出在信息传输速率低于信道容量时，对信息采用一定编码方法，可使通信的误码率任意小［8］.

LDPC 码（分组纠错码）于1962 年由麻省理工学院的Gallager R G.提出，并在1993 年由MACKAY D J C，NEAL R M 等人对其进行了重新研究.基于LDPC 码校验矩阵的稀疏特性［9-10］和低复杂度的置信度传播译码算法，LDPC 码的性能可无限逼近香农限［11］.

(n,k)LDPC 码的校验矩阵H(n-k)×n具备下述性质：①所有行中1 的个数为ρ；②所有列中1的个数为γ；③ρ相对于码长n的比值，以及和γ相对于校验位数(n-k)的比值都远小于1；④任意两行（或两列）间都存在1 的位置个数不大于2.

根据第③条性质可知，H矩阵中1 的密度很小.正因如此，H称之为低密度奇偶校验矩阵.第④条性质则使得H矩阵中不存在长度为4 的短环，从而保证了该H矩阵对应的码字有较好的纠错性能.文献［11］、文献［12］和文献［13］对LDPC 码的置信度传播译码算法进行了研究.

2.3 重要性程度因子迭代更新算法

借鉴LDPC 码的BP 译码算法，引入的重要性程度因子则可利用置信度传播算法进行迭代更新，算法表述如下：其中，Igvu,（i1 ≤u≤U，1 ≤i≤I）表示用户u传递给项目i的置信度，Ivgi,u（1 ≤u≤U，1 ≤i≤I）表示项目i传递给用 户u的置信度，{Si} ,1 ≤i≤I表 示与项目i有连接的用户集，{Siu} ,1 ≤i≤I表示除去用户u之外与项目i有连接的用户集，{Tu} ,1 ≤u≤U表示与用户u有连接的项目集，{Tui} ,1 ≤u≤U表示除去项目i之外与用户u有连接的项目集，|Tu|表示与用户u有连接的项目数目.UR(u)表示用户u的重要性程度因子，IR(i)表示项目i的重要性程度因子.

3 实验仿真分析

为验证所提算法的预测评分能力，本文基于MovieLens100K 数据集，利用Matlab 仿真平台，进行了仿真实验.其中，MovieLens 数据集的电影评分数据是GroupLens Research 在20世纪90 年末到21 世纪初采集的，由MovieLens用户提供（含943 个用户以及1 682 部电影，共100 000 个评分数据）.仿真过程中，公式（3）和公式（4）中的α因子和β因子分别取值为-0.5 和0.5.

GroupLens Research 给出 的MovieLens 数据集如表2 所示.第一列表示用户编号，从1～943；第二列表示电影编号，从1～1 682；第三列表示为用户对相应电影的评分值，分值为1～5 分；第四列是时间戳.

表2 MovieLens 原始数据集示例

为了对所预测的评分进行验证，现将该数据分成u1_base 和u1_test 两部分.u1_base 进行预测评分，u1_test 用来测试预测评分的精确度，其中，算法的准确性定量表述如公式（6）所示，err越大，算法准确度越低，反之则越高.

其中：v∈{R(u,v)≠0} 表示在测试数据集u1_test 中用户u对项目v评分不等于0 的项目，|{R(u,v)≠0} |表示测试数据集u1_test 中用户u对项目v评分不等于0 的项目数量，Pu,v表示测试数据集中用户u对项目v的实际评分，P′u,v表示预测评分.

为了进行对比，传统协同过滤推荐算法的预测精度也进行了仿真.仿真发现，传统协同过滤推荐算法的预测平均绝对误差为0.814 6 分.其中，第一个用户的前20 组预测评分和实际评分数据对比如表3 所示（表中的数据表示预测评分值或是实际评分值，评分值为1～5 分；下同）.可以看出，在这20 组评分中就有5 组评分误差达到了1 分以上.

基于同样的数据集，对本文所提算法的预测评分结果进行分析后，发现它们的预测评分平均误差为0.773 1 分.因此，本文所提算法的预测误精度要比传统的协同过滤推荐算法提升约（0.814 6-0.773 1）/0.814 6=5.09%.表4 还给出了第一个用户的前20 组预测评分和实际评分数据对比结果.从表4 的数据可以看出，在这20 组评分中只有3 组评分误差达到了1 分以上.

以下一次迭代更新后的重要性程度因子值与前一次迭代更新后的重要性程度因子值的差值平方和作为指标，图2 展示了重要性程度因子迭代更新的收敛情况.从图2 可以看出，算法在25 次迭代后已基本收敛.

图2 重要性程度因子迭代收敛情况

表3 传统协同过滤算法预测评分与实际评分对比表

表4 基于置信度传播的协同过滤推荐算法预测评分与实际评分对比表

4 结论

本文在传统协同过滤推荐算法的基础上引入了重要性程度因子，并基于LDPC 码的置信度传播算法对协同过滤推荐算法进行了改进.仿真实验结果表明，改进的推荐算法收敛速度较快，且有5.09%的准确度提升.