[机器学习实战札记]决策树

决策树(decision tree)是一类常见的机器学习方法。顾名思义&＃xff0c;决策树是基于树结构来进行决策的&＃xff0c;这恰是人类在面临决策问题时一种很自然的处理机制。一颗决策树包含一个根节点、若干个内部节点和若干个叶节点。叶节点对应于决策结果&＃xff0c;其他每个节点则对应于一个属性测试。

决策树学习的目的是从样本数据产生一颗泛化能力强的决策树&＃xff0c;其基本流程遵循简单且直观的“分而治之”策略&＃xff1a;

Function createBranch检测数据集中的每个子项是否属于同一分类&＃xff1a;If so return 类标签Else寻找划分数据集的最好特征划分数据集创建分支节点for 每个划分的子集调用createBranch并增加返回结果到分支节点中return 分支节点


算法有两个要点&＃xff1a;

1. 寻找划分数据集的最好特征
2. 递归

划分数据集的大原则是&＃xff1a;将无序的数据变得更加有序。组织杂乱无章数据的一种方法就是使用信息论度量信息&＃xff0c;信息论是量化处理信息的分支科学。

在划分数据集之前和之后信息发生的变化成为信息增益&＃xff0c;获得信息增益最高的特征就是最好的选择。

“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。其定义为&＃xff1a;

其中p(xi)是选择该分类的概率&＃xff0c;n是分类的数目。分类的概率可以用所有类标签的发生频率来计算。

对每个特征划分数据集的结果计算一次信息熵&＃xff0c;然后判断按照哪个特征划分数据集是最好的划分方式。

得到原始数据集&＃xff0c;然后基于最好的属性值划分数据集&＃xff0c;由于特征值可能多于两个&＃xff0c;因此可能存在大于两个分支的数据集划分。第一次划分之后&＃xff0c;数据将被向下传递到树分支的下一个节点&＃xff0c;在这个节点上&＃xff0c;我们可以再次划分数据&＃xff0c;可以采用递归的原则处理数据集。

递归结束的条件是&＃xff1a;程序遍历完所有划分数据集的属性&＃xff0c;或者每个分支下的所有实例都具有相同的分类。

本章使用的算法成为ID3&＃xff0c;无法直接处理数值型数据&＃xff0c;尽管我们可以通过量化的方法将数值型数据转化为标称型数值&＃xff0c;但如果存在太多的特征划分&＃xff0c;ID3算法仍然会面临其他问题。

参考

1. 《机器学习实战》, p32 ~ 52
2. 《机器学习》, p73 ~ 79