decision tree

决策树，说白了就是根据一系列if-else语句对空间构成的一个分划(parition)。每次分划都根据样本点的某一个特征作为依据。我们最直观的目标是让决策树越矮越好。可以想象，如果在某一层我们选择了某个特征，但是这个特征导致的分类结果和我们直接随机分类的结果如果是相同的话，那么我们认为这个特征是没有分类能力的，为了避免选择这样的特征，我们需要利用信息论中的一点知识，保证选出的特征能够有良好的分类能力（最好是一次性分完hhh）。

information gain

我们需要对每个特征进行信息增益的评价，然后选择其中最优的。计算特征A对训练数据集D的信息增益\(g(D, A)\)的方法是： $$ g(D, A) = H(D) - H(D, A) $$ 熟悉信息论的人可以马上知道，熵\(H(D)\)和\(H(D|A)\)的差就是互信息。

感性理解一下这个式子，熵描述了这个随机变量（在这里就是数据集D，关于随机变量的理解还是去看看probability部分的notes吧）不确定的程度。通过得到A的信息，我们让D的不确定性减小了。

所以算法的思路也非常清晰了，我们只需要每次都对还未用于分类的特征进行扫描，然后选取信息增益最大的那个。至于具体的计算还是参照课本吧。

information gain ratio

如果真的以信息增益作为划分特征选取的指标，那么实际上存在问题。如果一个特征的取值较多，那么会导致其信息增益虚高，所以更好的方法是利用信息增益比： $$ g_R(D, A) = \frac{g(D, A)}{H_A(D)} $$ 其中，\(H_A(D) = -\sum_{i=1}^{n}{\frac{D_i}{D}log_2\frac{D_i}{D}}\), n 是特征A取值的个数

反正这个地方我认为是我对信息论理解还不够，所以还没完全搞懂。希望以后能加深理解。

pruning

大部分情况下，我们不需要把所有不同的类都完全划分开（因为noise是不可避免的），但是按照我们的算法得到的决策树是会把所有的类都划分开的。所以我们就采取剪枝的策略。我们先计算每个叶节点的经验熵（下面介绍），然后从树的叶节点开始向上回溯，来计算整体树的某个损失函数（下面介绍）是否会降低，如果降低了，那就剪枝，直到无法继续停止。

某个叶节点的经验熵，实际上和之前计算整个数据集D的熵差不多，这次把D换成那个节点的数据集合就行了。这是合理的，因为一个节点里面如果全都是同一类的点，那么熵最小，也是我们最喜欢的。如果所有类的数据都很均匀，说明这个节点的信息量基本没有，那么我们实际上不喜欢。

损失函数，整棵树的损失函数就是所有叶节点的经验熵之和，加上一个正则项（某个系数乘以整棵树叶节点的个数）。为什么定义这个函数为损失函数？第一项很好理解，因为让所有节点的经验熵变小，也就是分类得很完善。如果只有第一项，那么这个损失函数就等价于极大似然估计。但是我们要考虑noise的存在，避免过拟合，所以我们需要第二个正则项，让叶子节点尽量少，这样的话，我们能够在一定程度上防止过拟合，并且我们的决策树也会变得更加简单。

remark： 1. 决策树生成的过程中，每个特征最多被使用一次。 2. 不考虑剪枝的情况下，我们在决策树生成的时候，还是有可能出现最后的叶节点中存在不同类的数据（首先其实我们的算法里面有输入阈值，如果选出来的特征的信息增益比小于这个阈值了，就停止；然后我们的数据可能存在noise，意味着特征完全相同的两个点，也有可能有相同标签。）