第三章 决策树(代码)
-
决策树算法优缺点
优点:计算复杂度不高，输出结果易于理解，对中间值不明干，可以处理不相关特征数据。
缺点:可能会产生过度匹配。
范围:数值型和标称型。
-
决策树的一般流程
收集数据
准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化
分析数据：可以使用任何方法，构造树完成之后，应该检查图形是否符合预期
训练算法：使用经验树计算错误率
使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义
-
信息增益
原则: 将无序的数据变得更加有序。
在划分数据集之前之后信息发生的变化
熵: 信息的期望值，或者集合信息的度量方式。
-
熵
若数据都为一类，那么
H=-1*log2(1)=0，不用任何信息就能区分这个数据。如有一枚正反两面硬币，分为正面或者反面的概率都为
0.5, H= -0.5log2(0.5) - 0.5log2(0.5) = 1,需要一个单位比特信息区分是否是正面或者反面，也即0或者1。熵，代表信息的混乱度信息。其基本作用就是消除人们对事物的不确定性。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个度量。
具体地可参考《信息论》。
-
划分数据集
将每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。
-
递归构建决策树
工作原理：得到原始数据集，基于最好的属性值划分数据集，第一次划分后，再次划分数据。因此可以递归处理数据集。
递归结束的条件：划分数据集所有属性，或者每个分支下的所有实例都具有相同的分类。
如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们通常采用多数表决的方法决定该叶子节点的分类。
-
测试算法:使用决策树执行分类
执行分类时，需要使用决策树以及用于决策树的标签向量。
测试数据与决策树上的数值，递归执行该过程直到进入叶子节点。
最后将测试数据定义为叶子节点所属的属性。
-
使用算法:决策树的存储
为了节约时间和节省内存消耗，使用了pickle模块序列化对象。
-
例子:使用决策树预测隐形眼睛类型
目标:通过决策树预测患者需要佩戴的隐形眼睛类型。
import trees fr = open('lensens.txt') lenses = [inst.strip().split('\t') for inst in fr.readlines()] lenseslabels = ['age', 'prescipt', 'astigmatic', 'tearRate'] lensestree = trees.create_tree(lenses, lenseslabels) lensestree treePlotter.create_plot(lensestree) -
小节
这里主要是采用
ID3算法划分数据集，用递归的方法将数据集转化为决策树，并可用pickle模块存储决策树的结构。ID3算法无法处理直接数值型数据，需要将其化为标量型数值。决策树最大的缺点在于过拟合问题。在构建树的时候，其能够完全匹配实验数据，但是这并不是我们想要的，为此，可以删掉一些只增加了很少信息的节点，将其并入到其他叶子节点中，或者裁剪一些分支。具体决策树的很多问题也待整理。
