决策树分类算法（精选8篇）
决策树分类算法 篇1
在遥感技术的研究中, 通过遥感图像判读识别各种目标是遥感技术发展的一个重要环节, 无论是专业信息获取、动态变化预测, 还是专题地图制作和遥感数据库的建立都离不开分类。目前, 遥感图像自动分类主要利用统计模式方法, 可分为非监督和监督两类。由于遥感图像往往存在异物同谱和同物异谱的现象, 用传统的统计模式方法分类的效果不甚理想, 因而人们不断研究新的分类方法。例如模拟人脑思维方式提出的人工神经网络分类;针对地物特征和模糊性提出的模糊聚类分类;模式识别与人工智能技术相结合的专家系统分类;计算混合像元内各典型地物所占面积比例的混合像元分解法;按照一定的知识规则, 采用分层思想的树分类等技术。
一、决策树算法的图像分类研究
1. 常用的决策树算法简介
决策树是一个类似流程图的树型结构, 其中树的每个内部节点代表对一个属性的测试, 其分支代表测试的每个结果, 而树的每个叶子节点代表一个类别, 树的最高层节点就是根节点, 是整个决策树的开始。这类算法无须相关领域知识, 且相对于基于模糊理论的分类方法, 具有更高的分类准确率和更快的处理速度。在很多领域特别是数据挖掘中, 决策树是一种经常要用到的技术, 它可以用于分析数据, 也可以用来作预测, 常用的算法有ID3, CART, C4.5等。
(1) ID3算法是最有影响和最早的决策树算法之一, 其建立在推理系统和概念学习系统的基础上, 但它是非递增学习算法。每当一个或数个新例子进来, 就必须重新执行一次该算法, 把新来的例子和以前旧的全部例子集合变成决策树, 因此效率非常低。而且它是基于单变量的, 难以表达复杂概念, 抗噪性差。
(2) C4.5是ID3的改进版本。它主要在以下几个方面对ID3作了改进:缺省值的预测属性仍可用, 提出了修剪思想, 可以进行规则推导。
(3) CART (ClassificationandRegressio nTree, 分类回归树) 是一种数据勘测和预测算法。它用一种非常简单的方法来选择问题, 即将每个问题均试一次, 然后挑出最好的一个, 用它把数据分成更有序的两个分割, 再对新的分割分别提出所有可能的问题。因此该算法得到的决策树每个节点有两个分支, 即二叉树。
2. 改进决策树生成算法
为了更好地将决策树算法应用于遥感图像分类中, 本文在CART算法的基础上作了以下改进。
(1) 常用的决策树算法均由用户提供训练样本集, 计算机执行算法生成决策树, 整个过程由计算机自动完成, 不需要任何人工干预。由于遥感图像训练集的属性取值太多, 而有些取值是用不到的, 需要把这些用不到的取值过滤掉, 否则会影响整颗树的质量。因此本文在决策树的生成过程中引入人机交互技术, 将用户的先验知识用于决策树的生成过程中, 使得生成的决策树更加合理可信。基于人机交互的决策树方法由用户与计算机相互交互, 共同完成, 故要求计算机提供可视化环境和工具, 友好的界面方便用户输入先验知识。
(2) 建立一棵树首先需要选择一个属性作为根节点, 然后将该属性的每一个可能值作为一个分支;再在每个分支所剩余的属性中找出一个属性作为该分支的下一个节点, 如此循环到所有属性均被选用为止。常用的决策树算法均采用信息熵作为选择标准。由于遥感图像中的噪音比较多, 而基于信息熵属性选择标准往往抗干扰能力不强且以对数计算为累加计算的计算量较大, 故本文采用了一种新型的属性选择标准:属性重要性来提高属性选择的效率。该方法是用训练值的变化而引起输出变化的累加值作为衡量属性重要性的标准, 即对于某个属性, 如果训练值的变化而引起的输出变化越大, 说明该属性就越重要。可用式 (1) 表示为C (K) =∑x (i, k) -x (j, k) ×signy (i) -y (j) (i≠j) (1) 式中:C (K) 表示第k个属性的输入/输出关联值;x (i, k) , x (j, k) 表示第i, j个样本的第k个条件属性值;y (i) , y (j) 表示第i, j个样本的决策属性值;sign (x) 表示符号函数。
3. 一种自定义的数据结构
数据结构的设计在程序设计中很关键, 一个好的数据结构可以让算法更加精练, 大大提高开发效率。本文采用的算法是在CART算法的基础上改进过来的, 因此生成的也是一棵二叉树。但由于在生成算法中要频繁地查找和调整决策树 (添加或者删除子树) , 传统的二叉树结构在速度上不能满足算法的需求, 故笔者在设计系统时创新了一种类二叉树的结构。在树的每一层都设置了一个头节点, 且树的每个节点只有指向父节点和左右兄弟节点的指针。
4. 系统实现
图3为系统架构图。其中D是训练集合, A为分类属性集合。另有测试数据集合T用来评估生成决策树的误差ε。整个过程分为两个部分进行: (1) 决策树构造, 也称学习过程, 主要工作是输入训练集, 采用改进的决策树生成算法生成决策树, 并作好分类前的预备工作, 即提取分类规则; (2) 决策树预测, 也称分类过程, 主要工作是应用分类规则进行分类, 并根据测试集, 计算出分类误差, 误差较大的对决策树作裁剪算法。误差较小的就输出其分类结果, 分类结果有两种: (1) 将分类结果写入新的遥感图像文件 (如MIG文件) 中; (2) 可视化的树结构, 在树的叶子节点保存着每一类的属性。
二、结语
通过本文研究发现:决策树算法对于输入数据的空间特征和分类标志具有更好的弹性和坚韧性, 它用于遥感数据分类的优势主要在于对数字图像数据特征空间的分割上, 其分类结构简单明了, 尤其是二叉树结构的单一决策树结构十分容易解释。因此, 当遥感图像数据特征的空间分布很复杂, 或者源数据各维具有不同的统计分布和尺度时, 基于决策树算法的分类方法能够获得较为理想的分类结果。
参考文献
[1]李宁, 等.决策树算法及其常见问题的解决[J].计算机与数字工程, 2010, 3 (33) :60264.
[2]孙雪莲.数据挖掘中分类算法研究[D].吉林大学硕士学位论文, 2010.
数据挖掘决策树算法的改进与实现 篇2
关键词:数掘挖掘;决策树算法;改进;实现
中图分类号:TP301.6 文献标识码:A文章编号:1007-9599 (2010) 04-0000-02
Data Mining Decision Tree Improvement&Implementation
Xia Yan,Zhou Xiaohong,Wang Dong
(Changchun Technology College,Changchun130033,China)
Abstract:The author studied on existing Data Mining decision tree classification method based on the practical application,and applied to the system,achieved a decision support module.
Keywords:Data Mining;Decision tree algorithm;Improve;Achieve
随着数据库技术的不断发展及数据库管理系统的广泛应用,数据库中存储的数据量急剧增大,在大量的数据背后隐藏着许多重要的信息,如果能把这些信息从数据库中抽取出来,将会产生重要的作用。
因此,数据挖掘涉及的学科领域逐渐扩大,数据挖掘的方法也在不断地改进和提高。分类在数据挖掘中是一项非常重要的任务,分类算法可以分为决策树分类算法、遗传算法、神经网络方法、K-最近邻分类算法等。这里,以疾病防控与儿童免疫管理系统中决策支持子系统的开发过程为例,对决策树分类算法的改进及在实际中的应用进行阐述。
一、数据选取和数据预处理
在本系统中,以预防接种中遇到异常反应后记录的“异常反应调查表”中的数据为例进行说明。具体实现过程详细说明:首先输入训练集,由于在真实的SQL Server数据库当中,为了降低存储要求和减少存储时间,并非真正存储每个数据项的属性值,而是用存储数字来对应相应的意义,如在数据库的数据表中,“性别”字段中“1”代表“男”、“2”代表“女”,反应到程序页面时再映射回原来的值,为了说理清晰又限于篇幅,这里只将所有数据集中有代表性的十几组数据作为分类模型创建的输入训练集。
二、生成决策树
对训练集的每一个属性,计算其信息增益。以“月龄”属性为例,每个结点中的正反例的个数分别为[2,3]、[3,2]、[4,0],分别计算如下:
info[2,3]= =0.971;
info[3,2]= =0.971;info[4,0]=0;
计算信息熵:E(月龄)= =0.693;
计算该属性的信息增益量,选取信息增益最大的属性为节点,按该属性的值划分数据集合:Gain(月龄)=Info(9,5)-E(月龄)=0.940-0.693=0.247;
同理,对“注射反应”属性、“出生状态”属性、“常住地”属性都可计算每个结点的正反例的个数(由于篇幅有限,不作计算)。通过对各属性信息增益的计算结果,选择“月龄”属性作为根节点,然后划分“月龄<=2”的所有可能性。计算当“月龄<=2”时,“注射反应”、“出生状态”、“常住地”的信息增益值:
Gain(注射反应)= Info(2,3)-E(注射反应)=0.971-0.4=0.571;
Gain(出生状态)= Info(2,3)-E(出生状态)=0.971-0=0.971;
Gain(常住地)= Info(2,3)-E(常住地)=0.972-0.951=0.020;
同理考虑“月龄>5”的情况,由于“月龄>5”时,各个节点都是纯节点,所以不再划分。
三、产生决策规则
遍历决策树,输出叶结点类属性值,用IF—THEN形式表达为
IF(月龄 2…5 AND 注射反应=无)THEN (类别=是)
IF(月龄 2…5 AND 注射反应=轻)THEN (类别=是)
IF(月龄 2…5 AND 注射反应=重AND 出生状态=正常产)THEN(类别=是)
IF(月龄 2…5 AND 注射反应=重AND 出生状态=非正常产 AND 常住地=城市)THEN (类别=否)
IF(月龄 2…5 AND 注射反应=重AND 出生状态=非正常产AND 常住地=农村)THEN(类别=是)
……
依此类推,共可产生十三条规则。
四、决策支持子系统的分析
用上述基于决策树的分类算法所得到的模型生成的规则来预测测试集中的未知数据属于哪一类,并通过该模型的测试结果与实际情况相吻合的准确率来判断该决策树是否有效。
首先,用整个数据集中2/3的数据作为训练集按照基于决策树的分类算法来建立模型,生成一棵决策树。
然后,用余下的1/3的数据作为测试集,通过创建的模型进行预测,并将预测结果和实际值进行比较。如果准确率达到或超过事先确定的阈值,则可以认定该模型对于数据分类是有效的,能够在实际中应用;反之,则认定该模型的分类效果不好,需要按以上步骤来重新判断,直到分类准确率达到预定的阈值为止。
在本系统中,经过测试预测准确率已达到87%,在可以接受的范围内,所以算法是有效、可行的。
参考文献:
[1]陈文伟,黄金才.数据仓库与数据挖掘.人民邮电出版社,2004
[2]王万森.人工智能原理及应用.电子工业出版社,2000
[3]范明,孟小峰.数据挖掘——概念与技术.机械工业出版社,2001
作者简介:
决策树分类算法-ID3的改进 篇3
近年来, 数据分类技术已被广泛、有效地应用于科学实验、案件侦破等领域, 引起了工业界和学术界的普遍关注。其中基于决策树的分类模型方法由于结构简单、效率高等优点被人们广泛使用。决策树方法起源于概念学习系统, 国际上最早最有影响的决策树方法是Quinlan提出的ID3算法, 在该算法中, 引入了熵的概念, 利用分割前后的熵来计算信息增益。在树的生长过程中, 在每次对记录集分割时均选择信息增益最大的属性进行分叉, 直到一个节点的记录的类别相同或者结点的记录数目小于给定的值没有属性供选择使用为止, 最后生成一棵树。
2 ID3算法
设训练实例集为X, 将其分为n类, 记为C={X1, X2……Xn}, 设第i类训练实例的个数是XÁ实例集X中的训练实例个数为。若记一个实例属于第i类的概率为P (Xi) , 则有:
此时决策树对划分C的不确定程度为H (X, C) , 可简记为H (X) ,
选择测试属性A进行测试, 设A具有性质a1, a2…, an, 在A=ai的情况下, 第i类的实例个数为|Xij|, A=aj的实例个数为|Xj|, 则有:
设Yj为A=aj时的实例集, 此时决策树对分类的不确定程度就是训练实例集对属性A的条件熵,
当选择测试属性A后, 分出每个A=aj时节点Xj对分类信息的信息熵为
属性A对于分类提供的信息量, 即属性的信息增益A为I (A)
显然, 式 (5) 的值越小则式 (6) 的值越大, 说明选择测试属性对于分类提供的信息越大, 选择之后对分类的不确定程度越小, ID3算法即采取I (A) 作为测试属性的选取标准, 分割训练实例集最终生成一棵决策树。
3 算法改进
传统的ID3算法偏向于选择取值较多但实际中并不总是最优的属性作为测试属性, 针对它的这一缺点, 本文引入用户兴趣度:给定0≤s≤1, s称为用户对不确定知识的兴趣度, 通常指关于某一事务的先验知识, 具体到决策树学习中则是指在决策树训练过程中, 除了用于生成和修改决策树的实例集之外, 还包括所有影响决策树规则生成和选择的因素。
改进的ID3算法是针对规则生成方法即属性选择标准算法进行了改进。通过对式 (5) 中加权和增加用户兴趣度, 加强了属性的标注, 降低非重要属性的标注, 最终使决策树减少了对取值较多的属性的依赖性。
利用用户兴趣度把 (5) 修改为:
相应式 (6) 变为:
改进ID3算法就是把式 (7) 和式 (8) 作为测试属性的选择标准来构造决策树。
4 算法举例
表1给出了影响夏天天气舒适度的几个相关指标的数据集合, 下面以该样本数据集为训练集, 分别采用ID3算法及其改进算法构造决策树, 对数据进行分类。
用ID3算法对样本训练集进行分类, 可得决策树, 如图1所示。
根据图1可以得到分类规则, 见表2。
由表2可以看到, 穿衣指数能在一定程度上反映天气的舒适程度, 但并不能成为决定天气舒适与否的客观条件。下面, 用改进算法对表1的样本数据集重新生成决策树, 通过测试指定穿衣指数属性的用户兴趣度s=0.3, 其它属性的用户兴趣度为0。
由表1可知, 初始时刻正例类实例个数为9, 反例类实例个数为11, 所以开始时熵值为:
选择穿衣指数作为测试属性, 该属性的信息熵为
类似可得H (X|温度) =0.9661;H (X|湿度) =0.9328;F (X|风力) =0.9880。比较可知:H (X|湿度)
由图2可得到新的分类规则, 用表3表示。
比较以上两种决策树算法的规则提取, 可以发现改进算法与ID3算法所生成的决策树有很大区别, 得到的分类规则也有较大不同。改进算法降低了穿衣指数对天气舒适影响的重要性, 相应地提高了湿度、温度、风力属性在分类中的重要性, 这显然与实际情况较相符, 达到了预期目的。
结束语
ID3是决策树生成算法中最早最经典的算法, 本文具体分析了ID3算法中存在的问题, 并对其进行了改进。从而提高了建立决策树的速度, 通过对实际例子的应用, 实验证明改进后算法是有效的。
参考文献
[1]史忠植.高级人工智能[M].北京:科学出版社, 2006.[1]史忠植.高级人工智能[M].北京:科学出版社, 2006.
[2]朱明.数据挖掘[M].合肥:中国科学技术大学出版社, 2002.[2]朱明.数据挖掘[M].合肥:中国科学技术大学出版社, 2002.
[3]郭景峰, 米浦波, 刘国华.决策树算法的并行性研究[J].计算机工程, 2002, 28 (8) .[3]郭景峰, 米浦波, 刘国华.决策树算法的并行性研究[J].计算机工程, 2002, 28 (8) .
[4]刘小虎, 李生.决策树的优化算法[J].软件学报, 1989, 9 (10) .[4]刘小虎, 李生.决策树的优化算法[J].软件学报, 1989, 9 (10) .
[5]杨明, 张载鸿.决策树学习算法ID3的研究.[J].微机发展, 2002 (5) .[5]杨明, 张载鸿.决策树学习算法ID3的研究.[J].微机发展, 2002 (5) .
决策树分类算法 篇4
分类是数据挖掘中的一个重要的研究课题,目前常用的分类方法有:决策树、贝叶斯分类、神经网络等,其中决策树分类方法以其理论清晰、易于理解,容易转换成分类规则等优点而被广泛地应用和研究。
决策树的基本算法是贪心算法,它采用自顶向下递归的方式来构造决策树,理想情况下,当所有树叶都是纯结点,即每个叶结点的实例都属于同一类时,决策树停止生长。但在实际应用过程中,常常无法达到这种理想结果,因为无法避免训练集中包含具有相同属性集,但属于不同类别的实例的情况。对于这种情况,由于没有剩余的属性可以用来进一步划分样本,所以决策树的这条分支无法继续生长下去产生纯的叶结点。目前针对这一情况,比较常用的处理方式就是使用多数表决方法来确定这种样本的分类,即将决策树中的该结点转换成叶结点并用样本中多数所在的类标记它[1]。多数表决的方式在一定程度上能决定样本所属的类别,但存在着两个问题,一是该方法对样本依赖过大,容易使决策树产生过拟合的现象,从而降低决策树的分类效果。二是如果样本空间中每个类别的实例数相等,不存在多数类别,将无法使用多数表决来判定样本的类别。针对这种状况,提出一种基于信息增益并结合最小距离分类的决策树改进算法。该算法首先利用信息增益进行属性空间的约简,然后针对决策树在构造过程中训练集中包含具有相同属性集,但属于不同类别的样本,利用基于信息增益的加权欧式距离公式计算这类样本的中心点与决策树中所有纯叶结点的样本中心点之间的距离,找到与其中心点距离最近的那个叶结点,并用最近的叶结点的类别来对该叶结点进行标记。
1 信息增益与ID3算法
在信息论中,信息量是指从N个相等可能事件中选出一个事件所需要的信息度量,事件ai的信息量可用-log2p(ai)来度量,其中p(ai)表示事件ai发生的概率[2]。熵的定义为[1]:,其中P1,P21…,Ps是给定概率,且,表达的是平均信息度量。
信息增益定义为
式(1)中,H(D)是原始数据集的熵,P(Di)子集Di所占整个数据集的比例,(Di)H)(Di)是分裂后所有子集的熵的加权和。式(1)表达的是样本分类前后熵值的变化差值,这一差值表明了属性对分类所提供的信息量大小。因此,可以用信息增益来量化属性与给定的类或概念的相关性,信息增益越大表明该属性与分类任务的相关性越大。
ID3算法是经典的决策树算法,其核心是以信息增益为衡量标准,它通过计算每一个属性的信息增益,并选取具有最高信息增益的属性作为分裂属性来构建决策树,这种方法将产生一棵简单的,但不必是最简单的决策树。
ID3算法思想如下:[1]
1)树以训练集中信息增益最大的属性A开始;
2)如果样本都属于同一类,则该节点成为树叶,并用该类标记;
3)否则,对属性A的每个有效值,创建一个分枝,并据此划分样本;
4)使用相同的方式,递归地产生每个划分样本上的决策树。
递归划分步骤仅当下列条件之一成立时停止:
a)给定节点的所有样本属于同一类;
b)没有剩余属性可以用来进一步划分样本,此时将该节点转换成树叶,并用多数表决法,用样本集中的多数所在的类标记它;
c)对有属性而训练集中无样本的分枝也采用多数表决法,来决定其类别。
2 基于信息增益的最小距离分类器
最小距离分类器是一种基于向量空间模型的简单而有效的分类器,其基本思想[3]是根据训练集按照算术平均生成一个代表该类的中心向量Uk(k=1,2,…,m;m是类的个数),对于每一个待分类的数据元组X,计算其与Uk之间的距离d(Uk,X),最后判定X属于与之距离最近的类。这里X=[x1,x2,…,xn,c],Uk=[μk1,μk2,…,μkn,c],c表示类别,c∈{c1,c2,…,cm}。
在实际应用中,由于各属性在分类过程中所起的作用大小不同,因此在计算最小距离时,一般采用加权的距离公式。
在式(2)中,权值wi的大小说明该属性对分类的影响的大小。
采用基于加权距离公式的最小距离分类器进行分类时,合理地对权值wi大小进行设置是至关重要的。为此,本文提出一种新型的基于信息增益的改进型最小距离分类器。该分类器基于式(2)中的权值wi用属性的信息增益值来设置。具体做法是:
1)计算属性空间中各属性的信息增益得到属性信息增益集AttrilnforGainSet;
2)将AttrilnfoGainSet中信息增益值归一化处理到[0,1]区间,并将处理的结果作为权值赋值给式(2)中相应的属性Xi的权值wi;
3)对参与分类的各属性的取值进行规范化处理,将属性值规范化在[0,1];
4)调用式(2)进行分类。
3 基于信息增益和最小距离分类的决策树改进算法
ID3算法简单、易实现,因此被广泛使用,但对于训练集中存在相同属性集,但属于不同类别的实例的情况仅简单地采用多数表决法来决定其类别,降低了决策树分类的精度。此外,ID3算法产生的决策树其结构往往过于庞大、复杂,后期的剪枝工作量比较大,这就影响了算法效率。基于信息增益和最小距离分类的决策树改进算法,在ID3算法的基础上,通过结合基于信息增益的属性约简和最小距离分类方法来改进ID3算法的性能,其中基于信息增益的属性约简[4]是根据属性增益的大小以及属性间的相关系数的大小来判断属性对分类的贡献大小,以及属性间的关联程度,从而删除对分类不相关、弱相关的属性以及冗余属性达到约简属性空间的效果。
3.1 算法描述
1)对属性空间作基于信息增益的属性约简,得到最优约简的属性集OptiAttriSet和对应的信息增益集OptiAttriGainSet。
2)用信息增益作为启发式信息来构造ID3决策树,但在构造过程中对于具有相同属性集,但属于不同类别的实例,暂时用null标识它的类别。
3)对决策树中所有类别为null的叶结点,调用基于信息增益的最小距离分类器对它们进行重新分类。
4)计算决策树所有叶结点Nk所在的子样本空间的中心结点Uk。具体操作如下:若属性i是数值类属性,中心结点Uk的属性值μki的值为样本空间中所有样本i属性的算术平均值,若属性i是标称型或字符串型属性,中心结点Uk的属性值μki取该类的所有数据元组中属性i的最频繁值[5]。
5)将决策树中每一个类别为null的叶结点Nm的中心结点Umi作为待分类样本,用基于信息增益的最小距离分类器来计算Umi与其他类别为非null的叶结点Nn的中心结点Uni之间的距离d(Umi,ni),i∈(i,…,k),并将叶结点Nm的类重新标识U为与其中心点Um距离最近的Uni所属的叶结点Nn的类标号C。
3.2 改进ID3算法实例
实例主要是针对训练集中存在相同属性集,但属于不同类别的实例的情况,说明改进后的ID3算法的分类效果优于传统ID3算法的分类效果。实例是在一个简单的气象数据集(表1所示)进行的,该数据集描述了气象因素对是否打网球这一行动的影响,表1中的weather、temperature、humidity、windy、tennis是进行了属性约简后保留的属性,其中tennis是类别属性,yes表示打网球,no表示不打网球。ID属性在这里仅用来表达记录号,不参与分类。针对表1中的数据用传统ID3算法产生的决策树如图1所示。
从图1中可以看出树叶1—6都是纯叶结点,树叶7不是纯叶结点,训练集中实例8,9属于树叶7,而实例8和实例9具有相同属性集,但属于不同类别,所以按照传统的ID3算法应该采用多数表决来决定其分类,但在该子集中不存在多数类,故无法用多数表决的方法来判定树叶7所属的类别。在改进的ID3算法中将采用基于信息增益的最小距离分类来决定树叶7的类别。
1)计算属性的信息增益并将信息增益归一化处理后结果为:InfoGain (climate)=0.56,InfoGain(temperature)=0.11,InfoGain (humidity)=0.31,InfoGain (wind)=0.02;
2)计算,树叶7与其他树叶之间的距离
a)首先计算树叶7与树叶4,5,6之间的距离,对于字符串型属性,中心结点的属性值取该类的所有数据元组中属性的最频繁值[6],因此:
树叶7的中心结点K的各属性值为:weather=rain,temperature=cool,humidity=normal,windy=yes,tennis=null;
树叶6的中心结点N6为(weather=rain,temperature=hot,humidity=high,windy=no,tennis=no);
树叶5的中心结点N5为(weather=rain,temperature=warm,humidity=high,windy=no,tennis=yes)
树叶4的中心结点N4为(weather=rain,temperature=warm,humidity=high,windy=yes,tennis=no)
调用基于信息增益的最小距离公式,计算结点K与N4-N6的距离。计算时对于字符性数据,如果两个属性值相等,则差值为0,如果不等则差值为1。点K与N4-N6的距离为D(K,N6)=0.663,D(K,N5)=0.663,D(K,N4)=0.648。
b)计算树叶7与树叶1,2,3之间的距离
树叶1,2,3的中心点N1,N2,N3的weather属性值分别为:sunny,cloudy,与树叶7的中点K的weather属性值rain不同,所以N1-N3与K的距离应该大于等于(InfoGain (weather)×1×1) 1/2=(0.56×1×1)1/2=0.748。
通过比较可知与K最近的应该是N4,因此树叶7的类别应该与树叶4一样为no。
3.3 基于信息增益和最小距离分类的决策树改进算法的性能测试
本实验在WEKA平台[7]上针对UCI数据库中的mushroom数据集进行,该数据集包含23个属性,8124条记录,类别数为2。实验时需要修改实例,使数据集中具有相同的属性取值,但属于不同的类别的记录。实验主要用来测试训练集中具有相同的属性取值,但属于不同的类别的记录数量不同的情况下传统ID3决策树和改进型ID3决策树的分类的性能。具体实验信息如表2所示。
从表2可以看出从分类效果上来看,改进型ID3决策树的分类正确率优于传统的ID3决策树分类,且随着数据集中具有相同的属性取值,但属于不同的类别记录数的增多,这种优势更明显。从算法的执行速度上来看,传统的ID3决策树的速度略高于基于信息增益和最小距离分类的决策树。这主要是因为与传统的ID3算法相比,改进型ID3决策树要多两个步骤:一是在构造决策树前对属性空间进行了基于信息增益的属性约简需要花费一些时间,二是对属于不同类别的实例要调用基于信息增益的最小距离分类器来决策其类别比用多数表决决策法判断分类花费的时间也要多一点,但改进后的ID3算法是在约简后的属性空间中构造决策树的,因此构造速度会更快,产生的决策树也会更小、更简单,同时也减少了后期为了避免过拟合而对决策树进行剪枝的时间开销,所以改进型ID3决策树与传统ID3相比速度相差不大。
4 总结
决策树是一种基于知识表示的树,它具有执行效率高,生成的规则容易理解等优点而被广泛应用,针对决策树的代表ID3算法进行改进。首先应用基于信息增益的属性约简的方法对属性空间进行约简,以加快决策树的生长、降低剪枝的工作量,并得到结构更好的决策树,接着对于训练集中具有相同的属性取值,但属于不同的类别的记录情况,不再采用多数表决法决定类别,而是采用最小距离分类方法来确定其类别,实验表明基于信息增益和最小距离分类的决策树提高了分类的准确率。
参考文献
[1] Han jiawei,Kamber M著.范明,孟小峰,等译.数据挖掘概念与技术.北京:机械工业出版社,2001:188-189
[2]魏存章,豆增发.一种基于信息增益的K-NN改进算法.计算机工程与应用,2007;43(19):188-191
[3] Jainak,Robert Pwduin,MAO J.statistical pattern recognition;a review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000;22(1):4—37
[4] Duan Wei,Lu Xiang-yang.Weighted Naive Bayesian classifier model based on information gain.Changsha,China;Intelligent System Design and Engineering Application,2010;(2);819—822
[5]任靖,李春平.最小距离分类器的改进算法——加权最小距离??分类器.计算机应用,2007;25(5):992-994
[6]邱潇钰,张化祥.基于核的最小距离分类法的参数选择方法.计算机工程,2008;34(5):188-190
[7]陈慧萍,林莉莉,王建东,等.WEKA数据挖掘平台及其二次开发.计算机工程与应用,2008;44(19):76-79
决策树分类算法 篇5
1 决策树算法概述
数据挖掘就是从模糊地、不完全地、大量地、有噪声的、随机的以及原始数据中提取隐藏在那里面的潜在的、我们预先不知道的有用信息知识的挖掘过程。作为数据挖掘分类法中一个分支的决策树算法起源于概念学习系统。决策树算法就是使用树的结构对数据进行分类, 每个条件下的记录集就好比一棵树的叶节点, 人们根据字段数据取值的不同, 可以对决策树进行分支, 在决策树各个分支的子集中再重复建立分支和决策树各下层节点, 这样一棵决策树就形成了。
决策树算法最早是由Hunt等人提出来的, 目前最有影响的是ID3和C4.5[1]。ID3主要是选择运用信息最大属性的增益值来进行样本训练划分的, 其目的是能够使商在分裂系统时达到最小, 以此来提高决策树算法的精确度和运算速度。当然ID3算法也有其自身的缺陷, 例如可以运用信息增益作为分裂属性的标准, 但是这种行为在取值时会不自然地偏向于取值较多属性, 然而在大部分情况下, 这种属性都不能为我们提供许多有价值的信息。C4.5是在改进ID3的中得到的一种新算法, 这种算法不但能够对连续值的属性进行处理, 而且可以对离散值的属性进行很好的处理, C4.5选择测试的标准主要是采用信息增益比, 这在很大程度上弥补了ID3的一些不足, 除此之外, 我们还可以采用其他的一些决策树算法进行计算, 例如CART、QUEST、OC1、CAL5等。
2 决策树算法中遇到的问题
2.1 取值问题
一个决策树的建立, 必须要根据字段对不同取值的记录来建立对决策树进行分支, 并且在每个决策树的子集分支中反复建立下层的分支与节叶点, 构建决策树的关键在于对不同取值的分支阶段进行选择。选择不同的字段值, 也会使得子集计录的划分值各不相同, 不同的字段值还会对决策树结构的好坏和生长的快慢造成一定影响, 从而影响到信息规则寻找的优劣。因此, 构建一个好的决策树最主要的难点在于对分支取值进行良好的选择。好的分支取值的利用, 不仅能够对决策树的结构产生良好的作用, 还能够使决策树的生长速度起到良好的加快作用, 从而使人们找到一个较好的规则信息[2]。相反, 如果对决策树的分支仅仅只是依据一个比较差的取值来来决定, 不但会影响决策树的生长的速度, 还会导致结构性差和对决策树的分支过细这类不良现象的发生, 因而难以发现那些本就可以得到有用规则的信息。
2.2 数据过分近似问题
在决策树的运算过程中产生数据过分近似的原因主要有两点。 (1) 在寻找测试属性时各个属性在选择自己算法上都有自己的偏好, 因而非常有可能会找到算法的偏好, 可这并不是和种类真正相关的属性。想要在选择决策树时避免选到不相关属性是不容易确定的, 所以要从决策树中把相关的属性删除, 这种技巧也就是决策树的修剪法[3], 修剪法可以分为后修剪方法和前修剪方法。后修剪方法是当决策树生长完成以后进行剪枝, 前修剪方法主要是指在树的生长完成前就先进行剪枝。 (2) 由于物体本身的属性太多, 其中有些和种类不相关, 决策树算法很容易选到和自身种类不相关的属性。
3 决策树算法现状
可以采用决策树的算法共同对处理数据挖掘任务进行处理以得到有价值的模式和规则, 但以前使用的大多数决策树算法都是针对小数据的, 要求必须有常驻内存存在与训练集中, 这就导致了决策树算法在效率、精确度以及可伸缩性等方面受到很大的限制。在实际应用中的数据挖掘中, 我们所面临的大部分都是容量巨大的数据仓库或者数据库等一些数据集, 但是不能完全把这些数据集放入主存中, 在决策树的建构时需要把在缓存和主存中的数据进行导出或者导入, 这样可以极大地降低运算效果。针对以上的这些问题, 许多学者都提出了自己在挖掘数据分类法中利用决策树算法处理大型数据集的一些意见[4]。
3.1 抽样方法
在数据挖掘分类方法的实际运用中时可以利用抽样方法来提高决策树的效率, 当我们对这种数据算法的要求越高时, 往往这种算法也更加有效。在构建一棵决策树时我们可以抽样分析其中的数据集, 抽样分析还可以在产生节点的过程对进行, 利用抽样统计法来对整个数据库中的一个子集进行样本抽取分析就是抽样分析, 再用这个抽取的子集样本建构一个决策树, 继而从中抽取分类规则或者对未知样本进行分类。但是抽样分析法有其自身的缺点, 主要是, 决策通过抽样子集而产生只能获得大致的整个数据集信息, 这就很有可能把数据集中一些非常有价值的数据模式给漏掉。但是, 这种以牺牲精度对为代价从而提高运算效率的做法, 并不可取。
3.2 综合其他算法
模拟自然界在工程进化中的优胜劣汰原则进行计算的模型是遗传算法, 遗传算法是一种全局最优化的算法。在对数据进行求解的过程中, 通过变异、选择以及交叉等操作使不断优化群体, 从而寻求最优解。传统的决策树算法在决策树的构造过程中可能并不一定能够得到最优化的决策树, 将遗传算法和决策树算法二者结合起来可能会的得到一个精确度更高的决策树。根据上面的方法对决策树进行构建可以分为两种:一种方法是对决策树不进行编码, 而对决策树直接进行变异、操作、交叉以及选择[5]。智能的CAIT决策树算法可以把遗传算法、抽样算法以及决策树算法三者相互结合起来, 这能够在一定程度弥补以子集方法为基础的缺陷。另一种方法是将决策树进行编码, 例如CALTROT这种算法, CALTROT算法可以通过遗传算法来建构一个二叉决策树。在这个二叉决策树系统中, 遗传的染色体被当成决策树来看待, 在这个染色体中又包含了若干个二叉决策树的子集树, 每个决策子集树都是由两个分支和一个节点组成。通过对些染色体顺序排列的改变, 一组初始群体就能够我们建构出来, 通过再选择, 加之变异和交叉的共同运用, 从而就可以产生一棵最优秀的决策树。但是每个子集所产生决策树节点的个数和形状都是不同的, 因此, 在有些时候使用固定的长度位串来表示决策树是不合适的。
4 决策树算法发展趋势
除去一些科学的研究之外, 比如SAS、Spss[6]、MS Miner等商用软件中也都或多或少的设计到了也把决策树算法, 并且得到了广泛的应用。虽然数据挖掘中的决策树算法在现代发展中取得了一些成就, 但是在还存在着一定的不足需要我们进一步改善, 笔者认为决策树算法为来的发展有以下几个方面:
4.1 精确度的提高
具有较高的方差也是决策树算法中的一个主要问题, 通常, 一个完全不同系列都可能因为一个很小的数据变化而造成分裂。过程的分层本性是形成这种不稳定的主要因素, 决策树可能会因为顶层分裂中的一个失误而造成传播到下面各个分层的分裂。在建构决策树的过程中可以使用相对稳定的分裂准则进行建构尝试, 我们能够在某些程度较好的缓解这种情况, 但是在决策树是中不可能消除这种固有稳定性的, 因此, 我们需要进一步解决的问题就是要努力提高决策树的精确度。
4.2 处理复杂数据
我们目前所面临的一些数据大多复杂多样化的, 所以, 决策树算法除了能够有效地处理结构和数据外, 还应该对各种数据库、结构化、半结构化等方面进行挖掘和挑战。
5 结束语
数据挖掘的方法有很多种, 其中一个重要方法就是决策树算法, 决策树算法是目前多种算法中使用最多的数据挖掘技术之一, 该文在分析了决策树算法实际中遇到的一些问题和发展现状作了一个简单分析和发展预测。决策树算法在运行的过程中还有一些不足之处, 决策树算法虽然已经有了广泛的应用, 也产生了大量成熟的系统, 但是, 解决一个复杂的数据挖掘问题时决策树还面临着很多的问题。研究表明, 决策树算法还存在这很多缺陷, 其中还有很多问题值得我们去开发和研究。
参考文献
[1]滕明鑫, 高占国, 杨秀清.数据挖掘中决策树算法优化研究[J].重庆通信学院学报, 2011 (15) .
[2]韩慧, 毛锋, 王文渊.数据挖掘中决策树算法的最新进展[J].技术机运用, 2013 (28) .
[3]刘慧巍, 张雷, 翟军昌.数据挖掘中决策树算法的研究及其改造[J].辽宁师专学报2011 (486) .
[4]卢东标.数据挖掘中决策树算法的研究和常见问题的解决[J].算法与语言, 2010 (321) .
[5]唐华松, 姚耀文.数据挖掘中决策树算法的探讨[J].华南理工大学技算机学院报, 2013 (12) .
[6]林巧.数据挖掘中决策树算法的探讨[J].伊犁师范学院学报, 2011 (785) .
决策树分类算法 篇6
随着数据库技术的广泛应用和数据库管理系统的普及, 现在各行业使用的信息系统尤其是国内金融部门使用的大多数业务处理系统都是基于数据库的, 能够实现业务数据的录入、查询、更新、统计等功能, 并将与业务相关的数据存储在数据库中。数据库存储中的这些大量数据往往隐含着重要信息, 如果对其进行深入的分析, 挖掘数据背后隐藏的信息, 发现大量客户数据中潜在的关联和规则, 以此对未来的发展趋势做出预测, 从而在企业的管理和决策中发挥重要作用。数据挖掘就是从大量的数据中提取出隐藏在其中的, 有应用价值的信息和规则的过程。
客户关系管理 (Customer Relationship Management, CRM) 是一种以客户为核心的经营理念, 通过不断完善客户的服务来实现企业利润的增长。即通过客户信息的分析处理, 不断改进客户业务流程, 满足客户需求, 为客户提供所需要的服务等手段来实现客户和企业利润的增加, 提高对客户的营销能力, 从而实现客户和企业的相互的利益满足。客户分类是CRM中一个重要方面, 而决策树方法是分类分析的常用工具。
决策树是数据挖掘技术中常用的分类方法, 将挖掘的结果以树形结构的图形方式体现出来, 具有结构简单, 易于理解, 效率高等优点。决策树分类挖掘技术广泛应用于各行业的客户关系管理系统中, 通过对客户相关信息的分析, 对客户所属的类别进行预测, 从而采取相应的措施和服务策略, 提高服务水平和工作效率, 从而得到较大的收益。
1 决策树C4.5算法
1.1 C4.5算法
决策树在数据挖掘领域因其分类预测的准确率较高、直观易于理解等特点, 广泛应用在各领域。决策树算法比较多, 不同算法创建的决策树的性能也各有所不同, ID3和C4.5算法是决策树方法中最有影响力的算法, 主要进行数据分类划分的处理。C4.5算法是ID3算法的改进和扩充。ID3算法只能对连续型属性数据进行处理, 而C4.5算法既可以处理离散型属性数据, 也能够对连续性属性数据进行处理。
C4.5算法构造决策树时选择分支节点属性的依据是信息增益率。ID3算法中节点属性的选择标准是信息增益的大小, 因为有较多取值的属性具有较大的信息增益的特点, ID3算法节点属性的选择侧重于取值较多的属性[1]。而C4.5算法以信息增益率为属性节点的选择依据, 克服了ID3算法的倾向于选择取值较多的属性的不足。
1.2 C4.5算法的处理过程
C4.5算法的详细步骤如下:
步骤1:若数据集中的有连续型属性, 需要离散化处理。进行离散化数据预处理后, 进行根节点属性的选择。计算数据集中所有属性的信息增益率, 选择其中的最大值的属性作为根节点属性。
1) 计算数据集分类的信息期望I。设S为有n个实例的数据集合, 依据实例所属的类别, 集合S有m种划分{S1, S2, …, Si, …Sm}, 每种划分的实例数目为ni, pi=ni/n是Si类出现的概率。将集合S划分为m个类别的信息熵或信息期望[2]为:
2) 计算非类别属性A的信息期望I (A=aj) , j=1, 2, …, v, 即属性A有v个取值, 将S划分为v个子集{D1, D2, …, Dv}, Dj为A=aj时的子集, Dj的实例数为dj, Dj子集中属于Si类的实例数为dij, 属于第i类的概率为pij, pij=dij/dj, 信息期望I (A=aj) 为:
当A=aj时的概率为pj=dj/n, 利用属性A的取值进行划分子集的期望信息, 即A的熵为:
属性A在进行分类划分时提供的信息量, 称作属性A的信息增益, 记为Gain (A) :
3) 属性A的信息增益率:
其中I (A) 为属性A的取值划分集合S的信息期望的比值
步骤2:确定节点属性后, 根据节点属性不同取值建立不同的分支, 而属性值的不同取值对应不同的数据子集。依此类推, 对各数据子集, 仍然以信息增益率最大值的属性作为作为子节点属性的选择标准[3], 直到各子集的实例都属于同一类别为止, 由此就能构造一棵决策树。
步骤3:提取决策规则。生成决策树后, 就可以依据各分支上属性的取值获取决策规则, 新数据集就可以根据决策规则进行分类预测。
1.3 C4.5算法对连续属性的处理
C4.5算法既能处理离散型属性数据, 也能够对连续性属性数据进行处理[4]。若数据集中有连续型属性时, 需要对连续属性的值进行离散化处理, 选择分支节点属性以信息增益率作为标准。
如果某节点中数据集合T的实例中有连续型属性A, C4.5算法需进行离散化处理[5]。首先可对连续属性值进行排序, 确定连续属性的最大值和最小值, 采用一定的算法将整个区间划分成多个相等的子区间或以排序后的连续型属性的相邻值的均值设定子区间, 然后计算该属性的信息增益率, 以信息增益率的最大值为标准找到连续属性的分割点, 对连续型属性的实际取值进行顺序查找确定实际的分割点[6]。具体步骤如下:
1) 对节点对应的T集合上的所有实例中连续型描述属性的取值, 按从小到大的顺序进行排列, 得到属性A的取值的顺序排列{a1, a2, …, av}。
2) 计算信息增益率。属性A的取值ai, 其中1≤i≤v-1, 按值a= (ai+ai+1) /2将集合T划分为两个子集:T1={ai|ai≤a}和T2={aj|aj>a}, 然后计算属性A按照a值划分的信息增益率。a值用区间[a1, ai], [ai, ai+1]来描述属性A的取值。
3) 确定连续属性的分割点。属性A的每个v-1种划分, ai和ai+1都可看作该连续属性的2个离散取值的情况进行处理, 计算每种a值划分的信息增益率, 选择v-1种划分中具有信息增益率最大值的a作为连续属性的分割点。
4) 确定实际分割点。在属性A的取值序列{a1, a2, …, av}中找出最接近分割点a, 但又不超过它的属性A的取值ai, 将ai作为属性A的实际分割点, 完成对连续型属性A的离散化处理。
2 连续属性处理过程的改进
将数据集合T以属性A的值按照升序排序后, 在离散化的处理过程中进行信息增益率的计算时, 可将通过比较得到的信息增益率最大值和对应的分割点的序列值分别保存到变量Gain Max和Index M ax中, 变量的初值可设为零。当计算完所有的v-1个区间的信息增益率值时, 就得到了Gain Max和Index Max值, 这样能够提高效率, 节省运算时间, 也省略了多次顺序查找, 因为如果在计算出的v-1个信息增益率中找出最大的信息增益率, 又在连续型属性取值中查找最接近但又不超过属性分割点的属性A的取值ai, 多次的查找会使算法的执行效率降低。
当数据集较大且连续属性值比较多时, 在离散化处理时, 对所有划分计算信息增益率会占用较多的时间, 如何快速找到最佳划分点, 即属性分割点成为解决问题的关键。根据Fayyad的研究, 无论数据集类别有多少种, 连续型属性所属类别分布如何, 最佳划分点总是在类别边界点处, 实际的分割点总是出现在边界处, 因此对离散化方法可做进一步优化。具体步骤如下:
1) 将该节点上的数据集合按照连续型属性的取值从小到大进行顺序排列, 即A属性的取值的顺序序列{a1, a2, …, av}。
2) 计算信息增益率。假设数据集合T分成两个类别, 以A属性ai为边界处, 即分割点, 其中1≤i≤v-1, 得到两个子集:T 1={aj|1≤j≤i}和T2={aj|i
3) 确定连续属性的分割点。假设数据集合T分成多个类别, 通过类别边界处找到分割点。这里分割点可选为相邻不同类别的两个属性值中较小的一个。例如, 当排序后的实例属性值为 (a1, a2, …, a8) , 其中前2个属于类别1, 中间3个属于类别2, 最后3个属于类别3, a2与a3分别属于类别1与类别2, 边界点在a2与a3之间, 选择属性值较小的a2为分割点, 因此只需考察两个分割点a2与a5而无需检查其余6个分割点。
4) 确定实际分割点。计算按照属性分割点的值划分得到的信息增益率, 选择信息增益率最大的属性值作为最佳分割点。
3 改进的处理过程与原处理过程的分析比较
在处理连续属性的离散化时, 需要将数据集合T以连续属性A的值从小到大排序, 减少了后续处理过程中排序和查找的次数, 提高了确定分割点的效率。在原C4.5算法中数据集合T中属性A的值为ai (1≤i≤v-1) , 按值a= (ai+ai+1) /2将T划分为两个子样本集, 改进的C4.5算法中直接用ai将T划分为两个子样本集, 由于{a1, a1, …, av}是有序序列, 用ai将T划分为两个子样本集与用a划分的效果相同。同样在计算信息增益率的过程中得到最大信息增益率和分割点序号, 节省了两次顺序查找的时间, 因此改进后的C4.5算法并没有改变原C4.5算法构造的决策树性质。
改进的分割点选择方法可以有效地减少信息增益率的计算次数, 从而提高效率, 当属性的取值越多, 而所属的类别越少, 性能会有明显的提高。当属性的每个取值都属于一种类别这种极端的情况出现时, 改进算法与未改进算法运行次数相同, 运行效率也不会降低。在未改进的算法中, 需要计算所有划分的信息增益率, 而在改进后的算法中, 只计算边界点处的属性值的信息增益率, 降低了计算复杂度。当连续型属性所属的类别较少时如只有2种类别时, 改进后的算法计算效率有明显提高。当遇到极端情况时, 每个属性值分别属于不同类别, 改进算法的与C4.5的计算复杂度相同。
4 实验分析对比
选取U C I机器学习库中的有1 4条记录的weather数据集创建决策树, 根据天气的情况判断是否适合打球 (yes为适合, no为不适合) , 使用C4.5算法和改进的C4.5算法构造的决策树相同 (如图1) , 由此可知, 改进的C4.5算法与原算法有大致相同的准确率。
在UCI机器学习库中选取4个数据集, 这4个数据集中都有连续型属性值, 通过数据集的测试将改进前后的算法在运算时间上进行分析比较。其中各数据集如表1所示。
C4.5算法与改进的C4.5算法运算时间的对比如图2所示。
使用数据集构造决策树所用时间, 与数据集的大小及连续型属性值的多少有关。通过上述4个数据集进行测试的结果可以看出, 使用改进的C4.5算法构造决策树所用的时间比未改进的算法要快, 尤其在数据量较大时较为明显, 对相同规模的数据集, 改进的C4.5算法构造决策树所用的时间较少。
5 结束语
本文详细的分析了决策树分类算法C4.5, 针对C4.5算法的连续属性离散化处理过程中需要处理所有划分情况的特点, 根据Fayyad边界点判别定理, 提出了尽快找到最佳划分的改进方法, 算法运算速度得到了提高, 改进的C4.5算法与原算法相比, 在构造决策树时具有相同的准确率和较高的计算速度。
参考文献
[1]姚亚夫, 邢留涛.决策树C 4.5连续属性分割阈值算法改进及其应用[J].中南大学学报 (自然科学版) , 2011, 42 (12) :3772-3776.
[2]黄文.决策树的经典算法:ID3与C4.5[J].四川文理学院学报 (自然科学) , 2007, 17 (5) :16-18.
[3]刘耀男.C 4.5算法的分析及应用[J].东莞理工学院学报, 2012, 19 (5) :47-52.
[4]冯帆, 徐俊刚.C 4.5决策树改进算法研究[J].电子技术, 2012, 39 (6) :1-4.
[5]乔曾伟, 孙卫祥.C4.5算法的两点改进[J].江苏工业学院学报, 2008, 20 (4) :56-59.
决策树分类算法 篇7
从80年代起, 数据挖掘作为新兴研究领域在各领域得以广泛应用, 如金融分析、生物学分析、企业分析等, 同时涌现了大批数据挖掘工具。然而, 在教育领域中的应用相对较少, 尤其是在学生成绩分析的应用更是欠缺。大部分高校的成绩管理依然停留在简单数据管理及查询阶段, 成绩分析多为分段划分与平均值计算, 对影响成绩的因素也多采取经验指导, 缺乏一定的科学管理。因此, 以研究影响学生成绩因素为基础, 通过决策树方法C4.5算法对学生计算机二级成绩进行分析挖掘并生成决策树, 找出相应的分类规则, 为今后教学工作提供指导, 进一步提高教学质量, 促进教育教学改革。
2 学生成绩数据的处理流程
分类方法是数据挖掘应用领域中的重要技术之一, 它通过分析训练集中的数据, 对类建立分类模型, 再利用分类模型来预测类标记未知的对象类[1]。数据在经过处理、算法分析、结果分析和应用四个阶段后, 通过已知数据集建立概念描述模型, 然后再利用所获得模型进行分类操作:首先对模型分类的准确率进行估计, 如果一个模型的准确率经测试被认为是可以接受的, 那就可以使用这一模型对未知类型的数据记录或对象进行分类, 整个处理流程如图1所示。
3 数据获取
数据由湖北工程学院新技术学院教务处提供, 从中抽取了12级报考计算机二级的学生信息, 针对该班级随机抽样其中一个学期计算机二级的考试成绩及平时记录并填写了相关评价表。由文献[2][3]指出:为保证数据有效性, 需要对数据进行预处理, 即进行初步的分析筛选。确保数据的有效性, 保证采集数据与分析内容有关, 避免丢失相关数据。经过调查分析, 总结得出影响学生的几个因素:
*学生自身因素:专业、爱好、到课率、兴趣程度、课程作业完成度、平时成绩等。
*教师因素:教学经验, 讲课质量, 作业布置程度等。
*学校因素:对其重视程度, 是否提供了良好的学习环境等。
为了简化分析过程, 提取了其中主要因素对数据进行汇总, 如表1、表2所示:
4 数据过滤
针对异构数据源中数据的不规范性、重复性和不完整性等问题进行清理, 一般采用分类分析将对象的集合划分成由相似的对象组成的多个子类, 对数据属性进行分类, 达到将数据去除噪声和纠正错误的目的, 提高数据质量, 符合分析要求。在抽样数据中, 讲课质量和试卷难度属性的学生评价几乎相同因此将这两个值进行删除清理;期中考试和期末考试具有相似价值属性且期末考试更具有代表性, 所以对这两个值合并。
分类要求, 需要对数据做出合并操作, 如:计算机二级成绩情况分为, 小于70分为不及格, 70分到85分为良好, 85以上为优秀。由于分类算法对数值型及字母型数据比较敏感, 在实际操作中能快速识别, 因此将作业提交数的评价分别用0、1、2代替, 其它评价指标如此类推, 得到的结果如表3所示。
5 决策树
对于数据库, 决策树具有以下性质[4]: (1) 每个内部结点都被标记一个属性Ai; (2) 每个弧都被标记为一个谓词, 这个谓词对应用于其父结点的属性; (3) 每个叶结点都被标记为一个类Cj。决策树的实现有ID3和C4.5两种常见算法。
ID3算法是一个以递归方式构造决策树的贪心算法。在分枝结点处属性的选择上ID3使用了信息论中的互信息的概念, 通过计算分枝结点每个属性的信息增益, 选择具有最高信息增益的属性作为当前结点的分枝属性, 并在每个分枝子中重复建立树的下层结点和分枝。
在ID3中, 每个特征都由数据有序程度 (熵) 用以对比决策前后的数据集的有序程度量, 熵的定义如式一所示:
表示随机变量X的不确定性, 其中pi表示事件发生概率。对于某个特征的熵值计算公式式二所示:
上式就是数据集D在特征条件A中的熵。
C4.5算法通过为训练集D构造决策树, 选择Gr (X) 值最大的属性作为分裂节点, 按照此标准将D分成n个子集。若第i个子集Di含有的元组的类别一致, 该节点就成为决策树的叶子结点并停止分裂。而对于不满足此条件的T的其它子集, 按照上述方法递归的生成树, 直至所有子集所含元组都属于一个类别为止[5]。
不同于ID3在信息增益分类决策时偏向取值较多的特征的问题, C4.5使用基于信息增益比的分类决策方法经行求解。信息增益比的定义如式三所示:
其中, Gr (D, A) 是信息增益, H (D) 是相应特征的熵, 其定义如式四所示:
6 生成决策树及分类规则
最后, 通过C4.5算法对数据进行决策树模型建立, 如图2所示。
决策树最大优点就是可以直接提取分类规则, 在本次研究中, 希望找到影响学生计算机二级成绩合格的因素, 因此对规则中分类为“合格”规则进行提取。使用IF...THEN规则对从根到叶节点的每条路径创建一个规则, 给路径上的每个属性一个规则前条件的合取项, 所生成的分类规则如下:
If“二级成绩”=“合格”and“平时成绩”=“良好”and“课程兴趣”=“合格”and“考勤记录”=“正常”and“全勤”and”作业提交”=“合格”;
从规则中可以看出, 如果学生计算机二级成绩合格及优秀那平时成绩也合格及优秀, 而该课程的兴趣度则会影响平时成绩;在考勤记录中可以看出对课程的兴趣度是否良好, 同时作业提交数也是对考勤记录的一种影响因素。可以看出平时成绩对学生计算机二级有很大的影响, 因此在今后的教学中应该注重每一次的考试, 同时加强老师上课质量, 提高学生的兴趣程度, 并督促学生考勤同时能按时提交作业, 以此达到来提高成绩的目的。
7 总结
文章讨论了决策树数据分析技术在学生成绩中的应用, 使用C4.5算法建立对学生计算机二级成绩影响因素的决策树, 对学生计算机二级影响的因素进行评价分析, 达到对今后教学工作提供意见性指导并提高考试的通过率, 达到提高教学质量和促进教育教学改革的目的。
参考文献
[1]Jiawei Han, Mieheline Kamber.范明, 孟小峰等译.数据挖掘概念与技术[M].第2版.北京:机械工业出版社, 2007.
[2]李哲, 张映雪, 胡蕙.聚类分析在大学生心理健康管理中的应用[J].湖北工程学院报, 2014, 34 (6) :53-57.
[3]Chen K, On coresets for k-median and k-means clustering in metric and Euclidean spaces and their application[sJ].SIAM Journal on computing, 2009, 39 (3) :923-947.
[4]陈安, 陈宁, 周龙骧, 等.数据挖掘技术及应用[M].北京:科学出版社, 2006.
决策树分类算法 篇8
关键词：数据挖掘,决策树,客户细分
引言
目前国内银行大部分的收入依然来自公司银行业务, 根据波士顿咨询公司 (BCG) 的一项最新分析, 银行业超过60%的收入来自公司客户。但是零售银行业务正以公司银行业务两倍以上的速度增长。在美国、西欧和日本市场, 零售银行不仅仅为银行带来一半或更多的收入来源, 而且相对风险较大的公司银行业务而言更为稳定和可靠。近几年国内零售银行市场也有明显变化, 如中信银行信用卡在2006年底发行量约为200万, 实现了盈亏平衡。到2007年中发行量已经达到300万, 并开始盈利。越来越多的银行意识到, 个人客户零售银行时代即将到来。
零售银行是目前中国银行业的一项关键业务。做好零售市场, 就必须重视优质客户的挖掘、客户细分、客户保持等方面的研究和应用。本人将基于决策树数据挖掘技术针对银行客户进行分类研究, 让银行根据不同的类型深化客户经营, 准确把握目标客户的消费特征以及需求特征, 有针对性地进行产品设计、销售和服务。
一、客户细分及变量选择
客户细分的概念是美国市场学家温德尔.史密斯于20世纪50年代中期提出来的。所谓客户细分主要指企业在明确的策略、业务模式下和专注的市场条件下, 根据客户的价值、需求和偏好等综合因素对客户进行分类, 分属于同一客户群的消费者具备一定程度的相似性, 而不同的细分客户群间存在明显的差异性, 如图1。正确的客户细分能够有效地降低成本, 获得更强、更有利可图的市场渗透。
变量选择是根据不同需求做出的。一般可供使用的细分变量主要有描述型变量和行为变量两类。客户描述型变量主要是用来理解客户的基本属性的信息。如个人客户的地理位置、年龄、性别、收入等变量指标, 这类指标在确定某个细分市场的成员方面具有关键的作用。如2006年9月至11月, 中信银行针对女性持卡客户开展的"魔力周年庆"活动, 推出了优惠女性体检、保险升级、取现及分期付款优惠方案等多项营销措施, 对魔力信用卡持卡人开展持续经营, 在两个月内拉动女性卡消费增长45%。行为变量主要是涉及客户交易行为和与银行关系的一系列变量指标, 这一类指标用于界定某一细分市场中企业应该努力的方向, 是确定目标市场的关键因素。它包括客户购买服务或产品的记录、客户的服务或产品的消费记录、客户的偏好、消费行为等相关信息。
二、数据预处理
数据预处理包含数据收集、数据清理、客户数据集成以及数据选择、数据变换等工作。太仓农村商业银行提供的个人客户内部测试数据包含了个人客户的基本信息。将定性数据转换为定量数据, 如表1。.并利用统计软件SPSS对客户进行分类。
三、依据决策树算法构造决策树
1. 决策树算法
决策树算法是数据挖掘的核心技术之一, 它通过将大量数据有目的的进行分类, 从中找出一些潜在的、对决策有价值的信息, 常用于预测模型中。C4.5算法采用信息增益率作为属性选择的度量标准。算法中, 决策属性信息增益的计算方法如下:
设S是客户数据样本的集合, 根据数据训练集, 类标号属性 (是否结婚、学历、年薪等) 有m个不同的值, 也就是说定义了m个不同的类Ci, i=1, 2, …, m;Ri为数据样本集合S中数据Ci类的子集, 用ri表示子集Ri中的样本数。
对于给定样本集合S (100人的基本信息) 分类所需的期望信息量可以由以下公式给出:
其中:p表示任意样本属于Ci类的概率:pi=ri/|s|, |s|为给定样本数据集中的元组数量。
2. 构造决策树
选取训练样本数据集, 100个元组, 在此略图。首先取属性"类别"作为类别标识属性, 属性"性别"、"年龄"、"学历"、"职位"、"家庭收入"、"婚姻状况"、"居住年限"、"健康状况"、"房产状况"作为决策属性集。
训练样本数据集得类别属性中, 共有100个元组, 其中风险客户、较差客户、一般客户、重点客户分布是:r1=2, r2=4, r3=25, r4=69;
为了计算每一个决策属性的信息增量, 首先利用公式计算集合S类的期望信息量:
然后计算每一个决策属性的期望信息量。当性别=男、女依次分别为:
由此得到"性别"的熵值:
由此得到"性别"的信息增益为G (性别) =I (S) -E (性别) =0.0302
其信息增益率为R (性别) =G (性别) /E (性别) =0.026544
同理计算R (年龄) =0.48889, R (学历) =1.39583, R (职业) =1.481, R (婚姻状况) =0.0621, R (年薪) =1.73487, R (房产状况) =0.3745
由于"年薪"具有最大信息增益率, 所以该属性作为根节点。
对于每个分支重复上述步骤, 生成决策树, 如图2。
3. 模型结果分析
由决策树叶子节点得出规则, 部分如下:
(1) 若某客户年薪为第二类 (收入在1~3万之间) , 且职业为第一类 (农民、学生、工人、服务员) , 则该客户判为较差客户。
(2) 若某客户年薪为第二类 (收入在1~3万之间) , 职业为第二类 (广播电视、石化公司、网通保险、银行职员、军人、烟草、公务员、房地产、进出口贸易) , 学历为第二类 (大专、本科) , 且年龄为第一类 (小于25岁) , 则将该客户判为一般客户。
(3) 若某客户年薪为第四类 (5万以上) , 未婚或已婚的判为重点客户。
参考文献
[1]张媛媛个人优质客户管理系统的设计, 华南金融电脑期刊, 西南财经大学, 2005-09
[2]曹寅商业银行客户关系管理_CRM_的应用及其优化研究, 硕士论文, 浙江大学, 2008-09
[3]郭东兰华夏银行客户信息管理系统应用设计, 硕士论文, 复旦大学, 2008-02
[4]姜志强商业银行个人客户营销管理的研究与实现, 硕士论文, 吉林大学, 2007-10
[5]郭喜全银行分析型客户关系管理系统的设计与实现, 硕士论文, 山东大学, 2008-04