版权归原作者所有,如有侵权,请联系我们

[科普中国]-决策树算法

科学百科
原创
科学百科为用户提供权威科普内容,打造知识科普阵地
收藏

简介

决策树(decision tree)是一种基本的分类与回归方法。决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。

其主要优点是模型具有可读性,分类速度快。学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型。预测时,对新的数据,利用决策树模型进行分类。

决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。1

决策树学习目标:根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。决策树学习本质上是从训练数据集中归纳出一组分类规则。能对训练数据进行正确分类的决策树可能有多个,可能没有。在选择决策树时,应选择一个与训练数据矛盾较小的决策树,同时具有很好的泛化能力;而且选择的条件概率模型应该不仅对训练数据有很好的拟合,而且对未知数据有很好的预测。1

损失函数:通常是正则化的极大似然函数

策略:是以损失函数为目标函数的最小化

因为从所有可能的决策树中选取最优决策树是NP完全问题,所以现实中决策树学习通常采用启发式方法,近似求解这一最优化问题,得到的决策树是次最优(sub-optimal)的。

决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得对各个子数据集有一个最好的分类的过程。包含特征选择、决策树的生成和决策树的剪枝过程。

剪枝:1

目的:将树变得更简单,从而使它具有更好的泛化能力。

步骤:去掉过于细分的叶结点,使其回退到父结点,甚至更高的结点,然后将父结点或更高的结点改为新的叶结点。

决策树的生成对应模型的局部选择,决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优,决策树的剪枝则考虑全局最优。

特征选择:

如果特征数量很多,在决策树学习开始时对特征进行选择,只留下对训练数据有足够分类能力的特征。(例如把名字不作为一个特征进行选择)

典型算法决策树的典型算法有ID3,C4.5,CART等。1

国际权威的学术组织,数据挖掘国际会议ICDM (the IEEE International Conference on Data Mining)在2006年12月评选出了数据挖掘领域的十大经典算法中,C4.5算法排名第一。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。C4.5算法产生的分类规则易于理解,准确率较高。不过在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,在实际应用中因而会导致算法的低效。2

决策树算法的优点如下:

(1)分类精度高;

(2)生成的模式简单;

(3)对噪声数据有很好的健壮性。

因而是目前应用最为广泛的归纳推理算法之一,在数据挖掘中受到研究者的广泛关注。2

基本思想1)树以代表训练样本的单个结点开始。

2)如果样本都在同一个类.则该结点成为树叶,并用该类标记。

3)否则,算法选择最有分类能力的属性作为决策树的当前结点.

4)根据当前决策结点属性取值的不同,将训练样本数据集tlI分为若干子集,每个取值形成一个分枝,有几个取值形成几个分枝。匀针对上一步得到的一个子集,重复进行先前步骤,递4'I形成每个划分样本上的决策树。一旦一个属性出现在一个结点上,就不必在该结点的任何后代考虑它。

5)递归划分步骤仅当下列条件之一成立时停止:

①给定结点的所有样本属于同一类。

②没有剩余属性可以用来进一步划分样本.在这种情况下.使用多数表决,将给定的结点转换成树叶,并以样本中元组个数最多的类别作为类别标记,同时也可以存放该结点样本的类别分布,

③如果某一分枝tc,没有满足该分支中已有分类的样本,则以样本的多数类创建一个树叶。3

构造方法决策树构造的输入是一组带有类别标记的例子,构造的结果是一棵二叉树或多叉树。二叉树的内部节点(非叶子节点)一般表示为一个逻辑判断,如形式为a=aj的逻辑判断,其中a是属性,aj是该属性的所有取值:树的边是逻辑判断的分支结果。多叉树(ID3)的内部结点是属性,边是该属性的所有取值,有几个属性值就有几条边。树的叶子节点都是类别标记。3

由于数据表示不当、有噪声或者由于决策树生成时产生重复的子树等原因,都会造成产生的决策树过大。因此,简化决策树是一个不可缺少的环节。寻找一棵最优决策树,主要应解决以下3个最优化问题:①生成最少数目的叶子节点;②生成的每个叶子节点的深度最小;③生成的决策树叶子节点最少且每个叶子节点的深度最小。

分类与回归树模型同样由特征选择、树的生成及剪枝组成,既可以用于分类也可以用于回归。

CART算法由以下两步组成

(1)决策树生成:基于训练数据集生成决策树,牛成的决策树要尽量大;

(2)决策树剪枝:用验证数据集对己生成的树进行剪枝并选择最优子树,这时用损失函数最小作为剪枝的标准。1