数据分析 论文数据挖掘算法论文——浅析数据挖掘分类方法中的决策树算法.doc

数据分析 论文数据挖掘算法论文浅析数据挖掘分类方法中的决策树算法摘 要分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。决策树分类是一种重要的数据分类技术,本文通过对对各种决策树分类算法的基本思想进行阐述,并分析比较了各种算法的主要特性,为使用者选择算法或研究者改进算法提供借鉴。 关键词算法 数据挖掘 分类 决策树 一、引言 随着社会的进步和经济的发展,社会各领域活动中会不断产生大量的数据,人们把这些按照一定的数据模型保存在数据库中。数据库中隐藏着许多可以为商业和科研等活动的决策提供所需要的知识,如何有效地获取这些知识,数据挖掘技术中的分类方法正是解决这个问题的可行而有效的方法。 分类方法是一种重要的数据挖掘技术,分类的目的是根据数据集的特点构造一个分类函数或分类模型,该模型能把未知类别的数据映射到给定类别的某一个中。该方法通常用于预测数据对象的离散类别。目前分类方法已被广泛应用于各行各业,如银行信用评估、医疗诊断、高等教育评估和市场营销等实际应用领域。本文将对数据挖掘分类方法中的决策树算法加以分析。 二、数据分类技术概述 数据分类过程主要包含两个步骤:第一步建立一个描述已知数据集类别或概念的模型;该模型是通过对数据库中各数据行内容的分析而获得的。每一数据行都可以认为是属于一个确定的数据类别,其类别值是由一个属性描述(即类别属性)。分类学习方法所使用的数据集称为训练样本集和,因此分类学习又称为监督学习,它是在已知训练样本类别情况下,通过学习建立相应模型;而无监督学习则是训练样本的类别与类别个数均未知的情况下进行的。通常分类学习所获得的模型可以表示为分类规则形式、决策树形式或数学形式。 第二步就是利用所获得的模型进行分类操作,首先对模型分类准确率进行估计,holdout方法就是一种简单的估计方法。它利用一组带有类别的样本进行分类测试(测试样本随机获得且与训练样本相互独立)。对于一个给定数据集所构造出模型的准确性可以通过由该模型所正确分类的数据样本各书所占总测试样本比例得到。 为了提高分类的准确性、效率和可扩展性,在进行分类之前,通常要对数据进行以下预处理。 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)如果样本都在同一个类中,则这个节点成为树叶结点并标记为该类别。 (3)否则算法使用信息熵(称为信息增益)作为启发知识来帮助选择合适的将样本分类的属性,以便将样本集划分为若干子集。该属性就是相应节点的“测试”或“判定”属性。同时所有属性应当是离散值。 (4)对测试属性的每个已知的离散值创建一个分支,并据此划分样本。 (5)算法使用类似的方法,递归地形成每个划分上的样本决策树。一个属性一旦出现在某个结点上,那么它就不能再出现在该结点之后所产生的子树结点中。 (6)整个递归过程在下列条件之一成立时停止。 给定结点的所有样本属于同一类。 没有剩余属性可以用来进一步划分样本,这时候该结点作为树叶,并用剩余样本中所出现最多的类型作为叶子结点的类型。 某一分枝没有样本,在这种情况下以训练样本集中占多数的类创建一个树叶。 ID3算法的核心是在决策树各级结点上选择属性时,用信息增益作为属性的选择标准,以使得在每一个非结点进行测试时,能获得关于被测试记录最大的类别信息。某属性的信息增益按下列方法计算,通过计算得到每个属性的信息增益,比较它们的大小,就可以获得最大信息增益的属性。 设S是s个数据样本的集合。假设类标号属性具有m个不同值,定义m个不同类别()。设是类别中的样本个数,那么要对一个给定数据对象进行分类所需要的信息量为: 其中是任意一个数据对象属于类别的概率。其中 log函数是以2为底,其原因是信息使用二进制编码。 设属性A具有v个不同的值。利用属性A可以将集合S划分为v个子集,其中包含了S集合中属性A取()值的数据样本。若属性A被选为测试属性,设为子集中属于类别的样本数。由A划分成子集的熵或信息期望可以计算如下: 熵值越小,子集划分的纯度越高。对于给定的子集,其信息期望计算为,其中是 中样本属于类别的概率。 这样利用属性A对当前分支结点进行相应样本集合划分所获得的信息增益就是: 决策树归纳算法计算每个属性的信息增益,并从中挑选出信息增益最大的属性作为给定集合 的测试属性并由此产生相应的分支结点。所产生的结点被标记为相应的属性,并根据这一属性的不同取值分别产生相应的分支,每个分支代表一个被划分的样本子集。 ID3算法的优点是理论清晰,方法简单,学习能力较强。其缺点是: 只能处理值是离散的属性,不能处理连续值的属性。 计算信息增益时偏向于选择取值较多的属性,不太合理。 对训练集合众属性值或类别给错的数据(即噪声)比较敏感。 在构造树的过程中需要多次扫描数据集,因而导致算法的低效。 只适合驻留于内存中的数据集使用,对训练集合大得无法在内存容纳的数据集无法运行。 2.树枝修剪 在一个决策刚刚建立起来的时候,由于许多分支是由训练样本集和中的异常数据(由于噪声等原因)构造出来的,决策树过于“枝繁叶茂”,这样既降低了树的可理解和可用性,同时也使决策树本身对历史数据的依赖性增大,也就是说这是这棵决策树对此历史数据可能非常准确,一旦应用到新的数据时准确性却急剧下降,这种情况被称为训练过度。为了使得到的决策树所蕴含的规则具有普遍意义,必须对决策树进行修剪。树枝修剪的任务主要是删去一个或更多的树枝,并用叶子替换这些树枝,使决策树简单化,以提高今后分类识别的速度和分类识别新数据的能力。 通常采用两种方法进行树枝的修剪,它们分别是: (1)事前修剪方法。该方法通过提前停止分支生成过程,即通过在当前节点上就判断是否需要继续划分该节点所含训练样本寄来实现。一旦停止分支,当前节点就成为一个叶节点。该叶节点中可能包含多个不同类别的训练样本。由于该修剪是在分支之前做出的,所以称之为事前修剪。 (2)事后修剪方法。该方法是从另一个角度解决训练过度的问题。它在允许决策树得到最充分生长的基础上,再根据一定的规则,剪去决策树中的那些不具有一般代表性的叶节点或分支。修剪后,被修剪的分支节点就成为一个叶节点,并将其标记为它所包含样本中类别个数最多的类别。 3.C4.5算法 C4.5算法在ID3算法的基础上,在以下几个方面进行了改进: (1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性不足。 (2)在树构造过程中进行剪枝。 (3)能够完成对连续属性的离散化处理。 (4)能够对不完整数据进行处理。 C4.5算法产生的分类规则易于理解,准确率较高。但是和ID3算法一样在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,导致算法低效;此外,C4.5也只适合于驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。 4.其他决策树算法 ID3算法和C4.5算法的有效性已经通过对许多小数据集的学习归纳得到了验证。但当应用这些算法对大规模现实世界数据库进行数据挖掘时,算法的有效性和可扩展性就成为应用的关键。近年来,数据挖掘领域中又提出了许多有关决策树可扩展问题的解决方法。其中比较有代表性的算法有SLIQ方法和SPRINT方法。 SLIQ算法对C4.5决策树算法的实现方法进行了改进,在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。所谓预排序,就是针对每个属性的取值,把所有的记录按照从小到大的顺序进行排序,以消除在决策树的每个结点对数据集进行的排序。集体实现时,需要为训练数据集的每个属性创建一个属性列表,为类别属性创建一个类别表。广度优先策略构造决策树,即在决策树的每一层只需对每个属性列表扫描一次,就可以为当前决策树中每个叶结点找到最优分裂标准。SLIQ算法由于采用了上述两种技术,使得该算法能够比C4.5大得多的训练集,在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。 SPRINT算法去掉了SLIQ中需要驻留于内存的类别列表,将其合并到每个属性列表中。这样,在寻找当前结点的最优分裂标准时,遍历每个属性列表就不必参照其他信息。但是,对非分裂属性的属性列表进行分裂变得很困难,需要用哈希表记录下每个记录属于个孩子结点。SPRINT算法具备以下优点:(1)训练样本量不受内存限制。(2)具有优秀的伸缩性、加速性和扩容性。(3)并行实现容易,效率高。SPRINT算法具备以下缺点:(1)使用属性列表,存储代价是原来的三倍。(2)节点分割要创建哈希表,加大系统负担。(3)节点分割处理相对复杂。 此外,RainForest也是一个基于决策树归纳的数据挖掘系统。RainForest可根据当前可用内存的大小,自适应地安排决策树归纳算法的具体操作过程。它保持一个AVC集合(属性值,类别),用以描述每个属性的类别分布。RainForest的归纳速度要高于SPRINT方法。 四、结束语 以上是几种常用的基于决策树的分类算法,随着算法研究的进行,出现了许