基于极速学习机和最近邻的回归推荐算法
2018-01-05陈爱霞李宁
陈爱霞,李宁
(1.河北大学 数学与信息科学学院,河北 保定 071002;2.中国科学院 信息工程研究所,北京 100093)
基于极速学习机和最近邻的回归推荐算法
陈爱霞1,李宁2
(1.河北大学 数学与信息科学学院,河北 保定 071002;2.中国科学院 信息工程研究所,北京 100093)
提出了一种基于极速学习机和最近邻的协同过滤回归推荐算法.该算法首先采用k最近邻法对评分矩阵的缺失值进行填充,然后将极速学习机作为回归器为用户产生推荐.在推荐领域中的标杆数据集上,将该算法与常用推荐算法- LRCF算法进行了比较,验证了该算法的有效性.
k最近邻;极速学习机;推荐系统
随着信息技术和互联网的飞快发展,信息量海量增长,使得用户在面对大量信息时无法从中获得对自己真正有用的那些信息.此时,推荐系统[1]应运而生.对用户而言,推荐系统不需要用户提供明确的目标,只需要提供一些建议性的条件,推荐系统会根据这些条件,结合相关信息,计算用户的需求,最终给出合适的有用信息.推荐系统现在已经广泛应用于很多领域,尤其在电子商务领域,推荐系统的价值更为突出.目前,几乎所有的大型电子商务网站都有自己的推荐系统,如亚马逊、淘宝、京东等.与此同时,推荐系统在理论方面也取得了丰硕的成果,推荐系统主要包含基于协同过滤的推荐系统[2]和基于内容的推荐系统[3]2大类.协同过滤推荐是目前应用最广泛和最成功的推荐系统[4].协同过滤推荐算法中的关键问题有相似性比较,数据稀疏性问题,冷启动问题,可扩展性问题,推荐的实时性,推荐策略,评估方法等[4].孙光福等[5]提出一种对用户(产品)间的时序行为建模的方法,有效地提高了推荐精度.荣辉贵等[6]引入用户相似度概念,定义了社交网络中属性相似度,以及相似度构成与计算方法,提出了一种改进的协同过滤推荐算法,有效地改善了社交网络中的推荐准确性.
极速学习机(extreme learning machine,ELM)是Huang等[7-8]于2004年针对单隐层前馈神经网络(single layer feed-forward neural networks,SLFNs)提出的一种快速学习算法.极速学习机算法克服了传统神经网络算法易陷入局部极小、迭代次数多、学习时间长等问题,并具有学习速度快、泛化能力好、能逼近任何复杂函数等优点,已经广泛应用在数据挖掘、机器学习、图像处理等领域.
本文首先采用k最近邻法对数据的缺失值进行填充,然后将极速学习机作为回归器为用户产生推荐,并在推荐领域中的3个标杆数据集上,验证了该算法的有效性.
1 极速学习机概述
极速学习机是针对单隐层前馈神经网络提出的一种快速学习算法,该算法只需要设置网络的隐层节点个数,其网络输入权值ai以及隐元偏置bi都是随机生成的,然后由最小二乘法得到唯一的最优解,即输出权重βi,如图1所示.其中,输入向量xj=(xj1,xj2,…,xjn)T∈Rn,隐层元个数为L,向量ai是输入层到第i个隐层元的权重,数bi是第i个隐层元的偏置,向量βi是第i个隐层元和输出向量之间的权重,输出向量oj=(oj1,oj2,…,ojm)T∈Rm.
图1 SLFNs极速学习机[7-8]Fig.1 SLFNs extreme learning machine[7-8]
假设有N个任意样本(xj,tj),j=1,2,…,N,其中xj=(xj1,xj2,…,xjn)T∈Rn,tj=(tj1,tj2,…,tjm)T∈Rm.对于一个有L个隐层节点的SLFNs极速学习机可以表示为
其中g(x)为激活函数,ai·xj表示ai和xj的内积.
SLFNs极速学习机的学习目标是使得输出误差最小,可表示为
oj-tj=0,
即存在βi、ai和bi使得
可以表示为
Hβ=T,
其中,H是隐层节点的输出,β为输出权重矩阵,T为期望输出.
在SLFNs极速学习机中,输入权重ai和隐层偏置bi一旦被随机确定,就会唯一确定隐层的输出权重矩阵β.因此,训练SLFNs极速学习机便转化为求解线性矩阵方程Hβ=T,并且输出权重矩阵β可由下式确定
2 协同过滤回归推荐模型[10]
假设X∈RU×I为一个稀疏的用户评分矩阵,回归推荐模型首先采用机器学习算法对用户评分矩阵X进行缺失值填充,然后通过最小化目标函数f(X)构造回归器fj(·),如下公式所示:
其中,输入样本X通常是一个包含U个用户和I个对象的稀疏的用户评分矩阵,⊗表示Hadamard乘积,即矩阵中对应元素之间分别相乘,·F表示Frobenius范数,简称F范数,fj(·)表示关于对象j的回归器,fj(i)表示对象j的回归模型关于用户i的输出值,矩阵F是由U×I个回归值fj(i)构成的矩阵,稀疏指示矩阵W其元素为1表示有值,元素为0表示缺值.
3 基于极速学习机和k最近邻的协同过滤回归推荐算法
当回归推荐模型中的回归器是极速学习机时,称为基于极速学习机的协同过滤回归推荐算法(ELMCF).详细过程如下:假设Ds是一个稀疏的用户评分矩阵(由于包含U个用户和I个对象,所以Ds是一个U行I列的矩阵),首先ELMCF算法采用机器学习算法将矩阵Ds的缺失值填充,得到一个满值矩阵Df.本文中,缺失值填充采用k最近邻算法,即找出这个样本的k个最近邻居,将这些邻居的平均值赋给该样本.
然后,对于满值矩阵Df的每一列构造一个基于极速学习机的回归器.具体地,将矩阵Df的第i(i=1,2,…,I)列作为输出矩阵,记作Ti,将剩余的I-1列作为输入矩阵,记作Pi,如式(1)所示.
(1)
与标准的ELM算法类似,ELMCF算法首先将输入矩阵Pi映射到隐含层,得到矩阵Hi,然后对于未知的权重β和输出矩阵Ti有下面矩阵方程成立:
Hiβ=Ti.
下面介绍基于极速学习机和最近邻的回归推荐算法的一般步骤.算法输入为训练集{xi|xi∈RU,i=1,…,N},并设隐含层节点数为L,隐含层函数为g(aj,bj,xi),j=1,…,L.对于每个对象训练得到一个ELM回归器,算法共输出I个ELM回归器.
1)用k最近邻法填充评分矩阵Ds上的缺失值.
2)对于对象i(i=1,2,…,I)构造输入矩阵Pi和相应的输出向量Ti.
3)对于对象i(i=1,2,…,I)构造ELM回归器fi(·).
与传统的“一对一”线性回归推荐算法相比,本文提出的算法具有如下几点优势:
①该方法中回归器的个数大大减少.在传统的算法中,对于每个对象需要构造I-1个回归器,因为共有I个对象,所以共需要构造I(I-1)个回归器.而本文的方法中,对于每个对象只需构造1个回归器,因此只需要构造I个回归器.
②该方法不需要对回归器进行集成,简单易行.在传统的算法中,对某一对象i的评分预测值需由I-1个关于该对象的“一对一”回归器的评分集成而得.本文的方法中,对某一对象的评分预测值直接由该对象的ELM回归器fi(·)产生,而不需进行集成.
③该方法中输入自变量通常是多个对象,从而有效地避免了输入相同而输出不同的情况发生,使得回归方式更加合理.
4 实验结果
为了验证本文提出的基于极速学习机和最近邻的回归推荐算法的有效性,分别在推荐领域的3个标杆数据集,Movielens数据集、Jester数据集及Tencent Weibo数据集上进行了实验,关于这3个数据集的描述见表1.
表1 实验中使用的数据集
首先对Jester数据集和Tencent Weibo数据集进行一些预处理.对于Jester数据集,设定阈值为80,即保留至少对80则笑话进行评分的用户,于是得到一个含有6 916个用户的评分矩阵,然后把每个评分值转化到1到5之间.对于Tencent Weibo数据集,设定阈值为300,即保留至少存在300个关注者对其评分的被关注者和至少对300个被关注者进行评分的关注者,于是得到一个含有6 806个关注者和1 274个被关注者的评分矩阵.
推荐系统中最常用的度量指标之一是平均绝对误差(mean absolute error,MAE).本文将采用MAE来度量推荐算法的性能优劣.
将本文提出的基于极速学习机和最近邻的回归推荐算法与常用的LRCF推荐算法在基于对象的回归推荐方式下进行实验比较.随机选择70%的评分项作为训练数据集,剩余评分项作为测试数据集.训练集的构造都独立重复10次,取10次实验结果MAE的均值作为它们最终的性能指标,如表2所示.实验中,采用k最近邻法填充缺失值时,选用的是欧式距离,并且参数k首先选取较小的数,经过反复实验,最终得到最优的k值.极速学习机回归器中的隐含层节点个数一般认为越大越好,实验中选取节点个数为80.
表2 基于对象的回归推荐方式下的平均绝对误差比较
从表2可以看出,在3个标杆数据集上,本文提出的算法和LRCF推荐算法相比,MAE较小,推荐效果更优,尤其在Tencent Weibo数据集上,本文提出的ELMCF算法在训练集和测试集上的优势更为明显,大大优于LRCF算法的推荐结果.另外,大多数情况下,测试误差都比训练误差稍微大一些,这也容易理解,因为测试样本分布与训练样本的分布往往不完全一致,于是造成了在基于训练样本建立的模型进行测试时产生误差较大.
5 结论
本文提出的基于极速学习机的回归推荐算法具有回归器个数少、不需要集成、回归方式更加合理等优点.与常用的LRCF推荐算法相比,平均绝对误差较小,推荐效果更优.但是,极速学习机回归推荐算法中,需要确定隐含层节点的个数,本文中指定了该参数的值,该参数的取值对推荐效果有无影响以及有什么影响将是未来研究工作的一部分.
[1] RESNICK P,VARIAN H R.Recommender systems[J].Communications of the ACM,1997,40(3):56-58.
[2] BREESE J S,HECKERMAN D,KADIE C.Empirical analysis of predictive algorithms for collaborative filtering[Z].The 14th Conference on Uncertainty in Artificial Intelligence,Madison,wisconsin,USA,1998.
[3] BASU C,HIRSH H,COHEN W,et al.Recommendation as classification: Using social and content-based information in recommendation[Z].The 15th National Conference on Artificial Intelligence and and 10th Innovative Applications of Artificial Intelligence Conference,Madison,Wisconsin,USA,1998.
[4] 马宏伟,张光卫,李鹏.协同过滤推荐算法综述[J].小型微型计算机系统,2009,30( 7) : 1282-1288.
[5] 孙光福,吴乐,刘淇,等.基于时序行为的协同过滤推荐算法[J].软件学报,2013,24(11):2721-2733.DOI:10.3724/SP.J.1001.2013.04478.
SUN G F,WU L,LI Q,et al.Recommendations based on collaborative filtering by exploiting sequential behaviors[J].Journal of Software,2013,24(11):2721-2733.DOI:10.3724/SP.J.1001.2013.04478.
[6] 荣辉桂,火生旭,胡春华,等.基于用户相似度的协同过滤推荐算法[J].通信学报,2014,35(2):16-24.DOI:10.3969/j.issn.1000-436x.2014.02.003.
[7] HUANG G B,ZHU Q Y,SIEW C K.Extreme learning machine: a new learning scheme of feedforward neural networks[C]//2004 IEEE International Joint Conference on Neural Networks.2004.DOI:10.1109/IJCNN.2004.1380068.
[8] HUANG G B,ZHU Q Y,SIEW C K.Extreme learning machine:Theory and applications[J].Neurocomputing,2006,70(1-3):489-501.DOI:10.1016/j.neucom.2005.12.126.
[9] 李纯果,李海峰.无监督排序学习算法的一致性比较 [J].河北大学学报(自然科学版),2015,35 (2): 182-187.DOI: 10.3969/j.issn.10001565.2015.02.013.
LI C G,LI H F.Comparison analysis on ranking consensus[J].Journal of Hebei University: Naturnal Science Edition,2015,35(2): 182-187.DOI: 10.3969/j.issn.10001565.2015.02.013.
[10] 尚田丰.协同推荐关键技术研究[D].北京:中国科学院大学,2014.
SHANG T F. Research on critical technologies of collaborative recommendation[D].Bei jing:University of chinese Academy of sciences,2014.
Regressionrecommendationalgorithmbasedonextremelearningmachineandnearestneighbors
CHENAixia1,LINing2
(1.College of Mathematics and Information Science,Hebei University,Baoding 071002,China; 2.Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China)
This paper proposed a collaborative filtering regression recommendation algorithm based on extreme learning machine(ELM) and nearest neighbors.The algorithm firstly used theknearest neighbors method to fill the missing attribute value,then the ELM regression machine is used to produce recommendations for the user.On the benchmarking data sets in the field of recommendation,we compared our algorithm with the common recommend algorithm—LRCF algorithm,and verified the effectiveness of the proposed algorithm.
knearest neighbors; extreme learning machine; recommender systems
10.3969/j.issn.1000-1565.2017.06.014
2016-11-08
国家自然科学基金资助项目(61672205)
陈爱霞 (1982—),女,河北宁晋人,河北大学讲师,主要从事不确定信息处理方面研究. E-mail:aixia_chen@163.com
TP183
A
1000-1565(2017)06-0662-05
孟素兰)