面向冷启动用户的代表性物品选择

汪 静，赵海燕，陈庆奎，曹 健2(上海市现代光学系统重点实验室，光学仪器与系统教育部工程研究中心，上海理工大学光电信息与计算机工程学院，上海200093)

2(上海交通大学计算机科学与技术系，上海200030)

E-mail:jingwang94@outlook.com

1 引言

1.1 研究背景

推荐系统已经被广泛应用，它通过对用户过去选择行为的学习获取用户的偏好，从而能够预测用户对未选择过或者新物品的喜爱程度.虽然目前各种模型已经被提出来以改进推荐系统的效果，但是，由于许多用户的历史数据偏少甚至没有历史数据(冷启动用户)，对这些用户难以获得满意的推荐效果.

主动学习策略改变了被动等待用户积累充分的数据以进行模型学习的方式，它通过选择特定的物品形成询问列表，向用户询问列表中物品的评分，在获得的新数据上对推荐模型进行再训练.由于需要用户配合提供物品的评分，因此，如何用尽可能少的用户评分来获得更好的推荐效果至关重要.前人提出了一些主动学习的策略，如文献［1］对物品赋予最小权重属性，提出的 Sufficient Weight策略，文献［2］在 Aspect Model的基础上，将用户等待时间考虑进去，提出的TAM算法，等等.这些策略都取得了不错的成果，但是对于新用户这一用户群中的特殊案例，现有的对其单独考虑的主动学习策略并不多.新用户冷启动是主动学习和推荐系统共同面临的严峻挑战，它可能极大降低新用户对系统的信任度，最终导致用户的大量流失.如果能够设计出有效的面对冷启动用户的主动学习策略，挑选较少但高效的物品给用户评分就能判断用户的兴趣偏好并为用户做出精准的物品推荐，从而增加用户对系统的信任程度，提高服务质量和用户体验.

1.2 问题描述

新用户是指在系统中拥有极少或没有评分、标签等相关数据的用户.新用户刚刚进入系统中，对系统的方方面面都不熟悉，此时系统的推荐功能对这一群体就显得更加重要.文献［3］中调查研究表明，用户对系统的忠诚度随着系统对用户提供有效的个性化服务的时间不同而不同，也就是说如果能尽可能早的对进入系统中的新用户实现推荐功能，用户就会更依赖该系统.因此，要提高推荐系统的质量和效率，就必须要先解决新用户冷启动问题.

另外，因为新用户缺少能反映其偏好信息的数据，使得现有的主动学习策略及推荐算法即使能在那些大部分拥有丰富数据的用户集上得到很好的效果，但不能推算出新用户的偏好和评分模式，应用在新用户上的结果并不理想.此外，在考虑新用户的询问列表时，由于数据稀疏性太大，即使是非个性化的主动学习也不能收获很好的效果.所以我们想借助用户的分类，通过对新用户归类获取更可靠的偏好信息.

推荐系统中，相似的用户一般有相似的评分模式.根据其对物品的评分的情况进行分类，可以将有相似评分习惯及兴趣偏好的用户归为一类.于新用户来说，如果可以尽早确定新用户是隶属于哪一用户群体，系统就能够给出较为准确的物品推荐，这样就能解决新用户冷启动的问题.

本文中提出了一个解决用户冷启动问题的代表性物品生成的主动学习策略.通过我们提出的协同聚类算法，一方面充分利用了用户对物品的评分信息，另一方面又让用户类群与物品类群的生成受彼此影响，最终达到系统最优的效果.

文章的后续内容安排如下:第二节介绍了实验的相关工作，重点介绍了主动学习、聚类以及决策树的思想和近年来的工作;第三节是协同聚类算法的详细介绍和实验过程;相关的对照试验以及实验结果分析放在第四节;最后是算法的总结及对未来工作方向的分析展望.

2 相关工作

2.1 主动学习

主动学习是机器学习中的一个重要分支，主要针对传统的有监督学习过程需要大量的带有类别标签的样本来构建学习器的弱点而提出的，尤其是在数据量十分巨大的情况下，为每一个样本进行标注需要耗费很大的代价.主动学习的目的就是使用有限的训练数据的情况下能够获得较高的分类精度，然后对这些样本再进行标注，既可以节约训练代价又可以提高学习器的分类效果.根据采样策略的方式不同，将主动学习分为三种方式［4，5］:成员查询综合(Membership Query Synthesis)、基于池(Pool-based)和基于流(Stream-based).

成员查询综合［6］是主动学习领域最早研究的方式，主要思想是学习模型能够选择输入空间中所有未标记的样本项目向监督者提出标注请求，但这样丢失了样本的分布信息.理论情况下，在有限的问题域中，成员查询算法是高效又易于掌控的.基于流的主动学习［7］是成员查询综合的一个替代方案.基于流的基本思想是从实际分布中采样一部分未标注案例，由学习模型决定是否对其进行标注，决定方式有多种，可以通过“信息量测试”或“询问策略”，也可以对那些模型不完全了解的实例空间中的样本实例的信息量设定一个阈值，若实例的信息量大于设定的阈值则被选择标注.基于池的主动学习［8，9］中会设置一个样本池(pool)，是一个容纳着海量的未标注的样本项目集P，主动学习的策略S按照一定的规则从P中选择一个或多个样本项目组成询问列表L让专家做标注工作.基于池的方法是应用最广泛的一种，但是该方法对机器的内存和处理能力要求较高，并且算法耗时较大.

文献［10］将成员查询综合与基于池的方法相结合，取长补短，保留了成员查询综合低复杂度的优势又解决了其不能识别人类监督者的标签结果的缺陷.文献［11］用基于池的思想对网页视频信息检索的模型进行训练.文献［12］提出A2ING算法，利用文本类别的不确定性实现文本分类等.

主动学习现有的策略中，识别有信息的物品从而发掘目标用户的偏好是策略的首要任务，而在我们提出来的策略中，主动学习的询问列表目的在于识别新用户应属的用户类群，以根据类群中的用户成员的相关信息实现对新用户的准确推荐.

2.2 聚类

聚类是将物理或抽象对象的集合根据对象属性或特征，分成多个对象类的过程，每个对象类就是一个簇(Cluster).聚类使得同一簇中对象之间具有很高的相似度，而不同簇中对象高度相异，对象间的相异度根据描述对象的属性值计算，通常使用距离来度量［13，14］.由此可见，聚类的过程是完全依赖于样本之间的特征差别的.

文献［15］提出将聚类嵌入到主动学习中，该算法首先在聚类的数据集上构造一个分类器，然后通过局部噪声模型将分类结果传播给其他样本.文献［16］的作者认为虽然聚类本质上是不受监督的，但是如果能提供有限的监督的话，可以提高聚类性能.文章提出运用主动学习的方法对聚类过程进行监督，引导类群向约束指示的方向发展.文献［17］设计了基于步行距离的路网聚类算法，向用户推荐最优的路径方案，缩小路网搜索空间，提高查询性能.文献［18］提出的UCNDBSCAN聚类算法运用联系数的思想重新定义对象间距离，巧妙地表示出对象的不确定性.

对于传统的聚类方法(如K-means等)，在很多复杂数据对象上的实现效果并不乐观，因为大多传统的聚类方法都是用样本对象的特征属性直接进行聚类，并没有事先优化特征属性这样的预处理阶段，从而使得样本的多个特征属性被放到一起计算时出现误差.单纯的聚类算法效率不仅有依赖于样本的分布情况的弊端，还受聚类中心点的初始选择的影响，所以本文没有采用单纯的聚类算法对用户或物品进行聚类，而是采用协同聚类的思想，让用户与物品的关联关系作为聚类的依据，让二者相互影响，使得聚类的结果更能反映不同类别的用户特性，更好反映用户的偏好，从而得到较可靠的实验结果.

2.3 决策树

决策树是一种常用的呈树状的分类预测模型.决策树自上而下建立，每个内部节点都表示对象的某一个或多个属性，分支代表属性的多个取值.每个分支又将原有数据集分割成更小的数据子集，在数据子集上重复建立下层节点，最终构建完整的树结构.选择不同的属性作为内部节点时，同一数据集可能会构造出不同决策树，因为不同属性会划分出不同的数据子集，从而影响决策树的构建速度和分类准确度.

文献［19］文献作者提出的 IGCN(Information Gain through Clustered Neighbors)算法将决策树的中间节点转换成物品集合，利用决策树的结构根据用户对数节点中物品集的评分选择分支，进行下一轮评分，直到达到树叶节点，实现用户分类，再针对不同的类别实现推荐.文献［20］提出 FDT(Factorized Decision Trees)算法重新定义决策树的生成方式，并用MPS(Most Popular Sampling)方法加速决策树的生长.文献［21］用分类器依据用户对物品评分的高低将用户分为三组:喜欢、不喜欢和未知，并以组为单位对那些未评价过的物品进行评分预测.

3 协同聚类

协同是协调两个或两个以上的不同资源或者个体、共同一致地完成某一任务的过程，包括不同数据对象之间的协同.协同聚类是一种建立在多个数据子集上的聚类模型，利用多个子集之间的协同关系并与聚类算法相结合，通过迭代更新，让多个子集相互影响，最终达到稳定的分类，提高聚类效果，是一种适用于综合研究不同特征角度的高维数据集的新算法.现有的国内外关于协同聚类的研究大多结合多核概念和模糊理论的相关算法.文献［22］在多子集上运用协同聚类算法，形成多核竞争的关系，将多子集之间的协同与竞争的关联关系充分利用.文献［23］用模糊协同聚类FCOW 算法处理weblog挖掘在用户聚类也页面聚类边界的问题.文献［24］将协作机制引入竞争核聚类中，通过在不同子集之间共享分区矩阵来提高聚类性能.

与一般的协同聚类是在同类对象的不同子集上进行不同，本文利用用户与物品间的联系，对用户和物品两种不同类型的对象进行协同聚类，然后进行交叉迭代.在用户的每一次调整中，会对物品的坐标产生影响;同理，在物品的每一次聚类更新时，也会让用户的坐标发生改变，就这样相互调整对方的聚类结果以改进最终聚类结果.

3.1 协同聚类算法

在我们的方法中，用户用m维的坐标表示，每一维代表目标用户对每个物品类中成员的平均评分，相应的n维的物品坐标也用每个用户类群中成员对该物品的平均评分来表示.用户的坐标表示如公式(1)所示，其中n表示物品分类个数，rik表示用户i对第k类物品群的平均评分:

物品的坐标表示如公式(2)所示，m表示用户分类个数，rkj表示第k类用户群对物品j的平均评分:

首先，随机选择m个用户作为用户聚类的初始中心点，选择n个物品作为物品聚类的初始中心点，根据中心点对用户和物品分别进行初始聚类.然后，用交叉迭代的方法依次调整用户聚类和物品聚类结果.交叉迭代的思想是在初始聚类结果基础之上，计算每个用户与多个用户类中心点的关联关系，每个用户都选择与其相关性最大的中心点作为新的归属.归类完成后在各个类群内部计算新的类群中心点，这些新的中心点将作为下次聚类的初始聚类中心点.由于用户类的变动，物品的表示坐标需要重新计算，重新计算后的物品聚类按照上述的过程进行聚类.如此往复，当用户类群与物品类群都趋于稳定时停止，以此达到协同聚类的目的.通过协同聚类，能够获取对于用户和物品都相似的类别群组，这样得到的用户组具有偏好代表性.具体的交叉迭代的步骤如下:

3.1.1 用户聚类更新

初始聚类之后，物品聚类不动，根据物品类群调整用户类群的更新.对于每一个用户类群Ul，通过公式(3)计算该类群中用户uj与类群中心点ucl的关联关系Su(uj，ucl):

其中，ucl(l=1，2，3，…，m)表示用户类群的每个中心点，表示求用户uj与中心点ucl的距离，k=1，2，3，…，n.如果得到的 Su(uj，ucl)越大，表示目标用户与中心点的相似度越小，相关性越弱;反之相似度大，相关性越强.公式(3)中，当目标用户恰巧为类群中心点时，相似度最大，其他的用户则比较其与每个类群中心点的距离，选择相似度最大相关性最强的类群中心点作为该用户的新类别.

待每个用户都找到新的归类后，在每个用户类群内部，寻找类群中与其他成员距离最小的用户作为新的中心点，计算成员最小距离Di的公式如下:

类群中心点发生变化，重复上述过程，不断调整用户类群，达到收敛状态.至此，一次用户聚类更新完成.

3.1.2 物品聚类更新

将用户类群固定，现在我们借助用户类群来调整物品聚类.对于每一个物品类群tl，通过公式(5)计算该类群中物品tj与类群中心点tcl的关联关系St(ti，tcl):

其中，tcl(l=1，2，3，…，n)表示物品类群的每个中心点，表示求物品ti与中心点tcl的距离，k=1，2，3，…，m.同理，得到的 St(ti，tcl)越大，表示目标物品与中心点的相似度越小，相关性越弱;反之相似度大，相关性越强.公式(5)中，依旧选择相似度最大相关性最强的类群中心点作为该物品的新类别.

计算成员最小距离，寻找类群中与其他成员距离最小的用户更新每个类群中心点，物品成员最小距离Di的公式如下:其中ObjectSet表示物品i所属的类群表示物品ti与物品tj的距离.

3.2 计算复杂度分析

协同聚类算法的开销主要在两个方面:一个是用户和物品聚类时用户和物品的坐标u和t的计算，二是目标对象与类群中心点的关联关系S的计算.这些计算在单次的迭代中复杂度并不高，但是依据协同聚类算法的特性，每次用户更新和物品更新都是经历多次的聚类迭代，重复很多次这两个方面的累计计算复杂度就很高了.用户坐标u和物品坐标t的计算复杂度均为O(NuNt)，其中Nu、Nt表示数据集中用户、物品的总数目.用户关联关系 Su的计算复杂度为 O(NuCtwu)，Ct表示物品类群数目，wu表示用户坐标维度.物品关联关系St的计算复杂度为O(NtCuwt)，Cu表示用户类群数目，wt表示物品坐标维度.因此，一轮用户与物品的迭代更新的总的时间复杂度为O(NuNt+NuCtwu+NtCuwt).

4 实验及其结果分析

4.1 实验过程

本实验要求用户与物品之间有评分数据作为关联，因而我们的实验采用美国明尼苏达计算机学院的GroupLens小组提供的MovieLens数据集［25］.该数据集有用户数目2113，电影数目10109，评分记录855598条，每条记录分别由用户ID，电影ID，评分和时间戳组成.实验时，我们以用户为单位，分成9:1的训练集与测试集，对用户或物品的各自聚类采用kmodies(k中心点)算法实现.用户与用户，物品与物品间的相似度采用欧几里得距离表示，距离越小表示相似度越高，反之，相似度越低.

根据前面的协同聚类、决策树以及主动学习方面的相关介绍，具体的策略过程如下:

1)首先用协同聚类算法，对用户与物品进行分类，得到m个用户类群和n个物品类群;

2)对每条记录中用户对物品的评分r进行转换处理:

6)整理用户类群U中的所有用户评价过的物品，用U中所有用户对物品的平均评分作为该用户u的预测评分，计算RMSE;

7)或者，根据用户类群U中不同用户对目标用户的影响大小对评分加权，预测出加权评分r'作为该用户u的预测评分，计算RMSE.

4.2 可行性分析

本文处在信息过载、数据稀疏的大前提下，虽然已经有很多推荐策略提出以帮助解决这些困境，但是对于新用户这一群体并没有足够针对性的策略提出.

实验运用的协同聚类算法，是一种能建立在多个数据子集上的聚类模型，它可以将本实验的物品集与用户集联系起来，充分利用二者之间的关系，再经过多次交叉迭代，最终得到能反应用户偏好的代表性物品列表.利用代表性物品构造决策树分类器，决策树的每个节点都由物品组成，根据用户对节点物品的评分生成分支，完成对新用户的分类.对分类后的新用户推荐该类其他非冷启动用户普遍喜欢的物品，使得新用户成功过渡冷启动阶段.

本文研究的问题目前国内外具备大量的文献资料可供参考，算法构思上逻辑清楚，编程上运用到的协同聚类和决策树

3)用已经得到的用户类群和物品类群中心点构造决策树.决策树的节点由物品类群中心点表示，用户类群中心点作为分类对象，利用转换后的用户对物品的评分r生成分支，并以此类推建立子树;

4)选择决策树顶端的k个物品作为代表性物品，向新用户发起询问;

5)得到新用户u对k个代表性物品的评分后，再利用决策树分类器对新用户u进行分类，得到用户类别U;算法都已经被运用到了很多领域，技术成熟.综上所述，本文提出的算法是切实可行的.

4.3 对照试验

本实验采用两个对照试验:基于流行度的方法popu和基于信息熵的方法infoEnt.对照试验popu直接选择流行度最高的p个物品作为“代表性物品”，infoEnt根据公式(7)计算物品的信息熵H，选择信息熵最高的前p个物品作为“代表性物品”，而不采用协同聚类的方式，并用这p个物品形成决策树T，对测试集中的新用户u，让用户u对这p个物品给出评分，借助于获得到的评分信息通过决策树预测出u所属的用户类群U.用用户类群U中所有用户对物品的平均评分以及用相似度加权之后的加权评分r'作为该用户u的预测评分，与测试集中的实际评分相比较，计算RMSE.

4.4 结果分析

实验过程中有多处参数可以调整，接下来选择四个对实验结果影响较大的参数，分别在平均评分珋r和加权评分r'两种实验操作下进行分析讨论(以下所有图例中CCM(Collaborative Clustering based Model)表示协同聚类策略的结果，popu表示流行度策略的结果，infoEnt表示信息熵策略的结果).

4.4.1 推荐列表长度L1

如图1所示，我们从RMSE对实验结果进行比较.图中横坐标表示询问列表L1的长度，纵坐标是RMSE的值.图1(a)中，我们可以看到随着L1长度的增加，特别是在L1＞15之后，对照试验popu和infoEnt和CCM都趋于平稳，在L1为15时，RMSE达到最优.因为随着推荐列表的增长，我们提出的策略能够有更大的机会推荐出适合不同用户的物品，从而更准确的“推算”出新用户的偏好，而popu和infoEnt策略在形成决策树时仅依照流行度和信息熵来选择“代表性物品”，没能利用到用户与物品之间的关系，所以不能很好的拟合新用户的需求.图1(b)中，CCM随着L1的增大，RMSE不断减小.当L1处于0到10之间时，对照策略popu的减小速度很快，之后就渐趋平稳，而infoEnt一直都保持缓慢速度下降，也在L1=20处趋于平稳.

图1 不同推荐列表长度下不同算法RMSE的比较Fig.1 Comparisons of RMSE between different algorithms with different recommendation number

4.4.2 “代表性物品”个数 L2

“代表性物品”的个数也就是主动学习策略的询问列表长度.如图2所示，横坐标表示“代表性物品”的个数，纵坐标表示实验的RMSE值，从图2(a)可以看出当L2在20时，三个实验结果都达到了一个低谷，并在30处，CCM的RMSE值达到最小.而在图2(b)中，在L2在20之前，CCM 的结果都比popu差，但是在25之后，CCM仍保持着较快的下降速度，而popu则趋于平稳，并当L2=30时，CCM的RMSE达到最小值.

图2 不同询问列表长度下不同算法RMSE的比较Fig.2 Comparisons of RMSE between different algorithms with different query number

4.4.3 物品类别个数m

图3 不同物品类别数目下不同算法RMSE的比较Fig.3 Comparisons of RMSE between different algorithms with different movie-clusters number

图4 不同用户类别数目下不同算法RMSE的比较Fig.4 Comparisons of RMSE between different algorithms with different user-clusters number

由于对照试验中没有用到协同聚类的思想，也就没有物品类别数目这一参数，所以图3中的对照试验结果分别是在L 1=15，L2=20和L1=20，L2=30的取值下RMSE的值，放入图中作为参照作用.另外，CCM的其他参数也与对照试验保持一致.在图3(a)中，m从20增大到35，RMSE不断减小，在35与40之间达到最小值.因为随着m的增大，对物品的划分更加细粒度，同一特征可能会有多个物品类群都满足，从而造成实验出现偏差，所以在m＞40之后RMSE值又不断增大.图3(b)中，CCM的RMSE值随着物品类别数目的增多不断减小，并在35左右达到最优值;当m＞35时，物品的划分过分细致，导致分类效果变差.

4.4.4 用户类别个数n

类似于参数m，用户类别数目n的实验也是在L1=15，L2=20和L1=20，L2=30的前提下进行的，且实验的其他参数设置与对照试验均相同.从图4可看出，当m取值在10到15之间时，RMSE值最小.

表1 各个策略对应的RMSE值Table 1 RMSE of different strategies

综上所述，各个策略对应的RMSE值如表1所示.平均评分珋r和加权评分r'是分别在(15，20，46，10)和(20，30，37，15)的参数组合下得到的最终RMSE结果.

5 总结

本文提出的针对用户冷启动的“代表性物品”生成的策略，利用协同聚类算法将用户与物品的关系充分利用了起来，也避开了单纯的聚类思想的弊端，选择的物品具有足够的代表性.主动学习的中心的一环:询问列表的生成，在碰到棘手的新用户问题时也能够通过“代表性物品”的选择得以解决.实验最终的结果也表明，通过选择一定数量的代表性物品向新用户发起询问，能够在新用户进入系统的最初就能有不错的推荐准确率，提高了新用户的体验.

本算法虽然取得了一定的效果，但仍有许多值得深入研究的地方.例如，这里构造决策树作为用户分类器时，决策树的中间节点都是由单个记录字段构成的，后面的研究可以考虑将决策树的中间节点用多个相似的物品共同决定，并且还可以考虑避开数据的稀疏性，在选择用户和物品代表时加入流行度的因素，这些都是后续将要研究的方向.