基于FCM用户聚类的协同过滤推荐算法

赵学健，张雨豪，陈 昊，刘 旭，李朋起

(1.南京邮电大学 现代邮政学院，江苏 南京 210003；2.南京邮电大学 通信与信息工程学院，江苏 南京 210003；3.南京邮电大学 物联网学院，江苏 南京 210003)

0 引 言

信息技术和互联网技术的迅猛发展，使得数据量呈指数性爆炸，人民逐渐从信息匮乏的时代走入了信息过载的时代[1]。无论是信息生产者还是销售者都遇到了很大的挑战，对于消费者而言，海量的数据筛选，获取有效信息越来越困难；生产者为了满足客户需求，生产有价值的信息，变得越来越困难。推荐算法是一种有效的信息处理工具，通过用户的历史行为信息，将用户和商品联系起来，解决信息过载的问题。目前，推荐算法已经成功应用到电子商务、在线音视频网站以及社交网络平台等各个领域。亚马逊的前首席科学家Andreas Weigend提及亚马逊有20%～30%的销售来自于推荐系统[2]。

推荐算法是推荐过程的重要组成部分，为推荐系统的核心内容。目前有许多种推荐算法，常见的推荐算法有基于人口学的推荐算法、基于内容的推荐算法、基于关联规则推荐算法、协同过滤推荐算法、混合推荐算法。而协同过滤推荐算法是目前发展最为成熟、应用最为广泛的个性化推荐技术之一。协同过滤算法可以分为基于内存(memory-based)的和基于模型(model-based)的两类[3]。其中基于内存的协同过滤推荐算法又可以分为基于用户的协同过滤算法和基于项目的协同过滤算法。

1 研究现状

随着电子商务深入人心，用户和项目的数量急剧增加，这使得协同过滤推荐算法计算量巨大，时间复杂度和空间复杂度都极大。另一方面，单个用户所关注的项目通常都很少，这又导致用户的评分矩阵极其稀疏，使得推荐系统的精度大大降低。近年来，研究者开始借助聚类方法来解决协同过滤推荐过程中的数据稀疏性和推荐精度降低的问题。

文献[4]提出了一个新的基于Web的推荐系统，该系统基于用户在Web页面上浏览的顺序信息，采用模糊C均值聚类算法为目标用户确定相似用户，并评估每个网页的权重，来预测推荐用户的下一次访问网页，极大提高了现有推荐系统的精度。

文献[5]提出一种用于医学图像模糊聚类与直觉模糊推荐结合的混合推荐模型-HIFCF(hybrid intuitionistic fuzzy collaborative filtering)。该模型比传统的模糊集合或单纯的推荐系统具有更好的预测精度。

文献[6]提出一种新的社交推荐模型，该模型首先将描述多个领域用户偏好的用户偏好矩阵形式化，然后利用偏距离策略模糊C-均值聚类算法-PDSFCM (partial distance strategy fuzzy c-means)得到用户聚类分组，然后设计了一个基于聚类的社交正则化项，将聚类关系与传统的矩阵分解模型进行融合，用以进一步提高推荐算法的精度。

文献[7]提出一种新的基于聚类的协同过滤方法-CBCF(clustering-based collaborative filtering)，该方法基于用户评分数据建立激励/惩罚用户模型，对用户进行聚类，在不需要更多先验信息的情况下，提高了推荐的准确性。

文献[8]将单领域基于聚类的矩阵分解方法扩展应用到多领域推荐，所提出的推荐方法可以更有效地利用来自辅助域的数据来获得更好的推荐效果，特别是对于冷启动用户。

文献[9]在2010年通过提出一种基于用户偏好模糊聚类的协同过滤推荐，用以解决推荐过程中的数据稀疏性和伸缩性。该方法将用户项评分矩阵转换为用户类矩阵，因此大大提高了矩阵中数据的密度。然后，使用模糊C均值算法将用户模糊地分为不同的组。采用模糊C均值聚类可以让每个用户属于不同的组，可以更为有效地捕获用户的各种偏好。

文献[10]在2015年提出了一种结合FCM和Slope One算法[11]的协同过滤推荐方法，该方法针对推荐算法的数据稀疏性问题，首先使用基于FCM聚类的Slope One算法来预测未评分的数据，然后通过基于用户的协同过滤推荐算法来实现推荐。

文献[12]为了提高推荐质量，将信任关系融合到推荐系统中，采用模糊C聚类算法，对信任关系进行聚类。利用信任类预测用户间的隐式信任，最后将信任关系与用户-项目关系线性融合进行推荐。实验表明该算法能够大幅度地改进推荐质量，提升算法的时间效率。

文献[13]为了克服评级数据的稀疏性问题，提出了一种新颖的稀疏性消除方法，该方法结合了评级和电影题材特征，应用模糊C均值聚类技术对电影进行聚类。该方案结合了评分和电影的题材来预测未评分数据，有效提升了推荐质量。

文献[14]提出了一种基于对用户真实性信息应用模糊C均值聚类的协作过滤模型。该文献提出一种新的度量用户相似度的方式，该公式结合了用户的使用组合系数对模糊真实性信息进行评级，在数据稀疏和冷启动条件下，推荐效果更佳。

文献[15]针对推荐算法的数据稀疏性和冷启动问题，将聚类算法和关联规则生成算法相结合，首先根据用户相似度对评分矩阵进行聚类，然后将聚类数据转换成布尔数据，并生成高效的关联规则，最后进行基于规则的推荐。实验表明，该方法不仅降低了推荐系统的稀疏度，而且提高了推荐系统的精度。

通过上述分析，可以看出当前借助聚类方法的协同过滤推荐通常只考虑了用户的显性特征进行聚类，没有考虑到项目的隐性特征；另一方面，当前采用模糊C均值聚类方法对用户进行聚类时，该算法容易收敛于局部极小值点，有时难以取得目标函数的全局最小值。因此，该文提出一种基于FCM用户聚类的协同过滤推荐算法GAFCM-CF(genetic algorithm based fuzzy c-means collaborative filtering)。该算法首先结合用户评分和项目特征构建用户特征偏好矩阵，然后采用模糊C均值聚类算法对用户进行聚类。此外，该算法为了防止模糊C均值聚类算法收敛于局部极小值，影响推荐质量，采用遗传算法对模糊C均值聚类算法进行了改进，以防止模糊C均值聚类算法出现局部最优解。实验结果表明，所提出的基于改进FCM的协同过滤推荐算法GAFCM-CF相比于传统的基于用户的协同过滤推荐算法具有更好的推荐质量。

2 算法理论基础

2.1 基于用户的协同过滤推荐算法

基于用户的协同过滤算法是推荐系统中比较古老的推荐算法，这个算法的诞生标志着推荐算法的诞生。该算法利用目标用户的历史行为信息，挖掘与目标用户具有高相似度的近邻用户集合，然后根据用户对此项目的评分来预测目标用户对该商品的相应的评分，之后再从预测的评分中选择靠前的Top-K个项目推荐给用户。

基于用户的协同过滤算法中，用户-项目评分矩阵Rm×n是算法的基础，如表1所示。该矩阵中，每行对应一个用户，每列对应一个项目，每个矩阵元素ri,j表示用户i对项目j的评分，当用户没有对项目进行评分时，ri,j为0或者NULL。

表1 用户项目评分表

在基于用户的协同过滤推荐算法中，可以选择皮尔逊相关系数、余弦相似度等不同的相似度计算方法。皮尔逊相关系数计算方法如公式(1)所示：

(1)

2.2 模糊C均值聚类算法

模糊C均值聚类算法(fuzzy c-means，FCM)是在硬C均值聚类算法模型基础上融合了模糊理论的精髓进一步推理得到的。硬C均值聚类算法要求每个用户只能明确属于某一个类之中，然而模糊C聚类可以提供更加灵活的聚类结果，它可以将每一个目标对象划分到多个类中。

假设数据集X={x1,x2,…,xn}⊂Rd×n，其中n为数据集的个数，d为数据集的维度。模糊C均值聚类算法将数据集划分成k个子集，则对应生成模糊划分矩阵U，cj(j=1,2,…,k)为每个聚类的中心，可记录为C，μi,j是第i个样本对应第j类的隶属度函数，则基于隶属度函数的聚类损失函数如公式(2)所示：

(2)

其中，m是加权指数，也可以称为平滑系数，一般取值为2。

模糊C均值聚类算法首先计算各个用户和聚类中心之间的距离，然后计算出用户对各聚类中心的隶属度矩阵，通过比较用户在各个聚类中心隶属度的大小，将用户分配到隶属度最大的用户簇中，使得在同一个用户簇之中用户与用户的相似度最高，降低不同用户簇中用户之间的相似度。使得聚类函数最小的必要条件为cj和μi,j分别满足公式(3)和公式(4)：

1≤i≤n,1≤j≤c

(3)

(4)

3 GAFCM-CF算法

该文提出的GAFCM-CF算法包括数据预处理，用户特征偏好矩阵构建，矩阵归一化处理，GAFCM聚类，用户相似度计算，目标项目评估及推荐六个步骤，如图1所示。算法的核心是用户特征偏好特征矩阵的构建和融合遗传算法对模糊C均值聚类算法进行改进，实现对用户的聚类分析，防止模糊C均值聚类算法出现局部最优解。

图1 改进FCM的协同过滤流程

3.1 数据预处理

数据预处理主要负责从原始数据中提取用户特征和项目特征数据并进行数据清洗操作，获得特定格式的数据集，并构建项目特征隶属矩阵和用户项目评分矩阵。

3.2 构建用户特征偏好矩阵

时间复杂度、空间复杂度高以及评分矩阵稀疏问题是协同过滤算法目前所面临的主要问题。为了解决用户评分矩阵的稀疏性问题，GAFCM-CF算法通过利用用户项目评分矩阵和项目特征隶属矩阵来构建用户特征偏好矩阵，构建方法如图2所示。

图2 用户偏好特征矩阵构建过程

图2中，矩阵UIn×m为用户项目评分矩阵，矩阵IFm×k为项目特征隶属矩阵，矩阵UFPn×k为用户特征偏好矩阵。可以通过用户项目评分矩阵和项目特征隶属矩阵聚合来构建用户特征偏好矩阵。项目特征隶属矩阵IFm×k中的元素取值为0或1，满足公式(5):

(5)

用户u对项目的评分向量为ru=(ru,1,ru,2,…,ru,m)，项目i对应特征的隶属向量为fi=(f1,i,f2,i,…,fm,i)，Rui计算过程如式(6)所示：

(6)

该方法中用户项目评分矩阵通常都是稀疏矩阵，这是由于用户数量和项目数量极多，而单个用户关联的项目数量极少。项目特征隶属矩阵中k的取值通常远小于用户评分矩阵中项目的数量m，因此通过该方法获得的用户对项目特征的偏好矩阵相对于用户项目评分矩阵维度得到了极大降低，有利于降低推荐算法的时间和空间复杂度。

3.3 归一化处理

对UFP矩阵进行min-max归一化处理，将矩阵各元素数值映射到区间[0，1]，映射公式如下所示：

(7)

其中，xi,j为矩阵第i行第j列对应的元素值，在UFP矩阵中表示用户i对项目特征j的偏爱程度，xmin为所有用户对项目特征偏爱程度中的最小值，xmax为所有用户对项目特征偏爱程度的最大值。

3.4 GAFCM聚类

GAFCM-CF算法为了达到快速收敛并避免局部最优，将遗传算法与FCM的算法融合，通过FCM算法使数据快速高效地趋于各自的极值点，又可以通过遗传算法摆脱数据在收敛过程中可能陷入的局部最小值的问题[16]。

GAFCM聚类的具体步骤如下：

步骤1：对原始数据进行预处理，构建用户偏好特征矩阵UFP并对其进行归一化处理。

步骤2：参数初始化，初始化GAFCM算法的相关参数，包括种群大小M，交叉概率Pc，变异概率Pm，最大迭代次数tmax，聚类簇数c，隶属度因子m，收敛精度ε。

步骤3：编码及种群初始化，根据公式进行编码，并随机产生一个种群X，X中有n个研究对象作为初始个体，即X=[x1,x2,…,xn]。

步骤4：计算个体适应度：

(8)

步骤5：对当前种群执行选择、交叉和变异操作，产生新一代个体。

步骤6：若t=tmax，遗传算法结束，输出最终的数据，并转入步骤7；否则，令t=t+1，并返回步骤4。

步骤7：根据全局最优解模糊划分整个数据集，输出聚类中心矩阵，实现用户聚类划分。

3.5 用户相似度计算

为计算用户的相似度，GAFCM-CF算法通过综合利用用户特征偏好矩阵以及用户项目评分矩阵来实现，既包含原始用户项目评分矩阵的显性信息，又考虑到用户对项目特征偏好的隐性信息，如公式(9)所示：

Sim(u,v)=λSim1(u,v)+(1-λ)Sim2(u,v)

(9)

其中，λ是权重因子，取值范围为(0,1)；Sim(u,v)表示用户u和用户v的综合相似度；Sim1(u,v)表示通过公式(1)计算得到的相似度，是使用原始用户项目评分矩阵得到的；Sim2(u,v)表示使用用户对项目特征偏好矩阵得到的相似度，可以通过公式(10)获得：

Sim(u,v)2=

(10)

3.6 目标项目评估

用户u对项目i的评分计算公式为：

(11)

4 实验分析

4.1 数据集描述

该文采用MovieLens 100k数据集验证算法的性能。该数据集包括1 682部电影中的943位用户的100 000个评分，数据集稀疏度为93.7%(用户未评分数量占用户最大评分数量的比例)。用户对电影的评分区间为1～5分，每个用户至少评分20部电影，用户对某电影的评分值越高表明用户对该电影喜爱程度越大。

该文将原始数据集随机划分为5部分，使用5折交叉验证方式，每次将其中4部分用于训练，剩下的1部分用于测试，将5次实验的平均值作为实验结果。

4.2 实验设置及评价指标

该文主要通过平均绝对误差(mean absolute error，MAE)、准确率(Precision)和召回率(Recall)三个指标对算法的性能进行分析。

MAE是衡量预测评分的准确性的重要指标，通过比较预测评分和真实评分之间的平均绝对误差计算得出。MAE值越小，则表示预测评分与真实评分越接近，算法精度也就越高。Precision表示正样本在预测为正的样本中所占的比例，即用户发生行为项目占推荐项目的比例。Recall表示预测为正样本占正样本的比例，即推荐项目占用户产生行为项目的比例。显然，Precision和Recall越大，说明算法的推荐精度越高。

MAE可以通过公式(12)进行计算：

(12)

其中，pu,i表示用户u对项目i的预测评分，ru,i表示用户u对项目i的真实评分,n表示用户u所评分的项目的数量。

Precision可以通过公式(13)进行计算：

(13)

Recall可以通过公式(14)进行计算：

(14)

上述公式(13)和公式(14)中，U表示所有项目的集合，R(u)表示给用户u推荐的项目集合，T(u)表示用户u发生行为的项目的集合。

实验相关参数设置如下：模糊聚类分类数c=8，隶属度因子m=2，迭代次数t=50，交叉概率Pc=0.6，变异概率Pm=0.1，收敛精度ε=0.000 1。

4.3 实验结果与分析

首先，对GAFCM-CF算法性能随权重因子λ的变化情况进行了分析。该组实验将相似用户数量k值设置为20，如图3所示，在相似用户数量k=15时，随着λ取值逐渐增大，准确率和召回率变化趋势均为先增大后减小，并且在λ=0.4时，准确率和召回率达到峰值，分别为0.251和0.129。由图4可以看出，随着λ取值逐渐增大，平均绝对误差MAE变化趋势为先减小后增大，并且在λ=0.4时，平均绝对误差取得最小值0.466。

图3 λ取值对Precision和Recall的影响分析

图4 λ取值对MAE的影响分析

其次，将GAFCM-CF算法与文献[6]提出的PDSFCM算法、User-CF算法的进行性能对比，分析了三种算法的MAE、Precision和Recall随相似用户数量k的变化情况。该组实验权重因子λ取值均设置为0.4。

由图5可以看出，GAFCM-CF算法、PDSFCM算法和User-CF算法的MAE均随着相似用户数量k的增大而减小。在k值相同的情况下，GAFCM-CF算法的MAE均比PDSFCM算法与User-CF算法的MAE要小，表明GAFCM-CF算法比User-CF算法和PDSFCM算法具有更好的精度。

图5 MAE对比分析

由图6和图7可以看出，GAFCM-CF算法、PDSFCM算法及User-CF算法的Precision和Recall均随着相似用户数量k的增大而增大。在k值相同的情况下，GAFCM-CF算法的预测准确率和召回率都比User-CF算法和PDSFCM算法的预测准确率和召回率要高，表明GAFCM-CF算法比User-CF算法和PDSFCM算法具有更好的推荐效果。

图6 Precision对比分析

图7 Recall对比分析

5 结束语

针对传统协同过滤推荐算法中存在的数据稀疏性及推荐准确率低的问题，提出了一种基于改进FCM的协同过滤推荐算法GAFCM-CF。实验结果表明，相比于传统的基于用户的协同过滤推荐算法，该算法具有更高的推荐质量以及推荐准确率。未来工作中，将考虑进一步挖掘用户隐藏信息，进一步提升推荐算法的准确率；另一方面，将对算法的复杂度和其他方面的推荐性能，比如推荐物品的覆盖率、流行度、惊喜度等进行更全面的评估。