前语

决议计划树：一种树形结构，其间每个内部节点表明一个属性上的判别，每个分支代表一个判别成果的输出，终究每个叶节点代表一种分类成果。

请确保已经了处理议计划树的根本工作流程再进行阅览。

最典型的决议计划树算法是Hunt算法，该算法是由Hunt等人提出的最早的决议计划树算法。现代，Hunt算法是许多决议计划树算 法的根底，包括ID3、C4.5和CART等。Hunt算法诞生时刻较早，且根底理论并非特别完善，本文由运用较广、理论 根底较为完善的ID3算法的根本原理开始进行解说。

决议计划树算法的中心是要处理几个问题：

  • 如何从数据表中找出最合适特征进行分支 ？
  • 什么时分让决议计划树中止成长，防止过拟合 ？

文章内容若不特别标示则默认以分类树为例来进行阐明。

不纯度的衡量目标

为了要将数据表转化为一棵树，决议计划树需求从一切特征中找到最佳特征用于分支，而衡量某个特征好不好的目标便是不纯度。

下面都是依据分类树来讲的，因为分类树的不纯度核算办法较为杂乱，关于回归树来讲，最常用的便是MSN(均方误差)。

决议计划树的每个节点中都包括一组数据，在这组数据中，假如有某一类标签占有较大的份额，咱们就说这组数据或节点比较 “纯”。某一类标签占的份额越大，叶子就越纯，不纯度就越低，分枝就越好。假如没有哪一类标签的份额很大，各类标签都相对均匀，则说该组数据或节点 “不纯”，不纯度高，分枝不好。

分类型决议计划树在叶子节点上的决议计划规则是少数服从多数，当叶子节点比较纯时，表明可信度越高，当叶子节点不纯时，成果可信度就相对更低。例如某叶子节点中A标签数据有10个，B标签数据有9个，按照少数服从多数，将该叶子节点的某测试数据归为A标签显然并没有多大掌握，分类过错的概率就高了。

回归型决议计划树在叶子节点上的决议计划规则是取其均值。

分类误差率(Classification error)

不纯度的核算或衡量办法一般由误差率衍生而来，误差率的核算非常简略粗犷：

Classificationerror(t)=1−max[p(i∣t)]\begin{align} Classification\space error(t) = 1-max[p(i|t)] \end{align}
  • 取值范围：0≤Classificationerror(t)≤0.050\le Classification\space error(t) \le 0.05
  • tt：表明某组数据
  • p(i∣t)p(i|t)：表明某组数据(tt) 下类别 ii 所占的份额

分类误差率越小代表越纯，不纯度越低，反之不纯度越高。

例如一个笼子里有3只小狗，4只小猫，5只小猪，那这组数据的误差率就为 1−53+4+5=7121-\frac{5}{3+4+5}=\frac {7}{12}。

误差率在核算的时分能够看出，将数量最多的类别以外的其它类别的数据都视为 “过错” 的数据，然后核算这些 “过错” 的数据在一切数据中所占的份额，将这个份额作为核算成果。

信息熵：Entropy

信息熵公式：

Entropy(t)=−∑i=0c−1p(i∣t)log2p(i∣t)\begin{align} Entropy(t)=-\sum^{c-1}_{i=0}p(i|t)log_2p(i|t) \end{align}
  • 取值范围：0≤Entropy(t)≤10\le Entropy(t) \le 1
  • tt：表明某组数据
  • p(i∣t)p(i|t)：表明某组数据(tt) 下类别 ii 所占的份额
  • c：样本数据中的类别个数

信息熵越小代表越纯，不纯度越低，反之不纯度越高。

信息中信息量的大小跟随机工作的概率有关。越小概率的工作发生的信息量越大，越大概率的工作发生了发生的信息量越小。

  • 某地发生了地震：小概率工作, 信息量大
  • 太阳从东方升起，西方落下：大概率视屏，信息量小

信息量：信息量是对信息的衡量，多少信息用信息量来衡量。

因而一个详细工作的信息量应该是跟着其发生概率而递减的，且不能为负

假定存在两个不相关的工作 xx 和 yy，依据知识咱们能够很简单理解当两个工作同时发生时发生的信息量等于每个工作各自发生时发生的信息量之和，即：f(px,py)=f(px)+f(py)f(p_x,p_y) = f(p_x)+f(p_y)

因为两工作不相关，因而 pxy=px∗pyp_{xy}=p_x*p_y，也便是工作 xx 和 yy 同时发生的概率等于两者发生的概率的积，则有 f(pxy)=f(px)+f(py)f(p_{xy})=f(p_x)+f(p_y)

咱们要找到满意这样一个联系的函数，很简单就能联想到 f(px)f(p_x) 与 pxp_x 的对数有关，因而得到信息量公式。fe

  • 信息量公式：h(x)=−log2p(x)h(x)=-log_2p(x)
  • 例如：h(x)+h(y)=−(log2p(x)+log2p(y))=−log2p(x)p(y)=−log2p(xy)h(x)+h(y)=-(log_2p(x)+log_2p(y))=-log_2p(x)p(y)=-log_2p(xy)
    • 即：h(xy)=h(x)+h(y)h(xy)=h(x)+h(y)
  • 为什么要加负号：概率小于等于1，因而 log2p(x)≤0log_2p(x) \le 0，信息量要求大于等于0
  • 为什么底数是2：咱们只需求信息量满意低概率工作 x 对应于高的信息量。那么对数的挑选是任意的。咱们仅仅遵循信息论的遍及传统，运用 2 作为对数的底

信息熵(Entropy)：信息量衡量的是一个详细工作发生了所带来的信息，而熵则是在成果出来之前对或许发生的信息量的希望——考虑该随机变量的一切或许取值，即一切或许发生工作所带来的信息量的希望，这时分再看信息熵公式应该会清楚许多。

此外，信息熵还能够作为一个体系杂乱程度的衡量，体系越杂乱，出现不同状况的品种越多，则信息熵越大，反之越小。关于决议计划树中的某节点也是如此。

信息增益(Information gain)：决议计划树中的信息增益是指子节点的信息熵减去父节点的信息熵，值一定是正数，信息增益越大，代表运用某特征进行分支的效果越好。

基尼系数：Gini

Gini系数公式：

Gini(t)=∑i=0c−1p(i∣t)[1−p(i∣t)]=1−∑i=0c−1[p(i∣t)]2\begin{align} Gini(t)&=\sum^{c-1}_{i=0}p(i|t)[1-p(i|t)]\\ &=1-\sum^{c-1}_{i=0}[p(i|t)]^2 \end{align}
  • 取值范围：0≤Gini(t)≤0.050\le Gini(t) \le 0.05
  • tt：表明某组数据
  • p(i∣t)p(i|t)：表明某组数据(tt) 下类别 ii 所占的份额
  • c：样本数据中的类别个数

Gini系数越小代表越纯，不纯度越低，反之不纯度越高。

Gini系数是衡量不纯度或不平等衡量的一种目标，常用于衡量贫富差距，与信息熵核算公式比较，只需将信息熵核算公式中的 log2p(i∣t)log_2p(i|t) 替换为 1−p(i∣t)1-p(i|t) 即可。

与分类误差率进行比较，分类误差率只考虑除占比最大的类以外的类所占的份额，但由公式能够看出，Gini系数则是考虑全部工作发生的概率求希望，而且比较信息熵的核算更加简略。

误差率、信息熵、Gini系数 比较

【机器学习】DecisionTree - 决策树中的数学原理

分类误差率的限制性：

  • 对样本分布不灵敏：分类误差率只考虑被过错分类的样本份额，而忽略了样本在各个类别中的分布状况。这意味着在处理不均衡数据集时，分类误差率或许无法准确反映数据的真实状况。
  • 不具备接连性：分类误差率只重视样本的分类成果，而不考虑类别之间的联系和接连性。这在处理接连型特征或特征之间存在明显次序联系的状况下，或许导致信息损失和决议计划不准确。
  • 不支持特征权重：分类误差率对一切特征都是等权重考虑，无法通过给予不同特征不同的权重来增强对某些特征的重要性。这在某些问题中或许约束了决议计划树的表达能力。
  • 不适用于多类别问题：分类误差率在处理多类别问题时存在问题。它只考虑了被过错分类的样本份额，而忽略了其他类别的信息。在多类别问题中，信息熵和Gini系数通常更常用和更可靠。

信息熵和Gini系数之间差别不大，大多状况都是运用的信息熵或Gini系数来作为不纯度的衡量标准。

ID3算法

特征挑选

决议计划树终究的优化目标是使得叶节点的总不纯度最低，即对应衡量不纯度的目标最低。

ID3运用的不纯度衡量办法是信息熵，最优条件是叶节点的总信息熵最小，因而ID3决议计划树在决定是否对某节点进行切分的时分，会尽或许选取使得该节点对应的子节点信息熵最小的特征进行切分。换言之，便是要求父节点信息熵和子节点总信息熵之差要最大。关于ID3而言，二者之差便是信息增益，即Information gain。

但这儿需求注意，一个父节点下或许有多个子节点，而每个子节点又有自己的信息熵，所以父节点信息熵和子节点信息熵之差，应该是父节点的信息熵 – 一切子节点信息熵的加权均匀。其间，权重是运用单个叶子节点上所占的样本量比上父节点上的总样本量。

I(child)=∑j=1kN(vj)NI(vj)I(child)=\sum^k_{j=1}\frac{N(v_j)}{N}I(v_j)
  • vjv_j：子节点
  • N(vj)N(v_j)：该子节点的样本量
  • NN：总样本量
  • II：不纯度，impurity

父节点和子节点的不纯度下降数：

I=I(parent)−I(child)\Delta I = I(parent) – I(child)

这儿的 I(vi)I(vi) 是某节点的不纯度衡量，能够是Gini系数、信息熵等办法，由父节点不纯度和子节点不纯度均值的差得到不纯度下降数，若运用信息熵办法，则该目标便是信息增益，不纯度下降数越大阐明效果越好。

关于某数据下的一切特征，咱们在挑选特征发生分支时会对一切特征核算不纯度下降数，然后挑选不纯度下降数最大的特征，挑选后该特征会被消费掉，不会再次对其进行核算和挑选。ID3算法运用的不纯度衡量目标是信息熵，其部分最优化条件也便是信息增益。

当特征较多时，挑选一切特征来核算不纯度下降数再进行比较会大大添加核算量，因而运用部分最优的办法，也便是从原本一切特征中随机选取一部分特征，把这些特征作为全部特征来从中进行核算和挑选。

总的来说，决议计划树模型是一个典型的贪心模型，总目标是一个大局最优解，即一整套合理的分类规则使得终究叶节点的纯度最高，但大局最优解在随特征添加而出现指数级添加的查找空间内很难高效获取，因而咱们退而求其次，考虑采用部分最优来一步步推导成果——只要确保信息增益最大，咱们就能得到次最优的模型。当然，部分最优不一定等于大局最优。

ID3 的限制性

ID3限制主要源于部分最优化条件，即信息增益的核算办法，其限制性主要有以下几点：

  • 分支度越高（分类水平越多）的离散变量往往子节点的总信息熵会更小，ID3是按照某一列进行切分，有一些列的分类或许对成果没有足够好的指示。例如一个比较极点的比如：ID3会选取样本的ID作为切分字段，因为每个样本的ID都是不唯一的，这样的话每个分类(子节点)的不纯度都是0，信息增益最大，但这样的分类方式是没有任何效益的
  • 不能直接处理接连型变量，若要运用ID3处理接连型变量，则首先需求对接连变量进行离散化
  • 对缺失值较为灵敏，运用ID3之前需求提前对缺失值进行处理
  • 没有剪枝的设置，简单导致过拟合，即在训练集上体现很好，测试集上体现很差

分支度/分类变量水平：例如性别这个特征有两个取值，分别是男、女，发生两个分支，分类变量水平便是2；再例如温度这个特征有三个取值，分别是高、中、低，发生三个分支，分类变量水平便是3。

C4.5算法 / CART算法

修正部分最优化条件

在C4.5中，首先通过引进分支度（IV：Information Value）的概念，来对信息增益的核算办法进行修正，简而言之，便是在信息增益核算办法的子节点总信息熵的核算办法中添加了 跟着分类变量水平的惩罚项。而分支度的核算公式仍然是根据熵的算法，仅仅将信息熵核算公式中的 p(i∣t)p(i|t) (某类别样本占总样本数) 改成了 P(vi)P(v_i) (某子节点的总样本数占父节点总样本数的份额)，这其实便是咱们加权求和时的 “权重”。这样的一个分支度目标，让咱们在切分的时分，主动避免那些分类水平太多，信息熵减小过快的特征影响模型，减少过拟合状况。

分支度核算公式如下：

InformationValue=−∑i=1kP(vi)log2P(vi)Information\space Value = -\sum^{k}_{i=1}P(v_i)log_2P(v_i)
  • ii：父节点的第 ii 个子节点
  • viv_i：第 ii 个子节点样本数
  • P(vi)P(v_i)：第 ii 个子节点具有样本数占父节点总样本数的份额

由前面讲过的信息熵来理解，便是分类变量水平越高，越杂乱，对应的信息熵越高，反之越低，因而能够作为其惩罚项，也便是说一个特征中假如标签分类太多，那对应的分支度就会相应增大。

在C4.5中，运用分支度作为惩罚项，也便是将信息增益除以分支度这个目标作为参阅标准，该目标被称为Gain Ratio (获利份额/增益率)，核算公式如下：

GainRatio=InforationGainInformationValueGain Ratio = \frac{Inforation\space Gain}{Information\space Value}
  • 翻译成中文便是 获利比率=信息增益分支度获利比率 = \frac{信息增益}{分支度}

这样就处理了ID3算法中运用信息增益作为部分最优化条件带来的问题。

处理接连型变量

在C4.5中，还添加了针对接连变量的处理办法。若输入特征字段是接连型变量，则有下列步骤：

  1. 算法首先会对这一列数进行从小到大的排序
  2. 选取相邻的两个数的中心数作为切分数据集的备选点，若一个接连变量有N个值，则在C4.5的处理过程中将发生 N-1个备选切分点，而且每个切分点都代表着一种二叉树的切分计划

这儿需求注意的是，此时针对接连变量的处理并非是将其转化为一个具有N-1个分类水平的分类变量，而是将其转化成了N-1个二分计划，而在进行下一次的切分过程中，这N-1个计划都要单独带入考虑，其间每一个切分计划和一个离散变量的地位均相同（一个离散变量便是一个单独的多路切分计划）；和ID3相同，当挑选后，该特征将会被消费掉，不会再次进行核算和挑选。

例如某年纪字段数据：11,12,13,14,15,16,17,18,19,20，共10个值

将会对每两个数进行切分，发生9种计划：

  • age<11.5，age>11.5age < 11.5，age > 11.5
  • age<12.5,age>12.5age < 12.5, age > 12.5
  • ⋯\cdots
  • age<19.5,age>19.5age < 19.5, age > 19.5

从上述论说能够看出，在关于包括接连变量的数据集进行树模型构建的过程中要耗费更多的运算资源。但与此同时， 咱们也会发现，当接连变量的某中心点参与到决议计划树的二分过程中，往往代表该点关于终究分类成果有较大影响，这 也为咱们接连变量的分箱压缩提供了指导性意见。

CART算法

现在被很多运用的是C4.5的改善CART树，CART树实质其实和C4.5区别不大，只不过CART树一切的层都是二叉树， 也便是每层只要两个分枝。

让咱们运用CART树来过一遍C4.5的流程，假定年纪是特征，性别是标签：

  1. 首先将年纪从小到大依此进行排列
  2. 然后核算两两相邻的年纪的均值
  3. 按均值所在的点，对接连性变量进行二分（变成数字形式的，第一类是>均值，第二类是<均值）， 二分得到的点叫做决议计划树的 “树桩”。
  4. 核算 n-1个 二分切分计划的获利份额，获利份额最大的切分点，便是切点
  5. 切完之后，核算加权信息熵，核算信息增益，引进分支度，能够核算出相应获利份额了

这个流程和C4.5算法的流程根本一致，但需求注意的是在一些方面存在不同。

改善计划：

  • CART算法 对接连型变量的这种切分办法，每次切分之后，并没有消费掉一整个特征，而是只消费掉了一个备选点。而 C4.5 算法每次进行特征挑选就会消费掉一整个特征。
  • 实际上，咱们能够只重视每次分类的时分，对信息熵的减少奉献最多的那个分类。按咱们的比如来说，咱们在分类 age 的时分，最重视的是 31 – 40 岁的那一个分类，咱们完全能够实现 31 – 40 为一类，其他算一类，然后咱们再对”其它”这个类别进行相似的二分类。这便是CART的中心原理，很多地减少了核算的量。

总结

决议计划树的根本流程其实能够简略概括如下：

  1. 核算全部特征的不纯度目标
  2. 选取不纯度目标最优的特征进行分支
  3. ⋯\cdots 直到没有更多的特征可用，或全体的不纯度目标已经最优，或到达设置的某些阈值 (如最大深度)，决议计划树就会中止成长。

关于KNN算法，咱们有一个假定：便是每一个特征关于咱们的揣度的重要性是相同的。这也是KNN最大的缺陷。而决议计划树天生就以为每个特征关于揣度的重要性不是相同的，而CART则是进一步以为，每个特征下的每个分类关于揣度的重要性也不是相同的。

Reference

  • 菜菜的sklearn机器学习
  • 相关网络资料和阐明