数据分享｜R语言谱聚类社会化推荐挖掘协同过滤电影社交网站Flixster数据集应用研究

全文链接：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 数据集描述

评分预测的预测准确度一般通过平均绝对误差 （MAE） 计算，平均绝对偏差越小，预测的准确度越高。

实验过程与结果分析

(1)确定最佳聚类数

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

图3.2 Flixster数据集不同聚类数对应的聚类有效性函数值

图3.2中的横坐标为聚类数，纵坐标为相应的4个聚类有效性函数值。由上述结果可知，在2到最佳搜索范围中，不同的聚类数c得到的VPE值与VFC值呈单调趋势，而VXB与VK函数值均在c=12时单调性发生改变。

表3.3 Xie-Beni方法确定的最佳聚类数cmax

因此， 本文选取Flixster数据集的最佳聚类数cmax为12，本文选取最佳聚类数cmax为12。

（2）MAE指标比较

模糊C均值聚类算法的关键步骤是确定最佳聚类簇数，为检验本节给出的FCMC CF算法，我们在Flixster数据集上进行了实验分析，并将其同K-means、K-medoids和K-mode聚类协同过滤算法进行了比较，实验结果如图3.4和3.5所示。

图3.4  不同算法MAE的比较