马 强

（长治学院计算机系，山西长治，046011）



数据挖掘中决策树算法的优化应用研究

马 强

（长治学院计算机系，山西长治，046011）

摘要：决策树算法是数据挖掘中一种非常重要的分类方法。决策树具有属性结构和较好的分类预测能力，提供了基本的提取决策规则。本文阐述了决策树算法的基本思想，并分析了决策树算法运用中会遇到的一些问题，并针对性的提出一些建议。

关键词：数据挖掘；决策树算法；应用研究

0　引言

数据挖掘指的就是利用一些分析工具从大量的、不完全的、模糊的、有噪音的、随机的数据中，提取出隐藏在其中的、实现未知并具有价值信息的过程。数据挖掘需要实现建立数据关系模型，对数据进行分析预测。在数据挖掘中，分类是一项非常重要的任务，分类用于预测，预测的目的就是从历史数据中自动推导出数据的描述趋势，从而对未来的数据进行预测。决策树算法是数据挖掘中最常用的方法，其作用于分类阶段，可以直接体现数据特点，分析预测数据，并能方便提取决策规则。

1　决策树的概念

决策树分类算法是数据挖掘中用到比较广并且非常有效的分类方法，包括ID3和C4.5算法，其采用“自上而下、分类治之”的方法，通过一些无序、无规则的事例推测出决策树的分类规则，可以实现对位置数据的分类、预测和数据预处理。决策树方法以分析和归纳利用信息理论为原则，采用流程图式树结构，分为根节点和叶点，最顶层根节点包含信息内容最大，每一分支叶点是代表样品类别或类分布。决策树一般分为构成和剪枝两个步骤，如图1所示：

图1　决策树工作原理流程图

2　常见的决策树算法分析

2.1ID3算法：ID3算法是一种基于信息熵的决策树学习算法，其中引入了Shannon信息论，将信息熵作为选择测试的标准，对实例集进行分类，同时构造决策树来预测如何由测试属性来对整个实例空间进行划分。在ID3算法中的每一个循环过程都是对训练集进行查询来确定属性的信息增益。构造决策树时采用自顶向下的递归方式，将大量数据通过归纳、概括、提炼出事物的属性规律后，以决策树的方式表示出来，如下：

总的来说，在处理大规模学习问题时，选择理论清晰、方法简单的ID3算法，不失为一种知识获取的有用工具。

2.2C4.5算法：C4.5决策树算法是D3 算法的扩展，通过信息熵方法递归形成决策树，具有更加强的连续属性，具有适用广、高效率的特点。对比两种算法的不同之处，一方面表现在C4.5的测试属性技术是信息增益率（信息增益率=信息增益/分割信息量），而ID3算法采用基于信息增益的方法选择测试属性。另一方面表现是C4.5算法不需要独立测试样本集，提高效率，可以直接处理连续属性和属性空缺的样本，这样的产生决策树分枝减少，而ID3算法的连续属性处理是离散化的。例：

3　决策树算法中存在的问题

3.1数据过分相似问题。决策树算法运算过程中产生数据过分相似的原因主要有两点：（1）决策树算法在选择物体属性时不能进行分辨，容易选到一些与自身种类不相关的属性，主要是因为事物本身的属性太多；（2）决策树在运算过程中根据自己的偏好选择各自属性，因此可能就会选择到和种类无关的属性，漏选真正需要的属性。采用决策树修剪法把不相关的属性删除，从而避免选到不相关属性。决策树生长完成后进行剪枝的方法称为后剪枝法，而决策树生长完成前进行剪枝方法称为前剪修法。

3.2取值问题。构建一个好的决策树最主要的难点在于对分支取值进行良好取值。决策树分支建立需要根据字段对不同取值的记录，在每个子集分支下层反复建立分支和节叶点，对不同取值的分枝阶段进行选择。子集记录的划分值不同受到不同的字段值选择的影响，进而影响到信息的规则寻找的优劣。假设依据一个较差的取值来构建决策树分支，即影响决策树的生产速度，也容易出现结构性差和分支过细等不良现象。

4　决策树分类算法的优化

通过分析决策树的两种算法ID3算法与C4.5算法的不同，以及决策树算法中存在的一些问题，主要提出从属性选择、连续属性离散化、抽样方法、综合其他算法的几方面改进决策树分类算法。

4.1属性选择。为了有效避免噪音和干扰属性对数据分类的影响，需要在建立决策树之前对属性重要性进行排序，并且对其重要属性要通过神经网络技术进行训练和检验来预测其精度。按照属性的重要次序依次向两端加减一个邻近的属性并进行训练和检验比较。一直反复进行，直到找的分类效果最佳的n个属性为止。

4.2连续属性离散化。离散化是分类过程中处理连续性的一种有效方法，并且离散化的效率会直接影响到后面机器学习算法的效率和性能。像ID3算法只能够处理离散属性，而C4.5虽然能够处理连续属性，但是其离散化也是系统集成的一个重要步骤。离散化方法可以分为两类：全局离散和局部离散。全局离散需要考虑到属性之间的相互作用，局部离散方法限制一次只能对一个属性进行离散。局部离散相对于全部离散要简单。由于全部离散要同时对所有的属性进行离散，所以计算代价要高于局部离散。

4.3抽样方法。提高决策树的效率可以采用抽样方法。用抽样方法分析决策树构建过程中产生的数据集，分析产生节点过程。抽样分析整个数据库中的子集，再利用抽取的子集样本构建决策树来分析未知样本类别或分类规制。也有其不好的一点就是容易把数据中一些非常有价值的数据模型漏掉。

4.4综合其他算法。通过将遗传算法与决策树算法结合能够得到一个精确度更高的决策树，采用这种方式构建决策树分为两种方法：一种是对决策树编码。以CALTROT算法为例构建一个二叉决策树，这种基于遗传算法构建决策树中其染色体就是决策树，其中又包含众多的二叉决策树，都由两个分支和一个节点组成，通过改变染色体的排列顺序，再选择，加之变异和交叉构建一棵最优的决策树。另一种方法是对决策树不编码，对决策树直接进行变异、操作、交叉和选择，将遗传算法、决策树算法和抽样算法相互结合，弥补子集方法上的缺陷。

5　结束语

随着信息技术的不断发展，数据挖掘分类问题和算法研究成为热点，本文对数据挖掘中决策树算法的应用进行了优化研究。通过分析决策树常见的两种算法以及决策树算法中存在的问题，针对实际问题，主要提出从属性选择、连续属性离散化、抽样方法、综合其他算法的几方面改进决策树分类算法，提高决策树算法的效率和性能。

参考文献

[1]唐华松,姚耀文.数据挖掘中决策树算法的探讨[J].计算机应用研究，2001（8）：18-19+22

[2]王黎明.决策树学习及其剪枝算法研究[D].武汉:武汉理工大学. 2007

[3]林震,王威.基于决策树的数据挖掘算法优化研究[J]. 现代计算机，2012（28）：11-14

作者简介

马强，1980.9，男，长治学院计算机系，讲师，硕士，研究方向：数据挖掘、数据库、软件设计等。

项目资助：长治学院教学研究项目（JY201418）。

Application research on optimization of decision tree in data mining algorithm

Ma Qiang
（Department of Computer Science, Changzhi University，Changzhi,Shanxi，046011）

Abstract：This paper describes the basic idea of the decision tree algorithm,and analyzes some of the problems encountered in the application of the decision tree algorithm,and puts forward some suggestions for the.

Keywords：data mining;The decision tree algorithm;Application research on