（计算机软件与理论专业论文）基于jep的分类算法研究.pdf

基于i e p 的分类算法研究 摘要 f 数据丰富而知识贫乏的状况导致了数据挖掘的出现，并且在短短 的几年内，引起了许多领域的人们的极大兴趣。分类作为数据挖掘的 一个重要主题，在统计学、机器学习、神经网络和专家系统中得到了 较早的研究，但其中大部分都是内存驻留算法，通常假定数据量很小。 随着数据库中数据量和维数越来越大，建立高效的、适用于大型数据 库的分类算法已成为数据挖掘的一个挑战性问题。， 近年来，数据挖担界提出一种新的知识模式，称作跳跃显露模式 ( j u m p i n g e m e r g i n gp a t t e r n s ，j e p ) ，用来表示两个数据集之间的重大 差异。并且，建立了一些基于j e p 的分类算法。研究表明，这些基于 j e p 的分类算法具有很好的预测准确性，并且在数据量和维数上都是 可规模化的。 但是，这些基于j e p 的分类算法通常需要挖掘大量的j e p ，因此 影响了它们的效率，并增加了分类算法的复杂性。本文提出一种特殊 类型的j e p ，称作最有效的跳跃显露模式( m o s ts i g n i f i c a n tj u m p i n g e m e r g i n gp a t t e r n s ，s j e p ) 。分析结果表明，s j e p 具有很强的区分能力， 足以用来建立精确的分类算法。由于已有的算法都不能直接挖掘这种 s j e p ，本文给出了一种可以在两个数据集上双向挖掘s j e p 的有效算 法，并讨论了如何建立基于s j e p 的分类算法( s j e pc l a s s i f i e r ) 。 与已有的基于j e p 的分类算法相比，仅使用s j e p 建立的分类算 法使用的j e p 数量少得多，不仅能够获得相同或更高的预测精度，而 且可以在很短的时间内( 通常为若干秒) 完成学习阶段。实验结果表 明，本文的分类算法( s j e p 一c l a s s i f i e r ) 在平均预测精度方面也优于c b a 和c 4 ，5 等分类算法。 苎! 竺塑坌鲞竺鲨! ! 壅一 a b s t r a c t d a t am i n i n gr e s u l t sf r o mt h es i t u a t i o nd e s c r i b e da s d a t ar i c hb u t i n f o r m a t i o np o o r ，a n dw i t h i no n l ys e v e r a ly e a r s ，h a sa t t r a c t e dm a n yp e o p l e i nd i f l 、e r e n tf i e l d s c l a s s i f i c a t i o n ，a sa l li m p o r t a n tt h e m ei nd a t am i n i n g ， h a sb e e nr e s e a r c h e de a r l i e ri ns t a t i s t i c s ，m a c h i n el e a r n i n g ，n e r v en e ta n d e x p e ns y s t e m s b u t m o s t a l g o r i t h m s a r e m e m o r yr e s i d e n t ，t y p i c a l l y a s s u m i n g as m a l ld a t as i z e w i t ht h eg r o w t ho fd a t ai nv o l u m ea n d d i m e n s i o n a l i t y , i th a sb e c o m eav e r yc h a l l e n g i n gp r o b l e m t ob u i l da n e f f i c i e n tc l a s s i f i e rf o r l a r g ed a t a b a s e s j u m p i n ge m e r g i n gp a t t e r n s ( j e p s ) ，an e w k i n do f k n o w l e d g ep a t t e r n s w e r er e c e n t l yp r o p o s e dt oc a p l u r es o m ec r u c i a ld i f f e r e n c eb e t w e e nap a i r o fd a t a s e t sa n ds o m ej e p b a s e dc l a s s i f i e r sw e r eb u i l t p r e v i o u ss t u d i e s s h o wt h a tt h o s ej e p - b a s e dc l a s s i f i e r sh a v e g o o d o v e r a l l p r e d i c t i v e a c c u r a c ya n d a r es c a l a b l eo nd a t av o l u m ea n dd i m e n s i o n a l i t y b u tt h e ys u f f e rf r o mt h el a r g en u m b e ro fm i n e dj e p s ，w h i c hm a k e s t h ec l a s s i f i e r sc o m p l e x i nt h i sp a p e r ，w ep r o p o s eas p e c i a lt y p eo fj e p s ， t h em o s t s i g n i f i c a n tj u m p i n ge m e r g i n gp a t t e r n s ( s j e p s ) ，w h i c h a r c b e l i e v e dt oh a v e s t r o n gd i s c r i m i n a t i n gp o w e r a n da r es u f f i c i e n tf o r b u i l d i n g a c c u r a t ec l a s s i f i e r s a n dw ep r e s e n t an o v e l a l g o r i t h m t o e f f i c i e n t l ym i n es j e p so fb o t hd a t ac l a s s e s ，b e c a u s ee x i s t i n ga l g o r i t h m s c a n td i r e c t l ym i n es u c hs j e p s t h e nw ei n t r o d u c eh o wt ob u i l dan e w c l a s s i f i e r ( s j e p c l a s s i f i e r ) b a s e do n s j e p c o m p a r e dw i t hp r e v i o u sj e p b a s e dc l a s s i f i e r s ，t h e c l a s s i f i e rb a s e d e x c l u s i v e l yo ns j e p s ，w h i c h u s e sm u c hf e w e rj e p s ，c a nn o to n l ya c h i e v e a l m o s tt h es a r n eo rh i g h e rp r e d i c t i v ea c c u r a c y ，b u ta l s of i n i s hl e a r n i n g p h a s e i nv e r ys h o r tt i m e ( u s u a l l yi naf e ws e c o n d s ) a sh a sb e e ns h o w ni n o u re x p e r i m e n t a lr e s u l t s ，o u rc l a s s i f i e ro u t p e r f o r m sb o t hc b aa n dc 4 5 g e n e r a l l yi nt e r m so fa v e r a g ea c c u r a c y 2 基于j e p 的分类算法研究 第一章引言 在过去的数十年中，我们产生羽收集数据的能力已经迅速提高。起作用的 圆素包括条码在火部分商业产品中的广泛使用，许多商务、科学和行政事务的 计算机化。以及由文本和图像扫描平台到卫星遥感系统的数据收集工具的进步。 此外，作为全球信息系统的万维网的流行，已经将我们淹没在数据和信息的汪 洋大海中。尽管很早就出现了简单的数据统计技术，但先进的智能数据分析工 具尚未成熟。因此，在数据生成和数据理解之间存在很大的差距。 存储数据的爆炸性增长业已激起对新技术和自动工具的需求，以帮助我们 将海鼍数据转换成信息和知识。于是，数据挖掘由大量数据中，用非平凡 的方法发现有用的知识就成了一种自然的需求。正是这种需求引起了人们 的广泛关注，导致了数据挖掘研究的蓬勃开展。 数据分类是数据挖掘中的一个重要问题，它是指在数据库的各个对象中找 出共同特性，并按照分类模型把它们进行分类。国内外的研究人员在数据挖掘、 统计分析、机器学习、神经网络、专家系统等领域中对分类问题进行了大量的 研究，提出了一系列的分类算法。近年米，数据分类技术已被广泛、有效地应 用于科学实验、医疗诊断、气象预报、商业预测、案件侦破等领域，引起了工 业界和学术界的极大关注。 在本章中，我们将详细介绍有关分类的问题，包括什么是分类，分类的基 本技术、分类的准确性和分类算法的比较标准，并给出本文的研究内容与成果， 以及本文j 勺结构安排。 1 1 什么是分类 数据分类是一个两步过程：第一步，建立一个模型，描述预定的数据类或 概念集。通过分析由属性描述的数据库元组来构造模型。假定每个元组属于一 个预定义的类，由一个称作类标号的属性确定。对于分类，数据元组也称作样 本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。训l 练数据 集中的单个元组称作训练样本，并随机地由样本群选取。由于提供了每个训练 样本的类标号，该步骤也称作有指导的学习( 即在被告知每个训练样本属于哪 个类的“指导”下进行模型的学习) 。它不同于无指导的学习( 或聚类) ，在那 里，每个训练样本的类标号是未知的，要学习的类集合或数量也可能事先不知 道。 通常，学习模型用分类规则、决策树或数学公式的形式提供。例如，给定 一个顾客信用信息的数据库，可以学习分类规则，根据他们的信誉度( 如优或 相当好) 来识别顾客。该规则可以用来为以后的数据样本分类，也能对数据库 的内容提供更好的理解。 第二步，使用模型进行分类。首先评估模型( 分类算法) 的预测准确率。 基于j e p 的分类算法研究 保持方法是一种使用类标号样本测试集的简单方法。这些样本随机选取，并独 立于i jj l g s ；样本。对于每个测试样本，将已知的类标号与该样本的学习模型类预 测比较。被模型正确分类的测试样本的百分比就是模型在给定测试集上的准确 率。注意，如果模型的准确率根据训练数据集评估，评估可能是乐观的，因为 学习模型倾向于过分适合数据( 即，它可能并入训练数据中某些异常，这些异 常不出现在总体样本群中) 。因此，使用测试集来评估分类算法的准确率。 1 2 分类的基本技术 目前，已发表的分类的基本技术已有很多，本节将介绍一些常用的技术，如 基于决策树的分类、贝叶斯分类和基于神经网络的分类，以及基于源于关联规 则挖掘概念的分类。 1 2 1 基于决策树的分类 基于决策树的分类方法是一种监督学习的方法，树的数量决定于分类的精 度和树的大小。这种方法首先选择训练样本的一个子集以形成个决策树，如 果此树没有为所有的对象给出个正确的答案将例外情况加入到树中，不断 重复这一过程直剑发现正确的决定集。最终将形成这样一株树：每一片叶子代 表个类名，每个内部节点描述一个属性，节点的每一个分支对应于该属性的 每一个可能的值。 决策树的算法有很多，1 9 8 6 年j r o s sq u i n l a n 提出了i d 3 算法。这是国际 上晟早、最有影响力的决策树算法。| d 3 算法是基于信息熵的决策树分类算法， 根据属性集的取值选择实例的类别。它采用自顶向下不可返回的策略，挫出全 部空间的一部分，它确保决策树建立最简单，每次所做的测试数据最少。i d 3 算法构造的决策树平均深度较小，分类速度较快。 i d 3 的不足之处：( 1 ) i d 3 算法偏向于选择属性较多的属性，而属性较多的 属性却不总是最优的属性。( 2 ) 学习简单的逻辑表达能力较差。( 3 ) 注意力集 中在属性的选择上，而最近有研究者认为属性选择对决策树的精度影响不大， 这一问题至今仍无定论。 自i d 3 出现后，研究人员围绕该算法展开了大量的研究，提出了许多富有 成效的改进、优化算法。其工作主要集中在如下几个方向：( 1 ) 扩充决策树属性 的取值范围及改进选择分离属性的选择：( 2 ) 提高决策树构造效率，削减数据库 遍历次数，减少i o 操作；( 3 ) 优化决策树，简化决策树输出；( 4 ) 扩充决策树， 形成决策图：( 5 ) 将遗传算法、神经网络技术引入决策树算法。 1 9 9 6 年，j r o s sq u i n l a n 对i d 3 算法进行了补充和改进，提出了后来非常流 行的c 4 5 算法。该算法是一种归纳学习算法，先从所有的事例中选取一部分构 造决策树，再用剩下的事例测试决策树并对它进行调整。它不仅能处理连续属 性，还可以对属性的取值集合进行等价类划分，划分在同一类的属性值在进行 4 基十j e p 的分类算法研究 判断时走向同一分支。 c 45 算法不足之处：( 1 ) c 4 5 算法采用分而治之的策略所得到决策树不一 定是最优的；( 2 ) 决策树的结构调整、性能改善较困难；( 3 ) 仅考虑决策树的 错误率，未考虑树的节点、深度，而树的结点个数代表了树的规模，树的平均 深度对应着决策树的预测速度；( 4 ) 对属性值分组时逐个探索，分组效率较低。 无论是i d 3 算法，还是c 4 5 算法，对于相对小的数据集是很有效的。当这 些算法用于非常大的、现实世界数据库的挖掘时，有效性和可规模性就成了关 注的问题。大部分决策树算法都限制训练样本驻留主存。在数据挖掘应用中， 包含数以百万计样本的非常大的训练数据集是很普通的。因此，这一限制就制 约了这些算法的可规模性。由于训练样本在主存和高速缓存换进换出，决策树 的构造可能变得效率低下。 由大型数据库构造决策树的早期策略包括对连续属性离散化，在每个结点 对数据选样。然而，这些仍然假定训练集可以放在主存。一种替代的方法是： 首先，将样本划分成子集，使得每个子集可以放在内存；然后，由每个子集构 造一棵决策树；最后，输出的分类法将由每个子集得到的分类法组合在一起。 尽管该方法可以用于大数据集的分类，其分类的准确性不如一次使用所有的数 据的方法高。 最近，已经提出了一些决策树算法，它们强调可规模性。由非常大的训练 数据集进行决策树归纳的算法包括s l i q 和s p r i n t ；它们都能处理分类属性 和连续属性。这两种算法都使用了预排序技术，对非常大，而不能放入内存的 驻留磁盘的数据集进行预排序。两种算法都定义使用新的数据结构，以利于树 的构造。s l i q 使用若干驻留磁盘的属性表和单个驻留主存的类表。每一个属性 具有一个属性表，由r i d ( 记录标识) 建立索引。每个元组由一个从每个属性 表的一个表目到类表的一个表目( 存放给定元组的类标号) 的链接表示。而类 表表目链接到它在决策树中对应的叶子结点。类表驻留在主存，因为决策树的 构造和剪枝时，经常访问它。类表的大小随训练集中元组数目成比例增长。当 类表不能放在主存时，s l i q 的性能下降。 s p r i n t 使州不同的属性表数据结构，存放类利r i d 信息。当结点分裂时， 属性表被相应划分，并在结果子女中分布。当表划分时，表中记录的次序维持 不变。冈此，划分表不需要重新排序。s p r i n t 的设计易于并行，这就进一步增 强了可规模性。 当s l l q 和s p r i n t 处理的驻留磁盘的数据太大，不能一次装入内存时， s l i q 的可规模性受限于它所使用的常驻内存的数据结构。s p r i n t 消除了所有 的内存限制，但仍然需要使用正比例于训练集的散列树。随着训练集的增长， 这可能变得代价昂贵。 雨林是用于可规模化的决策树归纳的框架。该方法适合有大量可用的内存， 并_ _ i 于任意决策树归纳算法。它使用一个a v c 集( 属性值类标号) ，指示每个 基于j e p 的分类算法研究 属性类分布。据称，雨林的速度超过s p r ! n t 。 1 2 2 贝叶斯分类 贝叶斯分类是统计学分类方法，它基于贝叶斯定理。可以预测类成员关系 的可能性，如给定样本属于一个特定类的概率。 分类算法的比较研究发现，一种称作朴素贝叶斯分类的简单贝叶斯分类算 法可以与决策树和神经网络分类算法相媲美。朴素贝叶斯分类假定一个属性值 对给定类的影响独立f 其它属性的值。该假定称作类条件独立。做此假定是为 了简化所需计算，并在此意义f 称为“朴素的”。 贝叶斯分类还可以用来为不直接使用贝叶斯定理的其它分类算法提供理论 决镱。例如，在某种假定下，可以证明正如朴素贝丌1 + 斯分类一样，许多神经网 络和曲线拟合算法输出最大的后验假定。 理论上讲，与其它所有分类算法相比，该分类具有最小的出错率。然而， 实践中并非总是如此。这是由于对其应用的假定( 如，类条件独立性) 的不正 确性，以及缺乏可用的概率数据造成的。 不象朴素贝叶斯分类，贝叶斯信念网络能表示属性子集间的依赖。贝叶斯 信念网络说明联合概率分布。它允许在变量的子集间定义类条件独立性。它提 供一种因果关系的图形，可以在其上进行学习。在学习或训练信念网络时，许 多情况都是可能的。网络结构可能预先给定，或由数据导出。网络变量可能是 可见的，或隐藏在所有或某些训练样本中。隐藏数据的情况也称为空缺值或不 完全数据。如果网络结构已知并且变量是可见的，训练网络是直接了当的。该 过程由计算c p t 项组成，与朴素贝1 1 - i 斯分类涉及的计算概率类似。当网络结构 给定，而某些变量是隐藏的时，则可使用梯度下降方法训练信念网络。 贝叶斯网络的研究在国外十分广泛，它可以对不确定性知识进行推理。例 如：医生看病，根据病人的症状，判断病人是否得了某种疾病，往往是一种不 确定的推理( 带概率的推理) ，多数情况下没有百分之百的把握。运用贝1 11 斯网 络进行推理，可以达到较好的效果。 1 2 3 基于神经网络的分类 神经网络最早是由心理学家和神经学家提出的，旨在寻求开发和测试神经 的计算模拟。粗略地说，神经网络是一组连接的输入输出单元，其中每个连接 都与一个权相联。在学习阶段，通过调整神经网络的权，使得能够预测输入样 本的正确类标号来学习。由于单元之间的连接，神经网络学习又称连接者学习。 神经网络需要很跃的训练时间，因而对于有足够长训练时间的应用更合适。 神经网络已经在很多领域得到了成功的应用，但由于缺乏严密的理论体系的指 导，其应用效果完全取决于使用者的经验。虽然h o r n i k 等人证明，仅有一个非 线性隐层的前馈网络就能以任意精度逼近任意复杂度的函数，但一些研究者指 6 拱于j e p 的分类算法研究 出对网络的配置和训练是n p 问题。在实际应j l f j 中，由于缺乏问题的先验知识， 往往需经大量费力耗时的实验摸索才能确定合适的神经网络模型、算法以及参 数殴苴，其应用效果完全取决于使用者的经验。即使采用同样的方法解决同样 的问题，由于操作者不同，其结果也很可能大相径庭。另外，由于人们很难解 释蕴涵在学习权之中的符号含义，神经网络常常因其可解释性差而受到批评。 这些特点使得神经网络在数据挖掘的初期并不看好。 然而。神经网络的优点包括其对噪音数据的高承受能力，以及它对未经训 练的数据的分类能力。此外，最近已提出了一些由训练过的神经网络提取规则 的算法。这些因素推动了神经网络在数据挖掘分类方面的应用。 最流行的基于神经网络的分类算法是8 0 年代提出的后向传播算法。该算法 通过迭代地处理一组训练样本，将每个样本的网络预测与实际知道的类标号比 较，进行学习。对于每个训练样本，修改权，使得网络预测和实际类之间的均 方误差最小。这种修改“后向”进行。即，由输出层，经由每个隐藏层，到第 一个隐藏层( 因此称作后向传播) 。尽管不能保证，一般地，权将最终收敛，学 习过程停止。可以由训练的神经网络提取规则，帮助改进学习网络的可理解性。 1 2 4 基于源于关联规则挖掘概念的分类 关联规则挖掘是数据挖掘研究的一个重要的、高度活跃的领域。最近，数 据挖掘技术业已将关联规则挖掘用于分类问题。本节，我们按历史次序介绍三 种方法。前两种方法，a r c s 和关联分类使用关联规则分类。第三种方法c a e p 挖掘“显露模式”，它考虑挖掘关联规则使用的支持度概念。 第一种方法基于聚类挖掘关联规i ! l j ，然厉使t l = i 规则进行分类。a r c s 或关 联规则聚类系统挖掘形如a q l a q 。c 2 j a 。的关联规则i 其中，a q 。【i ，a q 。2 是在量化属性区间上的测试( 区间动态地确定) ，而a 。为给定训练数据的分类 属性指定一个类标号。关聪规则画在2 - d 栅格上。算法扫描栅格，搜索规则的 矩形聚类。用这种办法，出现在一个规则聚类内的量化属性的相邻区间可以结 合。由a r c s 产生的聚类关联规则用于分类，其准确率可与c 4 5 媲美。一般地， 当数据中存在孤立点时，实验发现a r c s 比c 4 5 稍微精确一点。a r c s 的准确 性与离散化程度有关。从可规模性来说，不论数据库多大，a r c s 需要的存储 容量为常数。相比之下，( 2 4 5 具有指数运行时间，要求整个数据库( 乘以某个 因子) 全部装入内存。 第二种方法称作关联分类。它挖掘形如c o n d s e t ；y 的规则；其中，c o n d s e t 是项( 或属性值对) 的集合，而y 是类标号。满足最小支持度的规则是频繁的； 这里，规则具有支持度s ，如果给定数据集中的样本5 包含c o n d s e t 并且属于类 y 。满足最小置信度的规则是精确的；这里规则的置信度为c ，如果给定数据 集中包含c o n d s e t 的样本c 属于类y 。如果一个规则项集具有相同的c o n 出e t ， 则选择具有虽高置信度的规则作为可能规则( p r ) ，代表该集合。 基于j e p 的分类算法研究 关联分类方法由两步组成。第一步是找出所有频繁的、精确的p r 集合。这 些是类关联规则( c a r ) 。其c o n d s e t 包含k 个项的规则项称作 - 规则项。算法使 t l _ f j 迭代方法，先验知识用于裁减规则搜索。第二步使用一种启发式方法构造分 类。这里，发现的规则根据支持度和置信度按递减的优先次序组织。算法可能 需要多次扫描数据集，这依赖于找到的最长规则的长度。对一个新的样本进行 分类时，满足该样本的第一个规则用于对它分类。分类算法也包含省缺规则， 它具有最低的优先次序，用来为不被分类算法中其它规则满足的新样本指定一 个缺省的类。一般地，经验表明，上述关联分类方法在许多数据集上比c 4 5 更 精确。以上两步都具有线性可规模性。 c b a 是一种典型的关联分类算法，其基本思想是首先找出满足特定的支持 度和可信度闽值的c a r ，然后使用强规则用于分类。因为c a r 是一种特殊的 芙联规则，所以现有的关联规则挖掘算法( 如a p r i o r i 和m a xm i n e r ) 都可以不 作任何修改而直接用于挖掘c a r 。但是，该分类算法的缺点是所挖掘出的c a r 的数量通常很大。一种解决办法是提高支持度或置信度闽值，或同时提高两者， 但这种方法会影响分类的准确性。 第三种方法c a e p ( 通过聚集显露模式分类) 使t l ；项集支持度挖掘显露模 式( e m e r g i n gp a t t e m ，e p ) ，而e p 用于构造分类。粗略地说，e p 是一个项集( 项 的集合) ，其支持度由一个类到另一个类显著增加。两个支持度的比称作e p 的 增长率。例如，假定我们有顾客数据集，包含类b u y sc o m p u t e r = “y e s ”或c ，平| 】 b u y s _ c o m p u t e r = “n o ”或c 2 。项集 a g e = “ = 3 0 ”，s t u d e n t s = “n o ”) 是一个典型的e p ， 其支持度由在c l 中的o 2 增长到在c 2 中的5 7 6 ，增长率型兰2 ：2 8 8 。注意， 02 一个项或者是分类属性上的简单相等测试，或者是检查数值属性是否在某个区 间的测试。每个e p 是一个多属性上的测试，并且可能在区分一个类的实例与 另一个类的实例方面非常强。例如，如果一个新样本x 包含在上面的e p 中， 我们可以说x 属于c 2 的几率为9 9 6 。一般地，e p 的区分能力火约三比于它 的增长率和它在目标类的支持度。 对于每个类c ，c a e p 找出满足给定支持度和增长率阈值的e p ；这里，增 长率按所有的非c 类样本的集合对所有的c 类样本目标集合来计算。“基于边 界”的算法可以用于计算。在对一个新样本x 分类时，对于每个类c ，对出现 在x 中的类c 的e p 的区分能力聚集，得到c 的得分，然后对得分规格化。具 有最大规格化得分的类决定x 的类标号。 业已发现，在许多数据集上，c a e p 比c 45 和基于关联的分类更精确。它 在主要感兴趣的类占少数的数据集上也运行良好。它在数据量和维数上都是可 规模化的。 一种替代的分类算法称作j e p 分类算法( j e pc l a s s i f i e r ) ，该算法是基于跳 跃显露模式( j u m p i n ge m e r g i n gp a t t e r n ，j e p ) 提山的。其中，j e p 是一种特殊类 8 基于j e p 的分类算法研究 型的e p ，定义为这样的项集，其支持度由在一个数据集中的0 陡峭地增长到另 一个数据集中的非0 。因为j e p 具有无穷大的增氏率，而e p 具有有穷的增长率， 所以j e p 比e p 的区分能力更强。这使得在许多大型数据库( 尤其是维数也很大 的数据库) 中，基于j e p 的分类算法优于基于e p 的分类算法。例如，对于蘑菇 数据集( 取自于u c l 机器学习库) ，项集( o d o r = f o u l ) 是一个j e p ，它在可 食类中的支持度为o ，在有毒类中的支持度为5 5 。如果一个测试实例包含 这个j e p ，那么我们可以很有把握的认为该实例属于有毒类，而不属于可食类。 实验结果表明，与已发表的分类算法相比，j e p 分类算法确实能取得_classifier 更高的预测准确性。本文的第二章将详细讨论基于跳跃显露模式的分类。 1 3 分类的准确性 估计分类算法的准确率是重要的，这使得我们可以估计一个给定的分类算 法对朱米的数据( 即未经分类算法处理的数据) 正确标号的准确率。 1 3 1 评估分类算法的准确率 由于分类算法( 或模型) 对数据的过分特化，使用训练数据得到分类算法， 然后评估分类算法可能错误地导致过于乐观的估计。保持和肛折交叉确认是两 种基于给定数据随机选样划分的、常用的评估分类算法准确率的技术。 在保持方法中，给定数据随机地划分成两个独立的集合：训练集和测试集。 通常，三分之= 的数据分配到训练集，其余三分之一分配到测试集。使用训练 集导出分类算法，其准确率用测试集评估。评估是保守的，因为只有一部分初 始数据娟于导出的分类算法。随机子选样是保持方法的种变形，它将保持方 法重复k 次。总体准确率估计取每次迭代准确率的平均值。 在a 折交叉确认中，初试数据被划分成k 个互不相交的子集硝折3 ，s2 ，s 。，每个折的大小大致相等。训练和测试进行k 次。在第i 次迭代，s ，用作测试 集，其余的子集都用于训练分类算法。即，第一次迭代的分类算法在子集s2 ，s k 上训练，而在s 1 上测试；第二次迭代的分类算法在子集s 1 ，s3 ，sk 上训练， 而在上测试；如此下去。准确率估计是k 次迭代正确分类数除以初始数据中 的样本总数。在分层交叉确认中，折被分层，使得每个折中样本的类分布与在 初始数锯中的大致相同。 评估分类算法准确率的其它方法包括解靴带和留一。前者使刚一致的、带 放同的选样，选取给定的训练实例；后者是七折交叉确认，这里t 为初始样本 数s 。一般地，建议使用调整的l o - 折交叉确认，因为它具有相对低的偏置和方 差。 使用这些技术评估分类算法的准确率增加了总体运行时间，但对于由多个 分类算法中选择仍然是有用的。 1 3 2 提高分类算法的准确率 9 基于j e p 的分类算法研究 装袋( 或引导聚集) 和推进是两种提高分类算法的准确率的技术。每个都 将r 个学习得到的分类算法c ，c 2 ，c v 组合起来，旨在创建一个改进的分类算 法c + 。 “这些方法如何工作? “假定你是一个病人，希望根据你的症状进行诊断。 你可能选择看多个医生，而不是一个。如果某种诊断比其它诊断出现的次数多， 你可能将它作为最终或最好的诊断。现在，将医生换成分类算法，你就可以直 观地理解装袋。假定你根据医生以前诊断的准确率，对每个医生的诊断“值” 或价值赋予一个权值，则最终的诊断是加权的诊断的组合。这就是推进的基本 思想。l 止我们进一步考察这两种技术。 给定s 个样本的集合s ，装袋过程如下。对于迭代t ( f = 1 , 2 ，丁) ，训练集s ，采用放回选样，由原始样本集s 选取。由于使用放回选样，s 的某些样本可能 不在s 中，而其它的可能出现多次。由每个训练集s ，学习，得到一个分类算法 c ，。为对一个未知的样本x 分类，每个分类算法c ，返回它的类预测，算作一票。 装袋的分类算法c + 统计得票，并将得票虽高的类赋予。通过取得票的平均值， 而不是多数，装袋也可以用于连续值的预测。 在推进中，每个训练样本赋予一个权。学习得到一系列分类算法。学习得 到分类算法g 后，更新权，使得随后的分类算法c h “更关注”c ，的分类错 误。最终的推进分类算法c + 组合每个分类算法的表决，这里每个分类算法的表 决是其准确率的函数。推进算法也可以扩充到连续值预测。 1 3 3 准确率确定分类算法够吗 除准确率外，分类算法还可以根据其速度、强壮性( 例如，在噪音数据上 的准确性) 、可规模性、可解释性进行比较。可规模性可以通过计算给定分类算 法在渐增的数据集上的i o 操作次数评估。可解释性是主观的，尽管我们可以 在评估它时使用诸如结果分类算法的复杂性( 例如，决策树的结点数，或神经 网络的隐藏单元数) 等客观度量。 假定你已经训练了一个分类算法，将医疗数据分类为”c a n c e r ” 或”n o nc a n c e r 。9 0 的准确率使得该分类算法看上去相当准确，但是如果实际 只有3 - 4 的训i 练样本是”c a n c e r ，怎么样? 显然，9 0 的准确率是不能接受的 该分类算法只能正确地标记”n o nc a n c e r 样本。替换地，我们希望能够评估 该分类算法能够识别样本”c a n c e r ( 称作正样本) 的情况和它识别样 本”n o nc a n c e r ”( 称作负样本) 的情况。为此，我们可以分别使用灵敏性和特效 性度量。此外，我们可以使用精度评估标记为”c a n c e r ，实际是”c a n c e r 的样本 的百分比。 另外，在分类问题中，通常假定所有对象都是唯一可分类的，即每个训练 样本能够，并仅能够属于一个类。然而，由于大型数据库中的数据非常发散， 假定所有的对象都唯一可分类并非总是合理的。假定每个对象属于多个类是可 o 甚于j e p 的分类算法研究 行的。这样，如何度量大型数据库上分类的准确率呢? 准确率度量是不合适的， 冈为它没考虑样本属于多个类的可能性。 不返回类标号，而返回类分布概率是有用的。这样，准确率度量可以采用 二次猜测：一个类预测是正确的，如果它与最可能的或次可能的类一致。尽管 这在某种程度上确实考虑了对象的非唯一分类，但它不是完全解。 1 4 分类算法的比较标准 常州的分类算法的比较和评估标准有如下几点： ( 1 ) 预测的准确率：这涉及模型正确地预测新的或先前未见过的数据的类 标号的能力。 ( 2 ) 速度：这涉及产生和使用模型的计算花费。 ( 3 ) 强壮性：这涉及给定噪音数据或具有空缺值的数据，模型正确预测的 能力。 ( 4 ) 可规模性：这涉及给定大量数据，有效地构造模型的能力。 ( 5 ) 可解释性：这涉及学习模型提供的理解和洞察的层次。 目前，已有许多关于不同分类算法的比较，并且该问题仍然是一个研究课 题。尚未发现有一种算法对所有数据都优于其它方法。如准确性、训练时间、 强壮性、可解释性和可规模性必须考虑，并且可能涉及折衷，使得寻求更好方 法进一步复杂化。实验研究表明。许多算法的准确性非常类似，其差别是统计 不明显的，而训练时间可能显著不同。一般地，大部分神经网络和涉及样条的 统计分类与大部分决策树方法相比，趋向于计算量大。 1 5 本文的研究内容与结果 本文的研究内容是数据挖掘中的分类问题，尤其对基于j e p 的分类算法进 行了深入的研究。本文的研究成果有：提出了一种特殊的j e p ，即s j e p ；给出 了一个挖掘s j e p 的高效算法( m i n es j e p s ) ：构造了一种新的基于s j e p 的分 类算法( s j e pc l a s s i f i e r ) 。 结果如下：s j e pc l a s s i f i e r 分类算法可以使厢非常少的s j e p 而获得和基于 j e p 的分类算法相近的甚至是更高的准确性，在大部分情况下，比c b a 和c 4 5 具有更高的分类准确性，同时我们的分类算法效率很高，可以在几秒钟内完成 挖掘任务。 1 6 本文的结构安排 本文以后各章节安排如下；第二章介绍基于j e p 的分类算法。该章将给出 一种典型的基于j e p 的分类算法( 即j e p _ c l a s s i f i e r 分类算法) 的全面描述，包 括两个挖掘j e p 的算法，最有表现力的j e p 的选择和j e pc l a s s i f i e r 分类算法的 分类过程。第三章介绍最有效的跳跃显露模式( s j e p ) 。该章将给出s j e p 的形 皋- 二 e p 的分类算法研究 式化定义；详细介绍一个挖掘s j e p 的高效算法( m i n e s j e p s ) 。第四章介绍基 于s j e p 的分类算法。该章将详细讨论基于s j e p 的分类算法的主要思想，单个 s j e p 的区分能力、总分的计算和标准化，及该分类算法的构造方法；比较了该 分类算法和一些流行的分类算法，并给出了实验结果。 基十j e p 的分类算法研究 2 1 引言 第二章基于j e p 的分类算法 2 0 0 0 年，d o n g 、l i 和r a m a m o h a n a r a o 提出了一种特殊的知识模式，即跳 跃显露模式( j e p ) ，并建立了基于j e p 的分类算法( j e p _ c l a s s i f i e r ) 。在这里， j e p 被定义为一个项集，其支持度在一个数据集中为0 ，而在另个数据集中为 非0 一支持度增氏率为。利用j e p 作为分类的基础是考虑到j e p 具有很强 的区分能力。所以，通过聚集所有的j e p 就可以产生很强的分类能力。 然而，在一些大型的数据集中，用于分类的j e p 的数量通常很大，有时多 达1 0 8 。显然地，采用天真的算法来挖掘所有的j e p 和计算它们的集体效果是很 费时的。所以j e pc l a s s i f i e r 分类算法采用基于边界的算法来挖掘j e p ，另外， 边界表示法也有助于选出那些最有表现力的j e p 。实际上，最有表现力的j e p 就是那些具有较大支持度的j e p ，它们代表了训练数据集中具有区分能力的模 式的精华。 实验证明，与已发表的分类算法相比，j e pc l a s s i f i e r 确实能取得较高的预 测准确性。 本章首先进行问题描述，然后介绍两个挖掘j e p 的算法，接着介绍如何选 择最有表现力的j e p ，最后简要描述j e pc l a s s i f i e r 的分类过程，并对基于j e p 的分类算法作以总结。 2 2 问题描述 假定训练数据集d 是一个标准的关系表，它包含n 个实例，每个实例有 m 个属性，每个属性值可以是分类数据也可以是数值数据。训练数据集中共有q 个己知类，即c i c 。根据各个实例所属类别，将这n 个实例划分为q 个集 合。 为了将数据集d 编码，对分类数据，使用双射的方法将其映射为项；对数 值数据，首先采用等长分箱的方法将其离散化为十个不同的区问，然后，采用 类似于分类数据的方法将各个区间映射成项。 令i 表示编码后的所有项的集合，一个项集x 被定义为i 的子集。x 在类 c 中的支持度被定义为；类c ，中包含x 的实例数和类c ，中总实例数的比值， 记为s u p p 。i ( x ) 。 考虑包含两个类的训练数据集，j e p 定义如下： 定义2 2 1 ；从类c l 到类c 2 的j e p 是那些在类c l 中的支持度为0 ，而在 类c 2 中的支持度非0 的项集，记为j e e ( c i ，c 2 ) 。 不失一般性，对于包含q 个类( 即类c l ，c 2 ，c 。) 的数据集d ，共有q 组 基于j e p 的分类算法研究 j e p 组成：即从u ；：2 q 到c ，的j e p ，从u ；：【j ；2 g 到。的j 6 9 ，从 uq g 到g 的j e p 。 、i 例如：如果q = 3 ，那么共有3 组j e p ：从c 2 u c 3 到c i 的j e p ，从c iu c 3 到c 2 的j e p ，从c i u c 2 到c 3 的j e p 。 在一些基于j e p 的分类算法中，如j e pc l a s s i f i e r ，并不列举出所有的j e p ， 而是使用边界来简洁的表示它们。此外，边界表示法也有利于选择那些最有表 现力的j e p 。下面给出边界的概念： 定义2 2 2 ：边界是一个形女t l 的有序对。其中，l 中的每个元素是r 中某个元素的子集，r 中的每个元素是l 中某个元素的超集；l 称为左边界，r 称为右边界。 边界表示的集合为 l ，r = f y j j x l ，z r ，其中，x y c z ) 。 我们常称用边界 表示集合 l ，r ，或称对每个x l ，r 都被边界 所覆盖。 显然地，在所有被边界覆盖的项集中，左边界所包含的项集具有最大的支 持度。因此，我们取所有左边界所包含的项集的并集，称之为最有表现力的j e p 。 在j e pc l a s s i f i e r 分类算法中，最有表现力的j e p 是一个很重要的概念。为 了划分一个测试实例t ，我们估计那些是t 的子集的最有表现力的j e p 的集体 效果。 定义2 2 3 ：已知包含两个类c 】和c 2 的训练数据集和一个测试实例t ，则 所有支持类c ，的最有表现力的j e p 的集体效果定义如下： 2 。 s u p p 。， x c _ 7 ，r 劢p ( c i ( 2 ) 其中，m e j e p ( c 】，c 2 ) 是从类c 1 到类c 2 的最有表现力的j e p 利从类c 2 到类 c l 的最有表现力的j e p 的并集。所有支持类c 2 的最有表现力的j e p 的集体效果 的定义类似。 2 3j e p 挖掘算法 水平边界是j e p 挖掘算法中个重要的概念，所以，本节在介绍j e p 挖掘 算法前，先给出水平边界的定义和相关算法。 定义2 3 1 ；一个数据集的水平边界，记为 ，表示数据集中支持 度为非零的项集。 一个数据集d 的水平边界可以用算法h o r i z o n m i n e r 来找出。算法如下： h o r i z o n m i n e r ( d ) ( 4 桀于j e p 的分类算法研究 ；返回d 的水平边界 ：；假定事务被任意排序为t l ，t 。 r i g h t b o u n d ( - - t t ； f o r i f r o m2 t ond o i f t ii sn o tas u b s e to f a n ye l e m e n ti nr i g h t b o u n dt h e n a d dt it or i g h t b o u n d ； r e m o v ea l lti n 鼬g h t b o u n ds u c ht h a ttc t i ； r e t u r n 庐) ，r i g h t b o u n d ； ) 本算法的基本思想是