决策树算法介绍.docx

3.1 分类与决策树概述 分类与预测分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄、“性别、“收入水平、“职业等属性的值，来估计该用户“信用度属性的值应该取“好还是“差，在这个例子中，所研究的属性“信用度是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 决策树的根本原理1.构建决策树通过一个实际的例子，来了解一些与决策树有关的根本概念。表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名、“年龄、“职业、“月薪、.、“信用等级，每一行是一个客户样本，每一列是一个属性字段。这里把这个表记做数据集D。银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规那么。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规那么，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级的值是“优、“良还是“差，也就是说，要把这客户划分到信用等级为“优、“良、“差这3个类别的某一类别中去。这里把“信用等级这个属性称为“类标号属性。数据集D中“信用等级属性的全部取值就构成了类别集合：Class=“优，“良，“差。在决策树方法中，有两个根本的步骤。其一是构建决策树，其二是将决策树应用于数据库。大多数研究都集中在如何有效地构建决策树，而应用那么相比照拟简单。构建决策树算法比拟多，在Clementine中提供了4种算法，包括C&RT、CHAID、Q。采用其中的某种算法，输入训练数据集，就可以构造出一棵类似于图3.1所示的决策树。一棵决策树是一棵有向无环树，它由假设干个节点、分支、分裂谓词以及类别组成。节点是一棵决策树的主体。其中，没有父亲节点的节点称为根节点，如图3.1中的节点1；没有子节点的节点称为叶子节点，如图3.1中的节点4、5、6、7、8。一个节点按照某个属性分裂时，这个属性称为分裂属性，如节点1按照“年龄被分裂，这里“年龄就是分裂属性，同理，“职业、“月薪也是分裂属性。每一个分支都会被标记一个分裂谓词，这个分裂谓词就是分裂父节点的具体依据，例如在将节点1分裂时，产生两个分支，对应的分裂谓词分别是“年龄<40”与“年龄>=40”。另外，每一个叶子节点都被确定一个类标号，这里是“优、“良或者“差。基于以上描述，下面给出决策树的定义：由此可以看出，构建一棵决策树，关键问题就在于，如何选择一个适宜的分裂属性来进展一次分裂，以及如何制定适宜的分裂谓词来产生相应的分支。各种决策树算法的主要区别也正在于此。2.修剪决策树利用决策树算法构建一个初始的树之后，为了有效地分类，还要对其进展剪枝。这是因为，由于数据表示不当、有噪音等原因，会造成生成的决策树过大或过度拟合。因此为了简化决策树，寻找一颗最优的决策树，剪枝是一个必不可少的过程。通常，决策树越小，就越容易理解，其存储与传输的代价也就越小，但决策树过小会导致错误率较大。反之，决策树越复杂，节点越多，每个节点包含的训练样本个数越少，那么支持每个节点样本数量也越少，可能导致决策树在测试集上的分类错误率越大。因此，剪枝的根本原那么就是，在保证一定的决策精度的前提下，使树的叶子节点最少，叶子节点的深度最小。要在树的大小与正确率之间寻找平衡点。不同的算法，其剪枝的方法也不尽一样。常有的剪枝方法有预剪枝与后剪枝两种。例如CHAID与C5.0采用预剪枝，CART那么采用后剪枝。预剪枝，是指在构建决策树之前，先制定好生长停顿准那么例如指定某个评估参数的阈值，在树的生长过程中，一旦某个分支满足了停顿准那么，那么停顿该分支的生长，这样就可以限制树的过度生长。采用预剪枝的算法有可能过早地停顿决策树的构建过程，但由于不必生成完整的决策树，算法的效率很高，适合应用于大规模问题。后剪枝，是指待决策树完全生长完毕后，再根据一定的准那么，剪去决策树中那些不具一般代表性的叶子节点或者分支。这时，可以将数据集划分为两个局部，一个是训练数据集，一个是测试数据集。训练数据集用来生成决策树，而测试数据集用来对生成的决策树进展测试，并在测试的过程中通过剪枝来对决策树进展优化。3.生成原那么在生成一棵最优的决策树之后，就可以根据这棵决策树来生成一系列规那么。这些规那么采用“If.，Then.的形式。从根节点到叶子节点的每一条路径，都可以生成一条规那么。这条路径上的分裂属性与分裂谓词形成规那么的前件If局部，叶子节点的类标号形成规那么的后件Then局部。例如，图3.1的决策树可以形成以下5条规那么：If年龄<40and职业=“学生 or 职业=“教师Then 信用等级=“优If年龄<40and职业!=“学生 and 职业!=“教师Then 信用等级=“良If年龄>=40and月薪<1000Then 信用等级=“差If年龄>=40and月薪>=1000 and 月薪<=3000Then 信用等级=“良If年龄>=40and月薪>3000Then 信用等级=“优这些规那么即可应用到对未来观测样本的分类中了。ID3算法是最有影响力的决策树算法之一，由Quinlan提出。ID3算法的某些弱点被改善之后得到了C4.5算法；C5.0那么进一步改良了C4.5算法，使其综合性能大幅度提高。但由于C5.0是C4.5的商业版本，其算法细节属于商业机密，因此没有被公开，不过在许多数据挖掘软件包中都嵌入了C5.0算法，包括Clementine。 ID31.信息增益任何一个决策树算法，其核心步骤都是为每一次分裂确定一个分裂属性，即终究按照哪一个属性来把当前数据集划分为假设干个子集，从而形成假设干个“树枝。ID3算法采用“信息增益为度量来选择分裂属性的。哪个属性在分裂中产生的信息增益最大，就选择该属性作为分裂属性。那么什么是信息增益呢？这需要首先了解“熵这个概念。熵，是数据集中的不确定性、突发性或随机性的程度的度量。当一个数据集中的记录全部都属于同一类的时候，那么没有不确定性，这种情况下的熵为0。决策树分类的根本原那么是，数据集被分裂为假设干个子集后，要使每个子集中的数据尽可能的“纯，也就是说子集中的记录要尽可能属于同一个类别。如果套用熵的概念，即要使分裂后各子集的熵尽可能的小。例如在一次分裂中，数据集D被按照分裂属性“年龄分裂为两个子集D1与D2，如图3.2所示。2.ID3算法的流程ID3算法是一个从上到下、分而治之的归纳过程。ID3算法的核心是：在决策树各级节点上选择分裂属性时，通过计算信息增益来选择属性，以使得在每一个非叶节点进展测试时，能获得关于被测试样本最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树节点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树节点的分支，直到所有子集仅包括同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进展分类。下面通过一个实例来了解一下决策树的构建过程。表3-2是一个假想的银行贷款客户历史信息略去了客户姓名，包含14个样本。现要求以这14个样本为训练数据集，以“提供贷款为类标号属性，用ID3算法构造决策树。3.ID3算法的性能分析ID3算法是一种典型的决策树分析算法，后来开展的许多决策树算法都是以ID3算法为根底开展而来的。ID3算法的优点在于它构建决策树的速度比拟快，它的计算时间随问题的难度只是线性地增加，适合处理大批量数据集。同时，ID3算法的缺点也是突出的，包括以下几点。1ID3算法对训练样本的质量的依赖性很强，训练样本的质量主要是指是否存在噪声与是否存在足够的样本。2ID3算法只能处理分类属性离散属性，而不能处理连续属性数值属性。在处理连续属性时，一般要先将连续属性划分为多个区间，转化为分类属性。例如“年龄，要把其数值事先转换为诸如“小于30岁、“3050岁、“大于50岁这样的区间，再根据年龄值落入了某一个区间取相应的类别值。通常，区间端点的选取包含着一定的主观因素与大量的计算。3ID3算法生成的决策树是一棵多叉树，分支的数量取决于分裂属性有多少个不同的取值。这不利于处理分裂属性取值数目较多的情况。因此目前流行的决策树算法大多采用二叉树模型。4ID3算法不包含对树的修剪，无法对决策树进展优化。正因为ID3还存在着许多缺乏的地方，Quinlan对ID3算法进展了改良，并于1993年提出了ID3的改良算法C4.5。3. CC4.5算法的核心思想与ID3完全一样，但在实现方法上做了更好的改良，并增加了新的功能。主要包括：采用“增益比例来选择分裂属性、对连续属性的处理、对样本属性值缺失情况的处理、规那么的产生、穿插验证等。1.用“增益比例来选择分裂属性如前所述，ID3是采用“信息增益来选择分裂属性的。虽然这是一种有效地方法，但其具有明显的倾向性，即它倾向于选择具有大量不同取值的属性，从而产生许多小而纯的子集。尤其是关系数据库中作为主键的属性，每个样本都有一个不同的取值。如果以这样的属性作为分裂属性，那么将产生非常多的分支，而且每一个分支产生的子集的熵均为0因为子集中只有一个样本！。显然，这样的决策树是没有实际意义的。因此，Quinlan提出使用增益比例来代替信息增益。2.连续属性的处理ID3最初的定义假设数据集的各属性都必须是离散的。如果有连续属性，那么可以采用划分区间的方法来离散化。假设在前面的例子中，属性“年龄由于是连续型属性，被划分为“<30”、“30,50、“>50”3个区间，这样属性“年龄 的不同取值就只有3个了，这就是被离散化的过程。在C4.5中，算法采用另外一种方法来实现连续属性的离散化。设数据集中有一连续属性Y，现要测试是否可以选用该属性来对数据集进展分裂以及如何分裂即通过计算信息增益或增益比例来确认Y是否可以作为分裂属性，如果可以，还要确定分裂谓词。例如在表3-3所示的训练数据集中，如果要计算“年龄属性的信息增益，那么首先将不同的属性值排序20，25，28，40，46，55，56，58，60，65，70，那么可能的阈值集合为20，25，28，40，46，55，56，58，60，65，从中一一取出，并形成分裂谓词，例如取出“20”，形成谓词“<=20”与“>20”，用它们划分训练数据集，然后计算信息增益或增益比例。3.处理有缺失值的样本ID3是基于所有属性值都已经确定这一假设的。但是在实际应用中，经常会因为搜集样本时有的样本数据不完整，或者输入数据是有人为的误差等原因，一个数据集中会有某些样本缺少一些属性值。例如在表3-3中，有两个样本的“收入水平缺失了用“？代替。在用一个属性对数据集进展划分时，必须知道一个样本属于哪一类以便于计算每类有多少个样本，进而计算该属性的信息增益，这是根据这个样本的属性值来决定的，但是由于属性值缺失，那么该如何判断这个样本属于哪一类呢？C4.5并不会武断地将一个有缺省值的样本抛弃当然，样本数量很大的时候可以这么做，也不会随意地将它分配到某个类别中去。C4.5会根据其他属性值来计算一个有缺失值的样本属于某个类别的概率，这个样本可以属于每一个类，只是概率不同而已。例如，在表3-3的14个样本中，“收入水平有两个缺失值，其他的12个样本的分布如表3-4所示。4.树的修剪C4.5采用的修剪方法是所谓的“后剪枝，即待决策树完全生长完毕之后，再来修剪掉那些对分类精度奉献不大的叶子节点。对于某个节点，计算该节点分裂之前的误分类损失由于错误地预测了样本的类别而导致的损失与分裂成子树之后的误分类损失，如果分裂后的误分类损失没有得到显著降低，就可以考虑修剪掉这棵子树。在计算分类精度之前，用户可以自行定义各种误分类损失的权重，例如“A类样本被误分类为B类导致的损失比“B类样本误分类为A类导致的损失要大得多，在这种情况下就可以通过设置误分类损失的权重来加以区分。5.规那么的产生C4.5提供了将决策树模型转换为If-Then规那么的算法。规那么存储于一个二维数组中，每一行代表一个规那么。表的每一列代表样本的一个属性，列的值代表了属性的不同取值。例如，0与1分别代表“小于等于阈值与“大于阈值。如果列值为-1，那么代表规那么中不包含该属性。6.穿插验证分类是有监视学习，通过学习可以对未知的数据进展预测。在训练过程开场之前，将一局部数据保存下来，在训练之后，利用这局部数据对学习的结果进展验证，这种模型评估方法称为穿插验证。如果将这个“学习-验证的过程重复k次，就称为k次迭代穿插验证。首先将所有训练数据平均分成k份，每次使用其中一份作为测试样本，其余的k-1份数据作为学习样本，然后选择平均分类精度最高的树作为最后的结果。通常，分类精度最高的树并不是节点最多的树。另外，穿插验证还可以用于决策树的修剪。k次迭代穿插验证非常适合训练样本书目比拟少的情形，但由于要构建k棵决策树，因此，计算量非常大。3. CC5.0是C4.5的一个商业版本，被广泛应用于许多数据挖掘软件包中，如Clementine，但它的准确算法并没有公开。C5.0主要针对大数据集的分类。它的决策树归纳与C4.5很相近，但规那么生成不同。C5.0包括了生成规那么方面的改良。测试结果说明C5.0在内存占用方面的性能改善了大约90%，在运行反而要比C4.5快5.7240倍，并且生成的规那么更加准确。C5.0在精度方面主要的改良源于采用推进方法。一些数据集上的测试结果说明，C5.0的误差率比C4.5的一半还要低。第 20 页