一种利用Vague集理论改进的协同过滤推荐算法

引用本文

张慧颖, 薛福亮. 一种利用Vague集理论改进的协同过滤推荐算法. 现代图书情报技术, 2012, 28(3): 35-39
Zhang Huiying, Xue Fuliang. An Improved Collaborative Filtering Recommendation Algorithm Based on Vague Sets Theory. New Technology of Library and Information Service, 2012, 28(3): 35-39 复制到剪切板

Permissions

This article is the open access journal literature, in the following situations are free to use: academic research and academic exchanges, scientific research and teaching, etc., but don't allow for commercial purposes.

一种利用Vague集理论改进的协同过滤推荐算法

张慧颖¹, 薛福亮^1,²

1.天津大学管理与经济学部天津 300072

2.天津财经大学商学院天津 300222

基金:本文系天津市高等学校人文社会科学基金项目“电子商务个性化推荐系统瓶颈问题研究”（项目编号：20112125）的研究成果之一;

摘要

针对项目特征难以表达问题,提出采用Vague集理论对其进行提取与表示,在此基础上进行项目相似性聚类,利用聚类内项目相似性对未评分项目进行评分值预测,从而消除协同过滤推荐的稀疏性问题,进而基于预测后的评分矩阵进行相似用户聚类,并在项目聚类簇内实施协同过滤推荐,使推荐更有针对性。实验结果表明,该方法无论在推荐精度还是推荐相关性上都更为有效。

关键词: 推荐系统; 协同过滤; 项目相似性; 基于内容推荐; Vague sets

An Improved Collaborative Filtering Recommendation Algorithm Based on Vague Sets Theory

Zhang Huiying¹, Xue Fuliang^1,²

1.College of Management & Economics, Tianjin University, Tianjin 300072, China

2.Business School, Tianjin University of Finance & Economics, Tianjin 300222, China

Abstract

Aiming at the difficulty of project features expression,this paper brings forward to extract and represent it with vague sets theory.Then similar item is clustered to predict missing evaluation values of item, thus eliminating the sparsity problem of collaborative filtering recommendation. Based on the predicted rating matrix,similar users are clustered,and collaborative filtering recommendation is implemented in the space of item cluster to give more targeted recommendation. Evaluation results show that the proposed method is more effective both in the accuracy and in relevance of recommendations.

Keyword: Recommender system; Collaborative filtering; Item similarity; Content-based recommendation; Vague sets

Show Figures

1 引言

目前,推荐系统依据其采用的核心技术可以分为基于内容的推荐、协同过滤推荐和混合推荐。其中协同过滤方法对具有相似购物偏好的用户进行聚类,依据他们之间购物偏好的相似性进行交叉推荐。而基于内容的推荐则利用项目特征与用户购买行为特征的相似性实施推荐。如果用户对产品的评价信息非常完整,协同过滤推荐精度是非常准确的,而实际应用中因为数据的稀疏或者因为新产品没有足够的评价数据,会导致相似用户的聚类效果不佳,从而产生稀疏性以及冷启动等问题^{[ 1]}。

国内外学者针对协同过滤的数据稀疏性问题提出了很多解决方法。最经典的是使用用户个人社会信息对基础数据进行补值^{[ 2]},但这种方法可能会涉及到个人隐私;也有提出采用奇异值分解技术来缩减稀疏评价矩阵的维度,以消除评价矩阵的稀疏性^{[ 3]},但可能会丢失有价值的数据。Web数据挖掘理论可以对服务器日志进行数据挖掘,从而发现用户的行为模式以获取隐性的用户评价数据^{[ 4]},从而对稀疏的评价值进行补值;同时有学者提出利用神经网络去除稀疏性,进而进行聚类推荐的框架,该方法具有较好的稀疏性去除效果^{[ 5]}。基于内容的推荐也不断加入了新的思想,如在基于内容的产品推荐中应用了模糊数学的思想^{[ 6]},崔春生等^{[ 7]}首次将Vague集思想应用到了基于内容的产品推荐中,提出了一种产品相似性度量的新方法。

协同过滤是最为成熟的推荐方法,其关键是消除评价数据的稀疏性。本文提出利用Vague集思想进行商品特征的提取与表示,并基于商品特征的Vague值数据进行商品相似度计算,进而得到相似产品的聚类簇,利用同一聚类簇内产品的相似性进行用户未评分商品的评分值预测并补值,从而消除用户评分矩阵的稀疏问题。消除稀疏性后的评分矩阵使得相似用户聚类簇更为准确,同一聚类簇的用户具有相似的购物偏好,从而进行交叉推荐。本文进一步提出将相似用户聚类簇与相似产品聚类簇相结合,即在相似产品聚类簇内基于用户相似性实施推荐,使得待推荐产品更符合本次购物偏好,从而使推荐更有针对性。

2 本文推荐方法核心框架

本文方法的核心思想共分为三个阶段,如图1所示:

	Figure Option View Download New Window
	图1 推荐算法框架

(1)利用Vague集理论对项目数据库中的项目特征进行提取并对项目特征用Vague值表示,为项目相似性聚类提供保证。由于用户对项目的评分数据记录有限,因此得到的用户-项目评价数据是稀疏的。

(2)依据项目特征的Vague值来计算项目之间的相似性,并进行相似项目聚类,基于项目之间的相似性对稀疏的用户-项目评价矩阵进行补值处理,得到消除稀疏性后的完全评价矩阵。并依据完全评价矩阵进行用户之间的相似性计算与聚类,得到多个相似用户聚类簇。此处利用Pearson相关系数进行项目-项目及用户-用户之间的相似性计算,并利用K-均值聚类算法进行聚类簇的生成。

(3)利用同一相似用户聚类簇内用户购买偏好的相似性对同一项目聚类簇内的特征相似项目实施混合推荐,并向活动用户输出推荐结果。利用补值后的用户评价矩阵将会产生更精确的相似用户聚类。

3 基于Vague集评分预测的协同过滤推荐系统

Vague集是对模糊集的扩展,Vague集思想认为每个元素的隶属都可以分成支持和对立两个方面,也就是真隶属度和假隶属度,并且能够表示中立的程度,从而提出Vague集的概念。其成果对电子商务推荐系统有很好的借鉴意义。借鉴Vague的研究成果,利用Vague值进行商品特征的表示,可表达商品相对精确的接近程度,从而对相似商品进行聚类,并依据聚类内商品的相似性对未评价商品进行评分值预测。

本文所采用的符号作以下约定:

用I_j(j=1,2,…,n)来代表商品空间,n为商品数量。用X{x₁,x₂,…,x_l}来表示商品的特征空间向量,l为商品特征属性数量。

用 (I_j)=< (I_j), (I_j), (I_j)>来表示商品特征x_k(k=1,2,…,L)的Vague值函数。 (I_j), (I_j), (I_j)分别用来表示肯定隶属度、否定隶属度以及未知度。Vague 集理论认为,肯定隶属度、否定隶属度、未知度之间存在以下关系: (I_j)=1- (I_j)- (I_j)。r(I_j)表示顾客对项目I_j的原始评分值,r'(I_j)表示顾客对项目I_j归一化处理后的评分值,simI(I_k,I_j)表示项目I_k与I_j的相似度。

3.1 项目特征的Vague值提取与表示

对项目特征进行提取与表示,以寻找与用户购物偏好相似的项目。依据Vague集理论,商品特征的提取与表示步骤如下所示:

(1)定义项目特征属性

项目有多个特征属性,如电影特征属性集合可表示为X={枪战,爱情,情感,伦理,恐怖,侦探,古装,…},可用x_k表示为X{x₁,x₂,x₃,…}。

(2)确定项目特征的肯定隶属度

依据x_k与项目相关性程度降序排列。表示为X{x₈,x₅,x₃,…},第8个属性相关性最高,其他依次降低。定义 (I_j)为肯定隶属度,即:特征x_k与项目I_j的相关程度。X{x₈,x₅,x₃,…}中各特征x_k肯定隶属度依次降低。如商品有3个特征表示为X{x₁,x₂,x₃},可令 (I_j)=0.7, (I_j)=0.5, (I_j)=0.2, (I_j)=0,k=4,…,L。肯定隶属度的取值基本符合Gaussian函数特性,依据Gaussian函数定义,x_k的肯定隶属度为^{[ 7]}:

(I_j)= (1)

其中,|L_j|表示商品的特征数量,r_k(1≤r_k≤|L_j|)表示特征x_k所在的排序位置。α>1是需要确定的常数,其会影响到取值的连续性。如电影I₁有5个特征{枪战,爱情,情感,伦理,恐怖},分别表示为:x₁,x₂,x₃,x₄,x₅。取α=1.25,运用Gaussian函数得到: (I₁)=1, (I₁)=0.3536, (I₁)=0.2598, (I₁)=0.1986, (I₁)=0.1573。

(3)确定项目特征x_k的未知度

商品特征的未知度应以中间值为中心成对称分布,项目最重要特征未知度取值为0,项目所有特征未知度应满足: =1,故采用三角函数或梯形函数可得到上例中项目I₁各特征的未知度分别为0,0.25,0.5,0.25,0。

(4)Vauge值表示项目特征

由1- (I_j)= (I_j)+ (I_j)可得到项目各特征的Vague值。上例中项目I₁的Vauge值为: (I₁)=<1,0,0>, (I₁)=<0.3536,0.3964,0.25>, (I₁)=<0.2598,0.2402,0.5>, (I₁)=<0.1986,0.5514,0.25>, (I₁)=<0.1573,0.8427,0>。

3.2 依据项目Vague值进行相似产品聚类

项目I_j特征采用Vague集理论提取与表示后,基于项目Vague值可进行项目相似性计算。依据文献[8]的研究,项目Vague值相似性的计算公式如下所示,其中l为产品特征数量:

simI(I₁,I₂)=1- [ (| (I₁)- (I₂)|+1- | (I₁)- (I₂)|)+ (| (I₁)- (I₂)|)](2)

依据Vauge值表示,对项目之间相似性计算可得到项目相似性矩阵。基于项目相似性矩阵可利用K-均值聚类算法^{[ 9]}进行聚类,方法如下:

输入:项目相似矩阵,ij|1≤i≤M & 1≤j≤M>,M为项目数量。

输出:k个聚类簇[clusI_k={相似项目集合}]

方法:

①从 n个项目中依据simI_i,j值,鉴定Top k个相似项目作为k个聚类簇的初始聚类中心。

②根据每个聚类的均值,依据每个项目simI_i,j值计算其与聚类中心的距离;并根据最小距离将项目归入相应聚类簇中。

③重新调整聚类簇中心值(中心项目)。

④对M个用户循环计算步骤②和③,直到每个聚类不再发生变化为止。

3.3 基于产品聚类内产品相似性对用户-项目评价矩阵补值处理

用户-项目评价矩阵是一个稀疏的评分矩阵,基于上述产品聚类簇内产品之间的相似性对其进行补值处理。发现项目评分值的准确性依赖于对其进行评分的用户的数量,数量值越大评分相对越准确,为了提高预测准确度,使用调和权值因子来调和被不同用户数量评分的项目对预测值的贡献。调和权值因子如下:

ωm_i,j= (3)

m_i= (4)

此处n_i为评价项目m_i的用户数量。则某用户u对项目i的预测值P_u,i可用以下公式计算得到:

P_u,i= (5)

其中,k为聚类内与i最相近的k个项目。r_u,j为用户u对相近项目j的评分。利用P_u,i对稀疏用户矩阵进行补值处理可得到完全用户-项目评分矩阵r'_ij(消除稀疏性后的评分矩阵)。

3.4 基于完全用户-项目评价矩阵的相似用户聚类

输入:补值后的完全用户项目评分距阵ij|1≤i≤M & 1≤j≤N>,t是被用户i和用户j都评过分的项目集。和分别是用户i和用户j的平均评分。

输出:k个聚类簇[clus_k={相似用户集合}]

方法:

①for i=1 to M /*计算M个用户之间的相似性*/

②sim_count(i)=0

③for j=1 to M

计算用户i和j的Pearson相关系数simU_i,j

if simU_i,j=1 then

sim_count(i)=sim_count(i)+1

④鉴定top k个相似用户作为k个聚类簇的初始用户

⑤将用户归入相应聚类簇中

⑥对M个用户循环计算步骤③-⑤

3.5 推荐实施

整个用户集合空间划分为若干个具有相似购物偏好的聚类簇C={c1,c2,…,ck},对于聚类簇内某用户u可以调节聚类内用户顺序,使得c1 与u 的相似性sim(u,c1)最高,c2 与u 的相似性sim(u,c2)次之,依此类推,依据相似性程度得到目标用户的最近邻居。设用户u 的最近邻居集合用NBS_u 表示。当用户对某个项目表现出兴趣,则依据相似项目聚类簇,在其最相似项目空间内进行评分预测。用户u对项目i的预测评分可以通过用户u的最近邻居集合NBS_u对项目i的最相近项目的评分得到,计算方法如下^{[ 8]}:

P'_u,i=+ (6)

其中,sim(u,n)表示用户u 与用户n 之间的相似性,r'_n,i 表示用户n 对项目i 的评分, , 分别表示用户u和用户n对项目的平均评分。将预测值最高的Top-N个项目推荐给给定用户。

4 实验评价

MovieLens提供的推荐系统测试数据集为公开数据集,是一个基于Web的研究型推荐系统。借鉴其公开的评分数据集,将测试记录分为训练集和测试集,训练集和测试集比重为[80%,20%]。目标用户选择在训练阶段和测试阶段都至少有一次交易记录的用户。在训练集数据空间内进行数据预处理与推荐修正,在测试集空间内实施推荐,并将推荐结果与实际用户购买行为进行比较度量。

4.1 度量指标

准确率(Precision)和召回率(Recall)两个指标通常被用来度量推荐质量,准确率的定义是推荐的项目除以总推荐项目;召回率是推荐的相关项目除以总相关项目(应当检索到的)^{[ 8]}。由于准确率和召回率一定程度上是一对相互矛盾的指标,为了平衡两者,可用平均绝对误差(MAE)来评价预测结果与最终结果的接近度,如下所示^{[ 10]}:

MAE= (7)

其中,M、N、p_ij、r_ij分别代表用户数量、项目数量、用户i对项目j的预测评分和用户i对项目j的实际评分。

4.2 实验结果

图2所示为不同稀疏性水平评价数据分别进行评分预测后的稀疏度水平,稀疏度定义为:1-有效评分/(用户数×产品数)^{[ 8]}。经过Vague集补值后数据集稀疏度降低了超过50%,保证了协同过滤用户相似性聚类的准确性,进而保证了推荐质量。

	Figure Option View Download New Window
	图2 评分预测降低稀疏度效果

预测数据与真实数据的偏差通过平均绝对差来检测,将本文推荐算法与简单协同过滤算法以及经典的奇异值分解协同过滤算法的MAE进行比较,结果如图3所示:

	Figure Option View Download New Window
	图3 不同推荐模型平均绝度误差比较

可以发现,基于Vague集评分预测的协同过滤推荐相比简单协同过滤与经典的奇异值分解协同过滤,在平均绝对误差上随着不同的稀疏性水平有明显的降低。

5 结语

本文提出利用Vague值进行项目特征提取与表示,利用项目之间的相似性对未评分项目进行预测补值,从而消除评分矩阵的稀疏性,使相似用户聚类效果更好,在相似项目空间内实施推荐,使推荐更有针对性,同时降低了计算复杂度。实验研究表明系统推荐结果比简单协同过滤和奇异值分解协同过滤算法效果要好很多。Vauge集理论提供了一种新的产品特征度量方法,降低了协同过滤推荐中的稀疏性问题,但对协同过滤存在的冷启动、可扩展性等问题却无法解决,这将是下一步研究的重点。

参考文献

View Option

[1]	许海玲, 吴潇, 李晓东, 等. 互联网推荐系统比较研究[J]. 软件学报, 2009, 20(2): 350-362. (Xu Hailing, Wu Xiao, Li Xiaodong, et al. Comparison Study of Internet Recommendation System[J]. Journal of Software, 2009, 20(2): 350-362. ) [本文引用:1] [CJCR: 2.181]
[2]	Pazzani M J. A Framework for Collaborative, Content-based and Demographic Filtering[J]. Artificial Intelligence Review, 1999, 13(5): 393-408. [本文引用:1] [JCR: 1.565]
[3]	Sarwar B M, Karypis G, Konstan J A, et al. Application of Dimensionality Reduction in Recommender Systems——A Case Study[C]. In: Proceedings of ACM WebKDD Workshop, New York. 2000. [本文引用:1]
[4]	Cheung K W, Kwok J T, Law M H, et al. Mining Customer Product Ratings for Personalized Marketing[J]. Decision Support Systems, 2003, 35(2): 231-243. [本文引用:1] [JCR: 2.201]
[5]	Devi M K, Venkatesh P. Kernel Based Collaborative Recommender System for E-purchasing[J]. Academy of Sciences, 2010, 35(5): 513-524. [本文引用:1]
[6]	Zenebe A, Norcio A F. Representation, Similarity Measures and Aggregation Methods Using Fuzzy Sets for Content-based Recommender Systems[J]. Fuzzy Sets and Systems, 2009, 160(1): 76-94. [本文引用:1] [JCR: 1.749]
[7]	崔春生, 李光, 吴祈宗. 基于Vague 集的电子商务推荐系统研究[J]. 计算机工程与应用, 2011, 47(10): 237-239. (Cui Chunsheng, Li Guang, Wu Qizong. Research on Recommender Systems of Electric Commerce Based on Vague Sets[J]. Computer Engineering and Applications, 2011, 47(10): 237-239. ) [本文引用:2] [CJCR: 0.457]
[8]	邓爱林. 电子商务推荐系统关键技术研究[D]. 上海: 复旦大学, 2003. (Deng Ailin. The Research on Key Technologies of Recommendation System in E-Commerce[D]. Shanghai: Fudan University, 2003. ) [本文引用:3]
[9]	Kim K J, Ahn H. A Recommender System Using GA K-means Clustering in an Online Shopping Market[J]. Expert Systems with Applications, 2008, 34(2): 1200-1209. [本文引用:1] [JCR: 1.854]
[10]	牟向伟, 陈燕. 基于模糊描述逻辑的个性化推荐系统建模[J]. 计算机应用研究, 2011, 28(4): 1430-1433. (Mu Xiangwei, Chen Yan. Fuzzy Semantic Personalized Recommendation System Modeling[J]. Application Research of Computers, 2011, 28(4): 1430-1433. ) [本文引用:1] [CJCR: 0.601]

2009

0.0

2.181

. 2009, 20(2):350-362

Comparison Study of Internet Recommendation System

全面地总结推荐系统的研究现状,旨在介绍网络推荐的算法思想、帮助读者了解这个研究领域.首先阐述了推荐系统研究的工业需求、主要研究机构和成果发表的期刊会议;在讨论了推荐问题的形式化和非形式化定义之后,对主流算法进行了分类和对比;最后总结了常用数据集和评测指标,领域的重难点问题和未来可能的研究热点.

... 如果用户对产品的评价信息非常完整,协同过滤推荐精度是非常准确的,而实际应用中因为数据的稀疏或者因为新产品没有足够的评价数据,会导致相似用户的聚类效果不佳,从而产生稀疏性以及冷启动等问题^[1] ...

1999

1.565

0.0

... 最经典的是使用用户个人社会信息对基础数据进行补值^[2],但这种方法可能会涉及到个人隐私 ...

2000

0.0

... 也有提出采用奇异值分解技术来缩减稀疏评价矩阵的维度,以消除评价矩阵的稀疏性^[3],但可能会丢失有价值的数据 ...

2003

2.201

0.0

. 2003, 35(2):231-243 DOI:10.1016/S0167-9236(02)00108-2

Mining Customer Product Ratings for Personalized Marketing

Abstract With the increasing popularity of Internet commerce, a wealth of information about the customers can now be readily acquired on-line. An important example is the customers' preference ratings for the various products offered by the company. Successful mining of these ratings can thus allow the company's direct marketing campaigns to provide automatic product recommendations. In general, these recommender systems are based on two complementary techniques. Content-based systems match customer interests with information about the products, while collaborative systems utilize preference ratings from the other customers. In this paper, we address some issues faced by these systems, and study how recent machine learning algorithms, namely the support vector machine and the latent class model, can be used to alleviate these problems.

... Web数据挖掘理论可以对服务器日志进行数据挖掘,从而发现用户的行为模式以获取隐性的用户评价数据^[4],从而对稀疏的评价值进行补值 ...

2010

0.0

. 2010, 35(5):513-524 DOI:10.1007/s12046-010-0035-8

Kernel Based Collaborative Recommender System for E-purchasing

1.Department of Information Technology, Thiagarajar College of Engineering, Madurai, 625 015 India 2.Department of Electrical and Electronics Engineering, Thiagarajar College of Engineering, Madurai, 625 015 India

Recommender system a new marketing strategy plays an important role particularly in an electronic commerce environment. Among the various recommender systems, collaborative recommender system (CRS) is widely used in a number of different applications such as recommending web pages, movies, tapes and items. CRS suffers from scalability, sparsity, and cold start problems. An intelligent integrated recommendation approach using radial basis function network (RBFN) and collaborative filtering (CF), based on Cover’s theorem, is proposed in order to overcome the traditional problems of CRS. The proposed system predicts the trend by considering both likes and dislikes of the active user. The empirical evaluation results reveal that the proposed approach is more effective than other existing approaches in terms of accuracy and relevance measure of recommendations.

... 同时有学者提出利用神经网络去除稀疏性,进而进行聚类推荐的框架,该方法具有较好的稀疏性去除效果^[5] ...

2009

1.749

0.0

... 基于内容的推荐也不断加入了新的思想,如在基于内容的产品推荐中应用了模糊数学的思想^[6],崔春生等^[7]首次将Vague集思想应用到了基于内容的产品推荐中,提出了一种产品相似性度量的新方法 ...

2011

0.0

0.457

. 2011, 47(10):237-239

Research on Recommender Systems of Electric Commerce Based on Vague Sets

1.School of Management and Economics，Beijing Institute of Technology，Beijing 100081，China 2.School of Computer，Henan University of Economics and Law，Zhengzhou 450002，China

It is stable for the development of content-based recommendation system to represent the features of merchandise.The theory of Vague sets，Gaussian function and characteristics of uncertainty are used to represent features with Vague value.On this basis，the general steps of content-based recommendation with Vague sets are given，in order to get a new idea and method to recommender systems designers.Finally，some recommender formulas with different features are given，which will be conducive to the work of the actual recommendation.Select different formulas according different conditions will improve the quality and accuracy of the recommendation.

基于内容推荐系统发展的瓶颈在于商品特征的表示。借助Vague集方法，并利用高斯函数和Vague集中未知度的一些性质，将商品的特征用Vague值形象表示。在此基础上，给出了运用Vague集方法进行基于内容推荐的步骤，为推荐系统的设计提供了一种新的指导思想和方法。最后给出了多个推荐公式，并进行简单的比较，有利于在实际推荐工作中酌情选择不同的推荐公式，提高商品推荐质量和推荐精度。

... 肯定隶属度的取值基本符合Gaussian函数特性,依据Gaussian函数定义,x_k的肯定隶属度为^[7]: ...

2003

0.0

... 用户u对项目i的预测评分可以通过用户u的最近邻居集合NBS_u对项目i的最相近项目的评分得到,计算方法如下^[8]: ...

... 召回率是推荐的相关项目除以总相关项目(应当检索到的)^[8] ...

... 产品数)^[8] ...

2008

1.854

0.0

. 2008, 34(2):1200-1209 DOI:10.1016/j.eswa.2006.12.025

A Recommender System Using GA K-means Clustering in an Online Shopping Market

Abstract The Internet is emerging as a new marketing channel, so understanding the characteristics of online customers’ needs and expectations is considered a prerequisite for activating the consumer-oriented electronic commerce market. In this study, we propose a novel clustering algorithm based on genetic algorithms (GAs) to effectively segment the online shopping market. In general, GAs are believed to be effective on NP-complete global optimization problems, and they can provide good near-optimal solutions in reasonable time. Thus, we believe that a clustering technique with GA can provide a way of finding the relevant clusters more effectively. The research in this paper applied K -means clustering whose initial seeds are optimized by GA, which is called GA K -means, to a real-world online shopping market segmentation case. In this study, we compared the results of GA K -means to those of a simple K -means algorithm and self-organizing maps (SOM). The results showed that GA K -means clustering may improve segmentation performance in comparison to other typical clustering algorithms. In addition, our study validated the usefulness of the proposed model as a preprocessing tool for recommendation systems.

... 基于项目相似性矩阵可利用K-均值聚类算法^[9]进行聚类,方法如下: ...

2011

0.0

0.601

... 由于准确率和召回率一定程度上是一对相互矛盾的指标,为了平衡两者,可用平均绝对误差(MAE)来评价预测结果与最终结果的接近度,如下所示^[10]: ...