决策树 Decision Tree, DT
一般的，一颗决策树包含一个根节点、若干个内部节点和若干个叶节点；叶节点对应于决策结果，其他每个结果则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集。从根节点到每个叶节点的路径对应于一个判定测试序列。
决策树的直观解释：将数据根据其特征分布划分到不同的区域，使得同一个区域的样本有尽可能一致的类别标签。
每次数据划分衡量标准：
- 决策树的分支节点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。
- 信息增益是衡量数据划分的指标
信息增益：
- 信息熵：度量样本集合纯度最常用的一种指标
假定当前样本集合D中第 k 类样本所占的比例为Pk(k=1,2,……，|y|),则D的信息熵定义为
Ent(D)的值越小，则D的纯度越高
2. 信息增益：划分属性选择指标
假定离散属性α有V个可能的取值,若使用α来对样本集D进行划分，则会产生V个分支节点，其中第
个分支节点包含了D中所有在属性α上取值为
的样本，标记为
，计算出
的信息熵。考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重
，即样本数越多的分支结点的影响越大。计算出用属性α对样本集D进行划分所获得的“信息增益”：
一般而言，信息增益越大，则意味着使用属性α来进行划分所获得的“纯度提升”越大。因此，用信息增益来进行决策树的划分属性选择。
构建决策树的实际例子：
目标：该决策树用以学习一颗能预测没有刨开的瓜是不是好瓜？
-
计算根节点（好瓜）的信息熵：包含D中的所有样例（是、否）即 |y|=2，其中正例 P1=8/17，反例 P2=9/17。根节点的信息熵为：
- 计算当前每个属性的信息增益：
以属性“色泽”为例，它有3个可能的取值：{青绿、乌黑、浅白}。若使用该属性对D进行划分，则可得到3个子集，分别记为：D1{色泽=青绿}，D2={色泽=乌黑}，D3={色泽=浅白}。 子集D1包含编号为{1,4,6,10,13,17}的6个样例，其中正例占p1=3/6，反例占p2=3/6。计算用“色泽”划分之后所获得的3个分支结点的信息熵为：
计算属性“色泽”的信息增益为：