决策树算法的研究综述

摘要：数据挖掘中一项重要的方法是数据的分类，而决策树是分类算法中一个主要的算法分支，决策树算法是我们在数据挖掘中常常会用到的一种方法。本文重点介绍构造决策树过程中应用最广泛的ID3算法、C4.5算法和GART算法。

关键词：数据挖掘；分类算法；决策树；ID3、C4.5、GART算法

1.引言

随着计算机技术的不断进步，现在已经是互联网时代，互联网时代背景下是海量的数据，在大数据背景下，我们需要对数据进行更高层次的分析，发现数据之前存在的一切潜在的联系及规则。而数据挖掘技术便是将这些看似毫无规则，毫无联系的数据进行预测分析，提取其中有用的信息的过程。

数据挖掘技术中常用的一种分类方法便是决策树。决策树是一个树结构，其每个非叶节点表示一个特征属性上的测试，每個分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。运用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。决策树的应用十分广泛，目前决策树成功运用于医学，制造产业、天文学、分支生物学以及商业等诸多领域。

2.决策树的基本思想

首先，树以代表训练样本的单个结点开始，选择最具有分类能力的属性作为决策树的当前结点。其次根据当前决策结点属性取值的不用，将训练样本数据集分为若干子集，每个取值形成一个分枝。针对上一步得到的一个子集，重复进行先前步骤，形成每个划分样本上的决策树，一旦一个属性出现在一个结点上，就不必在该结点的任何后代考虑它。

3.决策树的构造

决策树的构造主要有两个步骤：分裂属性的选择和树剪枝。

3.1分裂属性的选择

分裂属性的选择就是选择哪个自变量作为树杈，即在n个自变量中，优先选择哪个自变量进行分叉，而采用何种计算方式选择树杈决定了决策树算法的类型，典型的分裂属性的选择的方法有ID3算法、C4.5算法、CART算法三种，三种决策树算法选择树杈的方式是不一样的。

3.1.1 ID3算法

ID3算法是目前决策树算法中较有影响力的算法，它是1986年由Quinlan 提出的，该算法只是一个启发式算法。ID3算法的核心是判断测试哪个属性为最佳的分类属性。ID3算法选择分裂后信息增益最大的属性进行分裂，以信息增益度量属性选择。ID3算法中常用到的两个概念是熵和信息增益。

熵，是刻画任意样本例集的纯度，如果目标属性具有m个不同的值，那么D相对于m这个状态的分类的熵定义为：

[info（D）=-i=1mpilog2（Pi）]

其中Pi表示Pi是m类别的比例。

一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低，更精确来讲，一个属性A相对样本例集合S的信息增益Gain（S，A）被定义为：

gain（A）=info（D）-infoA（D）

A对D划分的期望信息为；

[infoA（D）=j=1vDjDinfo（Dj）]

ID3算法不足之处是只能处理离散型数据，信息增益的选择分裂属性的方式会偏向选择具有大量值得属性.

3.1.2 C4.5算法

ID3算法在实际应用中存在一些问题，于是Quilan在保留ID3算法优点基础上提出了C4.5算法，C4.5算法只是ID3算法的改进算法。C4.5算法采用最大信息增益率的属性被选为分裂属性。C4.5算法中用到了“分裂信息”这一概念，该概念可以表示为：

[split_infoA（D）=-j=1vDjDlog2DjD]

信息增益率的定义是：

[gain_ratio（A）=gainAsplit_info（A）]

C4.5算法是对ID3算法的一种改进，改进后可以计算连续型属性的值。对于连续型属性的值，只需将连续型变量由小到大递增排序，取相邻连个值的中点作为分裂点，然后按照离散型变量计算信息增益的方法计算信息增益，取其中最大的信息增益作为最终的分裂点。

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整的数据进行处理。

3.1.3 GART算法

GART算法选择分裂属性的方式首先要计算不纯度，然后利用不纯度计算Gini指标，然后计算有效子集的不纯度和Gini指标，选择最小的Gini指标作为分裂属性。

不纯度的计算方式为：

[Gimi（D）=1-i=1MP2i]

Pi表示按某个变量划分中，目标变量不同类别的概率。某个自变量的Gini指标的计算方式如下：

[Gini（D）=1-i=1MP2i]

D1和D2分别为按变量的子集所划分出的两个不同元组。

3.2树的剪枝

即在构建树杈时，由于数据中的噪声和离群点，许多分支反映的是训练数据中的异常，而树剪枝则是处理这种过分拟合的数据问题，常用的剪枝方法为先剪枝和后剪枝。

3.2.1先剪枝

通过提前停止树的构造，如通过决定在给定的节点不再分裂或划分训练元组的子集，而对树剪枝，一旦停止，该结点即为树叶。

3.2.2后剪枝

它由完全生长的树剪去子树，通过删除节点的分支，并用树叶替换它而剪掉给定节点的子树，树叶用被替换的子树种最频繁的类标记。

其中C4.5使用悲观剪枝方法，CART采用后剪枝。

总结

数据挖掘中比较热门的就是分类算法的研究，而决策树算法是分类算法中最重要的，在我们的生活中也有着广泛的应用，本文介绍了从最基本的决策树的含义开始定义，到决策树的基本思想，最后介绍了决策树中经典的ID3算法、C4.5算法和CART算法。

参考文献：

[1]韩家炜.数据挖掘：概念与技术第二版[M].北京：机械工业出版社，2001.

[2]王艳兵，赵锐，姚青.基于可变精度的 ID3 改进算法[J].计算机工程与设计，2006，27（14）：2683-2685.

[3]韩松来，张辉，周华平.基于关联度函数的决策树分类算法[J]，计算机应用，2005，25（11）：2655-2657.

[4]Quinlan J R. Introduction of Decision Tree[J].Machine Learning， 1986.

[5]谢金梅，王艳妮.决策树算法综述[J].软件导报，2008，7（11）： 83-85.

作者简介：

田欣（1992.02- ），女，汉族，河北石家庄人，硕士研究生在读，现就读于河北大学管理学院，管理科学与工程专业。