全文链接：http://tecdat.cn/?p=31502
本课题着眼于谱聚类在社会化推荐挖掘中的应用研究（点击文末“阅读原文”获取完整代码数据）。
摘要
谱聚类算法是基于图论的数据聚类算法，与其他聚类方法相比具有明显的优势：建立在谱图理论的基础之上；操作简单，易于实现；具有识别非高斯分布的能力，非常适用于许多实际应用问题。所以，谱聚类算法成为近几年来机器学习领域的一个新的研究热点，处理方法以及机器学习本身算法理论的学习和代码实现在各领域具有相同性，之后同学可以在其他感兴趣的领域结合数据进行分析，利用此课题所学知识举一反三。
在电影社交网站Flixster 数据集（查看文末了解数据免费获取方式）上的实验结果表明，本文提出的改进的社会化推荐算法在一定程度上缓解了传统推荐系统面临的准确性、稀疏性、实时性的问题，在 MAE、准确率、召回率和覆盖率等指标上有了明显的提高。
基于用户谱聚类集成的社会化推荐
聚类集成是将单个聚类算法的聚类结果合并成一个最终的聚类结果，集成后的聚类结果优于单个聚类算法的聚类结果。目前，聚类集成技术已经广泛应用于医学诊断、基因表达、非数值型计算等领域[2]。
本章在已有研究基础上，拓展了聚类集成技术的应用领域，提出了基于用户谱聚类集成的社会化推荐算法(SCECF)。将用户互关联矩阵作为谱聚类的相似度矩阵再次聚类，得到最终的聚类结果。然后，在用户所属类中寻找用户最近邻并产生推荐。SCECF 算法同样可以分为离线谱聚类和在线 Top-N 推荐两个阶段。
离线谱聚类阶段
输入：原始评分矩阵 R，用户关系矩阵 T，聚类数目 k
输出：聚类后的用户关系矩阵 T’
1、聚类成员生成：
Step1：从 N 个用户中随机选取 n 个用户作为样本，利用公式(2.8)以下计算样本用户相似度矩阵 An×n 及样本用户与剩余用户的相似度矩阵 Bn× （N-n）
Step2：令 Gn× N=[A B]，构造 G 矩阵的度矩阵 Dn× n，根据公式(3.7)构造 A的规范化拉普拉斯矩阵 Lsym。
Step3：对 Lsym 进行特征分解，即 Lsym=UΛU-1。利用 Nystro m 扩展方法计算N 个用户的规范化拉普拉斯矩阵的特征向量U—。
Step4：选U—取前 k 个特征向量 v1，v2，…vk 组成矩阵 V=[v1，v2，…vk]T并对V 进行规范化处理。
Step5：利用 K-means 聚类方法将特征向量空间 V 聚为 k 类，即将用户聚为k 类， 生成用户聚类矩阵 CN× N， 当用户 i 与用户 j 属于同一类时 Cij=1，否则 Cij=0。
2、聚类集体生成：
Step6：重复执行以上步骤 m 次，将生成的 m 个用户聚类矩阵 CN× N 相加，得到用户关联矩阵 NP。
Step7：对用户关联矩阵 NP 进行谱聚类。
Step8：根据谱聚类结果生成最终的用户关系矩阵 T’，当用户 i 与用户 j 属
于同一类时 T’ij=1，否则 T’ij=0。
在线 Top-N 推荐阶段
输入：聚类后的用户关系矩阵 T’
输出：用户 Top-N 推荐列表
Step1：计算聚类后的用户相似度矩阵 PN× N。当用户 i 与用户 j 属于同一类
时 Pij=sim(i,j)，否则 Pij=0。
Step2：对 P 矩阵进行排序，生成用户最近邻集合。
Step3：利用公式(2.9)计算用户未评分项目的预测值，生成用户预测评分矩阵 Rpre。
Step4：对 Rpre 进行排序，将预测评分最高的 Top-N 个项目推荐给用户。
创新之处
本文的创新之处主要体现在以下几个方面：
（1）基于Nystrom扩展技术的谱聚类
针对谱聚类方法在大规模数据应用中计算时间复杂度和空间复杂度较高的问题，引入Nystrom扩展技术。首先计算所抽取的少量样本的相似度矩阵和特征向量，跟样本的特征向量采用Nystrom扩展方法逼近计算整个数据集的特征向量。相对于计算整个数据集的相似度矩阵和特征向量，采用Nystrom扩展的谱聚类方法，改善了计算的时间和空间复杂度，解决了谱聚类算法在大规模数据中的应用问题。
（2）谱聚类集成技术
由于谱聚类算法中使用近似逼近的方法，以及谱聚类算法本身的初值敏感问题，聚类的结果并不十分稳定，采用聚类集成策略来解决这个问题。通过寻找多个聚类结果的组合来获得相对较优的聚类结果，从而获取较好的平均性能，提高聚类结果的稳定，并且一定程度上克服了谱聚类算法对噪音、异常点、采样的变动的敏感性问题。
（3）应用领域创新
将改进的谱聚类算法应用到基于社交网络的推荐系统中，克服了目前推荐系统中存在的准确性、实时性、稀疏性等问题。谱聚类算法实质上是对图的划分，而社交网络中用户之间的关系也表示为图的形式，因此对社交网络中相似用户群的划分可以使用谱聚类的方法。在使用谱聚类后的用户群中，寻找用户最近邻，然后预测用户对问评分项目的评分，最后产生推荐。
实验与结果分析
实验数据集
本文分别在两个代表性的数据集Flixster上对算法进行了测试。Flixster 是一个电影社交网站，在 Flixster 网站上用户分享电影的评分，讨论新的电影，也可以通过电影认识有相同爱好的人。本章选取电影社交网站Flixster 的用户数据作为实验数据集。该数据集包含两个部分，一部分是用户评分数据，包含 885个用户对 1000个电影的评分记录 192775 条。用户评分值介于 0.5-5 之间，评分间隔为 0.5，数值越大，说明用户对项目的喜爱程度越高，反之，说明用户对项目兴趣度不高；另一部分是用户朋友关系数据，包含以上892个用户之间的朋友关系。数据集示例如图 3.2 所示。实验中随机抽取用户评分数据集的 80%作为训练集，其余 20%作为测试集。
图 3.1 Flixster 数据集（部分）
表3.2 数据集描述
| 名称 | 描述 | 简介 | 每个用户至少评分物品 |
| Flixster | 对电影的评分从1到5 | 885名用户对1000部电影的评价 | 100 |
评分预测的预测准确度一般通过平均绝对误差 （MAE） 计算，平均绝对偏差越小，预测的准确度越高。
实验过程与结果分析
(1)确定最佳聚类数
首先，通过比较不同聚类数相应的聚类有效性函数值来选出最佳聚类数cmax。实验结果如图3.2所示。
size(sc) withinss(sc) plot(testMatrix, col=sc)
图3.2 Flixster数据集不同聚类数对应的聚类有效性函数值
图3.2中的横坐标为聚类数，纵坐标为相应的4个聚类有效性函数值。由上述结果可知，在2到最佳搜索范围中，不同的聚类数c得到的VPE值与VFC值呈单调趋势，而VXB与VK函数值均在c=12时单调性发生改变。
表3.3 Xie-Beni方法确定的最佳聚类数cmax
| 判别函数 | VPE | VXB | VFC | VK |
| Flixster数据集 | cmax>25 | cmax=10 | cmax>25 | cmax=10 |
因此， 本文选取Flixster数据集的最佳聚类数cmax为12，本文选取最佳聚类数cmax为12。
（2）MAE指标比较
模糊C均值聚类算法的关键步骤是确定最佳聚类簇数，为检验本节给出的FCMC CF算法，我们在Flixster数据集上进行了实验分析，并将其同K-means、K-medoids和K-mode聚类协同过滤算法进行了比较，实验结果如图3.4和3.5所示。
preR=matrix(1,RECOMMENDER_NUM,ncol(M)) for(item in 1:ncol(M)){ R<-ItemBasedRecommenderlist(item,RECOMMEN lusplot(y[,1:2], cl$cluster , color=TRUE, shade=TRUE , labels=2, lines=0)
图3.4 不同算法MAE的比较
点击标题查阅往期内容
01
02
03
04
图3.5 不同算法MAE的比较
在图3.4和图3.5中，横轴为最近邻个数 k，纵轴为平均绝对偏差 MAE。曲线CF代表传统的协同过滤算法，曲线Kmean CF代表基于K均值聚类的协同过滤算法，曲线FCMC CF代表基于模糊C均值聚类有效性的协同过滤算法，曲线K medoids CF代表基于K medoids聚类的协同过滤算法。
由图3.4和图3.5可以看到基于有效性指标改进的FCMC CF算法在MAE指标上要明显优于其他算法。在Flixster数据集上的实验结果表明，FCMC CF得到的MAE值要优于其他几个算法。
（3）召回率和覆盖率的比较
在接下来的TOP-N实验中，我们选择FCMC CF算法与其他算法在召回率、覆盖率指标上进行比较。实验结果如图3.6和图3.7所示。
图3.6 不同算法覆盖率的比较
plot(seq(from=5, to=50, by=10),Coverage,type="l")
图3.7 不同算法召回率的比较
在图3.4和图3.5中，横轴代表推荐列表长度N，纵轴分别为召回率和覆盖率。其中，每个N值对应的两条曲线图分别为FCMC CF与CF、Kmeans CF对应的函数值。
FCMC CF算法与传统CF算法和Kmeans CF算法相比，在不同的最近邻水平下具有较高的召回率和覆盖率，即新算法在推荐质量上有所改善，有效地提升了推荐精度。
结论与展望
本文对社会化推荐系统进行了研究，将谱聚类算法、聚类集成技术应用到社会化推荐算法中，对传统的协同过滤推荐算法进行改进。
主要取得了如下成果：
（1）将社交网络信息和谱聚类算法应用到传统协同过滤算法中，提出了基于用户谱聚类的社会化推荐算法，在一定程度上缓解了数据稀疏性问题。在数据集上的实验表明，改进的算法提高了传统算法的推荐性能。
（2 ）针对处理大规模数据集时谱聚类算法执行效率较低的问题，使用Nyströ m 扩展方法对谱聚类算法进行改进，提出了基于 Nyströ m 扩展谱聚类的社会化推荐算法。实验结果表明，该算法在缩短了算法的执行时间的同时提高了推荐的性能。
（3）为了提高聚类结果的稳定性和准确性，在推荐算法中引入了聚类集成技术，提出了基于用户谱聚类集成的社会化推荐算法。实验结果表明，引入聚类集成后的推荐算法在预测准确率、召回率、覆盖率等指标上都有了明显提高。
参考文献
[1]许海玲,吴潇,李晓东,阎保平. 互联网推荐系统比较研究[J]. 软件学报,2009,20(2):350-362
[2]曾子明.信息推荐系统[M]. 北京:科学出版社, 2013.
[3]Mooney R J, Roy L. Content-based book recommending using learning for text categorization[C]. Proceedings of the 5th ACM Conference on Digial Libraries, New York, 2000:167-176.
[4]Balabonovic M, Shoham Y. Fab:content-based collaborative recommendation[C]. Communications of the ACM,1997,40(3):66-72.
