决策树方法的研究进展

曹 宁 高 莹 徐根祺

（1.西京学院 工程技术系，陕西 西安710123；2.日立永济电气设备〈西安〉有限公司，陕西 西安710016）

1 数据挖掘的应用背景

随着数据库技术的不断发展及数据库管理系统的推广应用，存储在数据库中的数据量急剧增大， 大量数据背后必定蕴藏着许多信息，如何从数据库中抽取出有用信息逐渐成为商业界普遍关心的问题。数据挖掘的概念为解决这一问题而提出并在近年来引起学术界的广泛关注，成为学术研究的热点。

数据挖掘，又称数据库中的知识发现，是指从大型数据库或数据仓库中提取隐含的、未知的、非平凡的及有潜在应用价值的知识或模式，它是数据库研究中的一个很有应用价值的新领域，融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术。

数据挖掘的任务是从大量的数据中发现模式或知识。模式按其作用可分为两类：一类称为描述型模式，它是对数据中存在的规律做出描述。 如泛化模式、聚类模式、关联模式及时间序列模式。 另一类是预测型模式，它依据从己有数据获得的知识对未知数据的某些性质进行预测。包括分类模式和回归模式。其中，分类模式是一种重要的预测型模式。

用于挖掘分类模式的方法有很多，如决策树方法，贝叶斯网络，遗传算法，基于关联的分类方法，粗糙集，k-最临近方法，等等。其中决策树方法以其易被人理解、需要信息觅少、效率及准确率较高等优点占据着重要地位。 决策树方法自产生至今，先后涌现出多种算法，包括ID3 、C4.5 、 CART, SLIQ、 SPRINTPUBLIC， 基于人机交互的方法等。他们的共同特点是对训练样本集进行挖掘后都会生成一棵形如二叉树或多叉树的决策树。树的叶子节点代表某一类别，非叶节点，包括根节点及内节点代表某个一般属性(非类别属性)的一个测试，测试的一个结果形成非叶节点的一个分枝。从根节点到叶子节点的一条路径形成一条分类规则。 一棵决策树能够很方便的转化为若干条分类规则。人们可以依据分类规则直观地对未知类别的样本进行预测。

2 数据挖掘工具

根据挖掘方法，数据挖掘可分为：机器学习方法、统计方法、神经网络方法和数据库方法。 根据所采用的方法，数据挖掘工具可以大致分为以下六类：

（1）基于规则和决策树的工具：大部分数据挖掘工具采用规则发现和决策树分类技术来发现数据模式和规则， 其核心是某种归纳算法，如ID3 和C4.5 算法。 它通常是对数据库中的数据进行挖掘生成规则和决策树，然后对新数据进行分析和预测。

（2）基于神经元网络的工具：基于神经元网络的工具由于具有对非线性数据的快速建模能力，因此越来越流行。 挖掘过程基本上是将数据簇聚，然后分类计算权伯。

（3）数据可视化方法：这类工具大大扩展了传统商业图形的能力，支持多维数据的可视化，同时提供了进行数据分析的图形方法。

（4）模糊发现方法：应用模糊逻辑进行数据查询排序。

（5）统计方法：这此工具没有使用人下智能技术，因此更适于分析现有信息，而不是从原始数据中发现数据模式和规则。

（6）综合方法：许多工具采用了多种挖掘方法，一般规模较大。

3 决策树方法的优缺点

决策树，又称判定树，是一种类似二叉树或多叉树的树结构。树中的每个非叶节点(包括根节点)对应于训练样本集中一个非类别属性的测试，非叶节点的每一个分枝对应属性的一个测试结果，每个叶子节点则代表一个类或类分布。从根节点到叶子节点的一条路径形成一条分类规则。 决策树可以很方便地转化为分类规则，是一种非常直观的分类模式表示形式。

相对于其它分类方法，决策树算法应用最为广泛，其独特的优点包括：（1）可以生成可以理解的规则；（2）计算量相对来说不是很大；（3）可以处理连续和种类字段；（4） 决策树可以清晰地显示哪些字段比较重要。

当然，决策树也存在着很多的缺点：（1）对连续性的字段比较难预测；（2）对有时间顺序的数据，需要很多预处理工作；（3）当类别太多时，错误可能会增加比较快；（4）一般算法分类的时候，只是根据一个字段来分类。

4 决策树方法的主要研究进展

4.1 决策树的精度

决策树的预测精度一直是研究的重点，判断各种决策树的生成算法和剪枝算法的优劣，精度是最重要的衡量指标。 构造多变量决策树是为了减小树的规模，其最终目的是为了提高决策树的精度。 如何提高决策树的预测精度是决策树方法的研究方向之一。

4.2 决策树技术与其他技术的结合

在知识发现中，不可能用一种方法处理所有的数据集，完成各种数据采掘任务，需要研究同其它方法相结合的问题。并且，决策树方法本身也可以和其它方法结合，现在已有人把决策树方法同神经网络技术、模糊集理论、遗传算法等相结合来进行研究，结果不同程度地提高了处理效率和精度。多种方法的交叉结合也是决策树方法研究的方向之一。

4.3 寻找更好的简化决策树方法

简化决策树的研究工作主要有两个方面，一是对比各种不同的简化决策树方法，分析它们各自的特性、优点和缺点。另外一个就是寻找更好的与传统方法不同的简化决策树的方法，这一直是决策树技术研究的一个热点。

4.4 不确定环境下决策树研究

实际的数据集中存在着一些缺值数据，最简单的方案是删除带有未属性值的例子或是将未知属性值用最常用的值代替，Quinlan J R 提出的一种解决方案是依据对象的其它属性值和类信息来预测未知属性的属性值。 对缺值数据的处理一直是决策树研究的热点。

4.5 决策树技术的软件实现

将决策树技术软件化一直是决策树技术的方向之一。如何开发出功能更加强大、使用更加方便、界面更加友好的软件以实现决策树技术，一直是大家努力的方向。

5 小结

决策树算法已经有了广泛的应用，并且已经有了许多成熟的系统，这此系统广泛应用于各个领域，如语音识别，模式识别，专家系统等。 但是，解决一个复杂的数据挖掘问题的任何算法都要面临以下问题：从错误的数据中学习、从分布的数据中学习、从有偏的数据中学习、学习有弹性的概念、 学习那些抽象程度不同的概念、 整合定性与定量的发现等，归纳学习当中还有很多未开发的课题等待我们去研究。

［1］李卿.决策树优化算法研究[D].西南交通大学,2009.

［2］万永锋.决策树学习算法在金融自助设备监控系统中的应用[D].郑州大学,2007.

［3］戴南.基于决策树的分类方法研究[D].南京师范大学,2003

［4］李明仑.基于动态模糊格的决策树理论及应用研究[D].苏州大学,2006.

［5］成文丽.基于决策树的数据挖掘算法的技术研究[D].太原理工大学,2003.