4.1基本流程

decision tree决策树的目的是为了产生一棵泛化能力强的树——用测试集检测泛化能力

如图4.1所示，从树的根结点，到叶子结点（也就是判别结果），其中一般会经过若干个中间结点，每个中间结点对应一个属性测试，例如图中的色泽属性，根蒂属性，敲声属性。其中根结点是包含样本全集的，每经过一个中间结点，则会根据中间结点属性测试的结果划分到子结点中。

其基本流程遵循**“分而治之”**divide and conquer策略
三种情形导致递归返回：
（1）当前结点包含的样本全属于同一类别，无需划分；（Y一样）
（2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；（X一样）
（3）当前结点包含的样本集合为空，不能划分（没有i了）

决策树的生成是一个递归过程。形象的来讲：决策树在生成过程中，从根结点开始，会一层一层往下延拓，生成更多的中间结点。
易知样本的属性类别（色泽，纹理，敲声）等有限，所以这颗决策树的层数（高度）以及每一层的中间结点数当然是有限的，而这个就依靠**“递归条件**”来限制这颗决策树的生成了。

在决策树的生成过程中，最重要的步骤之一就是步骤8，划分选择问题,这决定了这颗决策树的判别路径。

4.2划分选择

划分准则：让结点的“纯度”越来越高

如何判别纯度提升效果最优呢？：
1.信息增益 2.增益率结合信息增益 3.基尼指数

4.2.1信息增益（ID3决策树学习算法）

• 信息熵：一般来说，信息熵是用来量化信息的不确定性。
  假设当前样本集合D中第k类样本所占的比例为，则样本集合D的信息熵定义为：
  
  备注：|y|代表类别的数量
  Ent(D)越小，则D的纯度越高，集合的不确定性越小，信息熵越低。
• 信息增益information gain越大越好，意味着“纯度”提升更明显
  信息增益=信息熵-条件熵。
  设该属性为a，且a有V分可能取值
  即经过划分可以产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为，记该子集为$$D^v$$。
  对每个属性a对应的V个取值，计算出信息增益，进而比较出信息增益最大的那个属性a*
  信息增益越大，意味着在当前条件下，信息的不确定性减小的越多，不确定性越低，在本场景中就是样本的纯度越高。

因此我们就可以通过信息增益来进行决策树的划分属性选择，即在图4.2算法流程第8行选择属性$$a_{\ast }=argmaxGai{n}_{aϵA}^{}\left(D,a\right)$$

但是实际上，信息增益在一定程度上存在问题。例如集合D一共有100个样本，我们将样本从1-100进行编号。假如我们把编号也考虑进入属性划分选择，那么毫无疑问，编号带来的信息增益是特别高的。因为可想而知：一个样本一个编号，这个时候每个分支结点都只有一个样本，这已经是纯度最高的情况了。

换句话说，信息增益对属性多的有所偏好，此时增益会偏大。
所以引入了增益率。

4.2.2增益率（C4.5决策树算法的核心）

• 增益率 gain ratio

缺点：与信息增益方法相反，偏好可取值数目较少的属性

属性固有值在分母，显然增益率倾向于可取数目较少的属性。

• 综合信息增益和增益率，先从候选划分属性中找出信息增益高于平均水平的属性，再从中找出增益率最高的。

4.2.3基尼指数（CART决策树算法的核心算法）

数据集D的纯度可用基尼值度量：
Gini（D）反应了从数据集中抽取两个样本，其类别不一致的概率。因此基尼系数越大，则表示样本集合的纯度越低。

• a属性产生v个分支结点的总基尼系数定义为：
  
• 在候选属性集合中，选择那个使得基尼系数最小的作为最优划分属性。
• 再持续往下分叉，计算基尼系数，直到计算的结果没有分叉前的基尼系数大为止

例题：

#第一层
def gini_index_single(a,b):
    single_gini = 1 - ((a/(a+b))**2) - ((b/(a+b))**2)
    return round(single_gini,3)
gini_index_single(24+13,98+29)

#第二层
def gini_index(a,b,c,d):
    left = gini_index_single(a,b)
    right = gini_index_single(c,d)
    gini_index = left*((a+b)/(a+b+c+d)) + right*((c+d)/(a+b+c+d))
    single_gini = 1 - ((a/(a+b))**2) - ((b/(a+b))**2)
    print (single_gini)
    print (gini_index)
    return round(gini_index,3)
#a1属性-0.3
#gini_index(13,98,24,29)
#a2属性0.29
gini_index(24,25,13,102)

#结论：选第二层基尼系数更小的0.29

以下部分为平方误差最小原则——回归树问题——作为教材的补充
可以看.

4.3剪枝处理

• 用剪枝pruning解决“过拟合”，同时为了维持泛化能力，用测试集的精度判断是否剪枝

• 预剪枝 prepruning——能剪都剪掉
  ——自上而下，可能导致欠拟合

• 后剪枝 postpruning——能不剪就不剪 ——自下而上，欠拟合风险小，且泛化能力一般更高

4.3.1预剪枝

预剪枝的定义就是在决策树生成的过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分，并将当前结点标记为叶子结点。

我们可以认识到预剪枝是判断当前结点对于泛化性能的影响，并没有考虑当前结点的后续结点是否有机会能够提升泛化性能，这是一种“贪心”的本质。这个策略带来的问题就是有可能会丢失那些在后续确实能提高泛化性能的结点，因此预剪枝带来欠拟合的风险。

4.3.2后剪枝

后剪枝是发生于决策树生成完成以后，从由底至上考虑每个非叶节点，若将该结点替换为叶节点能够给决策树带来泛化性能的提升的话，则将该结点替换为叶节点。

因为后剪枝是在一棵完整的决策树的基础上从底至上考虑每个非叶节点，相对于预剪枝来说欠拟合风险很小，不过训练时间开销是比较大的。

4.4连续与缺失值

4.4.1连续值处理

• 前面讨论的划分选择问题，都是基于离散属性的。连续属性的我们用二分法 bi-partition将连续变量离散化——C4.5采用的机制

即连续属性a的信息增益是基于通过二分法将连续属性离散化后选出
最佳划分点的信息增益作为连续属性a的信息增益。

• 离散属性的划分中，作为当前结点划分依据的属性，再其分支结点将不再作为划分考虑。例如在判别西瓜的好坏分类中，我们第一个结点通过色泽分出了亮和暗，那么接下来这两个分支结点将不再考虑西瓜的色泽属性了。
• 而连续属性不同，连续属性例如通过二分法来离散化，划分重点不是”是什么“，而是”区间内属性值的大小关系“，这是可以多次划分多次比较的。例如在区间0到1，第一个结点是以t=0.5进行划分，得出两个分支结点v1,v2。 在v1中0到0.5，我们可以再次选定一个划分点t=0.25，再次划分出分支结点。

4.4.2缺失值处理

（1）如何在属性值缺失的情况下进行划分属性选择？

（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

（1）

假如100个样本中，属性a的缺失值高达99份，属性b的缺失值只有1个，属性c的缺失值有50个。假定他们在没有缺失值的情况下对于样本集合的纯度提升效果一样，那在存在前面缺失的情况下，哪个属性最可靠？
C4.5算法：按照该维度下无缺失值计算信息增益，然后再乘个系数（非缺失值/总数），就是最终的信息增益
（2）
若样本x在划分属性a上的取值已知，则将x划入与其对应的分支结点，并保持样本权重Wx不变。若样本x在划分属性a上的取值未知，则将样本x划入所有分支结点，且样本权重调整为*Wx。

4.5多变量决策树

想象一下，若我们把样本的每个属性都视为坐标空间中的一个坐标轴，则由d个属性描述的样本就对应了d维空间中的一个数据点。对样本的分类就意味着在这个坐标空间中寻找不同类样本之间的分类边界。而我们前面提到的决策树在d维空间中形成的分类边界有一个特点：轴平行，如图4.11所示，这个样本集的属性只包括两个连续属性（密度，含糖率），它的分类边界由若干个与坐标轴平行的分段组成的。


如图4.10以及4.11所示，在图4.10的决策树上有几个分支结点，对应图4.11则有几段关于轴平行的分类边界。这样的分类边界的确取得了很好的解释性，但是这仅仅是二维小样本容量上的应用。如果样本很复杂，是多维的大样本，那么必须通过很多很多段的划分才能取得较好的近似，例如图4.10中的决策树需要4段分类边界。通过多段的分类边界去划分，显然时间开销是很大的，因此假如我们不局限于平行与轴的分类边界，考虑使用斜的划分边界，如图4.12所示，此时就引入了“多变量决策树”。

“多变量决策树”与“普通决策树”相比，关键在于分支结点的属性测试的区别。“多变量决策树”的属性测试不再是单一的属性测试，而是对多个属性的线性组合进行测试。换句话说，对于分支结点的属性测试，我们不再是为每个结点寻找一个最优划分属性了，而是对每个分支结点建立一个合适的线性分类器，例如图4.10中的数据集，我们通过多变量决策树生成如图4.13所示的决策树，并且其分类边界如图4.14所示。
显然与“普通的决策树分类边界”相比，采用“多变量决策树”能够通过斜的划分边界取得较好的效果。

习题答案

1.试证明对于不含冲突数据(即特征向量完全相同但标记不同)的训练集，必存在与训练集一致(即训练误差为0)的决策树。

答：假设不存在与训练集一致的决策树，那么训练集训练得到的决策树至少有一个节点上存在无法划分的多个数据（若节点上没有冲突数据，那么总是能够将数据分开的）。这与前提-不含冲突数据 矛盾，因此必存在与训练集一致的决策树

2.试析使用"最小训练误差"作为决策树划分选择准则的缺陷

答：使用"最小训练误差"作为决策树划分选择准则，由于使用的是训练集数据，可能会将训练特征中的一些异常或者偶然作为模型的一部分，导致过度拟合的问题，而没有泛化能力。

3和4的python实现也可以参考 link.
4.3.试编程实现基于信息熵进行划分选择的决策树算法,并为表4.3中数据生成一棵决策树。
http://blog.csdn.net/icefire_ tyh/article/details/52081556
重写的不剪枝的决策树
http://blog. csdn.net/icefire_ tyh/article/details/54575527
即ID3算法

4.4.试编程实现基于基尼指数进行划分选择的决策树算法，并为表4.2中数据生成预剪枝、
答1:后剪枝决策树，并与未剪枝决策树进行比较。
http://blog.csdn.net/icefire tyh/article/details/52081879
即CART算法

答2:han1057578619/MachineLearning_Zhouzhihua_ProblemSets

未剪枝、后剪枝、预剪枝生成决策树分别如下，总体来说后剪枝会相比于预剪枝保留更多的分支。

有两个需要注意的地方。一个是在4.3中说过的，因为划分属性的信息增益或者基尼指数相同的原因，这个时候选择哪一个属性作为划分属性都是对的，生成决策树和书中不一致是正常的（书中第一个节点为“脐部”）。另外数据量这么小的情况下，常常会出现剪枝前后准确率不变的情况，原书中也提到这种情况通常要进行剪枝的，但是这道题中若进行剪枝，会出现只有一个叶节点的情况。为了画图好看点…所以都不无论在预剪枝还是后剪枝中，这种情况都会采取不剪枝策略。参考原书P82。

经过测试，在未剪枝的情况下，验证集上准确率为0.2857；后剪枝准确率为0.5714；预剪枝也为0.5714。

4.5.试编程实现基于对率回归进行划分选择的决策树算法，并为表4.3中数据生成一棵决策树。
http://blog.csdn.net/icefire_ tyh/article/details/52081770 .
思路:参考书p90-91的多变量决策树模型，这里我们将每个非叶节点作为一个对率回归分类器，输出为"是"、”否"两类,形成形如二叉树的决策树。

4.6.试选择4个UCI数据集，对上述3种算法所产生的未剪枝、预剪枝、后剪枝决策树进行实验比较，并进行适当的统计显著性检验。
答案一
简要的分析一下:
ID3算法基于信息熵增益，CART 算法则采用了基尼系数。两种划分属性选择均是基于数据纯度的角度，方法差距应该不大(CART 可能要好一点)。而对率回归进行划分选择，以斜划分的方式，实现了多变量参与划分，其模型决策边界更光滑。
相比于决策树的生成算法，剪枝操作更影响模型性能。
答案二
这里要对，上面三种实现的算法进行未剪枝，预剪枝，后剪枝做比较，对率回归划分就算了,都不知道是个什么情况，信息增益和基尼指数的差别并不大，其实就是为了比较未剪枝,预剪枝，后剪枝对测试样本的输出结果。显著性分析，对2种算法，3 种剪枝方式的错误数做方差分析，信息增益和基尼指数有显著区别是拒绝的，未剪枝，预剪枝，后剪枝有显著区别是接受的。

4.7.图4.2是一个递归算法，若面临巨量数据，则决策树的层数会很深，使用递归方法易导致“栈”溢出，试使用“队列”数据结构，以参数maxDepth控制数的最大深度，写出与图4.2等价、但不使用递归的决策树生成算法。
主要思路每一次循环遍历一层下节点(除去叶节点)，为每一个节点生成子节点，将非叶节点入队；用参数L保存每一层有多少个节点。下一次循环执行同样的步骤。直至所有的节点都叶节点，此时队列为空。具体如下：

输入：训练集D = {(x1, y1), (x2, y2)...(xm, ym)};
	  属性集A = {a1, a2... ad};
	  最大深度MaxDepth = maxDepth
过程：函数TreeDenerate(D, A, maxDepth)
1:  生成三个队列，NodeQueue、DataQueue、AQueue分别保存节点、数据、和剩余属性集;
2:  生成节点Node_root;
3:  if A为空 OR D上样本都为同一类别:
4:		将Node_root标记为叶节点，其标记类别为D中样本最多的类;
5: 		return Node_root;
6:  end if 
7:  将Node入队NodeQueue; 将D入队 DataQueue; 将A入队AQueue;
8:  初始化深度depth=0;
9:  初始化L = 1;	# L用于记录每一层有多少非叶节点。
10: while NodeQueue 非空:
11:		L* = 0
12:		for _ in range(L):			# 遍历当前L个非叶节点
13:			NodeQueue 出队Node; DataQueue出队D; AQueue 出队A;
14:			从A中选择一个最优划分属性a*;
15:			for a* 的每一个值 a*v do:
16:				新建一个node*，并将node*连接为Node的一个分支;
17:				令 Dv表示为D中在a*上取值为a*v的样本子集;
18:				if Dv为空:
19:					将node*标记为叶节点，其标记类别为D中样本最多的类;
20:					continue;
21:				end if
22:				if A\{a*}为空 OR Dv上样本都为同一类别 OR depth == maxDepth:
23:					将node*标记为叶节点，其标记类别为Dv中样本最多的类;
24:					continue;
25:				end if 			
26:				将node*入队NodeQueue; 将Dv入队 DataQueue; 将A\{a*} 入队AQueue;
27:				L* += 1;		# 用于计算在第depth+1 层有多少个非叶节点
28:		L = L*;
29:		depth += 1;
30:	return Node_root;
输入以Node_root为根节点的一颗决策树

4.8 试将决策树生成的深度优先搜索过程修改为广度优先搜索，以参数MaxNode控制树的最大结点数，将题 4.7 中基于队列的决策树算法进行改写。对比题 4.7 中的算法，试析哪种方式更易于控制决策树所需存储不超出内存。
4.7写的算法就是广度优先搜索的。这道题将MaxNode改为MaxDepth，只需要改几个地方。有一点需要注意的地方，就是在给一个节点生成子节点时（19-32行），可能造成节点数大于最大值的情况，比如某属性下有3种取值，那么至少要生成3个叶节点，这个时候节点总数可能会超过最大值，这时最终节点数可能会是MaxNode+2。

至于两种算法对比。个人理解当数据特征值，各属性的取值较多时，形成的决策树会趋于较宽类型的树，这时使用广度优先搜索更容易控制内存。若属性取值较少时，深度优先搜索更容易控制内存。对4.7中修改如下：

输入：训练集D = {(x1, y1), (x2, y2)...(xm, ym)};
	  属性集A = {a1, a2... ad};
	  最大深度MaxNode = maxNode
过程：函数TreeDenerate(D, A, maxNode)
1:  生成三个队列，NodeQueue、DataQueue、AQueue分别保存节点、数据、和剩余属性集;
2:  生成节点Node_root;
3:  if A为空 OR D上样本都为同一类别:
4:		将Node_root标记为叶节点，其标记类别为D中样本最多的类;
5: 		return Node_root;
6:  end if 
7:  将Node入队NodeQueue; 将D入队 DataQueue; 将A入队AQueue;
8:  初始化深度numNode=1;
9:  初始化L = 1;	# L用于记录每一层有多少非叶节点。
10: while NodeQueue 非空:
11:		L* = 0
12:		for _ in range(L):			# 遍历当前L个非叶节点
13:			NodeQueue 出队Node; DataQueue出队D; AQueue 出队A;
14:			if numNode >= maxNode:
15:				将Node标记为叶节点，其标记类别为D中样本最多的类;
16:				continue;
17:			end if;
18:			从A中选择一个最优划分属性a*;
19:			for a* 的每一个值 a*v do:
20:				numNode+=1
21:				生成一个node*，并将node*连接为Node的一个分支;
22:				令 Dv表示为D中在a*上取值为a*v的样本子集;
23:				if Dv为空:
24:					将node*标记为叶节点，其标记类别为D中样本最多的类;
25:					continue;
26:				end if
27:				if A\{a*}为空 OR Dv上样本都为同一类别:
28:					将node*标记为叶节点，其标记类别为Dv中样本最多的类;
29:					continue;
30:				end if 			
31:				将node*入队NodeQueue; 将Dv入队 DataQueue; 将A\{a*} 入队AQueue;
32:				L* += 1;		# 用于计算在第depth+1 层有多少个非叶节点
33:			end if;
34:		L = L*;
35:	return Node_root;

4.9 试将 4.4.2 节对缺失值的处理机制推广到基尼指数的计算中去.
使用书中式4.9、4.10、4.11有，对于原书中4.5式可以推广为：

属性a的基尼指数可推广为：

4.10从网上下载或自己编程实现任意一种多变量决策树算法，并观察其在西瓜数据集 3.0 上产生的结果
此处要求实现一种多变量决策树算法。实际上4.3与4.4题就是多变量决策树算法。其在西瓜数据集3.0上产生的结果如下