C4.5决策树（精选4篇）
C4.5决策树 篇1
0引言
决策树方法在分类、预测、规则提取等领域应用广泛。构造决策树的算法有很多种,其中最具影响力的决策树算法是ID3算法[1]和C4.5算法[2]。ID3算法是由Quinlan于1979年提出来的,C4.5算法是由Quinlan于1993年在ID3算法的基础上提出来的,保留了原有算法的优点并改进了原算法的缺点。但是,C4.5算法仍然存在一些不足,比如在处理现实数据时,数据集中存在很多与决策属性关联性很小甚至毫无关联的冗余属性;连续属性值处理过程中最优分割阈值选择比较耗时等等。因此,本文提出一种改进的C4.5算法,通过实验将它与传统的C4.5算法进行比较与分析,以此来说明改进算法的优越性。
1C4.5算法原理
C4.5决策树算法主要利用信息熵原理,选择信息增益率最大的属性作为分类属 性,递归地构 造决策树 的分支,完成决策树的构造[3]。它是在ID3算法的基 础上提出来的。ID3算法的基本原理[4]如下:设E = F1×F2 ×F…×Fn是n维有穷向量空间,其中Fi是有穷离散符号集。E中的元素e= {V1,V2,…Vn}称为样本 空间的例子,其中Vj∈Fi ,(j=1,2,…n),为简单起见,假定样本例子在真实世界中仅有两 个类别,在这两个 类别的归纳任务中,PE和NE是实体分配,称为概念的正例和反例。一样本集被一棵决策树作出正确分类所需要的信息量为:
如果选择属性A作为决策树的根,A取V个不同的值{A1,…,An},利用属性A可以将E划分为V个子集{E1,…Ev},其中Ei(1≤i≤V)包含了E中的属性A取Ai 值的样本数据,假设Ei中含有pi个正例和n个反例,那么子集Ei所需要的期望信息是I(pi,ni),以属性A为根,所需要的期望熵为:
其中,
以属性A为根的信息增益为:
对样本集T,假设A有s个不同取值的离散属性,划分为s1,s2,···,sn共n个子集,用A分割样本集所得的信息增益算法与ID3一样,分割信息量为:
信息增益率为:
C4.5算法的基本原理与以上ID3算法的基本原理类似,唯一不同的是ID3算法是选择信息增益最大的属性作为测试属性,而C4.5算法是按公式(6)计算信息增益率。选择具有最高信息增益率的属性作为测试属性,较好地解决了ID3算法的多值属性偏向问题。
2基于粗糙集理论的属性约简
1982年波兰数学家Z.Pawlak提出了一 种新的数 学工具,主要用来处理不确定性和模糊性问题,它就是粗糙集(RoughSet)理论。和处理不确定性问题的数学工具相比,粗糙集理论具有一定的优越性。比如,它在处理数据时,并不需要关于数据的任何已知的或额外的信息;另一个特点则是它能表达和处理不完备信息,能够通过属性约简推导出知识的最小表达。
2.1粗糙集概念
定义2:在一个已知的信息系统中,对于属性集RA且R≠Φ的不可区分关系IND(R)定义为:IND(R)={(x,y)|(x,y)∈U×U且a∈R,有f(x,a)=f(y,a)},若(x,y)∈IND(R),则称x和y是R不可分辨的。显然IND(R)是一个等价关系,记作U/IND(R)= {[x]p:x∈U},简记为U/R,其中:[x]p= {y∈U | (x,y)∈IND(R)}。
2.2粗糙集的属性约简
定义4:一个属性a的重要性(P对U有一个分类,R对U也有一个分类,如果分类完全相同,则P,R对于分类来说是一样的)可以利用两个属性集合P,R之间的相互依赖程度来确定。属性集P对R的依赖程度用γR(P)表示,定义如下:
其中card(.)表示集合的基数,POSR(P)是属性集R在U/IND(P)中的正区域。
定义5:属性a加入R,对于分类U/IND(P)的重要性程度为:SGF(a,R,P)=γR(P)-γR-{a}(P)。
定义6:在信息系统S= (U,A,V,f)中,,且P是独立的,满足IND(P)=IND(A),则称P是A的一个约简,用RED(A)表示P的所有约简集合;如果P中的所有元素在A中不可省 略,则称P是A的核,记为Core(A),显然Core(A)=∩RED(A)。
3C4.5决策树算法改进
3.1算法改进思想
3.1.1属性约简基本思想
粗糙集理论中进行属性约简的方法有很多种,本文采用的是基于属性重要性的属性约简方法,基本思想为:
依据定义4计算决策表中决策属性对条件属性C的依赖程度γc(D),如果POSc(D)≠POSC-{c}(D),表示该属性为核属性,将此属性加入核属性集Core(D);依据定义5分别计算每个属性相对于核属性集的重要性程度,选择重要性程度最高的属性与属性核集进行合并,作为当前约简结果集,直到约简集能够保持相对约简为止,输出约简结果;否则继续计算,相对约简的标准为IND(RED)=IND(D)。
3.1.2连续数据离散化过程改进基本思想
C4.5算法在连续属性离散化过程中,需要对属性的所有划分进行预测,这一计算量很大,将占有很多时间,如何快速定位连续属性的最佳分割点已成为亟待解决的问题。根据Fayyad[5]边界点判 定定理,无论数据 集有多少种分类,无论数据分类怎样分布,连续属性的最佳划分点总是出现于连续序列中两个相邻异类实例的边界点上[6]。所以,在对连续属性进行离散化过程中,不需要对每个阈值点比较,只要比较相邻不同类别的边界点即可。例如,当排序后的实例属性值为 {v1,v2,···,v10},其中前3个属性类别C1,后3个属于类 别C2,最后3个属于类 别C3 ,只需要检查两个边界点v3和v7,无需检查其余7个阈值点,然后选择v3和v7中使得平均类熵最小的那个作为最优阈值[7]。
3.2改进算法描述
输入:决策系统S = (U,V,F,C∪D)
输出:决策树
(1)对决策树系统进行规范,依次对每个属性从1开始逐个编号,每个属性的取值范围也从0开始逐个编号。
(2)根据定义2计算不可分辨关系U/IND(R),就是将相同条件属性值的实例分在同一个组,形成若干个这样的组,从而构成U上的一个划分,用二维数组IND的每一行存放每一组实例。
(3)根据定义3计算条件 属性C的正域POSC(D)。扫描IND数组的每一行,如果存在决策树属性值不一样的实例,就将这一行删除,POSC(D)就为剩下的实例集合。
(4)根据定义4计算决策表中决策属性对条件属性C的依赖程度γc(D)。
(5)令核属性集Core(D)=φ。
(6)对每个条 件属性c计算POSC-{c}(D),如果POSc(D)≠POSC-{c}(D),则Core(D)=Core(D)+{c}。
(7)令约简集RED =Core(C)。
(8)如果IND(RED)=IND(D),则输出最 小约简集RED,否则对每 个C-RED的属性p,计算属性 重要性SGF,选择属性重要性程度最大的加入到RED中,如果同时存在多个属性达到最大值,则从中选择一个属性值组合数最少的属性加入到RED中,重复第(8)步直至输出最终约简集RED。
(9)利用以上得到的最小约简属性,得到新的数据样本集合,作为算法的数据输入。
(10)利用传统算法中的方法创建节点,如果样本集中存在连续型属性时,则使用改进的离散化方法进行处理。
(11)对样本集重复进行步骤(10)操作,直至分支样本集中全为同一类别或者样本集为空。
3.3实验结果分析
为了验证改进算法 的优越性,在Win7系统和WEKA3.6.9平台下,利用UCI数据集中的Credit-a数据集进行具体分析和验证。Credit-a数据集包括690个样本,共16个属性(包含了决策属性),其中有6个连续型属性,有2类。首先,分别对每个属性和属性的取值范围逐个编号,利用上述的粗糙集属性约简算法对该数据集进行属性约简,约简后决 策表中仅 剩6个条件属 性:A2、A6、A7、A9、A14和1个决策属性class,然后采用改进的C4.5算法对约简后的数据集进行分类(其中70%作为训练样本,30%作为测试样本),分别利用传统的C4.5算法和改进的C4.5算法进行分类,对比分析与比较两种算法的结果,如表1所示。
结果显示,改进的C4.5算法得到的决策树比传统的C4.5算法小,属性个数从16降到了6,减少了数据冗余,节点数从42减到了22,叶子节点数也从30减到了14,决策树的规模得到了优化;分类时间从0.22减少到0.02,提高了分类 效率;分类准确 率则从85.507% 提高到86.087%。因此,可以看出改进的C4.5算法不仅缩小了树的规模,提高了分类效率,而且提高了分类准确率。
4结语
本文提出一种改进的C4.5决策树算法,不仅利用粗糙集理论中的属性约简方法对决策表中的条件属性进行了过滤,去掉大量冗余属性,减少噪声,而且对连续属性离散化过程进行了改进,将约简后的数据作为输入,得到最终分类结果。实验数据表明,改进的C4.5决策树算法不仅缩小了决策树规模,而且提高了分类准确率和决策树构造效率。该改进算法对今后决策树算法的研究与应用具有一定的指导意义。
一种改进的C4.5决策树算法 篇2
数据挖掘中决策树是解决分类问题的方法之一, 是一种归纳学习算法。通过一组属性值向量和相应的类, 采用归纳学习算法构造分类器和预测模型, 能够从一组无序和无规则的数据中生成决策树形式的分类规则。决策树基本不依赖于任何专业领域的知识, 所以在分类, 预测和规则提取等领域都被广泛的应用。70年代末, J.ROSS Quinlan提出了ID3算法后, 在机器学习和知识发现领域决策树算法都得到了进一步应用和发展。
ID3算法的核心是选择属性时, 用信息增益 (information gain) 作为选择属性的度量标准, 在测试每一个非叶子结点时, 能获得关于被测试记录最大的类别信息。虽然ID3算法具有算法清晰, 方法简单和学习能力较强的优点, 但是ID3算法不能处理连续的属性值, 并且依赖于训练数据集的质量, 只对数据集较小的情况有效, 训练数据集在逐渐变大时, 决策树可能会随之改变。由于ID3算法存在着许多需要改进的地方, 为此, J.ROSS.Quinlan于1993提出了C4.5算法, 对ID3算法进行了补充和改进。C4.5算法具有ID3算法优点的同时也改进和扩展了算法, 使其产生易于理解和准确率较高的分类规则。相比于ID3算法, C4.5算法用信息增益率来选择属性, 而不是ID3算法所用的信息增益;在ID3算法的基础上还增加了对连续属性的离散化、对不完整属性的处理能力和产生规则等功能。
2 C4.5算法
2.1 信息增益和信息增益率
设D是m个不同值的训练集有m个不同类Ci (i=1, 2, …, m) , 设Ci, d是元组的集合, D和Ci, d中的元组个数是|D|和|Ci, d|。
2.1.1 信息增益
ID3算法中选择具有最高信息增益的属性作为节点N的分裂属性, 使元组分类的信息量最小。期望信息为:
2.1.2 信息增益率
信息增益率用“分裂信息”值将信息增益规范化, 假设以属性A的值为基准对样本进行分割, 训练数据集D用分类信息Split InfoA作为初始信息量划分成对应于属性A的有v个输出的v个划分信息。定义如下:
C4.5算法选取信息增益比最高的属性为集合D的测试属性, 创建一个节点并为每个属性创建分支划分样本。
2.2 C4.5算法实现
假设用D代表当前样本集, 当前候选属性集用A表示, 则C4.5算法的流程图如图1所示。
3 C4.5算法的改进
3.1 C4.5算法改进原理
C4.5算法得到很好的应用, 但是还存在一些不足, C4.5算法因为要对数据集进行多次的扫描和排序所以算法的效率降低。根据信息量计算公式的特点, 改进划分函数的属性选择度量计算公式和连续属性处理方法, 简化信息量的计算复杂度, 提高C4.5算法的执行效率。
C4.5算法由于大量使用了对数函数进行熵值运算, 增加了计算机的运算时间, 降低了每一次属性选择时算法的运算效率, 所以为了解决这个问题, 引入泰勒中值定理和麦克劳林展开式, 对熵值中的对数运算进行变换, 优化熵值运算, 缩短其运算时间。
C4.5算法对每个分割点都要计算相应的熵值, 才能得到最优的分割点, 所以在选择最佳的属性分割点时效率较低。为了解决这个问题, 引入边界点定义和Fayyad定理。
Fayyad定理:连续属性X各个候选分割点对应的信息熵值的最小值一定在边界点Bp上取得。
由以上定理可知, 连续属性的最优分割点在计算时, 只需要通过比较属性值序列在边界点的最小信息熵值, 就可以计算出该属性的最大修正信息增益率, 减少了候补分割点, 因此可以大大提高了计算的效率。
3.2 实验及结果分析
使用Weka作为数据挖掘平台, 对改进C4.5算法与传统C4.5算法的分类性能进行比较。实验所需数据来自于UCI数据集中IRIS的样本实例。算法执行效率及分类正确率实验结果如图2、3所示。
随着样本实例数的增加, 改进算法的执行效率得到提高的同时分类的正确率也有一定的提升, 因此改进的C4.5算法缩短了数据分析的等待时间, 提高工作效率, 保障了分类正确率。
4 结束语
本文通过对决策树分类算法C4.5的分析, 在此基础上, 针对该算法所存在的不足之处, 改进了熵值的计算和连续属性最优分割点的计算, 并用实验验证, 得到较好的验证结果。
摘要：数据挖掘中基于决策树的C4.5算法是一种经典的分类算法, 该算法具有ID3算法的优点, 但是也存在缺点。针对原算法的不足, 改进算法简化了熵值的计算, 改进了连续属性的处理方法, 使C4.5算法在执行效率上得到很大提高的同时也保障了分类的正确率。
关键词：数据挖掘,决策树,C4.5算法,信息增益率
参考文献
[1]Quialan J R.hduetion ofdecision trees[M].Machine Learning, 1986, (1) :81-106.
[2]陈青山.决策树算法在高校教学质量评价系统中的应用研究[C].西南交通大学硕士论文, 2010.
[3]Quialan J R.C4.5:Programs for Machine Learning[M].New York:Morgan Kaufnan, 1993.
[4]黄爱辉.决策树C4.5算法的改进及应用[J].科学技术与工程.2009, 9 (1) :34-36.
C4.5决策树 篇3
随着计算机网络和数据库技术的迅速发展, 关于如何在海量数据里发现有用的价值的信息和知识的工作受到越来越广泛的重视。数据挖掘也成为知识发现, 正是在这样的背景下产生并蓬勃发展起来的。数据挖掘是从大量的数据中挖掘出隐含的、未知的、用户可能感兴趣的和对决策有潜在价值的知识和规则。分类技术是数据挖掘的重要任务之一, 其核心问题是解决分类模型的构造和分类算法的实现。决策树表示方法是应用最广泛的逻辑方法之一, 主要是因为它能非常方便地用图形化 (树型结构) 的方式表现挖掘结果, 适应于企业管理部门做出决定。
在构造决策树的算法中, ID3和C4.5算法最具有代表性, 其中C 4.5算法已经在商业、金融、医疗等领域得到了成功的应用。笔者利用C 4.5算法对银行信贷业务中对客户信息进行数据挖掘分析, 建立预测模型并解释该模型。
一、决策树生成及算法
决策树分类方法采用至顶向下的递归方式, 在决策树内部结点进行属性值的比较, 并根据不同的属性值判断从该结点向下的分支, 在决策树的叶结点得到结论。所以, 从决策树的根结点到叶结点的一条路径对应着一条合取规则。基于决策树的分类算法的一个最大的优点就是它在学习过程中不需要使用者了解很多背景知识。
要生成决策树模型, 首先将数据集划分为训练集和测试集。在训练集中, 根据每个属性的信息增益率, 构造出最初的决策树模型。决策树建立好后, 为消除决策树对测试数据分类时产生的模型“过度拟合”问题, 将其进行剪枝, 得到决策树决策规则。
1. 决策树生成的过程。
(1) 收集客户信息, 对数据信息进行合并, 形成结构统一的客户信息数据源。 (2) 对数据源进行数据预处理, 去掉与决策树无关的属性和高分支属性、将数值型属性进行概化以及处理含空缺值的属性, 形成决策树训练集。 (3) 对训练集进行训练, 计算每个属性的信息增益率和获取率, 选择获取率最大的但同时获取的信息增益率又不低于所有属性平均值的属性, 作为当前的主属性节点, 为该属性的每一个可能的取值构建一个分支。对该子结点所包含的样本集递归地执行上述过程, 直到子集中的数据记录在主属性上取值都相同, 或没有属性可再供划分使用, 生成初始的决策树。 (4) 对初始的决策树进行剪枝。有先剪枝和后剪枝两种算法, 主要采用后剪枝算法对初始决策树进行剪枝, 并在剪枝过程中使用一种悲观估计来补偿树生成时的乐观偏差。 (5) 由所得到的决策树提取分类规则。对从根到树叶的每一条路径创建一个规则, 形成规则集。将规则集显示给用户, 把用户筛选过认为可行的规则存入规则数据库。 (6) 当新客户在银行进行信贷业务时, 系统运用决策树所得到规则对新客户的数据信息进行分析, 预测该客户的行为属于哪一等级, 从而为银行是否对该客户进行贷款提供辅助决策。
3. 设数据划分D为类标记的元组的训练集。
假定类标号属性m个不同值, 定义m个不同的类Ci类 (i=1, …, m) 。设Ci, D是D中Ci类的元组的集合, 分别是D和Ci, d中元组的个数。 (1) 对D中的元组分类所需的期望信息为
(1) 对D中的元组分类所需的期望信息为
pi是D中任意元组属于类Ci的概率, 并用 估计。Info (D) 又称为D的熵 (entropy) 。
假设将属性A划分D中的元组, 其中属性A根据训练数据的观测具有v个不同值 可以用属性A将D划分为v个子集其中Dj包含D中的元组, 它们在A上具有值。那么属性A的信息熵为:
(2) 信息增益定义为原来的信息需求与新的需求 (即对A划分后得到的) 之间的差。即:
(3) 属性A有v个不同的值可以用属性A将D划分为v个子集 其中Di包含D中这样一些样本:它们在A上具有。假如我们以属性A的值为基准对样本进行分割, 就是初始信息量:
(4) 信息增益率定义为信息增益与初始信息量的比值:
4. 决策树的剪枝。
当得到完全生长的决策树后, 由于数据中的噪声和离群点, 许多分枝反映的是训练数据中的异常。剪枝方法处理这种过分拟合的问题。通常, 这种方法使用统计度量, 剪去最不可靠的分枝。有两中常用的剪枝方法:先剪枝和后剪枝。
C 4.5使用悲观剪枝方法, 它类似于代价复杂度方法, 也使用错误率评估, 对子树剪枝做出决定。然而基于训练集评估准确率或错误率是过于乐观的, 因此具有较大的偏倚。因此, 悲观剪枝法通过加一个罚来调节从训练集得到的错误率, 以抵消所出现的偏倚。
二、决策树C 4.5算法在银行信贷业务中的应用
1. 数据准备和数据预处理。
银行在以往的信贷业务中, 积累了大量客户信息和还贷情况等数据, 确定是否对具备贷款担保条件的客户发放贷款, 存在决策分析问题。
在选择哪些客户属性作为决策属性时, 可以去掉一些对贷款风险无关的属性, 如姓名、性别、身份证号、联系方式等信息, 选出的属性有客户的年收入、有无住房、信誉度、贷款期限和是否拖欠贷款5个属性, 其中是否拖欠贷款是我们要进行测试的目标属性, 建立判断客户是否拖欠贷款的训练样本集到表1。
2. 构造决策树。
通过对1 0个客户信贷情况的数据进行计算, 得到4个属性的信息增益和信息增益率, 如表2所示。
从表2可知, 属性信誉度具有最大的信息增益率值, 故选择该属性作为决策树的第一个分节点进行测试。在构造决策树的过程中以是否拖欠贷款作为目标属性, 根据决策树C 4.5算法和表2生成决策树, 并对决策树进行剪枝, 修剪后的决策树如图所示。
3. 决策树提取分类规则。
基于图1的决策树, 对其从根到树叶的每条路径创建一个规则, 以IF-THEN形式的分类规则表示。该分类沿着给定路径上的每个属性和属性相关联的值形成规则前件 (“if”) 的一个合取项, 则叶节点包含类预测, 形成后件 (“then”) 部分, 得出最后结论。从图1中提出的规则如下:
规则1:如果信誉度良好, 则该客户不拖欠贷款。
规则2:如果信誉度一般, 并且无住房, 则该客户拖欠贷款。
规则3:如果信誉度一般, 并且有住房、年收入≥3万, 则该客户不拖欠贷款。
规则4:如果信誉度一般, 并且有住房、年收入<3万并且贷款期限是中期, 则该客户拖欠贷款。
规则5:如果信誉度一般, 并且有住房、年收入<3万并且贷款期限是短期, 则该客户不拖欠贷款。
我们从这个决策树模型可以看出, 影响客户能够按时偿还贷款的属性主要由信誉度决定, 如果信誉度良好, 客户都会按时偿还贷款。有个这个预测模型, 银行就可以根据该预测模型, 判断申请银行贷款的客户能否按时还贷款。例如一个客户, 信誉度等级为一般, 年收入为2万, 贷款期限是短期, 则根据预测模型可知该客户是不会拖欠贷款的, 应该准予贷款。
这样就能大大降低银行信贷业务中的风险, 使银行的信贷风险尽可能降到最低, 从而减少银行的经济损失。
三、结束语
决策树是数据挖掘中的一个常用的算法, C4.5算法[6]是在ID3的基础上改进而生成的, 它更好地修正了ID3的剪枝算法。C4.5算法由于它易于转化为图像显示的特点, 使得它使用范围很广。通过数据预处理, 构造和修剪决策树, 进行分析和评估, 生成分类规则等步骤, 从而完成分类数据挖掘。本文主要将C4.5算法应用到银行信贷业务中, 通过建立决策树预测模型, 使银行信贷人员了解了客户的哪些属性影响到是否能按时还贷。但是在建立预测模型过程中, 有一些影响用户能否按时还贷的因素未能考虑进去, 例如客户遭受突发事件 (失业、意外事故等) 、偿还收入比、受教育水平等, 所以该模型还要不断地进行实验, 逐步改善不足之处。
参考文献
[1]刘华婷郭仁祥等:关联规则挖掘Apriori算法的研究与改进[J].计算机应用与软件, 2009, (1)
C4.5决策树 篇4
决策树作为一种有效的将复杂决策问题简化的决策方法,擅长高效处理大量决策相关信息并得到准确的决策结果[3],并且具有计算量小、可以处理连续和离散数据、能够生产可以理解的规则等优点。奶牛布氏杆菌病风险决策问题涉及的风险因素错综复杂,且涉及处理非数值型数据问题。因此,在目前布氏杆菌病风险难评价、难预测的形势下,将决策树方法应用到奶牛布氏杆菌病风险决策问题中来,具有很好的理论意义和现实意义。南方某省奶牛中发现布氏杆菌病尚属首次,应用决策树进行奶牛布氏杆菌病风险调研分析,对该省的奶牛布氏杆菌病防控具有实践意义。
1 决策树C4.5算法及其原理
1.1 决策树的概念
决策树方法由人工神经网络方法演变而来,是通过树状的逻辑思维方式解决复杂决策问题的一种方法。它认为每个决策或事件(即自然状态)都可能引出两个或多个事件,导致不同的结果,把这种决策分支画成图形,很像一棵树的枝干,故称决策树[4]。决策树由决策节点、分支和叶子几个部分组成[5],它很容易转换为分类规则,从根到每个叶节点的一条路径就对应着一条分类规则。
决策树构树是指从训练集的样本出发,通过决策树算法将整个训练集进行逐层划分,对除终节点外的每个节点选取一个(单变量)或几个(多变量)分类属性以及合适的分类策略进行分类,直至得到的节点中包含的样本属于同一等级的过程,它能够聚焦最适合的因素并进行分类。目前,已形成了多种决策树构树算法,如ID3 、C4.5 、CART 、SPRINT、SLIQ等。其中最著名的算法是Qulnlan提出的ID3 算法、C4.5 算法。
1.2 C4.5算法及其原理
C4.5算法是决策树构树的一种方法,是由ID3 算法演变而来的。C4.5采用信息增益率来选择属性,克服了ID3算法中用信息增益选择属性时偏向选择取值多的属性的不足。C4.5能够在保证训练集分类准确性的前提下构建结构尽可能简单的决策树[6]。其计算原理如下。
1.2.1 信息量大小的度量
1948年,Shannon提出了信息论理论。事件si的信息量I(si)可如下度量:
undefined
其中p(si)表示事件si发生的概率。
假设有n个互不相容的事件s1,s2,s3,…,sn,它们中有且仅有一个发生,则其平均的信息量可如下度量:
undefined
并规定当p(si)=0时,undefined
1.2.2 决策树的信息墒
在决策树分类中,假设S是s个样本数的数据样本集合,假定类标号属性具有m个不同类Ci(i=1,…,m),设si是类Ci中的样本数。对一个给定的样本分类所需的期望信息:
undefined
pi是任意样本属于Ci的概率,pi=si/s。
设属性Q具有v 个不同值{q1,q2,…,qv} ,可以用属性Q将S 划分为v个子集{ S1,S2,…,Sv} 。其中,包含Sj中这样一些样本,它们在Q上具有值qj。如果Q选作测试属性(即最好的分裂属性),则这些子集对应于由包含集合S 的节点生长出来的分支。设sij是Sj中类Ci的样本数,根据由Q划分成子集的熵(entropy)或期望信息为:
undefined
其中undefined项充当第j个子集的权,并且等于子集(即Q值为qj)中的样本个数除以S中样本总数。熵值越小,子集划分的纯度就高。
1.2.3 信息增益和信息增益率 通过测试属性Q划分的信息增益为:
Gain(Q)=I(s1,s2,…,sm)-E(Q) (5)
换言之,Gain(A)是由于获得属性Q的值而导致的熵的期望压缩。
然后,再计算属性A对应的信息增益率:
undefined
通过计算每个属性的信息,选择具有最高信息增益率的属性即是给定集合S中具有最高区分度的属性,将其作为分支结点对集合进行划分, 并由此产生相应的分支结点。
2 奶牛布氏杆菌病风险影响因素
根据规模化奶牛场布氏杆菌病风险评估分级所考虑的范围,通过查阅历史资料、流行病学分析和专家访谈、问卷调查的方法,确定奶牛布氏杆菌病的16个主要风险影响因素,见表1。
依照表1的主要影响因素,结合调研地的奶牛布氏杆菌病发展情况,设计了“奶牛布氏杆菌病风险评估调查问卷表”。根据调研问卷,课题组在南方某省奶牛农场进行实地考察和调研,获取有效调研数据200份,并对调研数据进行信度和效度测试,得出真实可靠的调研数据。
3 奶牛布氏杆菌病风险决策树的构建与评估
3.1 构建初始决策树
采用调研数据,用Weka3.6.6软件的C4.5(J48)算法进行计算,得到奶牛布氏杆菌病初始风险决策树,见图1。
从图1和统计结果可以看出,初始决策树有13个叶节点。 风险判断正确率为86.4%,其中判断阳性正确的有43例, 占76.8%; 阴性正确的有129例,决策树的分层交叉验证和混淆矩阵统计结果如下:
=== 分层交叉验证 ===
分类正确样例数 172 86.432 2 %
分类错误样例数 27 13.567 8 %
=== 混淆矩阵 ===
a b <-- 分类
43 14 | a = 阳性
13 129 | b = 阴性
占90.2%。
3.2 决策树的修剪
由于现实中的问题涉及面较广,初步构建的决策树往往因为包含大量分类属性和分支而比较复杂,难免存在一些错误或误差,即噪音。这些噪音在决策分类过程中逐渐积累放大,最终会使决策树对实际样本的分类出现较大偏差,即过度拟合,造成决策树精确性下降。因此,需要对初步构建的决策树进行修剪和验证,修剪目的在于优化决策树或者简化生成的规则。通常用两种方法进行树枝的修剪,分别为事前修剪(prepruning)和事后修剪(postpruning)。本研究采用事后修剪的方法,其基本思想是首先让决策树充分地生长,然后利用剪枝技术删除不具一般性的枝叶。在这个过程中,用户先指定一个最大的允许错误率或者置信因子,利用检验样本集数据,在决策树不断剪枝的过程中,检验决策树对目标变量预测的准确率,如计算出的错误率高于允许的最大值或者超过置信区间,则立即停止剪枝,否则可以继续剪枝。剪枝后奶牛布氏杆菌病风险决策树见图2。
剪枝后决策树的混淆矩阵统计结果如下:
=== 混淆矩阵 ===
a b <-- 分类
44 13 | a = 阳性
12 130 | b = 阴性
从结果可以看出,剪枝后决策树叶子节点减少到9个,总的判断正确率提高到87.4%,决策树评估见表2。
3.3 决策树的确定和评估
完成构树和验证剪枝过程后,决策树的基本结构就可以确定,下一步需要对决策树的分类精确性和分类效率进行评估。评估指标主要有召回率、准确率和评估值。其计算方法如下:召回率R=NCP/NC;准确率P=NCP/NP;评估值F=2RP/(R+P)。其中:NCP是正确预测奶牛氏杆菌布病情况的记录条数,NC是实际分类结果的记录数,NP是分类器预测奶牛布氏杆菌病情况的记录数。通过试验求得剪枝前后的这3个指标见表3。
从表3的评估结果可以看出,决策树修剪后的正确率和召回率都有所提高,而且系统的性能评估F值也提高了,表明系统的整体分类性能不仅没下降反而提高了,因此修剪决策树是一种优化方案。
4 结论
1)根据C4.5算法构建的最终决策树,可以从16个奶牛布氏杆菌病风险的影响因素中发现,导致南方某省奶牛场布氏杆菌病的最为关键的几个风险影响因素分别为调入混群前是否全部进行布氏杆菌病检测(Q2)、人工授精的精液是否经过布氏杆菌病检测(Q4)、本场/户远离村寨和其他养牛场户独立养殖(Q9)、附近周边农户饲养羊(Q14)、挤奶方式(Q1)、本场内卫生是否定时每周进行打扫和消毒处理(Q10)、产犊场地是否进行严格消毒(Q7)、人工授精时是否用一次性手套(Q5)。
2)利用算法构建的奶牛布氏杆菌病风险决策树,可以对未来该省奶牛布氏杆菌病进行风险预测,并且对训练数据评估,预测的正确率能达到87.4%。
3)可以为奶牛布氏杆菌病的风险分析提供一种科学、简单的风险分析方法:①直接从奶牛布氏杆菌病风险问题所涉及的风险因素和布氏杆菌病阳性或阴性的结果出发,可以得到更符合实际情况的评价结果;②可以将复杂的奶牛布氏杆菌病风险决策问题形成简单、直观的决策过程;③能够聚焦最适合的因素并进行分类,增强奶牛布氏杆菌病风险的决策能力和效率。
5 建议
研究表明,无论是奶牛场还是肉牛场,加强养殖场生物安全措施是预防和控制布氏杆菌病传播的关键因素。加强养殖场生物安全措施,一是要保证调入奶牛全部进行布氏杆菌病检测;二是人工授精的精液要进行布氏杆菌病检测;三是养殖场选址时要与居民点和其他养殖场相互隔离;四是选择恰当的挤奶方式;五是实施严格的程序化消毒和卫生打扫制度;六是人工授精时需佩戴一次性手套。
摘要：为了研究一套科学有效的奶牛布氏杆菌病风险分析和评估方法,试验采用基于决策树C4.5算法的奶牛布氏杆菌病风险分析方法,对南方某省奶牛布氏杆菌病感染区进行实地调研和分析,挖掘奶牛布氏杆菌病的风险影响因素,建立风险决策树,提出了风险管理建议。结果表明:决策树方法是一种科学、简单的风险分析方法,可以准确、快速、有效地进行奶牛布氏杆菌病风险分析和决策。
关键词：奶牛布氏杆菌病,决策树,C4.5,风险分析
参考文献
[1]贺磊,李金平,吕春华,等.阿勒泰地区动物布病疫情风险评估[J].新疆畜牧业,2010(3):25-27.
[2]王功民,池丽娟,马世春,等.我国畜间布鲁氏菌病流行特点及原因分析[J].中国动物检疫,2010,27(7):62-63.
[3]王磊,杨超,卢宝荣.利用决策树方法建立转基因植物环境生物安全评价诊断平台[J].生物多样性,2010,18(3):215-226.
[4]YUAN Y F,SHAW M J.Induction of fuzzy decision trees[J].Fuzzy Sets Systems,1995(9):125-139.
[5]黄晶晶,倪天倪.分类挖掘在大学生智能评估体系中的设计与实现[J].计算机与现代化,2005(3):96-98.