1.概述

决策树归纳是从有类标号的训练元组中学习决策树。

决策树是一种类似于流程图的树结构，其中，每个内部结点（非叶子结点）表示在一个属性上的测试，每个分支代表该测试的一个输出，而每个树叶结点存放一个类的类标号。

树的最顶层结点是根结点。

有些决策树只能产生二叉树，而有些决策树可能产生非二叉树。

决策树以自顶向下递归的分治方法构造

2.算法归纳

a.用三个参数D,attribute_list和Attribute_selection_method调用该算法。我们称D为数据分区，开始时，它是训练元组和它们相应类标号的完全集。参数attribute_list是描述元组属性的列表。Attribute_selection_method指定选择属性的启发式过程，用了选择可以按类“最好的”区分给定运足的属性。

b.树从单个结点N开始，N代表D中的训练元组。

c.如果D中的元组都为同一类，则结点N变成树叶，并用该类标记它。

d.否则，算法调用Attribute_selection_method确定分裂准则。分裂准则指定分裂属性，并且也指出分裂点或分裂子集。理想情况下，分裂准则这样确定，使得每个分支上的输出分区都竟可能“纯”。一个分区时纯的，如果它的所有元组都属于同一类。换言之，如果根据分裂准则的互斥输出划分D中的元组，则希望结果分区尽可能纯。

e.结点N用分裂准则标记作为结点上的测试。

3.算法描述

算法:Generate_decision_tree.由数据分区D中的训练元组产生决策树

输入：数据分区D，训练元组和它们对应类标号的集合

　　   attribute_list,候选属性的集合

　　   Attribute_selection_method,一个确定“最好的”划分数据元组为个体类的分裂准则的过程，这个准则由分裂属性(splitting_attribute)和分裂点或划分子集组成

输出：一个决策树

方法：

　　创建一个结点N；

　　if  D中的元组都在同一类C中  then

　　　　返回N作为叶结点，以类C标记；

　　if attribute_list为空   then

　　　　返回N作为叶子结点，标记中为D中的多数类；　　　　//多数表决

　　使用Attribute_selection_method(D,attribute_list),找出“最好的”splitting_criterion;　　　　//这里有多种方法作为"最好的"指标，下面会介绍

　　用splitting_criterion标记结点N；

　　if splitting_attribute是离散值的,并且允许多路划分 then

　　　　attribute_list  <-- attribute_list -splitting_attribute;

　　for splitting_criterion的每个输出j 

　　　//划分元组并对每个分区产生子树

　　　　设Dj是D中满足输出j的数据元组的集合；

　　　　if  Dj为空 then

　　　　　　加一个树叶到结点N,标记为D中的多数类;

　　　　else

　　　　　　加一个由Generate_decision_tree(D,attribute_list)返回的结点到N；

　　end for

　　返回N；

4.找出“最好的”splitting_criterion的各种指标方法（属性选择度量）

　　a.信息增益

　　   来源：应用信息熵的概念，选择具有最高信息增益的塑像作为结点N的分裂属性。

　　　目的：该属性使结果分区中对元组分类所需要的信息量最小，并反映这些分区中的最小随机性或“不纯性”。

　　  优点：这种方法使得对一个对象分裂所需要的期望测试数目最小，并确保找到一颗简单的（但不必是最简单的）树。　

　　　对D中的元组分类所需要的期望信息由下式给出：

　　　　　　　　Info(D)=-Σpi*log2(pi) ;i=1,2,...,m

　　  其中，pi是D中任意元组属于类Ci的非零概率，并用|C(i,D)|/|D|估计。使用以2为底的对数函数是因为信息用二进位编码。

　　  Info(D)是识别D中元组的类标号所需要的平均信息量。注意，此时我们所有的信息只是每个类的元组所占的百分比。Info(D)又称为D的熵(entropy).

　　　　现在，假设我们要按某属性A划分D中的元组，其中属性根据训练数据的观测具有v个不同值{a1,a2,...,av}.如果A是离散值的，则这些值直接对应于A上测试的v个输出。可以用属性A将D划分为v个分区或子集{D1,D2,...,Dv}，其中,Dj包含D中的元组，它们的A值为aj。这些分区对应于从结点N生长出来的分支。理想情况下，我们希望该划分产生元组的准确分类。即我们希望每个分区都是纯的。然而，这些分区多半是不纯的。(在此划分之后)为了得到准确的分类，我们还需要多少信息？这个量由下式度量：

　　　　　　　　　　Info_A(D)=Σ(|Dj|/|D|*Info(Dj)); 其中|Dj|为第j分区中元组的数目，|D|为总元组数目，|Dj|/|D|充当第j个分区的权重。

　　　　Info_A(D)是基于按A划分对D 的元组分类所需要的期望信息。需要的期望信息越小，分区的纯度越高。

　　　　信息增益定义为原来的信息需求(仅基于类比例)与新的信息需求(对A划分后)之间的差。即   Gain(A)=Info(D)-Info_A(D)

　　      换言之，Gain(A)告诉我们通过A上的划分我们得到了多少。它是指定A的值而导致的信息需求的期望减少。选择具有最高信息增益Gain(A)的属性A作为结点N的分裂属性。这等价于在“能做最佳分类”的属性A上划分，使得完成元组分类还需要的信息最小(即最小化Info_A(D)).

　　　　PS：读者有兴趣可以去百度看看信息熵和热熵的概念，就会明白为何要去信息熵的线性组合的和最小作为分类指标。

 　　b.增益率

　　　　信息增益度量偏向于具有许多输出的测试。换句话说，它倾向于选择具有大量值的属性。ID3的后继C4.5使用一种称为信息率(gain ratio)的信息增益扩充，试图克服这种偏倚。

　　      它用“分裂信息(split information)”的值将信息增益规范化。分裂信息类似于Info(D)，定义如下

　　　　　　　　　　SplitInfo_A(D)=-Σ{(|Dj|/|D|)*log2(|Dj|/|D|)}；j=1,2,...,v

　　　　该值代表有训练数据集D划分成对应于属性A测试的v个输出的v个分区产生的信息。注意，对于每个输出，它相对于D中元组的总数考虑具有该输出的元组数。它不同于信息增益，信息增益度量关于分类基于同样划分的所获得的信息。增益率定义为　　

　　　　　　　　　　GrianRate(A)=Grain(A)/SplitInfo_A(D)  ;

　　　　选择具有最大增益率的属性作为分类属性。然而需要注意的是，随着划分信息趋向于0，该比率变得不稳定。为了避免这种情况，增加一个约束：选取的测试的信息增益必须较大，至少与考察的所有测试的平均增益一样大。

　　c.基尼指数

　　　　基尼指数(Gini index)在CART中使用。基尼指数度量数据分区或训练元组集D的不纯度，定义为

　　　　　　　　Gini(D)=1-Σ(pi^2) ;   i=1,2,...,m

　　　　其中，pi是D中元组属于Ci类的概率，并用|C(i,D)|/|D|估计。对m个类计算和。

　　　　基尼指数考虑每个属性的二元划分。

　　　　首先考虑A是离散值属性的情况：

　　　　　　其中A具有v个不同值{a1,a2,...,av}出现在D中。为了确定A上最好的二元划分，考虑使用的已知值形成的所有可能子集。每个子集S_A可以看做属性A的一个形如“A€S_A?”的二元测试。给定一个元组，如果该元组A的值出现在S_A列出的值中，则该测试满足。

　　　　　　当考虑二元划分裂时，计算每个结果分区的不纯度的加权和。例如，如果A的二元划分将D划分成D1和D2，则给定该划分，D的基尼指数为  Gini_A(D)=|D1|/|D|*Gini(D1)+|D2|/|D|*Gini(D2);

　　　　      对于每个属性，考虑每种可能的二元划分。对于离散值属性，选择该属性产生最小基尼指数的子集作为它的分裂子集。

　　　　对于连续值属性，必须考虑每个可能的分裂点。其策略类似于上面介绍的信息增益所使用的策略，其中将每对(排序列后的)相邻值的中点作为可能的分裂点。对于给定的(连续值)属性，选择产生最小基尼指数的点作为该属性的分裂点。注意，对于A的可能分裂点split_point,D1是D中满足A《=split_point的元组集合，而D2是D中满足A>split_point的元组集合。

　　　　对于离散或连续值属性A的二元划分导致的不纯度降低为  ΔGini(A)=Gini(D)-Gini_A(D) 最大化不纯度降低(或等价地，具有最小基尼指数) 的属性选为分裂属性。该属性和他的分裂子集(对于离散值的分裂属性)或分裂点（对于连续值的分裂属性）一起形成分裂准则。

　　　　d.其他属性选择度量

　　　　　　如基于最小描述长度(Minimum Description Length,MDL)原理的属性选择度量。

5.最后内容

　　　　决策树后面还有关于 树剪枝、可伸缩性与决策树归纳、决策树归纳的可视化挖掘  等等内容，笔者也没搞明白，就先写到这里，搞明白了再续写。

采摘至《数据挖掘概念与技术》第3版。

决策树学习总结