基于社区结构的推荐系统中冷启动问题研究

曹珂崯 张天舒 孙娟 彭二帅

摘  要：由于推荐系统中数据稀疏性和冷启动问题日益严重，传统的算法无法有效地解决这些问题，现有的改进算法由于穩定性差，仍然需要预先确定具体的参数。文章提出了一种基于社区结构的冷启动算法以改善推荐系统中的冷启动问题，通过计算用户和项目节点的相似度投影二分网络，利用改进的Louvain算法对投影单模式网络进行社区检测，使新记录更新到社区，然后进行对用户社区组推荐。与其他冷启动算法相比，该算法在推荐准确率和运行效率有明显提升。

关键词：社区检测；冷启动；二分投影网络；推荐系统

中图分类号：TP301.6；TP391    文献标识码：A    文章编号：2096-4706（2023）01-0030-04

Research on Cold Start Problem in Recommendation System Based on Community Structure

CAO Keyin， ZHANG Tianshu， SUN Juan， PENG Ershuai

（Department of Computer and Communication， Jiangsu Vocational College of Electronics and Information， Huaian  223001， China）

Abstract： Due to the increasingly serious problems of data sparsity and cold start in recommendation systems， traditional algorithms cannot effectively solve these problems， and the existing improved algorithms still need to pre-determine specific parameters due to their poor stability. In this paper， a cold-start algorithm based on community structure is proposed to improve the cold-start problem in recommendation systems. By calculating the similarity bipartite projection network between users and project nodes， the improved Louvain algorithm is used to detect the community for the projected single-mode network. It updates the new record to the community and then makes recommendations to the user community groups. Compared with other cold-start algorithms， the algorithm has a significant improvement in recommendation accuracy and operating efficiency.

Keywords： community detection; cold start; bipartite projection network; recommendation system

0  引  言

推荐系统已广泛用于线音乐流媒体服务（例如Spotify、网易云音乐、QQ音乐、Apple Music）。推荐系统是简化用户决策的工具，通过挖掘用户行为数据以帮助用户浏览大量音乐[1]。随着越来越多信息的出现，数据稀疏性问题或新记录不足带来的冷启动挑战越来越严重。如果用户历史行为记录不足，或者歌曲缺少访问记录，推荐结果将不准确，甚至影响推荐其他歌曲的机会，从而产生负面反馈，这称为冷启动问题。

针对推荐系统中的冷启动问题，研究人员进行了相关的研究。Funk将SVD应用到推荐系统中，将用户与项目都投影到矩阵中，显式地表示用户对物品兴趣数据[2]。一些研究发现，来自社区的用户资料可以提高推荐系统的效率[3-5]。Shi提出了一种基于局部代表的矩阵分解方法，可以使用决策树创建相同兴趣的用户组，通过两轮划分为用户划定用户组从而实现组推荐[6]。周超提出了一种分别从用户和项目两个方向通过计算Pearson-Jaccard相关系数进行聚类[7]，从两个方向降低了数据稀疏性的影响。

通过对上述算法总结，结合现实生活中用户具有社区结构，本文提出了基于社区结构的冷启动推荐算法。该算法通过将用户与歌曲行为信息视为二分网络，计算余弦相似系数投影到两个单模网络，利用Louvain算法获得相似用户和歌曲的社区分组，并且能够根据新到达的数据逐步更新新记录的社区，从而对于整个社区组进行推荐，缓解了推荐系统中的冷启动问题。

1  基于社区检测的冷启动算法

在本节中，首先对二分网络进行投影操作，根据用户对音乐的行为对用户/音乐社区进行划分，音乐偏好相似的用户被划分到同一个社区。然后，将新纪录合并到已有社区，原有的用户或项目可能因为新纪录到来，偏好发生改变而更新社区。最后，对于用户社区组生成音乐推荐的结果。算法框架如图1所示。

1.1  二分网络社区检测

为了初始化推荐系统二分图的社区，首先对用户和歌曲进行单模投影，以减少划分社区所耗费的时间。使用余弦相似公式，以计算用户偏好相似矩阵，并设置最小相似度阈值，以突出相似度。

同理，也可计算歌曲之间相似度矩阵Wi。如式（1）所示，其中  和  表示用户u1和u2评价集合， 表示用户u1对歌曲i的评分， 表示用户u1对所有歌曲评分平均值。

（1）

其次，对单模投影网络进行社区划分。在网络中，更大的模块度意味着社区结构较强，用户兴趣更相似。Louvain算法[8]是一种基于模块度的图聚合类快速社区检测算法，算法将孤立的用户或歌曲节点一个个地加入获得最大的社区中，直至模块度不再增加。

通常对于二分投影网络大多方法采用在两个单模网络上直接使用Louvain算法，本文利用先前工作[9，10]中进行剪枝操作以减少算法耗费的时间，同时针对二分投影网络模块度进行相关改进。进行社区划分时通过将二分网络节点之间建立二分邻接矩阵，重新连接单模用户网络与项目网络，以此保留原始二分网络中的一些社区结构，将原公式修改如式（2）所示：

（2）

其中，QP表示二分投影网络模块度， 社区c内部邻接矩阵， 这里Bi，j表示二分邻接矩阵，。令  表示社区c内部边的权重， 表示社区c内和连接社区c的所有边的权重。

由于投影时单模网络的节点之间的连接是由原始图中的共享邻居引起的，在投影为单模网络之后，一些结构会丢失。通过改写二分投影网络的模块度计算方式，计算模块度时重新连接原始的二分图，因此包含原始二分网络中的一些信息。将节点n加入社区c中获得的投影模块度增量ΔQP如式（3）所示：

（3）

1.2  二分投影网络更新

当新纪录进入推荐系统时，首先重新计算投影相似性网络中相关用户的相似度，根据相似性矩阵更新用户相似网络[9]。接下来，对于新增记录可以分为两种类型：

（1）新记录节点已经存在于某个社区中。更新过程中将其视为老用户，在这种情况下根据先前的工作在计算模块度时删除某些边缘节点，削减社区划分时的运算时间，使用投影Louvain算法实现局部模块度最大，为用户找到最合适的社区，如果用户的社区发生变化，则代表用户对音乐偏好的迁移[10]。

（2）新记录节点没有社区信息。分别計算新纪录用户节点邻居节点社区边的权重，选取邻居社区中权重最大的社区将新节点更新到社区，以节省算法运算时间。计算新节点加入社区的ΔQP，如果ΔQP小于阈值，则对整个用户相似网络使用投影Louvain算法，重新划分网络中的社区。

1.3  个性化推荐

为了实现冷启动音乐推荐，首先定义用户偏好，本文根据用户对音乐的偏好，而不是使用显式评分信息来寻找相似的用户和音乐。

整个推荐过程，首先根据Pearson相关系数，将二分网络投影到用户与歌曲的单模网络中。利用投影Louvain算法对两个单模网络进行社区检测。其次，在新纪录到来后对社区进行更新，在这个过程中仅有一小部分用户和歌曲项目改变了社区。最后，将偏好信息嵌入到ALS算法中来更新社区集群因子，避免对整个模型重新训练。在算法1中介绍了更新过程：

算法1.Community cold-start

输入： Newrecord

输出： Music recommendation results

1. Cu： User communities; Cu： Musiccommunities

2. p，q is potential factor and s，g is community factor

3.Function Update New Record

4.   Using Projection Louvain Algorithm Update Cu and Ci

5.   Initialize l=1，diff =999

6.   while diff＞l do

7.    for u in Cu do

8.         Calculate

9.     end for

10.    for i in Ci do

11. Calculate

12.end for

13.     diff =

14.l=l+1

15.end while

16. results=ALS（p，q，s，g，Cu，Ci）

17. Return results

18.end Function

2  实验和讨论

在本节中，将通过一系列实验来演示算法的性能。将基于社区检测的冷启动算法（Community cold-start）与传统的SVD组推荐算法[11]以及一种考虑用户和项目之间的协作关系改进的在双向网络中聚类的方法Bipartite-cluster[12]和进行了比较，验证了该算法的有效性。实验使用三个现实世界的大规模数据集评估所有的模型，第一个是Million Song，第二个数据集是Yahoo Music，除此之外还使用了电影评分数据集MovieLens数据集，采用均值绝对误差（MAE）和准确度（Precision）用于衡量预测等级与真实等级的接近程度。为了消除随机性的影响，所有实验均在相同的条件下进行，实验重复10次取平均值。

2.1  评价指标

音乐推荐系统的主要目的是预测用户的基本兴趣和偏好，并向用户推荐合适的项目，以便从数量越来越多的音乐中找到喜欢的歌曲。有很多指标可以衡量推荐系统的各个方面。这里使用两种流行的度量标准，均值绝对误差（MAE）和准确度（Precision）用于衡量预测等级与真实等级的接近程度。对MAE和Precision定义如式（4）和式（5）所示：

（4）

（5）

其中，

2.2  实验结果

在3个真实用户评价数据集中分别计算MAE。对于投影网络中较小的群组，将它们分组为一个特殊的社区。数据前80%用于训练，后20%用于验证推荐准确性。通过对不同数据集的MAE计算，得到如表1所示的结果。

从表1中可以看出，在3个相关数据集中计算用户预测评价与真实评价的数据，在评价数据较多的较密集的MovieLens和Million Song数据集Community cold-start算法较好，Bipartite-cluster算法次之，SVD算法最差。在评价数目较少的和Yahoo Music数据集中Community cold-start和Bipartite-cluster算法性能差别不大，但是都要比SVD性能更强。

为了验证推荐歌曲的性能，本文还在Yahoo Music数据集对准确度（Precision）和运行时间进行测试，在测试集中随机选择5名用户，分别进行Top5、Top10、Top15、Top20推荐，对每组准确度求平均后获得推荐准确度，预测评分误差小于0.5时按照预测与实际评分相等处理。图2显示了三种算法在不同推荐项目数的准确度，推荐歌曲的数目设置为[5，10，15，20]。

当设置推荐音乐个数为5时，Community cold-start算法推荐准确度为44%比其他两种算法分别高2%和4%左右，随着推荐歌曲的数目逐渐增多，三种算法推荐歌曲的准确度都在下降，但是基于社区的冷启动算法趋于稳定保持了较高的准确度。

在图3中第一批数据到达音乐推荐系统时，由于要对二分网络进行相似度计算及投影操作，因此基于社区检测的冷启动算法消耗时间比其他两种算法耗时长。随着新纪录越来越多，基于社区检测的冷启动算法只需要更新社区中的小部分，Bipartite-cluster算法需要重新对用户和歌曲项目进行聚类，SVD算法每次都需要进行大规模矩阵运算，因此SVD算法消耗的时间成倍增加，在整个过程基于社区檢测的冷启动算法消耗时间较少。根据以上内容可以得出以下结论：对于评价数据密集的数据集三种算法的MAE得分相似，对于数据稀疏和遇到新用户/项目时基于社区检测的冷启动算法具有比其他方法更高的准确性，并且运行时间较短。

3  结  论

本文针对音乐推荐系统中的冷启动问题提出了讨论与分析，提出了一种基于社区结构的改善音乐推荐系统中的冷启动方法，首先将输入用户与音乐二分网络进行投影，降低后续复杂度，然后使用改进的投影Louvain算法得到用户和项目两个单模网络社区划分结果。新纪录到来时通过更新一部分网络来完成对新纪录的推荐，通过3个真实的用户评价数据集验证了方法的有效性。

本文虽在一定程度缓解新记录遇到的冷启动问题，但是实际生活中用户可能对不同流派音乐的感兴趣，而本文仅将用户划分到单一社区，未来将探索重叠社区划分算法解决冷启动相关问题，满足用户同时喜欢不同分类音乐的需求。同时本文面对大规模数据进行推荐时耗时较长，需要使用并行计算对推荐过程进行加速。下一步将把以上两点作为研究方向。

参考文献：

[1] 于鹏华.数据数量与质量敏感的推荐系统若干问题研究 [D].杭州：浙江大学，2016.

[2] FUNK S. Netflix update：try this at home [EB/OL].（2006-12-11）.http：//sifter.org/simon/journal/20061211.html.

[3] 朱传亮.基于社交关系和社区结构的协同过滤推荐算法研究 [D].重庆：重庆邮电大学，2019.

[4] 张凯涵，梁吉业，赵兴旺，等.一种基于社区专家信息的协同过滤推荐算法 [J].计算机研究与发展，2018，55（5）：968-976.

[5] 张川.基于内容和用户行为的个性化微博推荐算法研究与实现 [D].北京：北京邮电大学，2018.

[6] SHI L ，ZHAO W X ，SHEN Y D. Local Representative-Based Matrix Factorization for Cold-Start Recommendation [J].Acm Transactions on Information Systems，2017，36（2）：1-28.

[7] 周超，孙英华，熊化峰，等.基于用户和项目双向聚类的协同过滤推荐算法 [J].青岛大学学报：自然科学版，2018，31（1）：55-60.

[8] BLONDEL V D，GUILLAUME J，LAMBIOTTE R，et al.Fast unfolding of communities in large networks [J].Journal of Statistical Mechanics：Theory and Experiment，2008（10）：1-12.

[9] 陈东明，严燕斌，黄新宇，等.基于二分网络社团划分的推荐算法 [J].东北大学学报：自然科学版，2018，39（8）：1103-1107.

[10] 夏玮，杨鹤标.改进的Louvain算法及其在推荐领域的研究 [J].信息技术，2017（11）：125-128.

[11] BI X，QU A，WANG J，et al. A Group-Specific Recommender System [J].Journal of the American Statal Association，2017，112（519）：1344-1353.

[12] 王金.基于SVD++的协同过滤群组推荐算法研究 [D].金华：浙江师范大学，2018.

作者简介：曹珂崯（1994—），男，汉族，山东鄄城人，助教，硕士，研究方向：网络安全、人工智能。

收稿日期：2022-08-09