【原创】数据挖掘课程论文：基于SVD的模糊C均值聚类的协同过滤算(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 方法将用户评分分解为不同的特征及这些特征对应的重要程度,利用用户与项目之间潜在的关系，用初始评分矩阵的奇异值分解去抽取一些本质的特征，首先利用目标用户的最近邻居对商品评价的加权平均值来预测他对目标项的喜好程度，然后采用奇异值分解技术，获得的隐含语义关系对用户喜好进行判断，最后系统根 …… 此处隐藏：1998字，全部文档内容请下载后查看。喜欢就下载吧 ……