高虹雷，门昌骞，王文剑,2

1(山西大学 计算机与信息技术学院，太原 030006)2(山西大学 计算智能与中文信息处理教育部重点实验室，太原 030006)

E-mail：wjwang@sxu.edu.cn

1 引 言

随着大数据时代的来临，合理高效地对海量数据进行分类从而得到隐藏的、有价值的、可理解的知识，将会对日常生活产生重要的影响.分类作为机器学习的一个核心任务，在数据的分析处理上发挥着重要的作用.常见的分类方法有神经网络[1]、朴素贝叶斯法[2]、K最近邻法[3]、决策树[4]和支持向量机[5]、深度神经网络[6]等.决策树与其它分类算法相比，由于容易实现且易于理解，因而得到了广泛地应用.目前决策树的相关研究集中在决策树改进方面.

传统的决策树算法主要有ID3算法[7]，C4.5算法[8]以及分类与回归决策树(classification and regression tree，CART)[9]等.ID3算法通过使用信息增益准则进行特征选择，但不能处理连续特征值.Quinlan随后将ID3算法进行了改进，提出C4.5算法，采用信息增益比来克服ID3算法的不足，但C4.5算法需要对数据集进行多次的顺序扫描和排序，比较耗时.CART决策树本质上是一棵二叉树，使用Gini指数来进行特征选择，既可以处理连续值也可以处理离散值，被称为数据挖掘领域中里程碑式的算法.

Alsabti等人[10]从抽样方法的角度上提出了一种新的决策树分类器用于处理大规模数据集，在确定最优分裂结点上提供了两种新的度量方法，缩小了搜索空间.此外，Mehta和Agrawal等人提出的一种快速可伸缩分类器SLIQ(Supervised Learning In Quest)[11]对C4.5算法进行了改进，该算法在决策树构造过程中采用了预排序……