（计算机软件与理论专业论文）基于正相关关联规则的分类算法.pdf

基于正相关关联规则的分类算法 摘要 分类是数据挖掘研究中的一个基本任务，关联规则挖掘是数据挖掘研究中的 一个重要领域，把关联规则挖掘用于分类问题开辟了数据分类的一条新路。常见 的基于关联规则分类算法通常在训练数据集上生成关联规则的全部集合，然后选 择个高质量的规则子集作为分类规则集去分类和预测测试数据集。 研究表明，基于关联规则分类具有高准确率和强适应性的特点。但是，在生 成的分类器中，往往会产生大量的分类规则，而其中很大一部分的分类规则可能 对分类并没有好处。并且，有时因为选取单一高置信度的规则，使分类结果产生 了过分拟合。因此，基于关联规则的分类算法，其关键在于分类器也就是分类规 则集的建立。而且对挖掘得到的分类规则集需要有不同的度量去评估其分类性 能。 如何产生更有意义的关联规则，如何使用有意义的关联规则对测试数据集进 行分类，是本文研究的主要内容。本文提出了一种新的关联分类算法c p c a r 。 该方法对f p g r o w t h 算法进行改进，在频繁项集产生的过程中，引入正相关性的 判断，使最后生成的频繁项集是正相关的。并使用正相关的频繁项集得到正相关 的初始分类规则集。为了提高分类准确率和效率，再利用置信度对初始分类规则 集进行规贝选取，生成由正相关关联规则组成的分类器。分类时，本文算法首先 在每个分类器中选取分类规则，这些分类规则可以分类测试事务，每条分类规则 都有一个夕权值，然后计算每个分类器中选取出的分类规则的权值和，比较权值 和最大的分类器的类标号与测试事务的类标号，两个类标号一致则表示分类正 确。最后根据正确分类的测试事务数与总测试事务数得出本文算法在某事务数据 集上的分类准确率。实验表明，虽然本文算法在生成分类规则集的时候，删除了 大量的关联规则，但是在u c i 机器学习的1 4 个数据集中，最终的分类准确率可 以与c a 5 和c m a r 相媲美，且算法运行的时间开销明显降低。 关键词：分类；频繁项集；关联规则；正相关 基于正相关关联规则的分类算法 a b s t r a c t c l a s s i f i c a t i o ni sab a s i ct a s ko fd a t am i n i n gr e s e a r c h ，a s s o c i a t i o nr u l em i u l n gi sa l l i m p o r t a n ta r e ao f d a t am i n i n gr e s e a r c h , c l a s s i f i c a t i o nb a s e do na s s o c i a t i o nr u l em i n i n g b r e a kan e wp a t hi nd a t ac l a s s i f i c a t i o n t h en o r m a lc l a s s i f i c a t i o nb a s e do na s s o c i a t i o n r u l ea l g o r i t h m su s u a l l ym i n ea l la s s o c i a t i o nr u l e ss e ti nt r a i n i n gd a t a b a s e t h e n 曲e y c l a s s i f yo rp r e d i c tt h et e s td a t a b a s eb yah i g hp 叮f 湎柚c ec l a s s i f i c a t i o nr u l es e t w h i c hi sc h o s e ni na 1 1a s s o e i a f i o nr u l e ss e t p r e v i o u ss t u d i e sp r o p o s et h a tc l a s s i f i c a t i o nb a s e do i la s s o c i a t i o nr u l eh a sh i 曲 c l a s s i f i c a t i o na c c u r a c ya n ds t r o n gf l e x i b i l i t y h o w e v e r , t h e r ea r eh u g ec l a s s i f i c a t i o n r u l e si nt h ec l a s s i f i e r , a n dt h em o s to fi ta r eh d p l e s si nc l a s s i f i c a t i o n a n d c l a s s i f i c a t i o nw i l lb eo v e r f i t t i n gs o m e t i m e ss i n c ei t i sb a s e do no n l ys i n g l e h i g h - c o n f i d e n c er u l e s ot h ek e yo f c l a s s i f i c a t i o nb a s e do na s s o c i a t i o nr u l ea l g o r i t h m s i st h ec o n s t r u c t i n go fc l a s s i f i e ri e c l a s s i f i c a t i o nr u l es e t w en e e dd i f f e r e n t m e a s u r e m e n t st oe v a l u a t et h ep e r f o r m a n c eo f t h ec l a s s i f i c a t i o nr u l es e t t h em a i nc o n t e n to f t h i sp a p e ra r eh o wt og e tm o r em e a n i n ga s s o c i a t i o nr u l e sa n d h o wt oe l a s s i f yt e s td a t a s e t sb yt h em e a n i n ga s s o c i a t i o nr u l e s i nt h i sp a p e r , w e p r o p o s ean e wa s s o c i a t i v ec l a s s i f i c a t i o na l g o r i t h m c p c a r , i e c l a s s i f i c a t i o nb a s e d o np o s i t i v e l yc o r r e l a t e da s s o c i a t i o nr u l e s t h ea l g o r i t h mi m p r o v e st h ef p g r o w t h a l g o r i t h m , i te s t i m a t e sp o s i t i v e l yc o r r d a t i o no ff r e q u e n ti t e ms e t sw h e nm e ya r e g o t t e n s ot h ef i n a lf r e q u e n ti t c m s e t si sp o s i t i v e l yc o r r e l a t e d t h ea l g o r i f l 1 = mc a ng e t t h eo r i g i n a lc l a s s i f i c a t i o nr u l e ss e tb yp o s i t i v e l yc o r r e l a t e df r e q u e n ti t c m s e t s ，f o r e n h a n c i n gt h ea c c u r a c ya n de f f i c i e n c yo fc l a s s i f i c a t i o n , t h ea l g o r i t h ms e l e c t st h e p r e d i c t i v er u l e si nt h eo r i g i n a lc l a s s i f i c a t i o nr u l es e tb yc o n f i d e n c et og e n e r a t e c l a s s i f i e r sw h i c ha r ec o m p o s e db yp o s i t i v e l yc o r r e l a t e da s s o c i a t i o nr u l e s 。w h e ni t c l a s s i f i e s ，a tf i r s t , t h ea l g o r i t h ms e l e c t sa l lr u l e sw h i c hc a nc l a s s i f yt e s tt r a n s a c t i o ni n e a c hc l a s s i f i e r s t h e ni tc o m p u t e st h es u m m a r yo fw e i g h t 它o fm u l t i p l es e l e c t e d p r e d i c t i v er u l e si ne a c hc l a s s i f i e r s , a n dc o m p a r e sc l a s sl a b e lo ft h ec l a s s i f i e rw h i c h w e i g h ts u m m a t i o ni sm a x i m a lw i t ht e s tt r a n s a c t i o n i ft w oc l a s sl a b e li st h es a m e , i t m e a n sc l a s s i f i c a t i o ni sr i g h t t h ea c c u r a c yo fc p c a ra l g o r i t h mi na 仃a n s a c t i o n 基于正相关关联规则的分类算法 d a t a b a s ec a nb eg o t t e nb yt h en u m b e ro fa c c u r a t e l yc l a s s i f i e dt e s tt r a n s a c t i o n sa n d t o t a lt e s tt r a n s a c t i o n s a l t h o u g ht h ea l g o r i t h md e l e t e sag r e a td e a lo fa s s o c i a t i v er o l e s w h e ng e n e r a t e st h ep r e d i c t i v er u l e ss e t s ，o u re x p e r i m e n t so n1 4d a t a b a s e sf r o mu c i m a c h i n el e a r n i n gd a t a b a s er e p o s i t o r ys h o wt h a tt h ef i n a la c c u r a c yo fc p c a ri sc l o s e t oc 4 5a n dc m a i lb u tt h et i m eo f a l g o r i t h mc i r c u l a t i o nh a sb e e nr e d u c e do b v i o u s l y k e yw o r d s ：c l a s s i f i c a t i o n ；f r e q u e n ti t e m s c t s ；a s s o c i a t i o nr u l e s ；p o s i t i v e l y m 基于正相关关联规则的分类算法 1 1 1 研究背景及意义 第一章引言 分类是数据分析的一种重要形式，也是数据挖掘研究中的一个基本任务，可 以用于提取描述重要数据类的模型或预测未来的数据趋势。关联规则挖掘是数据 挖掘研究中的一个基本任务，同时是一个高度活跃的领域，把关联规则挖掘用于 分类问题开辟了数据分类的一条新路。 基于关联规则的分类算法，其关键在于分类器也就是分类规则集的建立。对 挖掘得到的关联规贝目即用于分类的分类规则，我们需要有不同的度量。对关 联规则的度量常使用支持度一置信度框架。但基于支持度一置信度的关联规则挖 掘可能产生负相关的关联规则。因此，考虑关联规则的相关性将会使挖掘得到的 关联规则更有趣、更有意义。 目前利用关联规则进行数据分类已经产生了不少成熟算法，其中的某些算法 无论在时间复杂度、空问复杂度还是分类的准确率上都比传统的分类算法有相当 程度的提高。在这些算法中，有些考虑到了规则前件( 属性集合) 和规则后件( 类 标号) 的相关性，使挖掘到的带有类标号的关联规则更有意义。但是这些算法都 没有考虑到规则前件( 属性集合) 中的属性之间的相关性，因此产生的用于分类 的关联规则可能是没有意义的。当这些算法用于数据量和维数都非常大的数据库 时，产生的用于分类的关联规则很容易规模巨大，而其中很大一部分的分类规则 可能对分类并没有好处。因此，如何产生更有意义的关联规则，如何使用有意义 的关联规则对测试数据集进行分类，是本文研究的主要内容。 1 2 本文的主要工作 本文根据当前的实际需要并结合国内外在基于关联规则分类方面的研究进 展和研究成果，对如何在分类规则集产生的过程中进行相关性判断进行了研究， 并在此基础上提出了一种新的基于正相关关联规则的算法c p c a r 算法。 本文的主要工作包括以下几个方面： ( 1 ) 对常见的分类算法进行分析，总结它们的优缺点，阐述进行相关性判断 基于芷相关关联规则的分类算法 对产生分类规则集的必要性； ( 2 ) 对正相关频繁项集的概念进行说明。并介绍了几种相关性的度量策略， 对这几种度量策略的特点进行了分析； ( 3 ) 改进了一种直接在f p 一树中挖掘频繁项集的算法，产生正相关的分类规 则，并在正相关关联规贝u 上利用置信度进行规则选取，生成分类器，使用分类器 对测试数据集进行了分类； ( 4 ) 对该算法的性能进行了实验分析。 本文以产生分类规则过程中的相关性判断为中心，研究了相关分析和相关性 度量，提出了新的分类算法，并用实验证明了该算法的正确性和有效性。 1 3 本文的内容组织 围绕前述研究内容，本文各章节安排如下： 第一章为本文的引言部分。介绍了课题研究的背景及意义，给出了论文的主 要工作以及本文的组织结构。 第二章介绍了常见的基于关联规则的分类算法，并详细介绍了两种最主要的 用于基于关联规则分类的分类器的产生算法。 第三章是关联规则的相关性分析，说明了正相关关联规则的概念，并对常见 的相关性度量做出了简要介绍。 第四章按照一般基于关联规则的分类算法的步骤，对本文算法做出了思想描 述和代码分析。 第五章是实验结果和分析，选择了多个测试数据集和多个基于关联规则的分 类算法作为实验数据对比，最后比较了算法的性能。 第六章是总结和工作展望，对本文的工作做了总结，并且对下步需要继续 研究的问题进行了探讨。 最后是本文的参考文献、致谢及附录。 基于正相关关联规则的分类算法 第二章基于关联规则的分类 2 1 数据挖掘中的分类方法 2 1 1 基于决策树的分类 基于决策树的分类算法是数据挖掘中最为典型的分类算法。决策树 ( d e c i s i o nt r e e ) 是一个类似于流程图的树结构，其中每个内部节点表示在一 个属性上的测试，每个分枝代表一个测试输出，而每个叶节点代表类或类分布。 基于决策树的分类算法的基本思想是开始时所有的训练样本在根部，基于最 高信息增益( i n f o r m a t i o n g a i n ) 自顶向下递归地划分数据集，生成决策树。当 一个结点上所有样本都属于同一类或者没有剩余属性可以用来进一步划分样本 时停止划分，形成一个叶结点。如果叶结点上的样本不属于同一类，则根据大多 数样本的分类来确定叶结点的类别。 当决策树创建时，由于数据中的噪声和孤立点。许多分枝反映的是训练数据 集中的异常。剪枝方法可以剪去不可靠的分枝，这将导致较快的分类，提高树独 立于测试数据集正确分类的能力。常用的剪枝方法有：先剪枝( p r e p r u n j n g ) 和 后剪枝( p o s t p r u n i n g ) 。前者通过提前停止树的构造而对树剪枝；后者在完全创 建好的树上剪去分枝。 决策树很擅长处理非数值型数据，其主要优点是描述简单，分类速度快，特 别适合大规模的数据处理。最为典型的决策树学习算法是i d 3 ，它采用自顶向下 不回溯策略，能保证找到一个简单的树。算法c 4 5 和c 5 0 都是i d 3 的扩展，它 们将分类领域从类别属性扩展到数值型属性。常见的决策树算法还有c a r t ， c h a i d ，q u e s t 和c 5 0 等。 从决策树中可以方便地提取分类规则。对从根到树叶的每条路径以i f - t h e n 形式表示一条分类规则，沿着给定路径上的每个属性一值对形成规则前件的一 个合取项，叶结点包含类预测，形成规则后件。 基于正相关关联规则的分类算法 2 1 2 贝叶斯分类 贝叶斯分类( b a y e s i a nc l a s s i ，i c a t i o n ) 也是一种常用的分类方法，它是 一种对属性集和类变量的概率关系建模的方法，其理论基础是贝叶斯定理： p ( c i x ) = 眢 其中j 是类标号未知的数据样本。设c 为某种假定，如数据样本j 属于某特 定类则p ( o 为c 成立的概率，也称为类f 的先验概率( p r i o r p r o b a b i l i t y ) 尸( 为j 的支持度。尸( d 是规定数据样本七假定c 成立的概率，称作类f 的 后验概率( p o s t e r i o rp r o b a b i l i t y ) 。尸( 卅o 是假定c 成立的情况下，样本z 的支持度，也称为类条件概率( 吒锄以 j 删jp r o b a b i l i t y ) 。 准确估计类标号和属性值的每一种可能组合的后验概率非常困难，因为即便 属性数目不是很大，仍然需要很大的训练集。此时，贝叶斯定理很有用，因为它 允许我们用先验概率尸( d 、类条件概率尸( 州口和尸( 来表示后验概率。 在比较不同类c 的后验概率时，分母尸( 肋总是常数，因此可以忽略。先验 概率尸( d 可以通过计算训练集中属于每个类的训练记录所占的比例很容易地估 计。因此类f 的后验概率以卅乃的确定取决于对类条件概率尸( 卅d 的估计。对 类条件概率尸( 州d 的估计，常使用两种贝叶斯分类方法来实现：朴素贝叶斯分 类和贝叶斯信念网络。 2 1 2 1 朴素贝叶斯分类 如果训练数据集具有许多属性，即j = 知x 2 , ，蔚，每个样本j 有n 个属 性。给定类标号a 此时计算类条件概率以州o 的开销可能非常大。为降低计算 类条件概率尸( 卅o 的开销，可以做出类条件独立的朴素假定。 给定样本的类标号c 假定属性值相互条件独立，即在属性间不存在依赖关 系，这时： p ( x i c ) = 兀p ( 以l c ) 概率尸( 厨i o ，尸( 局f 0 ，尸( 五i o 可以由训练样本估值。这种假设类条件独立 基于正相关关联规则的分类算法 的贝叶斯分类方法称作朴素( n a i v e ) 贝叶斯分类。 有了条件独立假设，在进行朴素贝叶斯分类时，就不必计算j 的n 个属性的 每一种组合的类条件概率，只需对给定的类标号g 计算每一个五的条件概率 以jo 就可以得到类条件概率尸( 州d 。这样就不需要很大的训练集就能获得较 好的概率估计。因为对于每个类标号a 尸( 国是固定的，因此只要找出使分子 以州d 以0 最大的类标号就足够了。 使用朴素贝叶斯分类方法获得的分类器面对孤立的噪声点是健壮的，因为在 从数据中估计条件概率时，这些点被平均分布：面对无关属性是健壮的，因为如 果噩是无关属性，那么尸( 西5d 几乎变成了均匀分布，盂的类条件概率不会对总 的后验概率的计算产生影响；但是相关属性可能会降低朴素贝叶斯分类器的性 能，因为对这些属性，条件独立的假设已不成立。 2 1 2 2 贝叶斯信念网络 朴素贝叶斯分类假定类条件独立，即给定样本的类标号，属性的值相互条件 独立。这一假定简化了计算，但是实际中变量之间完全可能存在依赖关系。贝叶 斯信念网络( b a y e s i a nb e l i e fn e t w o r k s , 届函d 不要求给定类的所有属性都条 件独立，而是允许指定哪些属性条件独立。 贝叶斯信念网络是用图形表示一组随机变量之间的概率关系。它有两个主要 成分：一个有向无环图，表示变量之间的依赖关系；一个概率表，把各结点和它 的直接父结点关联起来。 贝叶斯信念网络有一个重要的性质：贝叶斯信念网络中的一个结点，如果它 的父母结点已知，则它条件独立于它的所有非后代结点。因此朴素贝叶斯分类器 中的条件独立假设也可以用贝叶斯信念网络来表示。 贝叶斯网络的建模包括两个步骤：创建网络结构；估计每一个结点的概率表 中的概率值。网络拓扑结构可以通过对主观的领域专家知识编码获得。 2 1 3 人工神经网络 经常用于分类的还有人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 方法。 神经网络为解决大复杂度问题提供了一种相对来说比较有效的简单方法，它是模 基于正相关关联规则的分类算法 仿入脑神经网络的结构和某些工作机制而建立的一种非线形预测模型，经过学习 进行模式识别的。其工作机理是通过学习改变神经元之间的连接强度。神经网络 有前向神经网络、反馈神经网络、自组织神经网络等，在神经网络中，由权重和 网络的拓扑结构决定了它所能识别的模式类型。 人工神经网络具有如下特点： 1 人工神经网络可以用来近似任何目标函数。由于人工神经网络具有丰富的 假设空间，因此对于给定的问题，选择合适的拓扑结构来防止模型的过分拟合是 很重要的。 2 人工神经网络可以处理冗余特征。因为权值在训练过程中自动学习，冗余 特征的权值非常小。 3 人工神经网络对训练数据中的噪音非常敏感。处理噪音问题的一种方法是 使用确认集来确定模型的泛化误差，另一种方法是每次迭代把权值减少一个因 子。 4 人工神经网络权值学习使用的梯度下降方法经常会收敛到局部最小值。 5 训练人工神经网络是一个很耗时的过程，特别是当隐藏结点数量很大时。 然而，测试样例分类时非常快。 最流行的神经网络学习算法是后向传播算法( 屁幽t op r o p a g a t i o n a l g o r i t 细) 。后向传播算法是在多层前馈( f e e d - f o u w r a r d ) 神经网络上进行学习 的。这种神经网络具有一个输入层和一个输出层，在两者之问可能包含多个中间 层，这些中间层叫做隐藏层。后向传播通过迭代地处理一组训练样本，将每个样 本的网络预测与实际知道的类标号比较，进行学习。对于每个训练样本，修改权 值，使得网络预测和实际类之间的均方误差最小。这种修改后向进行，即由输出 层，经由每个隐藏层，到第一个隐藏层。一般的，权将最终收敛，学习过程停止。 算法的每一次迭代包括两个阶段：前向阶段和后向阶段。在前向阶段，使用前一 次迭代所得到的权值计算网络中每一个神经元的输出值。计算是向前进行的，先 计算第k 层神经元的输出，再计算第七吖层的输出。在后向阶段，以相反的方向 应用权值更新公式，先更新詹吖层的权值，再更新第七层的权值。 基于正相关关联规则的分类算法 2 1 4 最近邻分类 基于决策树的分类算法是积极学习方法( e a g e rl e a r n e r ) 的例子，因为一 旦训练数据可用，它们就开始学习从输入属性到类标号的映射模型。一个相反的 策略是推迟对训练数据的建模，直到需要分类测试样例时再进行。采用这种策略 的技术被称为消极学习方法( 1 a z yl e a r n e r ) 。最近邻( n e a r e s tn e i g h b o r ) 分 类方法就是一种消极学习方法。该方法是找出和测试样例的属性相对接近的所有 训练样例，这些训练样例称为最近邻。最近邻分类把每个样例看作d 维空间上的 一个数据点，其中d 是属性个数。给定一个测试样例，使用一种邻近性度量，通 常采用欧几里德距离作为度量，计算该测试样例与训练集中其它数据点的邻近 度。给定样例z 的肛最近邻是指和z 距离最近的k 个数据点。预分类样本点根 据其近邻的类标号进行分类。如果数据点的近邻中含有多个类标号，则将该数据 点指派到其最近邻的多数类。 k 值的选取很重要，如果k 太小，训练数据中的噪声可能产生的过分拟合， 最近邻分类器容易因此受到影响。相反，如果k 太大，最近邻分类器可能会误分 类测试样例，因为最近邻列表中可能包含远离其近邻的数据点。 最近邻分类是一类更广泛的技术的一部分，这种技术称为基于实例的学习， 它使用具体的训练实例进行预测，而不必维护数据的抽象( 或模型) 。基于实例 的学习算法需要一个相近性度量来确定实例间的相似性或距离，还需要一个分类 函数根据测试实例与其它实例的邻近性返回测试实例的预测类标号。像最近邻分 类器这样的消极学习方法不需要建立模型。然而，分类一个测试样例开销很大， 因为我们需要逐个计算测试样例和训练样例之间的相似度。最近邻分类器基于局 部信息进行预测，正是因为这样的局部分类决策，最近邻分类器 很小时) 对噪 声非常敏感。最近邻分类器可以生成任意形状的决策边界，这样的决策边界能提 供更加灵活的模型表示。最近邻分类器的决策边界还有很高的可变性，因为它们 依赖于训练样例的组合。增加最近邻的数目可以降低这种可变性。除非采用适当 的邻近性度量和数据预处理，否则最近邻分类器可能做出错误的预测。 基于正相关关联规则的分类算法 2 1 5 支持向量机 支持向量机( s u p p o r tg e c t o tm a c h i n e , s 啪已经成为一种倍受关注的分 类技术。这种技术具有坚实的统计学理论基础，并在许多实际应用( 如手写数字 的识别、文本分类等) 中取得了理想的结果。支持向量机可以很好的应用于高维 数据，避免了维灾难问题。这种方法具有一个独特的特点，它使用训练实例的一 个子集称作支持向量( s u p p o r tv e e t o r ) ，来表示决策边界。 假设一个数据集只包含属于两个不同类的样本，分别用方框和圆圈表示。这 个数据集是线性可分的，即可以找到这样一个超平面，使得所有的方框位于这个 超平面的一侧，而所有的圆圈位于它的另一侧。然而可能存在无穷多个这样的超 平面。虽然它们的训练误差都等于零，但是不能保证这些超平面在未知实例上运 行同样好。根据在检验样本上的运行效果，分类器必须从这些超平面中选择一个 来表示它的决策边界。 假设某个决策边界占能准确无误地将训练样本划分到各自的类中。曰对应着 一对超平面，分别记为6 j 和6 其中，6 是这样得到的；平行移动一个和决策 边界平行的超平面，直到触到最近的方框为止；类似地，平行移动一个和决策边 界平行的超平面，直到触到最近的圆圈，可以得到6 & 这两个超平面之间的间 距称为分类器的边缘。直观的，具有较大边缘的决策边界比那些具有较小边缘的 决策边界具有更好的泛化误差。因为如果边缘比较小，决策边界任何轻微的扰动 都可能对分类产生显著的影响。因此，那些决策边界边缘较小的分类器对模型的 过分拟合更加敏感。从而在未知的样本上的泛化能力很差。线性支持向量机 ( 1 i n e a r s v 翻o 就是寻找具有最大边缘超平面的一种分类器，以确保最坏情况下 的泛化误差最小。 支持向量机具有许多很好的性质，因此它已经成为最广泛使用的分类算法之 一。支持向量机可以利用已知的有效算法发现目标函数的全局最小值。而其它的 分类算法，如人工神经网路算法，采用一种基于贪心学习的策略来搜索假设空间， 这种方法一般只能获得局部最优解。支持向量机通过最大化决策边界的边缘来控 制模型的能力，但用户必须提供其它参数。通过对数据中每个分类属性值引入一 个哑变量，支持向量机可以应用于分类数据。 基于正相关关联规则的分类算法 2 1 6 其他分类方法 另外，还用于数据分类的一些方法有：基于案例的推理( c a s e - b a s e d r e a s o n i n g , 删) 分类法、遗传算法( g e n e t i ca l g o r i t h m ) 。 2 1 6 1 基于案例的推理分类法 基于案例的推理分类法是基于要求的，其存放的样本是复杂的符号描述。当 给定一个待分类的新案例时，基于案例的推理首先检查是否存在一个同样的训练 案例。如果找到一个，则返回附在该案例上的解。如果找不到同样的案例，则基 于案例的推理将搜索具有类似于新案例成分的训练案例，这些训练案例可视为新 案例的邻接者。 2 1 6 2 遗传算法 遗传算法结合了自然进化的思想。遗传学习开始时创建了一个由随机产生的 规则组成的初始群体，每个规则可以用一个二进制位串表示。根据适者生存的原 则，形成由当前群体中最适合的规则组成的新群体，以及这些规则的后代。后代 通过使用诸如交叉和变异等遗传操作来创建。由先前的规则群体产生新的规则群 体的过程继续进化，直到群体中每个规则满足预先指定的适合度阈值。 2 2 基于关联规则的分类 基于关联规则的分类方法是一种使用一组关联规则来分类事务的技术。每一 个分类规则可以表示为如下形式： 规则左边称为规则前件( r u l ea n t e c e d e n t ) 或前提( p r e c o n d i t i o n ) ，它是 属性测试的合取。规则右边称为规则后件( r u l ec o n s e q u e n