决策树(Decision Tree)

1.什么是决策树学习？

决策树学习是以实例为基础的归纳学习，采用自顶向下的递归方法，决策树的每一层结点依照某一属性值向下分为子结点，待分类的实例在每一结点处与该结点相关的属性值进行比较，根据不同的比较结果向相应的子结点扩展，这一过程在到达决策树的叶结点时结束。

=> 从根结点到叶结点的每一条路径都对应着一条合理的规则，规则间各部分的关系是合取关系，整个决策树对应着一组析取的规则。

基本思路：以信息熵为度量构造一棵熵值下降最快的树，到叶子结点处的熵值为零，此时每个叶结点中的实例都属于同一类。

信息熵(By C.E.Shannon)：信息中排除冗余后的平均信息量，用于描述信源的不确定度。

决策树学习算法的最大优点：可以自学习。即在学习过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。

2.决策树 ？

决策树又分为分类树和回归树。

(1)分类树：用于分类标签值 ，其输出是定性的。Eg.C4.5 /ID3

(2)回归树：用于预测实际的值，其输出时定量的。

E.g.图源自《人工智能》 马少平

树是由结点和分支组成的层次数据结构。

    结点用于存储信息或知识；

    分支用于连接各个结点。

在决策树的内部结点包含学习的实例，每层分支代表了实例的一个属性的可能取值，叶结点是最终划分成的类。

CART(Classification and Regression Tree) - 决策树是一棵二叉树，即对于每个问题的判定是二元的。

 

构造一棵决策树要解决的四个问题

(1)收集待分类的数据，这些数据的所有属性应该是完全标注的。

(2)设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。

(3)分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。

(4)设计分类停止条件。

E.g.1)该结点包含的数据太少不足以分裂。

       2)继续分裂数据集对树生成的目标没有贡献。

       3)树的深度过大不宜再分。

构造一棵决策树的过程

(1)决策树的特征选择。

可以通过计算信息增益(ID3)和信息增益比(C4.5)来进行选择。

(2)决策树的生成。

(3)决策树的剪枝。

主要用于防止过拟合，使决策树泛化能力更强。

3.基于决策树的机器学习？

机器学习的目的：确定实例的属性(对应生成规则的条件)和分类(对应生成规则的决策)，从而构造确定的规则。

机器学习中的决策树目的不是为了分类，而是为了确定训练实例的属性和其类别间的确定关系，是描述这种确定关系的形式和手段。

 

Some concepts

(1)自信息量

设信源X发出a的概率P(a)，在收到符号a之前，收信者对a的不确定性定义为a的自信息量I(a)。

(2)信息熵

自信息量只能反映符号的不确定性，而信息熵用来度量整个信源整体的不确定性。

            

其中，r为信源X发出的所有可能的符号类型。

信息熵反映了信源每发出一个符号所提供的平均信息量。

(3)条件熵

设信源为X，收信者收到信息Y，用条件熵H( X | Y )来描述收信者在收到Y后对X的不确定性估计。

设X的符号ai，Y的符号bj,P( ai | bj )为当Y为bj时，X为ai的概率。

(4)平均互信息量

用平均互信息量来表示信号Y所能提供的关于X的信息量的大小，用I( X | Y )。

 

ID3算法

将信息熵的下降速度作为属性选择标准。 //对于决策树学习来说，最重要的是如何在众多属性中进行选择从而实现结点分裂。

训练数据集D，特征集A，阈值e，决策树T

(1)若D中所有实例属于同一类C，则T为单结点树，并将类C作为该结点的类标记，返回T。

(2)若A = ∅，则T为单结点树，并将D中实例数最大的类C作为该结点的类标记，返回T。

(3)否则，计算A中各特征对D的信息增益，选择信息增益最大的特征Ag。

(4)如果Ag的信息增益小于阈值e，则置T为单结点树，并将D中实例数最大的类C作为该结点的类标记，返回T。

(5)否则，对Ag的每一可能值，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T。

(6)对第i个子结点，以Di为训练集，以A-{Ag}为特征集，递归调用(1)~(5)，得到子树Ti，返回Ti。