&>&&>&&>&&>&R决策树实现
R决策树实现
上传大小：863B
R语言决策树实现方法代码，library(rpart)
library(rpart)
library(rpart.plot)
library(rpart.plot)
#rpart决策树计算
run_statement&-paste('fit&-rpart(', names(data_in_sub)[length(names(data_in_sub))], '~., data=data_in_sub, method=&class&)')
eval(parse(text=run_statement))...展开收缩
综合评分：3.5（2位用户评分）
所需积分：2
下载次数：30
审核通过送C币
创建者：nigelyq
创建者：nigelyq
创建者：ccbhnldlrb
{%username%}回复{%com_username%}{%time%}\
/*点击出现回复框*/
$(".respond_btn").on("click", function (e) {
$(this).parents(".rightLi").children(".respond_box").show();
e.stopPropagation();
$(".cancel_res").on("click", function (e) {
$(this).parents(".res_b").siblings(".res_area").val("");
$(this).parents(".respond_box").hide();
e.stopPropagation();
/*删除评论*/
$(".del_comment_c").on("click", function (e) {
var id = $(e.target).attr("id");
$.getJSON('/index.php/comment/do_invalid/' + id,
function (data) {
if (data.succ == 1) {
$(e.target).parents(".conLi").remove();
alert(data.msg);
$(".res_btn").click(function (e) {
var q = $("#form1").serializeArray();
console.log(q);
var res_area_r = $.trim($(".res_area_r").val());
if (res_area_r == '') {
$(".res_text").css({color: "red"});
$.post("/index.php/comment/do_comment_reply/", q,
function (data) {
if (data.succ == 1) {
var $dd = $target.parents('dd');
var $wrapReply = $dd.find('.respond_box');
console.log($wrapReply);
var mess = $(".res_area_r").val();
var str = str.replace(/{%header%}/g, data.header)
.replace(/{%href%}/g, 'http://' + window.location.host + '/user/' + data.username)
.replace(/{%username%}/g, data.username)
.replace(/{%com_username%}/g, _username)
.replace(/{%time%}/g, data.time)
.replace(/{%id%}/g, data.id)
.replace(/{%mess%}/g, mess);
$dd.after(str);
$(".respond_box").hide();
$(".res_area_r").val("");
$(".res_area").val("");
$wrapReply.hide();
alert(data.msg);
}, "json");
//填充回复
function KeyP(v) {
$(".res_area_r").val($.trim($(".res_area").val()));
/*删除回复*/
$(".del_comment_r").on("click", function (e) {
var id = $(e.target).attr("id");
$.getJSON('/index.php/comment/do_comment_del/' + id,
function (data) {
if (data.succ == 1) {
$(e.target).parent().parent().parent().parent().parent().remove();
$(e.target).parents('.res_list').remove()
alert(data.msg);
评论共有2条
挺好了，可以用
代码比较少，只有一点点建立、剪枝有关的，没有评价，还是谢谢了
上传者其他资源上传者专辑
数据库热门标签
VIP会员动态
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
android服务器底层网络模块的设计方法
所需积分：0
剩余积分：720
您当前C币：0
可兑换下载积分：0
兑换下载分：
兑换失败，您当前C币不够，请先充值C币
消耗C币：0
你当前的下载分为234。
R决策树实现
会员到期时间：剩余下载次数：
你还不是VIP会员
开通VIP会员权限，免积分下载
你下载资源过于频繁，请输入验证码
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
若举报审核通过，可奖励20下载分
被举报人：
jenny828328
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：在网上看到一篇对从代码层面理解gbdt比较好的文章，转载记录一下：
GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力（generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。
第1~4节：GBDT算法内部究竟是如何工作的？
第5节：它可以用于解决哪些问题？
第6节：它又是怎样应用于搜索排序的呢？
在此先给出我比较推荐的两篇英文文献，喜欢英文原版的同学可直接阅读：
【1】Boosting Decision Tree入门教程
【2】LambdaMART用于搜索排序入门教程
GBDT主要由三个概念组成：Regression Decistion Tree（即DT)，Gradient Boosting（即GB)，Shrinkage (算法的一个重要演进分枝，目前大部分源码都按该版本实现）。搞定这三个概念后就能明白GBDT是如何工作的，要继续理解它如何用于搜索排序则需要额外理解RankNet概念，之后便功德圆满。下文将逐个碎片介绍，最终把整张图拼出来。
一、 DT：回归树 Regression Decision Tree
提起决策树（DT, Decision Tree) 绝大部分人首先想到的就是C4.5分类决策树。但如果一开始就把GBDT中的树想成分类树，那就是一条歪路走到黑，一路各种坑，最终摔得都要咯血了还是一头雾水说的就是LZ自己啊有木有。咳嗯，所以说千万不要以为GBDT是很多棵分类树。决策树分为两大类，回归树和分类树。前者用于预测实数值，如明天的温度、用户的年龄、网页的相关程度；后者用于分类标签值，如晴天/阴天/雾/雨、用户性别、网页是否是垃圾页面。这里要强调的是，前者的结果加减是有意义的，如10岁+5岁-3岁=12岁，后者则无意义，如男+男+女=到底是男是女？ GBDT的核心在于累加所有树的结果作为最终结果，就像前面对年龄的累加（-3是加负3），而分类树的结果显然是没办法累加的，所以GBDT中的树都是回归树，不是分类树，这点对理解GBDT相当重要（尽管GBDT调整后也可用于分类但不代表GBDT的树是分类树）。那么回归树是如何工作的呢？
下面我们以对人的性别判别/年龄预测为例来说明，每个instance都是一个我们已知性别/年龄的人，而feature则包括这个人上网的时长、上网的时段、网购所花的金额等。
作为对比，先说分类树，我们知道C4.5分类树在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature&=阈值，和feature&阈值分成的两个分枝的熵最大的feature和阈值（熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1），按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。
回归树总体流程也是类似，不过在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差–即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和 除以N。这很好理解，被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。若还不明白可以Google “Regression Tree”，或阅读本文的第一篇论文中Regression Tree部分。
二、 GB：梯度迭代 Gradient Boosting
好吧，我起了一个很大的标题，但事实上我并不想多讲Gradient Boosting的原理，因为不明白原理并无碍于理解GBDT中的Gradient Boosting。喜欢打破砂锅问到底的同学可以阅读这篇英文wiki
Boosting，迭代，即通过迭代多棵树来共同决策。这怎么实现呢？难道是每棵树独立训练一遍，比如A这个人，第一棵树认为是10岁，第二棵树认为是0岁，第三棵树认为是20岁，我们就取平均值10岁做最终结论？–当然不是！且不说这是投票方法并不是GBDT，只要训练集不变，独立训练三次的三棵树必定完全相同，这样做完全没有意义。之前说过，GBDT是把所有树的结论累加起来做最终结论的，所以可以想到每棵树的结论并不是年龄本身，而是年龄的一个累加量。GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。这就是Gradient Boosting在GBDT中的意义，简单吧。
三、 GBDT工作过程实例。
还是年龄预测，简单起见训练集只有4个人，A,B,C,D，他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生；C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图1所示结果：
现在我们使用GBDT来做这件事，由于数据太少，我们限定叶子节点做多有两个，即每棵树都只有一个分枝，并且限定只学两棵树。我们会得到如下图2所示结果：
在第一棵树分枝和图1一样，由于A,B年龄较为相近，C,D年龄较为相近，他们被分为两拨，每拨用平均年龄作为预测值。此时计算残差（残差的意思就是： A的预测值 + A的残差 = A的实际值），所以A的残差就是16-15=1（注意，A的预测值是指前面所有树累加的和，这里前面只有一棵树所以直接是15，如果还有树则需要都累加起来作为A的预测值）。进而得到A,B,C,D的残差分别为-1,1，-1,1。然后我们拿残差替代A,B,C,D的原值，到第二棵树去学习，如果我们的预测值和它们的残差相等，则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。这里的数据显然是我可以做的，第二棵树只有两个值1和-1，直接分成两个节点。此时所有人的残差都是0，即每个人都得到了真实的预测值。
换句话说，现在A,B,C,D的预测值都和真实年龄一致了。Perfect!：
A: 14岁高一学生，购物较少，经常问学长问题；预测年龄A = 15 – 1 = 14
B: 16岁高三学生；购物较少，经常被学弟问问题；预测年龄B = 15 + 1 = 16
C: 24岁应届毕业生；购物较多，经常问师兄问题；预测年龄C = 25 – 1 = 24
D: 26岁工作两年员工；购物较多，经常被师弟问问题；预测年龄D = 25 + 1 = 26
那么哪里体现了Gradient呢？其实回到第一棵树结束时想一想，无论此时的cost function是什么，是均方差还是均差，只要它以误差作为衡量标准，残差向量(-1, 1, -1, 1)都是它的全局最优方向，这就是Gradient。
讲到这里我们已经把GBDT最核心的概念、运算过程讲完了！没错就是这么简单。不过讲到这里很容易发现三个问题：
1）既然图1和图2 最终效果相同，为何还需要GBDT呢？
答案是过拟合。过拟合是指为了让训练集精度更高，学到了很多”仅在训练集上成立的规律“，导致换一个数据集当前规律就不适用了。其实只要允许一棵树的叶子节点足够多，训练集总是能训练到100%准确率的（大不了最后一个叶子上只有一个instance)。在训练精度和实际精度（或测试精度）之间，后者才是我们想要真正得到的。
我们发现图1为了达到100%精度使用了3个feature（上网时长、时段、网购金额），其中分枝“上网时长&1.1h” 很显然已经过拟合了，这个数据集上A,B也许恰好A每天上网1.09h, B上网1.05小时，但用上网时间是不是&1.1小时来判断所有人的年龄很显然是有悖常识的；
相对来说图2的boosting虽然用了两棵树 ，但其实只用了2个feature就搞定了，后一个feature是问答比例，显然图2的依据更靠谱。（当然，这里是LZ故意做的数据，所以才能靠谱得如此狗血。实际中靠谱不靠谱总是相对的） Boosting的最大好处在于，每一步的残差计算其实变相地增大了分错instance的权重，而已经分对的instance则都趋向于0。这样后面的树就能越来越专注那些前面被分错的instance。就像我们做互联网，总是先解决60%用户的需求凑合着，再解决35%用户的需求，最后才关注那5%人的需求，这样就能逐渐把产品做好，因为不同类型用户需求可能完全不同，需要分别独立分析。如果反过来做，或者刚上来就一定要做到尽善尽美，往往最终会竹篮打水一场空。
2）Gradient呢？不是“G”BDT么？
到目前为止，我们的确没有用到求导的Gradient。在当前版本GBDT描述中，的确没有用到Gradient，该版本用残差作为全局最优的绝对方向，并不需要Gradient求解.
3）这不是boosting吧？Adaboost可不是这么定义的。
这是boosting，但不是Adaboost。GBDT不是Adaboost Decistion Tree。就像提到决策树大家会想起C4.5，提到boost多数人也会想到Adaboost。Adaboost是另一种boost方法，它按分类对错，分配不同的weight，计算cost function时使用这些weight，从而让“错分的样本权重越来越大，使它们更被重视”。Bootstrap也有类似思想，它在每一步迭代时不改变模型本身，也不计算残差，而是从N个instance训练集中按一定概率重新抽取N个instance出来（单个instance可以被重复sample），对着这N个新的instance再训练一轮。由于数据集变了迭代模型训练结果也不一样，而一个instance被前面分错的越厉害，它的概率就被设的越高，这样就能同样达到逐步关注被分错的instance，逐步完善的效果。Adaboost的方法被实践证明是一种很好的防止过拟合的方法，但至于为什么则至今没从理论上被证明。GBDT也可以在使用残差的同时引入Bootstrap re-sampling，GBDT多数实现版本中也增加的这个选项，但是否一定使用则有不同看法。re-sampling一个缺点是它的随机性，即同样的数据集合训练两遍结果是不一样的，也就是模型不可稳定复现，这对评估是很大挑战，比如很难说一个模型变好是因为你选用了更好的feature，还是由于这次sample的随机因素。
四、Shrinkage
Shrinkage（缩减）的思想认为，每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。用方程来看更清晰，即
没用Shrinkage时：（yi表示第i棵树上y的预测值， y(1~i)表示前i棵树y的综合预测值）
y(i+1) = 残差(y1~yi)， 其中： 残差(y1~yi) =
y真实值 - y(1 ~ i)
y(1 ~ i) = SUM(y1, …, yi)
Shrinkage不改变第一个方程，只把第二个方程改为：
y(1 ~ i) = y(1 ~ i-1) + step * yi
即Shrinkage仍然以残差作为学习目标，但对于残差学习出来的结果，只累加一小部分（step*残差）逐步逼近目标，step一般都比较小，如0.01~0.001（注意该step非gradient的step），导致各个树的残差是渐变的而不是陡变的。直觉上这也很好理解，不像直接用残差一步修复误差，而是只修复一点点，其实就是把大步切成了很多小步。本质上，Shrinkage为每棵树设置了一个weight，累加时要乘以这个weight，但和Gradient并没有关系。这个weight就是step。就像Adaboost一样，Shrinkage能减少过拟合发生也是经验证明的，目前还没有看到从理论的证明。
五、 GBDT的适用范围
该版本GBDT几乎可用于所有回归问题（线性/非线性），相对logistic regression仅能用于线性回归，GBDT的适用面非常广。亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）。
六、 搜索引擎排序应用 RankNet
搜索排序关注各个doc的顺序而不是绝对值，所以需要一个新的cost function，而RankNet基本就是在定义这个cost function，它可以兼容不同的算法（GBDT、神经网络…）。
实际的搜索排序使用的是LambdaMART算法，必须指出的是由于这里要使用排序需要的cost function，LambdaMART迭代用的并不是残差。Lambda在这里充当替代残差的计算方法，它使用了一种类似Gradient*步长模拟残差的方法。这里的MART在求解方法上和之前说的残差略有不同，其区别描述见这里。
就像所有的机器学习一样，搜索排序的学习也需要训练集，这里一般是用人工标注实现，即对每一个(query,doc) pair给定一个分值（如1,2,3,4）,分值越高表示越相关，越应该排到前面。然而这些绝对的分值本身意义不大，例如你很难说1分和2分文档的相关程度差异是1分和3分文档差距的一半。相关度本身就是一个很主观的评判，标注人员无法做到这种定量标注，这种标准也无法制定。但标注人员很容易做到的是”AB都不错，但文档A比文档B更相关，所以A是4分，B是3分“。RankNet就是基于此制定了一个学习误差衡量方法，即cost function。具体而言，RankNet对任意两个文档A,B，通过它们的人工标注分差，用sigmoid函数估计两者顺序和逆序的概率P1。然后同理用机器学习到的分差计算概率P2（sigmoid的好处在于它允许机器学习得到的分值是任意实数值，只要它们的分差和标准分的分差一致，P2就趋近于P1）。这时利用P1和P2求的两者的交叉熵，该交叉熵就是cost function。它越低说明机器学得的当前排序越趋近于标注排序。为了体现NDCG的作用（NDCG是搜索排序业界最常用的评判标准），RankNet还在cost function中乘以了NDCG。
好，现在我们有了cost function，而且它是和各个文档的当前分值yi相关的，那么虽然我们不知道它的全局最优方向，但可以求导求Gradient，Gradient即每个文档得分的一个下降方向组成的N维向量，N为文档个数（应该说是query-doc pair个数）。这里仅仅是把”求残差“的逻辑替换为”求梯度“，可以这样想：梯度方向为每一步最优方向，累加的步数多了，总能走到局部最优点，若该点恰好为全局最优点，那和用残差的效果是一样的。这时套到之前讲的逻辑，GDBT就已经可以上了。那么最终排序怎么产生呢？很简单，每个样本通过Shrinkage累加都会得到一个最终得分，直接按分数从大到小排序就可以了（因为机器学习产生的是实数域的预测分，极少会出现在人工标注中常见的两文档分数相等的情况，几乎不同考虑同分文档的排序方式）
另外，如果feature个数太多，每一棵回归树都要耗费大量时间，这时每个分支时可以随机抽一部分feature来遍历求最优（ELF源码实现方式）。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：188401次
积分：2325
积分：2325
排名：第15832名
原创：36篇
评论：195条
(7)(1)(1)(2)(1)(10)(2)(5)(7)(5)(1)机器学习（11）
五、决策树
决策树（decision tree）是一种基本的分类与回归方法，这里主要讨论用于分类的决策树。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要的有点是模型具有可读性，分类速度快，学习时利用训练数据，根据损失函数最小化的原则简历决策树模型。决策树的学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。
5.1决策树模型与学习
5.1.1决策树模型
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或者属性，叶结点表示一个类。
5.1.2决策树与if-then规则
可以将决策树看成是一个if-then规则的集合。将决策树转化成if-then规则的过程是这样的：由决策树的根结点到叶结点的每一条路径构建一条规则;路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
5.1.3决策树与条件概率分布
决策树还表示给定特征条件下的类的条件概率分布。这一条件概率分布定义在特征空间的一个划分（partition）上。将特征空间划分为互不相交的单元（cell）或者区域（region），并在每个单元定义一个类的概率分布就构成了一个条件概率分布。
5.1.4决策树学习
决策树学习，假设给定训练数据集D={(x1,y1),(x2,y2),?,(xN,yN)}
其中，xi为输入实例（特征向量）yi为类标记，N为样本容量。学习的目标是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。
决策树学习本质上是从训练数据集中归纳出一组分类规则。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。另一个角度看，决策树学习是由训练数据集估计条件概率模型。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。
决策树学习用损失函数表示这一目标。如下所述，决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。
当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题（NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题），所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优(sub-optimal)的。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。
5.2特征选择
5.2.1特征选择问题
特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。
5.2.2信息增益
在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为P(X=xi)=pi,i=1,2,?,n
则随机变量X的熵定义为H(X)=-∑i=1npilogpi
通常上式中的对数以2为底或者以自然对数e为底，这时熵的单位分别称作比特（bit）或纳特（nat）。由定义可知，熵只依赖于X分布，而与X的取值无关，所以也可以将X的熵记作H(p),
H(p)=-∑i=1npilogpi
熵越大，随机变量的不确定性就越大。从定义可以验证
0≤H(p)≤logn
当随机变量只取两个值，例如1,0时，即X的分布为
P(X=1)=p,P(X=0)=1-p,0≤p≤1
熵为H(p)=-plog2p-(1-p)log2(1-p)
这时，熵H(p)随概率p变化的曲线如图
当p=0或p=1时，随机变量没有不确定性，当p=0.5时，H(p)=1,熵取值最大，随机变量不确定性最大。
设有随机变量(X,Y)，其联合概率分布为
P(X=xi,Y=yj)=pij
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望
H(Y|X)=∑i=1npiH(Y|X=xi)
当熵和条件熵中的概率由数理统计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。此时若有0概率，则令0log0=0
信息增益（information gain）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即
g(D,A)=H(D)-H(D|A)
一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中的类与特征的互信息。
决策树学习应用信息增益准则选择特征。信息增益大的特征具有更强的分类能力。
根据信息增益准则的特征选择方法是：对训练数据集（或子集）D,计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。
5.2.3信息增益比
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正。这是特征选择的另一准则。
定义（信息增益比）：特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比，即
gR(D,A)=g(D,A)HA(D)其中，HA(D)=-∑ni=1|Di||D|log2|Di||D|
5.3决策树的生成
5.3.1 ID3算法
ID3算法（interative dichotomiser 3）的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。
ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob * log(prob,2)
return shannonEnt
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy
if (infoGain & bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
def createTree(dataSet,labels):
classList = [example[-1] for example in dataSet]
if classList.count(classList[0]) == len(classList):
return classList[0]
if len(dataSet[0]) == 1:
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree
5.3.2 C4.5的生成方法
C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征。
5.4决策树的剪枝
决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树容易出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决这一问题的方法是考虑决策树的复杂度，对已生成的决策树进行简化。
在决策树学习中讲已生成的树进行简化的过程称为剪枝（pruning）。
决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。设树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有Nt个样本点，其中k类的样本点有Ntk个,Ht(T)为叶节点t上的经验熵，α≥0为参数，则决策树学习的损失函数可以定义为Cα(T)=∑t=1|T|NtHt(T)+α|T|
令Cα(T)=C(T)+α|T|
其中C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数α≥0控制两者之间的影响。较大的α促使选择较简单的模型（树），较小的α促使选择较复杂的模型（树）。α=0意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。
可以看出，决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。
树的剪枝算法
输入：生成算法产生的整个树T，参数α；
输出：修剪后的子树Tα
(1)计算每个结点的经验熵
(2)递归地从树的叶结点向上回缩
设一组叶结点回缩到其父结点之前与之后的整体树分别为TB与TA,其对应的损失函数值分别是Cα(TB)与Cα(TA),如果Cα(TA)≤Cα(TB)则进行剪枝，即将父结点变为新的叶结点
(3)返回(2)，直至不能继续为止，得到损失函数最小的子树Tα
5.5 CART算法
分类与回归树(classification and regression tree,CART)模型，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。以下将用于分类与回归的树统称为决策树。
**CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。**CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART算法由以下两步组成：
(1)决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
(2)决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
5.5.1 CART生成
决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼（Gini index）指数最小化准则，进行特征选择，生成二叉树。
1.回归树的生成
最小二乘回归树生成算法：
输入：训练数据集D;
输出：回归树f(x)
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
(1)选择最优切分变量j与切分点s，求解minj,s??minc1∑si∈Ri(j,s)(yi-ci)2+minc2∑xi∈R2(j,s)(yi-c2)2??
遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到最小值的对(j,s)
(2)对选定的对(j,s)划分区域并决定相应的输出值：
R1(j,s)={x|x(j)≤s},R2(j,s)={x|x(j)&s}
c^m=1Nm∑xi∈Rm(j,s)yi,x∈Rm,m=1,2
(3)继续对两个子区域调用步骤(1),(2),直至满足停止条件。
(4)将输入空间划分为M个区域R1,R2,?,RM，生成决策树：
f(x)=∑m=1Mc^mI(x∈Rm)
2.分类树的生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
基尼指数（定义）：分类问题中，假设有K个类，样本点属于第k类的概率为pk,则概率分布的基尼指数定义为：
Gini(p)=∑k=1Kpk(1-pk)=1-∑k=1Kp2k
对于二分类问题，若样本点属于第1个类的概率是p，则概率分布的基尼指数为
Gini(p)=2p(1-p)
对于给定的样本集合D，其基尼指数为
Gini(D)=1-∑k=1K(|Ck||D|)2
这里Ck是D中属于第k类的样本子集，K是类的个数。
如果样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分，即
D1={(x,y)∈D|A(x)=a},D2=D-D1
在特征A的条件下，集合D的基尼指数定义为Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)
基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性就越大，这一点与熵类似。
CART树的生成
输入：训练数据集D
输出：CART决策树
根据训练数据集，从根结点开始，递归地对每个结点进行一下操作，构建二叉决策树：
(1)设结点的训练数据集为D,计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试是“是”或“否”将D分割成D1和D2两部分
(2)在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点，依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中
(3)对两个子结点递归地调用(1),(2),直至满足停止条件
(4)生成CART决策树
算法停止的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。
5.5.2 CART剪枝
CART剪枝算法从“完全生长”的决策树的底端剪去一些子树，使决策树变小（模型变简单），从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成：首先，从生成算法产生的决策树T0底端开始不断剪枝，直到T0的根结点，形成一个子树序列{T0,T1,?,Tn}；然后，通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：18960次
排名：千里之外
原创：58篇
转载：27篇
(2)(9)(12)(16)(8)(21)(1)(4)(4)(1)(1)(1)(2)(3)