5.2决策树分类与ID3算法

5.2决策树分类与ID3算法决

策

树

分

类

与

ID3

算

法决策树的起源和发展决策树起源于1962年提出的CLS(ConceptLearningSystem)，由hunt、Marin和Stone为了研究人类概念模型而得来。1984年，L.Breiman等人提出CART(ClassificationandRegressionTree)算法，采用基尼指数作为属性分裂的标准。1979-1986年，J.R.Quinlan提出了ID3算法，但ID3算法无法处理连续型数据且没有考虑到缺失值的情况.1998年，R.Rastogi等人提出一种将建树和修剪相结合的分类算法PUBLIC(ADecisionTreethatIntegratesBuildingandPruning)。决

策

树

分

类

与

ID3

算

法决策树概念

决

策

树

分

类

与

ID3

算

法决策树举例一棵典型的决策树如图所示，它表示概念“岩石可钻性”，预测油气开采中岩石的钻探难易程度。岩石可钻性”的判定树，指油气开采中岩石的钻探难易程度。每个内部（非树叶）节点表示一个属性上的测试，每个树叶节点代表一个类（岩石可钻性=高,或岩石可钻性=低）。决

策

树

分

类

与

ID3

算

法

决策树构造的输入是一组带有类别标记的数据，构造的结果是一棵二叉或多叉树。树中节点可分为两类：决策节点和叶子节点。决

策

树

分

类

与

ID3

算

法决策树分类步骤1.

建立决策树，采用自上而下分而治之的方法利用训练样本生成决策树模型。2.

修剪决策树

去掉一些可能是噪音或者异常的数据使用决策树对未知数据进行分类按照决策树上采用的分割属性逐层往下，直到一个叶子节点判定树分类算法output训练集决策树input决

策

树

分

类

与

ID3

算

法一、使用决策树进行分类的一般有两个步骤第一步建立决策树基本算法自上而下分而治之的方法开始时，所有的数据都在根节点。所有记录用所选属性递归的进行分割属性的选择（关键）是基于一个启发式规则或者一个统计的度量（如:

informationgain）停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割决

策

树

分

类

与

ID3

算

法第二步修剪

树一旦生成后，便进入第二阶段—修剪阶段。主要是通过消除由于统计噪声或数据波动对决策树的影响来达到净化树的目的。决策树的修剪就是使用一个叶节点来替代一个子树。若一个规则检测到其子树中的误分类的比率比较大时，就替换。

决

策

树

分

类

与

ID3

算

法第二步修剪剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略：预先剪枝（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。后剪枝（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（TuningSet或AdjustingSet），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。剪枝过程中一般要涉及一些统计参数或阈值（如停机阈值）。要防止过分剪枝（Over-Pruning）带来的副作用。决

策

树

分

类

与

ID3

算

法

通常，建树阶段的耗时要比修剪阶段的要大，因为建树阶段要对数据进行多次扫描，而修剪阶段只需访问生成的决策树而已。决

策

树

分

类

与

ID3

算

法

二、决策树ID3算法

ID3与C4.5是Quinlan为了从数据中归纳分类模型而构造的算法。给定一个记录的集合，每个记录都有相同的结构，类别属性所取的值只限于

{true,false}，{success,failure}，{yes,no}等离散值。决

策

树

分

类

与

ID3

算

法ID3决策树生成法：决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。采用信息增益来选择能够最好地将样本分类的属性。决

策

树

分

类

与

ID3

算

法算法ID3的基本过程算法4.1：Generate_Decision_Tree

（由给定的数据产生一棵判定树）输入：训练样本Samples，由离散值属性表示；候选属性集attribute_list输出：一棵判定树Generate_Decision_Tree(Samples,attribute_list)决

策

树

分

类

与

ID3

算

法创建节点NIFSamples都在同一类C,THEN

返回N作为叶节点,以类C标记IFattribute_list为空,THEN返回N作为叶节点,用Samples中最普通的类标记选择attribute_list中具有最高信息增益的属性test_attribute标记节点N为test_attributeForeachtest_attribute中的已知值ai

由节点N长出一个条件为test_attribute=ai的分支

设si为Samples样本中test_attribute=ai的集合IFsi为空,THEN

加上一个树叶,用Samples中最普通的类标记

ELSE加上一个由：Generate_Decision_Tree(Si,attribute_list-test_attribute)返回的节点决

策

树

分

类

与

ID3

算

法算法ID3的基本过程

算法4.1递归操作的终止条件