结合用户聚类与改进用户相似性的协同过滤推荐

顾明星，黄伟建，黄 远，生 龙，申 超，张梦甜

河北工程大学 信息与电气工程学院，河北 邯郸056038

1 引言

随着互联网和电子技术的快速发展，以用户和商品为核心的信息生产模型使得网络信息量呈现爆炸式增长，人类进入了“信息过载”的时代。推荐算法作为解决“信息过载”的最有效手段之一，得到了广泛的应用[1-2]。但是随着用户和项目规模的扩大，推荐算法面临着严重的数据稀疏性问题[3]。以推荐系统在电子商务中的应用为例，通常用户购买的商品总量只占据网站商品总量的1%，并且用户仅仅对其中的极少数项目进行评分，用户项目评分矩阵极其稀疏[4]。同时，传统的协同过滤算法在计算用户间相似性时往往只强调用户间的评分相似度，使得推荐算法在实际应用中面临着用户相似性计算不准确，商品推荐的实时性低的问题[5]，严重影响了推荐算法预测准确率。

为了解决上述问题，国内外的相关学者提出了多种改进方案。首先为了解决数据矩阵的稀疏性问题，大量基于聚类的推荐算法被提出。文献[6]采用谱聚类算法，利用谱聚类将兴趣类似的用户划分为一簇，然后在簇内为目标用户进行项目推荐。文献[7]首先采用Kmeans算法对用户属性特征进行聚类，然后利用SlopeOne算法对矩阵进行缺值填充，最后利用协同过滤思想进行评分预测。文献[8]采用吸引子传播算法对用户属性进行聚类，相比于一般聚类算法而言，该算法不需要提供聚类中心数，因此聚类效果较好，但时间和内存开销过高。其次，为了改善推荐算法的预测准确性和推荐物品的实时性，文献[9]在传统的皮尔逊相似度中引入惩罚因子和时间权重。文献[10]先采用密度峰值聚类算法（Clustering by Fast search and find of Density Peaks，CFDP）对项目进行聚类以降低数据稀疏性，然后在计算项目评分时引入时间权重，降低了用户的兴趣动态变化的影响。文献[11]引入了社交网络中的用户信任关系，将传统的用户评分相似度与用户信任度进行融合，从而获得更加精确的用户相似度计算方式。

上述算法虽然在一定程度上提高了预测准确性，但对用户信息的挖掘仍然不够充分。因此本文提出了一种结合用户属性聚类与改进用户相似性的协同过滤推荐算法。算法首先利用K-means++算法对用户属性进行聚类，从而获得目标用户所在的评分矩阵；其次对用户的评分相似性引入时间因素，以增大用户最近行为项目的协同推荐能力；然后引入用户信任误差，计算改进后的用户直接信任度和间接信任度；最后将基于时间因素的用户评分相似性和改进的用户信任度合理地结合，从而改善用户间的相似性。通过改进后的用户相似性公式，利用协同过滤思想对目标用户未评分项目进行预测评分，产生推荐列表。

2 传统的协同过滤算法

传统的协同过滤算法基本步骤是：首先利用已有的用户历史行为数据信息，构建用户-项目评分矩阵；然后计算用户之间的相似度并选取相似度较高的用户作为目标用户的近邻集；最终在进行评分预测后按照Top-N原则对用户进行推荐[12]。该算法的流程如图1所示。

图1 Item_CF算法流程图

2.1 构建用户-项目评分矩阵

本文构建用户-项目评分矩阵Cm×n,users:{u1,u2,…,um}表示拥有m 个用户的集合；items:{i1,i2,…,in}表示拥有n 个项目的集合；cij表示用户i 对项目j 的实际评分，若用户i 对项目j 未评分，则cij记0。评分矩阵C如下：

2.2 用户评分相似性的计算

用户评分相似性的计算是以用户-评分矩阵为基础的，将评分矩阵中的每一行作为用户的评分向量来表示用户的实际兴趣。因此，计算用户评分相似性的本质就是计算用户评分向量之间的距离。传统的协同过滤算法中，计算相似度的方式有很多，主要包括余弦相似度、修正余弦相似度和皮尔逊相关系数[13]。本文采用最为常用且效果更好的皮尔逊相关系数作为用户间相似度计算公式[14]，如式（1）所示。

其中，sim(a,b)表示用户a 与b 的相似度，I 表示用户a与用户b 评分项目的交集，分别表示用户a 与b的平均评分。

2.3 预测评分

在获得用户a 与所有用户的相似度后，将相似度最高的前h 个用户作为其近邻集，并根据式（2）对a 未评分的项目预测评分。

其中，pa,i表示用户a 对项目i 的预测评分，G 表示用户a 的近邻集。

3 本文算法

3.1 基于K-means++的用户属性聚类

为了降低用户评分矩阵的稀疏性，本文首先对用户属性进行聚类分析，将属性相似的用户划分到同一簇内。K-means++算法是一种基于质心的聚类算法，是在K-means算法的基础上优化了初始质心的选择方式，使初始质心相互间距离尽可能得远[15]。 K-means++算法具有算法高效率、易实现、适合挖掘大规模数据集的特点[16]，因此本文选取K-means++算法作为聚类手段。

在对用户属性进行K-means++聚类前，首先需要对用户的属性信息进行预处理，过程如下。

步骤1 从数据集中获取用户的属性信息：UserAttr={age,sex,job}。

步骤2 对非数值的离散型数据进行编码，将文本特征进行数值化。在用户属性中，根据埃里克森八阶段理论[17]，将年龄划分为以下4个年龄段（数据集中用户年龄最小为15岁）：“15～18岁”编码为“1”，“19～40岁”编码为“2”，“41～65 岁”编码为“3”，“66 岁以上”编码为“4”；性别为“F”和“M”，编码为“0”和“1”；职业属性一共包含21种类别，因此构建长度为5的“01”编码串(21 ＜25)，并按照职业出现的顺序进行编码。例如在本文选用的数据集中，首先出现“technician”职业，则该职业编码为“00001”，其次出现为“writer”，则该职业编码为“00010”，然后出现“executive”，则该职业编码为“00011”，其余职业的编码以此类推。最后对用户的属性编码进行拼接。例如：用户属性为“age=42||sex=M||job=executive”，则该用户的属性编码串为“3100011”。

步骤3 对用户属性编码进行Embedding。Embedding通过将原稀疏向量与固定转换矩阵做内积变化，从而将高维稀疏特征向量向低维稠密特征向量转换。

步骤4 对用户属性进行预测处理后，最后得到用户属性矩阵p。

算法1 K-means++聚类算法

输入：用户属性矩阵p，聚类数目k。

输出：k 个聚类。

步骤1 随机选取一个样本作为初始质心center1；

步骤2 选取p 中的每一个样本点dx，计算该点与当前最近一个质心的距离dist(dx)；

步骤3 利用式（3）计算每一个样本点dx作为下一个质心的概率：

步骤4 将概率最高的点，作为下一个聚类质心点centeri；

步骤5 重复步骤2～步骤4直至找到预设的k 个质心；

步骤6 得到k 个用户簇并输出。

采用K-means++算法对用户属性进行聚类后，将目标用户所在的用户簇对应至用户评分矩阵，从而得到缩小规模的用户-项目评分矩阵。如果不经过该预处理，则评分数据会占用较大的内存，且严重降低协同推荐算法的执行效率和推荐准确性。

3.2 时间因素

传统的协同过滤算法计算用户间的相似度时仅仅考虑用户对项目的历史评分记录，忽略了用户对项目兴趣的动态变化，在当前各类的用户行为数据集中，用户行为的时间通常是被系统准确记录的，因此可以考虑用户对某一项目的兴趣程度会受到时间因素的影响。一般而言，用户最近访问的项目往往更能准确反映用户当前的兴趣特征。因此本文引入时间因素增大用户最近访问商品的协同推荐能力，相关定义如下。

定义1 Tfirst：用户第一次对商品进行评分的时间。

定义2 Ti：用户对商品i 进行评分的时间。

定义3 Tall：用户使用该系统的总时长。

根据分析，用户对某一项目的兴趣会随着时间的推移逐渐弱化，并趋于一个稳定值，即用户兴趣与时间呈现非线性负相关关系，这与心理学家艾宾浩斯发现的遗忘规律相似[18]，因此本文采用遗忘规律来量化时间因素，则用户u 对项目i 的时间因素权值的计算公式如下所示：

然后将时间权重与皮尔逊相似度计算公式结合，公式如下所示：

3.3 改进用户信任度

传统的用户间信任关系中，用户a 信任用户b，则用户b 也会信任用户a，并且双方的信任值是相同的。但结合实际，用户a 与用户b 之间的信任是不一定对等的。因为两者的评分项目的数量不一定相同，用户的评分尺度也不一定相同[19]。

3.3.1 直接信任度的计算

直接信任度是目标用户与其他用户的直接信任关系，对于用户a 与用户b，用户a 对用户b 的直接信任度可由下列公式计算。

其中，DTrust(a,b)表示用户a 对用户b 的直接信任度值。但是用户之间的信任度仅从用户共同评分项目的数量上来判断是不准确的，如表1所示。

表1 极端评分数据

由式（6）可得DTrust(a,b)=1，即用户a 与用户b 是极其信任的。但实际情况是，用户a 对列举的4种物品评价极高，用户b 则极低。说明单从用户间共同评分项目的数量上计算用户间的相似度是不准确的。

为了缓解用户间对物品的实际评分存在的差异对用户信任度的影响，本文定义信任误差值，公式如下所示：

其次，根据信任误差值定义用户交互响应因子数，公式如下所示：

其中，t 表示正响应因子数，记录用户a 与用户b 间的评分差异较小的次数；f 表示负响应因子数，记录两者评分差异较大的次数。若两者评分差异小，则t+1 →t，反之f+1 →f 。

用户间的信任是随着正负响应因子数呈非线性变化的量，用户间正响应因子数越多，相互信任程度越高，反之越低。因此，可以利用Logistic 函数将正负响应因子数进行恰当融合。Logistic函数是一种”S”形函数，在区间（0，1）变化，能充分抑制两端的值，且对中间值变化敏感[20-21]，公式如下所示：

则改进的直接用户信任度公式如下：

根据式（10）可以得出，用户间信任度随着正响应因子数的增加而提高，随着负响应因子数的增加而降低。

3.3.2 间接信任度的计算

若用户a 与用户c 共同评分的项目交集为空集，则用户a 与用户c 之间不存在用户直接信任度，此时可以采用信任传递的方式获取两位用户的间接信任度：假设至少存在一个中间用户群user={ub,ud,ue,…,uv}，使得用户a 与用户ub存在直接信任关系，用户群user 中相邻的用户存在直接信任关系，用户uv与用户c 存在直接信任关系，则可以推论出用户a 与用户c 之间存在间接信任度[22]。在计算用户间的间接信任度时，若存在多个用户群，则选取传递人数最少的中间用户群来计算间接信任度。用户间接信任度计算公式如下所示：

其中，| user|表示传播路径最短的中间用户群的人数。

同时，根据“六度区隔”理论[23]，设定| user|+1 ≤6，若大于6则PTrust*(a,c)=0。

综合了用户直接信任与用户间接信任，则用户间的最终信任表达公式如式（12）所示：

3.4 改进的用户相关性

在利用式（5）获得基于时间因素的用户评分相似度与式（12）获得改进的用户信任度后，本文将两种影响推荐效果的因素相结合，得到最终的用户间的相关性，公式如下：

当用户间的评分相似度为0时，则利用信任度表示用户间相关性；当用户间没有信任度时，则用户间不存在相关性；当两种因素均不为0 时，则用户间的相关性会随着两种因素的增加而提高。

最后预测出用户对项目的评分，公式如下所示：

其中，G*表示与用户a 相关性最高的前h 个近邻用户。

3.5 本文算法流程

算法2 结合用户属性聚类与改进用户相似性的协同过滤算法

输入：目标用户a，用户-用户评分矩阵C，用户评分时间信息T 。

输出：目标用户a 的推荐列表。

步骤1 利用算法1 的K -means++聚类算法获得目标用户a 所在的用户-用户属性簇S，并对应到相应的用户-评分矩阵中得到簇S′。

步骤2 在簇S′中，遍历除了用户a 外的用户，利用式（5）计算与用户a 的相似度。

步骤3 在簇S′中，遍历除了用户a 外的用户，利用式（12）计算与用户a 的信任度。

步骤4 在计算出其他用户与用户a 的相似度与信任度后，利用式（13）计算与用户a 的相关性。

步骤5 将与用户a 相关性最高的前h 个用户作为a 的近邻集。

步骤6 在用户a 的近邻集内，利用式（14）预测目标用户a 对未评分项目的评分。

步骤7 将预测评分最高的项目由高到低排序，并将前Top-N 个项目作为目标用户a 的推荐项目集。

4 实验与讨论

4.1 数据集

本文选取MovieLens ml-100K 电影数据集[24]，该数据集由明尼苏达大学GroupLens学习组发布，用户评分数据集中包含943名用户对1 682部电影的共约10万条记录，其中包括用户ID、电影ID、用户对项目的评分以及相应评分的时间。用户的评分区间为[1，5]，评分越高，则评价越高。用户属性数据集包括用户的ID、年龄、性别、职业。本文采用五折交叉实验法，将80%的数据用作训练样本，20%的数据用作测试样本。

4.2 评价指标

本文采用推荐算法实验中最为广泛的评价准则——平均绝对误差（Mean Absolute Error，MAE）作为实验的评分预测指标[25]，公式如下：

4.3 实验结果与分析

为了获取最佳聚类数k，将目标用户的近邻数从20变化到90，间隔为10。根据文献[7]和文献[26]的研究情况，本文将用户划分为k=5,6,7,8,9 个聚类，然后在对应不同的聚类数下计算不同用户近邻数下的MAE 值，重复实验10 次，并取其结果的平均值作为最终结果。实验结果如图2所示。

图2 不同聚类数下本文算法的MAE对比图

通过图2 可以得出，当聚类数目k=7 时，本文算法的推荐准确性更高。因此，本文实验聚类簇设定为7，聚类后每个簇中用户的数量如表2所示。

表2 不同类中的用户量

同时为了验证不同聚类数k 下K-means++算法的实际聚类效果，本文采用轮廓系数[27]作为评价聚类质量的标准。不同聚类数k 下的轮廓系数值如表3所示。

表3 不同聚类数下的轮廓系数

由表3可知，当聚类数k 为7时，K-means++算法的轮廓系数最高，即聚类效果最佳。

在确定了用户聚类数为7后，对用户相似性的分布进行实验。本文分别将皮尔逊相关系数与改进的用户相关性作为协同过滤推荐算法的相似度计算公式，实验统计了这两种方法得到不同相似度出现的次数，分布如图3所示。

图3 不同公式对应的用户相似性分布

通过图3可以看出，本文改进的用户相关性得到的相似性分布曲线没有皮尔逊相关性得到的分布曲线平稳和均匀，说明本文的相关性得到的用户相似性更具有个性化。在相似度[0.1，1.0]的范围内，皮尔逊相关系数得到相似度分布在[0.2，0.6]的次数占比69.8%，而本文改进的用户相关性仅占比63.5%。因为改进的用户相关性通过增加用户的评分时间信息和用户信任度，降低了用户评分尺度和评分时间的差异对用户相似性的影响。

为了验证本文提出的算法能有效提高协同过滤算法的推荐质量，本文选取传统的基于用户的协同过滤算法（User-CF）、文献[7]提出的CFUI-CF算法、文献[10]提出的CFDP-CF算法、文献[11]提出的UTLDA-CF算法作为对比算法，仅结合时间因素的本文算法以及仅结合改进用户信任的本文算法对比结果如图4所示。

图4 不同算法的MAE值对比

通过图4可以看出，所有算法的MAE 值，均随着目标用户近邻数的增加而逐渐减少，直到趋于平缓。首先通过观察可以发现，仅结合时间因素的本文算法和仅结合改进用户信任的本文算法能有效改善推荐算法的预测效果，分别比User-CF 的准确率高1.2%和2.9%，但预测效果不如将两者结合的本文算法。在实验范围内的用户近邻数下，本文提出的算法能够提高User-CF的准确率达5.6%，且分别比CFDP-CF、CFUI-CF、UTLDA-CF、仅结合时间因素的本文算法和仅结合改进用户信任的本文算法的MAE 值低0.6%、1.4%、3.1%、4.6%和3.1%，说明本文算法能有效提高推荐系统预测质量。

5 结束语

本文提出了结合用户属性聚类与改进用户相似性的协同过滤算法。首先利用K-means++对用户特征信息进行聚类，其次对皮尔逊相关系数引入用户对项目的评分时间信息，然后改进用户之间的信任关系，最后将引入时间信息的皮尔逊相关系数与改进的用户信任关系进行结合，最终得到改进的用户相关性。实验表明，本文提出的算法能有效提高推荐算法的预测准确性，且有一定的实际意义。