一.简介
决策树学习是一种逼近离散值目标函数的方法，在这种方法中学习到的函数被表示为一棵决策树。
二.决策树的表示法
决策树通过把实例从艮节点排列到某个叶子结点来分类实例，叶子结点即为实例所属的分类。树上的每一个结点指定了对实例的某个属性的测试，并且该结点的每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根节点开始，测试这个结点的属性，然后按照给定实例的属性值对应的树枝向下移动。然后这个过程在以新结点的根的子树上重复。
决策树对应表达式：
四.基本的决策树学习算法
1. ID3算法
通过自顶向下构造决策树来进行学习。构造过程是从“哪一个属性将在树的根结点被测试？”这个问题开始的。为了回答这个问题，使用统计测试来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作树的根结点的测试。然后为根节点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支之下。然后重复整个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。这形成了对合格决策树的贪婪搜索（greedy search），也就是算法从不回溯重新考虑原来的选。
专门用于学习布尔函数的ID3算法概要
ID3(Examples,Target_attribute,Attributes)
Examples即训练样例集。Target_attribute是这棵树要测试的目标属性。Attributes是除目标属性外供学习到的决策树测试的属性列表。返回一棵能正确分类给定Examples的决策树。
•如果Examples都为正，那么返回label=+的单结点树Root
•如果Examples都为反，那么返回label=+的单结点树Root
•如果Attributes为空，那么返回单结点树Root，label=Examples中最普遍的Target_attribute的值
•否则开始
•A←Attributes中分类Examples能力最好的属性
•Root的决策属性←A
•对于A的每个可能值vi
•在Root下加一个新的分支对应测试A=vi
•令Examples vi为Examples中满足A属性值为vi的子集
•如果Examples vi为空
•在这个新分支下加一个叶子结点，结点的label=Examples中最普遍的Target_attribute值
•否则在这个新分支下加一个子树ID3(Examples vi,Target_attribute,Attributes-{A})
•结束
•返回Root
2. 哪个属性是最佳的分类属性
熵（entropy）:刻画了任意样例集的纯度（purity）。
熵确定了要编码集合S中任意成员（即以均匀的概率随机抽出的一个成员）的分类所需要的最小二进制位数。
如果目标属性具有c个不同的值，那么S相对c个状态（c-wise）的分类的熵定义为：
Pi是S中属于类别i的比例。
信息增益（information gain）：一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低。
Values(A)是属性A所有可能值的集合，Sv 是S中属性A的值为v的子集。
例如，假定S包含14个样例-[9+,5-]。在这14个样例中，假定正例中的6个和反例中的2个有Wind=Weak，其他的有Wind=Strong。由于按照属性Wind分类14个样例得到的信息增益可以计算如下。
Values(Wind)=Weak,Strong
S=[9+,5-]
SWeak←[6+,2-]
Sstrong←[3+,3-]
=Entropy(S)-(8/14)Entropy(SWeak)-(6/14)Entropy(Sstrong)
=0.940-(8/14)0.811-(6/14)1.00
=0.048
3.举例
- 首先计算四个属性的信息增益：
Gain(S,Outlook)=0.246
Gain(S,Humidity)=0.151
Gain(S,Wind)=0.048
Gain(S,Temperature)=0.029
根据信息增益标准，属性Outlook在训练样例上提供了对目标属性PlayTennis的最佳预测。
Ssunny ={D1,D2,D8,D9,D11}
Gain(Ssunny,Humidity)=0.970-(3/5)0.0-(2/5)0.0=.970
Gain(Ssunny, Temperature)=0.970-(2/5)1.0-(2/5)1.0-(1/5)0.0=.570
Gain(Ssunny ,Wind)=0.970-(2/5)1.0-(3/5).918=.019
五．决策树学习中的假设空间搜索
ID3算法中的假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间。
当变了决策树空间时，ID3仅维护单一的当前假设。
基本的ID3算法在搜索中不进行回溯。
ID3算法在搜索的每一步都使用当前的所有训练样例，以统计为基础觉得怎样简化以前的假设。
六．C4.5
C4.5克服了ID3的2个缺点：
1.用信息增益选择属性时偏向于选择分枝比较多的属性值，即取值多的属性
2.不能处理连贯属性
| Outlook | Temperature | Humidity | Windy | PlayGolf? |
| sunny | 85 | 85 | FALSE | no |
| sunny | 80 | 90 | TRUE | no |
| overcast | 83 | 86 | FALSE | yes |
| rainy | 70 | 96 | FALSE | yes |
| rainy | 68 | 80 | FALSE | yes |
| rainy | 65 | 70 | TRUE | no |
| overcast | 64 | 65 | TRUE | yes |
| sunny | 72 | 95 | FALSE | no |
| sunny | 69 | 70 | FALSE | yes |
| rainy | 75 | 80 | FALSE | yes |
| sunny | 75 | 70 | TRUE | yes |
| overcast | 72 | 90 | TRUE | yes |
| overcast | 81 | 75 | FALSE | yes |
| rainy | 71 | 91 | TRUE | no |
Outlook和Windy取离散值，Temperature和Humidity则取连续值。
对于离散属性V，ID3中计算的是“信息增益”，C4.5中则计算“信息增益率”:
vj表示属性V的各种取值，在ID3中用信息增益选择属性时偏向于选择分枝比较多的属性值，即取值多的属性，在C4.5中由于除以了H(V)，可以削弱这种作用。
C4.5是如何处理连续属性的呢？实际上它先把连续属性转换为离散属性再进行处理。虽然本质上属性的取值是连续的，但对于有限的采样数据它是离散的，如果有N条样本，那么我们有N-1种离散化的方法：<=vj的分到左子树，>vj的分到右子树。计算这N-1种情况下最大的信息增益率。
在离散属性上只需要计算1次信息增益率，而在连续属性上却需要计算N-1次，计算量是相当大的。有办法可以减少计算量。对于连续属性先进行排序，只有在决策属性发生改变的地方才需要切开。比如对Temperature进行排序
本来有13种离散化的情况，现在只需计算7种。如果利用增益率来选择连续值属性的分界点，会导致一些副作用。分界点将样本分成两个部分，这两个部分的样本个数之比也会影响增益率。根据增益率公式，我们可以发现，当分界点能够把样本分成数量相等的两个子集时（我们称此时的分界点为等分分界点），增益率的抑制会被最大化，因此等分分界点被过分抑制了。子集样本个数能够影响分界点，显然不合理。因此在决定分界点是还是采用增益这个指标，而选择属性的时候才使用增益率这个指标。这个改进能够很好得抑制连续值属性的倾向。当然还有其它方法也可以抑制这种倾向，比如MDL。
Tree-Growth终止的条件以及剪枝策略很多，在CART树中已讲了一些。每个叶子上都是“纯的”不见得就是好事，那样会过拟合。还有一个方法是叶子节点上覆盖的样本个数小于一个阈值时停止Tree-Growth。
在《CART树》中介绍了基于代价复杂性的剪枝法，剪枝的目的也是为了避免过拟合。
第一种方法，也是最简单的方法，称之为基于误判的剪枝。这个思路很直接，完全的决策树不是过度拟合么，我再搞一个测试数据集来纠正它。对于完全决策树中的每一个非叶子节点的子树，我们尝试着把它替换成一个叶子节点，该叶子节点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替，这样就产生了一个简化决策树，然后比较这两个决策树在测试数据集中的表现，如果简化决策树在测试数据集中的错误比较少，并且该子树里面没有包含另外一个具有类似特性的子树（所谓类似的特性，指的就是把子树替换成叶子节点后，其测试数据集误判率降低的特性），那么该子树就可以替换成叶子节点。该算法以bottom-up的方式遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。
第一种方法很直接，但是需要一个额外的测试数据集，能不能不要这个额外的数据集呢？为了解决这个问题，于是就提出了悲观剪枝。悲观剪枝就是递归得估算每个内部节点所覆盖样本节点的误判率。剪枝后该内部节点会变成一个叶子节点，该叶子节点的类别为原内部节点的最优叶子节点所决定。然后比较剪枝前后该节点的错误率来决定是否进行剪枝。该方法和前面提到的第一种方法思路是一致的，不同之处在于如何估计剪枝前分类树内部节点的错误率。
把一颗子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。对于一颗叶子节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N。这个0.5就是惩罚因子，那么一颗子树，它有L个叶子节点，那么该子树的误判率估计为。这样的话，我们可以看到一颗子树虽然具有多个子节点，但由于加上了惩罚因子，所以子树的误判率计算未必占到便宜。剪枝后内部节点变成了叶子节点，其误判个数J也需要加上一个惩罚因子，变成J+0.5。那么子树是否可以被剪枝就取决于剪枝后的错误J+0.5在
的标准误差内。对于样本的误差率e，我们可以根据经验把它估计成各种各样的分布模型，比如是二项式分布，比如是正态分布。
那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率（误判率）为e（e为分布的固有属性,可以通过统计出来），那么树的误判次数就是伯努利分布，我们可以估计出该树的误判次数均值和标准差：
把子树替换成叶子节点后，该叶子的误判次数也是一个伯努利分布，其概率误判率e为(E+0.5)/N，因此叶子节点的误判次数均值为
使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但是使用校正后有误差计算方法却并非如此，当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝：
这个条件就是剪枝的标准。
当并不一定非要大一个标准差，可以给定任意的置信区间，我们设定一定的显著性因子，就可以估算出误判次数的上下界。
比如T4这棵子树的误差率：
子树误差率的标准误差：
子树替换为一个叶节点后，其误差率为：
因为，所以决定将子树T4替换这一个叶子节点。