基于规则的分类PPT.ppt

,2,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,计算机应用技术,基于规则的分类,1,2025/2/6 周四,目录,第一章 绪论,1.1,基本概念,1.2,研究背景和意义,1.3,国内外研究现状,第二章 构造分类规则的主要算法及流程,2.1,算法简介,2.2,规则质量度量,2.3,规则剪枝,第三章 主要算法举例及程序实现,3.1,直接法,-FOIL,3.2,间接法,由决策树提取分类规则,2,2025/2/6 周四,基于规则的分类法是使用一组,“IFTHEN”,规则来对记录进行分类的技术。,一个,IF-THEN,规则是一个如下形式的表达式：,IF,条件,THEN,结论。规则,R1,是一个例子,R1,：,IF age=youth AND student=yes THEN buys_computer=yes,规则的“,IF,”部分（或左部）称为,规则前件或前提,。“,THEN,”部分（或右部）是规则的,结论或后件,。规则前件，它是属性测试的合取：,IF,其中（,Aj,Vj,）是属性,-,值对，,op,是比较运算符，取自集合,（例如，,age=youth,和,student=yes,）。规则的结论包含一个类预测（在这个例子中，预测顾客是否购买计算机）。,R1,也可以写作,基本概念,3,2025/2/6 周四,基本概念,对于给定的元组，如果规则前件中的条件（即所有属性测试）都成立，则我们说规则前件,被满足,，并且规则,覆盖,了该元组。,规则,R,可以用它的覆盖率和准确率来评估。给定类标记的数据集,D,中的一个元组,X,，设,n,covers,为规则,R,覆盖的元组，,n,correct,为,R,正确分类的元组，,|D|,是,D,中的元组数。可以将,R,的,覆盖率,和,准确率,定义为,也就是说，规则的覆盖率是规则覆盖（即其属性值使得规则的前件为真）的元组的百分比。对于规则的准确率，考察在它覆盖的元组中，可以被规则正确分类的元组所占的百分比。,4,2025/2/6 周四,规则覆盖率和准确率举例,序号,名字,体温,表皮覆盖,胎生,水生动物,飞行动物,有腿,冬眠,类标号,1,人类,恒温,毛发,是,否,否,是,否,哺乳类,2,蟒蛇,冷血,鳞片,否,否,否,否,是,爬行类,3,鲑鱼,冷血,鳞片,否,是,否,否,否,鱼类,4,鲸,恒温,毛发,是,是,否,否,否,哺乳类,5,青蛙,冷血,无,否,半,否,是,是,两栖类,6,巨蜥,冷血,鳞片,否,否,否,是,否,爬行类,7,蝙蝠,恒温,毛发,是,否,是,是,是,哺乳类,8,鸽子,恒温,羽毛,否,否,是,是,否,鸟类,9,猫,恒温,软毛,是,否,否,是,否,哺乳类,10,虹鳉,冷血,鳞片,是,是,否,否,否,鱼类,11,美洲鳄,冷血,鳞片,否,半,否,是,否,爬行类,12,企鹅,恒温,羽毛,否,半,否,是,否,鸟类,13,豪猪,恒温,刚毛,是,否,否,是,是,哺乳类,14,鳗鲡,冷血,鳞片,否,是,否,否,否,鱼类,15,蝾螈,冷血,无,否,半,否,是,是,两栖类,5,2025/2/6 周四,规则覆盖率和准确率举例（续）,规则：（胎生=是）（体温=恒温）哺乳类,Coverage=,n,covers,/|D|=5/15*100%=33%,Accuracy=,n,correct,/,n,covers,=5/5*100%=100%,6,2025/2/6 周四,基于规则的分类器的特征,Mutually exclusive rules(,互斥规则,),Classifier contains mutually exclusive rules if the rules are independent of each other,如果规则彼此独立，则分类器包含互斥规则,Every record is covered by at most one rule,每个纪录都由最多一个规则所覆盖,Exhaustive rules,（穷举规则）,Classifier has exhaustive coverage if it accounts for every possible combination of attribute values,如果分类器考虑到属性值的每一个可能的组合，都将进行详尽的覆盖,Each record is covered by at least one rule,每条记录至少包含一条规则,Some algorithms not always achieve these two properties,7,2025/2/6 周四,研究背景和意义,研究背景,数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘广泛应用于各种领域，比如电力系统的电力负荷预测、证券分析、网络入侵、网络信息的搜索引擎、以及生物医学等等。当前主流的数据挖掘方法主要包括关联规则、分类、聚类。分类是根据已知类别信息寻找数据间的分类模式；分类作为数据挖掘的重要的任务之一，将在未来的智能系统中发挥重要作用。目前，常用的分类主要包括基于规则的分类技术（包括决策树分类、,FOIL,分类算法、关联分类）、贝叶斯分类、,K-,近邻分类、基于软计算的分类和粗糙集等,。,8,2025/2/6 周四,研究背景和意义,研究意义,基于规则的分类方法主要包括传统的基于规则分类方法（决策树，,FOIL,算法）等。决策树分类是典型的递归构造，它的分类模型简洁且易于理解，但当数据集的实例个数较多时，产生的决策树非常大，需要简化决策树。而且数据集中属性值的遗失情况和类分布均匀性对决策树的分类效果产生较大的影响，此外决策树是采用贪婪的算法，很难获得全局的信息，决策树上每条训练实例仅被一条分类规则覆盖，这也是决策树准确率不高的一个原因。,FOIL,算法只用最好的属性值产生的规则来构造分类器，且一条训练实例只被一条规则覆盖，因此当数据集特别小时，可能产生的规则特别少，对分类准确率有一定的影响；关联规则挖掘的分类技术是目前非常流行的而且也收到了广泛的关注，从总体上来说，关联分类的分类准确率要显著的高于传统的基于规则分类方法，比如,FOIL,算法，决策树等，但同时，关联分类也存在一些不足之处，例如，规则产生的过程中生成太多的冗余规则，导致效率不高，分类模型难以理解等问题。,9,2025/2/6 周四,国内外研究现状,FOIL,算法首次由,Quinlan,在,1993,年提出，该算法分为正例和负例提取规则，,FOIL,算法采用信息增益来提取最好的一个属性值来生成规则，而且一次只生成一条规则，再生成规则之后，将被规则覆盖的训练集删除，继续从剩余的训练集中寻找最好的属性值。该方法有效的减少了冗余的规则，然而每条训练集仅被一条规则覆盖，因此在分类的时候准确率不是很高，特别是当训练集较小的时候。,Yin,等人针对该问题提出了新的分类算法,CPAR,，在规则生成阶段，,CPAR,避免了一次只选择一个最好属性值的方法，因为通常有很多属性值的信息增益都很接近最好属性值的信息增益，因此,CPAR,将接近那些信息增益接近最好属性值的信息增益的属性值都用来生成规则，这样就同时生成好几条规则。在删除训练集时，,CPAR,也采用了权重的方法，每条训练实例只要被规则覆盖一次就赋给一个权重，当训练实例的权重达到一定程度时才会被删除，因此也保证了每条训练实例不只被覆盖一次。通过这样，,CPAR,取得了比,FOIL,算法较高的准确率。,10,2025/2/6 周四,国内外研究现状（续）,经典的分类方法之一就是决策树算法。决策树采用树的结构来构建分类模型，类标签为树的叶子节点，某个属性的分割为中间节点，该节点的分枝对应分割属性的一个取值。决策树提供了一种根据不同情况,(Case),采取对应决策的方法。因此，决策树分类模型易于理解，而且决策树能用于预测。,Quinlan,提出了最早的决策树方法即基于信息熵的,ID3,算法。后来，,Ouinlan,对,ID3,作进一步扩展，提出,c4.5,算法，将分类问题从类别属性扩展到数值型属性。决策树的不足之处是：对于某些数据集，当数据集的实例个数较多时，产生的决策树非常大，分类模型较为复杂，因此需要对决策树进行简化；此外，数据集中属性值的遗失情况和类分布均匀性对决策树的分类效果产生较大的影响。,11,2025/2/6 周四,构造分类规则的主要算法及流程,主要算法,直接方法：利用规则归纳技术直接生成规则,e.g.FOIL,AQ,CN2,RIPPER,etc,间接方法：从其他分类模型中提取规则：,利用决策树方法先生成决策树，然后再把决策树转换为规则；,使用粗糙集方法生成规则；,使用遗传算法中的分类器技术生成规则等,；,e.g.decision trees,neural networks,etc,12,2025/2/6 周四,构造分类规则的主要算法及流程,算法简介,规则归纳有四种策略：减法、加法，先加后减、先减后加策略：,减法策略：以具体例子为出发点，对例子进行推广或泛化，推广即减除条件（属性值）或减除合取项（为了方便，我们不考虑增加析取项的推广），使推广后的例子或规则不覆盖任何反例。,加法策略：起始假设规则的条件部分为空（永真规则），如果该规则覆盖了反例，则不停地向规则增加条件或合取项，直到该规则不再覆盖反例。,先加后减策略：由于属性间存在相关性，因此可能某个条件的加入会导致前面加入的条件没什么作用，因此需要减除前面的条件。,先减后加策略：道理同先加后减，也是为了处理属性间的相关性。,13,2025/2/6 周四,顺序覆盖算法流程,基本顺序覆盖算法,构造分类规则的主要算法及流程,14,2025/2/6 周四,构造分类规则的主要算法及流程,规则产生过程,：,这里，一次为一个类学习规则。理想情况下，在为,C,类学习规则时，我们希望它覆盖,C,类的所有（或许多）训练元组，并且没有（或很少）覆盖其他类的元组。这样，学习的规则应该具有高准确率。规则不必是高覆盖率的。这是因为每个类可以有多个规则，使得不同的规则可以覆盖同一类中的不同元组。该过程继续，直到满足终止条件，如不再有训练元组，或返回规则的质量低于用户指定的阈值。给定当前的训练元组集，,Learn_One_Rule,过程为当前类找出“最好的”规则。,也就是说，开始时,R,为空，接下来用函数,Learn_One_Rule,提取类,C,的覆盖当前训练集的最佳规则。在提取规则时，类,C,的所有训练记录被看作是正元组，而其他类的训练记录则被当成负元组。如果一个规则覆盖大多数正元组，没有或仅覆盖极少数负元组，那么该规则是可取的。一旦找到这样的规则，就删掉它覆盖的训练记录，并把新规则追加到,R,的尾部。重复这个过程，直到满足终止条件。然后，算法继续产生下一个类的规则。,15,2025/2/6 周四,示例,规则空间从一般到特殊的搜索,构造分类规则的主要算法及流程,16,2025/2/6 周四,示例说明,为了学习“,accept,”类的规则，从一般的规则开始，即从规则前件条件为空的规则开始，然后考虑每个可以添加到该规则中的可能属性测试。,Learn_One_Rule,采用一种贪心的深度优先策略。每当面临添加一个新的属性测试到当前规则时，它根据训练样本选择最能提高规则质量属性的测试。,而什么样的度量能被选择为规则质量？,构造分类规则的主要算法及流程,17,2025/2/6 周四,Learn_One_Rule,需要度量规则的质量。每当考虑一个属性测试时，乍一看准确率似乎是一个显然的选择，但我们先看一下下面的例子：,首先给出两个概念：,正元组（,pos,）：学习规则的类的元组,负元组（,neg,）：除去学习规则的类的元组，其余的元组。,规则质量度量,18,2025/2/6 周四,虽然,R2,只覆盖两个元组，但是,R2,的准确率为,100%,大于,R1,，在顺序覆盖算法中，将会选择,R2,而不是,R1,，这显然是不合理的。为了解决这个问题，我们采用另一种度量,-,信息增益，这种度量在一阶归纳学习器（,First Order Inductive Learner,，,FOIL,）中提出。用,Foil_Gain,作为规则质量标准：,其中,pos,，,neg,为新增规则,R,所覆盖的正元组和负元组，,pos,，,neg,是,R,覆盖之前的,R,所覆盖的正元组和负元组,FOIL_Gain,越大越好。,规则质量度量,19,2025/2/6 周四,上面介绍的规则质量评估使用原训练数据的原则，这种评估是乐观的，因为规则可能过分拟合这些数据。也就是说，规则可能在训练数据上性能很好，但是在以后的数据上就不那么好。为了补偿这一点，可以对规则剪枝。下面给出一个剪枝方法：给定规则,R,FOIL_Prune(R)=(pos-neg)/(pos+neg),其中，,pos,和,neg,分别为规则,R,覆盖的正元组和负元组。这个值将随着,R,在剪枝集上的准确率的增加而增加。因此，如果,R,剪枝后版本的,FOIL_Prune,值较高，则对,R,剪枝,规则剪枝,20,2025/2/6 周四,FOIL,算法举例,age,income,student,credit_rating,buys_computer,pos,3140,high,no,fair,yes,40,medium,no,fair,yes,40,low,yes,fair,yes,3140,low,yes,excellent,yes,40,medium,yes,fair,yes,neg,=30,high,no,fair,no,40,low,yes,excellent,no,=30,medium,no,fair,no,说明：首先以,buys_computer=yes,为正例，其它为负例,训练集（,Training Dataset,）,21,2025/2/6 周四,FOIL,算法举例（续）,带入公式，求出每个属性值的增益：,age,40,gain,-1.263,1.474,0.966,income,high,medium,low,gain,-0.848,0.304,0.966,student,yes,no,gain,1.660,-1.170,Credit-rating,fair,excellent,gain,1.257,-0.848,pos=6,neg=4;,例如，我们算一下,age0,，所以还要进行内循环,age,income,student,credit_rating,buys_computer,Pos,40,low,yes,fair,yes,3140,low,yes,excellent,yes,40,medium,yes,fair,yes,Neg,40,low,yes,excellent,no,23,2025/2/6 周四,FOIL,算法举例（续）,再次求最大,FOIL,增益，这时,pos=4,，,neg=1,。,age,40,gain,0.322,0.322,-0.526,income,low,medium,gain,-0.279,0.322,credit-rating,fair,excellent,gain,0.966,-0.678,所以当,p=credit-rating=fair,时有最大的,FOIL_Gain,。执行,append p to r,那么规则,r=student=yesAND credit-rating=fair,；移除,pos,、,neg,中不满足规则,r,的元组，这时，,neg=0,，内循环停止,24,2025/2/6 周四,FOIL,算法举例（续）,此时,pos=30,第二次执行外循环,:P,赋给,P,，,N,赋给,N,规则,r,清空,neg=40,执行内循环,:,age,income,student,credit_rating,buys_computer,Pos,3140,high,no,fair,yes,40,medium,no,fair,yes,3140,low,yes,excellent,yes,Neg,=30,high,no,fair,no,40,low,yes,excellent,no,40,medium,no,fair,yes,neg,=30,high,no,fair,no,40,low,yes,excellent,no,40,medium,no,fair,yes,Neg,40,那么,r=income=medium AND age=40,再删除,pos,和,neg,中不满足规则,r,的所有元组之后，,pos=0,，,neg=0,内循环停止。,这时，执行,R=R r,由于,pos=0,，所以第三次外循环执行之后停止，所有的正例规则全部找出，,R=,(student=yes AND credit-rating=fair),OR,（,age=3140,）,OR,（,income=medium AND age=40,）,28,2025/2/6 周四,FOIL,算法举例（续）,age,income,student,credit_rating,buys_computer,P,=30,high,no,fair,no,40,low,yes,excellent,no,40,medium,no,fair,yes,40,low,yes,fair,yes,3140,low,yes,excellent,yes,40,medium,yes,fair,yes,buys_computer=no,为正例，其它为负例,29,2025/2/6 周四,FOIL,算法举例（续）,我们按照同样的方法，算出,R=,（,age=40,）,那么综合以上所求的两个规则,R,，,我们可以从十条训练集中学习出以下结论：,IF(student=yes AND credit-rating=fair)THEN buys_computer=yes;,IF(age=3140)THEN buys_computer=yes;,IF(income=medium AND age=40,）,THEN buys_computer=yes;,IF(age=40)THEN buys_computer=no;,现在有个问题，就是提取出来的规则集的准确率有多高呢？,这时，我们需要通过检验集来验证规则集的准确率，检验集如下所示：,30,2025/2/6 周四,FOIL,算法举例（续）,检验集,age,income,student,credit_rating,buys_computer,40,medium,no,excellent,no,根据规则集可以知道，有三个元组类预测是正确的，而有一个元组类预测是错误的，所以准确率,=3/4=0.75,。总结：由于训练集只有,10,个元组，元组数比较少，可能导致根据,FOIL,算法提取出来的规则集的准确率比较低。,31,2025/2/6 周四,由决策树提取分类规则举例,由决策树提取,IF-THEN,规则，建立基于规则的分类器,概念,buys_computer,的决策树,沿着从根结点到树中每个树叶节点的路径，将决策树转换成,IF-THEN,分类规则：,R1,：,IF age=youth and student=no THEN buys_computer=no,R2,：,IF age=youth and student=yes THEN buys_computer=yes,R3,：,IF age=middle_aged THEN buys_computer=yes,R4,：,IF age=senior and credit_rating=excellent THEN buys_computer=yes,R5,：,IF age=senior and credit_rating=fair THEN buys_computer=no,所提取的每个规则之间蕴涵着析取的（逻辑,OR,）,关系。由于这些规则直接从树中提取，所以它们是互斥的和穷举的。,32,2025/2/6 周四,谢谢！,33,2025/2/6 周四,