搜索
《IntroductionofDecisionTrees》读后心得论文首先讲了决策树算法的起源与发展，然后通过PlayTennis这个例子详细介绍了ID3算法。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。布尔型熵定义:V个状态分类后熵的期望值：属性A相对于集合S的信息增益：ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个节点，并以该节点的属性标记，对该属性的每个值创建一个分支据此划分样本。同时还介绍了数据中出现噪音或损坏对分类的影响，并通过研究树的构造过程，控制分类条件处理噪音或者损坏的值。对于未知属性这一问题，一种方法是利用上下文提供的信息填充未知值，另一种就是把把“未知”作为一个新的可能值，为每个属性和处理它以同样的方式作为其他价值，而不是试图猜测未知的属性值。ID3通过循环处理，逐步求精，直至找到完全正确的决策树。ID3算法不存在无解的危险；全盘使用训练数据，而不是像侯选剪除算法逐个地考虑训练例，从而抵抗噪音。ID3算法缺点：ID3倾向于选择取值较多的属性，却不是最优的属性，这样就有可能得到局部最优解而失去全局最优解；在搜索过程中无回溯；ID3不能增量的接受训练集，每增加一次实例就抛弃原有的决策树，重新构造新的决策树，开销很大。针对ID3算法的缺点，进一步提出了C4.5算法。C4.5在ID3基础上引进分割信息量这个概念，其定义如下：信息增益率度量是用前面的增益度量Gain(S，A)和分割信息度量SplitInformation(S，A)来共同定义的C4.5利用信息增益率选择属性，克服了ID3中多值属性偏向问题。同时对于ID3算法中不能处理连续型属性值的问题，C4.5采用分区的方法将连续值离散化。具体做法是对于属性值构成的区间[min,max],n个分断点Ai，分别计算各个分区的Gain值，选取Gain值最大的Ak作为断点，将属性设为[min,Ak]和[Ak,max]两个区间值。C4.5优缺点：利用C4.5可以优化树结构，提高决策树的生长速度，避免树过度增长和数据过度拟合，挖掘较好的规则信息。但在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。下面是ID3算法运行结果示例：数据集：结果：