《机器学习》课后习题–周志华
4.1 试证明对于不含冲突数据(即特征向量完全相同但标记不同)的训练集，必存在与训练集一致(即训练误差为 0) 的决策树。
答：
从原书p74的图4.2的决策树学习的基本算法可以看出，生成一个叶节点有三种情况：
- 节点下样本 $D$ 全属于同一类样本 $C$，则将当前节点作为 $C$类叶节点。
- 属性集 $A=\oslash$，或者样本在当前属性集上取值相同。即特征用完了（当只剩最后一个特征时，进一步分裂，只能将各取值设立叶节点，标记为样本最多的类别。），或者的样本在 $A$ 上取值都相同（感觉这里貌似和第一条重复了）。这时取 $D$ 中最多的类作为此节点的类别标记。
- 在某一节点上的属性值 $a_{\ast}^{v}$ ，样本为空，即没有样本在属性 $a_{\ast}$ 上取值为 $a_{\ast}^{v}$ 。同样取 $D$ 中最多的类作为此节点的类别标记。
在这道题中，目标是找出和训练集一致的决策树，所以不必考虑第3点，从1、2情况来看出决策树中树枝停止“生长”生成叶节点只会在样本属于同一类或者所有特征值都用完的时候，那么可能导致叶节点标记与实际训练集不同时只会发生在特征值都用完的情况（同一节点中的样本，其路径上的特征值都是完全相同的），而由于训练集中没有冲突数据，那每个节点上训练误差都为 0。
- 贪婪学习
- 决策树停止生长的条件
- 实验：对任意数据集，是否一定能生成训练集上误差为 0 的决策树？
4.2 试析使用”最小训练误差”作为决策树划分选择准则的缺陷。
答：
这道题暂时没想出答案。在网上找了其他的答案，都是认为会造成过拟合，没给出具体证明。
而我的理解决策树本身就是容易过拟合的，就算使用信息增益或者基尼指数等，依旧容易过拟合，
至于使用“最小训练误差”会不会“更容易”过拟合暂时没理解明白。
- 决策树划分选择准则，有哪些，有什么区别及优缺点？
- sklearn.tree.DecisionTreeRegressor 中 criterion 参数取值
mse, friedman_mse, mae。原理及区别
4.3 试编程实现基于信息熵进行划分选择的决策树算法，并为表 4.3 中数据生成一棵决策树。
答：
因为数据集的原因，数据量比较小，在选择划分属性的时候会出现特征的信息增益或者信息增益率相同的情况。
所有生成的决策树和书中可能不一致。并且在生成叶节点时，会出现两类数量一致的情况，这时候叶节点就随机设置一个分类了。
代码实现了以信息增益、增益率、基尼指数划分准则。下面一道题（4.4）也是用相同的代码。
另外画图的代码是主要参考《机器学习实战》决策树那一章画图源码。
有些地方代码有点乱，比如进行剪枝的部分就有大量重复代码；并且预剪枝部分可以在生成决策树的时候实现，减少计算量。以后有机会再优化一下。
代码在：4.3-4.4
生成决策树如下：
4.4 试编程实现基于基尼指数进行划分选择的决策树算法，为表 4.2 中数据生成预剪枝、后剪枝决策树并与未剪枝决策树进行比较.
答：
代码在：4.3-4.4
未剪枝、后剪枝、预剪枝生成决策树分别如下，总体来说后剪枝会相比于预剪枝保留更多的分支。
有两个需要注意的地方。一个是在4.3中说过的，因为划分属性的信息增益或者基尼指数相同的原因，
这个时候选择哪一个属性作为划分属性都是对的，生成决策树和书中不一致是正常的（书中第一个节点为“脐部”）。
另外数据量这么小的情况下，常常会出现剪枝前后准确率不变的情况，原书中也提到这种情况通常要进行剪枝的，
但是这道题中若进行剪枝，会出现只有一个叶节点的情况。为了画图好看点…所以都不无论在预剪枝还是后剪枝中，这种情况都会采取不剪枝策略。参考原书P82。
经过测试，在未剪枝的情况下，验证集上准确率为0.2857；后剪枝准确率为0.5714；预剪枝也为0.5714。
未剪枝：
后剪枝：
预剪枝：
- 实验：预剪枝、后剪枝决策树并与未剪枝决策树进行比较
4.5 试编程实现基于对率回归进行划分选择的决策树算法，并为表 4.3 中数据生成一棵决策树.
答：
这个没实现。 一种思路就是拟合对率回归后，从所有特征中选择一个 w 值最高的一个特征值，即权重最高的一个特征值作为划分选择，
但是没想好对于 One-hot 之后的特征权重怎么计算，比如“色泽”有三种取值“乌黑”、“青绿”、“浅白”，在One-hot之后会有三个特征，
那么最后“色泽”这个特征的权重应该是取平均值？以后有机会….也不填坑。
- 对率回归
4.6 试选择 4 个 UCI 数据集，对上述 3 种算法所产生的未剪枝、预剪枝、后剪枝决策树进行实验比较，并进行适当的统计显著性检验.
答：
只拿sklearn中自带的iris数据集试了一下剪枝后的准确率，发现不同随机数种子（使得数据集划分不同）导致最后验证集的准确率变化挺大。
统计显著性检验没实现。
代码在这
- 统计显著性检验
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式可以推广为：
$Gini(D) =1-\sum_{k=1}^{\left| y \right|}\tilde{p_{k}}^{2}$ ，属性a的基尼指数可推广为：
$Gini_index(D, a)=p\times Gini_index(\tilde{D}, a) =p\times\sum_{v=1}^{V}\tilde{v}Gini(D^{v})$ 。
4.10 从网上下载或自己编程实现任意一种多变量决策树算法，并观察其在西瓜数据集 3.0 上产生的结果
答：
待补充。
- 多变量决策树算法
