决策树技术分类.docx

决策树分类技术研究 摘 要】 决策树分类是一种重要的数据分类技术。该文通过对决策树分类方法的研究，进一步讨论了实际使用过程中决策树学习出现的常见问题的解决方法。为实际应用提供了依据。【关健词】 决策树;分类1 引言数据分类是数据挖掘中的一个重要问题，是一种有效的KDD分析方法。数据分类通过分析训练集中的数据，对类建立分类模型，然后利用这个分类模型，把数据库中的数据项映射到给定类别中。近年来，数据分类技术已被广泛、有效地应用于科学实验、医疗诊断、气象预报、信贷审核、商业预测等领域，引起了工业界和学术界的关注。依据其采用的分类模型，数据分类技术主要可分为:机器学习方法(如决策树归纳)、统计方法(如贝叶斯分类和贝叶斯网络)、神经网络方法、遗传算法、粗糙集和模糊逻辑技术等。上述技术中，决策树技术是利用最广泛的分类技术。它有以下优点:首先，决策树方法结构简单，便于人们理解;其次，决策树模型效率高，对训练集数据量较大的情况较为适合;第三，决策树方法通常不需要受训数据外的知识;第四，决策树方法具有较高的分类精确度。同时决策树技术也有一些不足，如对于大型数据库的可伸缩性问题、对于非平衡数据进行分类时，剪枝会造成精确率的降低等。本文主要阐述了决策树分类的基本概念、算法以及实际使用中如何解决某些常见的问题，如:测试属性选择的度量标准、连续属性的离散化处理、处理缺少属性值、树剪枝与避免过度拟合、分类法的准确率评估及提高和决策树的可伸缩性等。2 决策树算法2.，决策树的构造方法决策树是一个类似于流程图的树结构，决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。 树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。决策树构造的基本算法是贪心算法，它以自顶向下递规的方式构造判定树。算法的基本策略如下:1)树以代表训练样本的单个节点开始。2)如果样本都在同一个类，则该节点成为树叶，并用该类标记。3)否则，算法使用一种度量标准作为启发信息，选择能够最好的将样本分类的属性，成为该节点的测试属性。4)对测试属性的每一个已知的值，创建一个分枝，并据此划分样本。5)算法使用同样的过程，递归的形成每个划分上的样本子决策树。当出现如下情况之一时，递归停止:(a)给定节点的所有样本属于同一类。(b)没有剩余的属性来进一步划分样本或者分枝中没有样本，这时使用多数表决，将给定的节点转换为树叶，并用父节点中多数类来标记它。2.2测试属性选择的度量标准J.RossQuinlan提出了ID31% 法。在此算法中采用信息论中的信息增益(informationgain)来衡量给定的属性区分训练样例的能力。其计算方法如下:如果目标属性具有。个不同的值，那么数据样例集S相对于c个状态的分类的嫡定义为Entorpy二艺Paog=pi;若A是S中的一个属性，Values(A)表示属性A所有可能的集合，S.是S中属性A的值为v的子集，即S,=IseSIA(s)=v)，则属性A相对于样例集合S的信息增益Gain(S,A)被定义为:Gain(S,A)=Entropy(S)一 艺怜v.YY州 人】iIsSddEntropy(S.)这种方法使生成的树平均深度较小，从而有较快的分类速度。但是，信息增益度量存在一个内在偏置，它偏祖具有较多值的属性。在此基础上，Quinlan又于1993年对ID3算法进行了补充和改进，提出了更先进的C4.52】算法，提出了信息增益率的属性度量方法。其定义如下:GainRatio(S,A卜Splulnformation(S,A)其中，Spiltlnformation(S,A)-i各骨logA分裂信息(SplitWonnation)用来衡量属性分裂数据的广度和均匀性，避免了ID3算法所采用的信息增益倾向于选择取值较多的属性。Quinlan通过试验，对若干属性测试标准做了比较，发现信息增益率能得到更好的决策树，而且不易产生不平衡的划分。除了以上两种方法外，LopezdeMantaras在1991年提出了基于距离(distance-based)的度量。这个度量标准定义了数据划分间的一种距离尺度。其效果接近信息增益率的度量效果，且避免了偏向有大量值的属性。此外，学者们还提出了Relief度量、J一度量,G统计、X2统计以及最小描述长度(MDL)等多种属性度量方法。对这些度量方法的研究和比较发现，没有一种度量方法在属性选择和处理噪声等问题中占有绝对的优势。因此，在实际构造决策树的过程中，要综合权衡效率和准确率等多种因素选择恰当的度量方法。2.3连续属性的离散化处理ID3算法被限制为只能取离散值的属性。为了消除这个限制，对于连续属性的离散化，我们可以采用信息增益率判别方法。具体的处理分三步操作:1)实例排序首先，将该判断节点处所有的实例按连续属性V升序排列，得到值序列vi,vx,.vk),2)生成候选分割点任何v，和v,。之间的任意取值都可以把实例集合分为两个部分，即T,=tIV-v;);对k个值的属性V就有k-1种分法。3)候选分割点的选择对于每一种分割，计算信息增益率，然后选取最高者作为这个连续属性离散化的闹值，作为属性V的分枝，即:Vthresh-基金项目:安徽省教育厅自然科学基全(2005kj093)万方数据福 建 电 脑 2005年第 8期old代)threshold仅)二、，则连续属性分割为两部分:V 除此两种方法之外，我们还可以根据编码所需的二进制位thershold仅)和Vthreshold(V)。 数，对树进行剪枝。即采用最小描述长度(MDL)方法。这一方法2.4处理缺少属性值的训练样例 . 遵循的原则是最简单的解是最期望的，它不需要独立的样本集。在某些情况下，可供使用的数据可能缺少某些属性的值。处 也可以交叉使用先剪枝和后剪枝，形成组合方式。理缺少属性值的一种策略是使用该属性最常见值补充缺少的属 2.6分类法的准确率评估及提高性值。这种方法简单易行。另一种策略是为属性的每个可能值赋 估计分类法的准确率是重要的，这使得我们可以估计一个予一个概率。C4.5使用这种方法处理缺少的属性值。 ， 给定的分类法对未来数据正确标号的准确率。保持(holdout)和2.5树剪枝与避免过度拟合 . K-折交叉确认(K-foldcross-vaildation)方法是两种基于给定数由于数据中的噪声和孤立点，许多分枝反映的是训练样本 据随机选样划分的、常用的评估分类法准确率的技术。为了提高的异常。剪枝方法处理这种过分适应数据问题。主要有剪枝方 决策树的准确率，可以使用bagging或者boosting两种技术。它法: 们都将T个学习得到的分类法CIA.CT组合起来，旨在得到一先剪枝(prepruning)方法中，通过提前停止树的构造，对树 个改进的分类法C,剪枝。然而选择一个适当的阂值是困难的。较高的阑值会导致过 2.7决策树的可伸缩性分简化的树，而较低的闭值可能使得树的化简太少。 已有的决策树算法，如ID3,C4.5对于相对小的数据集是很第二种方法是后剪枝(postpruning)方法。即允许完全生长， 有效的。当这些算法用于大型数据库时，有效性和可伸缩性就成然后剪枝。这种方法被证明在实践中更成功。后剪枝所需的计算 了关注的重点。SLIQ和SPRINT算法解决了可伸缩性。这两种算比先剪枝多，但通常产生更可靠的树。 法都使用预排序技术，对不能放人内存的数据集进行预排序。利同时，剪枝方法可以避免过度拟合，即决策树对当前的训练 用新的数据结构，以利用树的构造。集有十分好的预测效果，但是实际碰到未知的数据时未必十分 3 结论准确。但是，对于非平衡数据进行分类时，剪枝会造成对低概率 分类方法可以通过预测准确率、速度、强壮性、可伸缩性和的类别作为噪声去除。在精确度和简易性之间的权衡是不可避 可解释性等标准进行比较和评估。通过这些标准，我们可以继续免的。剪枝如果导致精确度大大降低，那是毫无意义的。 对决策树算法进行改造，以适应不同的分类要求。参考文献:川 QuinlanJR.InductionofDecisionTree田MachineLearing,1986,1(1):81-106.2RuggieriS.EficientC4.5Q.IEEETransactionsonKnowledgeandDataEngineering,2002,14(2):438-444.3TomM,Mitchel,曾华军，张银奎，等.机器学习M.北京:机械 工业出版社，2002,38-59.4范明，孟小峰等译数据挖掘:概念与技术M北京:机械工业出版社，2001149-184.(上接第8页)可监听计算机端口连接情况。MIB浏览器的测试输人javamibTreeViewmibfile，其中参数mibfile输人MIB文件的位置。Trap事件模块的测试输人javacorbatraperceiver-ORBInitialPotr1050-mmibfle一 engineid发送 trap;javacorbasendtrap-ORBInitialPotr1050-mmibfilelocalhost1.2.01ocalhost121001.5.0trap。经测试，所有功能模块均能良好工作，达到了预期的效果。5 结束语经测试，本模型可应用于大中型的网络管理中，实现分布式透明的网络管理。由于采用Java/CORBA技术，本模型实现的系统具有平台无关性，可在各种操作系统上运行。当前许多著名的开发商，如HP的。penview,IBM的sunnetmanager等采用的都是基于SNMP技术的网络管理模型。将该模型应用其中，能大大提高网管系统的分布式应用能力及各项性能。Java和CORBA的结合使客户端能够访问IDL定义的范围非常广泛的 CORBA对象服务.Java/CORBA的框架总的服务方是规则的CORBA对象，它们与客户端的连接可以是永久的，这种在事务方面的优势，可以保证客户端的实时故障报警响应和动态效果报警显示。用Java技术和CORBA分布式技术来实现网络管理.即可以体现出CORBA分布式的管理思想和CORBA所提供的各种服务，特别是事务服务的功能，又可以充分利用Java技术中的优势。目前正在研究基于CORBA的安全认证和防火墙技术