机器学习（⼆）基于决策树的分类预测
机器学习（⼆）基于决策树的分类预测决策树是什么？
决策树是⼀种基于预测变量对数据分类的算法。作为预测模型，决策树通过分析预测变量来得到有关⽬标变量的结论。决策树具有类似于流程图的结构，其中每个内部节点是测试属性，并且每个分⽀是测试的结果。在机器学习中，决策树是⼀个预测模型，他代表的是对象属性与对象值之间的⼀种映射关系
决策树是⼀种⼗分常⽤的分类⽅法。他是⼀种监督学习，所谓监督学习就是给定⼀堆样本，每个样本都有⼀组属性和⼀个类别，这些类别是事先确定的，那么通过学习得到⼀个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。
缺点：过拟合。过拟合的意思是什么呢？过渡拟合，在训练集上表现良好，但是在测试集上表现很糟糕，学习能⼒强但是学的太过精细。
对应⽟过拟合的是⽋拟合，⽋拟合的意思是，训练集和测试集的表现都很糟糕，学习能⼒很差。
前⾯⼏个概念是⽐较通⽤的，⼤家都接受的⼀种解释决策树是个什么东西。我理解中的决策树形式上就简单理解成⼀个树结构，有节点有分枝的结构。⽤决策树来做分类预测，通过我写的构造算法，对⼀个表中数据的各个属性进⾏分类，选择⼀个最优的结构树出来（依据什么属性来分类后⾯再说，最优的标
准后⾯也会将到），⽤这个树结构去预测训练集的数据从⽽得到最终预测值。学习⼀种模型，最终⽬的也是为了利⽤这个模型，去解决⼀些问题。先介绍⼏个概念
有⼏个参数，⽤来判断当前步骤或者⾏为”好“”坏“⽤的。尽量去理解吧？不理解也没关系，后⾯⽤着⽤着就习惯了。不纯度
“不纯度”：先举个例⼦，对⼀个班级学⽣分类，如果按照性别分类，⼀半男⼀半⼥，数据⾮常集中，不纯度就低。某⼀类标签的⽐例越⼤，这个节点就越纯。不纯度就越低，分枝就越好……有没有点感觉了，⼀个节点的不纯度⾼低就看这个节点中包含元素的是否存在某种元素的占⽐较⼤。如果特别分散就说不纯度⾼，⽐如班级按照名字分类，分为100个类别，班级节点不存度就⾮常低了。
误差率
t为节点，p(I|t）表⽰给定节点t中属于类别i的样本所占的⽐例。简单理解，1-最⼤样本占⽐；举个例⼦：
班级节点t按照18岁分类，分为⼩于18有10⼈，等于18有1⼈，⼤于18有5⼈，这么三个类别，最⼤⽐例的是⼩于18岁的10⼈也就是 ，那么这个节点的误差率就是 信息熵
ClassficationError =1−max [p (i ∣t )]
=16108583
信息熵（Entropy）也叫“⾹农熵”。就是样本混乱程度或者理解成变量的不确定性，熵越⼤，表明这样本越混乱，或者这个样本越不确定是什么东西，决策树决策的过程就是降低信息熵的过程，让不清晰变得清晰（降的越快越好，决策越好），先来说信息熵的公式：
c表⽰本节点上标签类别的个数（就是有多少个分类），因为P是概率，所以取对数后为负数，故前⾯加⼀个负号（不懂c啊i啊之类的话就直接群后⾯的例⼦去理解其实计算很简单，就是概率乘概率⼤对数）。举个例⼦来说明这个公式怎么计算：⽐如我这个⼩组t有6个⼈，5男1⼥。还是按照性别分类，那么t表⽰我这个⼩组，c=2表⽰有男⼥两种分类，条件熵条件熵以及后⾯的信息增益参考知乎⼀篇⽂章
熵是对事件结果不确定性的度量，但在知道有些条件时，不确定性会变⼩。例如，⼀个⼈是否是艾滋病的阳性，这个事件的不确定性会存着医疗检测结果⽽降低。条件熵衡量的就是在某个条件 X 下，事件 Y 的不确定性，记作 H(Y|X) 。其定义式为
理解为，X 事件每个可能性的结果的熵乘以发⽣概率的求和。
关于条件熵，再以单项选择题来举例⼦。在学霸圈做单项选择题有⼀个秘籍：三长⼀短选最短，三短⼀长选最长。姑且假设学霸的秘籍⼀般都是正确的。
如果在某场考试中，有10%的单项选题是三长⼀短，10%的选题是三短⼀长。计算该考试单项选题的关于长短题的条件熵:
H(三长⼀短)=0bit
H(三短⼀长)=0bit
H(都⼀样长)=2bit
得到结果，条件熵为0.10+0.10+0.8*2=1.6bit。
可见，学霸的秘诀就是好⽤，将信息熵由2bit降为了1.6bit，降幅达到了20%。信息增益（重要概念）
信息增益是知道了某个条件后，事件的不确定性下降的程度。写作 g(X,Y)。它的计算⽅式为信息熵减去条件熵，如下
表⽰的是，知道了某个条件后，原来事件不确定性降低的幅度。在上⾯单项选择的例⼦中，通过了解每个考题的长度信息，可以将信息熵由2bit降为了1.6bit。其中，信息增益就是0.4bit。
信息增益率
-假如某个条件极其严格，⽐如某个同学提前知道了所有选题的答案，那么将选题的序号作为条件，不存在任何不确定性，所以可以得到最⼤的信息增益。但是这个条件是没有意义的，假设⽼师换⼀份考卷答案就全部作废了。
信息增益率在信息增益的基础上增加了惩罚项，惩罚项是特征的固有值，是避免上述情况⽽设计的。
Entropy =−P (i ∣t )log P (i ∣t )i =0∑c −1
2Entropy =−∗61log ()−261∗65log ()=265
0.650H (Y ∣X )=p H (Y ∣X =i =1∑n i x )
i g (X ,Y )=H (Y )−H (Y ∣X )
写作 。定义为信息增益除以特征的固有值，如下
继续以单项选择题为例，通过分析选题的长短特征之后，信息增益g(X,Y)为2bit，惩罚项H（Y）=-0.1log0.1-0.1log0.1-
0.8*log0.8=0.92
信息增益率为0.4/0.92=43%，其中，信息增益率为43%。
Gini 指数
基尼系数表征的也是事件的不确定性，Gini指数计算公式：跟信息增益很像是不是？继续举个例⼦来说明计算过程：还是上⾯例⼦⼩组t有5男1⼥。对性别划分，则
下⾯是基尼指数，信息熵，误差率的对⽐：
构造决策树的⽅式决策树的构建参考知乎⼀篇⽂章
决策树的⽣成主要分以下两步，这两步通常通过学习已经知道分类结果的样本来实现。
1. 节点的分裂：⼀般当⼀个节点所代表的属性⽆法给出判断时，则选择将这⼀节点分成2个⼦节点（如不是⼆叉树的情况会分成
n个⼦节点）
2. 阈值的确定：选择适当的阈值使得分类错误率最⼩ （Training Error）。
⽐较常⽤的决策树有ID3，C4.5和CART（Classification And Regression Tree），CART的分类效果⼀般优于其他决策树
ID3
g (X ,Y )r g (X ,Y )=r H (Y )
g (X ,Y )
Gini =P (i ∣t )(1−i =0∑c −1P (i ∣t ))=1−[P (i ∣t )]i =0∑c −1
2Gini =1−()−612()=6520.5
由信息熵（Entropy）原理来决定那个做⽗节点，那个节点需要分裂。对于⼀组数据，熵越⼩说明分类结果越好。在选取⽗节点的时候也是跟觉这个熵的⼤⼩来分类的：。熵取值在[0,1]之间。越⼩越准确。举个例⼦：学⽣很多属性，根据这额属性划分好学⽣和坏学⽣（已知分类结果的监督学习）。
直观分类如下，通过学习上表的数据，可以设置A，B，C，D，E的具体值，⽽A，B，C，D，E则称为阈值：
熵的不断最⼩化，实际上就是提⾼分类正确率的过程。
⽐如上表中的4个属性：单⼀地通过以下语句分类：
1. 分数⼩于70为【不是好学⽣】：分错1个
2. 出勤率⼤于70为【好学⽣】：分错3个
3. 问题回答次数⼤于9为【好学⽣】：分错2个
4. 作业提交率⼤于80%为【好学⽣】：分错2个
最后发现 分数⼩于70为【不是好学⽣】这条分错最少，也就是熵最⼩，所以应该选择这条为⽗节点进⾏树的⽣成，当然分数也可以选择⼤于71，⼤于72等等，出勤率也可以选择⼩于60，65等等，总之会有很多类似上述1~4的条件，最后选择分类错最少即熵最⼩的那个条件。⽽当分裂⽗节点时道理也⼀
样，分裂有很多选择，针对每⼀个选择，与分裂前的分类错误率⽐较，留下那个提⾼最⼤的选择，即熵减最⼤的选择。
C4.5
通过对ID3的学习，可以知道ID3存在⼀个问题，那就是越细⼩的分割分类错误率越⼩，所以ID3会越分越细，⽐如以第⼀个属性为例：设阈值⼩于70可将样本分为2组，但是分错了1个。如果设阈值⼩于70，再加上阈值等于95，那么分错率降到了0，但是这种分割显然只对训练数据有⽤，对于新的数据没有意义，这就是所说的过度学习（Overfitting）。
分割太细了，训练数据的分类可以达到0错误率，但是因为新的数据和训练数据不同，所以⾯对新的数据分错率反倒上升了。决策树是通过分析训练数据，得到数据的统计信息，⽽不是专为训练数据量⾝定做。
就⽐如给男⼈做⾐服，叫来10个⼈做参考，做出⼀件10个⼈都能穿的⾐服，然后叫来另外5个和前⾯10个⼈⾝⾼差不多的，这件⾐服也能穿。但是当你为10个⼈每⼈做⼀件正好合⾝的⾐服，那么这10件⾐服除了那个量⾝定做的⼈，别⼈都穿不了。
所以为了避免分割太细，c4.5对ID3进⾏了改进，C4.5中，优化项要除以分割太细的代价，这个⽐值叫做信息增益率，显然分割太细分母增加，信息增益率会降低。除此之外，其他的原理和ID3相同。
CART
分类回归树
CART是⼀个⼆叉树，也是回归树，同时也是分类树，CART的构成简单明了。
CART只能将⼀个⽗节点分为2个⼦节点。CART⽤GINI指数来决定如何分裂：
GINI指数：总体内包含的类别越杂乱，GINI指数就越⼤（跟熵的概念很相似）。
a. ⽐如出勤率⼤于70%这个条件将训练数据分成两组：⼤于70%⾥⾯有两类：【好学⽣】和【不是好学⽣】，⽽⼩于等于70%⾥也有两类：【好学⽣】和【不是好学⽣】。
b. 如果⽤分数⼩于70分来分：则⼩于70分只有【不是好学⽣】⼀类，⽽⼤于等于70分有【好学⽣】和【不是好学⽣】两类。
⽐较a和b，发现b的凌乱程度⽐a要⼩，即GINI指数b⽐a⼩，所以选择b的⽅案。以此为例，将所有条件列出来，选择GINI指数最⼩的⽅案，这个和熵的概念很类似。
CART还是⼀个回归树，回归解析⽤来决定分布是否终⽌。理想地说每⼀个叶节点⾥都只有⼀个类别
时分类应该停⽌，但是很多数据并不容易完全划分，或者完全划分需要很多次分裂，必然造成很长的运⾏时间，所以CART可以对每个叶节点⾥的数据分析其均值⽅差，当⽅差⼩于⼀定值可以终⽌分裂，以换取计算成本的降低。
CART和ID3⼀样，存在偏向细⼩分割，即过度学习（过度拟合的问题），为了解决这⼀问题，对特别长的树进⾏剪枝处理，直接剪掉。以上的决策树训练的时候，⼀般会采取Cross-Validation法：⽐如⼀共有10组数据：
第⼀次. 1到9做训练数据， 10做测试数据
第⼆次. 2到10做训练数据，1做测试数据
第三次. 1，3到10做训练数据，2做测试数据，以此类推
做10次，然后⼤平均错误率。这样称为 10 folds Cross-Validation。
⽐如 3 folds Cross-Validation 指的是数据分3份，2份做训练，1份做测试。
⼩结⼀下
关于上⾯构造决策树多⽅法的介绍有⼀个描述更加详细的⽂章
