《数据仓库与数据挖掘》(分类规则).docx

第9章分类规则挖掘与预测主要内容 分类与预测的根本概念 决策树方法 分类规则挖掘的ID3算法 其他分类规则挖掘算法 分类规则的评估 微软决策树及其应用训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有指导的学习.如果训练样本的类标号是未知的，则称为无指导的学习(聚类)学习模型可用分类规则、决策树和数学公式的形式给出.第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类。（八）学习(b)分类图9-1数据分类过程2.常用的分类规则挖掘方法分类规则挖掘有着广泛的应用前景.对于分类规典J的挖掘通常有以下几种方法，不同的方法适用于不同特性的所有值按比例缩放，使其落入指定的区间.5.分类方法的评估标准 准确率：模型正确预测新数据类标号的能力. 速度:产生和使用模型花费的时间e 健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力. 伸缩性：对于给定的大量数据，有效地构造模型的能力。 可解狎性，学习模型提供的理解和观察的层次。9.2决策树方法决策树方法的起源是概念学习系统C1.S,然后开展到由QUiU1.an研制ID3方法，然后到著名的C4.5算法，C4.5算法的一个优点是它能够处理连续属性。还有CART算法和Assistant算法也是比较有名的决策树方法。1 .什么是决策树决策树(DecisionTree)又称为判定树，是运用于分类的一种树结构。其中的每个内部结点(interna1.node)代表对某个属性的一次测试，每条边代表一个测试结果，叶结点(Ieaf)代表某个类(CIaSS)或者类的分布(c1.assdistribution),最上面的结点是根结点.决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法.下例是为了解决这个问题而建立的一棵决策树，从中可以看到决策树的根本组成局部I决策结点、分支和叶结点.K例X图9-2给出了一个商业上使用的决策树的例子.它表示了一个关心电子产品的用户是否会购置PC（buys,co三puter）的知识，用它可以预测某条记录（某个人）的购置意向。图9-2buys_c(xnputer的决策树这棵决策树对侑售记录进行分类，指出一个电子产品消费者是否会购量一台计算机-puter*.每个内部结点（方形框）代表对某个属性的一次检测.每个叶结点（椭圆框）代表一个类，buys-computers=yes或者buys-co<puters=no在这个例子中，样本向量为I(age,student,Credit.rating;buys_computers)被决策数据的格式为：(age,student,credit_rating)输入新的被决策的记录，可以预测该记录隶属于哪个类.2 .使用决策树进行分类构造决策树是采用自上而下的递归构造方法.以多叉树为例，如果一个训练数据集中的数据有几种属性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各个子集。反之，则作为叶结点。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据.二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为（a=b）的逻辑判断，其中a是属性，b是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记.使用决策树进行分类分为两步： 第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程. 第2步：利用生成完毕的决策树对输入数据进行分类.对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。问题的关键是建立一棵决策树。这个过程通常分为两个阶段： 建树(TreeBui1.ding)：决策树建树算法见下，可以看得出，这是一个递归的过程，最终将得到一棵树. 剪枝(TreePruning)：剪枝是目的是降低由于训练集存在噪声而产生的起伏.9.3分类规则挖掘的ID3算法由Quin1.an在80年代中期提出的ID3算法是分类规则挖掘算法中最有影响的算法.ID3即决策树归纳(InductionofDecisionTree).早期的ID算法只能就两类数据进行挖掘(如正类和反类)；经过改良后，现在ID算法可以挖掘多类数据。待挖掘的数据必须是不矛盾的、一致的，也就是说，对具有相同属性的数据，其对应的类必须是唯一的。在ID3算法挖掘后，分类规则由决策树来表示。1.ID3算法的根本思想由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间，该搜索空间是针对某一特定问题而提出的。系统根据某个评价函数决定搜索空间中的哪一个决策树是“最好”的。评价函数一般依据分类的准确度和树的大小来决定决策树的质量.如果两棵决策树都能准确地在测试集进行分类，则选择较简单的那棵。相对而言，决策树越简单，则它对未知数据的预测性能越佳。寻找一棵“最好”的决策树是一个NP完全问题.ID3使用一种自顶向下的方法在局部搜索空间创立决策树，同时保证找到一棵简单的决策树一可能不是最简单的。ID3算法的根本思想描述如下：step1.任意选取一个属性作为决策树的根结点，然后就这个属性所有的取值创立树的分支；step2.用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例都属于同一类，则以该类为标记标识此叶结点：如果所有的叶结点都有类标记，则算法终止；step3.否则，选取一个从该结点到根路径中没有出现过的属性为标记标识该结点，然后就这个属性所有的取值继续创立树的分支：重复算法步骤step2：这个算法一定可以创立一棵基于训练数据集的正确的决策树，然而，这棵决策树不一定是筒单的。显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树.在ID3算法中，采用了一种基于信息的启发式的方法来决定如何选取属性.启发式方法选取具有最高信息量的属性，也就是说,生成最少分支决策树的那个属性。2.ID3算法的描述算法：Generate_decision_tree由给定的训练数据产生一棵决策树输入：训练数据集SainPIes,用离散值属性表示；候选属性的集合attributeist。输出：一棵决策树方法：(1)创立结点N；(2)ifsamp1.es都在同一个类Cthen(3)返回N作为叶结点，用类C标记；(4)ifattribute_1.ist为空then(5)返回N作为叶结点，标记SaInPIeS中最普通的类；多数表决设S是有S个训练样本数据的集合，类标号属性具有m个不同值，定义m个不同类CiG=I,2,m),si是类Ci中的样本数，则对一个给定的训练样本分类所需要的期望信息为：I(S1,sb,sj=-"1pi1.ogs(pi)其中Pi是任意样本属于Ci的概率，可用si/s来估计.设属性A具有k个不同值a1.,a2,ak,则可用属性A将S划分为k个子集S1,S2,Sk,Sj中包含的样本在属性A上具有值aj如果选择A作为测试属性，则这些子集对应于由包含集合S的结点生长出来的分枝.设SIJ是子集Sj中类Ci的样本数，则按照A划分成子集的炳为：E（八）="1-1(sj+S2J+S*j)ZSiJ)I(S1,St,SB)信息增益(InformationGain),表示系统由于分类获得的信息量.由系统烯的减少值定量描述.用属性A分类后的信息增益为IGain（八）=I(s,sit,sj-E（八）炳是一个衡量系统混乱程度的统计量。嬉越大，表示系统是混乱。分类的目的是提取系统信息，使系统向更加有序、有规则组织的方向开展.所以自然而然的，最正确的分裂方案是使烟减少量最大的分裂方案.炳减少量就是InformationGain,所以，量正确分裂就是使Gain（八）最大的分裂方案。通常，这个最正确方案是用“贪心算法+深度优先搜索得到的.因为这是一个递归过程，所以仅仅需要讨论对某个特定结点N的分裂方法.(1)分裂前设指向N的训练集为S,其中包含m个不同的类，它们区分了不同的类G(fori=1.,，三).设&是S中属于类G的记录的个数那么分裂之前，系统的总烯，I(Si,S1,Sa)=-mPiIog1(Pi)容易看出，总篇是属于各个类的记录的信息量的加权平均.(2)分裂后现在属性A是带有k个不同值的属性为,ak,A可以把S分成k个子集SbS1,SJ其中&=xIX£S&x.A=aj如果A被选为测试属性，那么那些子集表示从代表集合S的出发的所有树枝。设而表示在SJ中类为G的记录个数。那么，这时按A的每个属性值(更一般的是取A的一个子集)进行分裂后的信息量，也就是系统总熠为：E（八）=kM(sij+stj+.÷Smj)s)*I(s+s+.+smj)(sij+sw+.+%)s)表示第j个子集的权重，s=ISI.子集Sj的信息量(子集的总烯I(s+s+.+)=-"三pu1.oga(pu)总墙E（八）是各个子集信息量的加权平均。算法计算每个属性的信息增益，具有最高信息增益的属性选择作为给定训练数据集合S的测试属性.创立一个结点，并以该属性为标记，对属性的每一个值创立分枝，并据此划分样本.K例X顾客数据库训练数据集如下表所示：RIDageincomestudentcredit.ratingC1.ass:Buys_conputer1<=30highnofairno2<=30highnoexce1.1.entno331-40highnofairyes4>40mediumnofairyes5>401.owyesfairyes6>40Iovyesexce1.1.entno731401.owyesexce1.1.entyes如果在测试集中出现了某些错误的实例，也就是说，在待挖掘的数据中，本来应该属于同一结点的数据因为某些错误的属性取值而继续分支.则在最终生成的决策树中可能出现分支过细和错误分类的现象。ID3设置了一个阈值来解决这个问题：只有属性的信息量超过这个阈值时才创立分支，否则以类标志标识该结点.该阈值的选取对决策树的正确创立具有相当的重要性.如果阈值过小，可能没有发挥应有的作用：如果阈值过大，又可能删除了应该创立的分支。4.由决策树提取分类规则可以提取由决策树表示的分类规则，并以IF-THEN的形式表示。具体方法是：从根结点到叶结点的每一条路径创立一条分类规则，路径上的每一个“属性一值.对为规则的前件（即IF局部）的一个合取项，叶结点为规则的后件（即THEN局部）R例对于buys-co三puter的决策树可提取以下分类规则:IFage=*<=30,ANDstudent='no'THENbuys_computer='noIFage='<=30'ANDstudent='yes'THENbuys-conputer=*yes(2)属性选择度量ID3算法中采用信息增量作为属性选择度量，但它仅适合于具有许多值的属性.已经提出了一些其他的属性选择度量方法，如增益率，它考虑了每个属性的概率.(3) 空缺值处理常用的空缺值处理方法有：若属性A有空缺值，则可用A的最常见值、平均值、样本平均值等填充。(4) 碎片、重复和复制处理通过反复地将数据划分为越来越小的局部，决策树归纳可能面临碎片、重复和复制等问题。所谓碎片是指在一个给定的分枝中的样本数太少，从而失去统计意义。解决的方法是：将分类属性值分组，决策树结点可以测试一个属性值是否属于给定的集合。另一种方法是创立二叉判定树，在树的结点上进行属性的布尔测试，从而可以减少碎片.当一个属性沿树的一个给定的分枝重复测试时，将出现重复.复制是拷贝树中已经存在的子树.通过由给定的属性构造新的属性(即属性构造)，可以防止以上问题的发生.(5) .可伸缩性ID3算法对于相对较小的训练数据集是有效的，但对于现实世界中数据量很大的数据挖掘，有效性和可伸缩性将成为必须关注的问题。面临数以百万计的训练数据集，需要频繁地将训练数据在主存和高速缓存换进换出，从而使算法的性能变得低下。解决的方法是，将训练数据集划分为子集，使得每个子集能够放在内存；然后由每个子集构造一棵决策树；最后，将每个子集得到的分类规则组合起来，得到输出的分类规则.最近，已经提出了一些强调可伸缩性的决策树算法，如：S1.IQ.SPRINT等。这两种算法都使用了预排序技术，并采用了新的数据结构，以利于构造决策树.ID3算法对大局部数据集有效，但它不能挖掘域知识.同时，决策树在计算机中存储的方式决定了该分类规则相对于其他形式的分类规则（如公式）而言更晦涩难怪.因此，一般在算法结束后，需要把决策树以用户可视的方法显示出来。R例以下表所示的训练数据集为例，其中Sa1.ary为工资，Education为教育程度，CIaSS为信用级别。假设以20,000作为Sa1.ary的分段值，则创立的决策树如图9-3所示；假设以16,000作为Sa1.ary的分段值,则创立的决策树如图9-4所示.Sa1.aryEducationC1.ass10,000高中一般40,000学士较好15,000学士一般75,000硕士较好18,000硕士较好训练数据集T的准确性。9.4分类规则挖掘的其他算法9. 4.1分类规则挖掘的C4.5算法1. C4.5算法概述C4.5算法是ID3算法的扩展，但是它比ID3算法改良的局部是它能够处理连续型的属性.首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各个属性Gian值的大小.2. ”离散化"的方法把连续型属性值.离散化”的具体方法是：D寻找该连续型属性的最小值，并把它赋值给MIN,寻找该连续型属性的最大值，并把它赋值给MAX：2)设置区间MIN,MAX中的N个等分断点Ai,它们分别是Ai=MIN+(MAX-MIN)/N)*i其中，i=1,2,N3)分别计算把DnN,Ai和(Ai,MAX)(i=1,2,.tN)作为区间值时的Gain值，并进行比较4)选取Gain值最大的Ak做为该连续型属性的断点，把属性值设置为DnN,Ak和(Ak,MAX)两个区间值.3. Gain函数决策树是建立在信息理论(InfOmationTheO1.y)的基础上的，决策树的方法循环地寻找某一标准，它能够带来与本次分类相关的最大信息。构造好的决策树的关健在于如何选择好的属性。对于同样一组记录集，可以有很多决策树能符合这组记录集。人们研究出，一般情况下，树越小则树的预测能力越强.要构造尽可能小的决策树，关键在于选择恰当属性。属性选择依赖于各种对例子子集的不纯度(impurity)度量方法。不纯度度量方法包括信息增益(infornatingain)%信息增益比(gainratio)、Gini-index、距离度量(distancemeasure)、J-measureG统计、x2统计、证据权直(weightofevidence)-,最小描述长(M1.P)、正交法(Ortogona1.ityBasure)相关度(re1.evance)和Re1.ief.不同的度量有不同的效果，特别是对于多值属性.C4.5算法使用信息增益(informationgain)的概念来构造决策树，其中每个分类的决定都与前面所选择的目标分类有关.(1)信息理论(Inforn1.ationTheory)和熔(Entropy)考虑一个任意的变量，它有两个不同的值A和B。假设这个变量不同值的概率分配，将估测该概率分配的不纯度。情况1.如果P（八）=I和P(B)=0,那么知道这个变量的值一定为A,不存在不纯度，因此变量结果值不会带来任何的信息。情况2.如果P（八）=P(B)=0.5,那么它的不纯度明显地高于P（八）=O.1和P(B)=0.9的情况.在这种情况下,变量的结果值就会携带信息.不纯度的最正确评估方法是平均信息量，也就是信息情(Entropy)：S=-(piIog(Pi)在上面的例子中，情况1和情况2的信息熔分别是：S1.=-(11.og1+01.og0)=0S2=-(0.51.og0.5+0.51.og0.5)=0.301(2)信息增益(informationgain)信息增益是指信息烯的有效减少量(通常用"字节"衡量)，根据它能够确定在什么样的层次上选择什么样的变量来分类。4. .C4.5算法描述FunctionC4.5(R:asetofnon-goa1.attributesso<neofwhichwithcontinuousva1.ues,C:thegoa1.attribute,S:atrainingset)returnsadecisiontree;beginIfSisemptythenreturnasing1.enodewithva1.ueFai1.ure;IfSconsistsofrerdsa1.1.withthesameva1.ueforthegoa1.attributethenreturnasing1.enodewiththatva1.ue;IfRisemptythenreturnasing1.enodewithasva1.uethemostfrequentoftheva1.uesofthegoa1.attributethatarefoundinrecordsofS;notethatthentherewi1.1.beerrors,thatis,recordsthatwi1.1.beimproper1.yc1.assified;fora1.1.attributesofR(Ri)doifva1.uesofRiarecontinuousthenbegin1.etA1.betheDiniiiumofRi;1.etAmbethemaxinumofRi；m值手工设置forjfrom2to11r1.doAj=A1.+j*(A1.-Am)/m;1.etAbetheva1.uepointofRiwith1.argestGain(Ri,S)basedon<=Aj,>Aj);end;1.etDbetheattributewith1.argestGain(D,S)amongattributesinR;1.etdjIj=1.,2,mbetheva1.uesofattributeD;1.etSjIj=1.,2,.,mbethesubsetsofSconsisting化后的搜索空间中的每一个元组(记录)可以看作是一个口+1维向量d,%c),其中“(1im)对应于第i个实数类型的条件属性，c对应于决策属性(元组的类)所有的条件属性可以看作是一个三维向量(V,v,-.vn,)工定义】*是一个n维欧几里得空间，设PWR"且”0,bG史,则集合1.tp=Axe称为*中的一个超平面(n4).(当n=2时，集合确定一条直线：当n=3时，集合确定一个平面.)K定义】一个超平面将*'分成两个半空间，记为HYA/=(UIAw和H-(Ab)=(U1.AUM6).其中(A.加是/T中满足AUA的向量U构成的半空间，”(A.%)是*中满足AUa的向量U构成的半空间。R定义】一组单位向量(1.0,0,0),(0,1,0,，0),，(0,0,0,，1)是个中的一组基，用符号"，42,C”来表示该组单位向量。K定义】设r是一个超平面，如果p=1；(Yi«)，则是一个轴平行超平面，否则r是一个斜面超平面。K引理】ID3决策树的每一个结点等价于一个轴平行超平面。(证明略)大局部决策树都是在每一个结点检杳某个属性的值，或者对该数值属性进行分段检查.因此，称这种决策树为“轴平行.决策树.K定理】用超平面把一组n个的d维向:分成两个半空间，如果nd+1则存在"Z(k')种方法；如果nd+1则存在2种方法。(证明略)2.OC1.算法的根本思想根据以上定理，最多存在有限种不同的决策树从理论上可以采用一种穷举的方法来寻找一棵最优决策树，但在实际中这是不可行的算法.如前所述，寻找一棵最优决策树是一个NP完全问题.寻找一棵斜面超平面决策树也是一个NP完全问题。因此，用OCI算法只能找到一棵比较小的决策树，但不一定找到一棵最小的决策树。OC1.算法构建一棵斜面超平面决策树，其根本思想是：采用自顶向下的方法从条件属性都是正实数类型的搜索空间开始创立斜面决策树。如果搜索空间都属于同一类，则算法终止，否则，在搜索空间中寻找一个“最正确.划分搜索空间的斜面超平面，以此斜面超平面标识当前结点，把搜索空间分成两个半空间搜索空间（左子树和右子树）。反复在每个半空间搜索空间继续寻找“最正确"斜面超平面直至算法终止.3.1. OC1.算法描述step1.就当前搜索空间创立决策树的根结点，该结点的斜面超平面把搜索空间分为左半空间和右半空间；step2.用这棵树来对搜索空间进行分类，如果一个半空间的所有实例都属于同一类，则以该类为标记标织此半空间；如果所有的半空间都有类标记，则算法终止；step3.否则，分别以左半空间和右半空间为搜索空间，继续创立根结点的左子树和右子树；星复算法步骤step1.OC1.算法在每一个决策树结点处的算法描述如下：/*寻找当前搜索空间的“最正确"斜面超平面参数*/step1.寻找当前搜索空间的“最正确”轴平行超平面计算该轴平行超平面区的纯洁度小step2.随机选择一个斜面超平面令“最正确.斜面超平面（等于该斜面超平面计算该斜面超平面名的纯洁度小step3.重复R次以下步骤：step3.1：重复执行依次振荡斜面超平面%的系数：直到纯洁度没有进一步改良：step3.2：重复最多J次选择一个随机方向，以该随机方向改变斜面超平面MN如果改变后的斜面超平面纯洁度/,得到改良，转到步骤1.)step3.3：如果斜面超平面儿的纯洁度/“小于“最正确.轴平行超平面/的纯洁度小令I=小否则令I=t,Istep4.输出纯洁度I对应的超平面.根据OC1.算法描述可以看出，最重要的算法实现方式包括：(1)在决策数的每一个结点处如何生成一个斜面超平面H。、(2)计算超平面纯洁度的方法；4.OC1.算法的改良(1) OC1.算法改良的根本思想OC1.算法采用自顶向下的方法在条件属性都是正实数类型的搜索空间创立斜面决策树，如果条件属性是符号型则不能适用该算法.关于符号型条件属性的问题，很容易想到的解决方法就是将其对应到正实数类型上,再在其上采用OCI算法挖掘分类规则.如对条件属性“性别.，符号“男”对应"1",符号“女对应“2.针对不同的条件属性，可以创立不同的编码表，从而使OC1.算法适用于符号型条件属性的分类规则挖掘但是这样创立的编码表具有很强的随意性和主观性，不能真正反应数据的真实状况e如在搜索空间T中，条件属性"性别”为”男.的实例占了97%,而为“女”的实例只有3%,假设在编码表中符号“男.对应的编码为«1000*,符号“女”对应的编码为“2000*,根据斜面超平面方程EQ”，把实例了,代入方程£。“，可以得到表达式Z)+%1.匕。显然，尽管性别为“女”的实例在搜索空间的比例很小，但由于其对应的编码远远大于性别为“男”的实例，因此”的的取值只能在很小的范围振荡，从而影响进一步选择“最正确"斜面超平面.为了解决这个问题，可采用了一种基于分布的编码方式。首先，扫描整个搜索空间(实例集)，得到所有条件属性为符号型的离散数据，创立编码表，计算每个离散数据在该搜索空间出现的频率。根据每个符号对应的概率创立编码表，可以有效地解决上文中所提出的问题.(2) OC1.改良算法的描述该局部的算法描述如下：step1.扫描搜索空间；step2.统计每一个符号属性出现的次数；step3.计算每一个符号属性的概率分布值Istep4.生成编码表I（3）结果分析下表给出了OC1.算法和改良的OCI算法在同一个搜索空间，同样的随机改良系数（随机跳跃次数5）,同样的振荡次数（20）下搜索的正确率比较分析。该搜索空间是基于塔斯马尼亚州大学计算机科学系捐赠的塔斯马尼亚州（澳大利亚州名）基础工业渔业部的鲍鱼数据库的数据仓库的一个采样切片。由根据表可以看出，改良的OC1.算法在同样的搜索空间和一样的搜索系数情况下，决策树的正确度无论是从平均值、最大值还是最小值进行比较，都远远高于原算法，大大增强了决策树（分类规则）的正确性和可预测性.次数OC1.算法OC1.改良算法第一次0.760.84第二次0.700.77第三次0.660.80第四次0.730.78第五次0.690.78平均值0.7080.794最大值0.760.84最小值0.660.77表OCI算法和OC1.改良算法的比较9.4.4分类规则挖掘的S1.IQ算法1. S1.1.Q算法概述S1.IQ快速可伸缩算法（SUperViSed1.earningInQuest,其中QUeSt是IBMA1.Inaden研究中心的数据挖掘工程）是IBMA1.madenResearchCenter于1996年提出的一种高速可调节的数据挖掘分类算法.该算法通过预排序技术，着重解决当训练集数据量巨大，无法全部放入内存时，如何高速准确地生成决策树。能同时处理禽散字段和连续字段。S1.IQ的优点，（1）运算速度快，对属性值只作一次排序。（2）利用整个训练集的所有数据，不做取样处理，不丧失精确度。（3）轻松处理磁盘常驻的大型训练集，适合处理数据仓库的海量历史数据.（4）更快的，更小的目标树.（5）低代价的MD1.剪枝算法2. S1.IQ算法的关键技术（1）可伸缩性指标一般决策树中，使用信息量作为评价结点分裂质量的参数。S1.IQ算法中，使用gini指标（giniindex）代替信息量（Information）,gini指标比信息量性能更好，且计算方便.对数据集包含n个类的数据集S,gini（三）定义为Igini（三）=1-pj*pjPJ是S中第j类数据的频率gini越小，InformationGain越大.（2）属性的分裂方法区别于一般的决策树，S1.IQ采用二分查找树结构.对每个结点都需要先计算最正确分裂方案，然后执行分裂对于数值型连续字段(numericattribute)分裂的形式A<=v.所以，可以先对数值型字段排序，假设排序后的结果为V”v，v,因为分裂只会发生在两个结点之间，所以有n-1种可能性。通常取中点(v,+v,G/2作为分裂点.从小到大依次取不同的sp1.itpoint,取InformationGain指标最大(gini最小)的一个就是分裂点。因为每个结点都需要排序，所以这项操作的代价极大，降低排序本钱成为一个重要的问题，S1.IQ算法对排序有很好的解决方案，在后面对算法的描述中，将很详细的看到这一点.对于离散型字段(CategoriCaIattribute),设S（八）为A的所有可能的值，分裂测试将要取遍S的所有子集S'.寻找当分裂成S'和S-S'两块时的gini指标，取到gini最小的时候，就是最正确分裂方法。显然，这是一个对集合S的所有子集进行遍历的过程，共需要计算2次，代价也是很大的.S1.1.Q算法对此也有一定程度的优化。(3)剪枝SiJQ的剪枝算法MD1.属于后剪枝(POS-PrUnning)3.1.1.2算法.通常的后剪枝的数据源采用一个TrainingSet的一个子集或者与TrainingSet独立的数据集进行操作.3. 算法描述输入数据：训练集，配置信息(决策树大小)；输出数据：用线性表方式表示的二叉决策树.算法：Createnode(rt);Preparefordataofattribute1.istandc1.ass1.ist;数据准备Enterqueue(rt);算法的控制结构是一个队列，该队列存放当前的所有叶结点Whi1.e(note11ty(queue)doEva1.uateSp1.its0；计算最正确分裂fora1.1.the1.eafnodesinthequeuedoUpdate1.abe1.sO;升级结点(创立子结点、执行结点分裂)C1.eanthenevinterna1.nodeandthepure1.eafnodeoutofthequeue;对应该分裂的类表进行更改1.etthenew1.eafnodeenterthequeue;MD1.pruning(rt);利用MD1.算法进行剪枝图9-3计算分裂指标的例子一一当前待分裂属性Sa1.ary,右边为C1.aSShiStOgrai1.的变化过程属性表从上往下扫描,叶队列里面的结点有N2,N3.N3转为内部结点.图9-5执行结点分裂的例子一一结点N3分裂成N6、N7,9.4. 5CART算法1. CART算法概述CART算法可用来自动探费出高度复杂数据的潜在结构，重要模式和关系.这种探窝出的知识又可用来构造精确和可靠的81测模型,应用于分类客户、准确直邮、侦测通信卡及信用卡作和管理信用风险.技术上讲，CART技术可称为二元回归分化技术.因为根结点总是被分为两个子结点并不断分化，故称为二元回归.CART分析的技术要点包括一系列规则，可用于，(1)分裂树点(2)确定何时结束分裂(3)为每一叶结点指定类型或流值2. CART算法的分裂规则的选择将一个结点分化成两个子结点，CART总是问些“是”或“非，的问题.来分化根结点成二个子结点，以“是,为答爱的案例归入左子树结点，而否.为答爱的案例归为右子树结点.工例贷款申请中风险分析.有训练集包含WO个高风险和100个低风险的流试案例，构造一棵二叉树如图1所示：B9-贷欧风龄分析对于上图中所得到的二叉树，CART算法先检验分析中所有变量可生出的所有分裂，再选其优者.如上图中有200个案例，假设每个案例都有10个相关的数据变量，那么CART算法要比较200X10即2000种分裂的可能。接下来帚要根据分裂质量标准来评估每一个分化。最常用的一个标准是GINI标准，根本原则是根据该分化是否有效地分隔几个类别。除了GINI标准外，还可以用Twoing标准和规则Twoing标准。其中GINI标准在树成长时明显地包括费用信息，而Twoing标准和规则Twoing标准则在计算风险和结点分配时使用费用，或者把费用信息合并入先验以应用到模型.为了更有效地处理数据类型的选择，也可以运用连续自变变量的线性组合来作为分化的基础。通过质，标准评估每一个分化后，要选取一个最正确分化来构建决策树，并继续对每一个子结点重复进行“搜索和分化.的过程，直到进一步的分化不可能继续。不能继续的情况如：某个树点包含完全一致的案例，则无法进一步分化；一个结点包含太少案例时，也会停止分化。(一般取10为标准，少于10即为太少)当决策树构建完成后，需要要对决策树的终结点的案例进行分类.一种最值单的分类方法就是对数原则，即用数量最多的种类来确定分类.如上图的决策树，假设它已经构建完成，那么按多数原则，就确定左结点为低风险类，右结点为高风险类.3. CART算法的实现(1)以贷款申请中的风险分析为例，先确定一个训练集，如以100个高风险和100个低风险的数据集为训练集.假设每条客户记录有字段：姓名(Char)、年收入(MOn”)、1»(Int),籍贯(Char)、是否为高负债(Boo1).(为了举例字段的典型性，所以列举了上述这些字段，实际情况肯定不止这些字段，不过这些字段根相HE了在规则分化中要考虑的情况.)(2)根据训练集中的字段及每个案例在该字段上的取值，按顺序扫描训练集，并记录结果.a. 对于类型为数字型的字段，如DateTiae.Int,F1.oat、Money等，只要依次取每条记录的该字段的取值，然后按是否大于该值来扫描训练集.建立一个表来记录结果，基于数据阵中的数据一致性、减少数据冗余及方便后面对这个记录的操作，可以建立如下的表格tb_Resu1.t来存放靖果.序号Resu1.t1.(int)Resu1.t2(int)1234其中序号字段每次从1开始编号，添加一条记录，则序号加1.Resu1.t1.用来记录扫描时判断为“是”的高风险的案例数，如在扫描数字型字段时就记录大于扫描值的高风险案例的数目；在扫描字符型数据时就用来记录在该字段上的字符串与扫描字符串相同的高风险的记录数；在扫描布尔型数据时，用来记录取值为“是”的高风险案例数目,Resu1.t2用来记录扫描时判断为“是,的低风险的案例数.用序号字段，而不直接用扫描字段来记录，是为了实现表的重用，节省数据库开支，这样在扫描所存的字段的时候都可以共用这个表来记录结果，而不必因为字段不同及字段类型的不同而要设计不同的表来记录结果.由于每次使用tb_Resu1.t的时候，序号都是从1开始编号的，所以tb_Resu1.t中的记录结果是与训练集中的记录一一对应的，只要根据序号的对应关系，能够很方便的获得tb_Resu1.t表中的某条记录对应分化规则.如下列图：tb_Resu1.t«序号Resu1.t1.Resu1.t2332765训练集，序号姓名年收入工龄籍贯高负债高风险33一张三120008上海否否-J假设现在的扫描字段为工龄字段，那么表tb_Resu1.t中对应的扫描规则即为：工龄8年，表tb_Resu1.t中ResUIt1.字段的值27表示：工龄8年且为高风险的案例数；Resu1.t2字段的值66表示：工龄8且为低风险的案例数；而用总的高风险案例数10027=73即为,工龄8年且为高风险的案例用总的低风险案例数100-65=35即为:工龄8年且为低风险的案例数可见这样设计表tb.Resu1.t能降低数据冗余度，保持数据一致性，降低数据库开销(不用设计多个表来保存扫描结果)，而且掾作方便.b. 对于类型为字符串型的字段，只要依次取每条记录的该字段的取值，然后扫描训练集进行字符串的匹配，对于完全匹配的记录以答复为“是,的情况进行记录.