集成树类模型及其在百度搜索推荐系统中的应用

标签: 搜索引擎 机器学习 bagging boosting c45 | 发表时间:2014-02-18 11:31 | 作者:semo2524
出处:http://semocean.com

决策树是经典高效的机器学习分类算法, 非常适用于线性模型效果不能满足需求, 规则描述分布比较合适的场景。而决策树与传统bagging, boosting思想结合在一起, 就形成集成树模型方法, 包括Random Forest,GBDT等方法。 在百度搜索关键词搜索推荐系统策略中,实验证明集成树模型具有非常高的预估分类准确性。

决策树模型

举一个简单例子(引自公司pengzhiming同学的PPT): 老妈让自己相过多次亲的女儿再次去相亲, 女儿简单问了下对方的条件, 以判断是否去; 根据男方条件(特征)对去与不去进行分类的过程, 就是一个CART决策树。

cart

例如:

母女对话如下:

cart_text

如果将女儿的历史相亲经历看成是训练样本(男方条件为特征,女儿到对方后觉得是否靠谱作为label),将女儿积累到现在的相亲经验则是一个CART模型: 根据老妈的描述,就可以判断出是否有必要去见男方。

当然, 决策树模型也可以再细分, 包括经典的ID3,C4.5, CART。 不同的决策树具有不同的树结构,以及不同的节点拆分算法及拆分标准。

树模型的优缺点

总体来说,树类算法都是使用贪心算法, 选择当前最合适属性进行拆分建立整棵决策树,该类模型比较适用于能够用复杂规则描述的应用场景

以下为树模型的优点:

  • 实现较为简单, 且容易实现并行化
  • 训练速度较快, 且一般效果也比较好
  • 能够处理连续值特征(和LR类似的模型相比), 不用对特征做归一化即能取得较好效果
  • 能够处理高维特征
  • 训练完毕后, 能够给出哪些特征比较重要;而且很多情况下,即 使最终使用其他模型, 也可以使用树模型选择特征

当然, 所有的模型都有其弊端:

  • 树模型容易过拟合, 所以需要进行剪枝(以及使用后续的集成学习方法解决)
  • 不能表示复杂结构和运算: 树模型原则上天然表示‘与’操作, 所以不能表示类似于‘异或’的操作

因为树模型的以上优点, 树模型在很多场景均会被选用。

树模型训练框架

以下为使用数据集D,属性(特征)集合attribute_list产生决策树的算法框架。该算法未包含任何剪枝。

decision_tree

以上伪代码中(2)~(5)行用来处理数据中都是相同label及无属性拆分的情况,剩余代码使用贪心算法选择最合适的属性后,进行拆分,并递归建立子节点。

在上述伪代码中涉及到attribute_selection_method逻辑, 也就是决策树节点拆分标准的问题。

树模型节点分裂标准

如上所述,决策树使用贪心算法进行拆分, 选择当前认为最优的拆分特征进行树节点的分裂。 这就涉及到选择何种属性作为拆分的标准。一般说来, 经常使用的树节点拆分标准主要有以下几类:

  • information gain

一般情况下, 在决策树中, 使用信息增益(information gain)作为节点分裂的选择标准。

要定义信息增益, 我们需要定义‘信息’,我们将信息定义为: 对于数据集合D,我们需要对D中的各种类别进行编码的字节编码数,即:

infor

信息量, 也被称为熵(entropy),用于描述不稳定性或多样性。 对样本集合D中, 假设对于某一维度的特征, 该特征A有v种取值, 而每种取值对应的数据样本数为Dj, 则在知道了某属性A的各种取值,并将符合各v值得样本进行分类后, 需要将样本集合D完全分开所需要的信息量为:

infor_a

其中Dj为符合每个A的取值(假设A为离散可数种取值)的子样本集合。infor(Dj)为完全划分子样本集合所需要的信息量。 此时可定义信息增益:

info_gain

在ID3算法中, 使用信息增益进行分裂特征的选择, 算法会使用贪心算法选择信息增益最大的特征进行树节点的分裂。 但信息增益有一个缺点: 会选择有众多值的特征进行节点分裂, 极端情况, 对于ID类特征(利用用户ID, 或是item ID), ID的个数与待分类的样本数一样, 这样的分裂是没有意义的, 此时, 使用gain ratio作为节点拆分标准, 能避免该问题。

  • gain ratio

为了解决信息增益偏向于选择属性值较多的特征问题, 在c4.5中引入了gain ratio。 首先定义:

splitinfo

注意splitinfo_A 与info_A的不同: splitinfo的第二项受到的是符合特征A下每种取值的样本数量影响; info_A则受到特征A下每种取值的样本包含的信息的影响。注意参考entropy的定义, 当分布越是不均匀时, 描述这种状态所需要的信息量约小, 分布越是散时, 需要的信息量越大(info值越大), 所以当拆分特征的值越多时, splitinfo会越大。

gainratio

此时我们定义gainratio, 分母为splitinfo 起到抑制拆分多值特征的倾向。

  • gini index

在CART中, 使用gini index作为节点拆分的标准, gini系数的定义如下:

gini

其中pi为样本集合D中各类的占比(总共有m类, pi=Di/D, 其中Di为D中属于类别i的的样本数量)

定义:

gini_index

即使用属性A来对样本进行节点拆分后时的gini index, 此时可使用gini_A来对A进行拆分判定, 选择gini系数值下降最快的属性进行拆分。

gini_increse

一般说来information gain,gain ratio, gini index就是最常使用的三种拆分指标。结合前述树模型构建方法, 再加上构建树的过程中/后的限定条件及剪枝, 即可构建出实际中高效的决策树。

集成学习方法

集成学习方法是将bagging,boosting思路与树模型结合的高效学习方法。

bagging的思路比较简单, 就是汇集多个模型进行投票, 每个模型的票的权重一样, 获得票数最多的预估类胜出, 该类获得的票数与总票数的比值可以作为置信度。 如果是回归问题, 则多模型预估值得平均值作为bagging结果。

boosting方法在bagging的思想上前进了一步: boosting在训练时会更在乎分类错误的样本, 给予分类错误的样本更高的权重训练模型, 并将这些权重不一的模型根据权重进行bagging。boosting更像是是医疗专家诊断病情一样: 诊断容易出错的病情正确率更高的专家的话语权更高。 具体adaboost的介绍可参见《 adaboost

bagging方法, 特别是adaboost方法一般都会使用非常简单的弱分类器进行bagging和boosting, 随着计算机处理能力的增强, 可以使用更加复杂的模型进行bagging&boosting, 而过将弱分类器使用更加复杂的树模型, 就形成‘集成树模型’。比较常用的‘集成树模型’包括Random Forest和GBDT。

complex_decision_boundery

虽然单个树模型学习能力有限(拟合复杂的数据分布能力有限), 但多个树模型放到一起, 就能够高精度拟合出复杂的分布(如上图所示), 这就是集成学习的强大之处。

  • Random Forest

Random Forest(RF)是典型的bagging树模型的方法。 其思路就是使用随机的部分样本/特征构建树模型, 之后使用bagging思想进行分类。

RF不仅对特征集合进行采样, 同样也可以对样本进行采样, 例如在进行单个cart训练时, 对每个模型,随机使用这种方式一方面充分利用了所有样本, 特征的贡献, 另一方面, 又能避免部分噪音带来的过拟合。设置合适的样本随机采样率(例如0.6表示每个模型选择60%的样本进行训练)以及何时的特征随机采样率(例如0.6表示每个模型选择特征集合60%的特征进行训练)进行RF训练。

rf

在进行分类时, 根据样本和特征抽样训练出来的模型使用bagging方法进行投票。

相对于boosting会依赖于前一模型分类正确or错误调整样本权值的思路, RF更容易实现并行化, 因为RF中各子树的训练过程是完全独立的不会相互影响

  • GBDT

Grandent Boosting(GB)是将梯度下降思路融入boosting方法中, 不同于传统boosting每一步对分错样本进行加权(或对分对样本进行加权),GB定义整个模型的损失函数。

算法的每一步沿着损失函数下降最快的方向建立新的模型,这样使得算法在每一步均沿着下降最快的方向收敛。 直到满足要求, 建立满足要求的若干组合加权子模型。

gbdt_tree

 

Gradient Boosting将问题进行建模,定义loss function为

loss_function

则对于训练样本集合{y, x}, 我们的任务是寻找最小化loss的函数F*(x):

loss_f_F

而gradient boosting的思路是将映射模型函数表示为以下形式:

F_func

其中h(x;am)为简单函数/模型, am 为h的参数, 此时, belta, a, 就为我们要预估的最小化loss下的参数:

param

同时Fm与F_m-1的关系为

F_func1

 

之后可以求belta和a序列参数, 求解过程如下:

在第i个样本点, 第m个模型里边的伪残差求解方法为:

pesudo_residul

要构建模型h(x,am), 最快的方法, 就是让所有的样本点处, 损失函数都沿着最快的方向下降。

也就是: am

利用最小二乘法求解am后, 即可求解belta_m

belta_m

依次求解所有am, belta_m后, 即得到最终模型F*(x)

树模型在百度关键词搜索推荐中的应用及实验结果

当然, 很多时候我们不会直接去修改模型, 在应用中, 更多地是使用模型作为工具解决具体问题。 例如在百度关键词搜索推荐中, 我们更多是构建相关性判断的特征样本, 之后对模型参数进行搜索: 例如样本采样率, 特征采样率等参数。 具体效果参见实验部分。百度关键词搜索推荐介绍及交互流程参见《 百度关键词搜索推荐系统交互流程

一下为具体应用标注负样本示例,例如‘水仙花’, 从搜索引擎商业价值角度考虑, 是具体描述水仙花这个商品, 而不一样是信息型舞蹈名字query’紫蝶广场舞水仙花开’:

ada_boost_negative

具体GBDT在百度关键词搜索推荐中, 相关性判断的应用方法(包括特征选取和实验结果), 参见《 分类模型在关键词搜索推荐中的应用》, 使用树模型, 在没有任何样本,特征调整的情况下, 准确性直接提升了5个点 ,效果惊人。

而在排序任务重, 使用衍生GBrank对百度关键词搜索推荐结果进行排序, 一般情况下,效果随着树的深度增长而提升, 但树深度达到8后, 就不再提升。

gbrank_tree_depth

随着叶子节点书的增长, 效果仍然在提升, 所以在应用中,如果效率允许, 可以让最大叶子节点数多一些。

tree_max_leaf

在实际应用中, 理论上可以对众多参数进行全参数搜索, 找到最优参数。 实际应用中会快速找到比较好的参数后, 策略即上线进行实验。

参考文献:

  1. Friedman J H. Stochastic gradient boosting[J]. Computational Statistics & Data Analysis, 2002, 38(4): 367-378.
  2. Quinlan J R. Induction of decision trees[J]. Machine learning, 1986, 1(1): 81-106.
  3. Breiman L, Friedman J, Stone C J, et al. Classification and regression trees[M]. CRC press, 1984.
  4. 分类模型在关键词搜索推荐中的应用

百度关键词工具介绍参见:http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596

也可关注我的微博: weibo.com/dustinsea

或是直接访问: http://semocean.com

相关 [模型 百度搜索 推荐系统] 推荐:

集成树类模型及其在百度搜索推荐系统中的应用

- - Dustinsea
决策树是经典高效的机器学习分类算法, 非常适用于线性模型效果不能满足需求, 规则描述分布比较合适的场景. 而决策树与传统bagging, boosting思想结合在一起, 就形成集成树模型方法, 包括Random Forest,GBDT等方法. 在百度搜索关键词搜索推荐系统策略中,实验证明集成树模型具有非常高的预估分类准确性.

Min-Hash和推荐系统

- - xlvector - Recommender System
前几年看Google News Recommendation的那篇Paper,对里面提到的MinHash的算法基本没有注意,因为之前的习惯都是只注意论文的模型那块,至于怎么优化模型一般都只是扫一眼. 不过最近看了大量的Google Paper,发现Google在实现一个算法方面确实有很多独到之处. 其实,Min-Hash是LSH(Locality Sensitive Hash)的一种,我之前对LSH的了解仅仅限于知道它能把两个相似的东西Hash成两个汉明距离接近的2进制数.

推荐系统实战

- - 博客园_首页
推荐算法:基于特征的推荐算法. 推荐算法准确度度量公式:. 其中,R(u)表示对用户推荐的N个物品,T(u)表示用户u在测试集上喜欢的物品集合. 集合相似度度量公式(N维向量的距离度量公式):. 其中,N(u)表示用户u有过正反馈的物品集合. 其中,S(u,k)表示和用户u兴趣最接近的K个用户集合;N(i)表示对物品i有过正反馈的用户集合;w(u,v)表示用户u和用户v的兴趣相似度;r(v,i)表示用户v对物品i的兴趣.

推荐系统杂谈

- - 后端技术杂谈 | 飒然Hang
推荐系统是近些年非常火的技术,不管是电商类软件还是新闻类app,都号称有精准的推荐系统能给你推送你最感兴趣的内容. 现象级的资讯类app“今日头条”就得益于此成为了势头非常猛的一款产品. 本文就针对推荐系统讲述一些相关概念和实践经验. 首先需要明确的就是推荐系统的目标,一般来说不外乎以下几个:. 用户满意性:首当其冲的,推荐系统主要就是为了满足用户的需求,因此准确率是评判一个推荐系统好坏的最关键指标.

百度搜索评测三阶段

- - 互联网旁观者
作为搜索引擎,百度的目的是要让搜索结果的呈现次序更好. 这是设计任何算法之前必须考虑好的问题. “好”必须变成一个可以量化的指标. 来自百度网页搜索部的彭滔就跟我们介绍了他们的经验. 在百度搜索的发展历程中,“好”的评估方式大致被分为三个阶段. 彭滔取了一个query用作例子:“给我一片关于春天的作文,要长的,快点”.

百度搜索URL参数解析

- - 标点符
百度的搜索URL存在着一定的规律和逻辑,下面的链接是我使用百度搜索“标点符”后得到的链接,下面就来一起分析下百度搜索结果URL的秘密. URL中的s?表示搜索,&符号起到参数分割的作用. wd:Keyword,查询的关键词,有时还会是 word,比如 www.hao123.com打开的链接就是word,wd后面的关键词使用gb2312进行编码,如果搜索词中出现空格则使用+号替换;.

个性化推荐系统综述

- Tony - 所有文章 - UCD大社区
上个月写过一篇产品推荐的文章,详情请见《我所了解的产品推荐》,内容很泛,多为工作心得. 本周读了几篇相关的论文,收获颇多,分享点干货. 以下内容摘自《个性化推荐系统的研究进展》,该文发表于2009年1月的《自然科学进展》专题评述,作者是刘建国、周涛、汪秉宏. 我略去了具体的算法和许多公式,重点看原理、思路和比较.

推荐系统开源工具 – SVDFeature

- Roger - Resys China
SVDFeature是我们(上海交大Apex实验室)在参加KDDCUP 2011期间开发的. 通过这个工具,我们和港科大(HKUST)的联合小组InnerPeace在KDDCUP 2011中获得Track 1第三名,并创造单模型最好成绩. 在此分享给大家,并希望和大家有更多的交流. (1)基于feature的可扩展性 —— SVDFeature实现了我们的基础模型feature-based matrix factorization.

Reculike : 开源论文推荐系统

- votis - Resys China
今天这篇博文主要总结一下reculike的系统架构. 两周前我们宣布发布了reculike的alpha版. 本着分享的原则,今天在这儿介绍一下我们的各个模块的设计方法. 我们这个项目一开始叫paperlens,这是因为我们想学习业界的前辈movielens,开发一个源代码和数据都开源的系统. 关于数据的开源,我想当用户数达到一定程度后,每个月会dump一次我们所有的数据库(密码等隐私信息除外),放到网络上供大家下载.

推荐系统那些事儿1

- - 冰火岛
知识库:用户知识库,Item知识库,用户评分数据(显性和隐性)等.不同的业务背景不一样,譬如电商,社交网络,视频,app应用等. 协同过滤引擎:根据用户评分数据集,通过collaborative filtering方法,计算用户喜欢的top N item. 数据格式: userid, itemid,score.