学习决策树：使用科学方法进行最优处理

（一）决策树

决策是根据信息和评价准则，用科学方法寻找或选取最优处理方案的过程或技术。对于每个事件或决策（即自然状态），都可能引出两个或多个事件，导致不同的结果或结论。把这种分支用一棵搜索树表示，即叫做决策树。也就是说，决策树因其形状像树而得名。

决策树是一种描述概念空间的有效方法，在相当长时间内曾是一种非常流行的人工智能技术。20世纪80年代，决策树是构建人工智能系统的主要方法之一。20世纪90年代初，逐渐不为人们注意。然而，到了20世纪90年代后期，随着数据挖掘技术的兴起，决策树作为一种构建决策系统的强有力的技术而重新浮出水面。随着数据挖掘技术在商业、制造业、医疗业及其他科学与工程领域的广泛应用，决策树技术已在21世纪发挥越来越大的作用。

决策树由一系列节点和分支组成，在节点和子节点之间形成分支。节点代表决策或学习过程中所考虑的属性，而不同属性形成不同的分支。为了使用决策树对某一事例进行学习，做出决策，可以利用该事例的属性值并由决策树的树根往下搜索，直至叶节点止。此叶节点即包含学习或决策结果。

可以利用多种算法构造决策树，比较流行的有ID3、C4.5、CART和CHAID等。构造决策树的算法通过测试对象的属性来决定它们的分类。决策树是由上而下形成的。在决策树的每个节点都有一个属性被测试，测试结果用来划分对象集。反复进行这一过程直至某一子树中的集合与分类标准是同类的为止，这个集合就是叶节点。在每个节点，被测试的属性是根据寻求最大的信息增益和最小熵的标准来选择的。简单地说，就是计算每个属性的平均熵，选择平均熵最小的属性作为根节点，用同样方法选择其他节点直至形成整个决策树。

决策树学习是以实例为基础的归纳学习，能够进行多概念学习，具备快捷简便等优点，具有广泛的应用领域。

决策树学习采用学习算法来实现。如果学习任务是对大实例集进行概念分类的归纳定义，而且这些例子都是由用一些无结构的属性－值对来表示，那么就可采用决策树学习算法。下面对ID3算法进行分析。

（二）ID3算法

ID3算法是昆兰（J.R.Quinlan）于1979年提出的一种以信息熵（entropy）下降速度最快作为属性选择标准的一种学习算法。^[6]其输入是一个用来描述各种已知类别的例子集，学习结果是一棵用于进行分类的决策树。

1.信息熵和信息增益

信息熵和信息增益是ID3算法的重要数学基础，为更好地理解和掌握ID3算法，下面先简单讨论这两个概念。

（1）信息熵

信息熵（information entropy）是对信源整体不确定性的度量。假设S为样本集，S中所有样本的类别有k种，如（y1，y2，…，yk），各种类别样本在S上的概率分别为P（y1），P（y2），…，P（yk），则S的信息熵可定义为：

其中，概率P（yj）（j＝1，2，…，k），实际上是类别为yi的样本在S中所占的比例；对数可以是以各种数为底的对数，在ID3算法中采用以2为底的对数。E（S）的值越小，S的不确定性越小，即其确定性越高。

（2）信息增益

信息增益（information gain）是对两个信息量之间的差的度量。其讨论涉及样本集S中样本的结构。

对S中的每个样本，从其结构看，除了刚才提到的样本类别，还有其条件属性，或简称为属性。若假设S中的样本有m个属性，其属性集为X＝{x1，x2，…，xm}，且每个属性均有r种取值，则可以根据属性的不同取值，将样本集S划分成r个不同的子集S1，S2，…，Sr。(www.xing528.com)

在此结构下，可得到由属性xi的不同取值对样本集S进行划分后的加权信息熵

其中，t为条件属性xi的属性值；St为xi＝t时的样本子集；E（St）为样本子集St信息熵；分别为样本集S和样本子集St的大小，即S和St中的样本个数。

有了信息熵和加权信息熵，就可以计算信息增益。信息增益是指E（S）和E（S，xi）之间的差，即

可见，信息增益描述的是信息的确定性，其值越大，信息的确定性越高。

2.ID3算法的描述

ID3算法的学习过程实际上是一个以整个样本集为根节点，以信息增益最大为原则，选择条件属性进行扩展，逐步构造出决策树的过程。若假设S＝{s1，s2，…，sn}为整个样本集，X＝{x1，x2，…，xm}为全体属性集，Y＝{y1，y2，…，yk}为样本类别，则ID3算法过程可描述如下：

（1）初始化样本集S＝{s1，s2，…，sn}和属性集X＝{x1，x2，…，xm}，生成仅含根节点（S，X）的初始决策树。

（2）如果节点样本集中的所有样本都属于同一类别，则将该节点标记为叶节点，并标出该叶节点的类。算法结束。否则执行下一步。

（3）如果属性集为空；或者样本集中的所有样本在属性集上都取相同值，即所有样本都具有相同的属性值（无法进行划分），则同样将该节点标记为叶节点，并根据各类别的样本数量，按照少数服从多数的原则，将该叶节点的类别标记为样本数最多的那个类别。算法结束。否则执行下一步。

（4）计算每个属性的信息增益，并选出信息增益最大的属性对当前决策树进行扩展。

（5）对选定属性的每个属性值，重复执行如下操作，直到所有属性值全部处理完为止：

①为每个属性值生成一个分支；并将样本集中与该分支有关的所有样本放到一起，形成该新生分支节点的样本子集；

②若样本子集为空，则将此新生分支节点标记为叶节点，其节点类别为原样本集中最多的类别；

③否则，若样本子集中的所有样本均属于同一类别，则将该节点标记为叶节点，并标出该叶节点的类别。

（6）从属性集中删除所选定的属性，得到新的属性集。

（7）转第（3）步。