手机端网站怎么制作,做暧嗳xo小视频网站,云南网络公司哪家好,wordpress 种子插件熵与决策树 前言1.从数学开始信息量(Information Content / Shannon information)信息熵(Information Entropy)条件熵信息增益 决策树认识2.基于信息增益的ID3决策树3.C4.5决策树算法C4.5决策树算法的介绍决策树C4.5算法的不足与思考 4. CART 树基尼指数#xff08;基尼不纯度… 熵与决策树 前言1.从数学开始信息量(Information Content / Shannon information)信息熵(Information Entropy)条件熵信息增益 决策树认识2.基于信息增益的ID3决策树3.C4.5决策树算法C4.5决策树算法的介绍决策树C4.5算法的不足与思考 4. CART 树基尼指数基尼不纯度CART 分类树算法的最优特征选择方法CART 分类树算法对于连续特征和离散特征处理的改进CART 分类树算法的具体流程CART 回归树算法CART算法小结 决策树算法小结决策树算法的缺点 拓展阅读作业 前言
本章我们将从信息学的知识开始学习决策树一种基于划分的非线性模型决策树算法基于不同的分裂准则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) 信息熵(Information Entropy)
理解了信息量信息熵就很简单了一个随机事件有多种发生的可能太阳从东方升起或者从西方升起所有可能情况的信息量的期望就是信息熵 H ( x ) ∑ i 1 m p ( x i ) I ( x i ) H(x) \sum_{i1}^m p(x_i) I(x_i) H(x)i1∑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−145log21450.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−141log21410.371.
条件熵
信息熵是考虑该随机变量的所有可能取值即所有可能发生事件所带来的信息量的期望。公式如下 H ( x ) ∑ i 1 m p ( x i ) I ( x i ) H(x) \sum_{i1}^m p(x_i) I(x_i) H(x)i1∑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(Xxi,Yyi)pij,i1,2,…,n;j1,2,…,m 条件熵HY|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∣Xx) 当我们通过天气划分时:当前统计结果中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∣weathersunny)−52log252−53log2530.971 overcast时玩的概率为1,对应的信息熵为: H ( play ∣ weather overcast ) 0 H(\text{play}|\text{weather} \text{overcast}) 0 H(play∣weatherovercast)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∣weatherrainy)−53log253−52log2520.971
有了上面的铺垫之后我们终于可以计算我们的条件熵了我们现在需要求 HY|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.971144⋅0145⋅0.9710.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.6930.247 结论 我们可以看出如果什么都不知道的话出去玩的不确定性有0.940。当我们知道天气的信息后不确定度减少了0.247.也就是说天气这个信息对于出去玩和不出去玩有一定的判断作用这也就是决策树的原理通过树 的分叉创造各种条件获得信息增益降低目标的不确定度。 决策树认识
算法思想 决策树decision tree是一个树结构可以是二叉树或非二叉树,每一次分叉代表对某个特征属性的一次划分。预测结果为叶子节点没有子节点的节点所有样本标签的平均值回归问题或样本最多的标签类别概 率分类问题。 下图展示了一个分类问题好瓜、坏瓜分类的决策树案例在根节点处根据纹理属于清晰、模糊、稍糊进行划分然后再一次根据其他属性进行划分。最终在叶子节点统计属于该节点中的样本好瓜坏瓜的比例将比例最高的类别作为预测结果最高类别数量的占比作为预测概率值。
2.基于信息增益的ID3决策树 决策树ID3算法的信息论基础 ID3是一种基于信息增益的分裂策略。在前面数学知识学习过程中我们提到度量了Y的不确定性条件熵H ( Y|X )度量了我们在知道X以后Y剩下的不确定性已经条件X带来的信息增益GAINH(Y)−H(Y|X)。ID3算法就是用信息增益来判断选择当前信息增益最大的特征及对应的分裂点。ID3是多叉树且只能处理类别型离散特征每次基于最大化信息增益GAIN选择分裂特征特征有几个不同的类别就会形成多少个分叉。 决策树ID3算法的思路 上面提到ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树用计算出的信息增益最大的特征来建立决策树的当前节点。这里我们举一个信息增益计算的具体的例子。比如我们有15个样本D标签 为0或者1。其中有9个输出为1 6个输出为0。 样本中有个特征A取值为A1A2和A3。在取值为A1的样本的输出中有3个输出为1 2个输出为0取值为A2的样本输出中,2个输出为1 ,3个输出为0 在取值为A3的样本中4个输出为11个输出为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)−(159log2159156log2156)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(53log25352log252)−155(52log25253log253)−155(54log25451log251)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_{i1}}{2} Ti2aiai1。对于这 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_{i1}^n \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|} HA(D)−i1∑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 [1,k]} \frac{c}{n} 1−c∈[1,k]maxnc 熵 H ( x ) − ∑ i 1 m p ( x i ) log p ( x i ) H(x) -\sum_{i1}^m p(x_i) \log p(x_i) H(x)−i1∑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_{c1}^k p(x_i) \cdot (1 - p(x_i)) Gini(a)c1∑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_{k1}^K p_k(1 - p_k) 1 - \sum_{k1}^K p_k^2 Gini(p)k1∑Kpk(1−pk)1−k1∑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_{k1}^K \left(\frac{C_k}{|D|}\right)^2 Gini(D)1−k1∑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)
可以比较下基尼系数表达式和熵模型的表达式二次运算比对数运算简单很多。尤其是二类分类的计算更加简单。但是和熵模型的度量方式相比基尼系数对预测的误差有多大呢对于二类分类基尼系数和熵之间的曲线如下 从上图可以看出基尼系数和熵之半的曲线非常接近仅仅在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_{i1}}{2} Ti2aiai1
对于这 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)2c2minxi∈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. 决策树可视化
作业 回答采用信息增益、信息增益率作为决策树分裂策略有什么区别 在 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 进行导入。
