下文介绍学习决策树的过程，我们通过例子来更好地理解决策树。

决策树是什么，是一种基本的分类与回归的方法。分类决策树模型是一种描述对实例进行分类的树形结构。

决策树的算法包含：特征选择，决策树的生成、决策树的剪枝过程。

通过下面的例子来更好地了解决策树的机制。

希望通过训练得出决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款时，直接通过决策树决定是否批准贷款申请。

1.特征选择

特征选择是决定用哪个特征来划分特征空间。

现在存在四种可能的决策树的根节点，年龄（青年、中年、老年），工作（是、否），有房（是、否），信贷状况（非常好、好、一般）。那么问题是选择哪一个作为根特征更好一些？需要通过信息增益来解决。

1.1信息增益

熵（entropy）是表示随机变量不确定性的度量。设x是一个取有限个值的离散随机变量，其概率分布为P(X=xi)=pi,i=1,2,3...,n则随机变量x的熵定义为

条件熵H(Y|X)表示在已知随机变量x的条件下随机变量y的不确定性。

信息增益表示得知特征x的信息而使得y的信息不确定性减少的程度。

特征A对训练数据集D的信息增益g(D,A)=H(D)-H(D|A)。等价于训练数据集中类与特征的互信息。

决策树学习应用信息增益准则选择特征，给定训练数据集D合特征A，H(D)表示对D分类的不确定性，而H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性，差值为信息增益。不同的特征会有不同的信息增益，比较大小后信息增益大的特征具有更强的分类能力。

那么通过例子计算信息增益：

1.计算经验熵H(D)

2.计算四个特征的信息增益。

设A1,A2,A3,A4表示年龄、有工作、有房子、信贷状况。

年龄：D1,D2,D3为青年，中年，老年。

工作：D1,D2位是，否。

房子：

信贷状况：

其中A3的信息增益最大，则为最优特征。

在C4.5中使用信息增益比计算特征值：gR(D,A)=g(D,A)/H(D).

2.决策树的生成

2.1 ID3算法

决策树的各个节点上应用信息增益准则选择特征，递归构建决策树，具体方法是从根节点开始，对节点计算所以可能的特征信息增益，选择信息增益最大的特征作为节点的特征，在对子节点递归调用以上方法构建决策树。

由于特征A3的信息增益最大，所以选择特征A3为根节点，他可以划分为两个子集D1（A3为是），D2（A3为否），由于D1样本点均同意贷款，所以他成为一个没有子节点的叶节点。

对于D2需要从特征A1,A2,A4中选择最大特征作为其子节点。那么要计算信息增益：

A2的信息增益最大，那么作为房子后的节点。

工作有两个值是和否，但是由于没有房子但工作为是的有放了贷款，没有房子但是没有工作的都没有放贷，所以无需再增加子节点，该决策树只使用两个特征构成决策树。

2.2 C4.5

C4.5与ID3的区别在于使用信息增益比计算gR(D,A)=g(D,A)/H(D)。

2.3 CART分类与回归树

CART(classification and regression tree)的算法整体过程和上面的差异不大，然是CART的决策是二叉树的每一个决策只能是“是”和“否”，换句话说，即使一个feature有多个可能取值，也只选择其中一个而把数据分类两部分而不是多个，这里我们主要讲一下分类树，它用到的是基尼指数。

cart决策树生成就是递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

1.回归树的生成：？

最小二乘回归树生成算法：

2.分类树的生成:

首先计算各个特征的基尼指数，分别以A1,A2,A3,A4表示年龄、工作、房子和信贷状况，以1，2，3表示年龄的青年、中年、老年，已1，2表示是、否，已1，2，3表示信贷状况的非常好、好、一般。

》求A1的基尼指数：

Gini(D,A1=1)=P(A1=1)Gini(D1)+P(A1!=1)Gini(D2)

其中5/15为A1的概率，Gini(D1)为青年中放贷的基尼指数2p(1-p)，其中p为青年中放贷的概率为2/5,10/15为不是青年的概率，Gini(D2)为不是青年但是放贷的基尼指数2p(1-p)，其中p为不是青年但是放贷的概率7/10.

同理，算出其他的基尼指数：

Gini(D,A1=2)=0.48

Gini(D,A1=3)=0.44

由于Gini(D,A1=1)和Gini(D,A1=3)相等，且最小，所以A1=1和A1=3都可以最为A1的最优切分点。

》求特征A2和A3的基尼指数：

由于工作和房子均只有两种情况，是否，是和否的基尼指数相同，所以只有一个切分点。 

Gini(D,A2=1)=5/15Gini(D1)+10/15Gini(D2)=5/15*0+10/15*2*4/10*6/10=0.32

Gini(D,A3=1)=0.27

》求特征A4的基尼指数：

Gini(D,A4=1)=0.36

Gini(D,A4=2)=0.47

Gini(D,A4=3)=0.32

Gini(D,A4=3)最小，所以A4=3为A4的最优切分点。

在4个特征中，Gini(D,A3=1)最小，所以选择特征A3为最优特征，A3=1为最优切分点，于是A3为根节点，有两个子节点，其中一个全为是，则为叶节点，对领完一个节点继续使用以上方法，直至都为叶节点。

递归的停止条件，节点中的样本个数小于预定阈值，或样本集的基尼指数小于一定阈值（样本基本属于同一类）或没有更多特征。

3.剪枝

决策树会一直递归到结束为止，存在过拟合，原因是学习时过多的考虑如何提高对数据分类的准确性，构建了过于复杂的决策树。

前置裁剪在构建决策树的过程时，提前停止。那么，会将切分节点的条件设置的很苛刻，导致决策树很短小。结果就是决策树无法达到最优。实践证明这中策略无法得到较好的结果。

后置裁剪决策树构建好后，然后才开始裁剪。采用两种方法：1）用单一叶节点代替整个子树，叶节点的分类采用子树中最主要的分类；2）将一个字数完全替代另外一颗子树。后置裁剪有个问题就是计算效率，有些节点计算后就被裁剪了，导致有点浪费。

决策树剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。设树T的叶节点个数为|T|，t是树T的叶节点，该叶节点有Nt个样本点，其中k类的样本点有Ntk个，k=1，2...k,Ht(T)为叶节点t上的经验熵，α>=0为参数，则决策树学习的损失函数可以定义为：

C(T)表示模型对训练数据的预测误差，|T|为复杂度。损失函数为预测误差与复杂度的综合评价。

剪枝，就是当α确定时，选择损失函数最小的模型，即损失函数最小的子树。

如何进行剪枝：

（1）假设减掉最左边第一支，计算一次Cα(T1).

（2）假设减掉最左边第二支，计算一次Cα(T2).

（3）以上述方式递归向上每减掉一支计算一次一次Cα(Tn).

（4）求出Cα(T1)到Cα(Tn)中的最小值。

（5）减去此支，得到最优决策树。