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

1、2020/9/8,1,Ripper,20141306001高洁,一。主要讲的内容 1.介绍规则比决策树好的地方，天气举例。 2.介绍IREP和RIPPER算法流程 3.对比决策树J48（C4.5）和Ripper算法。 4. 基于Ripper的改进算法hRipper和iRipper Ripper结合决策和剪枝的决策规则，和决策树相比在不同数据下也表现比决策树好。,二。主要文献,1.为分类建立决策树，我们可以从叶节点找寻回根节点的规则（如上）。如果把这些规则减少一点，就形成了决策表，也就是分类规则。（如下） 过一遍下面的规则，感受不重复性。规则。前面处理了sunny和阴天，则剩下的都是雨天。所以可

2、以去除。,通过规则可以找到决策树。如果决策树太复杂，并且重复运行，例如三角形，使用归纳规则更有逻辑性，更简洁。如图天气例子，决策树的叶子节点很多，但是规则就只有三条。,规则算法总的来说是先创建规则尽可能的包括类中的所有实例，然后再将覆盖了的实例删除，继续寻找规则。规则在weka中比较主要的有part，prism，JRIP（Ripper）。 Part的工作原理是通过创建决策树来创建规则，为实例集创建和修建决策树，从大的叶节点读取最重要的规则，然后不再参考决策树，继续执行覆盖算法，不过可以只创建部分决策树而不是整棵决策树。 Prism算法创造规则很厉害，但是它的规则太精确。,Ripper在准确度和

3、规则创建上都有不错的表现。每条 RIPPER 规则由一些规则前件(如属性值条件) 和结果(如类名) 组成，它包括了更好的剪枝和停止准则(最小描述长度：MDL ) 以及对规则集合的后处理。 它是一种递增减少误差修剪算法将训练集的实例分为两个数据集，成长集和修剪集。 成长集用于生产规则，增加条件直到规则完美。修剪集用于修剪规则，删除规则中的条件，直到更好的规则。 然后对规则价值进行评价，然后移除最后的条件来看价值有没有变化，如果没有变化，就继续移除条件，直到得到最好的版本。,IREP算法 给定某一类别的若干正例和反例,从中获得该类别的一般定义,这就是归纳学习。 RIPPER算法是建立IREP算法基

4、础上的,因此,先来简单介绍一下IREP算法。 IREP使用贪婪算法构造规则集,每次构造一条规则。当发现一条规则之后,所有被这条规则“覆盖”的样本都被删除掉,不论是肯定的还是否定的。这一过程将反复进行,直到没有肯定的样本存在,或者学到了一条不可以接受的规则(规则的错误率太大,超过了预设定的闭值)。 在构造单个规则的过程中,IREP采用了以下策略: 尚未被覆盖的样本被随机地分成两个子集一个生长集和一个修剪集(在实现中,生长集包含总体样本的三分之二,修剪集包含总体样本的三分之一)。接着,采用贪婪算法生成一条规则。这种方法从一个空的条件(称其为规则前件或前件)链开始,然后顺序在空的规则前件链中加上如下

5、形式的规则前件: Ad是字符型的属性,v是Ad的一个有效值;An是实数型的变量,0是在训练集中出现的An的有效值。在“生长”的过程中,算法按照最大化信息增益的标准,不停地往规则中增加新的前件,直到生长集中没有否定的样本被覆盖为止。,IREP算法 生成一条规则之后,马上修剪这条规则。在实现中,可以修剪规则中的任何规则前件。修剪的标准是可以使得下式: P裁剪集中所有的肯定的样本数; n裁剪集中被规则覆盖的否定的样本数。 N裁剪集中所有的否定的样本数; p裁剪集中被规则覆盖的肯定的样本数;,IREP算法 IREP 算法的核心： 1）把训练数据分成生长集和修剪集， 2）通过生长集来产生规则， 3）通过

6、修剪集来对规则进行剪枝，停止剪枝 的时机是由停止条件(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的度量。 真特征项指在本类中出现次数较多, 在其它类中出现次数较少的特征项。 伪特征项

7、指在任何类中都可能出现并且出现次数较多的特征项。 稀疏特征项指在任何类中都可能出现并且出现次数较少的特征项。 这里剪枝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作为衡量停止学习的一个度量。每当一条规则被加到规则集之后,马上计算

8、采用此一条规则,删除覆盖的样本实例之后,样本集合与现有的规则集合的总的“比特长度”(字节数)。如果加入此一条规则将导致计算得到的总长度比迄今为止的最小长度大dbit,或者实例中没有肯定的实例的时候,停止学习。在Cohen的程序中,d=64。 3.当一个规则集被学到之后,对于规则集中的规则R1,R2,Rk,按照学到的顺序依次优化R1,R2,Rk 。优化方法是对R1产生两个R1和R1*。R1是在一条空的规则上加前件而产生的,修剪的时候是使得整个规则集在修剪集上的错误率最小。而R1*是通过贪婪地往R1上加规则前件产生的,然后把R1，R1和R1*放到规则集中,然后比较三个规则集MDL值,选取其中最小的

9、一个作为R1.,RIPPER算法 若一个数据项内的属性值满足规则中的条件,则它被该规则所覆盖;对于一个规则的结果(即目标类),那些属于这个结果的数据项称为主动数据项,不属于这个结果的数据项称为被动数据项。 实现过程如下: (1)把不属于规则的数据项(在训练数据中)随机地分为两个子集增长集和缩减集; (2)规则的扩张过程。开始时把规则的条件置空,接下来加入公式 的条件。 如此反复地向规则中加入条件,使信息增益Gain(D,At)达到更大的值,提高规则对数据项的覆盖面,直到规则涵盖了增长数据集中的所有数据项; (3)规则缩减过程。依次从规则的条件中剔除最后一个条件,使函数值v达到最大。函数v的表达

10、式： 重复执行这个过程直到通过缩减条件和删除规则无法使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 中

11、加入特征项, 使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上比较 数据比较可以从数据的

12、准确性，速度性，压缩性（大数据下表现），复杂度等方面考虑 选取weka自带数据。 Credit有1000个实例，21个属性。 labor有57个实例，17个属性。 Credit有1000个实例，21个属性。,credit 左J48，右Jrip,labor 左J48，右Jrip,weather 左J48，右Jrip,RIPPER缺陷和改进： ( 1)传统的RIPPER 算法缺陷,当规则本身变得很复杂( 也就是规则所涉及的特征项很多) 的时候, 其优点就不复存在, 而且算法本身的效果也大大下降。 ( 1) 增长规则的过程中只考虑特征项的FOIL值的大小。在生成规则的开始, FOIL 最大的特征项首

13、先被选进规则, 如果此时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 生成并且剪枝后, 将删除目前训

14、练集中覆盖该规则的所有文档, 训练过程的停止条件是本类文档都被删除。到了生成规则的后期, 所有的真特征项都被选入规则并且随着文档的删除而删除, 剩下的都是噪音特征项, 此时如果本类中还有没有被删除的文档, 则需要继续选择剩下这些特征项, 那么这些噪音特征项有可能单独作为规则出现。 （3）剪枝条件为v=(p-n)/(p+n),除n上下加减1，得到1-2/(（p/n）-1).所以，剪枝规则只和p/n有关，不够全面。 针对这个问题, 文献ALUMUALLLIM H, DIETTERICH T. Learning with many irrelevant features 提出当数据资源规模很大, 并

15、且存在着一定数量噪音数据的时候, 在调用RIPPER 分类算法之前首先进行特征选择可以改善算法效果。特征选择有很多方法, 对常用的特征选择方法进行比较, 得出IG和CHI 最有效的结论。对于基于规则的分类方法, 特征集的大小对结果的影响非常大。当特征集较大, 会造成过渡拟合 , 使得效果下降. 反之, 当特征集较小, 又会造成分类错误过高。因此, 如何选择一个合适的特征集成为算法设计的一个关键问题。,RIPPER缺陷和改进： （2）hRIPPER是利用分层次结构的方法解决在特征值多噪音多数据。该算法在不同层次上的类别选出具有代表性的特征集, 过滤掉了部分噪音特征项, 在一定程度上改善了RIPP

16、ER。 。但是，由于采用层次架构, 子类中的规则很多是父类的, 兄弟类别之间有很多相同的规则。可以通过剔除子类跟父类共有的规则来减轻兄弟类别的交叉, 从而提高分类效果。,RIPPER改进初想： （1）RIPPER将规则按信息增益大小排序选择，在选出信息增益最大的特征项后，先对pC ( w )/nC ( w ) 进行判断, 当p C ( w )/nC ( w ) 0（中间有一横）,即w 是真特征项的时候, 再把它加入规则, 这样就防止噪音特征项与真特征项一块加入规则的情况发生。 （2）因为特征项都是按照FOIL 由大到小选择出来。在规则生成后期, 特征项中剩下的都是噪音特征项,可以对FOIL 设定一个阈值, 当前规则的FOIL 小于等于该阈值, 则立即停止生成规则。但是怎么确定阈值。 （3）p为