数据挖掘中决策树算法及其应用
文章编号：1006-1576（2005）02-0035-02
数据挖掘中决策树算法及其应用
黄晓芳
（西南科技大学计算机科学学院，四川绵阳 621010）
摘要：决策树算法通过构造精度高、小规模的决策树采掘训练集中的分类知识。在客户关系管理系统中，采用了SQL Server 2000/Analysis Service两层结构决策树算法，以类记数表及深度优先策略生成决策树，在建树算法和数据库间设立数据挖掘中间件。应用结果表明用该方法实现保留高价值客户，发掘潜力客户。
关键词：决策树；数据挖掘；客户关系；中间件
中图分类号：TP301.6 文献标识码：A
Algorithm of Decision Tree in Data Mining and Its Application
HUANG Xiao-fang
(College of Computer Science, Southwest Science & Technology University, Mianyang 621010, China)
Abstract: Decision tree algorithm is that the category knowledge of the training set is mined through built high precision and small-scale decision tree. Two layers decision tree algorithm of SQL server 2000/analysis service was adopted in management system for relationship of clients. The decision tree was created by class count table and depth first strategy. A data mining middleware was set up between the algorithm built tree and database. The result of the application shows that the retention of the high value clients are reserved and the potential ones are mined by this way.
Keywords: Decision tree; Data mining; Client relationship management; KDD
1 引言
数据库中知识发现[1]（KDD：Knowledge Discovery in Database）技术难点是数据挖掘。数据挖掘技术的主要算法有：统计分析方法、神经元网络、决策树方法、遗传算法等，其中决策树算法通过构造决策树发现训练集中分类知识，其核心是如何构造精度高、规模小的决策树。
2 决策树算法
决策树算法围绕决策树的两个阶段展开：第一阶段，决策树构建。通过递归地算法将训练集生成一棵决策树。第二阶段，由测试数据检验生成的决策树，消除由于统计噪声或数据波动对决策树的影响来达到净化树的目的，得到一棵正确的决策树。
2.1 决策树的构建
(1) 决策树的构建步骤[2]：
①对训练集E，若E的记录都属于同一类(纯的)，类别属性值为Xi，则选择Xi作为叶节点（也是根节点），结束；否则把E作为当前数据集；
②对于当前数据集，选择最佳分割标准，把数据集划分为不同子数据集；
③逐个处理子数据集，若子数据集是纯的。类别属性值为Xi’，则选择Xi’作为叶节点，转④；否则，把该子数据集作为当前数据集，转②；
④若子数据集处理完，结束：否则转③。
决策树算法的关键是对决策树进行最佳分割，涉及两方面问题：第一，从众多的输入变量中找到一个最佳的分组变量；第二，从分组变量的众多取值中找到一个最佳阀值。根据分割方法的不同，决策树算法分为两类：基于信息论方法（ID3、C4.5）和最小GINI指标方法（CART、SLIQ、SPRINT）。
(2) 基于信息论的方法
算法ID3／C4.5使用信息增益作为选择属性对节点进行划分的指标。信息增益最高的划分将被作为分裂方案。1948年，C.E.Shannon提出了信息论。对信息量（Information）和熵（Entropy）的定义为：Information＝-log2p i
Entropy＝-∑p i log2(p i)
设数据集S有(A1,A2,…,An)，C共n+l个属性。其中分类属性C有m个不同的离散属性值(c1,c2,…,c m)。即数据集S中的记录可分成m个类别。设数据集S中全部的记录数为s，分类属性值为(c1,c2,…,c m)的记录数分别为(s1,s2,…,s m)。那么划分之前，数据集S的总熵为：
E(s1,s2,…,s m)=-∑p i log2(p i)
其中p i是S中任意一个记录属于类别Ci的概率，即P=(|C1|/|S|,|C2|/|S| ,…, |C m|/|S|)
设属性A具有V个不同的离散属性值，使用属性A把数据集S划分成V个子集(s1,s2,…,s v)。设子
收稿日期：2004-09-10；修回日期：2004-11-01
作者简介：黄晓芳（1977-），女，四川人，2002年毕业于西南科技大学，现西南科技大学在读硕士，从事数据挖掘及CRM系统研究。
·35·
集Sj中的记录数为s j，分类属性值为(c1,c2,…,c m)的记录数分别为(s1j,s2j,…,s mj)。子集Sj的熵为：E(s1j,s2j,…,s vj)=-∑p ij log2(p ij)
p ij是S j中记录属于类别C i的概率，用S ij/S j
估计。引入信息增益：表示系统由分类获得的信息量。由系统熵的减少值描述。将数据集S用属性A
划分后的信息增益为数据集S划分前后的熵差：Gain(A)=E(s1, s2, …, s m)-E(A)
选择属性对节点迸行划分的标准：划分属性
应具有最高信息增益。熵是一个衡量系统混乱程
度的统计量。熵越大，表示系统越混乱。分类的目
的是提取系统信息，划分后熵的减少量就是信息
增益，所以，选择属性对节点进行划分的标准就
是选取信息增益最大的属性。通常，决策树是用“贪心算法+深度优先搜索”得到。
(3) 最小GINI指标方法
如果决策树是二叉树，常用基尼指数作为划分的标准。CART算法采用基尼指数作为选择属性对节点进行划分的标准。数据集S的分类属性C有m 个不同离散属性值(c1,c2,...c m)，即S中的记录有m 个类别，基尼指数就是：Gini(S)＝1-∑(i=1,m)P2i。P i是类别c i出现的频率。用属性A将数据集S分成两部分S1,S2。这个划分的基尼指数就是：Gini(S)=(S1/S)*Gini(S1)+(S2/S) *Gini(S2)
选择基尼指数最小属性对节点数据划分。决策树是二叉树时，设离散型属性A有V个属性值，则属性A可有2v种划分数据集S的方法，其中一个划分方法的基尼指数最小，称之为属性A的最佳划分方法。在选择节点最佳划分时，找出每个属性的最佳划分方法，比较所有属性的划分方法，从中选出基尼指数最小者，最后选出节点最佳划分[5]。
2.2 决策树的修剪
剪枝算法分为前剪枝和后剪枝算法。前剪枝
算法是在树的生长过程完成前就进行剪枝。后剪
枝算法是当决策树的生长过程完成后再进行剪枝。
目前决策树修剪策略有三种：基于代价复杂度修剪、悲观修剪和MDL（Minimum Description Length，最小描述长度）修剪。基于代价复杂度修剪使用了独立的样本集用于修剪，即与用于树的构建过程中使用的样本集不同，称为修剪样本。它首先从训练数据中生成一系列增量式的小树，然后依据剪枝集的分类精度，选择一棵作为剪枝树。悲观修剪Quinlan在1987年提出，将训练样本都用于树的构建与修剪并用统计相关的测试来判断剪去某一枝前后的预测错误率。在实际使用中用的较多的是MDL修剪。当数据集较大时，一般使用需要单独剪枝集的剪枝算法，这样剪枝的可信度高；但当数据量不大时，单独的剪枝集会影响树的生长，一般采用不需要单独剪枝集的算法。近来有人发现MDL剪枝算法对用大数据集生成的树很有效。
3 决策树算法在客户关系管理的应用及结论
客户关系管理是一种旨在加强企业与客户之间关系的新的管理机制。其中，如何利用数据挖掘技术对客户数据进行深层分析，保留高价值客户，发掘潜力客户，实现在恰当的时间，为客户提供合适产品和服务是现在客户关系管理中的研究重点。
为此，利用商业银行提供的客户信息和银行业务信息等数据，通过客户存款情况，研究忠实客户的特征，以帮助银行留住客户并最大化客户价值。
该数据有6587个样本，包括38个客户特征描述变量和34个业务统计变量。客户特征描述变量包括客户的基本数据。业务统计变量包括银行业务信息记录。
本研究工作利用SQL Server 2000/Analysis Service中的微软决策树算法，采用类记数表（Class Count table, CC table）以及深度优先的策略生成决策树。为了能高效地分裂节点的类记数表，微软决策树算法采用了两层结构[7]。在建树算法和数据库之间设立了一个数据挖掘中间件，如图1所示。
图1 微软决策树算法结构
决策树结果表明：有活期存款的客户在一年内有一半可能走掉，有活期和定期存款的客户有三分之一的可能走掉，而有三种或以上的客户离开的概率可能会下降到15％。以客户为中心增加产品的种类和销售不仅可在短期内赢利，而且可留住客户。参考文献：
[1] 门志勇. CRM系统及应用研究[D]. 北京: 首都经济贸易
大学, 2002. 17.
[2] 朱绍文, 胡宏银, 王泉德, 等. 决策树采掘技术及发展
趋势[J]. 计算机工程, 2000, 26 (10).
[3] Breiman L Friedman, H H R A, Stone C J. Classification
Regression Trees [Z]. Wadsworth International Group, 1984.
[4] 曲东荣. CRM在中国银行领域中的应用[J]. 中国金融电
脑, 2000, (10).
[5] S Chaudhuri, U Fayyad, J Bernhardt. Scalable Classification
over SQL Databases [A]. In Proc.ICDE-99, Sydney, Australia, IEEE Computer Society [C]. 1999. 472-478.
·36·
决策树算法研究及应用概要
决策树算法研究及应用? 王桂芹黄道 华东理工大学实验十五楼206室 摘要:信息论是数据挖掘技术的重要指导理论之一,是决策树算法实现的理论依据。决 策树算法是一种逼近离散值目标函数的方法,其实质是在学习的基础上,得到分类规则。本文简要介绍了信息论的基本原理,重点阐述基于信息论的决策树算法,分析了它们目前 主要的代表理论以及存在的问题,并用具体的事例来验证。 关键词:决策树算法分类应用 Study and Application in Decision Tree Algorithm WANG Guiqin HUANG Dao College of Information Science and Engineering, East China University of Science and Technology Abstract:The information theory is one of the basic theories of Data Mining,and also is the theoretical foundation of the Decision Tree Algorithm.Decision Tree Algorithm is a method to approach the discrete-valued objective function.The essential of the method is to obtain a clas-sification rule on the basis of example-based learning.An example is used to sustain the theory. Keywords:Decision Tree; Algorithm; Classification; Application 1 引言 决策树分类算法起源于概念学习系统CLS(Concept Learning System,然后发展 到ID3
R语言-决策树算法知识讲解
R语言-决策树算法
决策树算法 决策树定义 首先，我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 观察上图，我们判决鸢尾花的思考过程可以这么来描述：花瓣的长度小于 2.4cm的是setosa(图中绿色的分类)，长度大于1cm的呢?我们通过宽度来判别，宽度小于1.8cm的是versicolor(图中红色的分类)，其余的就是 virginica(图中黑色的分类) 我们用图形来形象的展示我们的思考过程便得到了这么一棵决策树： 这种从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。 前面我们介绍的k-近邻算法也可以完成很多分类任务，但是他的缺点就是含义不清，说不清数据的内在逻辑，而决策树则很好地解决了这个问题，他十分好理解。从存储的角度来说，决策树解放了存储训练集的空间，毕竟与一棵树的存储空间相比，训练集的存储需求空间太大了。 决策树的构建 一、KD3的想法与实现 下面我们就要来解决一个很重要的问题：如何构造一棵决策树?这涉及十分有趣的细节。 先说说构造的基本步骤，一般来说，决策树的构造主要由两个阶段组成:第一阶段，生成树阶段。选取部分受训数据建立决策树，决策树是按广度优先建立直到每个叶节点包括相同的类标记为止。第二阶段，决策树修剪阶段。用剩余数据检验决策树，如果所建立的决策树不能正确回答所研究的问题，我们要对决策树进行修剪直到建立一棵正确的决策树。这样在决策树每个内部节点处进行属性值的比较，在叶节点得到结论。从根节点到叶节点的一条路径就对应着一条规则，整棵决策树就对应着一组表达式规则。 问题：我们如何确定起决定作用的划分变量。 我还是用鸢尾花的例子来说这个问题思考的必要性。使用不同的思考方式，我们不难发现下面的决策树也是可以把鸢尾花分成3类的。 为了找到决定性特征，划分出最佳结果，我们必须认真评估每个特征。通常划分的办法为信息增益和基尼不纯指数，对应的算法为C4.5和CART。 关于信息增益和熵的定义烦请参阅百度百科，这里不再赘述。 直接给出计算熵与信息增益的R代码：
数据挖掘-决策树
创建Analysis Services 项目 更改存储数据挖掘对象的实例 创建数据源视图 创建用于目标邮件方案的挖掘结构 创建目标邮件方案的第一步是使用Business Intelligence Development Studio 中的数据挖掘向导创建新的挖掘结构和决策树挖掘模型。 在本任务中，您将基于Microsoft 决策树算法创建初始挖掘结构。若要创建此结构，需要首先选择表和视图，然后标识将用于定型的列和将用于测试的列 1.在解决方案资源管理器中，右键单击“挖掘结构”并选择“新建挖掘 结构”启动数据挖掘向导。 2.在“欢迎使用数据挖掘向导”页上，单击“下一步”。 3.在“选择定义方法”页上，确保已选中“从现有关系数据库或数据仓 库”，再单击“下一步”。 4.在“创建数据挖掘结构”页的“您要使用何种数据挖掘技术？”下， 选择“Microsoft 决策树”。 5.单击“下一步”。 6.在“选择数据源视图”页上的“可用数据源视图”窗格中，选择 Targeted Mailing。可单击“浏览”查看数据源视图中的各表，然后单击“关闭”返回该向导。 7.单击“下一步”。
8.在“指定表类型”页上，选中vTargetMail 的“事例”列中的复选 框以将其用作事例表，然后单击“下一步”。稍后您将使用 ProspectiveBuyer 表进行测试，不过现在可以忽略它。 9.在“指定定型数据”页上，您将为模型至少标识一个可预测列、一 个键列以及一个输入列。选中BikeBuyer行中的“可预测”列中的复选框。 10.单击“建议”打开“提供相关列建议”对话框。 只要选中至少一个可预测属性，即可启用“建议”按钮。“提供相关列建议”对话框将列出与可预测列关联最密切的列，并按照与可预测属性的相互关系对属性进行排序。显著相关的列（置信度高于95%）将被自动选中以添加到模型中。 查看建议，然后单击“取消”忽略建议。 11.确认在CustomerKey行中已选中“键”列中的复选框。 12.选中以下行中“输入”列中的复选框。可通过下面的方法来同 时选中多个列：突出显示一系列单元格，然后在按住Ctrl 的同时选中一个复选框。 1.Age https://www.wendangku.net/doc/d24980255.html,muteDistance 3.EnglishEducation 4.EnglishOccupation 5.Gender 6.GeographyKey
决策树算法介绍(DOC)
3.1 分类与决策树概述 3.1.1 分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2 决策树的基本原理 1.构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={“优”，
(完整版)生物数据挖掘-决策树实验报告
实验四决策树 一、实验目的 1.了解典型决策树算法 2.熟悉决策树算法的思路与步骤 3.掌握运用Matlab对数据集做决策树分析的方法 二、实验内容 1.运用Matlab对数据集做决策树分析 三、实验步骤 1.写出对决策树算法的理解 决策树方法是数据挖掘的重要方法之一，它是利用树形结构的特性来对数据进行分类的一种方法。决策树学习从一组无规则、无次序的事例中推理出有用的分类规则，是一种实例为基础的归纳学习算法。决策树首先利用训练数据集合生成一个测试函数，根据不同的权值建立树的分支，即叶子结点，在每个叶子节点下又建立层次结点和分支，如此重利生成决策树，然后对决策树进行剪树处理，最后把决策树转换成规则。决策树的最大优点是直观，以树状图的形式表现预测结果，而且这个结果可以进行解释。决策树主要用于聚类和分类方面的应用。 决策树是一树状结构，它的每一个叶子节点对应着一个分类，非叶子节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。构造决策树的核心问题是在每一步如何选择适当的属性对样本进行拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策树是一个自上而下分而治之的过程。 2.启动Matlab，运用Matlab对数据集进行决策树分析，写出算法名称、数据集名称、关键代码，记录实验过程，实验结果，并分析实验结果 (1)算法名称: ID3算法 ID3算法是最经典的决策树分类算法。ID3算法基于信息熵来选择最佳的测试属性，它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行，测试属性有多少个不同的取值就将样本集划分为多少个子样本集，同时决策树上相应于该样本集的节点长出新的叶子节点。ID3算法根据信息论的理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性：信息增益值越大，不确定性越小。因此，ID3算法在每个非叶节点选择信息增益最大的属性作为测试属性，这样可以得到当前情况下最纯的划分，从而得到较小的决策树。 ID3算法的具体流程如下： 1）对当前样本集合，计算所有属性的信息增益； 2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本集； 3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处；否则对子样本集递归调用本算法。 (2)数据集名称：鸢尾花卉Iris数据集 选择了部分数据集来区分Iris Setosa（山鸢尾）及Iris Versicolour（杂色鸢尾）两个种类。
数据挖掘决策树算法Java实现
import java.util.HashMap; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.Iterator; //调试过程中发现4个错误，感谢宇宙无敌的调试工具——print //1、selectAtrribute中的一个数组下标出错 2、两个字符串相等的判断 //3、输入的数据有一个错误 4、selectAtrribute中最后一个循环忘记了i++ //决策树的树结点类 class TreeNode { String element; //该值为数据的属性名称 String value; //上一个分裂属性在此结点的值 LinkedHashSet
数据挖掘及决策树
理工大学信息工程与自动化学院学生实验报告 （ 2016 — 2017 学年第学期） 信自楼444 一、上机目的及容 目的： 1．理解数据挖掘的基本概念及其过程； 2．理解数据挖掘与数据仓库、OLAP之间的关系 3．理解基本的数据挖掘技术与方法的工作原理与过程，掌握数据挖掘相关工具的使用。 容： 给定AdventureWorksDW数据仓库，构建“Microsoft 决策树”模型，分析客户群中购买自行车的模式。 要求: 利用实验室和指导教师提供的实验软件，认真完成规定的实验容，真实地记录实验中遇到的 二、实验原理及基本技术路线图（方框原理图或程序流程图） 请描述数据挖掘及决策树的相关基本概念、模型等。 1.数据挖掘：从大量的、不完全的、有噪音的、模糊的、随机的数据中，提取隐含在其中的、 人们事先不知道的、但又潜在有用的信息和知识的过程。
项集的频繁模式 分类与预测分类：提出一个分类函数或者分类模型，该模型能把数据库中的数据项 映射到给定类别中的一个； 预测：利用历史数据建立模型，再运用最新数据作为输入值，获得未来 变化趋势或者评估给定样本可能具有的属性值或值的围 聚类分析根据数据的不同特征，将其划分为不同数据类 偏差分析对差异和极端特例的描述，揭示事物偏离常规的异常现象，其基本思想 是寻找观测结果与参照值之间有意义的差别 3.决策树：是一种预测模型，它代表的是对象属性与对象值之间的一种映射关系。树中每个 节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从 根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输 出，可以建立独立的决策树以处理不同输出。 算法概念 ID3 在实体世界中，每个实体用多个特征来描述。每个特征限于在一 个离散集中取互斥的值 C4.5 对ID3算法进行了改进： 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选 择取值多的属性的不足；在树构造过程中进行剪枝；能够完成对 连续属性的离散化处理；能够对不完整数据进行处理。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及Microsoft SQL Server套件 四、实验方法、步骤（或：程序代码或操作过程） （一）准备 Analysis Services 数据库 1.Analysis Services 项目创建成功
决策树算法的原理与应用
决策树算法的原理与应用 发表时间：2019-02-18T17:17:08.530Z 来源：《科技新时代》2018年12期作者：曹逸知[导读] 在以后，分类问题也是伴随我们生活的主要问题之一，决策树算法也会在更多的领域发挥作用。江苏省宜兴中学江苏宜兴 214200 摘要：在机器学习与大数据飞速发展的21世纪，各种不同的算法成为了推动发展的基石.而作为十大经典算法之一的决策树算法是机器学习中十分重要的一种算法。本文对决策树算法的原理，发展历程以及在现实生活中的基本应用进行介绍，并突出说明了决策树算法所涉及的几种核心技术和几种具有代表性的算法模式。 关键词：机器学习算法决策树 1.决策树算法介绍 1.1算法原理简介 决策树模型是一种用于对数据集进行分类的树形结构。决策树类似于数据结构中的树型结构，主要是有节点和连接节点的边两种结构组成。节点又分为内部节点和叶节点。内部节点表示一个特征或属性, 叶节点表示一个类. 决策树(Decision Tree),又称为判定树, 是一种以树结构(包括二叉树和多叉树)形式表达的预测分析模型，决策树算法被评为十大经典机器学习算法之一[1]。 1.2 发展历程 决策树方法产生于上世纪中旬，到了1975年由J Ross Quinlan提出了ID3算法，作为第一种分类算法模型，在很多数据集上有不错的表现。随着ID3算法的不断发展，1993年J Ross Quinlan提出C4.5算法，算法对于缺失值补充、树型结构剪枝等方面作了较大改进，使得算法能够更好的处理分类和回归问题。决策树算法的发展同时也离不开信息论研究的深入，香农提出的信息熵概念，为ID3算法的核心，信息增益奠定了基础。1984年，Breiman提出了分类回归树算法，使用Gini系数代替了信息熵，并且利用数据来对树模型不断进行优化[2]。2．决策树算法的核心 2.1数据增益 香农在信息论方面的研究，提出了以信息熵来表示事情的不确定性。在数据均匀分布的情况下，熵越大代表事物的越不确定。在ID3算法中，使用信息熵作为判断依据，在建树的过程中，选定某个特征对数据集进行分类后，数据集分类前后信息熵的变化就叫作信息增益，如果使用多个特征对数据集分别进行分类时，信息增益可以衡量特征是否有利于算法对数据集进行分类，从而选择最优的分类方式建树。如果一个随机变量X的可以取值为Xi（i=1…n），那么对于变量X来说，它的熵就是
决策树算法介绍
3.1分类与决策树概述 3.1.1分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病 症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是E—个离散属性，它的取值是一个类别值，这种问题在数 据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这 里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种 问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2决策树的基本原理 1. 构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D,建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是 “差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3 个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={ “优”，
决策树分类算法与应用
机器学习算法day04_决策树分类算法及应用课程大纲 决策树分类算法原理决策树算法概述 决策树算法思想 决策树构造 算法要点 决策树分类算法案例案例需求 Python实现 决策树的持久化保存 课程目标： 1、理解决策树算法的核心思想 2、理解决策树算法的代码实现 3、掌握决策树算法的应用步骤：数据处理、建模、运算和结果判定
1. 决策树分类算法原理 1.1 概述 决策树（decision tree）——是一种被广泛使用的分类算法。 相比贝叶斯算法，决策树的优势在于构造过程不需要任何领域知识或参数设置 在实际应用中，对于探测式的知识发现，决策树更加适用 1.2 算法思想 通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话： 女儿：多大年纪了？ 母亲：26。 女儿：长的帅不帅？ 母亲：挺帅的。 女儿：收入高不？ 母亲：不算很高，中等情况。 女儿：是公务员不？ 母亲：是，在税务局上班呢。 女儿：那好，我去见见。 这个女孩的决策过程就是典型的分类树决策。 实质：通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见 假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑
上图完整表达了这个女孩决定是否见一个约会对象的策略，其中： ◆绿色节点表示判断条件 ◆橙色节点表示决策结果 ◆箭头表示在一个判断条件在不同情况下的决策路径 图中红色箭头表示了上面例子中女孩的决策过程。 这幅图基本可以算是一颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。 决策树分类算法的关键就是根据“先验数据”构造一棵最佳的决策树，用以预测未知数据的类别 决策树：是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
数据挖掘——决策树分类算法 (1)
决策树分类算法 学号：20120311139 学生所在学院：软件工程学院学生姓名：葛强强 任课教师：汤亮 教师所在学院：软件工程学院2015年11月
12软件1班 决策树分类算法 葛强强 12软件1班 摘要：决策树方法是数据挖掘中一种重要的分类方法，决策树是一个类似流程图的树型结构，其中树的每个内部结点代表对一个属性的测试，其分支代表测试的结果，而树的每个 叶结点代表一个类别。通过决策树模型对一条记录进行分类，就是通过按照模型中属 性测试结果从根到叶找到一条路径，最后叶节点的属性值就是该记录的分类结果。 关键词：数据挖掘，分类，决策树 近年来，随着数据库和数据仓库技术的广泛应用以及计算机技术的快速发展，人们利用信息技术搜集数据的能力大幅度提高，大量数据库被用于商业管理、政府办公、科学研究和工程开发等。面对海量的存储数据，如何从中有效地发现有价值的信息或知识，是一项非常艰巨的任务。数据挖掘就是为了应对这种要求而产生并迅速发展起来的。数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用的信息，提取的知识表示为概念、规则、规律、模式等形式。 分类在数据挖掘中是一项非常重要的任务。 分类的目的是学会一个分类函数或分类模型，把数据库中的数据项映射到给定类别中的某个类别。分类可用于预测，预测的目的是从历史数据记录中自动推导出对给定数据的趋势描述，从而能对未来数据进行预测。分类算法最知名的是决策树方法，决策树是用于分类的一种树结构。 1决策树介绍 决策树（decisiontree）技术是用于分类和预测 的主要技术，决策树学习是一种典型的以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较，并根据不同属性判断从该节点向下的分支，在决策树的叶节点得到结论。所以从根到叶节点就对应着一条合取规则，整棵树就对应着一组析取表达式规则。 把决策树当成一个布尔函数。函数的输入为物体或情况的一切属性（property），输出为”是”或“否”的决策值。在决策树中，每个树枝节点对应着一个有关某项属性的测试，每个树叶节点对应着一个布尔函数值，树中的每个分支，代表测试属性其中一个可能的值。 最为典型的决策树学习系统是ID3，它起源于概念学习系统CLS，最后又演化为能处理连续属性的C4．5（C5．0）等。它是一种指导的学习方法，该方法先根据训练子集形成决策树。如果该树不能对所有给出的训练子集正确分类，那么选择一些其它的训练子集加入到原来的子集中，重复该过程一直到时形成正确的决策集。当经过一批训练实例集的训练产生一棵决策树，决策树可以根据属性的取值对一个未知实例集进行分类。使用决策树对实例进行分类的时候，由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。 决策树是应用非常广泛的分类方法，目前有多种决策树方法，如ID3，C4．5，PUBLIC，
数据挖掘决策树算法概述
决策树是分类应用中采用最广泛的模型之一。与神经网络和贝叶斯方法相比，决策树无须花费大量的时间和进行上千次的迭代来训练模型，适用于大规模数据集，除了训练数据中的信息外不再需要其他额外信息，表现了很好的分类精确度。其核心问题是测试属性选择的策略，以及对决策树进行剪枝。连续属性离散化和对高维大规模数据降维，也是扩展决策树算法应用范围的关键技术。本文以决策树为研究对象，主要研究内容有：首先介绍了数据挖掘的历史、现状、理论和过程，然后详细介绍了三种决策树算法，包括其概念、形式模型和优略性，并通过实例对其进行了分析研究 目录 一、引言 (1) 二、数据挖掘 (2) (一)概念 (2) (二)数据挖掘的起源 (2) (三)数据挖掘的对象 (3) (四)数据挖掘的任务 (3) (五)数据挖掘的过程 (3) (六)数据挖掘的常用方法 (3) (七)数据挖掘的应用 (5) 三、决策树算法介绍 (5) (一)归纳学习 (5) (二)分类算法概述 (5) (三)决策树学习算法 (6) 1、决策树描述 (7) 2、决策树的类型 (8) 3、递归方式 (8) 4、决策树的构造算法 (8) 5、决策树的简化方法 (9) 6、决策树算法的讨论 (10) 四、ID3、C4.5和CART算法介绍 (10) (一)ID3学习算法 (11) 1、基本原理 (11) 2、ID3算法的形式化模型 (13) （二）C4.5算法 (14) （三）CART算法 (17) 1、CART算法理论 (17) 2、CART树的分支过程 (17) （四）算法比较 (19) 五、结论 (24) 参考文献...................................................................................... 错误！未定义书签。 致谢.............................................................................................. 错误！未定义书签。
决策树算法的原理与应用
决策树算法的原理与应用 摘要：在机器学习与大数据飞速发展的21世纪，各种不同的算法成为了推动发 展的基石.而作为十大经典算法之一的决策树算法是机器学习中十分重要的一种算法。本文对决策树算法的原理，发展历程以及在现实生活中的基本应用进行介绍，并突出说明了决策树算法所涉及的几种核心技术和几种具有代表性的算法模式。 关键词：机器学习算法决策树 1.决策树算法介绍 1.1算法原理简介 决策树模型是一种用于对数据集进行分类的树形结构。决策树类似于数据结 构中的树型结构，主要是有节点和连接节点的边两种结构组成。节点又分为内部 节点和叶节点。内部节点表示一个特征或属性, 叶节点表示一个类. 决策树(Decision Tree),又称为判定树, 是一种以树结构(包括二叉树和多叉树)形式表达的 预测分析模型，决策树算法被评为十大经典机器学习算法之一[1]。 1.2 发展历程 决策树方法产生于上世纪中旬，到了1975年由J Ross Quinlan提出了ID3算法，作为第一种分类算法模型，在很多数据集上有不错的表现。随着ID3算法的 不断发展，1993年J Ross Quinlan提出C4.5算法，算法对于缺失值补充、树型结 构剪枝等方面作了较大改进，使得算法能够更好的处理分类和回归问题。决策树 算法的发展同时也离不开信息论研究的深入，香农提出的信息熵概念，为ID3算 法的核心，信息增益奠定了基础。1984年，Breiman提出了分类回归树算法，使 用Gini系数代替了信息熵，并且利用数据来对树模型不断进行优化[2]。 2．决策树算法的核心 2.1数据增益 香农在信息论方面的研究，提出了以信息熵来表示事情的不确定性。在数据 均匀分布的情况下，熵越大代表事物的越不确定。在ID3算法中，使用信息熵作 为判断依据，在建树的过程中，选定某个特征对数据集进行分类后，数据集分类 前后信息熵的变化就叫作信息增益，如果使用多个特征对数据集分别进行分类时，信息增益可以衡量特征是否有利于算法对数据集进行分类，从而选择最优的分类 方式建树。 如果一个随机变量X的可以取值为Xi（i=1…n），那么对于变量X来说，它 的熵就是 在得到基尼指数增益之后，选择基尼指数增益最大的特征来作为当前步骤的 分类依据，在之后的分类中重复迭代使用这一方法来实现模型的构造。 3. 决策树算法的优缺点 3.1决策树算法的优点[3] （1）计算速度快，算法简单，分类依据清晰 （2）在处理数据时，有很高的准确度，同时分类结果清晰，步骤明朗。 （3）可以处理连续和种类字段 （4）适合高维数据 3.2决策树算法的缺点 （1）决策树算法可以帮助使用者创建复杂的树，但是在训练的过程中，如
企业CRM系统中决策树算法的应用
企业CRM系统中决策树算法的应用 河北金融学院郭佳许明 保定市科技局《基于数据挖掘的客户关系管理系统应用研究》09ZG009 摘要：客户资源决定企业的核心竞争力，更多的关心自己的销售群体，并与之建立良好的、长期的客户关系，提升客户价值，对全面提升企业竞争能力和盈利能力具有重要作用。本文以某企业销售业绩为对象，利用决策树分类算法，得到支持决策，从而挖掘出理想客户。 关键字：客户关系管理；数据挖掘；分类算法 决策树分类是一种从无规则、无序的训练样本集合中推理出决策树表示形式的分类规则的方法。该方法采用自顶向下的比较方式，在决策树的内部结点进行属性值的比较，然后根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。 本文主要研究决策树分类算法中ID3算法在企业CRM系统中的应用情况。 1.ID3算法原理 ID3算法是一种自顶向下的决策树生成算法，是一种根据熵减理论选择最优的描述属性的方法。该算法从树的根节点处的训练样本开始，选择一个属性来区分样本。对属性的每一个值产生一个分支。分支属性的样本子集被移到新生成的子节点上。这个算法递归地应用于每个子节点，直到一个节点上的所有样本都分区到某个类中。 2.用于分类的训练数据源组 数据挖掘的成功在很大程度上取决于数据的数量和质量。我们应从大量的企业客户数据中找到与分析问题有关的，具有代表性的样本数据子集。然后，进行数据预处理、分析，按问题要求对数据进行组合或增删生成新的变量，从而对问题状态进行有效描述。 在本文研究的企业数据中，是将客户的年龄概化为“小于等于30”、“30到50之间”和“大于50”三个年龄段，分别代表青年、中年和老年客户，将产品价格分为高、中、低三档等，详见表1，将企业CRM系统数据库中销售及客户信息汇总为4个属性2个类别。4个属性是客户年龄段、文化程度、销售地区、产品档次，类别是销售业绩，分为好和差两类。
完整word版,决策树算法总结
决策树研发二部
目录 1. 算法介绍 (1) 1.1.分支节点选取 (1) 1.2.构建树 (3) 1.3.剪枝 (10) 2. sk-learn中的使用 (12) 3. sk-learn中源码分析 (13)
1.算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1.分支节点选取 2.构建树 3.剪枝 1.1.分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 基尼系数：同上，也可以作为信息混乱程度的衡量指标。
有了量化指标后，就可以衡量使用某个分支条件前后，信息混乱程度的收敛效果了。使用分支前的混乱程度，减去分支后的混乱程度，结果越大，表示效果越好。 #计算熵值 def entropy(dataSet): tNum = len(dataSet) print(tNum) #用来保存标签对应的个数的，比如,男：6，女：5 labels = {} for node in dataSet: curL = node[-1] #获取标签 if curL not in labels.keys(): labels[curL] = 0 #如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 #将标签记录个数加1 #此时labels中保存了所有标签和对应的个数 res = 0 #计算公式为-p*logp，p为标签出现概率 for node in labels: p = float(labels[node]) / tNum res -= p * log(p, 2) return res #计算基尼系数 def gini(dataSet): tNum = len(dataSet) print(tNum) # 用来保存标签对应的个数的，比如,男：6，女：5 labels = {} for node in dataSet: curL = node[-1] # 获取标签 if curL not in labels.keys(): labels[curL] = 0 # 如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 # 将标签记录个数加1 # 此时labels中保存了所有标签和对应的个数 res = 1
决策树分类算法
决策树分类算法 决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。 1．决策树的组成 决策树的基本组成部分有：决策节点、分支和叶，树中每个内部节点表示一个属性上的测试，每个叶节点代表一个类。图1就是一棵典型的决策树。 图1 决策树 决策树的每个节点的子节点的个数与决策树所使用的算法有关。例如，CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。 下面介绍一个具体的构造决策树的过程，该方法
是以信息论原理为基础，利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的一个节点，然后再根据字段的不同取值建立树的分支，在每个分支中重复建立树的下层节点和分支。 ID3算法的特点就是在对当前例子集中对象进行分类时，利用求最大熵的方法，找出例子集中信息量（熵）最大的对象属性，用该属性实现对节点的划分，从而构成一棵判定树。 首先，假设训练集C 中含有P 类对象的数量为p ，N 类对象的数量为n ，则利用判定树分类训练集中的对象后，任何对象属于类P 的概率为p/(p+n)，属于类N 的概率为n/(p+n)。 当用判定树进行分类时，作为消息源“P ”或“N ”有关的判定树，产生这些消息所需的期望信息为： n p n log n p n n p p log n p p )n ,p (I 22++-++- = 如果判定树根的属性A 具有m 个值｛A 1, A 2, …, A m ｝，它将训练集C 划分成｛C 1, C 2, …, C m ｝，其中A i 包括C 中属性A 的值为A i 的那些对象。设C i 包括p i 个类P 对象和n i 个类N 对象，子树C i 所需的期望信息是I(p i , n i )。以属性A 作为树根所要求的期望信息可以通过加权平均得到
决策树算法总结
决策树决策树研发二部
目录 1. 算法介绍 (1) 1.1. 分支节点选取 (1) 1.2. 构建树 (3) 1.3. 剪枝 (10) 2. sk-learn 中的使用 (12) 3. sk-learn中源码分析 (13)
1. 算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作 为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对 ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1. 分支节点选取 2. 构建树 3. 剪枝 1.1. 分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 Entropy = -V p ” 基尼系数：同上，也可以作为信息混乱程度的衡量指标。 Gini = 1 - p： l-L
数据挖掘-决策树
数据挖掘论文——决策树 1.什么是决策树 1.决策树(Decision Tree）是在已知各种情况发生概率的基础上，通 过构成决策树来求取净现值的期望值大于等于零的概率，评价项目 风险，判断其可行性的决策分析方法，是直观运用概率分析的一种 图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策 树。 2.决策树图示 1. 3.实例描述 1.女儿：多大年纪了？ 母亲：26。 女儿：长的帅不帅？ 母亲：挺帅的。 女儿：收入高不？ 母亲：不算很高，中等情况。 女儿：是公务员不？ 母亲：是，在税务局上班呢。 女儿：那好，我去见见。 2.这个女孩的决策过程就是典型的分类树决策。相当 于通过年龄、长相、收入和是否公务员对将男人分 为两个类别：见和不见。假设这个女孩对男人的要 求是：30岁以下、长相中等以上并且是高收入者或 中等以上收入的公务员，那么这个可以用下图表示 女孩的决策逻辑：
2. 4.决策树的组成 1.□——决策点，是对几种可能方案的选择，即最后选择的最佳方案。 如果决策属于多级决策，则决策树的中间可以有多个决策点，以决 策树根部的决策点为最终决策方案。[1] 2.○——状态节点，代表备选方案的经济效果（期望值），通过各状 态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方 案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出 现的自然状态数目每个分枝上要注明该状态出现的概率。[1] 1.——结果节点，将每个方案在各种自然状态下取得的损益值 标注于结果节点的右端 5.决策树的构建 1.不同于贝叶斯算法，决策树的构造过程不依赖领域知识，它使用属 性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策 树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结 构。 2.构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点 处按照某一特征属性的不同划分构造不同的分支，其目标是让各个 分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集 中待分类项属于同一类别。分裂属性分为三种不同的情况：
基于关联规则的决策树算法
基于关联规则的决策树算法 汪海锐1,2，李 伟2 (1. 河海大学计算机与信息学院，江苏 常州 213022；2. 海军蚌埠士官学校，安徽 蚌埠 233012) 摘 要：通过将关联规则与决策树算法相结合，形成一种基于关联规则的决策树算法。该算法对不同时期同一事务的异种数据结构进行处理，得到一种可扩展的多分支分类决策树，使得改进后的决策树算法具有良好的可扩展性。该算法解决了传统分类算法在数据集维度发生变化时分类过程无法持续进行的问题。 关键词关键词：：决策树；关联规则；分类算法；扩展性；组合算法 Decision Tree Algorithm Based on Association Rules W ANG Hai-rui 1,2, LI Wei 2 (1. Institute of Computer & Information, Hohai University, Changzhou 213022, China; 2. Navy Petty Officer Academy, Bengbu 233012, China) 【Abstract 】This paper combines association rules and decision tree algorithm, and proposes a new decision tree classification based on association rule. The decision tree algorithm can handle dissimilar transaction data set record blocks which are same investigations conducted in different times to the same transactions. Through the decision tree algorithm, it can get a multi-crunodes decision tree, which has a good extendable performance. The algorithm solves the problem, which exists in the traditional classification, that is the traditional classification can not classify effectively and sustaine when dimensions of dataset change. 【Key words 】decision tree; association rule; classification algorithm; extendable performance; combining algorithm DOI: 10.3969/j.issn.1000-3428.2011.09.035 计 算 机 工 程 Computer Engineering 第37卷 第9期 V ol.37 No.9 2011年5月 May 2011 ·软件技术与数据库软件技术与数据库·· 文章编号文章编号：：1000—3428(2011)09—0104—03 文献标识码文献标识码：：A 中图分类号中图分类号：：TP311.12 1 概述 在数据挖掘的诸多分支中，分类具有极大的实际意义， 渐渐成为数据挖掘在生活中应用的一个重要课题，也使得各种分类算法成为当前的研究热点。在分类算法中，决策树算法[1-2]是一个极为经典的分类算法，有不少学者对其进行研究改进。对于现行的决策树算法，虽然不少学者从多个方面提出了改进，部分算法解决了其缺值处理、并行处理等局限性，但它们同时都具有一个不可回避的缺点：无法适应因采样数据时期不同而导致的属性值不一致问题。同时，传统的决策树算法对于很庞大的数据集而言是很不合适的，由此一些研究人员采用了不同的方法来处理这个问题，如并行的处理方法、多决策树合并算法来提高决策树算法的效率，为此，文献[3]对数据集进行划分，将大数据集划分成小的数据集，再 在小数据集上应用决策树算法，生成小的决策树，再将各个 小的决策树联合起来形成整个决策树。该方法虽然解决了大数据集的分类问题，但降低了分类的准确度。 本文结合关联规则与决策树算法形成一种新的分类算法，既具有决策树的优点，又具有关联规则可并行处理的性质。该算法主要着眼于现实世界的事务数据集是不断变化的，在数据的采集过程中可能会出现某段时间只采集某一事务数据的某些属性值样本，而后期的采集又增加了一些属性，从而形成了对同一事务不同时期的数据采集，构成异种数据集。在这些数据集中可能还会出现新增的类别，也可能会出现某些类别的消亡。在此情况下，按照传统的决策树算法，一旦某一时段的数据集采集完成就进行处理，则如果该时段之后的新增数据集增加了采样属性，那么旧的数据集就有可能会失效或无法使用。如果在新数据集采集完成之前已经对旧数据集进行处理，则造成前期所有的处理工作都无用。为此， 本文考虑利用不同时期的数据集，建立新的决策树算法，使决策树具备良好的伸缩性及可调整性。 2 基于关联规则的决策树算法 2.1 算法流程及简介 本文通过决策树算法与关联规则的结合形成基于关联规则的决策树算法，并对传统决策树算法与关联规则进行结合，形成新的分类算法，该算法同时具有决策树分类准确、易于理解等特点。本算法主要流程如图1所示。