Ripper算法四川师范大学计算机学院.pptx

2024/8/28 周三1Ripper20141306001高洁 一。主要讲的内容1.介绍规则比决策树好的地方，天气举例介绍规则比决策树好的地方，天气举例。2.介绍介绍IREP和和RIPPER算法流程算法流程3.对比决策树对比决策树J48（C4.5）和）和Ripper算法。算法。4.基于基于Ripper的改进算法的改进算法hRipper和和iRipperRipper结合决策和剪枝的决策规则，和决策树相比在不同数据结合决策和剪枝的决策规则，和决策树相比在不同数据下也表现比决策树好。下也表现比决策树好。二。主要文献1.为分类建立决策树，我们可以从叶节点找寻回根节点的规则（如上）。如果把这为分类建立决策树，我们可以从叶节点找寻回根节点的规则（如上）。如果把这些规则减少一点，就形成了决策表，也就是分类规则。（如下）些规则减少一点，就形成了决策表，也就是分类规则。（如下）过一遍下面的规则，感受不重复性。规则。前面处理了过一遍下面的规则，感受不重复性。规则。前面处理了sunny和阴天，则剩下的都和阴天，则剩下的都是雨天。所以可以去除。是雨天。所以可以去除。通过规则可以找到决策树。通过规则可以找到决策树。如果决策树太复杂，并且重复运行，例如三角形，如果决策树太复杂，并且重复运行，例如三角形，使用归纳规则更有逻辑性，更简洁。如图天气例子，决策树的叶子节点很多，使用归纳规则更有逻辑性，更简洁。如图天气例子，决策树的叶子节点很多，但是规则就只有三条。但是规则就只有三条。规则算法总的来说是先创建规则尽可能的包括类中的所有实例，然后再将覆盖了的实例删除，继续寻找规则。规则在weka中比较主要的有part，prism，JRIP（Ripper）。Part的工作原理是通过创建决策树来创建规则，为实例集创建和修建决策树，从大的叶节点读取最重要的规则，然后不再参考决策树，继续执行覆盖算法，不过可以只创建部分决策树而不是整棵决策树。Prism算法算法创造规则很厉害，但是它的规则太精确。Ripper在准确度和规则创建上都有不错的表现。在准确度和规则创建上都有不错的表现。每条每条 RIPPER 规则由一些规则由一些规则前件规则前件(如属性值如属性值条件条件)和结果和结果(如类名如类名)组成，它包括了更好的剪枝和停止准则组成，它包括了更好的剪枝和停止准则(最小描述长度：最小描述长度：MDL)以及对以及对规则集合的后处理。规则集合的后处理。它是一种它是一种递增减少误差修剪算法递增减少误差修剪算法将训练集的实例分为两个数据集，将训练集的实例分为两个数据集，成长集和修剪集成长集和修剪集。成长集用于生产规则，增加条件直到规则完美。修剪集用于修剪规则，删除规则中的条件，直成长集用于生产规则，增加条件直到规则完美。修剪集用于修剪规则，删除规则中的条件，直到更好的规则。到更好的规则。然后对规则价值进行评价，然后移除最后的条件来看价值有没有变化，如果没有变化，就继续然后对规则价值进行评价，然后移除最后的条件来看价值有没有变化，如果没有变化，就继续移除条件，直到得到最好的版本移除条件，直到得到最好的版本。IREP算法算法给定某一类别的若干正例和反例给定某一类别的若干正例和反例,从中获得该类别的一般定义从中获得该类别的一般定义,这就是归纳学习。这就是归纳学习。RIPPER算法是建立算法是建立IREP算法基础上的算法基础上的,因此因此,先来简单介绍一下先来简单介绍一下IREP算法。算法。IREP使用贪婪算法构造规则集使用贪婪算法构造规则集,每次构造一条规则。当发现一条规则之后每次构造一条规则。当发现一条规则之后,所有被这条规则所有被这条规则“覆覆盖盖”的样本都被删除掉的样本都被删除掉,不论是肯定的还是否定的。不论是肯定的还是否定的。这一过程将反复进行这一过程将反复进行,直到没有肯定的样本直到没有肯定的样本存在存在,或者学到了一条不可以接受的规则或者学到了一条不可以接受的规则(规则的错误率太大规则的错误率太大,超过了预设定的闭值超过了预设定的闭值)。在构造单个规则的过程中在构造单个规则的过程中,IREP采用了以下策略采用了以下策略:尚未被覆盖的样本被随机地分成两个子集尚未被覆盖的样本被随机地分成两个子集一个生长集和一个修剪集一个生长集和一个修剪集(在实现中在实现中,生长集生长集包含总包含总体样本的体样本的三分之二三分之二,修剪集修剪集包含总体样本的包含总体样本的三分之一三分之一)。接着。接着,采用贪婪算法生成一条规则。这种采用贪婪算法生成一条规则。这种方法从一个空的条件方法从一个空的条件(称其为规则前件或前件称其为规则前件或前件)链开始链开始,然后顺序在空的规则前件链中加上如下形然后顺序在空的规则前件链中加上如下形式的规则前件式的规则前件:Ad是是字符型的属性字符型的属性,v是是Ad的一个有的一个有效值效值;An是实数型的变量是实数型的变量,0是在训练集中出现的是在训练集中出现的An的有效值。的有效值。在在“生长生长”的过程中的过程中,算法按照算法按照最大化信息增益最大化信息增益的标准的标准,不停地往规则中不停地往规则中增加新的前件增加新的前件,直到生长直到生长集中没有否定的样本被覆盖为止集中没有否定的样本被覆盖为止。IREP算法算法生成一条规则之后生成一条规则之后,马上马上修剪这条规则修剪这条规则。在实现中。在实现中,可以修剪规则中的任何规则前件。修剪的标可以修剪规则中的任何规则前件。修剪的标准是可以使得下式准是可以使得下式:P裁剪集中所有的肯定的样本数裁剪集中所有的肯定的样本数;n裁剪集中被规则覆盖的否定的样本数。裁剪集中被规则覆盖的否定的样本数。N裁剪集中所有的否定的样本数裁剪集中所有的否定的样本数;p裁剪集中被规则覆盖的肯定的样本数裁剪集中被规则覆盖的肯定的样本数;IREP算法算法 IREP 算法的核心算法的核心：1）把训练数据分成生长集和修剪集，）把训练数据分成生长集和修剪集，2）通过生长集来产生规则，）通过生长集来产生规则，3）通过修剪集来对规则进行剪枝，停止剪枝）通过修剪集来对规则进行剪枝，停止剪枝的时机是由停止条件的时机是由停止条件(stop condition)来决定。来决定。Ripper 算法对算法对IREP的改进的改进：1.改进改进 IREP 的修剪算法的修剪算法的的 PrunePule 函数函数IREP算法修剪规则函数有所偏重，比如一个算法修剪规则函数有所偏重，比如一个p1=2000,n1=1000的规则的规则,和一个和一个p2=1000,而而n2=1的规则。在大的规则。在大P和和N相等的时候相等的时候,规则规则1的错误率达到了的错误率达到了2/3,规则规则2的错误率只有的错误率只有1/1001。很显然很显然,规则规则2要比规则要比规则1好得多。但是好得多。但是,用公式前页用公式前页v做度量的结果却是规则做度量的结果却是规则1要比规则要比规则2好。因此好。因此,Cohen修改了修改了IREP的度量。的度量。真特征项指真特征项指在本类中出现次数较多,在其它类中出现次数较少的特征项。伪特征项指伪特征项指在任何类中都可能出现并且出现次数较多的特征项。稀疏特征项稀疏特征项指在任何类中都可能出现并且出现次数较少的特征项。这里剪枝p=pc(f)形式，n=nc(f)形式。剪枝规则阶段:从规则的末尾特征项开始,重复删除直到度量公式(p C(r)-nC(r)/(p C(r)+nC(r)达到最大。也就是V最大。而代之以而代之以 Ripper 算法对算法对IREP的改进的改进：2.将将 stop condition(即即(PrunePos,PruneNeg)exceeds 50%这一停止条件改为这一停止条件改为最小描述长度最小描述长度MDL作为衡量停止学习的一个度量。每当一条规则被加到规则集之后作为衡量停止学习的一个度量。每当一条规则被加到规则集之后,马上计算采用此一条规则马上计算采用此一条规则,删除覆盖的样本实例之后删除覆盖的样本实例之后,样本集合与现有的规则集合的总的样本集合与现有的规则集合的总的“比特比特长度长度”(字节数字节数)。如果加入。如果加入此一条规则将导致计算得到的此一条规则将导致计算得到的总长度比迄今为止的最小长度大总长度比迄今为止的最小长度大dbit,或者实例中没有肯定的实例或者实例中没有肯定的实例的时候的时候,停止学习。在停止学习。在Cohen的程序中的程序中,d=64。3.当一个规则集被学到之后当一个规则集被学到之后,对于规则集中的规则对于规则集中的规则R1,R2,Rk,按照学到的顺序依次优化按照学到的顺序依次优化R1,R2,Rk。优化方法是对。优化方法是对R1产生两个产生两个R1和和R1*。R1是在一是在一条空的规则条空的规则上加前件而产生的上加前件而产生的,修剪的时候是修剪的时候是使得整个规则集在修剪集上的错误率最小使得整个规则集在修剪集上的错误率最小。而。而R1*是通过贪婪地往是通过贪婪地往R1上加规则前上加规则前件产生的件产生的,然后把然后把R1，R1和和R1*放到规则集中放到规则集中,然后比较三个规则集然后比较三个规则集MDL值值,选取其中最小的一选取其中最小的一个作为个作为R1.RIPPER算法算法若一个数据项内的属性值满足规则中的条件若一个数据项内的属性值满足规则中的条件,则它被该规则所覆盖则它被该规则所覆盖;对于一个规则的结果对于一个规则的结果(即目标即目标类类),那些属于这个结果的数据项称为主动数据项那些属于这个结果的数据项称为主动数据项,不属于这个结果的数据项称为被动数据项。不属于这个结果的数据项称为被动数据项。实现过程如下实现过程如下:(1)把把不属于规则不属于规则的数据项的数据项(在训练数据中在训练数据中)随机地分为两个子集随机地分为两个子集增长集和缩减集增长集和缩减集;(2)规则的扩张过程。开始时把规则的扩张过程。开始时把规则的条件置空规则的条件置空,接下来加入公式接下来加入公式的条件。的条件。如此如此反复地向规则中加入条件反复地向规则中加入条件,使信息增益使信息增益Gain(D,At)达到更大的值达到更大的值,提高规则对数据项的覆盖提高规则对数据项的覆盖面面,直到规则涵盖了增长数据集中的所有数据项直到规则涵盖了增长数据集中的所有数据项;(3)规则缩减过程规则缩减过程。依次从规则的条件中剔除最后一个条件。依次从规则的条件中剔除最后一个条件,使函数值使函数值v达到最大。函数达到最大。函数v的表达的表达式：式：重复执行这个过程直到通过缩减条件和删除规则重复执行这个过程直到通过缩减条件和删除规则无法使无法使v的值增大为止的值增大为止。RIPPER 算法包括2 个阶段:(1)增长规则阶段增长规则阶段:根据贪婪算法的思想,尽可能多的往规则r 中加入特征项,使r 的信息增益FOIL 最大化,直到nc(r)=0（所有数据都被覆盖）;(2)剪枝规则阶段:从规则的末尾特征项开始,重复删除直到度量公式(p C(r)-nC(r)/(p C(r)+nC(r)，v达到最大。RIPPER算法算法再次简化：RIPPER 算法包括2 个阶段:(1)增长规则阶段增长规则阶段:根据贪婪算法的思想,尽可能多的往规则r 中加入特征项,使r 的信息增益FOIL 最大化,直到nc(r)=0（所有数据都被覆盖）;(2)剪枝规则阶段:从规则的末尾特征项开始,重复删除直到度量公式(p C(r)-nC(r)/(p C(r)+nC(r)，前文的v达到最大。RIPPER在分类时提高准确率在分类时提高准确率C4.5作为决策树中表现很好的一种算法，在作为决策树中表现很好的一种算法，在weka中以中以J48命名。命名。Ripper算法错误率小于或等于算法错误率小于或等于C4.5 且效率和训练数据集的样本个数成线形且效率和训练数据集的样本个数成线形,其时间复杂度为其时间复杂度为,更重要的是可以在包含几十万噪声数据的测试集上仍然保持很高的效率。更重要的是可以在包含几十万噪声数据的测试集上仍然保持很高的效率。在在weka上比较上比较数据比较可以从数据的准确性，速度性，压缩性（大数据下表现），复杂度等方面考虑数据比较可以从数据的准确性，速度性，压缩性（大数据下表现），复杂度等方面考虑选取选取weka自带数据。自带数据。Credit有有1000个实例，个实例，21个属性。个属性。labor有有57个实例，个实例，17个属性。个属性。Credit有有1000个实例，个实例，21个属性。个属性。credit左J48，右Jrip labor左J48，右Jripweather左J48，右JripRIPPER缺陷和改进：缺陷和改进：(1)传统的传统的RIPPER 算法缺陷算法缺陷,当规则本身变得很复杂(也就是规则所涉及的特征项很多)的时候,其优点就不复存在,而且算法本身的效果也大大下降。(1)增长规则的过程中只考虑特征项的增长规则的过程中只考虑特征项的FOIL值的大小。值的大小。在生成规则的开始,FOIL 最大的特征项首先被选进规则,如果此时nC(r)！=0,根据算法要求,需要继续加入特征项,使得加入后含2 个特征项的规则集r 的FOIL 最大,以此类推,直到nC(r)=0。假定真特征项集合ts 已被选入规则,如果nC(r)！=0,需要加入一个特征项到r 中使得nC(r)=0,作为候选的特征项可能是真特征项t,伪特征项f 和稀疏特征项s,如果FOIL(t s,f)或者FOIL(ts,s)信息增益比较大,那么就会把伪特征项f 或者稀疏特征项s 选入规则。（2）根据RIPPER 算法,一条规则r 生成并且剪枝后,将删除目前训练集中覆盖该规则的所有文档,训练过程的停止条件是本类文档都被删除。到了生成规则的后期到了生成规则的后期,所有的真特征项都被选入所有的真特征项都被选入规则并且随着文档的删除而删除规则并且随着文档的删除而删除,剩下的都是噪音特征项剩下的都是噪音特征项,此时如果本类中还有没有被删除的文档,则需要继续选择剩下这些特征项,那么这些噪音特征项有可能单独作为规则出现。（3）剪枝条件为v=(p-n)/(p+n),除n上下加减1，得到1-2/(（p/n）-1).所以，剪枝规则只和p/n有关，不够全面。针对这个问题,文献ALUMUALLLIM H,DIETTERICH T.Learning with many irrelevant features 提出当数据资源规模很大,并且存在着一定数量噪音数据的时候,在调用RIPPER 分类算法之前首先进行特征选择可以改善算法效果。特征选择有很多方法,对常用的特征选择方法进行比较,得出IG和CHI 最有效的结论。对于基于规则的分类方法,特征集的大小对结果的影响非常大。当特征集较大,会造成过渡拟合,使得效果下降.反之,当特征集较小,又会造成分类错误过高。因此,如何选择一个合适的特征集成为算法设计的一个关键问题。RIPPER缺陷和改进：缺陷和改进：（2）hRIPPER是是利用分层次结构的方法解决在特征值多噪音多数据。该算法在不同层次上的不同层次上的类别选出具有代表性的特征集类别选出具有代表性的特征集,过滤掉了部分噪音特征项,在一定程度上改善了RIPPER。但是，由于采用层次架构,子类中的规则很多是父类的,兄弟类别之间有很多相同的规则。可以通过剔除子类跟父类共有的规则来减轻兄弟类别的交叉,从而提高分类效果。RIPPER改进初想：改进初想：（1）RIPPER将规则按信息增益大小排序选择，在选出信息增益最大的特征项后，先对将规则按信息增益大小排序选择，在选出信息增益最大的特征项后，先对pC(w)/nC(w)进行判断进行判断,当当p C(w)/nC(w)0（中间有一横）（中间有一横）,即即w 是真特征项的时候是真特征项的时候,再把它再把它加入规则加入规则,这样就防止噪音特征项与真特征项一块加入规则的情况发生。这样就防止噪音特征项与真特征项一块加入规则的情况发生。（2）因为特征项都是）因为特征项都是按照按照FOIL 由大到小由大到小选择出来。在规则生成后期选择出来。在规则生成后期,特征项中剩下的都是噪特征项中剩下的都是噪音特征项音特征项,可以对可以对FOIL 设定一个阈值设定一个阈值,当前规则的当前规则的FOIL 小于等于该阈值小于等于该阈值,则立即停止生成规则。则立即停止生成规则。但是怎么确定阈值。但是怎么确定阈值。（3）p为为裁剪集中被规则覆盖的肯定的样本数裁剪集中被规则覆盖的肯定的样本数，剪枝时，不仅需要考虑，剪枝时，不仅需要考虑p C(w)/nC(w)的大的大小小,还可以考虑还可以考虑pC(r)的大小的大小,例如例如p C(r)小于等于一个阈值小于等于一个阈值,就对规则进行剪枝就对规则进行剪枝,这样就剪去这样就剪去了夹杂在规则中的噪音特征项。同时也可以剪掉噪音特征项单独作为规则的规则。了夹杂在规则中的噪音特征项。同时也可以剪掉噪音特征项单独作为规则的规则。总结：总结：(1)基于上诉三点，对基于上诉三点，对RIPPER改进。改进。(2)将将ripper这种算法应用在分类的地方，动态数据挖掘能够打赢决策树那篇吗？基于这种算法应用在分类的地方，动态数据挖掘能够打赢决策树那篇吗？基于ripper对对于入侵有更好的检测，于入侵有更好的检测，hripper还是用在分层结构上的特征值选择后的剪枝。还是用在分层结构上的特征值选择后的剪枝。