<style></style> <style></style> <style></style> <style></style>
1、决策树概述¶
决策树（decision tree）是一种基本的分类与回归方法。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合（互斥并且完备），也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据利用决策树模型进行分类。决策树学习通常包括三个步骤：
1.特征选择：从训练数据的特征中选择一个特征作为当前节点的分裂标准（特征选择的标准不同产生了不同的特征决策树算法）。
2.决策树生成：根据所选特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止声场。
3.决策树剪枝：决策树容易过拟合，需要剪枝来缩小树的结构和规模（包括预剪枝和后剪枝）。
今天主要讲解下如何选择最优划分属性，而在划分的过程中，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。测试数据如图：
2、ID3算法（信息增益）¶
信息熵（information entropy）：度量样本集合纯度最常用的一种指标，表示样本数据的混乱程度。假定当前样本集合D中第k类样本所占的比例为$p_k(1,2....|y|)$,则D的信息熵定义为：
$$Ent(D)=-\sum_{k=1}^{|y|}{p_k{\log_2{p_k}}}$$$Ent(D)$的值越小，纯度越高，数据越混乱。计算信息熵时约定，若$p=0$,则$p\log_2p=0$。$Ent(D)$为0，最大值为$\log_2{|y|}$。
以上可看，样本集合D*15条数据，样本类别数k为2。同意贷款的样本数为9个，不同意贷款的样本数为6个。则样本集合D的信息熵详细计算过程为：
$$Ent(D)=-\frac{9}{15} * \log_2 {\frac{9}{15}} - \frac{6}{15} * \log_2 {\frac{6}{15}} = 0.971$$假定离散属性$a$有$V$个可能取值$\{a1,a2,…,aV\}$，若使用$a$来对样本集$D$划分，则会产生$V$个分支结点，其中第$v$个分支结点包含了$D$中所有在属性$a$上取值为$a^v$,记作${D^v}$。 再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重$\frac{D^v}{D}$，,即样本数越多的分支结点的影响越大，于是可计算出用属性$a$对样本集$D$进行划分所获得的“信息增益”(information gain):
$$Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)$$一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的的“纯度提升”越大。因此，我们可以根据信息增益来选择结点，一般选择信息增益最大的属性作为划分结点。则
$$arg\,\max_{a\in{A}}Gain(D,a)$$则属性年龄$(A)$对样本集合$D$进行划分获得信息增益的详细计算过程为：
类别为青年$(A_1)$的信息熵：
$$Ent(A_1)=-\frac{2}{5} * \log_2 {\frac{2}{5}} - \frac{3}{5} * \log_2 {\frac{3}{5}} = 0.971$$类别为中年$(A_2)$的信息熵：
$$Ent(A_2)=-\frac{3}{5} * \log_2 {\frac{3}{5}} - \frac{2}{5} * \log_2 {\frac{2}{5}} = 0.971$$类别为老年$(A_3)$的信息熵：
$$Ent(A_3)=-\frac{4}{5} * \log_2 {\frac{4}{5}} - \frac{1}{5} * \log_2 {\frac{1}{5}} = 0.722$$则属性年龄$(A)$的信息增益：
$$Gain(D,A)=Ent(D)-\frac{5}{15}*Ent(A_1)-\frac{5}{15}*Ent(A_2)-\frac{5}{15}*Ent(A_3)=0.083$$同理，属性为是否工作$(B)$和是否有房$(C)$的信息增益分别是：
$$Gain(D,B)=Ent(D)-\frac{5}{15}*Ent(B_1)-\frac{10}{15}*Ent(B_2)=0.324$$ $$Gain(D,C)=Ent(D)-\frac{6}{15}*Ent(C_1)-\frac{9}{15}*Ent(C_2)=0.420$$则信息增益最大的属性为是否有房，将作为第一个划分节点。划分后的子节点再根据相同算法以此类推，递归计算，各子节点之间互不干扰。
3、C4.5算法（信息增益率）¶
为什么引入信息增益率？
这是为了解决信息增益的使用过程中，对属性值种类较多的属性比较偏好，这个问题，所以引入信息增益率。比如当误把编号当成属性时，此时条件熵为0，信息增益达到最大，因此将选择编号作为分类的一个属性，这显然是不合理的。
实际上，由于信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”来选择最优划分属性。增益率定义为：
$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$其中：
$$IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}$$称为属性$a$的“固有值”(intrinsic value).
须注意的是，由于增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法采用先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的方法来选择最优划分属性
则样本集合中各个属性的固有值为：
$$IV(A)=-\frac{5}{15}\log_2 \frac{5}{15}-\frac{5}{15}\log_2 \frac{5}{15}-\frac{5}{15}\log_2 \frac{5}{15}=1.585$$ $$IV(B)=-\frac{5}{15}\log_2 \frac{5}{15}-\frac{10}{15}\log_2 \frac{10}{15}=0.918$$ $$IV(C)=-\frac{6}{15}\log_2 \frac{6}{15}-\frac{9}{15}\log_2 \frac{9}{15}=0.971$$样本集合对各个属性的信息增益率分别是：
$$Gain\_ratio(D,A)=\frac{Gain(D,A)}{IV(A)}=\frac{0.083}{1.585}=0.052$$ $$Gain\_ratio(D,B)=\frac{Gain(D,B)}{IV(B)}=\frac{0.324}{0.918}=0.353$$ $$Gain\_ratio(D,C)=\frac{Gain(D,C)}{IV(C)}=\frac{0.420}{0.971}=0.433$$则信息增益率最大的属性为是否有房，将作为第一个划分节点。划分后的子节点再根据相同算法以此类推，递归计算，各子节点之间互不干扰。
4、CART算法（基尼系数）¶
$CART(Classification and Regression)$决策树使用基尼指数$(Gini Index)$来选择划分属性。数据集$D$的纯度可用基尼值来度量
$$Gini(D)=\sum_{k=1}^y\sum_{k^\prime\neq k}{p_k}{p_{k^\prime}}=1-\sum_{k=1}^{|y|}{p_k}^2$$直观来说，$Gini(D)$反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$越小,则数据集$D$的纯度越高。
属性$a$的基尼指数定义为：
$$Gini\_index(D,a)=\sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D_v)$$于是，我们在划分属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即：
$$arg\,\min_{a\in{A}}Gini\_index(D,a)$$信息熵代表了混乱程度。信息熵越小，信息增益越大，纯度越大。基尼值表示了类别不一致的概率，基尼值越小，纯度越大。
则基尼系数计算的详细流程为：
$$Gini\_index(D,A)=\frac{5}{15}*[1-(\frac{2}{5})^2-(\frac{3}{5})^2]+\frac{5}{15}*[1-(\frac{3}{5})^2-(\frac{2}{5})^2]+\frac{5}{15}*[1-(\frac{4}{5})^2-(\frac{1}{5})^2]=\frac{2}{5}$$ $$Gini\_index(D,B)=\frac{5}{15}*[1-(\frac{5}{5})^2-(\frac{0}{5})^2]+\frac{10}{15}*[1-(\frac{4}{10})^2-(\frac{6}{10})^2]=\frac{8}{25}$$ $$Gini\_index(D,C)=\frac{6}{15}*[1-(\frac{6}{6})^2-(\frac{0}{6})^2]+\frac{9}{15}*[1-(\frac{3}{9})^2-(\frac{6}{9})^2]=\frac{4}{15}$$则属性“是否有房”的基尼系数最小，作为第一部分划分的节点属性。
5、总结¶
本文主要讲述了决策树中特征选择的三个原则：信息增益、信息增益率和基尼系数。当然，决策树还有生成、裁剪、回归的知识，后续的博文会进行讲述。博文中若有错误和不足之处，欢迎指正。