3.系统学习-熵与决策树
前言本章，我们将从信息学的知识开始，学习决策树（一种基于划分的非线性模型），决策树算法基于不同的分裂准则（ID3、C4.5、CART）有多种变体，本章需要理解不同决策树分裂差异及优势劣势，并使用sklearn内置决策树模型进行建模，观察模型表现，调节模型参数提升模型性能。
学习目标：
[*]学习信息增益、信息增益率等概念及决策树算法发展过程及优劣势
[*]在Kaggle 泰坦尼克角逐使用 sklearn.tree.DecisionTreeClassifier 进行建模，查看官方文档，了解max_depth 、 min_samples_split 参数含义，调节参数，提交需大0.765使用决策树建模流程与之前学习的线性回归、逻辑回归并没有本质区别，模可以通过from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor进行导入.
1.从数学开始
信息量(Information Content / Shannon information)
有个人告诉你说，他有一个巨大的秘密。
你很好奇，问道：什么秘密？
他答：明天太阳将从东方升起。
信赖你的第一反映是，这个人不是刚从精神病院跑出来的吧？
为什么你会有如许的反映呢？ 因为太阳从东方升起是一个确定事件，不需要别人告诉你，你也可以非常准确的
预测，他所谓的大秘密，不包罗任何信息量。
如果需要我们用非常量化的方式来定义信息怎么办？我们从几个显而易见的角度来看看，信息量我们用I表示：
[*]显然，一个事变如果必然发生，那么告知的消息蕴含的信息量为0.
[*]当一个发生概率极低事变发生，那么告知你的消息蕴含的信息量将非常大，好比有个人告诉你明天彩票中奖号码，而且还真的就是那个号码.
[*]信息量与事变发生的概率负相干.
[*]信息量是非负的，最低为0.
[*]两个独立事件发生的概率为 p(x1) ∗ p(x2),其消息的信息量应该满足
I(x1,x2) = I(x1) + I(x2)，可以看到，概率是乘法，但是信息量应该是加法，两个信息一起告诉你的信息量理所应当等于连个信息的信息量综合。
信息量是关于事件发生概率的函数，I(x) = −log(p(x))函数完美的符合上述论述：
[*]log(1) = 0
[*]当概率 极低时候， − log ( p ) - \log(p) −log(p)极大
[*]‑log ( p)与 p简直负相干
[*]由于0<= p <=1， 所以 − log ( p ) - \log(p) −log(p)一定是非负的
[*]-log(p1 ∗ p2) = −log(p1) −log(p2)
我们可以把不同概率对应的信息量画出来观察一下：
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
probabilities = np.arange(0, 1, 0.01)
I = np.log(probabilities)
plt.plot(probabilities, I)
plt.xlabel("probabilities")
plt.ylabel("Information Content")
https://i-blog.csdnimg.cn/direct/675eb5f9492b47d791b726c8d22e05e1.png
信息熵(Information Entropy)
理解了信息量，信息熵就很简朴了，一个随机事件有多种发生的可能（太阳从东方升起大概从西方升起），所有可能环境的信息量的期望，就是信息熵： H ( x ) = ∑ i = 1 m p ( x i ) I ( x i ) H(x) = \sum_{i=1}^m p(x_i) I(x_i) H(x)=i=1∑mp(xi)I(xi)
这里通过一个例子来理解信息熵,根据以往的气候,温度,湿度,有风的环境下统计了出去玩和不出去玩的环境如下:
weathertemperathumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnormalFALSEyesrainycoolnormalTRUEnoovercastcoolnormalTRUEyessunnymildhighFALSEnosunnycoolnormalFALSEyesrainymildnormalFALSEyessunnymildnormalTRUEyesovercastmildhighTRUEyesovercasthotnormalFALSEyesrainymildhighTRUEno 由表格信息知道根据没有任何提示的环境下可以知道这一天玩的概率为9/14，不出去的概率为5/14,通过信息熵的公式得:
H ( x ) = − 9 14 log 2 9 14 − 5 14 log 2 5 14 = 0.940. H(x) = -\frac{9}{14} \log_2 \frac{9}{14} - \frac{5}{14} \log_2 \frac{5}{14} = 0.940 . H(x)=−149log2149−145log2145=0.940.
但如果14天中13天都出去玩,只有一天不出去玩则对应的信息熵为:
H ( x ) = − 13 14 log 2 13 14 − 1 14 log 2 1 14 = 0.371. H(x) = -\frac{13}{14} \log_2 \frac{13}{14} - \frac{1}{14} \log_2 \frac{1}{14} = 0.371 . H(x)=−1413log21413−141log2141=0.371.
条件熵
信息熵是思量该随机变量的所有可能取值，即所有可能发生事件所带来的信息量的期望。公式如下：
H ( x ) = ∑ i = 1 m p ( x i ) I ( x i ) H(x) = \sum_{i=1}^m p(x_i) I(x_i) H(x)=i=1∑mp(xi)I(xi)
我们的条件熵的定义是：定义为X给定条件下，Y的条件概率分布的熵对X的数学期望,这个照旧比较抽象，下面我们解释一下：设有随机变量（X ,Y），其联合概率分布为: p ( X = x i , Y = y i ) = p i j , i = 1 , 2 , … , n ; j = 1 , 2 , … , m p(X = x_i, Y = y_i) = p_{ij}, \; i = 1, 2, \dots, n; \; j = 1, 2, \dots, m p(X=xi,Y=yi)=pij,i=1,2,…,n;j=1,2,…,m
条件熵H（Y|X）表示在已知随机变量X的条件下随机变量Y的不确定性,条件熵的公式如下：
H ( Y ∣ X ) = ∑ x ∈ X p ( x ) H ( Y ∣ X = x ) H(Y|X) = \sum_{x \in X} p(x) H(Y|X = x) H(Y∣X)=x∈X∑p(x)H(Y∣X=x)
当我们通过气候划分时:当前统计效果中sunny、overcast、rainy的概率分别为：5/14、4/14、5/14 在sunny时玩得概率为2/5 ,对应的信息熵为:
H ( play ∣ weather = sunny ) = − 2 5 log 2 2 5 − 3 5 log 2 3 5 = 0.971 H(\text{play}|\text{weather} = \text{sunny}) = -\frac{2}{5} \log_2 \frac{2}{5} - \frac{3}{5} \log_2 \frac{3}{5} = 0.971 H(play∣weather=sunny)=−52log252−53log253=0.971
overcast时玩的概率为1,对应的信息熵为:
H ( play ∣ weather = overcast ) = 0 H(\text{play}|\text{weather} = \text{overcast}) = 0 H(play∣weather=overcast)=0
rainy时玩的概率为3/5,对应的信息熵为:
H ( play ∣ weather = rainy ) = − 3 5 log 2 3 5 − 2 5 log 2 2 5 = 0.971 H(\text{play}|\text{weather} = \text{rainy}) = -\frac{3}{5}\log_2\frac{3}{5} - \frac{2}{5}\log_2\frac{2}{5} = 0.971 H(play∣weather=rainy)=−53log253−52log252=0.971
有了上面的铺垫之后，我们终于可以盘算我们的条件熵了，我们现在需要求： H（Y|X = weather） 也就是说，我们想要求出当已知气候的条件下的条件熵。 根据公式我们可以知道，已知气候下的条件熵为：
H ( play ∣ weather ) = 5 14 ⋅ 0.971 + 4 14 ⋅ 0 + 5 14 ⋅ 0.971 = 0.693 H(\text{play}|\text{weather}) = \frac{5}{14} \cdot 0.971 + \frac{4}{14} \cdot 0 + \frac{5}{14} \cdot 0.971 = 0.693 H(play∣weather)=145⋅0.971+144⋅0+145⋅0.971=0.693
条件熵总结
实在条件熵意思是按一个新的变量的每个值对原变量进行分类，好比上面这个题把玩与不玩按气候分成了三类。
然后在每一个小类里面，都盘算一个信息熵，然后每一个信息熵乘以各个种别的概率，然后求和。 我们用另一个变量对原变量分类后，因为新增了X的信息原变量的不确定性就会减小了 。
信息增益
我们前面说了，信息熵是代表随机变量的不确定度，条件熵代表在某一个条件下，随机变量的不确定度。 信息增益是：信息熵‑条件熵。 换句话说，信息增益代表了在一个条件下，信息不确定性减少的程度。通过信息熵和条件熵的例子,可以求得随机变量play的信息熵为：
H ( play ) = 0.940 H(\text{play}) = 0.940 H(play)=0.940 H ( play ∣ weather ) = 0.693 H(\text{play}|\text{weather}) = 0.693 H(play∣weather)=0.693
那么我们知道信息熵与条件熵相减就是我们的信息增益，为
Gain ( weather ) = 0.940 − 0.693 = 0.247 \text{Gain}(\text{weather}) = 0.940 - 0.693 = 0.247 Gain(weather)=0.940−0.693=0.247
结论
我们可以看出，如果什么都不知道的话，出去玩的不确定性有0.940。当我们知道气候的信息后，不确定度减少了0.247.也就是说，气候这个信息对于出去玩和不出去玩有一定的判断作用，这也就是决策树的原理，通过树
的分叉创造各种条件，得到信息增益，低落目标的不确定度。
决策树认识
算法思想
决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）,每一次分叉代表对某个特征属性的一次划分。预测效果为叶子节点（没有子节点的节点）所有样本标签的平均值（回归问题）或样本最多的标签种别概
率（分类问题）。
下图展示了一个分类问题（好瓜、坏瓜分类）的决策树案例，在根节点处，根据纹理属于清晰、模糊、稍糊进行划分，然后再一次根据其他属性进行划分。终极在叶子节点统计属于该节点中的样本好瓜坏瓜的比例，将比例最高的种别作为预测效果，最高种别数量的占比作为预测概率值。
https://i-blog.csdnimg.cn/direct/1612166301ad450bb9038bf24ae8dd28.png
2.基于信息增益的ID3决策树
决策树ID3算法的信息论根本
ID3是一种基于信息增益的分裂策略。在前面数学知识学习过程中，我们提到度量了Y的不确定性，条件熵H ( Y|X )度量了我们在知道X以后Y剩下的不确定性，已经条件X带来的信息增益GAIN=H(Y)−H(Y|X)。ID3算法就是用信息增益来判断，选择当前信息增益最大的特征及对应的分裂点。ID3是多叉树，且只能处理种别型（离散）特征，每次基于最大化信息增益GAIN选择分裂特征，特征有几个不同的种别，就会形成多少个分叉。
决策树ID3算法的思路
上面提到ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用盘算出的信息增益最大的特征来建立决策树的当前节点。这里我们举一个信息增益盘算的具体的例子。好比我们有15个样本D，标签
为0大概1。此中有9个输出为1， 6个输出为0。 样本中有个特征A，取值为A1，A2和A3。在取值为A1的样本的输出中，有3个输出为1， 2个输出为0，取值为A2的样本输出中,2个输出为1 ,3个输出为0， 在取值为A3的样本中，4个输出为1，1个输出为0.
样本D的熵为：
H ( D ) = − ( 9 15 log 2 9 15 + 6 15 log 2 6 15 ) = 0.971 H(D) = -\left(\frac{9}{15}\log_2\frac{9}{15} + \frac{6}{15}\log_2\frac{6}{15}\right) = 0.971 H(D)=−(159log2159+156log2156)=0.971
样本D在特征下的条件熵为：
H ( D ∣ A ) = − 5 15 ( 3 5 log 2 3 5 + 2 5 log 2 2 5 ) − 5 15 ( 2 5 log 2 2 5 + 3 5 log 2 3 5 ) − 5 15 ( 4 5 log 2 4 5 + 1 5 log 2 1 5 ) = 0.888 H(D|A) = -\frac{5}{15}\left(\frac{3}{5}\log_2\frac{3}{5} + \frac{2}{5}\log_2\frac{2}{5}\right) - \frac{5}{15}\left(\frac{2}{5}\log_2\frac{2}{5} + \frac{3}{5}\log_2\frac{3}{5}\right) - \frac{5}{15}\left(\frac{4}{5}\log_2\frac{4}{5} + \frac{1}{5}\log_2\frac{1}{5}\right) = 0.888 H(D∣A)=−155(53log253+52log252)−155(52log252+53log253)−155(54log254+51log251)=0.888
对应的信息增益为 G A I N ( D , A ) = H ( D ) − H ( D ∣ A ) = 0.083 GAIN(D,A) = H(D)−H(D|A) =0.083 GAIN(D,A)=H(D)−H(D∣A)=0.083
ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法接纳自顶向下
的贪心搜索遍历可能的决策树空间。 其大致步骤为：
[*]初始化特征集合和数据集合；
[*]盘算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点进行分裂；
[*]删除上一步使用的特征，在分裂后的每个节点上，执行第2步，直到该节点盘算的信息增益小于某个阈值ϵ,则该节点停止分裂；
[*]所有节点停止分裂后，盘算叶子节点（无子节点的节点）样本属于各个种别的概率。
在预测时，根据样本属性将样本归属到某个叶子节点，使用叶子节点各个种别的概率作为预测效果。
决策树ID3算法的不足
ID3算法固然提出了新思路，但是照旧有很多值得改进的地方。
[*]ID3没有思量一连特征，好比长度，密度都是一连值，无法在ID3运用。这大大限定了ID3的用途。
[*]ID3接纳信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比
取值少的特征信息增益大。好比一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，实在他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。
[*]ID3算法对于缺失值的环境没有做思量
[*]只通过阈值ϵ一个参数来控制过拟合
3.C4.5决策树算法
C4.5决策树算法的介绍
上一节我们讲到ID3算法有四个主要的不足，
[*]不能处理一连特征，
[*]信息增益作为标准容易偏向于取值较多的特征，
[*]缺失值处理的问
[*]过拟合问题。 昆兰在C4.5算法中改进了上述4个问题。
[*]对于第一个问题，不能处理一连特征，C4.5 的思路是将一连的特征离散化。比方， m m m 个样本的一连特征 A A A 有 m m m 个，从小到大排列为 a 1 , a 2 , … , a m a_1, a_2, \dots, a_m a1,a2,…,am，则 C4.5 取相邻样本值的平均数，一共取得 m − 1 m-1 m−1 个划分点，此中第 i i i 个划分点 T i T_i Ti 表示为 T i = a i + a i + 1 2 T_i = \frac{a_i + a_{i+1}}{2} Ti=2ai+ai+1。对于这 m − 1 m-1 m−1 个点，分别盘算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该一连特征的二元离散分类点。比方，取到的增益最大的点为 a t a_t at，则小于 a t a_t at 的值为种别 1，大于 a t a_t at 的值为种别 2，如许我们就做到了一连特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为一连属性，则该属性后面还可以到场子节点的产生选择过程。
[*]第二个问题，信息增益作为标准容易偏向于取值较多的特征的问题。作者引入一个信息增益比的变量 I R ( X , Y ) IR(X, Y) IR(X,Y)，它是信息增益和特征熵的比值。表达式如下：
I R ( D , A ) = I ( D , A ) H A ( D ) IR(D, A) = \frac{I(D, A)}{H_A(D)} IR(D,A)=HA(D)I(D,A)
此中 D D D 为样本特征输出的集合， A A A 为样本特征，对于特征熵 H A ( D ) H_A(D) HA(D)，表达式如下：
H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ log 2 ∣ D i ∣ ∣ D ∣ H_A(D) = -\sum_{i=1}^n \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|} HA(D)=−i=1∑n∣D∣∣Di∣log2∣D∣∣Di∣
此中 n n n 为特征 A A A 的种别数， D i D_i Di 为特征 A A A 的第 i i i 个取值对应的样本个数， ∣ D ∣ |D| ∣D∣ 为样本总个数。特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多特征的问题。
[*] 第三个缺失值处理的问题，主要需要办理的是两个问题：
一：是在样本某些特征缺失的环境下选择划分的属性，
二：是选定了划分属性，对于在该属性上缺失特征的样本的处理。
对于第一个子问题，对于某一个有缺失特征值的特征 A。C4.5 的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为 1），然后划分数据，一部分是有特征值 A 的数据集 D1，另一部分是没有特征 A 的数据集 D2。然后对于没有缺失特征 A 的数据集 D1 来对对应的 A 特征的各个特征值一起盘算加权重后的信息增益比，末了乘上一个系数，这个系数是无特征 A 缺失的样本加权后所占权总样本的比例。
对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。好比缺失特征 A 的样本 a 之前权重为 1，特征 A 有 3 个特征值 A1, A2, A3。3 个特征值对应的无缺失 A 特征的样本个数为 2, 3, 4，则 a 同时划分入 A1, A2, A3。对应权重调整为 2/9, 3/9, 4/9。
[*] 第四个问题，C4.5 引入了正则化系数进行初步的剪枝。具体方法这里不讨论。
除了上面的 4 点，C4.5 和 ID3 的思路区别不大。
决策树C4.5算法的不足与思考
C4.5 固然改进大概改善了 ID3 算法的几个主要的问题，仍旧有优化的空间：
[*] 依然非常容易过拟合
C4.5 的模型复杂度较高，容易在训练数据上表现出色，但在测试数据上表现较差。
[*] C4.5 天生的是多叉树
即一个父节点可以有多个子节点。很多时候，在盘算机中二叉树模型会比多叉树运算效率高。如果接纳二叉树，可以提高效率。
[*] C4.5 只能用于分类
如果能将决策树用于回归的话，可以扩大它的使用范围。
[*] C4.5 由于使用了熵模型
内里有大量的耗时的对数运算，如果是一连值还会有大量的排序运算。如果能够加以模型简化可以减少运算强度，但又不捐躯太多准确性的话，那就更好了。
4. CART 树
基尼指数（基尼不纯度）
绝大部分环境下熵（entropy）和基尼指数（Gini Index）在决策树节点分裂时做出的决策都是等价的。那为何存在两种常用算法呢？实在是因为一种使用了熵，另一种使用了基尼指数。两个工具都有很高的开创性，因此都被保存下来了。
先看一下怎样定义节点分裂时的不纯度函数（impurity），有三种（假设有 k k k 种别）：
[*] 误分率：
把当前节点 n n n 下所有样本划分为 c c c 类的误分率，也就是：
1 − max c ∈ [ 1 , k ] c n 1 - \max_{c \in } \frac{c}{n} 1−c∈maxnc
[*] 熵：
H ( x ) = − ∑ i = 1 m p ( x i ) log p ( x i ) H(x) = -\sum_{i=1}^m p(x_i) \log p(x_i) H(x)=−i=1∑mp(xi)logp(xi)
此中， p ( x i ) p(x_i) p(xi) 代表了当前节点 n n n 中属于 c c c 类的比例。
[*] 基尼指数：
G i n i ( a ) = ∑ c = 1 k p ( x i ) ⋅ ( 1 − p ( x i ) ) Gini(a) = \sum_{c=1}^k p(x_i) \cdot (1 - p(x_i)) Gini(a)=c=1∑kp(xi)⋅(1−p(xi))
不丢脸出，三个函数均为凸函数（convex function），只不过误分率（函数 1）是分段线性函数（piece-wise linear），有时候节点分裂会无法低落不纯度。所以函数 2 和 3 一般是常接纳的手段，它们的优势如下：
[*] 二者均为凸函数。
[*] 二者都可以微分，所以便于数值盘算。
[*] 二者都可以代表的函数 1 的偏差上界（upper bound）。正因为它们都是光滑凸函数且为训练误分函数的错误上界，所以不仅包管了每次节点分裂团体的不纯度函数会下降且更得当运算。在绝大部分环境下，二者都是等价的。
如果非要说不同的话，就是熵的盘算会需要求 log，所以可能预算法开销更大。但是求 log 是防止盘算溢出的利器，特殊得当用于处理极小概率的环境，所以并非只有缺点。基尼指数是信息熵的一个泰勒展开。
CART 分类树算法的最优特征选择方法
我们知道，在 ID3 算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在 C4.5 算法中，接纳了信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是 ID3 照旧 C4.5，都是基于信息论的熵模型构建，这里都会涉及大量的对数运算，既不能简化模型同时也不至于完全丢失熵模型的优点。
CART 分类树算法使用基尼系数来取代信息增益或信息增益比。基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益越大是相反的。具体的，在分类问题中，假设有 K K K 个种别，第 k k k 个种别的概率为 p k p_k pk，则基尼系数的表达式为：
G i n i ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(p) = \sum_{k=1}^K p_k(1 - p_k) = 1 - \sum_{k=1}^K p_k^2 Gini(p)=k=1∑Kpk(1−pk)=1−k=1∑Kpk2
如果是二类分类问题，如果属于第一个样本输出的概率是 p p p，则基尼系数的表达式为：
G i n i ( p ) = 2 p ( 1 − p ) Gini(p) = 2p(1 - p) Gini(p)=2p(1−p)
对于一个给定的样本 D D D，假设有 K K K 个种别，第 k k k 个种别的数量为 C k C_k Ck，则样本 D D D 的基尼系数表达式为：
G i n i ( D ) = 1 − ∑ k = 1 K ( C k ∣ D ∣ ) 2 Gini(D) = 1 - \sum_{k=1}^K \left(\frac{C_k}{|D|}\right)^2 Gini(D)=1−k=1∑K(∣D∣Ck)2
特殊的，对于样本 D D D，如果根据特征 A A A 的某个值，把 D D D 分成 D 1 D_1 D1 和 D 2 D_2 D2 两部分，则在特征 A A A 的条件下， D D D 的基尼系数表达式为：
G i n i ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) Gini(D, A) = \frac{|D_1|}{|D|} Gini(D_1) + \frac{|D_2|}{|D|} Gini(D_2) Gini(D,A)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)
可以比较下基尼系数表达式和熵模型的表达式，二次运算比对数运算简朴很多。尤其是二类分类的盘算，更加简朴。但是和熵模型的度量方式相比，基尼系数对预测的偏差有多大呢？对于二类分类，基尼系数和熵之间的曲线如下：
https://i-blog.csdnimg.cn/direct/bba10b2638d34fbba95c36dba800e6ba.png
从上图可以看出，基尼系数和熵之半的曲线非常接近，仅仅在45度角附近偏差稍大。因此，基尼系数可以做为熵模型的一个近似替代。而CART分类树算法就是使用的基尼系数来选择决策树的特征。同时，为了进一步简化，CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，如许CART分类树算法建立起来的是二叉树，而不是多叉树。如许一可以进一步简化基尼系数的盘算，二可以建立一个更加优雅的二叉树模型。
CART 分类树算法对于一连特征和离散特征处理的改进
对于 CART 分类树一连值的处理问题，其思想和 C4.5 是相同的，都是将一连的特征离散化。唯一的区别在于在选择划分点时的度量方式不同，C4.5 使用的是信息增益比，而 CART 分类树使用的是基尼系数。具体的思路如下：
好比某个样本的一连特征 a a a 有 m m m 个，从小到大排列为 a 1 , a 2 , . . . , a m a_1, a_2, ..., a_m a1,a2,...,am，则 CART 算法取相邻两样本值的平均数，一共取得 m − 1 m-1 m−1 个划分点，此中第 i i i 个划分点 T i T_i Ti 表示为：
T i = a i + a i + 1 2 T_i = \frac{a_i + a_{i+1}}{2} Ti=2ai+ai+1
对于这 m − 1 m-1 m−1 个点，分别盘算以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为该一连特征的二元离散分种别点。好比取到的基尼系数最小的点为 a t a_t at，则小于 a t a_t at 的值为种别 1，大于 a t a_t at 的值为种别 2，如许我们就做到了一连特征的离散化。
需要注意的是，与 ID3 或 C4.5 处理离散属性不同的是，如果当前节点为一连属性，则该属性后面还可以到场子节点的产生选择过程。
对于 CART 分类树离散值的处理问题，接纳的思路是不停的二分离散特征。对于 ID3 大概 C4.5，如果某个特征 A A A 被选取建立决策树节点，如果它有 A 1 , A 2 , A 3 A1, A2, A3 A1,A2,A3 三种种别，我们会在决策树上一下建立一个三叉的节点。如许导致决策树是多叉树。但是 CART 分类树使用的方法不同，它接纳的是不停的二分。
比方：CART 分类树会思量把 A 分成 {A1} 和 {A2, A3}，{A2} 和 {A1, A3}，{A3} 和 {A1, A2} 三种环境，找到基尼系数最小的组合，好比 {A2} 和 {A1, A3}，然后建立二叉树节点，一个节点是 A2 对应的样本，另一个节点是 {A1, A3} 对应的节点。
同时，由于这次没有把特征 A 的取值完全分开，后面我们还会在子节点中继承选择特征 A 来划分 A1 和 A3。这和 ID3 大概 C4.5 不同，在 ID3 大概 C4.5 的一棵子树中，离散特征只会到场一次节点的建立。
CART 分类树算法的具体流程
上面介绍了 CART 算法的一些和 C4.5 不同之处，算法输入是训练集 D D D，基尼系数的阈值，样本个数阈值。输出是决策树 T T T。我们的算法从根节点开始，用训练集递归地建立 CART 树。
[*] 对于当前节点的数据集为 D D D，如果样本个数小于阈值大概没有特征，则返回决策子树，当前节点停止递归。
[*] 盘算样本集 D D D 的基尼系数，如果基尼系数小于阈值，则返回决策子树，当前节点停止递归。
[*] 盘算当前节点现有的各个特征的各个特征值对数据集 D D D 的基尼系数。缺失值的处理方法和 C4.5 算法里描述的相同。
[*] 在盘算出来的各个特征的各个特征值对数据集 D D D 的基尼系数中，选择基尼系数最小的特征 A A A 和对应的特征值：
[*]根据这个最优特征和最优特征值，把数据集划分成两部分 D 1 D_1 D1 和 D 2 D_2 D2，同时建立当前节点的左右子节点，做如下操纵：
[*]左节点的数据集为 D 1 D_1 D1，右节点的数据集为 D 2 D_2 D2。
[*] 对左右的子节点递归调用 1-4 步，天生决策树。对于天生的决策树做预测的时候，假如测试集里的样本 A A A 落到了某个叶子节点，而节点里有多个训练样本，则对于 A A A 的种别预测接纳的是这个叶子节点里概率最大的种别。
CART 回归树算法
CART 回归树和 CART 分类树的算法大部分是类似的，所以这里我们只介绍 CART 回归树和 CART 分类树的建立算法不同的地方。首先，我们要知道什么是回归树，什么是分类树。两者的区别在于样本输出，如果样本输出是离散值，那么这是一颗分类树。如果样本输出是一连值，那么这是一颗回归树。
除了概念的不同，CART 回归树和 CART 分类树的建立和预测的区别主要有下面两点：
[*]一连值的处理方法不同
[*]决策树建立后做预测的方式不同
对于一连值的处理，我们知道 CART 分类树接纳的是用基尼系数的大小来度量特征的各个划分点的优劣环境。这比较得当分类模型，但是对于回归模型，我们使用了常见的和方差的度量方式。CART 回归树的度量目标是，对于恣意划分特征 A A A，对应的恣意划分点 s s s 两边划分成的数据集 D 1 D_1 D1 和 D 2 D_2 D2，求出使 D 1 D_1 D1 和 D 2 D_2 D2 各自集合的均方差最小，同时 D 1 D_1 D1 和 D 2 D_2 D2 的均方差之和最小时对应的特征和特征值划分点。表达式为：
min A , s [ min c 1 ∑ x i ∈ D 1 ( A , s ) ( y i − c 1 ) 2 + min c 2 ∑ x i ∈ D 2 ( A , s ) ( y i − c 2 ) 2 ] \min_{A,s} \left[ \min_{c_1} \sum_{x_i \in D_1(A,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in D_2(A,s)} (y_i - c_2)^2 \right] A,smin c1minxi∈D1(A,s)∑(yi−c1)2+c2minxi∈D2(A,s)∑(yi−c2)2
此中， c 1 c_1 c1 为 D 1 D_1 D1 数据集的样本输出均值， c 2 c_2 c2 为 D 2 D_2 D2 数据集的样本输出均值。
对于决策树建立后做预测的方式，上面讲到了 CART 分类树接纳叶子节点概率最大的种别作为当前节点的预测种别。而回归树输出不是种别，它接纳的是用最小叶子节点均值大概叶子节点中位数预测输出效果。除了上面提到的以外，CART 回归树和 CART 分类树的建立算法和预测没有什么区别。
CART算法小结
上面我们对CART算法做了一个详细的介绍，CART算法相比C4.5算法的分类方法，接纳了简化的二叉树模型，同时特征选择接纳了基尼系数来简化盘算。当然CART树最大的好处是还可以做回归模型，这个C4.5没有。下表给出了ID3、C4.5和CART的一个比较总结。
算法支持模型树结构特征选择一连值处理缺失值处理剪枝ID3分类多叉树信息增益不支持不支持不支持C4.5分类多叉树信息增益比支持支持支持CART分类、回归二叉树基尼系数、均方差支持支持支持 CART算法还有什么提升空间？
[*] 无论是ID3、C4.5照旧CART，在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。如许决策得到的决策树更加准确。这个决策树叫做多变量决策树（multi-variate decision tree）。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1，这里不多介绍。
[*] 如果样本发生一点改动，就会导致树结构的剧烈改变。这可以通过集成学习内里的随机丛林之类的方法办理。
决策树算法小结
决策树算法作为一个大种别的分类回归算法的优缺点如下，首先我们来看决策树算法的优点：
[*]简朴直观，天生的决策树很直观。
[*]基本不需要预处理，不需要提前归一化，处理缺失值。
[*]使用决策树预测的代价是 (O(\log 2m))。m 为样本数。
[*]既可以处理离散值也可以处理一连值。很多算法只是专注于离散值大概一连值。
[*]可以处理多维度输出的分类问题。
[*]相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释。
[*]可以交错验证的剪枝来选择模型，从而提高泛化本事。
[*]对于非常点的容错本事好，健壮性高。
决策树算法的缺点：
[*]决策树算法非常容易过拟合，导致泛化本事不强。可以通过设置节点最少样本数量和限定决策树深度来改进。
[*]决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法办理。
[*]寻找最优的决策树是一个 NP 难的问题，我们一般是通过开导式方法，容易陷入局部最优。可以通过集成学习之类的方法来改进。
[*]有些比较复杂的关系，决策树很难学习，好比异或。这种就没有办法了，一般这种关系可以换神经网络分类方法来办理。
[*]如果某些特征的样本比例过大，天生决策树容易偏向于这些特征。这个可以通过调整样本权重来改善。
拓展阅读
链接: 1. 为什么C4.5决策树能处理一连特征，ID3树不能处理一连特征？
链接: 2. 为什么CART能做回归而ID3和C4.5不可以?
链接: 3. 决策树可视化
https://i-blog.csdnimg.cn/direct/eebe3f1202074b968b207433877766ca.png
作业
[*] 回复接纳信息增益、信息增益率作为决策树分裂计谋，有什么区别？
[*] 在 Titanic 角逐数据集中，对年事做对数处理 (np.log(age))，是否会对决策树模型产生影响，为什么？
[*] 如果发生过拟合环境，怎样调整 max_depth 和 min_samples_split 参数？
[*] 在 Kaggle 泰坦尼克角逐 使用 sklearn.tree.DecisionTreeClassifier 进行建模，查看官方文档，相识 max_depth、min_samples_split 参数含义，调节参数，提交需大于 0.765。使用决策树建模流程与之前学习的线性回归、逻辑回归并没有本质区别，模型可以通过 from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor 进行导入。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]