机器学习实战 第三章 决策树 学习笔记

    第三章，决策树，主要讲了用ID3这种算法构建出决策树，并将其用于分类的方法。

    原理：假设我们有一些待分类数据，那么可先按特征的某些规律将其一分为二（就成了二叉树，一分为n，就是n叉树），再将其子节点再分，分到不能再分时，训练结束。预测时按照分类的原则去找分支，直到找到叶子节点，叶节点的值就是预测的值。

    那么就会有一个问题：以何种规律来进行每一次划分？书上给出了明确的解答：按照信息熵值，即信息增益值最高的划分方法来划分！

l(xi)=-log2p(xi)#l(xi)即是xi的信息，p(xi)是选到xi的概率
           

    这里可以多解释一句，假设有[1,2,3,3,3]这么一组5个数，那么选到3的概率就是五分之三，0.6。选到另外两数的概率都是五分之一。

    有了信息的定义，我们就可以算信息增益，也就是熵 了。

H=-[求和：i从1加到n]{p(xi)log2p(xi)}#这里H就是熵，求和符号不好打……
           

    有了这个公式，我们就能在所有可能的划分情况中找出最优的一种（也就是熵最高的那种）。然后每次都用最优划分来将现有数据分为二叉，一棵二叉树就这么完成了。

    书上的代码是用字典来存储二叉树结构的。以书上海洋生物是否是鱼类的问题为例，树结构如下：{是否有鳍：{无：不是鱼类，有{是否有脚蹼：{无：不是鱼类，有：是鱼类}}}}。书上有绘好的树形图，就不附了。

具体流程如下：

对整个数据集
通过计算香农熵的方法找到当前最优划分方式；
用此方式划分
若还有未划分特征，返回第二行