---

可下载资源

所以，谱聚类算法成为近几年来机器学习领域的一个新的研究热点，处理方法以及机器学习本身算法理论的学习和代码实现在各领域具有相同性，之后同学可以在其他感兴趣的领域结合数据进行分析，利用此课题所学知识举一反三。

基于用户谱聚类集成的社会化推荐

聚类集成是将单个聚类算法的聚类结果合并成一个最终的聚类结果，集成后的聚类结果优于单个聚类算法的聚类结果。目前，聚类集成技术已经广泛应用于医学诊断、基因表达、非数值型计算等领域[2]。

2、聚类集体生成：

Step6：重复执行以上步骤 m 次，将生成的 m 个用户聚类矩阵 CN× N 相加，得到用户关联矩阵 NP。

Step7：对用户关联矩阵 NP 进行谱聚类。

Step8：根据谱聚类结果生成最终的用户关系矩阵 T’，当用户 i 与用户 j 属

于同一类时 T’ij=1，否则 T’ij=0。

（2）谱聚类集成技术

由于谱聚类算法中使用近似逼近的方法，以及谱聚类算法本身的初值敏感问题，聚类的结果并不十分稳定，采用聚类集成策略来解决这个问题。通过寻找多个聚类结果的组合来获得相对较优的聚类结果，从而获取较好的平均性能，提高聚类结果的稳定，并且一定程度上克服了谱聚类算法对噪音、异常点、采样的变动的敏感性问题。

---

---

（3）应用领域创新

将改进的谱聚类算法应用到基于社交网络的推荐系统中，克服了目前推荐系统中存在的准确性、实时性、稀疏性等问题。谱聚类算法实质上是对图的划分，而社交网络中用户之间的关系也表示为图的形式，因此对社交网络中相似用户群的划分可以使用谱聚类的方法。在使用谱聚类后的用户群中，寻找用户最近邻，然后预测用户对问评分项目的评分，最后产生推荐。

实验与结果分析

实验数据集

本文分别在两个代表性的数据集Flixster上对算法进行了测试。Flixster 是一个电影社交网站，在 Flixster 网站上用户分享电影的评分，讨论新的电影，也可以通过电影认识有相同爱好的人。本章选取电影社交网站Flixster 的用户数据作为实验数据集。该数据集包含两个部分，一部分是用户评分数据，包含 885个用户对 1000个电影的评分记录 192775 条。用户评分值介于 0.5-5 之间，评分间隔为 0.5，数值越大，说明用户对项目的喜爱程度越高，反之，说明用户对项目兴趣度不高；另一部分是用户朋友关系数据，包含以上892个用户之间的朋友关系。 数据集示例如图 3.2 所示。 实验中随机抽取用户评分数据集的 80%作为训练集，其余 20%作为测试集。

 表3.2 数据集描述

名称	描述	简介	每个用户至少评分物品
Flixster	对电影的评分从1到5	885名用户对1000部电影的评价	100

实验过程与结果分析

(1)确定最佳聚类数

首先，通过比较不同聚类数相应的聚类有效性函数值来选出最佳聚类数cmax。实验结果如图3.2所示。

size(sc)
withinss(sc)
plot(testMatrix, col=sc)

图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算法，我们在Movielens和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的比较

 图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指标上要明显优于其他算法。在Movielens和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.