机器学习算法：J48和JRip

电子产品可靠性与环境试验　

分类算法的分析与比较★　

陈媛媛．彭新光　

太原理工大学计算机科学与挂术系．山西　太原０３００２４　

摘　要：在全面综述通用毫『Ｌ器学习归纳分类算法的基础上，采用算法分类机制分析的方括，从预涮精度、　学习效率、健壮性等方面对决策村和规则归纳分类算法进行睬人的分析和比较研究，为在不同的应用领域选　择最优分类算法奠定了基础。由于Ｒ【ＰＰＥＲ分类算法采用了重复增量裁减机制，所以在计算复杂性、分类精　度、噪音数据适应性等方面都优于其它分类算１哇，更适用于入侵检测建攘使用　关键词：机器学习；分类算法：入侵检测　中图分类号：ｒＩ’Ｐ　３０１．６　文献标识码：Ａ　文章编号：１６７２－５４６８（２ｏｏ４）０６－－００７２—ｏ４　

Ａｎａｌｙｓｉｓ　ａｎｄ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　

ＣＨＥＮ　Ｙｕａｎ—ｙｕａｎ，ＰＥＮＧ　Ｘｉｎ—ｇｕｍ￣ｇ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ＆ｎ（】Ｔｅｅｈｎｏ］ｏｇｙ　ｏｆ　ＴＵＴ，Ｔａｉｙｕａｎ　０３００２４，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｉｔ　ｓｕｍｍａｒｉｚｅｓ　Ｉｈｅ　ｍａｉｎ　ｆｅａｔ，Ｉｒｅｓ　ｏｆ　ｄｅｘ．ｉｓｉｏｎ　ｔｒｅｅ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｌｈｍ　ａｎｄ　ｒｕｌｅ　ｌｅａｒｎｉｎｇ　

ａｌｇｏｒｉｔｈｍ　ｂｙ　ｉｎ—ｄｅｐｔｈ　ａｎａｌｙｓｉｓ　ａｎｄ　ｃｏｍｐａｒｉｓｏｎ　ｆｒｏｍ　ａｌｌ　ａｓｐｅｃｔｓ　ｓｕｃｈ　ａｓ　ｐｒｅｄｉｃｔｉｏｎ　ａｃｃｕｒａｃｙ　

ｌｅａｒｎｉｎｇ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ｒｏｂｕｓｔｎｅｓｓ．Ｉｔ　ｉｓ　ｓｈｏｗｎ　ｔｈａｔ　ＲＩＰＰＥＲ　ｉｓ　ｓｕｐｅｒｉｏｒ　ｔｏ　ｏｔｈｅｒ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｔｅｒｍｓ　

ｏｆ　ｃｏｍｐｌｅｘｉｔｙ　ｉｎ　ｃｏｍｐｕｔａｔｉｏｎ，ｃｌａｓｓｉｆｉｅｄ　ｐｒｅｅｉｓｉＯ１３　ａｎｄ　ｎｏｉｓｙ　ｄａｔａ　ａｄａｐｔａｈｉｌｉｔｙ　ｂｅｃａｕｓｅ　ｏｆ　ｉｔｓ　

ａｄｏｐｔｉｏｎ　ｏｆ　ｔｈｅ　ｒｅｐｅａｔｅｄ　ｉｎｃｒｅｍｅｎｔａｌ　ｒｅｄｕｃｔｉｏｎ　ｍｅｃｈａｎｉｓｍ，ａｎｄ　ｉｔ　ｉｓ　ｍｏｒｅ　ｓｕｉｔａｂｌｅ　ｔｏ　ｔｈｅ　ｉｎｔｒｕｓｉｏｎ　

ｄｅｔｅｃｔｉｏｎ．　

Ｋｅｙ　ｗｏｒｄｓ：ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ；ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｌｇｏｒｉ山ｍ；ｉｎｔｒｕｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　

１　引言　

分类就是在已有数据的基础上　学习一个分　

类函数或构造一个分类模型．即我们通常所说的　

分类器（Ｃｌａｓｓｉｆｉｅｒ）。该函数或模型能够把数据库　

巾的记录映射到给定类别中的某一个　从而应用　

于数据预测。构造分类器的过程一般分训练丰钉测　

试两个阶段　在训练阶段．分析训练数据集中数　

据记录的特征属性，为每种类型标识生成精确的　分类规则描述。在测试阶段　利用分类规则进行　精度测试，然后用于对实际数据集中的数据记录　

进行分类　一般来说，测试阶段的代价远远低于　圳练阶段　本文主要采用算法分析的方法来比较　

不同的分类算法，分析过程中主要用到下列指标：　１）预测精度：分类器正确预ｌ蜊新的或先前未　

见过的数据类标的能力；　２）学习效率：产生和使用分类器的时间；　

３）健牡性：给定噪声数据或具有空缺值的数　

★基金项目：山西省自然科学基金项目（２００４ｌ０４７）责助　收稿日期：２００４＿０９—０ｌ　作者简介：陈斌谩（１９８０－），士．山西省交城县人，太朦理工大学计算机科学与技术系硕士砰览生．研究方向为机器学习　与网络安奎。

　维普资讯 http://www.cqvip.com 第６期　陈媛媛等：分类算法的分析与比较　

据。分类器正确预测的能力。　这些指标较全面地反映了归纳分类算法的性　

能。这里主要针对目前广泛使用的决策树和规则　

分类算法进行分析与比较。　

２决策树分类算法　

决策树方法起源于概念学习系统（ＣＬＳ：　

Ｃｏｎｃｅｐｔ　Ｌｅａｒｎｉｎｇ　Ｓｙｓｔｅｍ）。然后发展了ＩＤ　３方法并　

达到高峰。最后又演化为能处理连续属性的Ｃ　４．５　

【ｌ】数据挖掘研究兴起之后，为了适应大规模数据　

集的处理，对它又进行了改进，其中ＳＬＩＱ　２】　

（Ｓｕｐｅｒｖｉｓｅｄ　Ｌｅａｒｎｉｎｇ　Ｉｎ　Ｑｕｅｓｔ）是比较有代表性的　

算法。　

２．１　Ｃ　４．５算法　

Ｃ　４．５算法构造决策树的核心思想是贪婪算法，　

它采用自上而下递归的各个击破方式构造决策树。　

开始时，属性都在根节点，所有记录采用属性递　

归方式进行分裂。属性选择基于信息增益统计度　量。然后把这个过程递归到每个子树，当一个节　

点上的数据都属于同一个类别或者没有属性可以　

再用于对数据进行分裂时停止。决策树生成之后，　对树剪枝以处理过分适应数据（Ｏｖｅｒ—ｆｉｔｔｉｎｇ）的问　

题。决策树分类算法与统计方法、神经网络等其　

它分类算法比较，有如下优点：　

ａ）产生的规则易于理解。决策树的每个分支　

都对应一个分类规则，因此，决策树分类算法最　

终可以输出一个容易理解的规则集。　

ｂ）速度相对较快，其时间复杂度是Ｏ（ｎ　），　

这里ｎ指训练数据集合中样本的个数。　Ｃ）准确率相对较高。　

如果决策树在建立过程中生长得太“枝繁叶　茂”，既降低了树的可理解性和可用性，同时也使　

决策树本身对历史数据的依赖性增大。导致决策　

树对历史数据非常准确，但应用到新数据时，准　

确性将急剧地下降。为了避免数据过适应问题和　

减少训练时间。必须选择好的修剪方法。修剪方　法一般有先剪枝法（Ｐｕｂｌｉｃ算法）和后剪枝法　

（Ｓｐｒｉｎｔ算法）。实质是消除训练集中的异常和噪　

声。由于在构造树的过程中，需要对数据集进行　多次顺序扫描和排序，降低了算法的学习效率。　

此外，Ｃ　４．５只适合于能够驻留内存的数据集，当　

训练集大得无法在内存容纳时。程序将无法运行。　２．２　ＳＬＩＱ算法　

ＳＬＩＱ算法在决策树构造过程中，采用了“预　

排序”和“广度优先”两种技术，可以处理符号　

值和连续值。　决策树构造过程中要选择最优属性，必然要　

对训练集中属性的取值进行排序，而排序很耗费　

时间。ＳＬＩＱ算法采用了预排序技术，把所有记录　

按照每个属性的取值从小到大进行排序，消除了　

决策树每个节点都要进行数据集排序的要求。实　

现时．需要为训练集数据的每个属性创建一个属　

性列表。为每个元组的类别创建一个类别列表。算　

法实现时需要足够的内存来保存类别列表。在Ｃ　４５　

中。树的构造是按照深度优先策略完成的，需要　

对每个属性列表在每个节点处都进行一遍扫描，　

费时很多。ＳＬＩＱ采用广度优先策略构造决策树，　

在决策树的每一层只需对每个属性列表扫描一次，　

就可以为当前决策树中每个叶子节点找到最优的　

标准。　ＳＬＩＱ算法主要改进之处是采用了“预排序”　

和“广度优先策略”，因而它能处理大规模数据　

集，因此，在一定程度上，具有随记录个数和属　

性个数增长的可扩展性。但是仍然存在缺点：　

ａ１大规模数据集无法一次全部放入内存。　

ＳＬＩＱ由于需要使用驻留内存的数据结构而限制了　

可以处理的数据集的大小。　ｂ１非线形复杂度。排序算法复杂度不与记录　

个数成线形关系，使ＳＬＩＱ算法不能实现随记录个　

数增长的线形可扩展性。　

３规则归纳学习算法　

归纳学习从分类实例出发能够归纳出一般的　

概念描述。这种方法对领域知识没有要求，但需　

要大量的训练实例，而且归纳性能受描述语言、　

概念类型、信噪比、实例空间分布、归纳模式等　

的影响　

３．１　ＩＲＥＰ算法　

ＩＲＥＰ（Ｉｎｃｒｅｍｅｎｔａｌ　Ｒｅｄｕｃｅｄ　Ｅｒｒｏｒ　Ｐｒｕｎｉｎｇ）算　法采用“分而治之”的策略，把ＲＥＰ（Ｒｅｄｕｃｅｄ　

Ｅｒｒｏｒ　Ｐｒｕｎｉｎｇ）技术紧密地结合在一起［３１。构造规　

则集采用贪婪算法。每次构造一条规则。当发现　

条规则之后，所有被这条规则覆盖的样本不论　

是正例还是反例都被删除掉。这一过程反复进行，

　维普资讯 http://www.cqvip.com 电子产品可靠性与环境试验　２０｛｝４正　

直到没有正例存在．或者学到一条不可接受的规　

则（规则的错误率太大．超过了设定的阈值１。　

ＩＲＥＰ首先把尚未被覆盖的样本随机分成两个　

子集：生长集和修剪集。然后，采用贪婪算法生　

成一条规则　这种方法从一个空的条件链开始，　

然后顺序在空的规则前件链中加上如下形式的规　

则前件：　

Ａ　，Ａ　≤　或者ｊ４　≥０　（１）　式（１）中：Ａ　——字符型的属性；　

的一个有效值；　

Ａ　——实数型的变量；　

在训练集中出现的Ａ　的有效值　

在“生长”过程中．算法按照最大信息增益　

的标准，不停地往规则中增加新的前件，直到生　

长集中没有反例被覆盖为止　

ＩＲＥＰ相对于ＲＥＰ算法提高了学习速度，算法　

消耗的时间和训练数据集的大小成线形关系．而　

ＲＥＰ算法的时间消耗是Ｏ（　）。此外，ＩＲＥＰ算法　提高了噪声数据集上的学习效率。但存在只能处　

理两类问胚和归纳能力不及Ｃ　４．５算法的缺点。　

３．２　ＲＩＰＰＥＲ算法　

ＲＩＰＰＥＲ（ｆｏｒ　Ｒｅｐｅａｔｅｄ　Ｉｎｃｒｅｍｅｎｔａｌ　Ｐｒｕｎｉｎｇ　ｔｏ　Ｐｒｏｄｕｃｅ　Ｅｒｒｏｒ　Ｒｅｄｕｃｔｉｏｎ）包括了更好的剪枝和停　

止准则（最短描述长度准则ＭＤＬ）以及对规则集　

合的后处理　在规则的候选条件序列中，ＩＲＥＰ删　

除了部分条件以使得　（Ｒｕｌｅ，ＰｒｕｎｅＰｏｓ，ＰｒｕｎｅＮｅｇ）　

最大　其定义为：　

（Ｒｕｌｅ，ＰｒｕｎｅＰ。ｓ－ＰｒｕｎｅＮｅｇ）　ｆ２１　

式（２）中：Ｐ和　分别代表ＰｒｕｎｅＰｏｓ和ＰｒｕｎｅＮｅｇ　

中样本总数；　

Ｐ和Ｈ分别表示ＰｒｕｎｅＰｏｓ和ＰｒｕｎｅＮｅｇ　中能够被规则正确标记的样本数目。　

ＲＩＰＰＥＲ用　（Ｒｕｌｅ　ＰｒｕｎｅＰｏｓ，ＰｒｕｎｅＮｅｇ）　

替代了ＩＲＥＰ中的　（Ｒｕｌｅ，ＰｒｕｎｅＰｏｓ，ＰｒｕｎｅＮｅｇ）。　

（Ｒｕ　ｅ．ＰｒｕｎｅＰｏｓ，ＰｒｕｎｅＮｅｇ）　（３）　Ｊ　ＲＩＰＰＥＲ算法［４１通过上述３点改进，其错误　

率小于或等于ｃ　４．５。且效率和训练数据集的样本　

个数成线形，其时间复杂度为Ｏ（ｎｌｏｇａｎ）　更重要　

的是．可以在包含几十万噪声数据的测试集上仍　

然保持很高的效率，与其它分类算法相比，特别　

７４　适台入侵检测建模使用　

４算法的实验比较　

采用５００　０００个实例和２０％噪声数据的数据　

集．对Ｃ　４．５、ＩＲＥＰ和ＲＩＰＰＥＲ算法在学习效率、　

归纳能力方面进行了比较一　

４　１学习效率　

实验结果表明．ＩＲＥＰ和ＲＩＰＰＥＲ苒法速度都　

比Ｃ　４．５算法快，学习时间和训练数据集的大小几　

乎成线形关系：Ｃ　４．５算法学习时间和训练数据集　

的大小成三次方关系．学习效率比较结果如表ｌ　

所示　

表ｌ不同分类算法学习效率比较　

４．２归纳能力　

比较实验采用】０次交叉确认方法Ｈ，确定每　

种算法的优劣。首先比较Ｃ　４．５、ＩＲＥＰ的归纳能　

力．ＩＲＥＰ错误率比Ｃ　４．５错误率高的次数有ｌ８　

次．而Ｃ　４．５错误率比ＩＲＥＰ错误率高的次数只有　９次，两者相同有９次　从实验结果可以看出，　

ＩＲＥＰ错误率较高，归纳能力较Ｃ　４．５差：　

采用相同的方法对Ｃ　４．５、ＲＩＰＰＥＲ的归纳能　

力进行比较．ＲＩＰＰＥＲ错误率比Ｃ　４．５错误率高的