1.决策树

决策树指一类常见的机器学习算法，以二分类为例，我们希望从给定训练集学得一个模型用以对新实列进行分类，这个把样本分类的任务，可以看作对‘“当前样本属性正常吗”这个问题的“决策”过程。而决策树就是基于树结构来进行决策的，如下图所示如果一个女生的妈妈给她介绍对象，如果这个被介绍的人的年龄大于30岁就不见，如果小于30岁长相丑的话也不见，年龄低于30岁长的帅收入低也不见，如果收入中等不是公务员不见，是公务员才会见面。最终这个女生经过了一系列的决策，决定最终见面还是不见。这个决策的过程就构成了一颗决策树。决策过程的最终结论对应了我们所希望的判定结果：见还是不见。一般的，一棵决策树包含一个根节点，若干个内部节点和若干个叶结点。叶节点对应与决策结果，其他每个结点则对应于一个属性测试。
在这里插入图片描述
下面给出决策树学习的基本流程：
有训练集D，属性集A
①生成结点node
②如果D中所有样本全部属于同一类别C，这时将node标记为C类结点。结束
③如果 A为空集或者D中所有样本在A上取值相同，这时将node标记为D中样本数最多的类。结束
④从A中选取最优划分a
⑤对a中的每一个值生成子决策树
西瓜书
显然生成决策树的过程与生成二叉树的过程一样，是一个递归的过程。

3.如何划分

由算法可以看出，生成决策树的关键步骤是从A中找到最优划分属性a，那么a是如何求出来的呢，目前主要有三种算法：ID3算法，C4.5算法，和CART算法，接下来我们先来介绍几组概念。

3.1信息熵

‘信息熵’是度量事物不确定性的一种指标，越不确定的事物，其信息熵就越大。其计算表达式为：

Ent(X)=−∑k=1npklog2pkEnt(X)=-\sum_{k=1}^{n}{p_{k}log_{2}{p_{k}}}

n表示X可以取到的离散值的个数,pkn表示X可以取到的离散值的个数,p_{k}为样本集合D中样本为k的概率。比如说X可以取0，1两种取值，其概率分别为1323\frac{1}{3} \frac{2}{3},其信息熵为Ent(X)=−13log213−−23log223=13log23−−23log23Ent(X)=-\frac{1}{3}log_{2}\frac{1}{3}--\frac{2}{3}log_{2}\frac{2}{3}=\frac{1}{3}log_{2}3--\frac{2}{3}log\frac{2}{3}

3.2条件熵

条件熵类似于条件概率，他是来度量X在知道Y以后的不确定性。

Ent(X∣Y)=∑k=1nP(yk)∗Ent(X∣Yk)Ent(X |Y)=\sum_{k=1}^{n}P(y_{k})*Ent(X|Y_{k})

3.3信息增益

Gain(D,a)=Ent(D)−Ent(D∣a)Gain(D,a)=Ent(D)-Ent(D |a)

一般信息增益越大，意味着使用属性a来进行划分的可靠性越高。
下面来举列子来说明一下这三个值是怎么算的：

feature labels
A1 1
A1 1
A1 1
A1 0
A1 0
A2 1
A2 1
A2 0
A2 0
A2 0
A3 1
A3 1
A3 1
A3 1
A3 0
样本D的信息熵为：

Ent(D)=−(915log2915+615log2615)=0.971Ent(D)=-(\frac{9}{15}log_{2}\frac{9}{15}+\frac{6}{15}log_{2}\frac{6}{15})=0.971

样本的条件熵为：

Ent(D∣A)=515Ent(D∣A1)+515Ent(D∣A2)+515Ent(D∣A3)Ent(D|A)=\frac{5}{15}Ent(D|A1)+\frac{5}{15}Ent(D|A2)+\frac{5}{15}Ent(D|A3)

=−515(35log235+25log225)−515(25log225+35log235)−515(45log245+45log215)=0.888=-\frac{5}{15}(\frac{3}{5}log_{2}\frac{3}{5}+\frac{2}{5}log_{2}\frac{2}{5})-\frac{5}{15}(\frac{2}{5}log_{2}\frac{2}{5}+\frac{3}{5}log_{2}\frac{3}{5})-\frac{5}{15}(\frac{4}{5}log_{2}\frac{4}{5}+\frac{4}{5}log_{2}\frac{1}{5})=0.888

信息增益为：

Gain(D,A)=Ent(D)−Ent(D∣A)=0.083Gain(D,A)=Ent(D)-Ent(D|A)=0.083

3.ID3算法

ID3决策树学习算法为准则信息增益来进行选择划分属性的。下面给出算法的过程：
①判断样本是否为同一类别C，如果是，则返回单节点树，标记类别为C
②判断特征是否为空，如果是则返回单节点数T，标记类别样本中输出类别为样本中的各类别实例数最多的类别
③通过计算样本各个特征的信息增益，挑选出信息增益最大的特征A1.
④按照特征A1的不同取值将对应的样本D划分成不同的子类别。
⑤对所有的子类别执行上述操作，得到决策树后返回。
ID3算法的不足：
ID3算法容易倾向于选择特征取值较多的特征作为最优特征。举了极端情况：如给上边的那个表格加上一列不同的编号，把编号也作为构造决策树的一个特征。显然，编号那列计算出来的条件熵会是0，由于信息熵一样，所以标号那列的信息增益会是最大的，根据ID3算法将增益率作为选择标准的原则，那么编号这一列会是最优特征，但这回将样本划分成15个子类别，每个子列的样本数都为1，但明显这样划分是不合理的。而且ID3算法也只能处理离散型的数据，对于连续型的数据，ID3无法运用。所以ID3算法的设计者就对此算法进行了改进，提出了C4.5算法。

4.C4.5算法

4.1连续型数据处理

对于连续型数据，C4.5思路是将连续的特征离散化。比如m个样本的连续型特征A有m个，将这m个数据由小到大排序，取相邻两个样本值得平均数作为划分点，一共会取得m-1个划分点，分别计算这m-1个点分别作为二元分类点时得信息增益，取信息增益最大得点作为该连续性特征得二元离散分类点。
在这里插入图片描述
图中左边为一系列年龄为特征从小到大排好顺序的数据，分别取相邻两个样本的平均值得到了右边的一列数据，假设我们要按年龄划分为大人和小孩，则就分别以右边的那列数据作为划分点来计算对应的信息增益，如17说，将小于17的划分为小孩，大于17的划分为大人，来计算其信息增益。计算出每个划分点的信息增以后，选出信息增益最大的那个对应的点作为最终的划分点。

4.2.C4.5的改进

对于将信息增益作为标准倾向于选择取值较多的特征的问题，C4.5引入了一个新的信息增益的比量，他是信息增益和特征熵的比值增益率。
增益率的定义：$$Gain_ratio(D,a)=\frac{Gain(D,A)}{Ent_{A}(D)}$$
其中D为最终输出的特征标签，A为样本特征。特征熵的表达式为

EntA(D)=−∑i=1n∣Di∣∣D∣log2∣Di∣∣D∣Ent_{A}(D)=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}log_{2}\frac{|D_{i}|}{|D|}

其中n为特征A的类别数，DiD_{i}为特征A的第i个取值对应的样本个数。|D|为样本个数。
特征数越多的特征对应的特征熵越大，他作为分母，可以校正信息增益容易偏向取值较多的特征的问题。C4.5便是将增益率来作为选择标准。
参考自：刘建平决策树决策树算法原理

5.Crat算法(分类树)

5.1基尼系数

CART是基于基尼(Gini)系数最小化准则来进行特征选择，生成二叉树。

基尼系数代表了模型得不纯度，基尼系数越小，则不纯度越低，特征越好。这点和信息增益是相反的。

在分类问题中，假设有K各类别，第k个类别概率为pkp_{k},则基尼系数的表达式为：

Gini(D)=1−∑k=1Kpk2Gini(D)=1-\sum_{k=1}^{K}p_{k}^{2}

若给定样本D，如果根据特征A的某个值a，把D分为D1和D2两个部分，则在特征条件A下，D的基尼系数表达式为：

GiniA(D)=D1DGini(D1)+D2DGini(D2)Gini_{A}{(D)}=\frac{D_{1}}{D}Gini(D_{1})+\frac{D_{2}}{D}{Gini(D_2)}

5.2连续型特征处理

CART处理连续值问题与C4.5一样，都是将连续的特征离散化，唯一区别在于，C4.5采用信息增益率而CART算法采取的是基尼系数。

具体思路如下：有m个样本的连续的特征A有m个，从小到大排序。取相邻两个样本值的平均数，则会得到m-1个二分类点。分别计算这m-1

个点分别作为二分类点时的基尼系数。选择基尼系数最小的点作为该连续型特征的二元分类点。与ID3和C4.5不同的是如果当前节点为连续属性，则该属性在后面还可以参与子节点的产生选择过程。

在ID3和C4.5中，特征A被选取建立决策树结点，如果他有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.

5.3CART算法

在这里插入图片描述
在这里插入图片描述

来自李航《统计学原理》一书。

5.5 举例说明

如下图所示的一组数据，其中样本特征有三个分别为是否有房，婚姻状况和年收入，其中有房情况和婚姻状况是离散型的取值，而年收入是连续型取值。是否拖欠贷款属于分类的结果。

对于是否有房这个特征，他是一个二分类离散数据，其基尼系数为：

在这里插入图片描述

Gini=310Gini(有房)+710Gini(无房)Gini=\frac{3}{10}Gini(有房)+\frac{7}{10}Gini(无房)

=310(1−((33)2+(03)2)+710(1−((47)2+(37)2)=\frac{3}{10}(1-((\frac{3}{3})^{2}+(\frac{0}{3})^{2})+\frac{7}{10}(1-((\frac{4}{7})^{2}+(\frac{3}{7})^{2})=0.343

对于婚姻状况这个有三个取值的离散型特征，他有三种分类情况，要计算出每一种对于的基尼指数：

单身或已婚 离婚
是否拖欠贷款 否 6 1
是 2 1

Gini=210Gini(离婚)+810Gini(单身或已婚)Gini=\frac{2}{10}Gini(离婚)+\frac{8}{10}Gini(单身或已婚)

=210(1−((12)2+(12)2)+810(1−((68)2+(28)2)=\frac{2}{10}(1-((\frac{1}{2})^{2}+(\frac{1}{2})^{2})+\frac{8}{10}(1-((\frac{6}{8})^{2}+(\frac{2}{8})^{2})=0.4

单身或离婚 已婚
是否拖欠贷款 否 3 4
是 3 0

Gini=410Gini(已婚)+610Gini(单身或离婚)Gini=\frac{4}{10}Gini(已婚)+\frac{6}{10}Gini(单身或离婚)

=410(1−((44)2+(04)2)+610(1−((36)2+(36)2)=\frac{4}{10}(1-((\frac{4}{4})^{2}+(\frac{0}{4})^{2})+\frac{6}{10}(1-((\frac{3}{6})^{2}+(\frac{3}{6})^{2})=0.3

已婚或离婚 单身
是否拖欠贷款 否 5 2
是 1 2

Gini=410Gini(单身)+610Gini(已婚或离婚)Gini=\frac{4}{10}Gini(单身)+\frac{6}{10}Gini(已婚或离婚)

=410(1−((24)2+(24)2)+610(1−((56)2+(16)2)=\frac{4}{10}(1-((\frac{2}{4})^{2}+(\frac{2}{4})^{2})+\frac{6}{10}(1-((\frac{5}{6})^{2}+(\frac{1}{6})^{2})=0.3667

对于收入这个连续型数据，要先转换为离散型才可以计算，

在这里插入图片描述

通过计算我们得出了当以97作为分类点时其基尼系数最小，所以选择97作为此时该特征得二元分类点。

此时我们通过比较，发现 ==离婚==作为婚姻状况得分类点和97作为收入得分类点得基尼系数一样，所以我们可以随意选择他们两个其中任意一个作为最有特征得最优特征值。选择得点不一样，构造出来的决策树也会不一样。在选择一个点后，将数据分为了D1和D2两个部分，对这两个部分用上边方法计算其基尼系数。

选择婚姻状况为最优特征得到的一个决策树：