基于随机森林-马尔可夫用户冷启动推荐系统

滕传志，赵月旭

(杭州电子科技大学 经济学院，浙江 杭州 310018)

0 引 言

用户冷启动问题是推荐系统中亟待解决的问题之一。目前大量的学者在这方面做了深入的研究工作，取得了丰硕的研究成果：高玉凯等[1]、王斯峰[2]、毛明松等[3]以及刘江红等[4]在协同过滤的基础上进行改进和扩展，取得了良好的效果，一定程度上缓解了冷启动问题。朱坤广等[5]、黎雪微等[6]、Margam等[7]以及Wei等[8]从个性化角度对冷启动问题进行了较为详细的研究，取得了不错的效果。王素琴等[9]针对用户冷启动问题提出了改进的Epsilon-greedy算法。Antoio等[10]利用统计学中概率模型来解决非注册的用户冷启动问题。冯宇等[11]、胡祥[12]以及张亚楠等[13]将社会关系信息融入推荐系统中，较好缓解了冷启动。本文将马尔科夫的动态时效转移优势与随机森林对数据噪声和数据缺失等问题敏感性低的优点结合起来，从而既可以充分利用用户的个性化标签属性特征来保障推荐的商品的个性化效果，又使得推荐具有动态效果，以保障在不同时间段都能够得到较为满意且符合用户个性化特征的商品列表，同时在推荐精度以及覆盖率上较传统以及其它算法有一定提升。从目前国内对冷启动推荐算法研究来看，随机森林较少涉及，本文尝试将随机森林引入并用来解决用户冷启动问题，可以为以后对随机森林在这方面的研究提供一定参考。

1 模型与算法

为方便计算首先引入下面一些记号：记N(>0) 为总用户量，M(>0) 为总商品量，U={un+1|u1,u2,…,un} 为系统中的n个用户，n+1为新进的用户。记C={c1,c2,…,cm} 为系统中m个商品量。S={s1,s2,…,sf}(f∈N)，记Tag={tag1,tag2,…,tagw} 为用户特征属性集合，Ctagi={tag1,tag2,…,tagk} 表示商品i的k个标签属性。A=[vij]n×m是用户-商品评分矩阵，vij表示用户i对商品j的评分值，若用户对某一商品没有评分，则记为空值。

1.1 随机森林

随机森林属于集成算法Bagging类型的一种，它是将多个弱分类器进行组合，以“少数服从多数”的原则或者取其平均值形成强分类器。相较于其它分类算法，随机森林在精度与泛化上均有良好的表现。该算法只需通过对给定样本的学习训练分类规则，不需要任何先验假设条件。随机森林由于简单、易实现、计算开销小等优点使得其在现实中得到广泛的应用。

为实现随机森林，下面给出该算法的操作步骤：

(1)记初始数据集分为N个样本集，利用自助法随机抽取N个样本集作为训练集，抽取K次，训练集分别为：T1,T2,…,Tk。

(2)设原始数据集中有D个特征，并组成D维特征空间，在生成每颗决策树中，随机选取S个特征 (S

(3)根据上述的训练，得出分类结果，运用“少数服从多数”的原则进行投票或者将分类结果进行平均化，求其平均值。具体流程如图1所示。

图1 随机森林实现流程

1.2 马尔可夫链

马尔可夫链模型是一个重要的统计模型，其中时间和状态空间都是离散形式的马尔可夫链的转移概率为

(1)

对应的状态转移概率矩阵为P=[pij]k×k。

1.3 算法阐述

1.3.1 随机森林分类

记用户特征属性以及与之对应的偏好标签集合为：{(Tag1,S1)，(Tag2,S2),…,(Tagl,Sl)}，其中Tagi={tagi1,tagi2,…,tagin} 表示用户i的特征属性集合，Si={si1,…,sik} 为第i个用户偏好的商品标签集合。运用随机森林对特征属性进行有监督分类训练，监督属性即为商品标签属性值。根据新用户特征属性得出的偏好标签记为 {s1,s2,…,sn}，初始推荐列表为 {c1,…,cn}。

1.3.2 时间-商品模型

由马尔可夫链转移概率公式，注意到时间范围选择尤为重要，因为如果选择的时间范围过大，会导致推荐效果欠佳(后面的模拟中会给出相关说明)，如果选择时间范围过小则会导致转移矩阵过大，增加计算量。因此选择适当的时间范围。设时间T={t1,t2,…,tx}，记TH=[tq,tq+h](q,q+h∈{1,2,…,x}) 为一步时间区间，其中h=tq+h-tq为状态转移的时间长度，为简便计算以及考虑时间的连续性，文中选择一步转移马尔可夫链模型。

1.3.3 转移概率修正

本文将用户偏好标签考虑进去，将用户偏好的商品赋予较大的概率值使其在下一阶段将被优先考虑。故马尔可夫一步转移概率可表示为

(2)

其中，I(si→sj) 表示si一步转移到sj的示性函数，T(Utagk∩tagcj) 表示用户偏好的标签与商品j标签匹配数量，为了体现差别且保证未匹配的商品概率不为0，做以下规定

(3)

由于在大样本情况下，当发生状态转移时会使得转移矩阵出现较为严重的稀疏现象，而这对于提高运行效率是非常不利的。为此本文在确定状态空间时引入转移阈值α，以此来缓解转移矩阵的稀疏性问题，借鉴最大信息熵方法来确定阈值α，即

αi=arg min max{(∑pij)log(∑pij)}

(4)

以随机森林分类模型得到新进用可能偏好的商品标签类别，并以此为依据进行第一层商品推荐列表。然后以第一层推荐商品为基础，建立商品之间的状态转移矩阵，当用户点击商品时，触发转移矩阵，自动形成下一时刻可能偏好的商品。但当用户没有点击原始列表中的商品，则根据用户当前点击的商品立即更新转移矩阵，由此来推测下一时刻用户可能感兴趣的商品。

1.3.4 商品质量修正

1.3.5 随机森林-马尔可夫链算法步骤

(2)求出阈值αi，并训练转移矩阵P。

(3)以标签选择符合的U个商品组成第一层列表。

(4)以被选出的商品为基础，结合训练好的一步转移概率矩阵，并且将运用质量修正因子进行修正后概率最大的商品作为下一阶段推荐商品。

(5)以上一阶段用户点击商品为基础可以再进行推荐，下一阶段推荐以此类推形成动态推荐。

2 实验与分析

2.1 数据集介绍

本文使用推荐系统中常用的movielens数据集，选择 m1-1m 数据集，该数据集包含约3900多部电影，6040位用户共1 000 209条评分记录，每位用户至少对一部电影做出评价。表1展示了movielens数据集中部分信息具体情况。

表1 movielens数据集部分数据展示

表1数据中Occupation代表职业，本数据集中共分为20类职业并分别进行了虚拟化处理，Zip-code代表邮编(美国)，Times代表时间该数据集的时间是以1970年1月1日为基准，将后期对某部电影评分时间节点转化为秒的形式。将数据集随机拆分成训练集与测试集比例为7∶3。

2.2 数据预处理

将该数据集分成两部分，一部分是用户特征属性集合，例如：职业、性别、年龄等，另一部分为其它集合，例如：时间、电影、标签值等。在时间区间划分上由于该数据集的时间戳是以1970年1月1日为基准将用户评分的时间转换成以秒为单位的时间值。经过计算得出：1 h=3600 s，1 day=86 400 s，1 m=2 592 000 s(以30天为准)，1 year=31 104 000 s。

在运用随机森林进行分类时，本文做如下设置：每次随机重复抽取训练集：N=50 000样本，训练次数为500次。

2.3 模型评价指标

为了可以和其它方法进行比较，本文以第一，二层共20种商品为准进行比较。选用推荐系统中常用的准确率与召回率作为各模型评比标准。表2为准确率与召回率的具体计算方法。

表2 召回率与准确率计算方法

准确率=A(A+B)-1，召回率=A(A+C)-1。

2.4 模型结果及比较

本节给出各模型的准确率与召回率及其比较，以及相关参数变化给算法准确率与召回率带来的影响分析。具体如下。

2.4.1 时间阈值影响验证

根据上文1.3.2节可知，时间阈值的选取对模型准确率与召回率有较大影响，需要对其进行模拟说明，图2展示了所提算法在movielens数据集中由于选择不同时间阈值对准确率与召回率产生的影响结果。

图2 不同时间阈值下准确率与召回率的表现

图2中18 000、36 000、86 400分别代表5小时、10小时、1天的时间范围。从图2可以看出，时间因素对模型的准确率与召回率有重要影响，当时间阈值由5小时逐步扩大到1天可以看到准确率呈现出下降的趋势，对于实现个性化推荐是不够理想的，但注意到召回率却呈现出递增的趋势，但是召回率范围过大会导致推荐的商品种类过于繁多，这不仅增加了计算机的运算负担，降低了推荐时效性而且使得推荐列表不够精准化。因此要综合权衡这两方面的考虑选择最佳阈值。

2.4.2 随机森林中树的深度影响验证

随机森林中各棵决策树的深度选择也将会影响到模型的准确率与召回率的表现，图3展示了本文所提给出的算法在movielens数据集中由于树的深度不同而使得准确率与召回率的差异的具体表现。

图3 随机森林中各决策树的深度选择

由图3可知，决策树的深度选择对模型是有一定的影响的，当决策树的深度为4时，其准确率最高，但是召回率有所降低，因此在决策树深度的选择上，要结合实际考虑。

2.4.3 算法有效性验证

为验证本文所提算法的有效性，将随机森林-马尔可夫算法(random forest-Markov chain，RF-MC)与冷启动中经典算法：流行策略及用户协同过滤(USER-CF)，当前较新算法：协同概率矩阵分解与迭代决策树(GBDT-MPMF)与近邻协同过滤算法(CF-AFN)，进行对比分析。表3展示了各算法在movielens数据集中准确率与召回率的具体表现。

表3 不同策略的准确率与召回率比较/%

从表3可以看出相较于经典的算法如流行策略，USER-CF在准确率和召回率上有较大的提升，相比于新的算法如GBDT-MPMF、CFAFN，准确率和召回率有一定的提升。

3 结束语

在冷启动推荐系统中，以往的研究很少能做到实时动态推荐的效果，文中的算法可以较好地完成这一目标。从模拟的结果来看，该算法具有较高的准确率和召回率，注意到时间区间划分上不是越大越好，当范围扩大后虽然召回率得到提升但是准确率会有所降低，不利于实现个性化推荐，因此在时间选择上应该根据实际需要做适当选择。同时在决策树深度的选择上同样也要根据实际需要进行选择。当然本文也有不足之处，其一在时效性方面，由于目前没有较好的在线测试平台，故而无法有效验证实际效果，其二本文只考虑了用户的特征属性信息以及消费时间因素。所以如何将社会关系信息加入模型当中而且又有较好时效性是今后的主要研究工作。