决策树应用的意义和方法
决策树表示方法是应用最广的逻辑方法之一,它能从一组无次序、无规则的事例中推理出决策树表示形式的分类规则,决策树分类方法采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较,利用信息“熵”的理论,根据不同的属性值判断从该结点向下的分支,在决策树的叶结点得到结论。
1.决策树的ID3算法:决策树算法中最常用的是ID3算法,ID3算法是Quinlan提出的一个著名决策树生成方法,其基本概念如下:①决策树中每一个非结点对应着一个非类别属性,树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。②每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。③采用信息增益来选择能够最好地将样本分类的属性。
2.信息增益的计算:信息增益基于信息论中熵(Entropy)的概念。ID3总是选择具有最高信息增益(或最大熵压缩)的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量小,并反映划分的最小随机性或“不纯性”。这种信息理论方法使得对一个对象分类所需的期望测试数目达到最小,并尽量确保找到一棵简单的(但不必是最简单的)树来刻画相关的信息。
对于给定的训练集S,设S是s个数据样本的集合。假定类标号属性具有m个不同值,定义m个不同类Ci(i=1,2,…,m)。设si是类Ci中的样本数。对一个给定的样本分类所需的期望信息由下式给出:
其中pi是任意样本属于Ci的概率,并用si/s估计。
设属性A具有v个不同取值{a1,a2,…,av}。可以用属性A将S划分为v个子集{S1,S2,…,Sv},其中,Sj包含S中这样一些样本,它们在A上具有值aj。如果A被选作测试属性(即最好的分裂属性),则这些子集对应于由包含集合S的节点生长出来的分支。(https://www.daowen.com)
设Sij是子集Si中类Ci的样本数。根据由A划分成子集的熵由下式给出:
这里,
充当第j个子集的权,并且等于子集(即A值为aj)中的样本个数除以S中的样本总数。熵值越小,子集划分的纯度越高。而对于给定的子集Sj,其期望信息有下式计算:
其中,
是Sj中的样本属于类Ci的概率。
由期望信息和熵值可以得到对应的信息增益值。对于A上分之将获得的信息增益可以由下面的公式得到:
Gain(A)=I(s1,s2,…,sm)-E(A)
ID3算法计算每一个属性额信息增益,并选取具有最高增益的属性作为给定集合S的测试属性。对被选取的测试属性创建一个结点,并以该属性标记,对该属性的每一个值创建一个分支,并据此划分样本。
3.决策树噪声的修剪:树剪枝的目的就是由于噪声数据而引起的分支,从而避免决策树的过匹配。本研究探讨采用预先剪枝的方法,定义两个原则:各属性变量的信息“熵”增益之间没有最高值(小数后保留3位);按增益最高值的属性中阴阳两类证,其中一类超过90%。出现以上两类情况考虑终止决策树扩展。决策树的修剪后是否正确,关键在于测试集的测试评价是否成功。