李 凌,顾晓梅,刘子豪
1.河海大学 计算机与信息学院,南京211100
2.南京师范大学 外国语学院,南京210097
3.江苏科技大学 计算机学院,江苏 镇江212003
移动互联网(Mobile Internet)、物联网(Internet of Things,IoT)和全球定位系统(Global Positioning System,GPS)等技术的普及,极大地促进了基于位置服务(Location Based Service,LBS)的发展,并产生了海量的情境大数据[1]。用户所处的时空信息(Spatio-Temporal Information)中包含了大量的用户行为习惯和生活情境信息[2]。因此,人们可以使用数据挖掘、机器学习等技术从情境信息数据中提取出潜在的、有效的、新颖的知识和价值。
冷启动和数据稀疏是影响推荐系统预测精度的两个主要问题,其中冷启动问题又包括用户冷启动、项目冷启动和系统冷启动[3]。一方面,情境感知技术可以改进用户冷启动问题。用户冷启动问题是指新用户刚进入系统的时候,系统内没有该用户的历史行为数据,很难向此用户推荐偏好的项目[4]。解决用户冷启动问题的有效方案之一是将用户情境信息加入推荐模型中。以物流车辆和货物之间信息推荐为例,当新的司机完成注册并进入系统时,系统没有该司机的历史行为数据,不能根据历史数据向该司机进行货物推荐。此时,可以根据物流司机当前所处的情境信息进行推荐,比如以该司机所在位置为圆点,向他推荐半径40 km圆内的有运输需求的货物。另一方面,情境感知也可以改进数据类别稀疏问题。通过引入情境感知技术主动获取用户与系统交互行为的情境信息,不仅能够使获取的用户信息数大幅增加,而且使获取的用户信息时间分布更合理[5]。用户信息的获取和用户与系统的交互行为直接相关,系统可以实时获取用户的当前情况,使推荐服务能够动态反映用户需求的变化情况,改善数据稀疏问题。因此,在推荐系统中应用情境感知技术非常必要。
本文提出一种基于多子域随机森林算法的情境感知推荐方法。该方法首先对特征重要性按权值大小进行排序,将权值的取值区域分为多个大小相等的子区域,在这些子区域中随机选择特征,构造特征子空间来改进随机森林算法;然后通过改进的随机森林算法来分解并降低用户、项目和情境的特征维度;最后使用协同过滤推荐算法来进行冷链物流配载个性化推荐。对LDOS-CoMoDa 和Cycle Share 两个数据集进行仿真实验,结果表明该方法相比传统方法平均绝对误差减少近10%,有效地提高了推荐系统的预测精度,为情境感知推荐的应用提供借鉴。
目前情境感知推荐方法主要有三类:基于内容的情境感知推荐,基于协同过滤的情境感知推荐,混合式情境感知推荐[6-7]。基于协同过滤的情境感知推荐将情境信息融入到用户相似性、项目相似性和模型计算上,以提高推荐精度[8-9]。基于内容的情境感知推荐重点考虑用户偏好、情境信息与项目属性的匹配度,挖掘用户在不同情境下对不同项目属性的偏好,并结合每个具体项目的属性描述,发现用户、项目、情境之间的匹配程度,从而预测潜在的情境用户偏好,最后结合用户当前情境生成推荐[9]。混合式情境感知推荐将上述多种单一推荐方法混合进行推荐,混合的策略主要有加权、串联、混合呈现、特征组合等[10]。上述三类情境感知推荐方法有效地将情境信息应用到推荐系统,取得了广泛应用,但也存在一些不足,主要体现在:
(1)目前的研究主要是基于用户位置的信息推荐,较少有将地理位置与用户所从事的活动类型这两方面综合起来描述情境的特征。
(2)目前的研究主要将情境感知与个性化推荐结合时都赋予了情境因素相同的权重,忽略了用户在不同的情境下所偏好项目的不同,以及情境因素在推荐过程中所起的影响作用不同。
近年来,多种包含情境信息的推荐方法被提出,有效地提高了推荐结果。Wang等人考虑了利用层次结构提高推荐质量的问题,提出了一种新的两阶段推荐模型,称为层次分解机(Hierarchical Factorization Machines,HFM)[11]。Zheng等人[12]提出了属性和全局增强(Attribute and Global Boosting,AGB)模型来完成情境感知推荐中的评分预测任务。该研究的主要结论是,属性可以通过局部优化和全局优化来充分利用。Ren等人[13]提出了一种称为TGSC-PMF的情境感知概率矩阵分解方法,用于POI(Point-of-Interest)推荐。TGSC-PMF模型利用了文本信息、地理信息、社会信息、分类信息和流行信息,并有效地结合了这些因素。Hidasi等人[14]提出了一个通用分解框架(General Factorization Framework,GFF),GFF是一种单一的灵活算法,将偏好模型作为输入维度的输入和计算的潜在特征矩阵。GFF 无论是对显式反馈还是隐式反馈,均允许在情境感知的推荐任务中使用多种线性模型。Alhamid等人[15]提出一种新模型来帮助推荐系统通过整合情境参数来选择最适合、最喜欢的或相关的内容。该模型利用社交标签,计算用户对来自其他相似情境的潜在偏好,以及计算项目来自其他相似情境的潜在偏好。Unger等人[16]提出了一种以环境特征表示低维无监督潜在情境为中心的新方法。他们从移动传感器中提取大量数据,以无监督的方式推断用户的情境。潜在情境被建模为从原始传感器数据有效提取的数字向量的隐藏情境模式。使用无监督深度学习和主成分分析(Principal Component Analysis,PCA)技术从用户手机收集的数据中,为每个用户自动学习潜在情境。候营辉等人[17]将情境感知思想加入到流式应用分发系统中,实现为用户在不同的情境下提供个性化应用推荐。该方法通过采集流式应用场景下用户的情境信息数据,利用机器学习Xgboost算法识别用户情境活动,并根据识别的用户情境来为用户推荐应用。
随机森林是一种基于随机决策树的集成学习方式,已被用于处理多种学习任务,并取得了很好的效果[18]。随机森林的总体思想是以随机的方式建立一个森林,森林里面包含多个决策树,每一棵决策树之间没有关联性。在随机森林生成后,当新的样本输入进来时,随机森林让每一棵决策树分别对样本进行预测,然后选择所有决策树预测最多的类别作为新样本的类别。
随机森林的分类准确率受到决策树数目的影响较大,而实际应用中考虑到计算代价,样本集数目又不宜设置过大[16]。如果要改善随机森林在高维数据中的问题,需要在样本集数目一定的情况下,尽量减少冗余特征带来的干扰,降低特征子空间的不确定性,让随机选取的特征具有更高的代表性。
标准随机森林算法通过随机方法选取特征属性,在这种情况下,每一个特征被选中的概率是一样的。而在现实情况中,每一个特征的重要程度并不一样,对节点分裂影响也不一样。如果所有树均以特征相关性大小作为参考进行特征子空间选取,会出现权值大的特征总被选中的情况,降低了特征子空间的多样性,使得被选中的树具有较高的相关性,反而降低了模型的泛化能力。为了既能体现被选中树的特征重要程度,又能保持被选中树的多样性,本文提出了一种基于多子域随机森林算法,总体思路如下:首先选定特征子空间个数g,不同的数据集可以通过实验确定最优的g 值,g 值建议取值范围是2 ≤g ≤10,较大的g 值表示划分的特征子空间个数较多,反而会降低模型精度;然后对特征的重要性进行评估,根据计算的权值大小重新排序;接着将重新排序后的权值区间分为g 个子区域;最后根据划分的子区域,分别从每个区域随机选取特征,构造g 个特征子空间。标准随机森林算法的每棵决策树的每个节点分裂依据是从f 个输入特征中,随机挑选fsub个特征(fsub<<f),按照节点不纯度(如Gini不纯度)最小原则,从这fsub个特征中选出一个特征作为该节点的分裂属性。本文提出的改进随机森林算法中节点分裂方法与标准随机森林算法的分裂方法基本原理相同,只是特征选取范围原来是“从所有输入特征中随机选取fsub个特征”改变为“从各个子区域内的多次循环随机选取个特征”。
详细的改进随机森林算法步骤如下:
输入:包含k 个样本的原始训练集H ,训练集特征为f 。
输出:包含z 棵决策树的随机森林。
步骤1 选取特征子空间个数g。
步骤2 对包含k 个样本的原始训练集H 中的数据,采取随机有放回抽样(Bootstrap 抽样)抽取样本,重复抽样k 次后形成一个大小相同的新的训练数据集(有可能出现重复的样本)。
步骤3 重复步骤2共z 次,最终形成z 个训练数据集。
步骤4 从z 个训练数据集中选取一个数据集,以此生成一棵决策树,该数据集将是这棵决策树的全部训练数据。
步骤5 使用PCA计算各个特征的权值Fl。
步骤6 将Fl降序排列,以为边界,划分出g 个子区域分别如式(1)、式(2)和式(3)所示。
步骤7 按照步骤6 的节点分裂方法生成整个决策树。如果某一节点选出的分裂属性是刚刚其父节点分裂时用过的属性,则该节点已经达到叶子节点,无须继续分裂了。整个决策树的形成过程中不进行剪枝。
步骤8 重复步骤4~步骤7,直到完成对全部z 个训练数据集的训练后停止。
步骤9 输出包含z 棵决策树的随机森林,使用随机森林对新的数据进行预测,预测结果按照z 棵决策树的投票结果决定。
在标准随机森林中每一棵决策树模型的训练均是采用随机有放回抽样方法(Bootstrap抽样)抽取样本,这样使得每一棵决策树模型的训练样本不完全相同,每一棵决策树模型都存在一些样本不在该模型的训练集中的情况,这些没有被抽中的样本可以作为该决策树模型的测试集样本。在构造每一棵决策树模型的过程中并没有使用全部的特征变量,而是随机地从全部特征中抽取一个子集来训练模型,从而使得每一棵决策树的训练选取的样本不完全一样,选取的特征变量也不完全一样,保证了随机森林中多棵决策树模型的多样性。本文提出的多子域随机森林算法中每一棵决策树的训练样本选取与标准随机森林中决策树一致,也是采用Bootstrap 抽样方法抽取样本,使得每一棵决策树模型的训练样本不完全相同,每一棵决策树模型都存在一些样本不在该模型的训练集中的情况,那些没有被抽中的样本作为该决策树模型的测试集样本。另外,本文提出的多子域随机森林算法中特征变量的选取方法是先计算各个特征的权值并按照权值大小排序,然后以为边界,划分出g 个子区域,特征选取时分别从g 个子区域内多次循环随机选取特征,每个特征被选中的概率也是一样的,保证了特征的多样性。图1为标准随机森林子树选取分裂特征过程示意图,图2为本文提出的多子域随机森林子树选取分裂特征过程示意图。
图1 标准随机森林子树选取分裂特征过程示意图
图2 多子域随机森林子树选取分裂特征过程示意图
本文提出的基于多子域随机森林的情境感知推荐方法模型包括三个主要过程:初始化用户偏好,计算用户偏好权重,预测用户偏好。推荐过程如图3所示。
图3 基于多子域随机森林算法的情境感知推荐过程
3.2.1 初始化用户偏好
流程开始时,首先输入包含用户、项目、情境和评分信息的历史数据集H=(U,I,C,R) 。初始化用户偏好时的情境可以看作是静态变量,此时可以只考虑用户和项目两个维度。
用户可以对项目信息进行查看、发布、转发和点赞四种浏览行为。如果用户对某一页面查看次数较多,表示用户对该页面的信息内容比较关注,即对该项目偏好度较高。用户对某一项目的“查看”“评论”“转发”“点赞”的单次行为可以设置为1 分;“发布”“查看+评论”“查看+转发”“查看+点赞”可以设置为2 分;“查看+评论+转发”“查看+评论+点赞”“查看+转发+点赞”可以设置为3 分;“查看+评论+转发+点赞”可以设置为4 分。使用节点中心度来衡量节点在预测模型中的重要程度,可以通过计算某节点入度数与其他节点总数的比值来进行定义:D( u,i,c )=InD( u,i,c )/( M-1) 。综合用户兴趣评分和节点中心度两方面,用户偏好初始值如式(6)所示。
其中,P( u,i,c )为用户对偏好项目的初始评分,L( u,i,c)为用户在Web 页面或者移动APP 中对项目的浏览行为评分,D( u,i,c )为项目在模型中的重要程度,α 为调节参数。
3.2.2 计算用户偏好权重
用户偏好权重的计算是系统个性化推荐过程中的重要步骤,不仅需要对传统推荐系统中的用户和项目进行考虑,还需要对实时动态变化的情境信息进行考虑。由于用户、项目、情境这三个维度的特征较多,本文提出的方法采用改进随机森林算法进行特征选择,经过特征选择后的模型具有较少的计算量,可以用G′=(U′,I′,E′)表示。该方法借鉴了混合推荐的思想,使用协同过滤方法处理用户-用户的相似度,使用内容过滤方法处理项目-项目的相似度。使用协同过滤方法处理用户-用户之间相似度的原因是根据用户对项目的偏好,发现与当前用户偏好相似的“邻居”用户群,再基于这些邻居用户群的历史偏好信息,为当前用户进行推荐。使用内容过滤方法处理项目-项目之间相似度的原因是根据推荐项目的元数据,发现项目之间的相关性,然后基于用户以往的喜好记录,推荐给用户相似的项目。最后得到与目标用户相似的其他用户偏好项的权重Wu′,i′,c′=Sim(( u′x,i′x,c′x),( u′y,i′y,c′y))。该权重可看成是空间中任意两个小立方体之间的距离,即点A( u′x,i′x,c′x)和点B( u′y,i′y,c′y)之间的距离。权重的大小与两个小立方体之间的距离成反比,同时该权重在推荐系统也表示用户之间、项目之间、情境之间的相似度,因此相似度也与两个小立方体之间的距离成反比,相似度公式如式(7)所示。
常用的用户偏好的权重度量方法有欧几里德距离(Euclidean Distance)、闵科夫斯基距离(Minkowski Distance)、马氏距离(Mahalanobis Distance)等,其中欧几里德距离是最简单、最易理解的度量方法[19]。本文选取欧几里德距离测度用户偏好的权重,欧几里德距离如式(8)所示。
由于向量之间距离越大表示用户之间、项目之间或者情境之间的相似度越低,可以用余弦相似度的倒数来表达用户之间、项目之间或者情境之间的距离:
本章提出方法中的用户相似度Sim(u′x,u′y)基于不同用户对相同项目具有交叉的浏览行为(查看、发布、转发和点赞),即,用户可以用向量u′=( r′1,r′2,…,r′n)表示,其中r′n表示用户浏览过的项目的得分。项目相似度Sim( i′x,i′y)是基于两个项目存在被同一用户浏览的情况,即,项目可以用向量i′=(1 ,0,1,…,q )表示,q 表示该项目是否被用户点击过,1表示被点击过,0表示未被点击过。情境相似度Sim(c′x,c′y)采用基于内容过滤的方法,使用向量来表示情境信息的内容,如使用c=( time,position,emotion )来表示时间、位置和情感。如果用户情境信息相同,则直接采用传统的二维推荐模型进行推荐。最终的权重如式(10)所示。
3.2.3 预测用户偏好
对于由用户、项目、情境组成的记录,偏好信息的预测如式(11)所示。
给定目标用户u′ ,向u′ 推荐的项目评分如式(12)所示。
采用协同过滤推荐的思想,向目标用户推荐与其情境相似的其他用户偏好的项目,可以将式(12)转换为式(13)。
式(13)中的ru′x,i′x,c′x为在c′x情境下,用户u′x对项目i′x的评分。如式(10)所示。k 为调节因子,一般k 的取值为:
由上文可知
与相似度成正比例。最后,将预测评分较高的Top- N个项目Irec={i ′r1,i′r2,…,i′rn} 推荐给目标用户,其中r1>r2>…>rn。
3.2.4 算法详细步骤
输入:原始训练集H(包含用户、项目、情境、评分)。
输出:推荐的项目Irec。
步骤1 初始化用户偏好模型G=(U,I,E )。
步骤2 用户偏好初始值:
步骤3 使用多子域随机森林算法对用户特征进行选择,得到U′。
步骤4 使用多子域随机森林算法对项目特征进行选择,得到I′。
步骤5 使用多子域随机森林算法对情境特征进行选择,得到C′。
步骤6 经过特征选择后的模型G′=(U′,I′,E′)。
步骤7 计算两两用户之间的相似度:
步骤8 计算两两情境之间的相似度:
步骤9 如果sim(u′x,u′y)>m 或者sim(c′x,c′y)>m,则G′=G′⋃{( u′y,c′y,i′y,ry)},否则G′=G′⋃φ。
步骤10 重复步骤7~步骤10共N 次。
步骤11 对( u′y,c′y,i′y,ry)∈G′ 中的每一个(u′y,c′y,i′y,ry),计算预测评分:
步骤12 将预测评分较高的Top- N 个项目Irec={i ′r1,i′r2,…,i′rn} 推荐给目标用户,其中r1>r2>…>rn。
本文选取LDOS-CoMoDa 数据集[20]和Cycle Share数据集[21]参与实验。LDOS-CoMoDa数据集包含了121个用户对1 232部电影的2 296条评分数据,评分的取值区间为1~5,5表示最喜欢,1表示最不喜欢,用户通过评分的数值表达了自己的兴趣爱好。该数据集除了用户和项目之外,还包含30 个变量,其中有12 个是情境变量,分别为time、daytype、season、location、weather、social、end Emo、dominant Emo、mood、physical、decision、interaction。Cycle Share数据集包括了美国西雅图市500辆共享单车在54 个站点之间的140 000 条数据,每一行数据表示了某一用户某次骑行记录。该数据集包含了41 个变量,其中有27 个是情境变量,主要包括start time、stop time、from station name、to station name、date、min/mean/max temperature、min/mean/max dew point、min/mean/max humidity、min/mean/max sea level press、min/mean/max visibility miles、min/mean/max wind speed等。
实验选取推荐系统中两种常用的预测指标来评估推荐模型的预测准确性:平均绝对误差(Mean Absolute Error,MAE)和均方根误差(Root Mean Square Error,RMSE)。MAE通过计算推荐项目的预测评分与实际评分之间的平均绝对误差来衡量推荐模型的预测准确度,MAE 的定义如式(14)所示。MAE 值越小表示推荐系统的推荐精度越高,相反,MAE值越大表示推荐系统的推荐精度越低。RMSE 通过计算推荐项目的预测评分与实际评分之间的偏差平方和与项目数N 比值的平方根来评估推荐模型的性能,RMSE 的定义如式(15)所示。RMSE 值越小表示推荐系统的推荐精度越高,相反,RMSE值越大表示推荐系统的推荐精度越低。
其中,r′i′表示预测评分,r′i′表示真实评分,N 表示项目数。
实验中选择不同的参数会产生不同的实验结果。为了取得较好的实验结果,需要确定子区域大小g 、样本集采样率、特征向量维数Dim 。为了方便对比和讨论,将本文所提方法简称为CRMMRF(Context-aware Recommendation Method based on Multi-subdomain Random Forest)。实验中,选择MF[22]和CRMMRF作为确定参数设置的方法。
(1)确定特征子空间个数g。在确定LDOS-CoMoDa数据集和Cycle Share 数据集合适的特征子空间个数g前,先设定样本集采样率取值0.6,特征向量维度Dim取值10 和20。特征子空间个数g 分别取2,3,4,5,6。LDOS-CoMoDa 数据集和Cycle Share 数据集的子区域大小的选取如图4和图5所示。从图4可以看出,LDOSCoMoDa 数据集最好的特征子空间个数g 为3,然后依次为4、2、5、6和7。从图5可以看出,Cycle Share数据集最好的特征子空间个数g 为4,然后依次为3、5、2、6和7。
(2)选择样本集采样率。在确定LDOS-CoMoDa数据集和Cycle Share 数据集合适的样本采样率前,设定特征向量维度Dim 取值10 和20。样本集采样率分别取0.3,0.4,0.5,0.6,0.7,0.8。LDOS-CoMoDa 数据集和Cycle Share 数据集的样本采样率的选取如图6 和图7所示。从图6 可以看出,LDOS-CoMoDa 数据集最好的样本集采样率为0.6,然后依次为0.7、0.5、0.8、0.4 和0.3。从图7 可以看出,Cycle Share 数据集最好的样本集采样率为0.6,然后依次为0.7、0.8、0.5、0.4 和0.3。在两个数据集中,在采样率低于0.6 时,MAE 值和RMSE值随采样率增长而降低,但当采样率高于0.6 时,MAE值和RMSE 值随采样率增加而增加。这个现象表明了当采样率高于0.6时,产生了过拟合现象。
图4 选取LDOS-CoMoDa特征子空间个数g
图5 选取Cycle Share特征子空间个数g
图6 选取LDOS-CoMoDa样本集采样率
图7 选取Cycle Share样本集采样率
(3)选择特征向量维数Dim。LDOS-CoMoDa数据集包含30 个特征向量的维度,Cycle Share 数据集包含41个特征向量的维度。本文通过PCA来计算每个特征的贡献实现特征向量维数的降低。选择总贡献率的80%特征向量参与实验。图8为LDOS-CoMoDa数据集每个特征的贡献率以及总贡献率为80%的特征向量,图9 显示了Cycle Share 数据集每个特征的贡献率以及总贡献率为80%的特征向量。从图8 可以看出,LDOSCoMoDa数据集前80%贡献率的12个属性分别为country、city、budget、age、genre1、movieCountry、actor3、dominantEmo、interaction、location、social 和endEmo。从图9可以看出,Cycle Share 数据集前80%贡献率的22 个属性分别为Max_Temperature_F、Mean_Temperature_F、Min_Temperature_F、Max_Dew_Point_F、MeanDew_Point_F、Min_Dewpoint_F、Max_Sea_Level_Pressure_In、Mean_Sea_Level_Pressure_In、Min_Sea_Level_Pressure_In、Max_Humidity、Mean_Humidity、Min_Humidity、trip_id、Precipitation_In、Mean_Wind_Speed_MPH、Max_Wind_Speed_MPH、to_latitude、to_longitude、from_latitude、Mean_Visibility_Miles、Min_Visibility_Miles 和sto_current_dockcount。
实验选用基于用户最近邻推荐(User-based Nearest Neighbor Recommendation,UserNNR)[23]、基于项目最近邻推荐(Item-based Nearest Neighbor Recommendation,ItemNNR)[24]、HF[11]、GFF[14]和矩阵分解推荐(Matrix Factorization,MF)[22]作为参比方法。上述所有方法的默认参数均设置为文献中提到的最优值。
图8 LDOS-CoMoDa数据集特征维度影响
图9 Cycle Share数据集特征维度影响
为了使实验具有更好的代表性,对比实验中训练数据集选取0.4、0.5、0.6 和0.7 四种样本采样率,特征维度Dim 分别取12和22两种维度。
由不同参数组合构成的实验重复进行5次,实验结果取这5 次的平均值。实验中LDOS-CoMoDa 数据集的比较实验如图10 所示,具体数值如表1 所示。Cycle Share 数据集的比较实验如图11 所示,具体数值如表2所示。表3 为CRMMRF 方法与其他5 种方法的MAE和RMSE值的平均降低百分比。
从图10、图11和表1、表2中可以看出,CRMMRF在忽略条件偏好的情况下,在两个实验数据集中,预测结果均优于UserNNR、ItemNNR、MF、HFM 和GFF,表现出较好的预测准确度和泛化能力。从表3 中还可以看出,CRMMRF 与其他参比方法的MAE 和RMSE 值,在LDOS-CoMoDa数据集上平均减少了11.17%~14.29%和10.87%~18.28%,在Cycle Share 数据集上平均减少了2.48%~16.83%和1.96%~9.42%。
图10 LDOS-CoMoDa数据集比较实验(Dim=12)
表1 LDOS-CoMoDa数据集比较实验中的MAE值和RMSE值
图11 Cycle Share数据集比较实验(Dim=22)
表2 Cycle Share数据集比较实验中的MAE值和RMSE值
表3 MAE和RMSE平均降低百分比 %
本文提出了一种基于多子域随机森林算法的情境感知推荐方法。该方法首先对特征重要性按权值大小进行排序,将权值的取值区域分为多个大小相等的子区域,在这些子区域中随机选择特征,构造特征子空间来改进随机森林算法。然后,通过改进随机森林算法来分解并降低用户、项目和情境的特征维度。最后,使用基于内容的情境表示和协同过滤推荐的思想来预测用户偏好,将预测评分较高的Top- N 项目推荐给用户。实验结果表明,该方法有效提高了推荐准确度,为情境感知推荐系统的应用提供借鉴。