《数据仓库与数据挖掘》(分类规则).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有空