决策树（Decision Tree）
基本概念
-
由很多“树”组成，是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。
-
包含了一个根结点，若干个内部结点和若干个叶结点；
- 叶结点对应于决策结果，其他每个结点则对应于一个属性测试
- 每个结点包含的样本集合根据属性测试的结果被划分到子结点中
- 根结点包含样本全集
- 从根结点到每个叶结点的路径对应了一个判定测试序列
学习目的
- 产生一棵泛化能力比较强，处理未遇见的示例能力强的决策树。也就是说，根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。
伪代码
划分选择
-
问题提出
- 如何获得最优划分属性
-
信息熵（information entropy）
- 度量样本集合纯度的常用指标
- 公式：
-
信息增益（information gain）
-
基本定义和解释
-
意义
- 信息增益越大，则意味着使用属性a来进行划分所获得的纯度提升越大。
-
结论
- 可以使用信息增益来进行决策树的划分属性选择，即
-
计算步骤（示例）
- １、先计算所有样例的正反例的比例，得出根结点的信息熵
- ２、计算其他每个属性集合的信息增益（需要先计算出每个属性的信息熵）
- ３、信息增益最大的就被选为划分属性，成为了根结点的划分
- ４、再对分支节点进一步进行划分（划分属性集合的信息），划分后对每个结点再次计算信息增益
- ５、再根据信息增益最大的被选为划分属性，如此重复上述步骤。对每个分支节点进行操作
-
-
增益率（gain ratio）
-
提出问题
- 信息增益准则对可取值数目较多的属性有所偏好，会带来不利的影响
-
基本概念
- 对可取值数目较少的属性有所偏好
- 属性ａ为“固有值”（intrinsic value）。属性ａ的可取值数目越多（Ｖ越大），则IV(a)的值通常也会越大。
-
特点
-
并不直接选择增益率最大的候选划分属性，而是使用了一个启发式
- 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的
-
-
-
基尼指数（Gini index）
-
基本概念
- 用基尼值带度量数据集Ｄ的纯度
-
公式
-
说明
- 反映了从Ｄ中随机抽取两个样本，其类别标记不一致的概率。所以，Gini(D)越小，数据集Ｄ的纯度越高。
-
属性的基尼指数计算
- 在属性集合Ａ中，选择使的划分后基尼指数最小的属性作为最优划分属性
-
PS
后续会把这章没看完的补全
Reference
【1】周志华. Machine Learning 机器学习