一种基于MMEPA的决策树构造方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于MMEPA的决策树构造方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要： 决策树是一种有效的数据分类方法，它的构造方法很多。在这里，提出一种基于mmepa（改进的最小熵原理方法）的决策树构造方法，并通过一个实例对其进行说明，用此方法提取分类规则，构造决策树模型。最后，对噪声剪枝等问题提出了解决思路。
关键词：分类；决策树；MMEPA(modified minimize entropy principle approach)
中图分类号：TP181 文献标识码：A文章编号：1009-3044(2007)05-11292-02
1 引言
一般来说，分类是把数据项映射到其中一个事先定义的类中的这样一个学习函数的过程。由一组输入的属性值向量和相应的类，用基于归纳学习算法得出分类。学习的目标是构建一个分类模型，通常也叫分类器，它可以根据有效的属性输入值预测一些实体（所给样本）的类。导出的模型是基于对训练数据集的分析，并用分类规则（IF-THEN）、决策树、数学公式或神经网络等形式表示。目前数据分类的技术方法主要有决策树、贝叶斯方法、神经网络、基于关联的方法、k-最近邻方法、遗传算法、粗糙集等。[1]
某个规则集合S的熵值H(S)计算公式如式（1）所示：
Pi表示i类型在集合S中所占的比例。
规则集合S关于属性A的信息增益Gain(S.A),由式（2）计算：
在这个等式中，Sv是规则集合S的子集合，Sv中的所有规则都具有相同的属性A值。|Sv|和S分别表示集合Sv和S的规则数目。
C4.5算法是ID3算法的扩展，采用增益比率的标准来选择分类属性。C4.5算法继承了ID3全部优点，且克服了ID3在应用中的不足，主要体现在以下几方面[2]：
(1)用信息增益率来选择属性，克服了ID3用信息增益选择属性时偏向于选择取值多的属性的不足；
(2)在树构造过程中或者构造完成之后，使用不同的修剪技术以避免树的不平衡；
(3)能够完成对连续属性的离散化处理；
(4)能够对不完整数据进行处理；
(5)K次迭代交叉验证；
(6)C4.5采用的知识表示形式为决策树，并能最终可以形成产生规则。
2 最小熵原理方法MEPA（Minimize Entropy Principle Approach）[3]
最小熵原理主要是确定数据集中的信息量。为了进一步细分数据，建立数据类别之间的初始值是必须的。初始值由熵最小原理方法确定，然后建立细分过程。因此，一个带有初始值计算的重复的细分过程将数据分为一系列的模糊集。
假定初始值范围在x1和x2中，区间[x1,x]用p表示，区间[x,x2]用q表示，熵值表示如下：式
pk(x)和qk(x)分别表示类别k在区间[x1,x1＋x]和区间[x1＋x,x2]的条件概率，p(x)和q(x)分别表示所有的类别在区间[x1,x1＋x]和区间[x1＋x,x2]的概率。式
nk(x)表示区间[x1,x1＋x]中k的类别数目，n(x)表示区间[x1,x1＋x]中所有类别的数目，Nk(x)表示区间[x1＋x,x2]中k的类别数目，N(x)表示区间[x1＋x,x2]中所有类别的数目，n表示区间[x1,x2]中类别的所有数目。
图1显示了分裂过程。当x在[x1,x2]中移动时，寻找当分裂成两块时的熵值，熵值最小时，也就是最佳分裂方法，把这时的x值称为初始优先值（如图1所示的PRI）。在已分裂成两块的各块中重复分裂过程，依次找到熵值最小的x值，如图1中的SEC1、SEC2、TER1、TER2、、TER3、TER4。显然，这是一个对[x1,x2]中的所有取值进行遍历的过程。
图1 最小熵原理方法的分割过程
3 用改进后的MMEPA构造决策树
这里，有一个决策树生成的例子，是天气是否适合踢足球的问题。天气由四个属性描述，即outlook(天气形势)、temperture(温度)、humidity(湿度)、windy(风)。Outlook取值sunny(晴朗)、overcast(有云)、rain(下雨)；temperture和humidity取值用具体数据表示；windy取值为false(无)、true(有)。共有14条记录，如表1所示。
表1 关于天气的数据集
本文详细描述了改进的MEPA方法。此方法能提高C4.5决策树的准确率和降低规则的数目，图2显示了此方法的研究模型。
图2 研究模型MEPA方法的具体步骤如下：
(1)输入r值，计算m值（r表示叶子取值的数目，m表示转换成语言上的表达等级）。当r≥2时，m≤2r－1,当r为其他时，m≤2。在这里，我们只考虑决策树的叶子只取两个值的情况，所以m＝3。
表2 属性值“潮湿度”的熵值计算
(2)计算每个属性的初始值。图2表示了当x=82.5时，属性值“潮湿度”的熵值S(x)最小，因此初始值是82.5。重复这个过程细分数据，得到所有的熵值，在这里，得到的是SEC1=72.5，SEC2=95.5，如表3所示。直到n(x)和N(x)都为0，停止分裂数据。
表3 属性初始值
(3)进行等级转换。把每一个数据转换成语言上的等级表示，分别用具有描述意义的单词来表示，如表4所示。
表4 数据转换成等级表示
(4)用C4.5算法建造决策模型。计算每个属性的熵值，选取熵值最小的属性作为节点向下生成决策树。[3-4]
根据C4.5算法，我们得到如图3所示的决策树。
图3 C4.5算法构造决策树
4 提取规则
提取决策树规则的过程也就是从根节点到每个叶子节点走一遍，然后提取决策树规则。把所有数据作为训练集，能得到6条规则，而且正确率为100％。规则如下:
规则1：如果天气晴朗，并且中度潮湿,那么不适合踢足球。
规则2：如果天气晴朗，并且高度潮湿，那么不适合踢足球。
规则3：如果天气晴朗，并且低度潮湿，那么适合踢足球。
规则4：如果有云，那么适合踢足球。
规则5：如果下雨，并且没有风，那么适合踢足球。
规则6：如果下雨，并且有风，那么不适合踢足球。
5 结束语
真实世界的数据(数据挖掘的对象显然就是真实世界数据)一般不可能是完美的，①可能某些属性字段上缺值(missing values)；②可能缺少必须的数据而造成数据不完整；③可能数据不准确含有噪声甚至是错误的。
剪枝是一种克服噪声的技术，它常常用统计学方法，去掉最不可靠、可能是噪音的一些枝条。剪枝方法是很丰富的，主要有两类剪枝方法：向前剪枝（forward pruning）和向后剪枝(backward pruning)。[5]剪枝时要用到一个测试数据集合，若存在某个叶子剪去后能使得在测试集熵的准确度或其它测度不降低，则剪取该叶子；否则不进行修剪。从理论上来说，向后剪枝好于向前剪枝，但计算复杂度大。
参考文献：
[1]范明,孟小峰. 数据挖掘――概念与技术[M].北京:机械工业出版社,2001.
[2]张彦,李茂青等.基于信息论的决策树算法探讨[J].自动化技术与应用, 2006,25(1): 4-7.
[3]Chen,J.-S.,&Cheng,C.-H.(2003),Extracting classification rule of software diagnosis using modified MEPA[J]. Expert Systems with Application(2006),doi: 10.1016/j.eswa.2006.09.042.
[4]胡智喜,唐学忠.基于信息增益法的决策树构造方法[J].自动化技术与应用, 2006,(3): 28-30.
[5]王兆红.基于信息熵的决策树[J].潍坊学报, 2006,6(4): 28-32.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。