数据挖掘中的基于决策树的分类方法

1 分类的概念及分类器的评判

分类是数据挖掘中的一个重要课题。分类的目的是学会一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类可用于提取描述重要数据类的模型或预测未来的数据趋势。
分类可描述如下：输入数据，或称训练集（training set）是一条条记录组成的。每一条记录包含若干条属性（attribute），组成一个特征向量。训练集的每条记录还有一个特定的类标签（类标签）与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：(v1,v2,…,…vn:c)。在这里vi表示字段值，c表示类别。

分类的目的是：分析输入数据，通过在训练集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型。这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意是预测，而不能肯定。我们也可以由此对数据中的每一个类有更好的理解。也就是说：我们获得了对这个类的知识。

对分类器的好坏有三种评价或比较尺度：

预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法是10番分层交叉验证法。
计算复杂度：计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。

模型描述的简洁度：对于描述型的分类任务，模型描述越简洁越受欢迎；例如，采用规则表示的分类器构造法就更有用。

分类技术有很多，如决策树、贝叶斯网络、神经网络、遗传算法、关联规则等。本文重点是详细讨论决策树中相关算法。

2 基于决策树的数据分类算法及其性能

2.1 ID3和C4.5算法

决策树技术是用于分类和预测的主要技术，决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事例中推理除决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分支，然后进行剪枝，最后在决策树的叶节点得到结论。所以从根到叶节点就对应着一条合取规则，整棵树就对应着一组析取表达式规则。基于决策树的分类有很多实现算法。ID3和C4.5是较早提出并普遍使用的决策树算法。

Quinlan提出的著名的ID3学习算法是较早的经典算法。它通过选择窗口来形成决策树，是利用信息论中的互信息寻找训练集具有最大信息量的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建立树的分支；在每个分支子集中重复建立树的下层节点和分支过程。C4.5算法和ID3算法相似，它是对ID3算法的一种改进，它是根据信息增益（Information Gain）值选择作为分裂结点的属性及标准,按照此标准将训练集分成若干个子集。这两中种方法的优点是描述简单，分类速度快，分类较准确特别适合大规模的数据处理。但这两种算法是借用信息论中的互信息或信息增益作为单一属性能力的度量，试图减少树的平均深度，忽略了叶子数目的研究，其启发式函数并不是最优的，存在的主要问题还有：（1）抗噪性差，训练例子中正例和反例较难控制。（2）在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。（3）这两种算法只适合于能够驻留于内存的数据集使用,当训练集大得无法在内存容纳时程序无法运行。

2.2 SLIQ算法

SLIQ算法对C4.5决策树分类算法的实现方法进行了改进。

一般决策树中，使用信息量作为评价节点分裂质量的参数，SLIQ算法中使用gini指标代替信息量，gini指标比信息量性能更好，且计算方便，对数据集包含n个类的数据集S，gini(S)定义为：

gini(S) = 1 - ∑pj*pj

pj是S中第j类数据的频率gini越小，Information Gain越大。

区别于一般的决策树 SLIQ采用二分查找树结构 对每个节点都需要先计算最佳分裂方案，然后执行分裂。

对于数值型连续字段分裂的形式A<=v。所以，可以先对数值型字段排序，假设排序后的结果为v1,v2,…,…vn，因为分裂只会发生在两个节点之间，所以有n-1种可能性。通常取中点(vi + vi+1)/2作为分裂点，从小到大依次取不同的split point，取Information Gain指标最大(gini最小)的一个就是分裂点,因为每个节点都需要排序，所以这项操作的代价极大。

对于离散型字段(categorical attribute)，设S(A)为A的所有可能的值，分裂测试将要取遍S的所有子集S'。寻找当分裂成S'和S-S'两块时的gini指标，取到gini最小的时候，就是最佳分裂方法。显然，这是一个对集合S的所有子集进行遍历的过程共需要计算2|S| 次，代价也是很大的。
SLIQ算法对此采用了预排序的技术,以便能够消除在决策树的每个结点对数据集进行排序的需要。所谓预排序,就是针对每个属性的取值,把所有的记录按照从小到大的顺序进行排序。

在C4.5中,树的构造是按照深度优先策略完成的,需要对每个属性列表在每个结点处都进行一遍扫描,费时很多。SLIQ采用广度优先策略构造决策树,即在决策树的每一层只需对每个属性列表扫描一次,就可以为当前决策树中每个叶子结点找到最优分裂标准。
SLIQ的剪枝算法MDL属于迟滞剪枝(post-prunning)算法，通常的迟滞剪枝的数据源采用一个Training Set的一个子集或者与Training Set独立的数据集进行操作。

SLIQ算法具体实现

输入与输出：输入与输出采用下面的方案 输入数据包括训练集配置信息(决策树大小) 输出数据 包括用线性方式表示的二分决策树
算法的控制：算法的控制结构是一个队列，这个队列存放当前的所有叶子节点。这是为了控制广度优先搜索的结束。当队列空时，说明所有的叶子都已经被处理过，这时建树算法结束。

（1）数据准备

系统输入是训练集，训练集是样本向量(v1,v2,…,…vn ：c)组成的集合，每个属性对应训练集的一列，训练集进入以后，分成一个一个的属性表：

(Attribute List){(vi,i)| i<=training data num && i>=0}

i是属性vi的记录索引号，将所有类标识放入类表，类表中的leaf字段指向该记录对应的决策树的叶子，初始状态下，所有记录指向树根，对属性表进行预排序，交换属性值vi，同时交换I，生成有序的属性表序列。排序完成后属性表中的i是属性值指向类表的指针。完成属性表的排序后，数据初始化工作就完成。

（2）计算最佳分裂

当完成数据预处理之后 算法进入往复的求最佳分裂指标的阶段。这一阶段 经过一次对所有属性表的遍历，可以找出所有叶子节点的最佳分裂方案，在这个阶段有一个重要的结构，类直方图(class histogram)，它位于决策树的每个顶点内，存放每个节点当前的类信息——左、右子树的每个类各拥有多少节点。

当前属性A是数值型字段时 每次作遍历时类直方图亦随之改变，随时表征以当前属性A的当前值v为阈值的节点分裂方式对叶子L的分裂状况由Class Histogram即可算出某个分裂方案的gini值，完成对A的遍历后，gini值最小既Information Gain最高的A的值就是用属性A分裂的最佳阈值。新方案可以存入决策树节点。

当前属性是离散型字段时，在遍历过程中记录下每个属性值对应的类的个数，遍历完成后，利用贪心算法得到Information Gain最高的A的子集，

即为所求的用A的分裂方案，新方案可以存入决策树节点。

对整个属性表的每个属性进行一次完全的遍历之后 对每个节点而言，最佳分裂方案包括用哪个属性进行分类以及分类的阈值是什么已经形成。并且存放在决策树的节点内。

（3）升级节点

当最佳分裂参数已经存放在节点中以后，算法的下一步是创建子节点，执行节点分裂(升级类表)。这一步的主要任务是对应该分裂的类表进行更改。

（4）结果输出

算法生成的决策树通过前序遍历的方式存入输出表。

SLIQ的优点有：（1）运算速度快，对属性值只作一次排序。（2）利用整个训练集的所有数据，不作取样处理，不丧失精确度。（3）轻松处理磁盘常驻的大型训练集，适合处理数据仓库的海量历史数据。（4）更快的更小的目标树。（5）低代价的MDL剪枝算法。
SLIQ的存在的缺点有：（1）由于需要将类别列表存放于内存,而类别列表的长度与训练集的长度是相同的,这就一定程度上限制了可以处理的数据集的大小。（2）由于采用了预排序技术,而排序算法的复杂度本身并不是与记录个数成线性关系,因此使得SLIQ算法不可能达到随记录数目增长的线性可扩展性。

2.3 SPRINT算法

为了减少数据量，SPRINT算法改进了SLIQ决策树算法实现时的数据结构，去掉驻留于内存的类别列表，将其合并到每个属性列表中。这样，在寻找当前结点的最优分裂标准时，遍历每个属性列表就不必参照其他信息。但是，对非分裂属性的属性列表进行分裂变得很困难，需要用哈希表记录下每个记录属于个孩子结点。

SPRINT串行算法

算法的基本步骤如下:

Procedure BuildTree (S , A )

(S:训练样本集，A:分类属性集合)

初始化样本集S，生成有序属性列表和直方图，创建节点队列，放人N

while队列不为空

从队列中取出第一个节点N

if N纯or为空then

标记为叶节点，continue

for N的每一个分割点F

计算该节点F上的gini值，选出最佳分割点F* ,N长出分支节点N1,N2，放人队列中.将该分割点的属性列表分割，并用该列表的rids生成记录所在节点的哈希表，用哈希表分割其他属性列表，列表分割同时生成属性直方图。

串行环境下，刚开始SPRINT比SLIQ时间消耗高一些，样本继续增加后，SLIQ时间消耗要比SPRINT高。在并行环境下采用并行算法，相同处理器时相应时间SLIQ要大于SPRINT。

SPRINT算法具备以下优点:（1）训练样本量不受内存限制。（2）具有优秀的伸缩性、加速性和扩容性。（3）并行实现容易，效率高。

SPRINT算法具备以下缺点:（1）使用属性列表，存储代价是原来的三倍。（2）节点分割要创建哈希表，加大系统负担。（3）节点分割处理相对复杂。

以上是几种常用的基于决策树的分类算法，随着算法研究的进行，出现了许多其他基于决策树的算法，它们与神经网络、遗传算法等技术结合，从不同的方面对算法进行了提高。相信以后会出现更多效率更好、准确度更高的算法。