雪绒花英文
决策树学习笔记（DecisionTree）
什么是决策树？
决策树是⼀种基本的分类与回归⽅法。其主要有点事模型具有可得性，分类速度快。学习时，利⽤训练数据，根据损失函数最⼩化原则建⽴决策树模型；预测时，对新数据，利⽤决策树模型进⾏分类。
决策树学习通常包含以下三个步骤：
选择特征
决策树⽣成
剪枝
决策树的改进路线：
embedded ID3--->C4.5--->CART
（1）其中ID3是基于信息增益来选择划分属性
（2）C4.5不直接使⽤增益率来选择划分属性，⽽是使⽤了⼀个启发式：先从候选划分属性中选取信息增益⾼于平局⽔平的属性，再从中选择增益率最⾼的。
（3）CART（Classification and Regression Tree）算法使⽤基尼系数来代替信息增益⽐。
英语哲理文章 信息
这个是熵和信息增益的基础概念，是对⼀个抽象事物的命名，⽆论⽤不⽤‘信息’来命名这种抽象事物，或者⽤其他名称来命名这种抽象事物，这种抽象事物是客观存在的。如果带分类的事物集合可以划分为多个类别当中，则某个类（xi）的信息（量）定义如下：
I(x)⽤来表⽰随机变量的信息，p(xi)指是当xi发⽣时的概率。当事件xi发⽣的概率p(xi)很⼩，但是它却发⽣了，那这个信息量相当⼤，⽐如买彩票中奖了，那么这个信息量肯定是很⼤的。相反，对于⼤概率事件，⼈们习以为常，那么这个事件的信息量就很⼩。这就体现在上述公式中。
信息熵
“信息熵”是度量样本纯度最常⽤的⼀种指标。所谓样本纯度，相反⽽⾔之就是凌乱程度。如⼀个数据集U中的样本都属于同⼀类，那么这时样本纯度最⾼⽽凌乱程度最低。信息熵定义为：
实习医生格蕾第十二季毕业证书翻译 其中D表⽰样本集合，|y|样本中类别的数⽬， pk表⽰第k种分类占集合的⽐例。Ent(D)的值越⼩，D的纯度越⾼。
信息增益
信息增益指的是，使⽤某⼀个属性a进⾏划分后，所带来的纯度提⾼的⼤⼩。⼀般⽽⾔，信息增益越⼤，意味着使⽤属性a来进⾏划分所获得的“纯度提升”越⼤。信息增益定义如下：
即
信息增益 = 根节点的信息熵 - 所有分⽀节点的信息熵的加权和
其中，权值为划分后属性a=ak节点中样本的数量与划分前节点中的样本数量的⽐值，即概率。概率确保了权重的和为1.
上图描述的是，使⽤属性a对样本集合D进⾏划分，因为a有V个取值，因此决策树会有V个分⽀。划分后每⼀个节点中样本的数量为属性a=ak的样本的数量。
问：如何理解：信息增益越⼤，意味着使⽤属性a来进⾏划分所获得的“纯度提升”越⼤?
答：因为Ent(D)的值越⼩，D的纯度越⾼。⽽划分后，所有的分⽀节点的Ent(Dk)的和就是划分后的信息熵，公式体现了前后的差距，如果差距越⼤，那么就说明划分后所有的分⽀节点的信息熵越⼩，纯度提升越⼤。
增益率
背景：当样本集中的某⼀属性取值使得所有样本被分到不同类别，此时分⽀的纯度达到最⾼，⽆需再继续划分。然⽽这样的决策树不具备泛化能⼒。事实上，信息增益准则对可取值较多的属性有所偏好。
为了减少这种偏好可能带来的影响，因此使⽤增益率代替信息增益准则选择划分属性。
即增益率(Gain_ratio(D,a))=信息增益Gain(D,a)/属性固有值(IV(a))。
属性A的可能取值越⼤，固有值IV(a)通常越⼤。
死机英语
信息增益率偏向于可能取值减少的属性。因此C4.5算法不直接使⽤信息增益率来选择划分属性。
基尼值
基尼值 Gini(D) 反映了从数据集中随机抽取两个样本，其类别标记不⼀致的概率。当数据集的纯度越⾼，每次抽到不同类别标记的概率越⼩。打个⽐⽅，在⼀个袋⼦⾥装100个乒乓球，其中有99个⽩球，1个黄球，那么当我们随机抽取两个球的时候，很⼤概率是抽到两个⽩球。
所以数据集D的纯度可以⽤基尼值来度量，其定义如下：
基尼值越⼩，数据集D纯度越⾼。
基尼指数
基尼指数是针对于属性定义的，其反映的是，使⽤属性a进⾏划分后，所有分⽀中（使⽤基尼值度量的）纯度的加权和。
属性a的基尼指数定义如下：
yingyihan
我们在属性集合A中选择划分属性的时候，就选择使得划分后基尼指数最⼩的属性作为最优划分属性。CART就是⽤基尼指数来选择划分属性的。
决策树的剪枝处理
剪枝是决策树学习算法解决过拟合的主要⼿段。在决策树的学习过程中，为了尽可能地正确分类训练样本，节点划分得不断重复，有时候会造成决策树的分⽀过多，这时候就是算法在训练样本上学得太好，导致把训练集本⾝的⼀些特点作为所有数据所有数据都有的⼀般性质（实际上新数据中可能没有这些特点），从⽽导致过拟合。因此可以主动去掉⼀些分⽀来降低过拟合的风险。
决策树的剪枝分为预剪枝和后剪枝。
预剪枝，是指在决策树⽣成过程中，对每个节点在划分前先进⾏估计，若当前的节点划分不能带来决策树泛化的提升，则停⽌划分并将当前节点标记为叶⼦节点。
后剪枝，是指先从训练数据集中⽣成⼀课完整的决策树，然后⾃底向上对⾮叶⼦节点进⾏考察，若将该节点对应的⼦树替换为叶⼦结点能够带来决策树泛化能⼒的提升，则将该节点替换为叶⼦节点。
（注：叶⼦节点的类别指定为训练数据集中数量最⼤的类别）
预剪枝
在某个节点的预剪枝的估计建⽴在已经确定最优划分属性的前提之上，要不要以该属性对当前节点进⾏划分，还得先计算泛化能⼒是否有提⾼。提交
在预剪枝中，泛化能⼒的计算依赖于验证数据集。验证精度的计算是将验证数据集输⼊决策树模型进⾏判别，取正例样本数量与验证集样本数量的⽐值（百分⽐）。划分前验证精度由上⼀步计算给出。泛化能⼒的提⾼与否，要对⽐划分前后验证集的⼤⼩。
预剪枝基于“贪⼼”本质禁⽌这些分⽀的展开，给预剪枝决策树带来⽋拟合的风险。
后剪枝
将验证集输⼊到决策树算法，计算出剪枝前的验证精度。然后，找到最底下的⾮叶⼦结点，（模拟）将其领先的分⽀去除，取其中数量最⼤的分类作为该节点的判别标记。然后计算剪枝后的验证精度。通过对⽐剪枝前后的验证精度，来确定是否需要进⾏剪枝。
剪枝处理总结：
后剪枝决策树通常⽐预剪枝决策树保留更多的分⽀，⼀般情形下，后剪枝决策树的⽋拟合风险⼩，泛化能⼒往往优于预剪枝。但后剪枝决策树训练开销⽐预剪枝⼤得多。
连续值与缺失值
连续值处理
连续属性的可取值数⽬不再有限，因此不能直接根据连续属性可取值来对节点进⾏划分（因为如果以可取值来对数据集进⾏划分，如果在该属性上所有的可取值是不⼀样的，使得划分后纯度达到最⼤，不利于决策树的泛化）。此时可以使⽤连续属性离散化技术。最常⽤的是⼆分法。
给定样本集D合连续属性a，嘉定a在D上出现不同取值，将这些取值从⼩到⼤排序，记为{a1,a2,......,
love paradi歌词an}，基于划分可以将t划分为⼦集Dt-，Dt+, 其中Dt-包含那些属性a取值不⼤于t的样本，Dt+包含取值不⼤于t的样本。显然，对于相邻的属性取值ai和a(i+1)来说，t在半开区间[ai a(i+1)) 中所产⽣的划分结果是相同的。因此，对于连续属性a, 我们可以考虑包含n-1个元素的候选划分点集合
即把区间[ai a(i+1))的中位数(ai+a(i+1))/2作为候选划分点，之后我们就可以像离散属性值⼀样来考察这些划分点，选取划分点进⾏样本集合的划分，例如可以对离散属性的信息增益式⼦稍加改造：
其中，Gain(D,a,t)是样本集D基于划分点⼆分后的信息增益于是我们就可以选择使Gain(D,a,t)最⼤化的划分点。
缺失值
对于数据缺失问题，我们需要解决两个问题：
（1）如何在属性值缺失的情况下进⾏划分属性选择？
（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进⾏划分？ticketed
