基于信息熵和改进相似度协同过滤算法

黄 皓，陈 荔

(上海理工大学管理学院, 上海 200240)

0 引 言

随着互联网的高速发展，信息的产生呈现了一种爆炸增长速度，造成了信息过载现象。信息过载是指数据过量，它导致的后果使得用户难以在短时间内接收到某一方面的全部相关信息，可能会使用户在信息接收不全面的情况下造成错误的决定。当今社会解决此问题的主流方法有以下2种：第一类是以推荐系统为代表的信息过滤技术；第二类是谷歌百度等搜索引擎主要使用的信息检索技术。但搜索引擎存在的最大问题是它很难提供个性化的推荐，它的主要方法是由用户提供精准的文字来进行查找。相反，推荐系统使用用户的历史信息(比如购买、评分信息等)来推荐用户潜在的需要信息，它能够为用户提供更加精准的服务。

协同过滤算法作为推荐系统最常用的方法，它也存在自己的问题：一是噪音数据，大规模地人为捏造数据等行为会造成数据的失真；二是数据稀疏性，随着现代互联网的发展，数据的数目一般是上千万，但用户评分的商品常常很少，导致评分矩阵中大量的空白，导致典型的类似数据集都相当稀疏。

国内外在改进相似度上进行了很深的研究。苏庆等[1]针对数据稀疏和准确率相对较低原因，提出了改进模糊划分聚类的协同过滤算法(GIFP-CCF+),使用了时间差因子、热门物品权重因子和冷门物品权重因子相结合的相似度计算结果，结合改进模糊划分的算法。王运等[2]针对数据稀疏和评分项目差异的问题，提出了FunkSVD矩阵分解和相似度矩阵结合的推荐算法，利用相似度矩阵和FunkSVD生成新的用户相似度矩阵。李容等[3]针对传统相似度忽略共同评分和稀疏数据的问题，提出了一种2个修正因子的改进相似度推荐算法，同时改进了协同过滤算法。王留芳等[4]针对稀疏数据和冷启动问题，提出了一种修正余弦相似度和用户属性的相似度算法加权混合的协同过滤算法。薛亚非[5]针对算法准确率低和耗时长的问题，提出了基于相似度的多重信息协同过滤算法，利用加权信息熵计算兴趣相似度将其和评分矩阵相结合，获得最终的相似度。刑长征等[6]针对稀疏的用户评分矩阵方法，提出了一种改进的填补法和改进相似度相结合的推荐算法。罗辛等[7]针对k近邻法的不足提出了一种相似度支持度优化基于k近邻的推荐算法。

协同过滤算法作为常用的推荐算法，研究者也非常多。王玉珍等[8]为了减小算法的误差，提高推荐的效率和质量，提出了一种SGA-RBF遗传算法优化的神经网络与协同过滤算法相结合的推荐算法，使结果更加精确。王努努[9]针对用户偏好挖掘不全面、冷启动、数据稀疏的问题，提出了基于Softmax回归和矩阵分解协同过滤算法，利用文本挖掘技术进行特征的情感强度分析，利用该算法进行运算。赵宇等[10]为了提高算法的精确度，提出马尔可夫聚类和混合协同过滤的协同过滤算法，利用马尔可夫聚类将人群划分为不同人群然后挖掘不同人群的特征。岳希等[11]针对数据稀疏性，提出了一种将基于用户和基于项目相结合的推荐方法。罗园等[12]提出了一种考虑到用户兴趣变化和用户标注信息的推荐算法，引入了遗忘曲线、文本挖掘技术TF-IDF和混合余弦相似度和改进皮尔逊相似度的方法。袁泉等[13]针对算法只能考虑外部评价不能考虑电影内部的相似度关系，提出构建知识图谱辅助计算电影内部的相似度方法，并且引入了TransE模型和TransHR模型然后将使用混合相似度计算方法。刘国丽等[14]针对冷启动、数据稀疏、可扩展性不高和不同社区簇之间存在相关性的问题，提出在考虑同社区簇内专家信任基础上结合不同社区簇专家信任的算法，将专家机制和推荐算法相结合提高算法的精确性。崔岩等[15]为了提高算法准确性，提出了XGBoost和协同过滤算法相结合的推荐算法，采用百度深度学习框架进行实验。王井[16]为了给读者提供优质服务，提出了一种基于订阅记录的图书协同过滤算法，引入对订阅权重的惩罚机制，增加了热门订阅的权重。张锋等[17]针对推荐算法中数据稀疏的问题，将BP神经网络加入协同过滤算法中，避免了常规降维法的缺点也缓解了数据稀疏的问题。辛菊琴[18]提出了一种融合用户偏好和BP神经网络的推荐算法，在MovieLens数据集上得到了很好的效果。杨远奇[19]将注意力机制的神经网络算法和网络中群组成员的个性化偏好相结合，更加突出用户的个性化特征，加强了算法的准确性。张艳红等[20]针对噪音数据和数据稀疏的问题，提出了一种基于噪音检测修正和神经网络的top-k推荐算法，检测用户评分矩阵的奇异点，对奇异点进行修正处理，使用神经网络缓解数据稀疏问题。

国内外关于信息熵方面的研究也有很多。刘江冬等[21]将信息熵和时效性结合同时解决了噪音问题和数据稀疏性问题；苏梦珂等[22]提出了一种考虑信息熵和用户行为一致性的算法，用信息熵解决噪音数据，考虑用户行为的一致性将用户分组来提高精确度。

本文从信息熵解决噪音数据角度，设计一种基于信息熵和面向数据稀疏的相似度的协同过滤算法，这种算法同时解决了噪音数据和数据稀疏性这2个协同过滤算法中比较重要的问题，提高了推荐算法的准确性。

1 相关工作

1.1 协同过滤算法

协同过滤算法是推荐算法中应用最广泛的一个大类，在工业界等方面得到了广泛应用。现在的协同过滤算法细分为2个类别：基于模型的协同过滤和基于内存的协同过滤。基于模型的协同过滤算法采用概率统计模型和机器学习等方式来解决问题，常见的有：非常热门的矩阵分解、贝叶斯模型、隐语义模型等。基于内存的协同过滤主要通过用户评分矩阵计算相似度，然后找到它的邻居，以此来推荐。它主要分为2大类：基于项目的协同过滤(item-cf)和基于用户的协同过滤(user-cf)。而本文用的是基于用户的协同过滤算法。常见的基于用户的协同过滤算法一般情况下有3个步骤：形成用户-项目评分矩阵、计算相似度寻找最近邻集合N和依据相似度求未知项评分。以下是每一部分的具体过程。

1)形成用户-评分矩阵。

用户评分矩阵通常是用户对项目的评分历史记录，可以表现用户的兴趣所在。设矩阵R为用户-评分矩阵，R是一个m×n的矩阵。其中m表示顾客的数量，用户集合U表示为U={u1,u2,…,um}。其中n表示项目的数量，项目集合I表示为I={i1,i2,…,in}。用户a对项目b的评分分数由sab表示。具体表示见表1。

表1 用户-评分矩阵R

2)计算相似度寻找最近邻集合N。

在第二步寻找近邻集合N的过程中，根据用户评分矩阵R计算相似度，但相似度计算方法有多种，而每一种方法的效果不尽相同。所以选择何种方法计算相似度是一门功夫。在下一节中会具体介绍不同的相似度以及它的具体计算公式。根据相关论文表明,在user-cf中，皮尔逊相似度计算方法的效果相比其他的计算方法更胜一筹。计算完相似度之后将通过排序取出前K个近邻构成最近邻集合N，N=(n1,n2,n3,…,nK)。因为K不是一个确定的值，所以在第二章中会具体分析K的取值对结果的影响。

3)依据相似度求未知项评分。

在第2步中通过计算相似度找到近邻集合N，在最后一步中要根据近邻和相似度计算出最终的未知项评分。它的计算公式如下:

(1)

1.2 传统相似度计算方法

在大部分协同过滤算法中，计算相似度可以说是算法的核心步骤。常见的相似度计算方法有以下几种：

1)余弦相似度。

(2)

2)修正余弦相似度。

(3)

3)Pearson相似度。

(4)

2 结合信息熵和改进相似度的推荐算法

2.1 用户信息熵

1948年，香农提出信息熵这一概念，它解决了信息的度量问题。设X为一随机变量，X取值为X的概率用p(x)表示，则可以用信息熵来表达其不确定性，其计算公式为：

(5)

由公式(5)可以看出，信息熵的值与实际的值无关，与它的概率分布有关。所以在推荐系统中，信息熵能在一定程度上有效地过滤部分噪音数据，同时过滤掉部分信息值较低的用户，以此来提高推荐系统的精确性。

但是一般的信息熵只与评分出现的次数有关，而不与用户的具体分数有关，所以本文引入了用户信息熵模型。

设用户A，其评分集合用Ra={r1,r2,…，rm,…，rn}表示，在评分系统中rm∈{1,2,3,4,5}，其中n=︱Ra︱表示用户A在系统中产生的评分数。对用户A，根据式(5)，其信息熵为：

(6)

其中，c表示评分单位的度量，在10分制的评分系统中c=10；Pak是表示用户a的评分落在区间k的概率。Pak的计算过程为：

Pak=[∑rm∈RaI{rm=k}]/|Ra|

(7)

其中，I{x}为指示函数。综合式(5)和式(6)即可计算用户的评分信息熵。

当然，计算用户的信息熵的目的是为了消除噪音数据，在这当中就免不了确定信息熵的阈值F，当H(u)

2.2 改进相似度计算方法

在推荐系统中一直存在一些比较明显的问题，而最有名的便是冷启动和数据稀疏的问题，专家学者针对这一问题一直在考虑很多的解决方法。在基于内存的协同过滤算法中计算相似度是不可或缺的一个步骤，普通的协同过滤相似度计算方法依赖用户的共同评分项来计算相似度，但因为数据稀疏使得共同评分项数据很少存在，导致在计算相似度上存在比较大的误差问题。所以本文使用了一种面向数据稀疏的相似度计算方法。这种方法改进了冯军美等[23]在论文中提出的方法，使用全部评分数据也不依靠共同的评分项计算来解决数据稀疏问题。

定义用户a和用户b在所有评分项目的集合为Ia、Ib，用户a和用户b相似度计算方法如下：

(8)

其中，︱Ia︱、︱Ib︱用来表示用户a和用户b的总评分个数，用户a在评分矩阵中第k个的评分数值为ra，k，用户b在评分矩阵中第w个的评分数值为rb,w，max(ra,k,rb,w)和min(ra,k,rb,w)分别表示ra,k、rb,w中的最大值和最小值。

计算完相似度之后寻找最近邻居，然后以此来计算用户x未知项i的评分预测为Px,i，它的计算公式见公式(1)。

2.3 结合信息熵和改进相似度的推荐算法步骤

推荐算法的处理流程如下：

Step1输入goodbooks数据集，通过去除重复值等数据处理方式进行数据预处理，形成用户评分矩阵R。

Step2在用户评分矩阵R的基础上结合公式(6)、公式(7)计算所有用户的用户信息熵H(x)。

Step3通过数据建模实验可视化分析信息熵阈值F与RMSE和MAE的关系，确定信息熵阈值F。

Step4当用户信息熵H(x)<信息熵阈值F时，去除该组用户评分数据，得到新的用户评分矩阵Rnew。

Step5计算改进相似度simnew(a,b)。

Repeat

Step5.1逐个计算用户的总评分个数︱Ia︱。

Step5.2max(ra,k,rb,w)和min(ra,k,rb,w)分别表示(ra,k、rb,w)中的最大值和最小值。

Step5.3通过公式(8)计算改进相似度simnew(a,b)。

Step6通过数据建模方法、实验分析方法确定最近邻K的数值，尽量找到能够达到较优解的K的数值。

Step7寻找用户x的相似度最高的K个近邻集合。

Step8通过公式(1)可求出对未知项目的预测评分。

Step9通过对用户的预测评分来计算出RMSE、MAE的结果，并进行可视化分析。

图1为算法的流程图。

图1 算法流程图

3 实 验

3.1 实验数据集

本文采用的是来源于goodreads网站的goodbooks图书数据集，它的评分方法是让用户对图书打出1～5分中间的一个分数，分数间隔为1,分数越高则表示用户越喜欢。该数据集中包含了53424个用户对10000本图书进行的评分，总共有981756条评分数据。它的稀疏度通过计算为：

(9)

通过上式可以看出稀疏程度相当高，该数据集主要包括4个部分：图书标签、图书详细信息(包括作者、语言、年份等)、用户意向阅读的图书(即用户当前或以后感兴趣的图书)和评分数据。

3.2 评价指标

在推荐系统中常用的评价指标为平均绝对误差(MAE)、均方根误差(RMSE)、召回率、准确率、F1值等。本文选用MAE、RMSE作为评估指标。其计算公式分别为：

(10)

(11)

3.3 实验结果与分析

3.3.1 信息熵的计算及阈值的确定

根据之前的算法步骤，先输入评分矩阵，这一步骤比较简单先省略过去。第二步是计算用户的信息熵H(x)。主要使用公式(6)、公式(7)来计算，计算结果如图2所示。使用Python计算用户的信息熵，横轴为用户的编号(userId)，纵轴为用户的信息熵(information entropy)。从图中可以看出绝大多数数据的信息熵处在0.8～2.2，图中上半部分的数据很紧凑，将上半部的图表遮盖得严严实实，当然还有零零散散的一些用户处在0.8以下，可以认为绝大多数处于0.8以下的数据为噪音数据。

图2 信息熵分布图

算法的第三步是确定信息熵阈值F，当用户信息熵H(x)

观察表2可以看出，当设置阈值F为0时RMSE的值为0.867，当阈值在0～0.8的范围中增大时RMSE随着它的增大而减小。当阈值设置为0.8时阈值达到了最小值0.859,。当阈值在0.8～1.6的范围中增大时，可以明显看出RMSE在回升，当阈值设置为1.2时可以看出RMSE已经超过当设置为0的时候，当然之后RMSE继续增长，算法效率越来越低。可以概括地说当阈值在0～0.8范围中增加时，RMSE逐渐降低，算法精确度逐渐上升，当阈值F=0.8时，RMSE达到最低值0.859，当阈值在0.8～1.6中增长时，RMSE逐渐上升，算法精确度逐渐下降。从表2中可以看出当阈值F=0.8时RMSE最小，精确度最高，所以之后将阈值F设置为0.8。

表2 不同阈值F的RMSE

3.3.2 对比实验

图3 不同相似度下最近邻K与RMSE关系图

图4 不同相似度下近邻数K与MAE关系图

图3、图4是选用上文4种相似度的情况下，使用基于KNN的协同过滤算法随着最近邻K变化产生的RMSE变化趋势图，最近邻设置为[0,100]，步长为1。从图3可以看出，在近邻K值取0时，4种相似度下RMSE由大到小依次为皮尔逊>改进余弦>欧氏距离>余弦相似度，RMSE越小时算法准确度越高，所以刚开始时准确度和RMSE大小相反；可以看出在(0,10]这个区间变化时，4个相似度下的RMSE值都处于快速下降的趋势，当K在10左右时，4条曲线的斜率都变得非常小；在K=10时，4种相似度下RMSE由大到小依次为欧氏距离>皮尔逊>改进余弦>余弦，可以看出在K=10时余弦相似度的准确度相对较高；在(10,100]这个区间，4种相似度下RMSE的变化幅度相对较小，但还是有变化的，可以看出最后几种算法的准确度为皮尔逊≈改进余弦>余弦>欧氏距离；则表示在使用goodbooks数据集KNN算法下，皮尔逊和改进余弦相似度准确度最高，而余弦相似度则稍微差一点，欧氏距离可能差得更多一点。

图5 不同相似度下数据稀疏度与RMSE的关系图

为了验证改进相似度对于数据稀疏性的提升效果，图5在KNN算法下选择了改进相似度、皮尔逊相似度、改进余弦相似度，探究稀疏度越来越高的情况下RMSE的变化情况；当数据稀疏度为97%时，可以看出对算法的准确度来说，改进相似度>改进余弦相似度>皮尔逊相似度，但改进相似度和其他2个相似度差距并不大，当然皮尔逊相似度准确度将近0.99，精确性不理想；随着数据稀疏度在(97.0,99.0]上增加，相似度变化规律并不大，皮尔逊相似度随着稀疏度增大它的RMSE增加，导致准确度越来越差，而其他2个相似度差不多但增长率并没有皮尔逊大；当数据稀疏度达到99.5时，3种相似度的RMSE飞速增长，但它们的算法准确度还是保持改进相似度>改进余弦相似度>皮尔逊相似度，这时改进相似度和其他2种相似度的准确度有较大的差距，显示出该相似度在数据稀疏的情况下的优越性；当数据稀疏度为99.9%时，此时更可以看出改进相似度和另外2种相似度相比，它的准确度更精准。通过该图可以看出，改进相似度对数据稀疏度的影响有缓解效果。

算法下一步是找出最近邻居然后计算预测评分来计算RMSE。就像上文提到的近邻的数量对于结果有着很大的影响。接下来将设置几个对照组来对比分析近邻对实验的影响。并且将本文算法与李容等[3]提出的基于改进相似度的协同过滤算法(算法1)、邢长征等[6]提出的填补法和改进相似度相结合的协同过滤算法(算法2)进行对比实验，在研究近邻的影响的同时与普通的协同过滤算法进行比较。如表3所示。

表3 不同近邻数K对RMSE的影响

从表3可以明显看出，本文算法相比上述的基于改进相似度的协同过滤算法都有所提升，3种算法的性能依次对比为本文算法>算法1>算法2。在近邻数K依次增长的情况下RMSE在逐渐减小。K的值的选取确实对于算法的精确性有非常大的影响。

本文在计算相似度时，改进了冯君美等[23]的改进相似度计算方法，为了验证该算法的优越性，将本文算法与冯君美等提出的算法进行对比实验。其中将冯君美等提出的算法称做算法3。

图6是对比实验图，从图中可以看出，本文算法在初始时，MAE的值差距相当大，但当K值逐渐变大之后，本文算法变动区间相对较小，而算法3变动区间比较大，但本文算法在该数据集下它的MAE值一直小于算法3，可以看出本文算法的优越性。

图6 不同算法对比实验图

4 结束语

本文采用了一种将用户信息熵和面向数据稀疏的相似度相结合的推荐算法，分别用以解决协同过滤算法中噪音数据和数据稀疏性的问题，并通过实验表明本文的算法准确性比普通的协同过滤算法有了一定的提升。

但本文对噪音数据影响的研究是通过比较直接的方法，或许会在某种程度上进行错误判断。在这个方面还有待提升，这是以后笔者可以进一步研究发展的方向。