，章金平，徐启南12

(1.安徽大学 计算智能与信号处理实验室，安徽 合肥 230601； 2.安徽大学 计算机学院，安徽 合肥 230601)

根据中国互联网络信息中心(China Internet Network Information Center，CNNIC)最新发布的第40次《中国互联网络发展状况统计报告》，截至2017年6月，我国网民规模达到7.51亿，随之信息也出现了爆炸式增长。人们逐渐从信息匮乏向信息过载转变，信息给人们带来利益的同时，也带来了一定程度上的困扰。如何从大量的数据中选择自己感兴趣的数据，曾是很多人面临的一道难题。搜索引擎的出现，一定程度上缓解了信息过载问题，但其必须依靠用户的主动输入且反馈的结果非个性化，因此存在着一定的局限性。后来，为了解决搜索引擎的局限性，推荐系统诞生了，它能够根据用户的历史行为，为每个用户建立自己的兴趣模型，从而主动为用户进行推荐。现在典型推荐系统有：今日头条、天猫、亚马逊等。为了更好、更准确地进行推荐，推荐算法是推荐系统中的核心部分。协同过滤(Collaborative Filtering,CF)推荐算法是推荐系统中应用最广泛、最成功的推荐技术之一[1]。然而，在面对众多的项目和用户时，协同过滤推荐算法会遇到的最大难题是数据稀疏性问题。其常会导致相似度计算不准确，最终影响预测精度。

为了提高推荐系统的预测精度，很多研究者基于该算法的相似性方面进行了研究。文俊浩等人[2]利用用户共同评分和用户所有评分之间的关系对用户相似度进行改进。荣辉桂等人[3]引入用户相似度概念，定义社交网络中属性相似度、相似度构成和计算方法，提出了一种改进的协同过滤推荐算法。于金明等人[4]提出了新的项目相似度度量方法，该项目相似性度量由评分相似性和结构相似性两个部分构成。张俊等人[5]通过计算用户兴趣相似性，并使用用户兴趣相似性和评分相似性进行两次融合，从而对传统相似性度量仅仅依靠用户评分进行相似性计算引起的误差进行修正。李伟霖等人[6]提出了基于评论与评分的user-based协同过滤算法和基于评论与评分的item-based协同过滤算法。这些方法虽然改进了相似度计算方法,一定程度上提高了推荐系统的预测准确度。但都是在基于传统的相似度度量方法的基础上进行修正的。

本文提出了一种新的协同过滤推荐算法，将互信息作为度量项目之间的相似性方法，解决了Pearson相关系数一般情况下只考虑了线性相关性，对非线性的变量相关性效果一般问题。同时在互信息方法上引入了平滑系数因子，来缓解了余弦相似度方法对稀疏性数据比较敏感问题。

1 相关工作和定义

1.1 基于项目的协同过滤实现

基于项目的协同过滤推荐算法主要有3个步骤：① 构建用户-项目评分矩阵；② 根据用户-项目评分矩阵计算项目之间的相似度；③ 选取目标项最近邻居集，并进行推荐。在整个推荐算法的过程中，相似度计算是该推荐算法的核心部分。因此，一个好的相似度计算方法显得十分重要。

1.2 传统的相似性度量方法

传统的度量用户间相似度方法有很多，其中最具有代表性的有余弦相似度、Pearson相关系数。

余弦相似度是一种常用的相似度度量方法，而且应用十分广泛。它将n个用户对项目i和项目j的评分看成是n维上的一个向量，通过计算向量之间的夹角余弦值来度量项目之间的相似性程度。其中Ru,i表示用户u对项目i的评分，Iu,v表示共同评分项目i与项目j的用户集[4]，计算公式为

(1)

(2)

在实际的推荐系统中，共同评分过的项目i与项目j的用户数很少，因此，传统的相似度方法就遇到了瓶颈。如果共同评分过项目i与项目j的用户数为1，则余弦相似性的计算结果总是1，从而扩大的项目之间的相似度值。Pearson相关系数忽略了用户的评分标准不一样，导致针对每个项目的具体评分差异，会出现以下情况，如5个用户对项目i与项目j的评分向量分别为(1,2,1,2,1)和(4,5,4,5,4)，用Pearson计算得到结果为1。所以，传统的相似度方法计算项目之间的相似性时存在着一定的误差。

1.3 互信息方法

在信息论中，“信息熵”是度量样本集合纯度最常用的一种指标，可用H(X)表示：

(3)

式中，P(xi)为样本xi的概率；q为可能的样本数目。对此，引入X和Y的联合熵H(X,Y)：

(4)

对于整个变量X，由于变量Y的发生及二者间的相关性，使其不确定性减少的熵值称为互信息(Mutual Information)[7]，定义为

I(X;Y)=H(X)-H(X|Y)

(5)

又可以表示为

I(X;Y)=H(X)+H(Y)-H(X,Y)

(6)

综合式(3)～式(6)，可以得到最终的互信息表达公式为

(7)

特别指出，互信息对变量X和Y的分布没有任何特殊要求，它可以用来描述变量之间的线性相关关系或非线性相关关系。在此，为了使互信息的值在[0,1]之间，将其进行归一化处理，即

(8)

将变量X看成为项目i被所有用户评分的向量，记为I。变量Y看成为项目j被所有用户评分的向量，记为J。则项目之间的相似度计算公式为

(9)

式中，I(I,J)为项目i和项目j的互信息值；H(I)为项目i的信息熵。

2 互信息项目协同过滤推荐算法

2.1 用户对项目评分的相似性度量

表1为一个m×n的用户-项目评分矩阵。m行代表m个用户，n列代表n个项目。Rm,i代表第m个用户对项目i的评分。

表1 用户-项目评分矩阵

在真实的推荐系统中，数据稀疏性十分严重，导致共同评分的项目用户数很少，考虑到互信息方法能够更好地挖掘两个随机变量之间的关联程度，即在已知一个随机变量的前提下，使得另一个随机变量不确定性减小的程度。同时引入了平滑系数因子，来缓解共同评分的项目用户数过少，导致相似度计算不准确。如5个用户对项目i与项目j的评分向量分别为(1,2,1,0,0)和(0,0,5,0,4)，用互信息方法，项目i和项目j的相似度值为0.1406，说明了两个项目之间相关性很弱。在互信息方法上加入了平滑系数后，计算结果为0.0468，表明两个项目相似性很低。相比于传统的余弦相似度方法，提出的方法计算项目之间的相似度更加准确。其中平滑系数为

(10)

上述平滑系数的取值范围为[0,1]，当项目i和j完全被相同的用户评分时，此时取值为1。当项目i和j被完全不同的用户评分时，此时取值为0。一般期望共同评价项目i和j的用户数越多越好，即平滑系数值趋向于1时，此时相似度值的计算更加准确，从而提高推荐系统的预测精度。另外，平滑系数能够很好地反映用户打分的重叠部分，且能够获得项目i和j在用户打分方面的相对差异程度，即|I|-|J|。根据式(9)和式(10)，可以得到用户对项目评分的相似性度量为

simscore(i,j)=coefficient(i,j)·I*(I,J)

(11)

式中，i和j分别为两个不同项目；|U|为共同评价项目i和j的用户数；|I|为所有用户对项目i评分用户数；|J|为所有用户对项目j评分用户数；I*(I,J)为项目i和项目j之间经过归一化后互信息值。

2.2 生成推荐集

设集合N(i)={I1，I2，I3，…,In}为目标项Ii的邻居集合，Ii∉I，集合I中元素Ij与目标项Ii之间相似性递减。则预测目标项目Ii评分值计算公式为

(12)

2.3 算法描述

根据前几节的新思想，将所提出方法中核心算法——基于互信息的项目协同过滤算法描述如下。

输入：用户-项目评分矩阵

输出：目标项目的评分预测并产生推荐

开始

沃尔特·格罗佩斯（Walter Gropius,1883～1969）是 20 世纪最重要的现代设计家、设计理论家和设计教育的奠基人。他不仅在理论上和在设计实践中提倡“功能追随形式”的观念，而且把现代主义的设计观念从包豪斯带到了美国，从而影响到全世界。格罗佩斯把“功能追随形式”设计观念更加明确表达为“功能第一，形式第二”。

步骤1:构建m×n的用户-项目评分矩阵

步骤2:计算项目之间的相似度。

根据式(11)计算项目之间在评分上相似度；

步骤3：选取目标项最近邻居集

假设目标项为i，目标项的最近邻居数为N，该用户u已经评价过的项目集合为URDB。根据URDB中的项与目标项i之间的相似性，选择相似度最高的前N个项目作为项目项的最近邻N(i)。

步骤4：根据式(12)预测目标项目评分并产生推荐

结束

3 实验结果及分析

3.1 数据集及数据的预处理

所采用的数据来自GroupLens研究组(http://www.grouplens.org)和Jester(http://eigentaste.berkeley.edu/dataset/)两个数据集。该两个数据集已经被广泛应用在推荐系统的评测中。表2展示了这两个数据集的一些记录情况。分别在这两个数据集上进行了实验。将这两个数据集分别按4∶1比例分成训练集和测试集。

表2 实验数据

3.2 评价指标

本文主要采用平均绝对偏差(MAE)和均方根误差(RMSE)作为评价推荐系统的预测质量的评价指标。MAE和RMSE都是推荐系统中常用的方法，可以直观地对预测质量进行衡量。(pi,qi)为用户评分对，其中pi为预测项目的得分，qi为实际得分。MAE和RMSE的值越小，推荐系统的预测准确度越高。MAE、RMSE的计算公式为

(13)

(14)

3.3 实验结果和分析

为了验证所提方法可行性，分别在MovieLens和Jester数据集上进行了实验。在基于项目的协同过滤前提下，分别选用相似性度量方法为余弦法(CC)、Pearson相关系数(PCC)、互信息(MI)、互信息+平滑系数(MICC)，即本文方法，用MAE和RMSE评价指标做了大量的对比实验。以此来验证本文方法(MICC)的有效性。

(1) MovieLens数据集下不同相似度方法下的MAE和RMSE比较。

表3为MovieLens数据集上不同相似性度量法下MAE和RMSE的实验结果。从表3可以看出，随着最近邻数量的增加，MAE和RMSE值基本上逐渐减少。另外，互信息(MI)方法较传统的相似度方法相比，MAE值降低了0.04左右。在互信息的基础上引入平滑系数后(MICC)，较传统的方法MAE值降低了0.1左右。同时，当最近邻居数目比较少时(小于25)，MAE值明显降低，最近邻居数超过25时，MAE值降低的效果不明显。则可以证明加入平滑系数能够有效地缓解共同评分过少的项目之间相似度计算问题。

(2) Jester数据集下不同相似度方法下的MAE和RMSE比较。

表4为在Jester数据集上不同相似性度量法下MAE和RMSE的实验结果。表4可以看出，由于该数据集项目数非常少，导致其邻居数也很少。当邻居数达到9时，随着最近邻居数量的增加，MAE和RMSE值基本上达到稳定。同时，还可以看出，互信息方法(MI)较传统的相似度方法MAE值降低了0.06左右，加入了平滑系数因子后，所提出的方法(MICC)较其他方法计算出MAE和RMSE都最小，证明了平滑系数对数据稀疏性带来的相似度计算不准确有着一定的影响。

表3 MovieLens数据集下不同相似度方法下MAE和RMSE

表4 Jester数据集下不同相似度方法下的MAE和RMSE比较

4 结束语

本文主要针对推荐系统中数据稀疏性对传统的相似度方法计算项目之间的相似度值不准确问题，提出了基于互信息的项目协同过滤算法，即利用互信息方法有效地挖掘不同项目之间的相关性强弱，同时，引入平滑系数因子来缓解共同评分过少的项目之间相似度度量问题。在MovieLens和Jester数据集上的测试实验结果表明，互信息+平滑系数(MICC)方法在预测准确率方面比传统的相似度方法有着一定的优越性。在以后的工作中，应更深入研究推荐系统，考虑更多的项目信息和用户社交网络信息等，进一步提升推荐系统质量。