机器学习—决策树（ID3,C4.5）算法解析

100 阅读 0 评论 66 点赞

我是靠谱客的博主能干衬衫，最近开发中收集的这篇文章主要介绍机器学习—决策树（ID3,C4.5）算法解析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Label 机器学习决策树解析

这里写图片描述
决策树实现思路：假设有已知的数据集X【例如某些人的集合，数据内容包括用于描述他们的特征属性及特征属性值，如性别（男|女），年龄（整数），收入（较低|中等|较高）等】，以及数据集的分类标签Y【是否是某俱乐部的成员（是|否）】，对数据集做特征属性测试【在当前可选的特征属性中选取最佳分裂属性，其评判标准为特征属性的度量值，一般越大越好，根据该度量值的计算不同，将决策树算法分为ID3和C4.5】，对数据集做属性分裂，其子类可再进行属性测试和属性分裂，直至可选属性为空或者子类不能分；不理解的概念参看本节备注
决策树是一种贪心算法，每次选取的分割数据的特征都是当前的最佳选择，并不关心是否达到最优。很容易在训练数据中生成复杂的树结构，造成过拟合（overfitting）。剪枝可以缓解过拟合的负作用，常用方法是限制树的高度、叶子节点中的最少样本数量。
1 ID3
ID3算法的核心思路是，在决策树的整体框架下，利用信息增益来作为属性度量值，取最大信息增益对应的特征属性作为最佳分裂属性对样本集做属性分裂；

以下引自：http://www.cnblogs.com/wxquare/p/5379970.html
【ID3决策树可以有多个分支，但是不能处理特征值为连续的情况。ID3算法十分简单，核心是根据“最大信息熵增益”原则选择划分当前数据集的最好特征，信息熵是信息论里面的概念，是信息的度量方式，不确定度越大或者说越混乱，熵就越大。在建立决策树的过程中，根据特征属性划分数据，使得原本“混乱”的数据的熵(混乱度)减少，按照不同特征划分数据熵减少的程度会不一样。在ID3中选择熵减少程度最大的特征来划分数据（贪心），也就是“最大信息熵增益”原则】

相关的定义：
信息熵： H(X)=−∑i=1Lpilog(pi) ； pi=|Xi||X| ；分子表示数据集X中属于最终标签下第i类的样本数，分母表示X的总样本数，L表示最终标签数（如是否为俱乐部成员，则L=2）；
期望信息： HA(X)=∑j=1LA|Xj||X|H(Xj) ；A表示某一特征属性，LA表示A特征属性下的类数（如收入，则LA=3）；
期望增益： gain(A,X)=H(X)−HA(X) ;
选取期望增益最大的特征属性为最佳分裂属性
缺点：信息增益选取属性时容易偏向取值多的属性。因为属性值多的Feature会有相对较大的信息增益：【信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大】

2 C4.5
C4.5算法的核心思路是，在决策树的整体框架下，利用信息增益比来作为属性度量值，取最大信息增益比对应的特征属性作为最佳分裂属性对样本集做属性分裂，为ID3的改进版；

特点：
1. 信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的Feature。
2. C4.5还弥补了ID3中不能处理特征属性值连续的问题。具体流程如下：
将样本数据该属性A上的具体数值按照升序排列（total个值），在上一步生成的序列值中生成total-1个分割点。第i个分割点的取值为Ai和Ai+1的均值，每个分割点都将属性序列划分为两个子集。计算每个分割点的信息增益,得到total-1个信息增益。对分裂点的信息增益进行修正：减去log2(N-1)/|D|，其中N为可能的分裂点个数，D为数据集合大小。选择修正后的信息增益值最大的分类点作为该属性的最佳分类点。计算最佳分裂点的信息增益率作为该属性的度量。选择度量最大的属性作为分类属性。

相关定义：
分裂信息： inferA(X)=−∑j=1LA|Xj||X|log2(|Xj||X|) ；
信息增益比： gain_ratio=gain(A,X)inferA(X)
选取期望增益比最大的特征属性为最佳分裂属性

备注：
什么是当前可选的特征属性：在第一次属性测试时，所有属性性别，年龄，收入等都为可选属性，若第一次选择收入作为最佳分裂属性，则第二次属性测试的可选属性就只有性别，年龄等了；
什么是属性分裂：就是根据选取出来的最佳分裂属性对数据集进行分类，加入最佳属性为性别，则将数据集中的人按男女分成两个子类；
什么是子类不能分：某一子类中的所有样本都属于同一个标签（如，全属于该俱乐部的成员）；
当可选属性为空时但子类仍能再分怎么办：一般采用多数表决，即使用该子类中标记最多的标签作为该类的标签；

可参考的同类博文：
1. http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
2. http://blog.csdn.net/dark_scope/article/details/13168827

Python实现
http://download.csdn.net/detail/xiequnyi/9608752