决策树入门篇

前言：分类是数据挖掘中的主要分析手段，其任务就是对数据集进行学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号，把类标号未知的样本按照某一规则映射到预先给定的类标号中。

分类模型学习方法其中一类就是基于决策树的学习方法，下面，简单总结一下决策树的基础知识和构造决策树的两种算法：ID3、C4.5。

关键词：决策树、ID3、C4.5、信息熵、信息增益、分裂信息、信息增益率

正文

决策树分类的方法的特点是对训练样本集进行训练，生成一颗二叉或多叉的决策树。

ID3算法：使用信息增益作为属性选择标准。首先检测并计算所有的属性，然后选择信息增益最大的属性作为决策树节点，由该属性的不同取值建立分支，再对各分支的子集采取相同的信息增益计算方法后继续选择信息增益大的属性作为节点。一直递归调用下去，直到所有子集仅包含一个类别的数据为止，最后就得到了一颗决策树。

熵（Entropy,信息熵）的计算方法：假定S为训练集，S的目标属性C有m个可能的类标号值，C={C1,C2,C3…Cm}，每个类标号值相应的概率为p1，p2,p3…pm。那么训练集S的信息熵定义为：Entropy(S)=Entropy(p1,p2,,pm)=-(p1*log2(p1)+p2*log2(p2)+pm*log2(pm));

信息增益：假设训练集为S，并用属性A来划分S，那么属性A的信息增益Gain（S,A）为训练集S的熵减去按属性A划分S后的子集的熵，即Gain（S,A）=Entropy(S)-Entropy_A(S)。

优缺点分析：ID3算法采用一种自顶向下、贪婪的搜索方法，理论清晰，方法简单，学习能力较强，但是ID3算法只能处理分类型数据，无法处理连续性数据。该算法使用信息增益作为决策树属性节点的选择标准，由于信息增益在类别值多的属性上大于类别值少的属性的计算结果，这将导致决策树偏向于选择类别值多的属性。

C4.5算法：基于ID3算法的不足而改进的决策树分类算法。

如果属性A为离散型数据：计算方法和ID3相同。

如果属性A为连续型数据：则对属性A的取值排序，将每两个相邻值的中点看做分裂点，然后对每个分裂点计算Sl和Sr（Sl和Sr分别对应于属性A的取值对该分裂点进行划分开的两部分子集，即Sl为属性A取值中比该分裂点小的值的个数，Sr亦如此），然后计算该分裂点的熵Entropy_A(S)=abs(Sl)/abs(S)Entropy(Sl)+abs(Sr)/abs(S)Entro

py(Sr)，选择Entropy_A(S)值最小的分裂点作为属性A的最佳分裂点，并以此分裂点按属性A划分S的熵值作为属性A划分S的熵值。

分裂信息SplitE(A)=-(S1/S*log2(S1/S)+S2/S*log2(S2/S)……Sk/S*log2

(Sk/S)

对有缺失数据的处理：以某种方式填充缺失的数据（如平均值，常见值，赋予概率等等）

信息增益率定义为GainRatio(A)=Gain(A)/SplitE(A)。

优缺点分析：C4.5算法能够处理离散型数据和连续型数据以及有缺失值的数据，使用信息增益率来作为决策树的属性选择标准，对生成的决策树进行剪枝处理；在构造树的过程中，需要对数据集进行多次扫描和排序，因此算法相对而言不是很高效，并且C4.5算法对大规模数据集的处理不是很理想。