【原创】基于模糊C均值聚类有效性的个性推荐算法附数据代码
- 格式：doc
- 大小：313.56 KB
- 文档页数：9
基于模糊C均值聚类有效性的协同过滤算法摘要：针对传统协同过滤算法普遍存在的稀疏性和扩展性问题，提出了一种基于模糊C均值聚类有效性的协同过滤算法。
首先依据聚类有效性指标确定合理的聚类簇数区间并搜寻得到最佳聚类簇数，然后在进行协同过滤前使用最佳聚类簇数对项目进行聚类，将用户对单个项目的偏好转化为对相似群组的偏好，旨在构造密集的用户-项目模糊簇评分矩阵。
在MovieLens数据集上实验结果表明，该方法确实可提高协同过滤推荐算法的推荐精度。
关键词：模糊C均值聚类；协同过滤；推荐系统；最佳聚类数；模糊聚类有效性A Personalization Recommendation Method Based on Fuzzy C-MeansClustering ValidityAbstract:Aiming at the sparse and cold-sart probelm of exising recommendation algorithms,this paper proposes a method which combines the similar relation in attributes and characters of items to user-based collaborative filtering recommendation algorithm based on fuzzy c-means clustering algorithm validity.The method preset some reasonable cluster numbers,and then chose a cluster number as the optimal cluster number by some representative validity ing the optimal number of cluster,this method transforms the users' preferences of single item to similar groups,which forms the dense preferences of users-fuzzy cluster before Using traditional collaborative filtering.Finally this method realizes the user-based collaborative filtering recommendation algorithm based on the above steps,tested on data set got from MovieLens.Keywords: Fuzzy C-Means Clustering; Collaborative filtering; Recommender system; Optimal number of cluster；Fuzzy cluster validity随着网络的普及，Web已成为人们获取信息的一个重要途径。
然而，网络信息量的不断膨胀，用户很难在众多的选择中挑选出自己真正需要的信息。
作为解决互联网中“信息过载”问题的有效手段，推荐系统被广泛应用在电子商务领域，它能主动为用户推荐需要但无法轻易获取的有用信息，在提供更具针对性的个性化服务的同时也提高了电子商务网站的销售量。
因此，推荐系统已成为当下电子商务应用领域中的研究热点。
在推荐系统中，最流行的方法有两种：基于内容过滤的推荐和协同过滤推荐。
其中，协同过滤推荐技术是目前最流行和最成熟的推荐技术[1-3]。
在实际应用中，随着推荐系统用户和项目数量的增加，一方面，由于用户评价过的项目占全体项目数量的比例很小，导致用户－项目评分矩阵的稀疏性，从而影响协同过滤算法的推荐质量[4]；另一方面，当用户和项目数目较大时，计算复杂度增加，导致该算法的效率降低。
针对以上的问题，许多学者进行了深入研究并取得了一系列出色的研究成果[5-14]。
比如文献[15][ Tsi CF, Hung C, Cluster ensembles in collaborative filtering recommendation[J]. Applied Soft Computing, 2012, 12(4):1417-1425.]使用K-means 方法对用户或是项目聚类，减少了寻找最近邻的开销，然而在实际应用中一个项目可能同时属于几个类，采用K-Means聚类方法属于硬聚类算法很难符合实际情况。
文献[16][Ling Zheng, Xinyu Zhao, Shuo Cui, Dong Yue, Hung C, An imporved personalized recommendation algorithm based on fuzzy clustering[C].3rd International Conference on Advanced Computer Theory and Engineering, 2010:408-412.][李华, 张宇, 孙俊华. 基于用户模糊聚类的协同过滤推荐研究[J]. 计算机科学, 2012, 39(12): 83-86.]提出了一种基于等价关系模糊聚类的协同过滤算法，通过设定一系列用户相似度阈值来对用户进行模糊聚类，并从理论和实验两个方面与传统的协同推荐算法进行了比较，但它们的缺点是为了确定最佳聚类阈值计算代价较大。
本文针对现有基于聚类的协同过滤算法存在的不足进行研究，在使用模糊C 均值聚类算法的基础上，引入了模糊聚类有效性指标函数，首先确定一个最佳的聚类簇数，从而解决了聚类对初始聚类中心过于敏感的问题，提出了基于模糊C 均值聚类有效性的协同过滤算法。
在MovieLens 公开数据集上的实验结果表明，本文提出的改进算法与传统协同过滤算法相比，可以获得更好的推荐质量。
1 基础定义及相关知识介绍1.1 协同过滤算法概述协同过滤算法是推荐系统中应用最广、效果最好的算法之一。
典型的协同过滤算法是基于用户的，其基本思想是通过用户-项目评分矩阵(表1)计算出用户之间的相似度，从中选出与用户最相似的前k 个用户，根据这k 个用户对当前用户的未评分项目的打分，预测当前用户对其未评分项目的打分，选出前n 个推荐。
协同过滤推荐算法的实现过程主要分为3步：建立用户模型、寻找最近邻居和产生推荐项目。
① 建立用户模型协同过滤算法的输入数据通常表示为一个m*n 的用户评价矩阵R ，m 是用户数，n 是项目数，ui R 表示第u 个用户对第i 项的评价值。
通常采用5级评分的办法，评分越高表明该用户对该项目的兴趣越大。
表1 用户-项目评价矩阵 Table1 User-item rating matrix② 寻找最近邻居在这一阶段，主要完成对目标用户最近邻居的查找。
通过计算目标用户与其他用户之间的相似度，找出与目标用户最相似的“最近邻居”集。
即：对目标用户u ，产生一个以相似度sim(u ，v)递减排列的“邻居集合”，即：对目标用户 u ，Nu={N1，N2,...,Ni}。
该过程分两步完成：首先计算用户之间的相似度，可采用皮尔森相关系数、余弦相似性和修正的余弦相似性等度量方法。
由于修正余弦考虑用户的平均评分，可以较好地保证寻找邻居的准确性，本文采用的是修正的余弦相似性(式1)。
设用户u 和v 共同评分过的项目集合用I uv 表示，I u 和I v 分别表示用户u 和用户v 评分过的项目集合，则用户u 和用户v 之间的相似性：()()(,)R R R R sim u v --=其中u R 表示用户u 的平均评分，v R 表示用户v 的平均评分。
③ 产生推荐项目最后根据当前用户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 ∈∈⋅-=+∑∑ (2)通过上述方法预测出目标用户对未评价项目的评分，然后选择预测评分最高的TOP-N 项推荐给目标用户。
1.2 模糊C 均值聚类理论（FCMC ）[17-18]简介聚类算法分为硬聚类算法和软聚类算法。
硬聚类算法将每个数据对象归到一个类，但是数据对象往往具有大量性和多样性的特点，经常可以被归到几个类中，归属于每个类的程度也不相同。
结合这一点就出现了C 均值的改进算法——模糊C 均值聚类算法。
[19-20]模糊C 均值聚类算法是由Ruspini 和Bezdek 于1981年提出的，目前被广泛应用。
模糊C 均值因算法设计简单，解决问题范围广，易于实现，被应用于很多领域。
它是一种非常有效的模糊聚类算法，使用每个样本隶属于某个聚类的隶属度，即使对于很难分类的变量，模糊C 均值聚类算法也能够得到比较满意的聚类效果。
对于论域中的有限个对象{}12,,,n X X X ⋅⋅⋅集合为一有限对象的集合，模糊Ｃ均值聚类是用隶属度确定每个数据点属于某个聚类程度的一种聚类方法。
FCMC 把n 个向量(1,2,,)i X i n =⋅⋅⋅分成ｃ个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数(式3)达到最小。
21111),,,(ijci nj m ij ci i c d u J H H U J ∑∑∑=====⋅⋅⋅...................................................................(3) 其中，]1,0[∈ij u ，i H 为模糊聚类i 的聚类中心，||||j i ij X H d -=为第i 个聚类中心与第j 个数据点之间的欧氏距离；),1[∞∈m 是一个加权指数。
1.3 模糊聚类的有效性模糊C 均值聚类算法可以方便快捷地判定数据集合中样本的类别，但是该算法属于无监督的学习，必须事先指定一个聚类数k 。
为此，不断有人对确定最佳聚类数k 进行研究,主要可以分为两类，一类是基于模糊划分的方法：认为好的聚类对应于数据集是较分明较明晰的，代表函数如Bezdek 提出的分割系数V PC 和分割熵V PE ；(Bedzek J C. Cluster Validity with Fuzzy Sets[J ]. Journal of Cybernetics ,1973 ,3(3) :58272.)另一类是基于几何结构的方法：认为每个子类应当是紧致的子类与子类相互间尽可能分离，代表函数有Xie 和Beni 的V XB ，(Xie X L,Beni G .A Validity Measure for Fuzzy Clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence,1991,8(13):8412847.)Fukuyama 和Sugeno 的V FC 、[Fukuyama Y ,Sugeno M.A New Method of Choosing the Number of Clusters for the Fuzzy C-Means Method.In:Proc.of the fifth Fuzzy Systems Sympo sium,1989, 247~250]Kwon 的V K 等[Kwon S H.Cluster Vali dity Index for Fuzzy Clustering[J].Electronics Letters,1998,34(22):21762 2177.]。
