摘  要： 提出一种基于谱聚类的协同推荐算法(SCBCF)。首先从用户——项目二分网络的单顶点投影中得到用户之间的相似矩阵，然后对该矩阵应用谱聚类算法，将用户聚成k类，并将得到的聚类结果用于数据平滑和邻居结点的选择，最后基于最近邻居集评分行为，对目标用户产生推荐。在MovieLens上的实验结果证明本文方法比传统的协同过滤算法能更好地应用于二分网络的协同推荐。
关键词： 协同过滤；谱聚类；推荐算法；平均绝对偏差

    随着互联网信息的不断膨胀，信息过载也越来越严重，因而推荐系统越来越受到人们的重视。最简单的推荐算法是全局排名方法GRM(Global Ranking Method)，该算法不考虑用户的个性化需求，因而其推荐结果的质量并不好。于是，考虑用户偏好的协同过滤CF(Collaborative Filtering)推荐算法被广为应用，并迅速成为最受欢迎的推荐算法之一。协同过滤算法考虑用户兴趣，在用户群中寻找目标用户的相似用户组，综合这些相似用户对某一项目的评价，预测目标用户对此项目的兴趣。
    目前，协同过滤算法主要分为两类[1]：基于内存的方法和基于模型的方法。基于内存的方法在整个数据库上执行，从训练数据库中找出与目标用户最相关的K个用户，然后把他们的评分信息结合在一起对目标用户的评分情况进行预测。主要有基于Pearson相关性的方法、基于向量相似度的方法等。这些算法主要有两个缺点：易受稀疏的评分数据的影响；算法的可伸缩性差。与之相对，基于模型的方法并不直接使用单个用户的评分信息，而是预先按照用户评分的模式对用户进行聚类，然后计算目标用户与各个类别之间的相似度，找出最相似的类，用该类对某个项目的评分作为目标用户对该项目的评分。主要的方法有贝叶斯网络方法、聚类的方法。基于模型的方法在建立聚类的过程中较为耗时，而且对目标用户做出的评分预测也存在准确性较低的问题。
    本文考虑将谱聚类的方法引入到协同过滤推荐算法中，对训练集中的用户进行谱聚类，结合基于内存和基于模型这两种方法的优势，而对目标用户评分的预测任务则交由其最相关的用户群组来完成。对于如何构造谱聚类算法的输入矩阵，本文将用户——项目二分网络投影到只包含用户结点的单顶点网络，构造n×n的用户相似矩阵。考虑到评分数据的稀疏性，本文利用类的信息对类中每个用户未评分的项目进行数据平滑处理，从得到的N个聚类中找出与目标用户最相似的一个或几个类别作为最近邻居候选集，再从候选集中找出最相似的K个用户进入最近邻居集，最后预测目标用户对每个项目的评分。
1 相关工作
1.1 二分网络的投影
    二分网络单顶点投影[2]是研究二分网络的一个重要方法。二分网络投影成单顶点网络的方式主要分为两类：无权投影和加权投影。如图1所示，图1(b)、图1(c)分别为图1(a)关于X、Y的单顶点投影，单顶点网络中的任意两个点之间边的权值大小为这两点在二分网络中的共同邻居数。虽然单顶点网络无法完全描述二分网络的全部信息，但是这个只含一种结点的单结点网络完美地保存了二分网络中此类结点的拓扑关系，网络中边的权值构成的关系矩阵可以用来表示同类结点之间的相似关系。
1.2 谱聚类
    近年来，谱聚类已经成为一种广受欢迎的现代聚类算法[3]。与传统的聚类算法如K-means算法相比，这种算法效率更高，聚类结果更优。谱聚类易于实现，可以用标准的线性代数的方法来高效解决。
    给定数据点集x1，x2，…，xn，以及所有点对xi和xj之间的相似度sij≥0所构成的n×n的相似度矩阵S。聚类的目标是把这些点划分进不同的类中，使得类内点的相似度大，而类间点的相似度小。本文用一个相似图G=(V，E)来表示上述信息，每个顶点vi表示数据点xi。如果sij≥0，那么顶点vi和vj之间存在边，且其边的权值即为wij。将二分网络抽象成二分图之后，可以这样来阐述聚类问题：找到一个图的划分，使得不同组之间的边的权值和小，而组内边的权值和大。
    谱聚类的衍化算法有很多种，此处介绍的是非正规化谱聚类算法，这也是本文在后面推荐算法中用到的。非正规化的谱聚类算法描述如下：
  
 
其中，分子为两个用户评分向量的内积，分母为两个用户向量模的乘积。
    修正的余弦相似性（adjusted cosine）：修正的余弦相似性度量方法考虑不同用户的评分尺度问题。设经用户i和用户j共同评分的项目集合用Iij表示，Ii和Ij分别表示经用户i和用户j评分的项目集合，则用户i和用户j之间的相似性sim(i，j)为：
 

3.3 实验结果及分析
    本文将聚类数设为20，分别取最近邻居数为5、10、20。在实验中，本文将传统的基于Pearson相关系数的协同过滤算法作为基线方法进行了比较，并把该方法记为TCF。对比结果如表1所示。

    从表1可以看出，协同过滤易受数据稀疏性的影响。本文的方法对训练集的数据进行了平滑处理，从而减轻了这一因素的影响。同时，随着最近邻居数的增加，实验结果也随之改善。这是因为考虑更多相似用户的评分行为，使目标用户的预测评分趋于稳定，从而使得预测值与实际值之间的偏差减小。本文提出的算法在很大程度上缩小了最近邻居候选集的大小，与传统的协同过滤算法相比，算法的伸缩性得到了提高，时间复杂度也进一步降低。
    本文考虑将更加高效的谱聚类算法引入到协同过滤推荐中来，实验结果证明本文提出的SCBCF算法比传统的协同过滤推荐算法能更好地提高推荐系统的推荐质量。在对用户进行谱聚类时，本文发现聚类结果的各个类之间的用户数并不均衡，这限制了预测能力的进一步提升，因此如何将用户更准确地归类将是未来的研究工作之一。
参考文献
[1] SU X，KHOSHGOFTAAR T M.A survey of collaborative  filtering techniques[J].Adv.Artif.Intell，2009(1)：421-425.
[2] ZHOU T，REN J，MEDO M，et al.Bipartite network projection  and personal recommendation[J].Phys.Rev.E，2007，76(4)：046115-046121.
[3] LUXBURG U.A tutorial on spectral clustering[J].Statistics  and Computing，2007，17(4)：395-416.
[4] SARWAR B，KARYPIS G，KONSTAN J，et al.Item-based collaborative ltering recommendation algorithms[C].In www10，Hong Kong，2001.
[5] XUE G R，LIN C，YANG Q，et al.Scalable collaborative filtering using cluster-based smoothing[C].In Proceedings of  the ACM SIGIR Conference，Salvador，Brazil，2005：114-121.