[学习笔记]机器学习实战（三）
第3章 决策树
我们经常使用决策树处理分类问题，近来的调查表明决策树也是最经常使用的数据挖掘算法。
决策树可以使用流程图来理解。
矩形代表判断模块(decision block)，椭圆形代表终止模块(terminating block)，表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作分支(branch)，它可以到达另一个判断模块或者终止模块。
上一章介绍的kNN可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，而决策树的主要优势就在于数据形式非常容易理解。决策树的一个重要任务就是理解数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，这些机器根据数据集创造规则的过程，就是机器学习的过程。
3.1 决策树的构造
在构造决策树时，首先需要考虑的就是，当前数据集上的哪个特征在划分数据分类时起决定性作用，因此需要评估每个特征。之后原始数据集就被划分为几个数据子集，这些子集会分布在第一个决策点的所有分支上，而若某分支下的数据属于同一类型，则无需进一步对数据集进行分割，否则继续划分，直到所有具有相同类型的数据均在一个数据子集内。
3.1.1 信息增益
划分数据集的大原则是将无需的数据变得更加有序。组织杂乱无章数据的一种方法就是使用信息论度量信息，信息论是量化处理信息的分支科学。我们可以在划分数据之前或之后使用信息论量化度量信息的内容。
几个概念：
- 熵：体系的混乱的程度，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。
- 信息：如果带分类的事物可能划分在多个分类之中，则符号的信息定义为
- 信息熵（香农熵）： 是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。例如：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。它定义为信息的期望(取值×取值的概率)
- 信息增益： 在划分数据集前后信息发生的变化称为信息增益。
感觉贴代码没有什么意义，理解代码也没有遇到什么困难，暂时先不贴了，后面遇到坑了再说
3.1.2 划分数据集
前面提到了如何度量数据集的无序程度和如何计算信息熵，我们先计算原始数据集的信息熵，再对每个特征划分数据集的结果计算一次信息熵，就能得出每个特征划分数据集对应的信息增益，选择值最大的，作为最好的特征。
3.1.3 递归构建决策树
目前我们已经学习了从数据集构造决策树算法所需要的自功能模块，其工作原理如下：
1. 得到原始数据集
2. 基于最好的特征划分数据集，由于特征取值可能多于两个，因此可能存在大于两个分支的数据集划分。
3. 第一次划分后，数据将被向下传递到树分支的下一个节点，就可以再次划分数据
4. 递归处理数据集
5. 结束递归：遍历完所有划分数据集的特征，或每个分支下的所有实例都具有相同的分类
C4.5和CART在运行时并不总是在每次划分分组时都会消耗特征。