龙源期刊网 http://www.qikan.com.cn
浅析数据挖掘分类方法中的决策树算法
作者：徐 枫
来源：《商场现代化》2010年第23期
[摘 要]分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。决策树分类是一种重要的数据分类技术,本文通过对对各种决策树分类算法的基本思想进行阐述,并分析比较了各种算法的主要特性,为使用者选择算法或研究者改进算法提供借鉴。 [关键词]算法 数据挖掘 分类 决策树 一、引言
随着社会的进步和经济的发展,社会各领域活动中会不断产生大量的数据,人们把这些按照一定的数据模型保存在数据库中。数据库中隐藏着许多可以为商业和科研等活动的决策提供所需要的知识,如何有效地获取这些知识,数据挖掘技术中的分类方法正是解决这个问题的可行而有效的方法。
分类方法是一种重要的数据挖掘技术,分类的目的是根据数据集的特点构造一个分类函数或分类模型,该模型能把未知类别的数据映射到给定类别的某一个中。该方法通常用于预测数据对象的离散类别。目前分类方法已被广泛应用于各行各业,如银行信用评估、医疗诊断、高等教育评估和市场营销等实际应用领域。本文将对数据挖掘分类方法中的决策树算法加以分析。
二、数据分类技术概述
数据分类过程主要包含两个步骤:第一步建立一个描述已知数据集类别或概念的模型;该模型是通过对数据库中各数据行内容的分析而获得的。每一数据行都可以认为是属于一个确定的数据类别,其类别值是由一个属性描述(即类别属性)。分类学习方法所使用的数据集称为训练样本集和,因此分类学习又称为监督学习,它是在已知训练样本类别情况下,通过学习建立相应模型;而无监督学习则是训练样本的类别与类别个数均未知的情况下进行的。通常分类学习所获得的模型可以表示为分类规则形式、决策树形式或数学形式。
第二步就是利用所获得的模型进行分类操作,首先对模型分类准确率进行估计,holdout方法就是一种简单的估计方法。它利用一组带有类别的样本进行分类测试(测试样本随机获得且与训练样本相互独立)。对于一个给定数据集所构造出模型的准确性可以通过由该模型所正确分类的数据样本各书所占总测试样本比例得到。
龙源期刊网 http://www.qikan.com.cn
为了提高分类的准确性、效率和可扩展性,在进行分类之前,通常要对数据进行以下预处理。
1.数据清理。主要帮助出去数据中的噪声,并妥善解决遗失数据的问题。 2.相关性分析。其目的是删除那些与分类任务不相关的或冗余的属性。
3.数据转换。利用概念层次树,数据能够被泛化到更高的层次。例如属性“收入”的数值就可以被泛化为“低、中等、高”的离散区间。
以数据库为研究对象,数据挖掘分类模型的构造算法主要有决策树、贝叶斯、神经网络、基于关联和基于数据库技术的方法等。 三、决策树(decision tree)分类算法
所谓决策树就是一个类似流程图的树型结构,决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式,在决策树的内部节点进行属性值的比较,并根据不同的属性值从该结点向下分支,其中树的每个内部节点代表对一个属性的测试,叶结点是要学习划分的类。从根节点到叶结点的一条路径就对应着一条分类规则,整个决策树就对应着一组析取表达式规则。树的最高层点就是根节点。
决策树的生成分为学习和测试两个阶段。决策树学习阶段采用自顶向下的递归方式。决策树算法分两个步骤:一是树的生成,开始时所有数据都在根节点,然后递归地进行数据划分,直至生成叶结点。二是树枝修剪,在一个决策树刚刚建立起来的时候,它其中的许多分支都是根据训练样本集合中的异常数据(由于噪声等原因)构造出来的。树枝修剪就是去掉一些可能是噪声或异常的数据。决策树停止分割的条件是一个节点上的数据都是属于同一个类别;没有属性可以再用于对数据进行分割。决策树模型可以建立得很快,并适合应用到大量的数据上。
目前已经形成的决策树算法有:ID3、C4.5、SLIQ、SPRINT、RainForest、CLS、CHAID、CART、FACT、GINT、SEE5等。其中比较有著名的是Quinlan提出的ID3算法,以及在ID3算法基础上提出的C4.5算法。 1.ID3算法原理
基本决策树构造算法就是一个贪心算法,它采用自顶向下递归的方法构造决策树。著名的决策树算法ID3算法的基本策略如下: (1)树以代表训练样本的单个节点开始。
(2)如果样本都在同一个类中,则这个节点成为树叶结点并标记为该类别。
龙源期刊网 http://www.qikan.com.cn
(3)否则算法使用信息熵(称为信息增益)作为启发知识来帮助选择合适的将样本分类的属性,以便将样本集划分为若干子集。该属性就是相应节点的“测试”或“判定”属性。同时所有属性应当是离散值。
(4)对测试属性的每个已知的离散值创建一个分支,并据此划分样本。
(5)算法使用类似的方法,递归地形成每个划分上的样本决策树。一个属性一旦出现在某个结点上,那么它就不能再出现在该结点之后所产生的子树结点中。 (6)整个递归过程在下列条件之一成立时停止。 给定结点的所有样本属于同一类。
没有剩余属性可以用来进一步划分样本,这时候该结点作为树叶,并用剩余样本中所出现最多的类型作为叶子结点的类型。
某一分枝没有样本,在这种情况下以训练样本集中占多数的类创建一个树叶。
ID3算法的核心是在决策树各级结点上选择属性时,用信息增益作为属性的选择标准,以使得在每一个非结点进行测试时,能获得关于被测试记录最大的类别信息。某属性的信息增益按下列方法计算,通过计算得到每个属性的信息增益,比较它们的大小,就可以获得最大信息增益的属性。
设S是s个数据样本的集合。假设类标号属性具有m个不同值,定义m个不同类别()。设是类别中的样本个数,那么要对一个给定数据对象进行分类所需要的信息量为:
其中是任意一个数据对象属于类别的概率。其中 log函数是以2为底,其原因是信息使用二进制编码。
设属性A具有v个不同的值{}。利用属性A可以将集合S划分为v个子集{},其中包含了S集合中属性A取()值的数据样本。若属性A被选为测试属性,设为子集中属于类别的样本数。由A划分成子集的熵或信息期望可以计算如下:
熵值越小,子集划分的纯度越高。对于给定的子集,其信息期望计算为,其中是
浅析数据挖掘分类方法中的决策树算法
