【原创】数据挖掘课程论文：基于SVD的模糊C均值聚类的协同过滤算法附数据代码

上海大学2013-2014学年冬季学期硕士研究生课程考试

课程名称：数据挖掘与商务智能文献阅读课课程编号：29SBG9016课程名称：博弈论文献阅读课课程编号： 291101911

课程名称：系统理论与战略管理文献阅读课课程编号： 291101904

论文题目：基于SVD的模糊C均值聚类的协同过滤算法

研究生姓名（学号）：

论文评价：

论文成绩：

任课教师：评阅日期：2014年6月

基于SVD的模糊C均值聚类的协同过滤算法

摘要：针对传统协同过滤算法普遍存在的实时性、稀疏性和扩展性的问题，本文提出了一种基于SVD 矩阵填充技术的模糊C均值聚类协同过滤算法。首先利用SVD降维方法对原始的高维稀疏矩阵进行预测填充,得到一个缺失值较少的评分矩阵，然后利用模糊C均值聚类算法在填充完整的数据上对用户进行聚类，最后在用户所属类中寻找目标用户最近邻并产生推荐。该算法利用用户与项目之间的潜在关系克服了稀疏性问题，同时保留了聚类方法可离线建模、可扩展性好等优点。在MovieLens数据集上实验结果表明，该方法确实可提高协同过滤推荐算法的推荐精度。

关键词：SVD；模糊C均值聚类；协同过滤；推荐系统

SVD-Based Fuzzy C-Means Clustering Collaborative Filtering Algorithm

Ge Lintao

School of Management, Shanghai University, Shanghai 200444

Abstract:Aiming at the weakness of low real-time ability, data sparse and scalability probelm of exising recommendation algorithms, a SVD-based Fuzzy C-means clustering CF algorithm is proposed. The algorithm first fill the missing ratings by SVD prediction, and then implement Fuzzy C-means clustering in the filled matix. Finally, according to the user’s cluster it finds the nearest neighbors of the object user and generates recommendations. This algorithm overcomes the data sparsity issue via SVD and keep the advantage of clustering, such as good real-time ability and scalability. The experimental results on MovieLens show that the new algorithm improves recommendation quality in MAE, recall and coverage.

Keywords: SVD; Fuzzy C-Means Clustering; Collaborative filtering; Recommender system

随着互联网技术的不断发展、网络的不断普及，Web已成为人们获取信息的一个重要途径。然而，网络信息量的不断膨胀，用户很难在众多的选择中挑选出自己真正需要的信息，网上已出现“信息过载”问题。作为解决互联网中“信息过载”问题的有效手段，推荐系统被广泛应用在电子商务领域，它能主动为用户推荐需要但无法轻易获取的信息，在提供更具针对性的个性化服务的同时也提高了电子商务网站的销售量。这些系统的例子包括：卓越亚马逊（http://www.77cn.com.cn）、当当网（http://www.77cn.com.cn）为用户推荐各种其可能喜欢的商品，如书籍、音像、电器、服装等；Netflix电影出租系统（http://www.77cn.com.cn）为用户推荐各种其可能喜欢的电影；Google、Baidu、Yahoo等为用户推荐这种个性化的新闻和搜索服务。GroupLens[1]首先使用了最近邻方法来进行协同过滤，该系统为Usenet用户提供对新闻的个性化推荐。因此，推荐系统已成为当下电子商务应用领域中的研究热点。

一般来说，推荐系统通常使用两种不同的策略。基于内容的方法（Content-Based Approach）为每个用户和商品建立一个文档来刻画他们的特征。比如一个电影文档可以包括该电影的年代，演员和内容简介等。一个用户文档可以包括用户的性别、年龄、职业等人口特征。这样，程序就可以搜索用户和与之匹配的商品。但是，基于内容的方法需要搜集额外的信息，而这些信息往往不容易得到。另一种策略是协同过滤（Collaborative Filtering，CF），是目前电子商务推荐系统中最成功和应用最广泛的技术[2-4]，在理论研究和实践中都取得了快速的发展。协同过滤的算法核心是分析用户兴趣，在用户群中找到与指定用户的相似（兴趣）用户，综合这些相似用户对某一信息的评价，形成系统对该指定用户对此信息的喜好程度预测，因此它依靠的是用户过去行为，而并不需要建立一个文档，根据用户的历史选择信息和相似性关系，收集与用户兴趣爱好相同的其他用户的评价信息利用数据挖掘的一些算法来产生推荐。和基于内容的方法相比，协同过滤具有前者没有的一些优点：（1）支持过滤不容易分析内容的商品。（2）基于特征与爱好的过滤。（3）具有发现意想不到的巧妙推荐。然而，在实际应用中，随着电子商务网站用户和资源数量不断地膨胀增加，

传统的协同过滤算法面临数据稀疏用户相似性难以度量，实时性和可扩展性差等方面的挑战，影响了推荐系统的质量，存在的三个主要问题是：（1）提高协同过滤算法的应用数据的规模，即可扩展性。现代商业系统中的用户、商品数量是非常多的，如何提高协同过滤算法在大规模数据上的实时计算变得非常重要。（2）解决协同过滤算法的应用数据的稀疏程度，即稀疏性。在实际中，用户和项目的数量都非常大，在这种情况下，评分矩阵就会极度的稀疏，这个问题就是通常说的稀疏性问题，对协同过滤的算法有着消极的影响。由于这个问题的存在，两个用户之间的相似度非常有可能为0。这种情况称邻居传递损失。例如，如果用户u和用户v具有很高的相关性，并且用户v和用户w也具有很高的相关性，那么用户u和用户w 不一定具有很高的相关性，因为他们可能具有很少的共同的评分，甚至可能由于具有很少的评分而导致具有负的相关性。（3）解决新用户进入无法推荐的问题，即冷启动问题。例如，当一个新用户刚刚注册之后，并没有足够的历史信息来找出这个用户的兴趣偏好，这时协同过滤算法的预测效果往往就不那么准确。然而当一个用户拥有足够多的历史信息之后，通过协同过滤对于此用户的预测结果会有明显的提高，随着互联网行业竞争日益加剧，为吸引用户留给用户的第一印象就显得十分重要，因此如果能够有效解决新使用者问题，在新用户刚注册网站时就给出准确的预测与推荐，将可能留住更多的用户群体。

正是由于协同过滤有如此良好的特性，以及现实存在的诸多问题，因而引起了研究者的研究兴趣，并得到了广泛的商业应用。针对以上的问题，许多研究者进行了相关研究。如文献[5]提出一种基于项的最近邻法。对于项来讲，它们之间的相似性要稳定很多，因此可以离线计算相似性，从而大大降低了在线计算量，提高了推荐效率，但是项之间同样面临共同评分过少的问题。文献[6]提出一种基于项目评分预测的协同过滤推荐技术，通过估计用户评分的办法补充用户评分矩阵，减小数据稀疏性对计算结果的负面影响。也有一些学者提出了利用矩阵分解或者降维的方法来解决推荐系统数据稀疏和可扩展性差的问题，如奇异值分解(SVD)[7-8]、非负矩阵分解(Nonnegative Matrix Factorization，简称NMF)、主成分分析(Principal Component Analysis，简称PCA)等，有效地降低训练数据的维度和稀疏性[9-10]。如国际上Eigenstate[11]使用PCA分解结合递归聚类的方法来估计评分。它从原矩阵中抽出一部分评分数据形成一个子集，在这个子集组成的相对完整的矩阵基础上使用PCA方法，从而解决了矩阵稀疏问题。然而这种忽略其他评分数据的做法降低了预测精度，而且在实际情况下，如何抽取数据是个不容易解决的问题。Koren，A.Paterek，D.D.Lee 等提出了基于传统的矩阵分解模型（SVD）的协同过滤算法[12-14]。基于奇异值分解的协同过滤算法在生成评分预测的时候仅需要做一些简单的算术运算，因此具有很好的在线性能，但在计算SVD过程中代价很高，而且还要面对矩阵稀疏的问题。因此，文献[15]提出了使用折叠（folding-in）技术的增量SVD算法，极大地提高了奇异值分解速度，但是由于增量SVD空间特征向量的非正交性，使得计算精度下降。国内的徐翔，王煦法等对基于SVD的协同过滤算法也进行了相应研究[16]。国内中山大学的潘嵘还将矩阵分解模型运用到了单类问题[17-18]。也有学者将聚类技术引入协同过滤中有效提高系统实时性，大量文献[19-23]使用K-means方法对用户或是项目聚类，减少了寻找最近邻的开销，但是在实际应用中一个项目可能同时属于几个类，采用硬聚类算法很难符合实际情况。文献[24]中将模糊C均值聚类应用到协同过滤算法中，有效缓解由于数据稀疏带来的推荐精度问题。尽管基于聚类的协同过滤算法改善了传统协同过滤算法的一些弊端，但是当数据非常稀疏时，基于聚类的协同过滤算法推荐精度往往较低同时，奇异值分解(SVD)在处理高维稀疏数据时效果比较好。

基于上述工作，本文针对传统协同过滤算法在线计算量较大且可扩展性较低的缺点，结合了SVD和聚类两者的优点，提出了一种基于SVD矩阵填充技术的Fuzzy C-means聚类协同过滤算法。该算法利用用户与项目之间的潜在关系克服了稀疏性问题，同时保留了聚类方法可离线建模可扩展性好等优点。在MovieLens公开数据集上的实验结果表明，本文提出的改进算法与传统协同过滤算法相比，可以获得更好的推荐质量。

1 基础定义及相关知识介绍

1.1 协同过滤算法概述

协同过滤算法是推荐系统中应用最广、效果最好的算法之一。典型的协同过滤算法是基于用户的，其基本思想是通过用户-项目评分矩阵(表1)计算出用户之间的相似度，从中选出与用户最相似的前k个用户，

根据这k 个用户对当前用户的未评分项目的打分，预测当前用户对其未评分项目的打分，选出前n 个推荐。 协同过滤推荐算法的实现过程主要分为3步：建立用户模型、寻找最近邻居和产生推荐项目。

1) 建立用户模型

协同过滤算法的输入数据通常表示为一个m n ?的用户评价矩阵R ，m 是用户数，n 是项目数，ui R 表示第u 个用户对第i 项的评价值。通常采用5级评分的办法，评分越高表明该用户对该项目的兴趣越大。该评分矩阵记载了用户对项目的主观评分，要么由用户显示确定，要么由系统隐式推断得出。一旦了确定了评分矩阵，推荐系统就能够做出用户对未评分项目的预测评分，从而产生推荐。

表1 用户-项目评价矩阵

2) 寻找最近邻居

在这一阶段，主要完成对目标用户最近邻居的查找。通过计算目标用户与其他用户之间的相似度，找出与目标用户最相似的“最近邻居”集。即：对目标用户u ，产生一个以相似度sim(u ，v)递减排列的“邻居集合”，即：对目标用户u ，Nu={N1，N2，…，Ni}。该过程分两步完成：首先计算用户之间的相似度，可采用皮尔森相关系数、余弦相似性和修正的余弦相似性等度量方法。由于修正余弦考虑用户的平均评分，可以较好地保证寻找邻居的准确性，本文采用的是修正的余弦相似性(式2)。

余弦相似性(Cosine Correlation ，CC)：用户对n 个项目的评分可视为n 维向量，用户和用户的相似性即为相应两个n 维向量的夹角余弦：

(,)ui vi

R R sim u v

(1)

用余弦相似性计算相似度，计算速度较快，实现起来简单。但是，这种度量方法未考虑用户评分尺度的问题，计算出的邻居数据不够准确。

修正余弦相似性(Adjusted Cosine Correlation ，ACC)：修正余弦相似性考虑了用户的评分尺度问题，可由如下公式定义：

()()

(,)ui u vi v R R R R sim u v --=

(2)

其中表示用户的平均评分，表示用户的平均评分。修正余弦考虑用户的平均评分，可以较好地保证寻找邻居的准确性。

Pearson 相关相似性(Pearson Correlation ，PC)：在这类方法中，通过计算两个用户的Pearson 相关系数来确定它们之间的相似性。Pearson 相关相似性可由如下公式计算得到：

()()

(,)R R sim u v -- (3)

其中表示用户的平均评分，表示用户的平均评分。 3) 产生推荐项目

最后根据当前用户m 个最近邻居对项目的评分信息预测当前用户对其未评分项目的评分，以此产

生TopN 推荐。目标用户u 对任意项目i 的预测评分P u,i 可通过邻居用户S (u )(即v )对项目i 的评分得到，计算方法如下：

()()(,)()

|(,)|vi v v S u ui u v S u sim u v R R P R sim u v ∈∈?-=+∑∑ (4)

通过上述方法预测出目标用户对未评价项目的评分，然后选择预测评分最高的TOP-N 项推荐给目标用户。

1.2 奇异值分解（SVD ）算法

奇异值分解(Singular Value Decomposition ，简称SVD)是一种常用的矩阵分解技术，能够有效地提取代数特征，深刻揭示了矩阵的内部结构，奇异值分解在图像压缩、最小二乘法等方面有着广泛的应用[25]。目前，奇异值分解在信息检索方面的应用主要是隐含语义检索(Latent Semantic Indexing ，LSI)。潜在语义索引可以将文档在向量空间模型中的高维表示，投影到低维的潜在语义空间中，这一方面缩小了检索的规模，另一方面也在一定程度上避免了数据的过分稀疏。

矩阵分解模型的中心思想是将用户-物品评分矩阵分解成若干规模较小的矩阵乘积，本文中使用增量奇异值矩阵分解的方式将用户-物品评分矩阵R 分解为两个矩阵的乘积，s 这样做有两点好处：能够有效减少空间复杂度，能够提取出隐藏的k 维属性，为预测矩阵缺失值(用户对物品评分的预测)提供依据。

SVD 是矩阵维数简化的一种常用方法，它将一个m ×n 的矩阵R 分解为3个矩阵。R U S V =??，其中U 是一个m ×m 的正交矩阵，V 是一个n ×n 的正交矩阵，S 是一个m ×n 的对角矩阵，它的对角线上的元素由上往下依次递减。Sarwar 通过将用户对未评分项的评分设为一个固定的缺省值来减少数据集的稀疏性。将矩阵R 中评分值为0的项用相关列的项目评分平均值代替，接着将矩阵每行规范化为相同长度，用

ij i R R -代替原来的R ij (i R 是第i 个用户的平均评分值）

。规范化为相同长度后，选择项目数较多的用户对相似度计算结果的影响降低了。经过这样的预处理得到矩阵'R ，作为SVD 算法的输入矩阵，其算法流程如下：

输入：矩阵R 。

输出：矩阵U 、S 、V 。

步骤：

1)将矩阵R 中的缺失值用对应列的平均值i r 代替；

2)用ij i r r -代替矩阵R 中的元素ij r ，得到矩阵'R ；将'R 进行奇异值分解，得到三个矩阵'U 、'S 、'V ；

3)简化S ’，将其对角线上小于1的值用0代替，而后将对应的全为0的行或者列删除，得到一个k 维的对角矩阵S ；

4)利用矩阵S 简化'U 、'V ，得到U 、V ，则矩阵'R 可简化为",'''R U S V R R =??≈；

5)

U

T V 。

在第三步中，如果原始数据高维稀疏的话，得到的简化矩阵S 的维数k 要远小于初始的维度n ，因此经过奇异值分解后，大大降低了原始数据的稀疏性，进而可以产生较好的推荐精度。

1.3 模糊C 均值聚类理论（FCMC ）简介

聚类算法分为硬聚类算法和软聚类算法。硬聚类算法将每个数据对象归到一个类，但是数据对象往往具有大量性和多样性的特点，经常可以被归到几个类中，归属于每个类的程度也不相同。结合这一点，Ruspini 和Bezdek 于1981年提出了C 均值的改进算法—模糊C 均值聚类算法(FCMC)[26]。模糊C 均值聚类算法因其设计简单、解决问题范围广、易于实现等特点，被应用于很多领域。它是一种非常有效的软聚类算法，使用每个样本隶属于某个聚类的隶属度进行聚类，即使对于很难分类的变量，模糊C 均值聚类算法也能够得到比较满意的聚类效果。

模糊C 均值聚类算法是一种基于函数最优方法的聚类算法，使用微积分计算技术求最优代价函数。在基于概率算法的聚类方法中将使用概率密度函数，为此要假定合适的模型。模糊聚类算法中向量可以同时属于多个聚类，从而解决假定合适模型困难的问题。

对于论域中的有限个对象｛X 1,X 2,...,X n ｝集合为一有限对象的集合，模糊Ｃ均值聚类是用隶属度确定每个数据点属于某个聚类程度的一种聚类方法。FCMC 把n 个向量X i (i=1,2,...,n )分成ｃ个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数(式5)达到最小。

21111),,,(ij

c i n

j m ij c i i c d u J H H U J ∑∑∑=====??? (5) 其中，u ij [0,1]∈，H i 为模糊聚类i 的聚类中心，d ij =||H i -X j ||为第i 个聚类中心与第j 个数据点之间的欧氏距离；m [1,)∈∞是一个加权指数。

我们采用拉格朗日最值法可以求得式(5)达到最小值的必要条件，构造函数如下：

1111121111(U,H ,...,H ,,...,)J(U,H ,...,H )(1)(1),c n n c

c j ij j i c n n c

m ij ij j ij i j j i J u u

d u λλλλ=======

+-=+-∑∑∑∑∑∑ (6)

其中，(j 1,2,...,n)j λ=是n 个拉格朗日乘子。对所有输入参数求导，用h i 表示H i 的第i 个属性，得到

式(5)达到最小的必要条件为：

1

1n m ij j j i n

m ij j u

x c u

===∑∑ (7) 2/(1)11ij m c

ij k kj u d d -==?? ? ???∑ (8) 总的来说可归纳为以下四个步骤：

步骤1：用值在0到1之间的随机数初始化隶属矩阵U 。

步骤2：用式(7)计算c 个聚类中心c i ，i=1，…，c 。

步骤3：根据式(5)计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数值的改变量小于某个阀值，则算法停止。

步骤4：用(8)隶属度计算新的U 矩阵，返回步骤2。

2 基于SVD 的模糊C 均值聚类的协同过滤算法

基于聚类的协同过滤算法改善了传统协同过滤算法的一些弊端，但是当数据非常稀疏时，基于聚类的协同过滤算法推荐精度往往较低[27]，而SVD 在处理高维稀疏数据时效果比较好。Sarwar 等人首次将SVD 算法应用到协同过滤中[28]，他使用SVD 方法将用户评分分解为不同的特征及这些特征对应的重要程度,利用用户与项目之间潜在的关系，用初始评分矩阵的奇异值分解去抽取一些本质的特征，首先利用目标用户的最近邻居对商品评价的加权平均值来预测他对目标项的喜好程度，然后采用奇异值分解技术，获得的隐含语义关系对用户喜好进行判断，最后系统根据这一喜好程度来对目标用户自动进行推荐。

因此，本文结合了SVD 和聚类两者的优点，先采用SVD 方法对原始高维稀疏数据进行预测填充，而后在得到的不含缺失值的矩阵上再进行Fuzzy C-means 聚类，从而对用户产生推荐。具体步骤描述如下：

第一步：首先利用SVD 对原始的稀疏矩阵进行平滑，填补缺失值。

在训练集上，根据文献[28]，目标用户u 在项目i 上的预测评分可通过以下公式9得到：

,)'()u i u k k P R U u i =+ (9)

本文来源：https://www.bwwdw.com/article/7zyh.html