决策树是一种用于分类和预测的机器学习算法。它可以从已知数据中构建一棵树，其中每个分支节点都表示一个属性或特征，每个叶子节点代表一个类别或结果。通过对未知数据进行分类或预测时，决策树使用这棵树来做出决策。
(资料图)
例如，一名女性相亲的决策过程就是典型的决策树决策。该女性通过年龄、长相、收入和是否公务员对决定是否和男性见面。假设这名女性对男性的要求是：30岁以下、长相帅并且是高收入者或中等收入的公务员，下图表示了女孩的决策逻辑。
在上述女性相亲的例子中，每个女性对男性的要求都不尽相同。例如，一些女性会优先考虑男性的长相，而另一些则会优先考虑年龄。那么就存在一个问题，选择哪个特征作为当前的决策点？
信息增益（information gain）就能够很好帮助我们优先选择哪个特征。
1. 熵
在概率统计中，熵（entropy）表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为：
那么随机变量X的熵定义为：
熵越大随机变量的不确定性越大，就更难分类。例如，在抛硬币的例子中，熵为1，此时随机变量的不确定性最大。如果让你猜下一次硬币的正反面，可能没什么把握。但是如果这枚硬币是特制的，正面的概率是0.9，反面的概率是0.1，那么下一次猜正面肯定会更有把握，也就是说随机变量的不确定性变小了。
其实我们可以发现熵其实就是的数学期望，至于为什么选择log函数？
信息量应该依赖于概率分布，所以说熵的定义应该是概率的单调函数。
假设两个随机变量是相互独立的，那么分别观测两个变量得到的信息量应该和同时观测两个变量的信息量是相同的。
信息量应该要大于0
信息量应当连续依赖于概率变化。
可以证明满足以上条件的函数形式是唯一的，当然还可以乘上任意常数。
2. 条件熵
设有随机变量（X,Y），其联合概率分布为：
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，定义为X给定条件下Y的条件概率分布的熵的期望。
3. 信息增益
信息增益表示得知特征X的信息而使得Y的不确定性减少的程度，特征A对训练数据集D的信息增益定义如下：
很明显，信息增益越大说明该特征A具有更强的分类能力，就是更有把握把数据分类。所以通过计算每个特征的信息增益，最后选择那个最大的特征作为当前决策特征即可。
使用信息增益来选择特征，构建一棵决策树。基本步骤如下：
输入：数据集D，特征集A，信息增益阈值ɛ
输出：决策树T
若D中所有实例的类别相同，则T为单节点树，将该类别作为节点类别。返回T
若A为空集，则T为单节点树，把最大投票类别作为节点类别。返回T
否则，计算信息增益，选择特征Ag
如果信息增益小于ɛ，则T为单节点树，把最大投票类别作为节点类别。返回T
否则，根据Ag的每一个取值，将D切割成若干非空子集，继续对每个子集按特征集合 继续构建子树(递归调用1~5)。返回T
1. 数据结构设计
2. 树的构建
3. 训练和测试
Mnist数据集必须要经过灰度处理，因为测试集中特征值可能会出现新的值，目前只支持了特定离散特征值的实现。
测试，使用序列化保存决策树
最后测试结果错误率在0.1079，上述实现中并没有做阈值判断。关于阈值如何选择还有待进一步学习！
关键词：
