基于粗糙集规则提取的协同过滤推荐算法

任永功，张云鹏，张志鹏

（辽宁师范大学计算机与信息技术学院，辽宁 大连 116000）

1 引言

进入互联网时代以来，人们能够获取的信息资源愈加丰富，这些信息资源在方便人们生活的同时也带来了一定的问题，人们需要花费更多的时间和精力去搜索对他们有用的信息，因此“信息超载（information overload）”所带来的问题越来越严重。推荐系统（RS,recommendation system）[1]能够有效地解决信息超载问题，通过为用户推荐满足其需求的对象，实现个性化服务。

协同过滤（CF,collaborative filtering）[2]是目前推荐系统领域应用最广泛且最成功的推荐技术之一。协同过滤就是根据用户模型找到与之匹配的信息，然后将这些信息推荐给用户，或者建立具有相似兴趣的用户群，在用户群中进行信息推荐。协同过滤通常分为 2 类：基于用户的协同过滤（UBCF,user-based collaborative filtering）和基于物品的协同过滤（IBCF,item-based collaborative filtering）[3]。基于用户的协同过滤技术随着用户数量的增加，其算法时间复杂度不断加大，具有一定的缺陷；基于物品的协同过滤技术是目前研究的热点方向。

在实际应用中，用户和物品数量不断增加，导致数据稀疏程度增大，从而使协同过滤推荐算法的准确性降低[4]。对于这一问题，国内外众多研究者开展了大量工作，给出一些解决办法，可以概括为4 类。1)填充矩阵：使用用户-物品矩阵行和列的加权平均值、众数、中位数等对稀疏矩阵进行填充，以改善数据的稀疏性[5]，这种方法虽然对稀疏数据改善直观、显著，但对空值的预测会产生较大偏差，影响后续计算的准确性。2)新相似性方法：有效利用用户评分数据中所包含的各种有用信息，计算用户或物品之间的相似度，与传统的相似性计算方法相比，这种方法具有更高的稳定性，但它并没有从根本上改变评分矩阵的稀疏程度，导致推荐质量改善程度有限[6]。3)推荐结果融合：将不同方法计算出的用户对物品喜爱程度进行综合，根据综合结果对用户进行推荐，与单一推荐结果的计算方法相比，这种方法可以提高推荐质量[7]，但其计算结果的可解释性差，方法的准确性会受到融合机制的影响。4)基于内容的方法：通过建立用户描述文件和物品内容文件，把最符合用户描述的物品内容匹配给用户[8]，但很多物品内容是非结构化的，难以对内容进行分析，导致该方法使用受限。

针对现有方法的缺点，本文提出一种基于粗糙集规则提取的协同过滤推荐算法，该算法首先通过提取用户属性、物品属性和用户对物品的评分，构建决策表，利用粗糙集理论对决策表进行约简，依次求出表中每一条规则的核值，通过核值决策规则，找出所有决策规则的约简，提取规则；然后根据规则对未评分的用户进行评分，有效填充评分矩阵中的缺失值，缓解协同过滤算法在相似度计算阶段由于数据稀疏性引起的推荐问题。最后，在MovieLens 数据集上与已有的3 种推荐算法进行对比分析，实验结果表明，相比于已有的算法，本文算法具有更大的优越性。

2 相关工作

随着数据量的急剧增加，网站中用户和物品数量越来越多，很多用户通常只会对自己所喜欢的物品进行认真准确的评分，导致可以用来计算用户-物品之间相似度的数据非常有限，甚至经常会出现2 个用户或2 个物品之间没有共同评分，相似度无法计算，从而使推荐系统的质量难以保证。因此，如何解决好数据稀疏性问题显得越来越重要。

针对上述问题，国内外众多研究者从不同角度展开一系列研究，并给出一系列解决办法。部分研究者从填充矩阵的角度出发，提出将用户对未评分物品的评分设为一个固定缺省值，或者设为用户的平均评分[5]，以缓解矩阵的稀疏性问题。邓爱林等[9]提出一种基于项目评分预测（IRP,item rating prediction）的协同过滤算法。IRP 使用基于物品的协同过滤算法对用户进行预测评分，然后对用户评分项中的评分空值进行填充，在填充后的数据集上对用户之间的相似度进行计算。郑荔平等[10]提出了一种基于粗糙集的协同过滤算法，首先利用用户评分数量和用户的评分值对用户进行分类，然后利用粗糙集属性约简的方法剔除对用户分类影响较小的物品，形成更小的用户-物品评分矩阵，以降低数据的稀疏性和规模。张锋等[11]按照用户评分向量交集大小选取候选邻居集合，使用BP 神经网络预测用户对物品的评分，缓解候选邻居评分数据的稀疏性问题。

部分研究者有效利用用户评分数据中所包含的各种有用信息，计算用户或物品之间的相似度，孟桓羽等[12]通过建立基于图的评分数据模型，将传统的协同过滤算法与图计算及改进的KNN 算法结合，提出一种基于图和K 近邻模型的协同过滤推荐算法。冷亚军等[13]提出一种两阶段最近邻选择（TPNS,two-phase neighbor selection）算法。TPNS首先计算用户之间的近邻倾向性，将近邻倾向性较高的用户组合为初始近邻集合；接着按照初始近邻集合计算目标用户和其他用户之间的等价关系相似性，修正目标用户的初始近邻集合，获得最近邻集合。于洪等[14]根据用户时间权重值的大小和用户对新项目的偏爱程度，在充分考虑用户、标签、项目属性、时间等信息基础上，获得个性化的预测评分值公式。朱敬华等[15]提出了融合用户相似性、地理位置相似性和信任关系的混合推荐模型。

上述改进方法在一定程度上缓解了稀疏性对推荐准确性的影响，但还不能直观、准确地改善稀疏数据，并且对已有评分信息的利用还很不充分，基于此，本文提出一种基于粗糙集规则提取的协同过滤算法。

3 粗糙集规则提取的协同过滤算法

由于现实生活中用户-物品评分矩阵往往是稀疏的，基于物品的协同过滤算法无法产生较好的推荐。本文将粗糙集理论融入基于物品的协同过滤中，通过粗糙集理论提取规则，预先对用户-物品评分矩阵中的空值进行有效的填充，缓解用户-物品评分矩阵中数据稀疏性的问题，提高推荐的准确性。

3.1 粗糙集理论的规则提取

粗糙集（rough set）理论是Pawlak[16]在1982 年提出的一种能够定量分析处理不精确、不一致、不完整信息与知识的数学工具。粗糙集理论方法能够从决策表中提取经过属性约简和值约简的规则，在保证决策表决策能力不变的情况下，去除冗余属性，提供简洁并且正确的决策规则。

利用粗糙集理论提取规则的过程即为对决策表进行值约简的过程。首先，删除决策表中的冗余属性，即对决策表进行属性约简，属性约简是利用粗糙集理论挖掘规则的关键，属性约简的结果将直接影响规则挖掘的结果[17]。其次，对约简后的决策表进行值约简。决策表中每一条实例均可视为一条规则，冗余属性值也包含在其中。决策规则的约简是将每条规则中的不必要条件分别进行消除，针对每条决策规则依次删除冗余属性值，以便使规则最小化。决策规则相对于决策表而言，它的形式更加简洁，又尽可能地保留了决策表中的信息。

粗糙集基于不可分辨关系，给出知识表达系统的模型，设知识表达系统S=(U,A,Va,f)，其中，U表示对象的非空有限集合，称为论域；A表示属性的非空有限集合；Va表示属性a∈A的属性值的取值范围，即属性a的值域；f:UA→Va是一个信息函数，它为每个对象的各种属性赋予一个信息值，即对任意a⊆A,x⊆U，都有f(x,a)⊆Va。知识表达系统也叫作信息系统，也可用S=(U,A)表示，其中，U={u1,u2,...,un}，A={a1,a2,...,an}。A中的元素称为属性，C∪D=A，C∩D=Ø，C称为条件属性集，D称为决策属性集。决策表是同时具有条件属性集和决策属性集的知识表达系统。

在知识表达系统S=(U,A,Va,f)中，设R∈A，则不可分辨关系IND(R)={(x,y)∈U2|a(x)=a(y),a∈R}，不可分辨关系实际上就是一种等价关系。

粗糙集利用上、下近似集逼近不精确对象，为推理不精确知识提供了新思路。对于∀X⊆U，有RX={x∈U|[x]R⊆x} 表示X的下近 似 ；={x∈U|[x]R∩X≠∅}表示X的上近似。其中[x]R表示包含元素X∈U的R等价类，R是U上的一个等价关系；posR(x)=RX称为X的R正域，negR(x)=U-X称为X的R负域。posR(x)或RX是根据知识R判断U中一定属于X的元素的集合；根据知识R判断U中有可能属于X的元素的集合；negR(x)是根据知识R判断U中一定不属于X的元素的集合。

在知识发现和信息系统分析等领域，知识约简有着重要的应用意义。知识能否进行约简取决于知识之间的依赖性，这种依赖性所赋予的知识的重要性往往是知识约简的启发式信息。核是所有约简计算的基础，核包含在所有约简之中，在知识约简中，核是不能消去的知识特征的集合。令C和D为等价关系族，R为不可分辨关系，若pos(c-|R|)(D)=pos(c)(D)，则称R为C中D不必要的，否则R为C中D必要的。C中所有D必要的原始关系构成的集合称为C的D核，简称为核，记作coreD(C)。

3.2 粗糙集规则提取的协同过滤算法

本文首先对数据进行填充，利用粗糙集理论提取规则，对未被用户评分的物品进行评分，构建新的用户-物品评分矩阵，根据新评分矩阵计算物品之间相似度，最后，利用加权求和的方法对物品进行预测评分，并为用户进行推荐，具体步骤如下。

1)对用户-物品评分表进行填充。建立决策表S=(U,A)，A中包含用户属性、物品属性和评分信息，其中用户属性和物品属性为条件属性，物品评分为决策属性。根据决策表，删除具有相同条件属性和决策属性的集合，得到新的决策表S1=(U1,A)。在S1中寻找等价关系族，令C和D为等价关系族，R是不可分辨关系，若pos(c-|R|)(D)=pos(c)(D)，则删除R，得到决策表S2=(U1,A1)，对其中每一条U1，依次去掉一个属性值，若没有出现与该规则不一致的规则，则删除该属性值，依次求出表中每一条规则的核值，得到核值表。通过核值表的核值决策规则，找出所有决策规则的约简，提取决策规则。根据决策规则，提取用户属性、物品属性和评分信息，构建评分表，对原始的用户-物品评分表进行填充。

2)计算物品之间相似度。2 个物品之间相似性计算的基本思想是先分离出所有对这2 个物品进行评分的用户，然后根据相似性计算技术计算这2 个物品之间的相似性。本文选用余弦相似性计算方法，这种方法将2 个物品作为m维空间中的2 个矢量，并用这2 个矢量之间夹角的余弦值定义2 个物品之间的相似度。

其中，“·”表示2 个矢量之间的点积，分子为2个物品评分矢量的内积，分母为2 个物品矢量模的乘积。

3)预测评分。通过排列物品之间的相似性，找到物品i的邻居集合，通过目标用户u对物品i邻居的评分值进行加权求和，得到最终的预测结果。

其中，S(i)表示物品i的k近邻集合，sim(i,j)表示物品i和物品j之间的相似度，和分别表示物品i和物品j所有评分的均值，ru,j表示用户u对物品j的实际评分。

4)产生推荐。通过预测评分，将用户对物品的喜爱程度进行排列，将排在前面的物品推荐给用户。

算法1粗糙集规则提取的协同过滤算法

输入用户-物品评分表

输出为目标用户推荐的N个物品

3.3 算法分析

传统基于物品的协同过滤算法，对于物品相似度迭代计算只需要进行一次，没有反复的迭代计算。假设用户-物品评分矩阵中有n个物品，那么，传统的基于物品的协同过滤算法的时间复杂度为O(n2)。

从算法描述中能够看出，本文算法可以分为3个部分。第一部分，通过粗糙集理论对决策表进行约简；第二部分，计算物品之间相似度；第三部分，预测评分。算法的时间开销主要来源于前2 个部分。在通过粗糙集理论对决策表进行约简时，要把每n个项目的m个属性依次进行删除并计算，因此，时间复杂度为O(mn)；在计算物品相似度阶段，对于物品相似度迭代计算只需要计算一次，并没有反复的迭代计算，时间复杂度为O(n2)。因此，本文算法的时间复杂度为O(mn)+O(n2)。但在实际计算的过程中，物品的属性个数m并不会很大，所以本文算法的时间复杂度为O(n2)。相对于传统的相似度计算算法，也需要迭代物品的个数，时间复杂度为O(n2)。因此本文算法在原有算法的基础上没有产生更高的消耗。

4 实验及结果分析

本节通过实验分析，验证所提推荐算法的性能。

4.1 实验数据集和评价指标

为了评价算法的性能，本文采用MovieLens 数据集中2 个不同规模的数据集来进行实验。

1)MovieLens-100K 数据集。该数据集包含了943 个用户对1 682 部电影的10 万次评分，其中每位用户至少对20 部电影进行过评分，评分采用5级评分制。

2)MovieLens-1M 数据集。该数据集包含了6 040 个用户对3 952 部电影的100 万次评分，其中每位用户至少对20 部电影进行过评分，评分采用5 级评分制。

本文使用交叉验证来确定模型的有效性，并对得到的结果进行分析。将原始数据集按照4:1 随机划分为2 个互补子集，并选取80%为训练集，20%为测试集。首先对训练集进行分析，然后验证对测试集影响。为了减少可变性，本文使用不同的划分进行多轮交叉验证，并对每次验证的结果进行平均，本文实验进行了五重交叉验证。

为了衡量所提方法的性能，本文使用了平均绝对误差（MAE,mean absolute error）、均方根误差（RMSE,root mean squared error ）和精度（Precision）作为评估指标。MAE 和RMSE 指标显示了预测与实际值之间的平均误差，这些值越低，表示推荐系统的推荐效果越好。MAE 和RMSE 分别定义为

其中，ri,j表示用户i对物品j的实际评分，r'i,j表示用户i对物品j的预测评分，N表示测试集中包含的评分数量。

Precision 表示推荐系统为用户推荐的物品中用户实际喜欢的物品所占的比例，比例越大，说明算法推荐精度越高。Preci sion 定义为

其中，R(u)表示根据用户在训练集上的行为给用户做出的推荐列表；T(u)表示用户在测试集上的行为列表，即用户喜欢的商品；绝对值表示列表长度。

4.2 本文实验结果和相关方法对比

为了验证本文所提算法对推荐性能的影响，在相同的相似度计算条件下，将本文算法 RECF（rough sets rule extraction collaborative filtering）与下述3 种算法进行比较。

1)基于物品的协同过滤（IBCF,item-based collaborative filtering）算法[3]。只利用评分信息，通过度量物品间余弦相似度，进而基于物品最近邻进行预测推荐。

2)固定缺省值的评分填充算法[5]。将用户对未评分物品的评分设为一个固定的缺省值，本文设为物品的平均评分（MVCF,mean value collaborative filtering），利用物品历史评分信息，计算物品平均评分，对评分矩阵进行填充，然后采用与IBCF 相同的策略进行预测推荐。

3)基于粗糙集的协同过滤（RSCF,rough set collaborative filtering）算法[10]。利用用户评分数量和用户的评分值，对用户进行分类，利用粗糙集属性约简的方法剔除对用户分类影响较小的物品，形成更小的用户-物品评分矩阵，然后采用与IBCF 相同的策略进行预测推荐。

本文选取邻居数为20、25、30、35、40、45，分别对上述3 种算法以及本文所提算法的MAE 和RMSE 进行计算。计算结果如表1 和表2 所示。

图1 展示了在MovieLens-100K 数据集下4 种算法的结果比较。图2 展示了在MovieLens-1M 数据集下4 种算法的结果比较。实验结果表明，本文算法相比于另外3 种算法具有较好的推荐结果，证明了通过粗糙集理论预先进行规则提取，能有效解决数据稀疏性对推荐系统造成的负面影响。

本文选取推荐列表长度为4、6、8、10，邻居数为20、30、40、50、60，分别对4 种算法的推荐精度进行计算，表1 展示了在MovieLens-100K 数据集下4 种算法Precision 的结果比较。表2 展示了在MovieLens-1M 数据集下4 种算法Precision 的结果比较。当推荐长度一定时，随着邻居数量的增长，4 种算法的推荐精度总体上呈下降趋势，当邻居数量和推荐长度一定时，本文算法的推荐精度大多都高于另外3 种算法。

表1 MovieLens-100K 数据集下4 种算法推荐Precision 比较

表2 MovieLens-1M 数据集下4 种算法推荐Precision 比较

4.3 实验结果对比分析

由于数据的稀疏性，IBCF 不能给出准确的预测；MVCF 参考的是大多数人平均水平的建议，不能进行较好的填充，也无法给出较好的预测；RSCF虽然能删除一些低质量的评分，对推荐结果有一定的改进，但遇到没有历史评分的物品或用户便没有办法为其进行推荐；本文算法通过粗糙集理论进行规则提取，预先对物品进行评分，可以在解决稀疏性问题的同时，一定程度上解决冷启动问题。相比于另外3 种对比算法，本文算法在3 个指标上都有更好的结果，说明将粗糙集理论引入协同过滤推荐算法中，通过粗糙集理论预先进行规则提取，能有效解决数据稀疏性对推荐系统所造成的负面影响。

图1 4 种算法在MovieLens-100K 数据集的结果比较

图2 4 种算法在MovieLens-1M 数据集的结果比较

从图1 和图2 中MAE 和RMSE 的变化趋势可以看出，4 种算法的MAE 和RMSE 都会随着邻居数量的变化而变化，当邻居数量选取较少时，由于只参考了少数人的意见，导致预测评分受个人因素影响较大，不能给出准确的预测；当邻居数量选取过多时，由于加入较多低质量评分，会对预测产生负面的影响，导致MAE 和RMSE 有所升高，但这些低质量评分对推荐系统的影响会随着邻居数量的增多而趋于稳定。通过以上分析可以得出，当邻居数量选取适中时，推荐系统的性能最好。由表1和表2 可以看出，本文算法的推荐精度总体上高于另外3 种算法。当推荐长度一定时，推荐精度大多会随着邻居数量的增多而降低；当邻居数量较小时，本文算法可以达到比较理想的推荐效果。

综上，本文所提算法相比于另外3 种算法在MAE、RMSE 和Precision 这3 个指标中均有明显提高，验证了将粗糙集理论提取的规则引入推荐系统中，能正确对较稀疏的用户-物品矩阵进行填充，更好地反映用户偏好，从而提高推荐系统的性能，为用户提供更加准确的推荐。

5 结束语

本文分析了协同过滤算法中数据稀疏性对推荐质量的影响。由于现有的改进方法还不能充分利用已有的评分信息直观、准确地改善稀疏数据，本文提出一种基于粗糙集规则提取的协同过滤算法，通过粗糙集理论进行规则提取并填充稀疏矩阵，缓解数据稀疏性问题。实验表明，本文算法有效提升了稀疏数据中的推荐精度。本文利用用户及物品的一些属性信息，对评分进行填充，忽略用户社交关系、时间信息等，在未来工作中，要将更多信息融入推荐过程中，以进一步改善协同过滤算法的推荐性能。