基于用户多种关联信息和项目聚类的推荐算法

孙克雷，沈华理

(安徽理工大学计算机科学与工程学院，安徽 淮南 232001)

随着科学技术的不断进步，网络已经慢慢变成人们获取外界信息的重要工具，使得网络信息正以喷井式的方式增长，大量的网络用户在面对巨大的网络信息时，很难快速方便查询到自己的需求信息。为了解决用户需求很难得到满足的现象，研究者们提出了很多的应对方案，推荐系统就是其中的一种。推荐系统[1-3]的目标是排除掉大量地无用信息，为用户带来个性化的推荐效果。其主要的过程是通过分析用户的历史行为信息，提取出用户的偏好标签，得到一组标签集合，将与用户偏好标签集合相匹配的信息推荐给用户，从而可以过滤掉大量跟用户需求无关地数据，极大地提升了用户体验。

目前推荐技术主要采用基于关联规则的推荐[4]、基于内容的推荐[5]、基于协同过滤推荐(CF)[6]和混合推荐[7]等。几种常用的技术中协同过滤技术运用的最为普遍，传统的协同过滤技术主要由两部分组成：基于数据的协同过滤和基于模型的协同过滤。基于模型的CF通常根据数据进行建模，然后利用模型实现推荐。基于数据的协同过滤又可以分为：基于用户(User-Based CF)[8]和基于项目(Item-Base CF)。随着信息量的不断增加，现在的推荐系统包含有大量的用户和项目，并且系统中的项目和用户数量还在持续的扩大，从而使得评分矩阵变得越来越稀疏，同时还存在新用户的冷启动问题[9]。

对于上述方法存在的不足，研究者们从各个方面来对其进行改善。例如文献[10]提出的一种奇异值分解方法来降低推荐系统数据库的维度，通过减小输入矩阵的维度缓解数据稀疏性。文献[11]采用计算项目相似度的方案用于填充评分矩阵，可以有效减小输入矩阵的稀疏性。文献[12]采用基于项目特征聚类的方法，其主要是按照用户评价过的项目，找到与这些项目最近邻的若干个聚类，并依据聚类结果进行推荐，有效地解决了稀疏性。文献[13]利用k-means算法对项目聚类，找出目标项目的相似近邻项目进行推荐，可以有效降低稀疏性。以上这些解决方案主要通过利用项目属性进行评分矩阵数据填充，可以在有效降低稀疏性问题，但是其目的性主要都放在了解决数据稀疏性。

本文提出一种基于User-Based CF改进算法。该算法不仅将用户自身固有的属性，如用户的年龄、性别、职业，作为计算相似用户的因素，并且通过分析用户与项目间的关联信息，得到用户偏爱项目和用户评价过的项目数量等用户非自身固有属性也作为计算相似用户的因素，以此来排除干扰近邻用户，提高用户间相似度地准确度。通过用户最近邻对项目的评分，预测未评分项目的预评分。然后将预测评分填充到稀疏评分矩阵，再利用协同过滤算法计算得到目标用户对未评分项目地最终预评分。最后依据最终预评分结合项目聚类产生Top-N推荐。

1 基于用户的协同过滤算法

User-Based CF算法主要依据用户的历史行为数据产生推荐，如果一个用户不存在任何历史行为数据，那么该算法将不能计算出该用户地相似近邻用户，也就不能实现对该用户进行项目推荐，这种缺陷称为新用户的冷启动现象。如果一个用户存在历史行为数据，那么就可以利用相似度的计算公式得到与该用户历史行为相似的最近邻，依据最近邻对项目地评分数据来给目标用户未评分地项目进行预评分，按照预评分为目标用户产生Top-N推荐。User-Based CF算法实现比较简单，可分为三步进行描述：构建稀疏评分矩阵模型、计算得到最近邻、预测评分并且产生Top-N推荐。

(1)构建用户-项目评分矩阵模型

首先根据用户历史行为数据，可以建立稀疏评分矩阵Rm×n，如表1所示。其中，m代表用户个数，n代表项目个数。

表1 用户-项目评分矩阵

其中UX是用户X，Ii是项目i，RX，i是用户X对项目i的评分，null表示用户还没有评分的项目，一般初始化为0。从表1可以容易看出，该矩阵存在大量的数据冗余，数据稀疏性严重。

(2) 计算得到最近邻

利用Rm，n矩阵，通过相似度计算公式得到用户之间的相似度，从而构建出用户相似度矩阵Sm，m，计算相似度的常见方法有很多种，例如欧几里得距离公式、曼哈顿距离公式、余弦相似性、修正余弦相似性和Pearson相关系数。此处采用的是Pearson相关系数[14]计算法，计算方法如下

sim(X，Y)=

(1)

(3) 预测评分并且产生Top-N推荐

按照用户之间的相似度，可以选择出与目标用户最相似地前k个近邻用户，利用近邻用户地历史行为数据预判出目标用户未评分项目地预评分，按照预评分向用户进行Top-N推荐。此处计算预评分的方法为加权均值法[15]，公式如下

(2)

2 推荐算法的改进

根据上一节分析，基于用户的协同过滤算法主要存在两个问题：没有最大化利用与用户有关的关联信息和准确度偏低。 为了解决上述问题，在基于用户的协同过滤算法的基础上进行了改进，提出一种基于用户多种关联信息和项目聚类的推荐算法。该算法主要分为两部分，第一部分是利用用户历史行为信息和用户关联信息，构建用户-项目评分矩阵、用户相似度矩阵、填充后的用户-项目评分矩阵。第二部分根据填充后的评分矩阵，结合User-Based CF算法，产生目标用户的最终预评分，并且利用最终预评分通过项目聚类产生Top-N推荐列表。

2.1 填充用户项目评分矩阵

根据用户关联信息能够挖掘出用户间共性，进而可以确定与其相似的近邻用户。因为用户有些自身固有属性特征是长期不变的，例如，地理位置、职业、年龄、性别等，这些属性特征本身是没有特殊含义的，但是如果和一些场景联系起来，就能够通过这些特征反应出一个群体的兴趣偏好。除了用户自身固有属性可以产生用户间相似性关联外，还有一些用户非固有属性也可以挖掘出用户之间的关联，例如，本文将用户偏爱项目属性和用户评价过的项目数量也作为计算用户间相似度的属性。利用用户的属性信息，计算出用户之间的相似度，构建用户相似度矩阵，然后得到用户预评分，最后将预评分填充到稀疏评分矩阵中。

本文将计算用户间相似度分为三部分：计算用户固有属性间的相似度、计算用户非固有属性间的相似度、计算用户总的相似度。

2.1.1计算用户固有属性间的相似度

用户各个固有属性Ak之间的取值类型可能是不同的，一般可分为数值属性、二元属性、分类属性。各个属性间相似度的计算方法如下

1) 当Ak为二元属性时

(3)

式中：AXk代表用户X第k属性地取值，AYk代表用户Y第k属性地取值。

2) 当Ak为数值属性时

(4)

经过多次实验，用户年龄相差在5岁之内定义相似度为1比较合适。

3) 当Ak为分类属性时

例如Ak为职业属性时，各个职业之间具有语义上的关联，为了获取分类属性间关联度的大小，本文根据分类词典构建出分类属性层次树，树的结构图如下

图1 分类属性层次树

如图1可知，将分类属性按照层次划分为4类，从上到下为包含关系，分类属性Ak的值对应为树中叶子结点，也就是细类。属性间的相似度的计算思想为：对任意两两属性进行深度和广度相结合的遍历，并且在遍历过程中进行结点的比较，先进行树的广度遍历，如果在同一层存在相同的结点，则跳转到下一层进行树的深度遍历，直到在树的某一层所有结点都不相同时，停止遍历，记录此时的遍历深度，最后用遍历深度除以树的深度得到属性间的相似度，计算公式如下

(5)

式中：father(AXk，AYk)代表两个用户AXk，AYk属性对应树中叶子结点地共同父节点，depth(father(AXk，AYk))代表该结点地深度，depth(T)代表树地深度。

2.1.2计算用户非固有属性间的相似度

根据本文采用的数据集选取用户偏爱的项目属性和用户评价过的项目数量为用户非固有属性。用I表示项目集合，I={i1，i2，i3，…，in}，n代表项目个数。用item-A表示项目属性集合，item-AI={a1，a2，a3，…，ap}，p代表项目属性个数，则项目-属性矩阵Attr=|I|×|item-A|如表2所示。

表2 项目-属性矩阵

在项目-属性矩阵中如果项目ij具有属性ak则将该属性对应的值设置成1，否则设置成0，其中ij表示项目集合中的第j个项目，其中ak代表项目属性集合中第k个属性。

接下来根据用户-项目评分矩阵和项目-属性矩阵，通过计算提取出用户偏爱电影项目属性集合。主要推导过程如下：

1) 根据用户X的历史电影评分记录，计算出用户X对项目属性集合中各个属性的偏爱值(Bias Value)，计算公式如下

(6)

2) 计算出用户X对项目属性集合中各个属性偏爱值的最大值，计算公式如下

(7)

3) 计算出用户X对项目属性集合中各个属性的偏爱因子。

(8)

式中：I′表示用户X评价过的项目集合；ak表示项目属性集合中的第k属性；iak表示项目i的第k个属性，取值为0时表示该项目不具有该属性，取值为1时表示该项目具有该属性；B(X，ak)表示用户X对项目属性集合中各个属性的偏爱值；max-B(X， item-A)表示用户X对项目属性偏爱值中的最大值。

用T表示用户偏爱的项目属性集合，定义T={t1，t2，t3，t4，…，tk，…，tp}。当γ(X，tk)≥ε舽时，则tk=1。 当γ(X，tk)<ε舽时， 则tk=0。 其中tk=1表示用户偏爱项目属性集合中的第k个属性；其中tk=0表示用户不喜欢项目属性集合中的第k个属性；ε舽为预设定的阈值。上述用户非固有属性可分为两种：集合属性和数值属性。各个属性相似度计算方法如下

1) 当Ak为集合属性时

定义：AXk={tX1，tX2，…，tXk，…，tXp}

AYk={tY1，tY2，…，tYk，…，tYp}

式中:tXk代表用户X是否偏爱项目属性集合中第k个属性，tYk代表用户Y是否偏爱项目属性集合中第k个属性，tXk和tYk值为0或1，值为1表示偏爱，值为0表示不偏爱，相似度的计算方法如下

(9)

其中：

F(AXk∩AYk)=(tX1∩tY1，tX2∩tY2，…，tXk∩tYk，…，tXp∩tYp)

(10)

F(AXk∪AYk)=(tX1∪tY1，tX2∪tY2，…，tXk∪tYk，…，tXp∪tYp)

(11)

sum(F)表示将集合中的元素进行相加。

2) 当Ak为数值属性时

(12)

式中：min[Aik，Ajk]表示取两个值中最小值，max[Aik，Ajk] 表示取两个值中最大值。

2.1.3计算用户总的相似度

在计算用户总相似度前，需要确定用户各个属性在相似度计算中所占的权重w(Ak)，在确定各个属性权重后，用户间相似度计算公式如下

(13)

式中：q代表用户属性地个数，a-sim(AXk，AYk)代表用户X和用户Y在第k个属性上地相似度。

按照上述公式(13)可以计算任意两个用户间的相似度来构建用户相似度矩阵Sm，m，依据Sm，m对目标用户未评价过的项目进行预评分，并将用户预评分填充到稀疏评分矩阵Rm，n中。用户预评分的计算方法如下[16]

(14)

2.2 通过项目聚类构建推荐列表

由2.1节可得到填充后的评分矩阵，然后结合User-Based CF算法，求出目标用户对未评分项目的最终预评分。

接下来对数据集里所有的项目进行聚类操作。通过表2的项目-属性矩阵来求出项目间的相似度，进而将相似或相同的项目进行聚类。聚类操作需要设定项目间相似度的阈值β，即当两个项目相似度item-sim(iu，iv)≥β时，就把这两个项目聚为同一类。本文的项目相似度计算方法为

(15)

式中：p是项目属性个数；aiuk是iu项目第k个属性值；aivk是iv项目第k个属性值。

接下来通过利用已知的聚类结果产生初始推荐列表。根据目标用户的最终预评分，将预评分最高的项目按照公式(15)进行聚类，统计出相似或相同项目所在最多的项目类，本文采用的评分标准为[1-5]分制，最高分为5分。最后在对应的项目类中按照用户预评分产生前Top-N个未评分的初始推荐项目。此时产生的推荐项目并不一定满足推荐位越靠前推荐命中率越高的规则，所以本文引入了用户评价项目的时间戳属性，利用时间戳[17]属性可以在一定程度上满足上述规则。首先，寻找出目标用户在训练集里最近评价过的且喜欢的项目，然后将初始推荐列表中项目与该项目进行相似度的比较，按照相似度高低进行重排序[18]。经过重排序后的项目列表在一定程度上满足推荐位越靠前命中率越高的规则，进而不仅可以使整个推荐列表准确度提高，还可以使每个推荐位的命中率提高。

2.3 算法的推荐步骤

算法 基于用户多种关联信息和项目聚类的推荐算法

输入 待推荐的用户ID，需要推荐的项目个数N

输出 推荐项目列表List(Top-N)

step1 根据用户历史行为数据，建立稀疏评分矩阵Rm，n，利用用户多种关联信息依据公式(13)计算得到两两用户间的相似度，建立用户相似度矩阵Sm，m。

step2 利用Sm，m矩阵，依据公式(14)计算得到各个用户未评分项目的预评分，并将预评分填充到Rm，n。

step3 利用填充后的评分矩阵，结合User-Based CF算法，产生目标用户的最终预评分。

step4 对数据集中所有项目进行聚类操作，通过公式(15)求出项目间的相似度，然后按照给定的阈值β，将相似或相同的项目聚为同一类。

step5 根据得到的用户最终预评分，将预评分最高的项目进行聚类，统计出相似或相同项目所在最多的项目类，在对应的项目类中按照用户预评分产生Top-N个未评分的初始推荐项目。

step6 结合用户评分的时间戳属性对初始推荐项目列表重排列，产生最终推荐序列List(Top-N)。

3 实验结果和分析

3.1 实验数据集

本实验采用的是公共数据集，GroupLens-MovieLens数据集。该数据集中有项目信息表、用户项目评分信息表、用户信息表、电影的类型信息表、用户职业信息表等。由于数据集中包含了一些与本实验无关的噪声数据行预处理。需要将项目信息表中，所以在使用该数据集之前需要对其进除项目属性信息以外的其他所有信息过滤掉，并且使不同属性值之间用空格隔开。

为了确保实验地合理性，选择不少于被10个用户共同打过分地项目并且每个用户不少于对10个项目进行评价过地用户作为测试集合，总共选取100 000条用户项目评分数据。把100 000条数据进行8/2划分，80%用来作为训练数据，20%用来作为测试数据，训练数据中用户评论数量为80 000条，测试数据中用户评论数量为20 000条。为了验证本文提出方法的有效性，分别在平均绝对误差MAE和准确率评价标准上与其他推荐方法进行比较。使用五交叉验证法来对上述两种评测标准进行实验论证，其中测试集数据互不相交。

3.2 测评指标

1) 平均绝对误差(MAE)评价

MAE是指经过算法计算得到地用户预评分数据与用户地实际评分数据的误差值，误差值越小，说明算法预评分越是接近用户真实的评分，进而就会使得推荐越符合用户的兴趣，准确率就越高。MAE的计算公式[19]如下

(16)

式中：n是目标用户在测试集中评价地项目个数；Pt是目标用户对第t个项目地预评分；Rt是目标用户对第t个项目地真实评分。

2) 准确率评价

在推荐算法中准确率是衡量算法性能的重要指标之一，能够反映出系统推荐的项目是否在一定程度上满足用户的需求。准确率的计算公式[20]如下所示

(17)

式中：R(u)是推荐系统为目标用户u生成地项目群；T(u)是测试集中目标用户u对某个项目评分为4分以上地项目群；U是测试集中地用户集。

3.3 实验结果与分析

本文选取2种对比算法如下：

1) 基于用户的协同过滤算法(User-Based CF， UB-CF)。根据用户评分矩阵信息，为用户未评分的项目进行预评分，最后生成推荐列表。

2) 基于评分矩阵填充与用户兴趣的协同过滤推荐算法(Collaboration Filtering Recommendation Algorithm Based on Score Matrix Filling and User Interest，SMFUI-CF)。该算法首先是计算出用户对项目的偏好度，然后填充用户项目评分矩阵，最后引入时间的兴趣度权重函数进和偏好度到项目相似度计算中，最终实现算法的推荐结果。

实验1 在本文为了计算用户间偏爱的项目属性相似度，首先需要得到用户偏爱的项目属性集合，在这个过程中需要预先设定用户偏爱因子阈值ε，因为阈值ε会对算法的MAE值产生较大的影响。由于ε的取值范围是[0，1]，所以需要验证ε在取不同值时MAE值的变化，本文取ε的值为0.1～0.9，间隔为0.1。已有研究表明当最近邻k取[30，60]范围内的值时会有很好的推荐效果。因此，设置k=50。此外，进过多次实验统计当对应的性别、年龄、职业、偏爱的项目属性和评价的项目数量五种用户属性的权值为w1=0.1，w2=0.1，w3=0.3，w4=0.3，w5=0.2本文算法会有很好的推荐效果。如图2所示，不同的ε的取值对MAE值产生了很大的印象。

偏爱因子阀值ε图2 偏爱因子阈值ε与MAE的关系

实验2 参照实验1中的结果，可以确定偏爱因子阈值ε的最优取值为ε=0.5，然后计算出本文提出的基于用户多种关联信息和项目聚类的推荐算法在最近邻数k取不同值时对应的MAE值，并且分别与UB-CF算法和SMFUI-CF算法进行比较，实验对比结果如图3所示。

图3 MAE与最近邻数k的关系

实验3 在产生推荐结果的过程中需要进行项目聚类，而进行项目聚类需要预先确定项目相似度阈值β，因为β会对算法推荐的准确率产生重要的影响。本文中β的取值范围是[0.1，0.9]，间隔为0.1，算法推荐项目个数取10，其他的参数设定与前两个实验一致。如图4所示，项目相似度阈值β取不同值时，对算法准确率的影响。

项目相似度阀值β图4 准确率与项目相似度阈值β的关系

实验4 参照实验3中的结果，可以确定项目相似度阈值β的最优取值为β=0.9，然后计算出本文提出的基于用户多种关联信息和项目聚类的推荐算法在算法推荐项目个数取不同值时对应的准确率值，并且分别与UB-CF算法和SMFUI-CF算法进行比较，实验对比结果如图5所示。

图5 准确率与推荐项目个数的关系

4 结论

本文提出一种基于用户多种关联信息和项目聚类的推荐算法，该算法可以有效的利用用户关多种联信息计算出两两用户间地相似度，依据最近邻计算出预评分并填入稀疏评分矩阵，其次通过协同过滤算法得到最终预评分，在此基础上通过结合项目聚类产生初始推荐项目列表，最后融入时间戳属性对推荐列表进行重排列，产生最终Top-N推荐。本文在MovieLens数据集验证了该算法，实验结果表明该算法不仅可以有效的降低MAE值，还可以提升推荐系统的准确率。