分类算法——决策树分类(二)

       前一篇《分类算法——决策树分类（一）》 解释了什么是决策树，本文继续讲解决策树分类算法，将从以下4个方面进行讲解：

       1) 决策树算法的基本思想

       2) 决策树算法的适应情况

       3) 决策属性的选择

       4) 常见的决策树分类算法。

1. 决策树基本思想

         决策树算法有很多变种，包括ID3、C4.5、C5.0、CARD等，但其基础都是类似的。首先来探讨一下决策树树算法的基本思想：

       具体步骤如下：

       1).  假设D为训练样本集。

       2).  从属性集合Attributes中选择一个最能区别D中样本的属性。

       3).  创建一个树节点，它的值为所选择的属性。创建此节点的子节点，每个子链代表所选属性的一个唯一值（唯一区间），使用子链的值进一步将样本细分为子类

      

       对于每一个分支继续重复(2)(3)的过程，直到满足以下两个条件之一：

       (a): 所有属性已经被这条路径包括。

       (b): 与这个节点关联的所有训练样本都具有相同的目标属性（熵为0，下文将详细介绍熵）。

2. 决策树适用情况

       通常决策树学习最适合具有以下特征的问题：

       1) 实例是由“属性-值”对表示的。

       2) 目标函数具有离散的输出值。例如上文提到示例中女孩对相亲对象的见或者不见

       3) 实例的所有属性都是离散值。如果是连续值或者离散值种类太多，可以把它分为不同的区间，例如上面的age分为了3个区间而不是每个独立的值为一个判断分支。

3. 决策属性的选择

       属性选择方法总是选择最好的属性最为分裂属性，即让每个分支的记录的类别尽可能纯。将所有属性列表的属性进行按某个标准排序，从而选出最好的属性。

       属性选择方法很多，常用的方法：信息增益（InformaDion gain）、增益比率（gain raDio）、基尼指数（Gini inDex）,本文将简单介绍一下信息增益。

       在介绍信息增益之前，我们先介绍一个概念，“熵”。信息增益是用熵作为尺度，是衡量属性对训练数据分类能力的标准。而“熵”是衡量训练集集合纯度的标准。公式表示为：

       其中的m表示数据集 D 中类别 C 的个数，Pi 表示 D 中任意一个记录属于 Ci 的概率，计算时

                     Pi=(|Ci|/|D|)

       Entropy(D) 表示将数据集 D 不同的类分开需要的信息量。

      

       如果某个数据集的类别的不确定程度越高，则其熵就越大。比如我们将一个立方体A抛向空中，记落地时着地的面为f1，f1 的取值为 {1,2,3,4,5,6}，f1 的熵

                 Entropy(f1)=-(1/6*log(1/6)+…+1/6*log(1/6))=-1*log(1/6)=2.58

       现在我们把立方体 A 换为正四面体 B ，记落地时着地的面为 f2，f2 的取值为{ 1,2,3,4}，f2 的熵

                 Entropy(f2)=-（1/4*log(1/4) + 1/4*log(1/4)+1/4*log(1/4)+1/4*log(1/4)) =-log(1/4)=2

       如果我们再换成一个球 C，记落地时着地的面为 f3，显然不管怎么扔着地都是同一个面，即 f3 的取值为 {1}，故其熵

                 Entropy(f3)=-1*log(1)=0

      

       可以看到面数越多，熵值也越大，而当只有一个面的球时，熵值为0，此时表示不确定程度为0，也就是着地时向下的面是确定的。

       信息增益简单来说就是衡量熵的效应值，信息增益越大，说明“熵”的效应值越高，选择信息增益最大的一个作为此次的分类属性，信息增益的计算：

       信息增益的定义为分裂前后，两个信息量只差：

       信息增益 Gain(R) 表示属性 R 给分类带来的信息量，我们寻找 Gain 最大的属性，就能使分类尽可能的纯，即最可能的把不同的类分开。

4. 常见的决策树算法

       ID3算法：

       优点：算法的理论清晰，方法简单，学习能力较强。

       缺点：只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。

      C4.5算法：

       优点：产生的分类规则易于理解，准确率较高。

       缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

       SLIQ算法

       优点：SLIQ算法对C4.5决策树分类算法的实现方法进行了改进，在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。使得该算法能够处理比C4.5大得多的训练集，在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。

       缺点：

       1) 由于需要将类别列表存放于内存,而类别列表的元组数与训练集的元组数是相同的,这就一定程度上限制了可以处理的数据集的大小。

       2) 由于采用了预排序技术，而排序算法的复杂度本身并不是与记录个数成线性关系，因此，使得SLIQ算法不可能达到随记录数目增长的线性可伸缩性。

       SPRINT算法

       优点：寻找每个结点的最优分裂标准时变得更简单

       缺点：对非分裂属性的属性列表进行分裂变得很困难。

参考文献：

分类算法之决策树介绍

数据挖掘系列（6）决策树分类算法

数据挖掘分类算法之决策树