一种双向聚类协同过滤推荐算法研究

范奥哲 何利力

摘 要：针对传统协同过滤推荐算法在大数据环境下存在数据稀疏性及计算复杂性等问题，提出一种双向聚类协同过滤推荐算法。该算法首先从用户维度和项目维度两个方向分别进行属性聚类，然后在目标用户和目标项目所在类簇中分别使用改进后的相似度计算方法进行协同过滤推荐，最后通过平衡因子综合预测评分并形成最终推荐列表。在MovieLens公开数据集上进行实验，结果表明，该算法（DCF）相比传统协同过滤推荐算法（TCF）、基于用户聚类的协同过滤推荐算法（UCF）以及基于项目聚类的协同过滤推荐算法（ICF），在平均绝对误差上分别降低了16%、8.1%、7.5%，有效提高了推薦精度。

关键词：协同过滤推荐算法;数据稀疏性;聚类;推荐系统

DOI：10. 11907/rjdk. 191963 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2020）005-0078-05

0 引言

随着互联网技术的快速发展，各种信息呈爆炸式增长，人类进入信息超载时代。面对海量信息，如何从中找到自己想要的内容成为一个亟需解决的问题。目前人们可通过搜索引擎寻找自己感兴趣的内容，从一定程度上解决了信息超载问题，但搜索引擎仍不能完全满足人们的个性化需求，存在较大局限性，因此推荐系统[1]应运而生。推荐系统作为一种有效的信息过滤手段，是解决信息超载问题及实现个性化推荐的重要方式。

推荐系统的核心内容是推荐算法，常用推荐算法有基于协同过滤的推荐算法、基于内容的推荐算法与混合推荐算法[2-3]。其中协同过滤（Collaborative-Filtering，CF）推荐算法应用最为广泛，根据用户历史行为信息即可完成推荐。协同过滤推荐算法根据对象不同可分为两类：基于用户或基于项目的协同过滤[4]。其中，基于用户的协同过滤是通过寻找目标用户的相似用户，将相似用户的相关喜好推荐给目标用户;基于项目的协同过滤是通过计算项目间的相似度，将相似项目推荐给喜欢当前项目的用户[5]。其共同特点是计算用户或项目之间的相似度，因此相似度计算在协同过滤推荐中起着至关重要的作用。但是随着大数据时代的到来，传统协同过滤推荐算法难以解决大数据环境带来的数据稀疏性、计算复杂性等问题[6]。

针对以上问题，研究人员提出了一系列解决方案。例如，胡朝举[7]、许智宏等[8]将基于用户的模糊聚类应用到协同过滤推荐算法中，将用户划分到不同用户簇中，使同一簇中用户相似度最高，并在同一簇中进行协同过滤推荐。聚类的引入降低了数据稀疏性和计算复杂性，并提高了推荐精度;张林等[9]将基于项目的聚类思想引入协同过滤推荐算法中，充分挖掘用户对项目类的兴趣度以及项目在类中的权重关系，提高了推荐效果。然而，以上基于聚类的协同过滤推荐算法都只考虑了用户属性或项目属性单方面聚类对推荐的影响，而没有同时考虑用户属性和项目属性双向聚类对推荐结果的影响。还有一些学者为提高推荐精度，将研究方向放在对相似度的改进上。如任看看等[10]对Jaccard相似性进行改进，在相似度计算中充分考虑共同评分项与所有评分项之间的关系，以及用户评分差异对相似度计算的影响，最终得到较为精确的推荐结果;孟俊才等[11]在相似度计算中提出平均分惩罚机制和共同评分项惩罚机制，对缺失的项目评分进行计算，提高了推荐准确性。但在传统相似度计算方法中，通常只考虑评分值或评分项单方面对相似度计算造成的影响，该方式显然是片面的，无法准确描述出其之间的相似关系。因此，本文首先对用户属性和项目属性分别进行聚类分析，然后在相应类簇中使用改进后的相似度计算方法对二者分别进行预测评分，最后通过平衡因子综合预测评分，并形成最终推荐列表。实验结果表明，该算法降低了数据稀疏性和计算复杂性，并提高了推荐精度。

1 传统协同过滤推荐算法

传统协同过滤推荐算法[12]是指根据数据集构建用户—项目评分矩阵，计算目标用户与其他用户之间的相似度，并根据相似度寻找最近邻居集合，最终为目标用户预测评分产生推荐列表的过程。其实现过程可分为如下3个步骤：

1.1 用户—项目评分矩阵构建

根据用户对项目的评分信息能够构建出用户—项目评分矩阵[Rm×n]，如表1所示。其中m行、n列分别表示用户数和项目数，矩阵值[Rm×n]表示某个用户对某项目的评分值，评分值通常与评分项目类别有关。例如在电影推荐中，评分值通常用整数表示，范围是1～5分，当没有评分信息时用0填充。

1.2 寻找最近邻居

寻找最近邻居是指通过计算用户或项目之间的相似度，选取与目标用户相似度最大的N个用户作为目标用户的最近邻居。其中相似度计算是协同过滤算法最核心的内容，目前广泛使用的相似度计算方法有余弦相似性、Jaccard相似性、Pearson相似性，其中最常用的是Jaccard相似性和Pearson相似性[13]。

Jaccard相似性：Jaccard相似性通常表示为样本集合中公共部分在所有样本集合中所占比重，在推荐算法中两个用户的相似度计算公式如式（1）所示。

1.3 预测评分产生推荐

根据前面得到邻居用户对目标项目的评分，预测目标用户对该项目的评分值，产生最终推荐列表。其计算公式如式（3）所示。

其中，[Pu，i]表示目标用户[u]对项目[i]的预测评分值，[Ru]、[Rv]表示用户[u]、[v]对项目的平均评分值，[Rv，i]表示目标用户[u]最近邻居集中用户[v]对项目[i]的评分，[N]表示目标用户最近邻居的用户个数。

通过以上对传统协同过滤推荐算法的分析可知，相似度计算在推荐过程中起着至关重要的作用，并且传统协同过滤推荐算法中并没有考虑用户属性和项目属性聚类对相似度计算的影响。因此，本文提出一种基于用户属性和项目属性双向聚类及改进相似度计算的协同过滤推荐算法。

2 双向聚类协同过滤推荐算法

2.1 基于用户与项目的属性聚类

在大数据背景下，由于用户对项目的评分数据过少，导致用户—项目评分矩阵过于稀疏，从而影响了用户或项目相似度计算的精确度。同时随着用户和项目规模的不断扩大，其计算复杂度也在不断增加，对于具有m个用户、n个项目的用户—项目评分矩阵而言，传统协同过滤推荐算法的时间复杂度为[O（n*m*m）][14]。因此，为了降低数据稀疏性与计算复杂性，利用聚类技术对原始数据进行聚类预处理是优化推荐结果的常用策略之一。通过聚类技术将用户和项目根据属性信息分别聚类到若干个类簇中，使得同一類簇中的用户或项目相似度最高，而不同类簇中的相似度最低，从而将最近邻居选择缩小到对应类簇中，降低相似度计算的复杂性。

针对用户属性和项目属性，在进行聚类前，需要对数据进行标准化处理。例如在用户属性中考虑年龄、性别、职业等，将年龄定义为数值类型表示，性别用0或1分别表示女性或男性，职业定义为标称型数据，使用数值标号的形式进行标准化[15]。通过该形式的预处理，可得到用户属性表达形式为User={23，1，11}，即年龄为23岁从事软件开发的男性。同理可得项目属性标准化处理后的表达形式。

传统基于用户或基于项目聚类的协同过滤推荐算法，仅从某个方向进行单向聚类，在一定程度上降低了数据稀疏性对相似度计算的影响，但这种考虑是不够全面的。为了解决这一问题，本文提出基于双向的属性聚类分析，分别从用户维度和项目维度两个方向进行属性聚类，然后分别进行协同过滤推荐，从而进一步提高推荐精准度。本文采用使用广泛且计算简单的K-means聚类算法，分别从用户和项目两个维度进行聚类。K-means聚类[15]基本思想是首先在数据源中选择K个点作为初始聚类中心，然后计算数据源中其它点到所有初始聚类中心的距离，将距离近的用户划分到对应簇中，计算簇中所有元素平均值作为当前簇新的聚类中心，如此迭代，直到所有簇的聚类中心不再变化，输出聚类后的结果。该算法时间复杂度为[O（m*k*t）]，其中m代表数据源中的元素个数，k代表聚类中心个数，t代表迭代次数[15]。基于用户的K-means聚类算法流程如图1所示，同理可得基于项目的K-means聚类。

2.2 相似度计算方法改进

由于相似度计算在推荐算法中的核心地位，其计算准确性将直接影响推荐质量。传统Pearson相似性是根据两个用户共同评分项目的集合计算不同用户之间的差异[16-17]，在计算两个用户相似度时忽略了平均值差异，并且没有考虑用户对一些相同项目评分所占比重对相似度计算的影响，从而影响了最终推荐结果。例如用户A、B共同购买了10件商品，但他们没有给出相似评分，用户A、C共同购买了3件商品，但他们给出了相同或相似评分。通过Pearson相似性计算，A、B之间的相似度小于A、C之间的相似度，而事实上A、B的相似度明显大于A、C的相似度，在需求比较严谨的情况下应该避免此类问题产生。传统Jaccard相似性主要根据用户共同评分项目在所有评分项目中所占比重计算相似度，并没有考虑用户实际评分值对相似度计算的影响。

2.3 预测评分产生推荐

通过改进相似度计算，得到目标用户的最近邻居集合，并据此预测目标用户对未评分项的评分，最后进行个性化推荐。利用上述改进的相似度计算方法，本文将综合用户和项目两个维度的协同过滤，在两个方向进行预测评分，然后通过平衡因子综合预测评分，形成最终推荐列表，如式（6）所示。

其中，[Pu]表示在用户维度进行K-means聚类后的预测评分，[Pi]表示在项目维度进行K-means聚类后的预测评分，[λ（0<λ<1）]为平衡因子，通过上式可得到综合的预测评分[P]。该公式具体含义是从用户和项目两个方向进行预测评分，然后加权求和，通过动态调整[λ]的值，以平衡用户和项目两个方向对预测评分的影响。通过上式可知，当[λ]=1时，变为对用户维度单项聚类的协同过滤推荐，当[λ]=0时，变为对项目维度单项聚类的协同过滤推荐。实际应用中应该动态调整[λ]的值，同时考虑两个维度的预测值，使综合预测评分获得最优解，最终产生精准推荐。

2.4 改进后算法描述

本文提出一种基于双向聚类的协同过滤推荐算法，具体过程如下：首先通过用户历史行为数据构建用户—项目评分矩阵，其次从用户和项目两个维度分别使用K-means聚类算法进行用户聚类和项目聚类，然后使用改进的相似度计算方法分别计算两个维度的预测评分，最后通过平衡因子动态调整综合预测评分，并产生推荐列表。具体推荐流程如图2所示。

3 实验与分析

3.1 实验数据与评估指标

本文采用美国明尼苏达大学GroupLens实验室收集整理的MovieLens公开电影评分数据集，该数据集包含了用户属性信息、电影属性信息、用户对电影评分信息等。实验所用评分信息包含943名用户对1 682部电影产生的100 000条评分记录，其中每位用户至少对其中20部电影进行了打分，评分范围为1～5分，评分越高表示用户对该电影喜爱程度越高。为验证本文算法的优越性，将训练集和测试集比例设为4∶1，进行交叉重复实验，训练集用于训练算法中的相关参数，测试集用于验证算法准确性。

在推荐系统中评价推荐结果的指标有多种，其中广泛使用的是平均绝对误差MAE（Mean AbsoluteError），其是通过计算预测值与实际值之间的平均绝对误差得到的，平均绝对误差的值越小，表示推荐结果越好[18-20]。若用户预测评分集合为[p={p1，p2，？，pn}]，用户实际评分集合为[q={q1，][q2，？，qn}]，则MAE表达式如式（7）所示。

3.2 实验方案与结果分析

本文通过3个实验方案验证提出算法的优越性，通过前两个实验动态调整聚类中心K和平衡因子[λ]，使其达到最佳推荐效果。在最佳参数条件下，验证本文算法相比传统协同过滤推荐算法的优越性。

实验1：在基于用户或基于项目的K-means聚类协同过滤推荐算法中，选用不同K值产生的聚类效果是不一样的，最终导致推荐结果也不同。为了验证不同K值对推荐结果的影响，本文通过实验动态调整K值，选择最佳参数。实验结果如图3、图4所示。

通过实验可以看出，聚类中心K的选择对推荐结果有着直接影响，过多或过少的聚类数目都会引起MAE值升高。从图中可以看到，当K=10时，基于用户聚类的协同过滤推荐达到最佳效果，当K=30时，基于项目聚类的协同过滤推荐达到最佳效果。

实验2：平衡因子是确定基于用户和项目双向聚类预测评分，综合获取最终推荐的重要因素。因此，本文选取[λ]为0.1～0.9之间的数值，通过综合评估获取最佳参数。实验中选取的聚类数目分别为K=10和K=30，最终得到的实验结果如图5所示。

通过以上实验可以看到，当[λ]=0.4时MAE值最小，此时协同过滤推荐达到最佳效果，因此将[λ]的值设为0.4。

实验3：为了验证双向聚类协同过滤推荐算法的精准度，将本文算法命名为DCF，与其它3种算法进行对比实验。3种算法分别为传统协同过滤推荐算法TCF、基于用户聚类的改进相似度协同过滤推荐算法UCF、基于项目聚类的改进相似度协同过滤推荐算法ICF，实验结果如图6所示。

通过以上实验可以看出，本文提出算法的MAE值在全局范围内明显小于其它3种协同过滤推荐算法，其中传统协同过滤推荐算法的MAE值最大，而基于用户或基于项目聚类的改进相似度协同过滤推荐算法MAE值略小，其两者之间相差不大。在数值方面，基于双向聚类的协同过滤推荐算法相比传统协同过滤推荐算法的平均绝对误差降低了16%，相比基于用户聚类的协同过滤推荐算法降低了8.1%，相比基于项目聚类的协同过滤推荐算法降低了7.5%，从而证明了本文提出双向聚类协同过滤推荐算法的准确性。

4 结语

针对传统协同过滤推荐算法在大数据环境下存在的数据稀疏性、计算复杂性等问题，提出一种基于双向聚类的协同过滤推荐算法。该算法首先从用户维度和项目维度两个方向分别进行属性聚类，然后利用改进的相似度计算方法分别产生各自的预测评分，通过平衡因子综合预测评分形成最终推荐列表。最后通过实验得出，本文提出的推荐算法相比传统协同过滤推荐算法的平均绝对误差降低了16%，提高了推荐精度。然而，该算法虽然在很大程度上提高了推荐精度，但仍然存在一定提升空间，后续研究还可以考虑其它聚类算法对推荐结果的影响等。

参考文献：

[1] SCHAFER J B，KONSTAN J A，RIEDL J. Recommender systems in E-Commerce[C]. In：ACM Conference on Electronic Commerce（EC99），1999：158-166.

[2] 黄立威，江碧涛，吕守业，等. 基于深度学习的推荐系统研究综述[J]. 计算机学报，2018，41（7）：1619-1647.

[3] 孙辉，马跃，杨海波，等. 一种相似度改进的用户聚类协同过滤推荐算法[J]. 小型微型计算机系统，2014，35（9）：1967-1970.

[4] 王鹏，王晶晶，俞能海. 基于核方法的User-Based协同过滤推荐算法[J]. 计算机研究与发展，2013，50（7）：1444-1451.

[5] 关志芳，孟海东. 融合用户聚类与项目聚类的加权Slope One算法[J]. 控制工程，2018，25（7）：1297-1302.

[6] 杨丰瑞，郑云俊，张昌. 结合概率矩阵分解的混合型推荐算法[J]. 计算机应用，2018，38（3）：644-649.

[7] 胡朝举，孙克逆. 基于用户模糊聚类的个性化推荐研究[J]. 软件导刊，2018，17（2）：31-34.

[8] 许智宏，田雨，闫文杰，等. 基于模糊聚类和改进混合蛙跳的协同过滤推荐[J]. 计算机应用研究，2018，35（10）：2908-2911.

[9] 张林，王晓东，姚宇. 基于项目聚类和时间因素改进的推荐算法[J]. 计算机应用，2016，36（S2）：235-238.

[10] 任看看，钱雪忠. 协同过滤算法中的用户相似性度量方法研究[J]. 计算机工程，2015，41（8）：18-22，31.

[11] 孟俊才，李存志. 基于改进相似度计算方法的协同过滤算法[J]. 电子技术与软件工程，2018（24）：151-152.

[12] 王巧，谢颖华，于世彩. 结合用户聚类和项目类型的协同过滤算法[J]. 计算机系统应用，2016，25（12）：132-137.

[13] 黄正. 面向数据稀疏的协同过滤推荐算法研究与优化[D]. 广州：华南理工大学，2012.

[14] 项亮. 推荐系统实战[M]. 北京：人民邮电出版社，2012.

[15] 申晋祥，鲍美英. 基于用户聚类与项目划分的优化推荐算法[J]. 计算机系统应用，2019，28（6）：159-164.

[16] 于金霞，臧利明，王俊峰，等. 一种改进相似度的协同过滤算法[J]. 河南理工大学学报：自然科学版，2019，38（2）：116-121.

[17] 李荣，李明奇，郭文强. 基于改进相似度的协同过滤算法研究[J].  计算机科学，2016，43（12）： 206-208，240

[18] WEI Z. Optimization collaborative filtering recommendation algorithm based on ratings consistent[C]. The Institute of Electrical and Electronics Engineers，IEEE Beijing，2016：1055-1058.

[19] PAPAGELIS M，PLEXOUSAKIS D. Qualitative analysis of user- based and item-based prediction algorithms for recommendation agents[J]. Engineering Applications of Artificial Intelligence，2005， 18（7）：781-789.

[20] 翁小蘭，王志坚. 协同过滤推荐算法研究进展[J]. 计算机工程与应用，2018，54（1）：25-31.

（责任编辑：黄 健）