决策树理论部分学习笔记

决策树的理解，理解了，数字代表是变量，如 $X_{i}$ ，第 $i$ 个变量。考虑之后可以复盘、做图。

输入一个数据

根据数据的某个特征来把数据分成好几份

如果分完数据后发现

大概就这三步。可以发现，大部分时间都是根据某个“准则” ²来进行操作的，所以怎样选择这个准则就成了至关重要的问题。

为什么定义 $\frac{e n t_{N}}{l e n (l a b e l)}$ ，因为 $N = 1, . ., N$ 表示是改节点变量 $X$ 的level情况。 len(label)表示数据表的行数。

这个没看懂，但是不重要，往后走！

信息增益。这是决策树生长的重点，但有了上面两个函数之后，根据定义的话、直接条件熵减去熵就行（或者更宽泛地说、是混乱程度减去条件混乱程度），最多再做一些小的改动。

最后分的最干净，也是最理想的方式。这里面没讲什么。

所以，如果条件熵 $H (Y | A)$ 越小，就意味着 $Y$ 被 $A$ 分开后的总的混乱程度越小、从而意味着 $A$ 更能够帮助我们做出决策。

$H (Y | A) = - \sum_{i = 1}^{n} p_{i} \sum_{k = 1}^{K} p_{i, k} \log_{2} p_{i, k}$

信息增益:

$g (Y, A) = H (Y) - H (Y | A)$

因此信息增益低，说明不需要再 $| A$ 了。

根据信息增益判断是否终止（比如在 ID3 中，如果信息增益小于阈值的话就直接终止。这种判断方法会有比较严重的缺陷。

prune 函数: 核心思想其实就是把该 node 变成一个 leaf 。

Python具体的code不太清楚，但是至少现在决策树的理论部分、node、leaf、prune(node $\to$ leaf)、信息增益都搞懂了。

决策树理论部分 学习笔记