基于用户模糊聚类的个性化推荐研究
胡朝举+孙克逆
摘 要:推荐系统是根据用户的历史浏览记录或对项目的评分记录,自动为用户推送需要的信息,完成个性化推荐功能,是信息获取领域非常重要的技术。首先对用户进行模糊C均值聚类操作,将用户分为用户簇。将加权的欧氏距离替换传统的欧氏距离计算方法,在目标用户所在的用户簇内进行协同过滤推荐,得到Top-n推荐集,为用户完成项目推荐。实验结果表明,该方法可以提高推荐精度,减少评分误差,提高推荐质量,优化推荐效果。
关键词:模糊聚类;推荐系统;协同过滤;加权欧氏距离
DOIDOI:10.11907/rjdk.172225
中图分类号:TP301
文献标识码:A 文章编号:1672-7800(2018)002-0031-04
0 引言
随着Web2.0的飞速发展,互联网技术日益成熟,人类进入信息超載(Information Overload)时代。如何在爆炸的信息中获取想要的信息,是信息时代面临的最大挑战。人们通过搜索引擎找到自己感兴趣的信息[1],但搜索引擎并不能完全满足需求,因为有时需求并不是很明确,无法通过搜索引擎搜索,于是推荐系统应运而生。通过分析用户的一些行为习惯自动给用户推荐各种信息,且推荐内容根据用户的行为变化实时更新,能够最大程度地提高用户体验,为用户带来最精准的互联网信息。
当今的推荐技术中,协同过滤是最为成熟、应用最成功的技术。该技术主要针对用户-项目评分矩阵进行推荐[2],但该技术有很多不足,如最典型的稀疏性问题和实时性问题。由于用户不可能对每个项目进行评分,所以当项目评分矩阵比较稀疏时,进行用户相似度计算会产生较大的误差,且在整个用户中寻找相似用户花费时间较长,从而影响推荐效率。
本文在进行协同过滤推荐前,首先对用户进行聚类操作,通过模糊聚类算法把兴趣爱好类似的用户分到一类,即同一个簇中;针对待推荐用户所在的簇,通过协同过滤算法进行用户相似度计算,最后得到待评价项目的预测值,产生Top-N推荐[3]。聚类技术的引入可以缩小相似邻居的计算范围,从而减少推荐算法的时间。同时,本文针对聚类中距离的计算进行了改进。实验表明本文方法可以优化聚类效果,提高推荐质量。
1 基于用户模糊聚类的协同过滤推荐
1.1 模糊C-均值聚类(FCM)
模糊聚类的本质就是针对对象的某些属性来构建模糊矩阵,然后通过一定的方法进行分类操作,模糊聚类算法分类比较简单且分类效果较好。
模糊C-均值聚类(FCM)是J.C.Dunn按照E.Ruspini[4]定义的模糊划分集合的概念,从硬C-均值聚类算法推广得到的,最大的不同是在隶属度uij上乘一个权重值m[5]。FCM的数学模型如下:
1.2 FCM在用户-项目评分矩阵中的应用
1.2.1 用户-项目评分问题的数学模型
将模糊聚类引入评分矩阵X中,该矩阵表示n个用户对m个项目进行评价,(xik)n表示用户i对项目k的评分,需要根据用户对各个项目的评分对用户进行聚类,将用户分为c个簇,使得同一个簇中的用户相似性最高,并且把聚类的结果通过矩阵U表示出来,其中uki表示用户i对用户簇k的隶属度。
针对用户模糊聚类的函数为:
式(10)中:uki表示用户i在用户簇k中的隶属程度,dki表示用户i与用户簇k的聚类中心距离(通常为欧几里德距离),ck表示用户簇k的中心点,即该簇的聚类点,m表示决定聚类结果模糊度的权重指数,一般1.25≤m≤2.5。参考国内外文献和实验,将m设为2。
本模糊聚类的基本原理为:计算用户与各个聚类中心间的距离,通过得到的距离值计算用户和各个聚类中心的隶属度,通过比较隶属度高低,将用户分到最高的隶属度用户簇中,使同一个用户簇中的用户之间相似度最高,减少不同簇用户之间的相似度。
所以,要求得用户-评分模糊聚类的最优值,只需找到最佳的聚类中心点ck,k∈1,c和各个用户对聚类中心的隶属度uki,i∈1,n即可。
1.2.2 FCM聚类算法
为了解得模糊聚类目标函数的最优值,利用模糊聚类法则,在极值的约束条件[7] ∑ck=1uki=1下,求min{Jm(U,c)},构建拉格朗日函数,如式(11)所示:
1.3 基于用户的协同过滤算法
基于用户的协同过滤算法是分析其他用户观点,为目标用户产生推荐[9],其基本思想是:如果某几个用户对项目的评分类似,则称他们为“邻居用户”,他们之间就可能会有相同的兴趣爱好,就可以把其他用户喜欢的推荐给目标用户。
1.3.1 用户相似度
协同过滤算法中最主要的是用户最近邻查询,本文只需在目标用户所在簇中计算出与目标用户最相近的邻居,然后进行预测评分。度量两个用户之间的相似度需要首先获得两个用户对项目的所有评分,然后通过相似度度量公式计算两个用户之间的相似度,记为sim(i,j),其中i,j分别代表两个用户。用户相似度计算方法有很多,本文采用相关相似性来度量,计算公式如下:
1.3.2 预测评分
在利用协同过滤算法完成用户相似性度量之后,下一步就是预测评分,利用公式(16)对目标用户未评分的项目进行预测,将评分按降序排列,把排名前n个项目推荐给用户。
2 相关算法改进
2.1 模糊聚类距离计算方法改进
模糊C均值算法最重要的步骤是距离计算,计算各个用户与聚类簇中心点的距离。距离的计算方法有很多,如欧氏距离、马氏距离、相关系数法、最小算术平均法等,其中最常用的就是欧氏距离,计算公式如下[11]:
欧氏距离使用方便,计算简单,但是也有非常严重的缺陷。它将用户对不同项目的兴趣爱好视为“一般重要”,这样不能体现出不同项目对不同用户的重要程度,所以在一些情况下使用欧氏距离公式计算距离,聚类结果效果不理想。
本文用加权的欧氏距离来替换传统的欧氏距离,通过对不同的分量进行不同的权重分配,改进了聚类效果,计算公式如下:
式(17)中,si是对应的方差,可将方差的倒数看作一个权重,弥补欧氏距离的缺陷,提高聚类效果。
2.2 推荐过程
首先通过模糊C均值聚类算法将用户进行分类,然后在各个用户簇中使用协同过滤算法进行用户推荐,算法流程如图1所示。
3 实验结果及分析
3.1 数据集
本文实验采用的数据集为MovieLens网站提供的电影评分数据集,该数据集包括各种用户对各个类别电影的评分,分值为1-5,本文使用932个用户对1538部电影超过9000次的评分数据进行实验。将所有的数据平均分为5组,每次选择其中4组作为训练集,另外一组作为测试集,进行5次实验。
本实验采用的衡量标准为平均绝对偏差(MAE),其基本原理是通过计算整个算法对目标项目的预测值,和用户实际评分值之间的误差来衡量整个算法的优劣。MAE值越低,说明推荐的准确度越高。计算公式如下:
3.2 实验结果
对用户进行模糊C均值聚类,采用相关相似性计算方式进行相似度计算。由于分成不同数量的簇可能会对推荐结果产生较大的影响,所以本实验将分别对不同数量的聚类中心进行测试,通过与传统的协同过滤以及以普通欧氏距离为聚类距离计算的算法对比,验证本方法的优劣。本实验测试的聚类中心个数为5-50,间隔为5,实验结果如图2所示。
从图2可以看出,随着聚类中心的增加,MAE值呈变大的趋势,说明推荐的精度越来越低,推荐质量越来越差。由折线图可以看出,本文使用加权欧氏距离推荐算法,在推荐精度上要高于传统的模糊聚类推荐算法,所以本算法可以提高推荐系统的推荐质量。
3.3 实验结果分析
本实验通过不断的对比测试验证本算法的优势,通过实验结果可以得出,本文的推荐算法跟传统的协同过滤算法以及传统欧氏距离的模糊聚类推荐算法相比,在推荐精度上具有一定的提高。
因为传统欧氏距离计算的是各个点之间的绝对距离,未考虑到样本之间不同屬性的差别,所以未满足实际需求。本文将加权的欧氏距离代替传统的欧氏距离计算,弥补了传统欧氏距离的缺陷,提高了推荐质量。
参考文献:
[1] 冯刚.基于J2EE的多语种元搜索引擎的研究与实现[D].成都:电子科技大学,2006.
[2] 刘明.基于聚类和会话情景的混合推荐算法研究[D].武汉:华中科技大学,2013.
[3] 李华,张宇,孙俊华.基于用户模糊聚类的协同过滤推荐研究[J].计算机科学,2012,39(12):83-86.
[4] ABBATTISTA F,DEGEMMIS M,LICCHELLI O.Improving the usability of an E-commerce web site through personalization[C].Proceedings of Workshop on Recommendation and Personalization in E-commerce,2002:231-278.
[5] 范九伦,吴成茂.FCM算法中隶属度的新解释及其应用[J].电子学报,2004,32(2):350-352.
[6] 熊拥军,刘卫国,欧鹏杰.模糊C-均值聚类算法的优化[J].计算机工程与应用,2015,51(11):124-128.
[7] 张乾君.模糊聚类分析在企业竞争情报系统中的应用研究[D].西安:西安电子科技大学,2011.
[8] 孙静.基于模糊聚类的电子商务协同过滤推荐研究[D].天津:河北工业大学,2011.
[9] 薛扣平.具有可信机制的推荐系统及其应用研究[D].南京:东南大学,2008.
[10] 胡斌.基于用户和资源权重的协同过滤推荐系统的研究与设计[D].武汉:武汉理工大学,2009.
[11] 光俊叶,刘明霞,张道强.基于有效距离的谱聚类算法[J].计算机科学与探索,2014,8(11):1365-1372.
摘 要:推荐系统是根据用户的历史浏览记录或对项目的评分记录,自动为用户推送需要的信息,完成个性化推荐功能,是信息获取领域非常重要的技术。首先对用户进行模糊C均值聚类操作,将用户分为用户簇。将加权的欧氏距离替换传统的欧氏距离计算方法,在目标用户所在的用户簇内进行协同过滤推荐,得到Top-n推荐集,为用户完成项目推荐。实验结果表明,该方法可以提高推荐精度,减少评分误差,提高推荐质量,优化推荐效果。
关键词:模糊聚类;推荐系统;协同过滤;加权欧氏距离
DOIDOI:10.11907/rjdk.172225
中图分类号:TP301
文献标识码:A 文章编号:1672-7800(2018)002-0031-04
0 引言
随着Web2.0的飞速发展,互联网技术日益成熟,人类进入信息超載(Information Overload)时代。如何在爆炸的信息中获取想要的信息,是信息时代面临的最大挑战。人们通过搜索引擎找到自己感兴趣的信息[1],但搜索引擎并不能完全满足需求,因为有时需求并不是很明确,无法通过搜索引擎搜索,于是推荐系统应运而生。通过分析用户的一些行为习惯自动给用户推荐各种信息,且推荐内容根据用户的行为变化实时更新,能够最大程度地提高用户体验,为用户带来最精准的互联网信息。
当今的推荐技术中,协同过滤是最为成熟、应用最成功的技术。该技术主要针对用户-项目评分矩阵进行推荐[2],但该技术有很多不足,如最典型的稀疏性问题和实时性问题。由于用户不可能对每个项目进行评分,所以当项目评分矩阵比较稀疏时,进行用户相似度计算会产生较大的误差,且在整个用户中寻找相似用户花费时间较长,从而影响推荐效率。
本文在进行协同过滤推荐前,首先对用户进行聚类操作,通过模糊聚类算法把兴趣爱好类似的用户分到一类,即同一个簇中;针对待推荐用户所在的簇,通过协同过滤算法进行用户相似度计算,最后得到待评价项目的预测值,产生Top-N推荐[3]。聚类技术的引入可以缩小相似邻居的计算范围,从而减少推荐算法的时间。同时,本文针对聚类中距离的计算进行了改进。实验表明本文方法可以优化聚类效果,提高推荐质量。
1 基于用户模糊聚类的协同过滤推荐
1.1 模糊C-均值聚类(FCM)
模糊聚类的本质就是针对对象的某些属性来构建模糊矩阵,然后通过一定的方法进行分类操作,模糊聚类算法分类比较简单且分类效果较好。
模糊C-均值聚类(FCM)是J.C.Dunn按照E.Ruspini[4]定义的模糊划分集合的概念,从硬C-均值聚类算法推广得到的,最大的不同是在隶属度uij上乘一个权重值m[5]。FCM的数学模型如下:
1.2 FCM在用户-项目评分矩阵中的应用
1.2.1 用户-项目评分问题的数学模型
将模糊聚类引入评分矩阵X中,该矩阵表示n个用户对m个项目进行评价,(xik)n表示用户i对项目k的评分,需要根据用户对各个项目的评分对用户进行聚类,将用户分为c个簇,使得同一个簇中的用户相似性最高,并且把聚类的结果通过矩阵U表示出来,其中uki表示用户i对用户簇k的隶属度。
针对用户模糊聚类的函数为:
式(10)中:uki表示用户i在用户簇k中的隶属程度,dki表示用户i与用户簇k的聚类中心距离(通常为欧几里德距离),ck表示用户簇k的中心点,即该簇的聚类点,m表示决定聚类结果模糊度的权重指数,一般1.25≤m≤2.5。参考国内外文献和实验,将m设为2。
本模糊聚类的基本原理为:计算用户与各个聚类中心间的距离,通过得到的距离值计算用户和各个聚类中心的隶属度,通过比较隶属度高低,将用户分到最高的隶属度用户簇中,使同一个用户簇中的用户之间相似度最高,减少不同簇用户之间的相似度。
所以,要求得用户-评分模糊聚类的最优值,只需找到最佳的聚类中心点ck,k∈1,c和各个用户对聚类中心的隶属度uki,i∈1,n即可。
1.2.2 FCM聚类算法
为了解得模糊聚类目标函数的最优值,利用模糊聚类法则,在极值的约束条件[7] ∑ck=1uki=1下,求min{Jm(U,c)},构建拉格朗日函数,如式(11)所示:
1.3 基于用户的协同过滤算法
基于用户的协同过滤算法是分析其他用户观点,为目标用户产生推荐[9],其基本思想是:如果某几个用户对项目的评分类似,则称他们为“邻居用户”,他们之间就可能会有相同的兴趣爱好,就可以把其他用户喜欢的推荐给目标用户。
1.3.1 用户相似度
协同过滤算法中最主要的是用户最近邻查询,本文只需在目标用户所在簇中计算出与目标用户最相近的邻居,然后进行预测评分。度量两个用户之间的相似度需要首先获得两个用户对项目的所有评分,然后通过相似度度量公式计算两个用户之间的相似度,记为sim(i,j),其中i,j分别代表两个用户。用户相似度计算方法有很多,本文采用相关相似性来度量,计算公式如下:
1.3.2 预测评分
在利用协同过滤算法完成用户相似性度量之后,下一步就是预测评分,利用公式(16)对目标用户未评分的项目进行预测,将评分按降序排列,把排名前n个项目推荐给用户。
2 相关算法改进
2.1 模糊聚类距离计算方法改进
模糊C均值算法最重要的步骤是距离计算,计算各个用户与聚类簇中心点的距离。距离的计算方法有很多,如欧氏距离、马氏距离、相关系数法、最小算术平均法等,其中最常用的就是欧氏距离,计算公式如下[11]:
欧氏距离使用方便,计算简单,但是也有非常严重的缺陷。它将用户对不同项目的兴趣爱好视为“一般重要”,这样不能体现出不同项目对不同用户的重要程度,所以在一些情况下使用欧氏距离公式计算距离,聚类结果效果不理想。
本文用加权的欧氏距离来替换传统的欧氏距离,通过对不同的分量进行不同的权重分配,改进了聚类效果,计算公式如下:
式(17)中,si是对应的方差,可将方差的倒数看作一个权重,弥补欧氏距离的缺陷,提高聚类效果。
2.2 推荐过程
首先通过模糊C均值聚类算法将用户进行分类,然后在各个用户簇中使用协同过滤算法进行用户推荐,算法流程如图1所示。
3 实验结果及分析
3.1 数据集
本文实验采用的数据集为MovieLens网站提供的电影评分数据集,该数据集包括各种用户对各个类别电影的评分,分值为1-5,本文使用932个用户对1538部电影超过9000次的评分数据进行实验。将所有的数据平均分为5组,每次选择其中4组作为训练集,另外一组作为测试集,进行5次实验。
本实验采用的衡量标准为平均绝对偏差(MAE),其基本原理是通过计算整个算法对目标项目的预测值,和用户实际评分值之间的误差来衡量整个算法的优劣。MAE值越低,说明推荐的准确度越高。计算公式如下:
3.2 实验结果
对用户进行模糊C均值聚类,采用相关相似性计算方式进行相似度计算。由于分成不同数量的簇可能会对推荐结果产生较大的影响,所以本实验将分别对不同数量的聚类中心进行测试,通过与传统的协同过滤以及以普通欧氏距离为聚类距离计算的算法对比,验证本方法的优劣。本实验测试的聚类中心个数为5-50,间隔为5,实验结果如图2所示。
从图2可以看出,随着聚类中心的增加,MAE值呈变大的趋势,说明推荐的精度越来越低,推荐质量越来越差。由折线图可以看出,本文使用加权欧氏距离推荐算法,在推荐精度上要高于传统的模糊聚类推荐算法,所以本算法可以提高推荐系统的推荐质量。
3.3 实验结果分析
本实验通过不断的对比测试验证本算法的优势,通过实验结果可以得出,本文的推荐算法跟传统的协同过滤算法以及传统欧氏距离的模糊聚类推荐算法相比,在推荐精度上具有一定的提高。
因为传统欧氏距离计算的是各个点之间的绝对距离,未考虑到样本之间不同屬性的差别,所以未满足实际需求。本文将加权的欧氏距离代替传统的欧氏距离计算,弥补了传统欧氏距离的缺陷,提高了推荐质量。
参考文献:
[1] 冯刚.基于J2EE的多语种元搜索引擎的研究与实现[D].成都:电子科技大学,2006.
[2] 刘明.基于聚类和会话情景的混合推荐算法研究[D].武汉:华中科技大学,2013.
[3] 李华,张宇,孙俊华.基于用户模糊聚类的协同过滤推荐研究[J].计算机科学,2012,39(12):83-86.
[4] ABBATTISTA F,DEGEMMIS M,LICCHELLI O.Improving the usability of an E-commerce web site through personalization[C].Proceedings of Workshop on Recommendation and Personalization in E-commerce,2002:231-278.
[5] 范九伦,吴成茂.FCM算法中隶属度的新解释及其应用[J].电子学报,2004,32(2):350-352.
[6] 熊拥军,刘卫国,欧鹏杰.模糊C-均值聚类算法的优化[J].计算机工程与应用,2015,51(11):124-128.
[7] 张乾君.模糊聚类分析在企业竞争情报系统中的应用研究[D].西安:西安电子科技大学,2011.
[8] 孙静.基于模糊聚类的电子商务协同过滤推荐研究[D].天津:河北工业大学,2011.
[9] 薛扣平.具有可信机制的推荐系统及其应用研究[D].南京:东南大学,2008.
[10] 胡斌.基于用户和资源权重的协同过滤推荐系统的研究与设计[D].武汉:武汉理工大学,2009.
[11] 光俊叶,刘明霞,张道强.基于有效距离的谱聚类算法[J].计算机科学与探索,2014,8(11):1365-1372.