（计算机软件与理论专业论文）基本显露模式的挖掘算法.pdf

基本显露模式的诧搓算法 摘要 数据挖撼是扶海量豹数据中挖掘有潜凌稔僮豹售患鹣技术。分炎蹩数据挖 掘中一项非常熏骚的任务，在政府组织、科学研究、商她等诸多领域鼹有广泛的 应用。统计学、机器学习、神经网络等领域的研究者提出了很多分类算法，这些 算法大罄透曩予，l 、型数据集，慕予显露摸式( e m e r g i n gp a t t e r n s ，e p s ) 戆分类方法是 针对大型数据集的分类提出的。 显露模式是那些从一个数据集到另一个数据集支持魔发生显著变化的项集， 它霹分类是有麓豹，这是嚣鸯它戆撬获数掇榘孛不霜类之闽戆差异。蘩一个基于 e p s 的分类算法怒gd o n g 等掇出的c a e p 算法，此后相继提出了j e p + c l a s s i f i e r 、 d e e p s 等一系列熬于e p s 的分类算法。在分必时我们发现用于分类的e p s 的数量 逶露缀夫，不齄选建溪畜夔e p s 廷予分类。f a n 穰r a m a m o h a n a r a o 提议镬蘑一静 特殊的e p s ，称作基本显露模式( e s s e n t i a le m e r g i n gp a t t e r n s ，简称e e p s ) ，进行 分类，并建立了熬于e e p 的b a y e s 分类法，取得了很好的分类效果。 溜_ l 邈，魏舞麓效逮挖掘蠢e e p s 是一个 夔蓬要豹闰嚣。e e p s 是箨骛“最短秘” e p s ，使用e p s 的边界表示，e e p s 恰是e p s 边界表示的一组下界，因此可以使用 g d o n g 和l i 提出的边界算法米挖掘所有的e e p s 。然而，这种方法的效率极低。 爻捡据c 类上戆e e p s ，必绥藏先挖据e 类鞠箨c 类上瓣彀模式，然麓傻用透赛 算法得到c 类上的e e p s 。挖掘长模式是一颁很耗时的工作，并且采用边界算法 产生的e e p s 并不包含支持度和增长率信息。为了得到e e p s 的支持度署日增长率， 还鬻黉孬次 霉攒数器集，绫计每个e e p 斡蠢淡频率著计算增长率。 本文的主票工作是提出了一种基于模式树( p 树) 的e e p s 挖掘新算法 e e p m i n e r 。e e p m i n e r 采用模式增长豹策路，只嚣两次掴摇事务数据撵，就能挖 掘蹬c 类上所有静e e p s ，著阏辩得到它们的增长率秘支持度。并虽禚挖掘过程 中，模式树不仅存储数据集中所有项的信息，而且支持类的信息。我们不需要附 加静室翅就可以纛接在模式褥上挖掘出所有的e e p s 。在u c i 机器学习数据库豹 多个数据集上的实验表瞬，e e p m i n e r 其有缀好的住髓，其速度跑蓥予边赛的算 法快得多。 关键譬：数据撼攒，分类，驻簇模式，基本显露模式 基本靛露模式避挖掘算法 a b s t r a c t d a t am i n i n g ，i sk n o w na sau s e f u lt e c h n o l o g yt of i n dv a l u a b l ei n f o r m a t i o nw h i c h i sp o t e n t i a li nv e r yl a r g ed a t a b a s e s c l a s s i f i c a t i o n ，a sa ni m p o r t a n tt h e m ei nd a t a m i n i n g ，h a sb e e nw i d e l yu s e di nm a n yf i e l d s ，s u c ha sg o v e r n m e n to r g a n i z a t i o n ， s c i e n t i f i cr e s e a r c h b u s i n e s sc o r p o r a t i o n , a n ds oo n m a n ys c h o l a r sw h ow o r ka t s 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 u r a ln e t w o r k , e x p e r ts y s t e m se r ep r o v i d eal 斑o f a l g o r i t h m s b u tm o s to ft h e ma r eo n l yu s e di nas m a l ld a t as i z e m e t h o d sf o r c l a s s i f i c a d o nb ye m e r g i n gp a r e m s ( e p s ) w e r ep r o p o s e di no r d e rt oc l a s s i f yl a r g e d a t a s e t s e m e r g i n gp a r e m s ( e p s ) a l ei t e m s e t sw h o s es u p p o r t sc h a n g es i g n i f i c a n t l yf r o m o n ed a t ac l a s st oa n o t h e r t h e yc a ns e r v ea sag o o dc l a s s i f i c a t i o nm o d e lb e c a u s et h e y r e p r e s e n tk n o w l e d g ew h i c h d i s c r i m i n a t e sb e t w e e nd i f f e r e n tc l a s s e so fd a t a s e t s c a e p , w h i c hh a sb e e np r o v i d e db y & d o n ga n dj l ii n1 9 9 9 ，i st h ef i r s ta p p l i c a t i o no f e m e r g i n gp a t t e r n st oc l a s s i f i c a t i o n a f t e rt h a t , as e r i e so fe p s b a s e dc l a s s i f i e r sw e r e p r o p o s e ds u c ha sj e p c l a s s i f i e r , a n dd e e p s b u tt h en u m b e ro fe p su s e di n c l a s s i f i c a t i o na l w a y si sl a r g e , w ec a l l tc h o o s ee v e r yo n e r e c e n t l y , as p e c i a lk i n do f e p s ，n a m e de s s e n t i a le m e r g i n gp a t t e r n s ( e e p s ) ，i su s e di nc l a s s i f i c a t i o nb yf a na n d r a m a m o h a n a r a o b a s e do nt h e s en e wp a t t e r n s ，t h e yb u i l dab a y e sc l a s s i f i e rw h i c h h a sa ne x c e l l e n tp e r f o r m a n c e f o l l o w i n g 畦l a t ih o w t om i n ee f f e c t i v e l yt h ee e p sb e c o m ea ni m p o r t a n ti s s u e 。e e p i st h e s h o r t e 鑫”e p , a n di tr e m o v e st h er e d u n d a n te p si nc l a s s i f i c a t i o n 。b yt h e b o r d e r - b a s e dr e p r e s e n t a t i o n , e e p sa r ej u s tt h es e t so fl e rb o r d e ro fe es ow ec a nu s e t h eb o r d e r - b a s e da l g o r i t h m sw h i c hb s e dt og e te p st om i n ee e p s h o w e v e r , t h e m e t h o di si n e f f e c t i v e i no r d e rt 0g e tt h ee p so fcc l a s s ，w em u s tf i r s t l ym i n et h e m a x - p a a e r n so fc c l a s sa n dn o n - cc l a s s 。b 诚t h es p e e df o rm i n i n gm a x p a r e m si s s l o w b e s i d e s ，t h eb o r d e r - b a s e da l g o r i t h m sc a n tg e ts u p p o r ta n dg r o w t h r a t ew h i c ha r e u s e f u lt oc l a s s i f i c a t i o ni nt h ep r o c e s so fm i n i n ge p s i no r d e rt og e ts u p p o r ta n d g r o w t h r a t eo f e p s w en e e dt os c a nt h ed a t a s e tf o rt h es e c o n dt i m e t 撼sp a p e rp r e s e n t san o v e la l g o r i t h mn a m e de e p m i n e rw h i c hb a s e so np a r e m t r e e ( p * t r e e ) t h ea l g o r i t h mu s e st h ep a t t e r nf r a g m e n tg r o w t hs t r a t e g y ，a n do n l yn e e d s t os c a nd a t a s e tt w i c et og e te e p sw i t ht h e i rs u p p o r ta n dg r o w t h r a t e m o r e o v e r , t h e p a t t e r nt r e en o to n l ys t o r e sa l li t e m si nd a t a s e tb u ta l s os u p p o r t sc l a s si n f o r m a t i o n w e c a nm i n ea l le e p si np a t t e mt r e ew i t h o u ta d d i t i o n a ls p a c e t h ee x p e r i m e n ts t u d y c a r r i e do nb e n c h m a r kd a t a s e t sf r o mt h eu c im a c h i n el e a m i n gr e p o s i t o r ys h o w st h a t e e p m i n e rp e r f o r m sv e r yw e l l ，a n di sm u c hf a s t e rt h a nb o r d e r - b a s e da l g o r i t h m s k e y w o r d s ：d a t am i n i n g ，c l a s s i f i c a t i o n ，e m e r g i n gp a t t e r n ，e s s e n t i a le m e r g i n g p a t t e r n i i 郑重声盟 本人的学彼论文怒在导师指导下独立撰写并完成的，学位论文没有飘窃、抄 袭等违反擎术遴德、学术籁范静侵校行为，否煲| l ，本人愿意承拯由噩乏产生豹一切 法律责强和法德惑果，特此郑蓬声明。 学饿论文作者( 签名) ：锻麓 王5 年5 月o j 闫 基本显露模式的挖掘算法 第一章绪论 近十几年来，人们利用信息技术搜集和处理数据的能力大幅度提高，无数个 数据库被用于商业管理、政府办公、科学研究和工程开发等，这一趋势仍将持续 发展下去。于是，一个新的挑战被提了出来：在这被称之为信息爆炸的时代，信息 过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没，从中 及时发现有用的知识，提高信息利用率呢? 要想使数据真正成为有用的资源，只有 充分利用它为人们决策和企业战略发展服务才行，否则大量的数据可能成为包袱 甚至成为垃圾。因此，面对“人们被数据淹没，人们却饥饿于知识”的挑战，一种 智能化的、综合应用各种统计分析、数据库、智能语言来分析庞大数据资料的技 术就应运而生，这种技术就是数据挖掘。 数据挖掘不但能够学习已有的知识，而且能够发现未知的知识；得到的知识 是“显式”的，既能为人所理解，又便于存储和应用，因此一出现就得到各个领 域的重视。从8 0 年代末的初露头角到9 0 年代末的广泛应用，以数据挖掘为核心 的商业智能( b i ) 已经成为r r 及其它行业中的一个新宠。当前数据挖掘应用主要 集中在电信( 客户分析) ，零售( 销售预测) ，农业( 行业数据预测) ，网络日志( 网 页定制) ，银行( 客户欺诈) ，电力( 客户呼叫) ，生物( 基因) ，天体( 星体分类) ， 化工，医药等方面。据专家预测，在今后的5 1 0 年内，随着数据量的日益积累 以及计算机的广泛应用，数据挖掘将在中国形成一个产业【2 l 。 本章将介绍有关数据挖掘的一些知识，并给出本文的研究内容，以及文章的 结构安排。 1 1 数据挖掘的概念 数据挖掘( d a t am i n i n g ) ，有时也称作数据采掘、数据开采等。它是从大量的、 不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不 知道的、但又是潜在有用的信息和知识的过程。还有很多和它相近似的术语，如 从数据库中发现知识( k d d ) 、数据分析、数据融合( d a t af u s i o n ) 以及决策支持 等。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据 基本显露模式的挖掘算法 可以是结构化的，如关系型数据库中的数据，也可以是半结构化的，如文本、图 形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学 的，也可咀是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用 于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。 因此，数据挖掘是- - f 广义的交叉学科，它汇聚了不同领域的研究者，尤其是数 据库、机器学习、数理统计、模式识别、粗糙集、模糊数学等方面的学者和工程 技术人员。由于它是多学科综合的产物，人们提出了多种定义，例如： s a s 研究所( 19 9 7 ) ：“在大量相关数据基础之上进行数据探索和建立相关 模型的先进方法“。 b h a v a n i ( 1 9 9 9 ) ：“使用模式识别技术、统计和数学技术，在大量的数据中 发现有意义的新关系、模式和趋势的过程”。 h a n de ta l ( 2 0 0 0 ) ：“数据挖掘就是在大型数据库中寻找有意义、有价值信 息的过程”。 许多人还把“数据挖掘”和“数据库中的知识发现”( k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ，简称k d d ) 看作是等价的概念，在这种意义下它们的定义是一致的。 一种比较公认的定义是wj f r a w l e y ，gp i a t e t s k y s h a p i r o 等人提出的，描述为： “数据挖掘，即数据库中的知识发现( k d d ) ，是一个在数据中提取模式的过程， 这些模式是有效的、新颖的、有潜在实用价值的和易于理解的。” 还有人把k d d 看作发现知识的完整过程，而数据挖掘只是这个过程中关键 的一个部分。这种观点对数据挖掘的定义是： “数据挖掘是数据库中的知识发现( ) d ) 过程中的一个步骤，这个步骤由 一些特定的数据挖掘算法组成，这些算法的任务是在满足一定计算效率的约束条 件下，从数据中提取有效的模式。” 数据挖掘操作的对象蕴含了未知的模式和知识，之所以运用各种各样的算法 进行挖掘也是因为数据规模的扩张带来的新的效率问题。抽取的模式一定是特定 的而非泛泛的，是符合一定要求的，即必须是针对特定应用的特定需求，因为不 同的应用对模式的理解和运用有很大的差别，对决策的支持是数据挖掘的最终目 标。数据挖掘对决策的支持是通过对模式的正确解释和运用，也就是利用抽取的 模式从宏观上观察和分析数据，从微观上深入的理解数据的含义，同时对未来的 2 基本显露摸式的挖掘算法 数据取向和趋势做出预测。 。2 数据挖撼鳇功熊 数据挖掘综合了很多学科技术，风有多种功能，当前的主要功能如下： 分类；分类裁是找趱一个类别浆概念描述，它 弋表了这类数据的整体锩 崽，即该类的内涵描述，并用这；f 辛捺述米构造模型，一般用规则躐决策树模式袭 示。 2 。聚类：就是把数据按照穗似性魉纳成若予类剐，嗣一类中的数据彼她稠 儆，不同类巾的数据稽箨。槊类分析可以建立宏观的概念，发现数攮的分布模式， 以及可能的数据属性之间的相互关系。聚类算法可分为基于层次的聚类肼，5 1 ，撼 予密疫兹聚类舆，基予剃格敢聚类鼽1o ，1 1 1 ，基于模型豹聚类 1 2 a 3 和基于划分的 浆类等。 3 关联规则【1 4 , 1 5 1 和序列模式1 t 1 7 1 的发现：关联是某种事物发生时其他枣物 也会发生这榉一静联系。一般用支持度敷可售度两个阑值来度量关联援刚豹翊关 性，还不断弓l 入兴趣度、稽关性等参数，使得所掩瓣的规贝更符合需求。例如： 每天购买啤洒的人也有可能购买香烟，比重有多大，可以通过关联的支持度和可 信疫来攒述。与关联不疑，滂捌是一秘缴囱豹联系。 4 预测1 1 8 a 9 ：就是霸用历史数据找出变化规律，建立模型，并由此模型对 未来数据的种类及特征进行预测。预测关心的是精魔和不确定性，通常用预测方 差来度量。 5 偏麓的检测 2 0 , 2 h ：对分析对象少数的、极端的特例的描述，揭示内在的 原因。例如：在银行的1 0 0 万笔交易中有5 0 0 例的欺诈行为，银行为了稳健经髂， 藏要发理这5 0 0 铡豹蠹在因素，减小戳嚣经营豹风黢。 1 3 数据挖掘的方法 鼗据藏瓣瓣方法，大致分为圈稃；统诗方法、梳器学习方法、毒牵经鼹络 方法和数据库方法。 基本显露模式的挖掘算法 统计方法中，可细分为：回归分析( 多元回归、自回归等) 、判别分析( 贝 叶斯判别、费歇尔判别、非参数判别等) 、聚类分析( 系统聚类、动态聚类等) 、 探索性分析( 主元分析法、相关分析法等) 、以及模糊集、粗糙集、支持向量 机等。 机器学习方法中，可细分为：归纳学习方法( 决策树【捌、规则归纳等) 、 基于范例的推理c b r 、遗传算法、贝叶斯信念网络 2 3 】等。 神经网络方法，可细分为：前向神经网络( b p 算法等) 、自组织神经网 络( 自组织特征映射、竞争学习等) 等。 数据库方法主要是基于可视化的多维数据分析或o l a p 方法，另外还有面 向属性的归纳方法。 我们对常用的一些方法做较为详细地介绍： ( 1 ) 传统统计方法：在数据库字段项之间存在两种关系：函数关系( 能用函 数公式表示的确定性关系) 和相关关系( 不能用函数公式表示，但仍是相关确定 性关系) ，对它们的分析可采用统计学方法，即利用统计学原理对数据库中的 信息进行分析。 ( 2 ) 可视化技术：用图表等方式把数据特征直观地表述出来，如直方图等， 这其中运用许多描述统计的方法。可视化技术面对的一个难题是高维数据的可 视化。 ( 3 ) 决策树：利用一系列规则划分，建立树状图，可用于分类和预测。常 用的算法有c a r t 、c h a i d 、i d 3 2 4 1 、c 4 5 2 卯、c 5 0 等。 ( 4 ) 神经网络【2 6 】：模拟人的神经元功能，经过输入层、隐藏层、输出层等， 对数据进行调整，计算，最后得到结果，用于分类和回归。 ( 5 ) 遗传算法：基于自然进化理论，模拟基因联合、突变、选择等过程的 一种优化技术。 ( 6 ) 关联规则挖掘算法f 2 7 ，2 8 l ：关联规则是描述数据之间存在关系的规则， 形式为“a 1a a 2 a a n b 1a b 2 a b n 。一般分为两个步骤：求出大数 据项集用大数据项集产生关联规则。 4 基本显露模式的挖掘算法 1 4 数据挖掘的实施步骤 数懿挖壤莓粳疆缝瑗辫兔三部楚：数蹇缕各( d a t a p r e p a r a t i o n ) ，数握挖攘， 以及结果的解释评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 。 具体地的步骤如下： 翊嚣璎鳃窝提塞一数据准冬数据整理建立模黧 浮徐鞠 解释 1 问题理解和提出：在开始数据挖掘之前最基础的就是理解数据和实际的 簸务阔题，程这个基磁之上捉遗翊透，瓣嚣标蠢硬赡瓣定义。 2 数攒准备：获取原始的数据，并从中抽取一定数量的子集，建立数掇挖 掘库，如果服来的数据仓库满足数据挖掘的要求，就可以将数据仓库作为数据挖 撼痒。 3 数据蹙理：由于数据可能是不兜全的、有噪声的、随机的，有复杂的数 据结构，就袋对数据进行初步的整理，清洗不完全的数据，做初步的描述分析， 选择与数摄挖糖有关豹交爨，或者转羧变量。 4 建立模型：根据数据挖掘的目标和数据的特征，选择合邋盼模型。 5 评价和解释：对数据挖掘的结果进行评价，选择最优的横趔，作出评价， 速蕉子实酝阏嚣，著显要鄹专选知识缝合鼹结象遗蟹解释。 在实际成用中以上步骤并不一定怒簧一次完成盼，可能其中菜些或者全部步 骤需要反复执行。 。s 数据挖掘的分类 近年来，数据分类技术已被广泛、有效地应用于科学实验、医疗诊断、气敖 镁摄、囊鼗羰灏、案终篌簸等矮壤，零| 越了工鲎赛粒学零雾豹极大关注。分类纛 是数据挖掘中的一个重戮问题。 分类是一种数据分析形式，可以用于从数据库中提取重要数据类豹模型或预 溯未来秘数攒憝势。它是糖在数蕹瘁鹣袈个对象孛援爨共嚣耱黢，并按照分类模 型把它们进行分类。它常涉及到如下几个基本术语：样本，也称为实例，指分淡 算法作用的对象，是现实世界数据集念的一个真子集，一般以元组的形式存放； 类标号，稃本豹一令重要瓣性，臻予舔谈元筑疆褒瓣类翅；分类器，氇穗爻分类 基拳燕露模式的挖强算法 函数或分类模型，是指一个有学习能力并且能瀚过其内部结构给未知类标号的实 饿确定类标号鲍系绞模型；训练数摄集，为建立分类器两被分耄蓐的数据元缀集合， 其中的单个元组称为训练样本：测试数据集，为评估分类嚣的健能而被分析的数 据元组集合，其中的单个元组称为测试样本。 1 5 1 肖指导静分类和无指导的分类 根掇分类任务侧重的具体目标，分类闻题可以分为两类：有指导的和无指导 豹t 2 9 , 捌。镁竣给定一个实镶集合，无豢导分癸，逸稔为聚癸，就是定义粪和确定 实例所属类的过程。这一过程的主要目标就是发现样本点之间最本质的“抱团” 性质并形成类：在选定了表示样零的特征之后，样本点就表示特征空间中的一个 点，懿祭孬选定样零点之闻的鞫曦鬟瞧度量函数，那么臻柒藏疲该是确定酌总 之，它怒样本点“抱团”性质的一种客观反映。通常，每个类有一个与其他类不 同的标号。无指导分类任务的第二二个目标是把一个薪的实例归类到已有的簇中， 或者玺成一个包含薪实铡静薮簇。 另一方面，在脊指导的分类中，每个给定实例的类标号必须明确给出( 这在 无指导分类中不是必褥的) ，并盥嚣要一个训练数据集。主裳譬标就是从绘定训 练数掇集中获取知谖( 规燕| j 或模式) ，然后驳发现的知识为指导把每一个新实弼 分到预先定义的某个类中。在这个过程中，需骚领域专家知识的指导，领域专家 指明哪魃样本属于令类，哪些样本属于另一个类，但是这种先验知识常常茭存 很大的主观性不溺领域的专家有不同静观瘾，即使是藏一领域的不阐专家观 点之间也会有很大的麓异。 1 5 。2 分类器酶梭造 分炎的目的是构遮一个分类器，并用它对新的未知的数据分类，以用于决策 支持。焚擒透过程分疆步：第一步，建立一个楱整，接述联邂茨数据类繁耱壤念 集，通过分析由属性描述的训练数据集来构造模型。假定每个元组属于一个预定 义的类，由一个类标号属性确定。这一步称为“训练阶段”戚“学习阶段”。第 二步，袋震模型遴嚣分类。薹先壤惩溺试集译镳模型懿该溅溱磙率( 称麓“溺试 阶段”) ，如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组 6 基本照露模式的诧撩雾法 或对敷进行分类。 分类器匏褥遘方法有统诗方法、被经鼹终方法、掇嚣学习方法纛遴糙集方法 【3 1 1 等等。 1 5 。3 分类算法戆比较标准 常用的分类算法的比较和评估标准有如下几点； ( 1 ) 预测的准确搴；涉及到模型正确地预测瓶的或先前采见过的数据的类标 号静# 力。 ( 2 ) 速度：涉及产生和使用模溅的计算花赞。 ( 3 ) 强壮性：涉及给定噪音数据或具有空缺假的数据，模型正确预测盼能力。 转) 蕊褒模洼：涉及臻定大豢数据，有效穗构造模型翡麓力。 ( 5 ) 可解释性：涉及学习模型掇供的理解和洞察的层次。 此外还有计算复杂度和模型描述的简洁度，计算复杂度依赖于具体的实现细 节窝矮传嚣凌，在数摄挖掘孛，凌予搡露对象怒蓬量静数鬟藤，因鼗簿阙秘空蠢 的复杂度将是非常煎要的问题。对于描述型的分类任务，模型描述越简浩越受欢 迎。例如，采用规则袭示的分类器构造法就更谢用，而神经网络方法产生的结果 藏鼹绫疆艇。 1 6 本文工作和结构安排 本文的主要工作是提出势窳现了一种麓于模式橱豹e e p s 挖掘新算法 e e p m i n e r 3 2 1 。在挖掘过程中，模式树不但存储了数据集中所有项的信息，而且 支持类瓣信息。我们不需要附加的空间就可以搬接在模式树上挖掘所有的e e p s 。 e e p m i n e r 借鉴了f p g r o w t h 3 3 愚慧，只需要两次扫摇事务数旗疼( 样本集) ，就 能挖掘出c 类上的所有e e p s ，并同时得到它们的增长率和支持度。在u c i 3 4 1 机 器学习数据库的多个数据集上的实验表明，e e p m i n e r 具有缀好的性能，其速度 魄墓予逸赛静算法抉褥多。 文章余下章节安排如下：第二章介绍e p s 和e e p s 概念及其挖掘算法：第三 章分缨算法e e p m i n e r 所媛酶数挺缝梅和它斡突蠛愚想；算法的正确性秘然分 析在第疆章给出。第五章介绍了e p s 和e e p s 用予分类的算法；最后，总结全文。 基本显露模式的挖掘算法 第二章e p s 和e e p s 及其挖掘算法 1 9 9 9 年，d o n g 和“提出了一种新的知识模式，即显露模式【3 5 ( e m e r g i n g p a t t e r n s ，e p s ) ，是指那些从一个数据集到另一个数据集支持度发生显著变化的项 集，这些项集能够捕获数据库中两个数据集之间的多属性差异。随后d o n g 和“ 又提出了基于e p 的分类算法：c a e p ( c l a s s i f i c a t i o nb ya g g r e g a t i n ge m e r g i n g p a a e m s ) ，实验表明基于e p 的分类算法可以取得很好的分类结果。 然而，在一些大型的数据集或高维数据集中，用于分类的e p s 的数量通常很 大，有时多达1 0 8 ，并且由于e p s 并不具有反单调性，在稠密的数据集中挖掘所 有的e p s 比挖掘所有的频繁模式困难得多。因此，有效地挖掘、表示这些e p s ， 以及对冗余的e p s 进行有效地剪枝对提高分类器的性能起着极其重要的作用。在 本章中我们将介绍一种基于边界的算法来挖掘e p s ，另外，边界表示法也有助于 选出那些最短的e p r 我们称之为e e p s 。e e p s 是表示e p s 边界的一组左边界 集合，它们代表了训练数据集中具有区分能力的模式的精华。实践证明这些e e p s 具有分类的完备信息并且可以抵抗分类的噪音，提高分类的效率。 本章的其余部分如下安排：2 1 给出e p s 的概念；2 2 介绍e p s 的特性及其常 见特殊形式；2 3 讨论e e p s 的概念及其特点；2 4 介绍e p s 的边界挖掘算法；2 5 给 出基于边界算法改进的f f b d 和e u b b d 算法。 2 1e p s 的概念 假设训练数据集是一个标准的关系表，它包含个实例( 样本) ，每个实例 有m 个不同的属性。所有的连续属性已经离散化，并映射到区间值。 r 个实例被 划分为k 个已知类c ic 2 , ，c b 并给定了每个训练实例所属的类，那么每一个实 例都可以看作是由一个整数值的集合和一个类标号来组成。 使用频繁模式的术语，项是对偶( 属性名，属性值) ，令，= i l ，2 , ， 是样 本中出现的所有项的集合。，的子集x ，称作项集或模式。训练数据集是项集 的集合。由于项集，是一个有限集，很容易建立一个映射表，将j 映射到正整数 集上。为简化讨论，以下将项视为正整数。 定义2 1 ：项集琏类c 中的支持度，记为s u p c ( x ) ，s u p c ( x ) = c o u n t c ( x ) i c i ，其中 基本燕露模式砖 宅骚算法 c o u n t ( x ) 是在类c 中包含瑚样本个数， 定义2 。2 ：给定疆个鼗攥集d7 灏p ， 如下： 而旧怒类c 中样本的总数。 瑗集蹴d 裂d 豹增长率移( 盖d ：廖) 定义 l 0 s u p t r ( x ) = s u p d ( 一o g r ( x , y ，功= s u p u ( x ) = 0 , s u p d ( x ) o s u p d ( x ) s u p 箕他 如果数据集d 和d 分别是c 噗和c 类样本的集合，则增长率是项集肖从类 c 到类c 支持度变化显著程度的发量。 定义2 3 ：给定增长率阂值p l ，如果项集并从d 到d 的增长率浅d ：d ) p ，则称z 是从d 到d 的, o - e p s ( 或e p ) ，域者简单地称x 是d 的e p ，并且 称s u p d ( x ) 为e p x 的支持度。 碟予分类对，数据集d 代表c 类样本的豢台，丽d ， 弋裘稚e 类样本的集合。 此时，瞵d ：d ) 筒记为g r d ( a 3 ，戏g r d x ) ，它怒项集x 从c 类到非c 类支持度 变化摄薄程度的度爨。有时也穆移为e p 靛宿数据集，藤d 豫爻e p 的对立数据 集。 e p s 能够捕捉两个数据集之间的显著变化。当它被应用于有类别的数据集时 ( 例如吸煺者与菲吸煺考，舂毒炎与可食类，滚愈与未治愈) ，它能够蠢效建臻 捉到类之闻的明显冀器。对于与嚣寸问相关韵数攒集( 例如消费者在2 0 0 3 年与在 2 0 0 4 年的消费能力) ，它能够发现商业数据中的屁著趋势。e p s 的增长率代表着 它的分类戆力羁预测戆力，e p s 懿支持度决定羲它爨起终塌熬范围。 侧如：对于u c i 中的m u s h r o o m 数据集， 设肛 ( o d o r = n o n e ) ，( o i l l _ s i z e = b r o a d ) ，( r i n gn u m b e r = o n e ) y - - ( b r u i s e s = n o ) ，( m e t s p a c i n g - - - c l o s e ) , ( v e i k e o l o r - q v h i t e ) 对应的支持度和增长率如下淡2 1 所示。 袭中，两个e p s 都有很高的增长率。例如，在有毒类中的支持度为o 在食爽孛懿支持发瓷6 3 。9 ；佟羹零食类熬e p s ，x 魏壤长率为c o 。懿莱一个 测试样本s 包含模式托我们几乎可以断定它属于可食类。y 在有毒类中的支持 度为8 1 4 ，在可食类中的支持度为3 8 ；作为商毒类的e p ，y 的增长率为2 1 4 。 蠡采s 镪食模式y 藏浚秀它爨缀舞豹壤率属予蠢毒类。 9 基本燕露模式酌挖掘算法 e p 有簿类可食类 增长率 x o 6 3 9 y8 1 4 3 8 2 1 4 2 。2e p s 的特性及其常见特殊形式 2 2 。1e p s 的特性 e p s 是作为一种新的k d d 知识模式被引入的，它具有如下几个特性【3 7 】： 1 ) 有效性( v a l i d i t y ) 发现静模式被鬻于薪数摇辩废该表现密一定程度静霄效瞧：实验表鞠，当在 原来的数据库中加入小比例的新数据时，许多船s 仍然是e p 8 。并且，即使是有 较大比例新数据被合并到以前的被处理过的数攒中，仍然保鼹着一些具露缀离可 信菠静e p s 。这一攀实表明，我稍可瑷使用e p s 豹穰念来捺挺系统的一黧本质， 因而，e p s 是一种有效的知识模式。 2 ) 新颖性( n o v e l t y ) 发现静e p s 有珂能会校长，戳至于可憨永远不会被餐统鹣统计方法发现，这 些令人惊讶的长模式髓为我们对过去已经“非常”理解的问题提供新的见解。 3 ) 潜在有用性( p o t c m i a lu s e f u l n e s s ) e p s 麓够描述镁惫两个没有鬟叠的对闽数撅集闼豹趋势，也能摇述经意两个 空问数据库间的重要麓异。显而翁见，发现的e p s 能被用于预测市场趋势、识别 一些常照疾病在不隧秘族群体闻的隐含的原匿、手写体识别以及区分正铡期反例 ( 比如，可食或有毒，胜利或失效，健康或霄瘸) 。 4 ) 可理解性( u n d e r s t a n d a b i l i t y ) e p s 是一些篱单条传豹基本缀合。剿如，模式 ( o d o r = n o n e ) ，( o i l l s i z e = b r o a d ) ， ( r i n g _ n u m b e r - - o n e ) 魏含3 个简单条件，它藏怒m u s h r o o m 数据库中静个e p ( b l a k e & m u r p h y , 1 9 9 8 ) 。这个模式中存在两个搿寓：1 ) 给定一个蘑菇，如果o d e r 是“n o n e ”，g i l l _ s i z e 是“b r o a d ”势且r i n g _ n u m b e r 是“o n c ”，那么这个蘑菇一 定是可禽的两不是有毒的。2 ) 大约6 3 9 酶可食类蘑菇具肖上面的特征，很是， 1 0 基本显露模式酌诧掘算法 任何有毒类蘑菇都不具备这些。鼹然，这个模式区别了可食必和有毒类的蘑菇。 l = 蠡此罄嶷，e p 具有镶妊的霹理麓性。 2 2 2 常见特殊形式的e p s 在麓面的，j 、节中，我们绘出了e p s 豹一般形式鹣定义。然丽，这些e p s 数量 巨大，并且存在着一定的冗余，因此，在实际的应用中常常考虑一些特殊形式的 e p s ，它们是前面提剁的一般性e p s 的子集，也都各自表现出一定的特性。 定义2 4 ：强e p s ( s t r o n ge m e r g i n gp a t t e r n s ) 1 3 7 1 ，给定一令增长率溺俊，如 果一个e p 的所有非空子集都是e p ，那么，这样的e p 就愚强e p 。 定义2 5 ：跳跃e p 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 ) 1 3 s 】，如果个e p 扶 d j 羁协的增长率为o o ，那么，它就被称作一个从蚤j 黉现豹跳跃e p s 。 在2 1 小节的例子中，x 就是一个从有毒类到可食类的j e p 。 定义2 6 ：高原e p s ( p l a t e a ue m e r g i n gp a t t e r n s ) 口9 1 ，给怒一个边界e p ，所有 在宿类中跟它有穗黼支持度的它的超集被称为该e p 豹商甄e p s 。任意边界e p 都是它本身的高原e p 。 定义2 7 ：高原空间( p l a t e a us p a c e ) 3 9 t ，其有相同支持度的所有边爨e p s 的 高原e p s 静集台被称为高原空i h - j ( 或简称为p * 空间) 。 因此，从其在宿激和对立类中的支持度意义上来说，p 窳间中的所有e p s 处 于相嗣的重要程度。假设宿类支持度是n ，则谈p 空闻也被发示为p 。空间。 定义2 8 ：e e p s ( e s s e n t i a le m e r g i n gp a t t e r n s ) 4 0 1 ，鲡聚一个项集x 满足下面 的三个条件： l 楚满足一定增长率阂僮黪e p ； 2 程类e 中满足一定的支持发闽值； 3 熟任何真子集都不满足上面两个条件； 则称x 为e e p s ，即簇本显露模式。 e e p s 能够捕捉两个类之间的巨大差异。窀在边界表示法中代表的怒友边界 的集合，因此，也称霞为边界e p s ( b o u n d a r ye m e r g i n gp a t t e r n s ) 3 9 1 。 基本显露援式的挖掘算法 2 3e e p s 的特点 基本萎嚣模式( e s s e n t i a le m e r g i n gp a t t e m s ，e e p s ) 楚一类蒋豫瓣e p s ，在上“一 节我们给出了它的定义，本节将详细讨论e e p s 的性籁以及用e e p s 构造分类器独特 的优点。 e e p s 。是袋示秘透赛戆一组左逮赛戆嶷合，其蠢绞褰豹黉长警。它去捧了零 些包含冗余倍息和噪声的项集，其数激比e p 少得多，并且具有很高的分类效率。 事实上，e e p 是那些“最缎的”e p ，由于如下原因，e e p 被认为怒e p 中最具表达 麓力夔模式： 1 ) 足够商甚至无穷大的增长率确保e e p 具有很好的区分能力。 2 ) 最小支持度阂值确保每个e e p 至少覆盖一定数最的样本，从而具有一定 豹绕诗意义，臻绦它霞静实蘧瞧。 3 ) e e p 的超集对于分类并没有多大用处，其理由如下：假定髓匕历，并鼠 占l 是e e p 。根据定义，五l 具有很搿的增长率，并且被恳覆盖的样本定 罄毅蕊覆盖，获露惩莠不提袋愆墨更多鹣分类僖惑。 在构造分类器的过程中，只有大予定支持度闽值和增长率闽值的e e p s 才 是有意义的。增长率太低的e e p s 区分能力太差，飓够高的增长率保证了e e p s 其鍪莛簿静酝分能力。圈辩谨孤必舔覆羞一定数羹瓣徉本，这榉秘e e p s 霞表懿 特征才具有酱遍意义。支持度过低的e e p s 常常代表地是数据中的噪音或者是训 练集特有的不代表整体数据分布的特征，即表现为过分适应训练集，发现豹知识 不爨有代表後。嚣瑟，矮小支葑凄添壤檬汪了e e p s 粪备一定豹绕诗意义。 e e p s 的超集对分类的意义不大：荫先，e e p s 的所有超集都包含了e e p s ，这 些e p s 反映系列近似的特征。这一系列近似的特缎包含了一个避具代表性的特 征，帮e e p s 掰接逮豹将筑。目辩e e p 爨鸯足够亵斡增长率，它掰籀述静特征凝 备足够好的酝分能力。因此，e e p 的怒集没有为分豢提供更多有用的信息。e e p 反映的是更具有普遍性的知识，它覆盏了所有它的越集覆盖的样本。 e e p 是缀短黥e p ，不目靛e e p 之阂不霹髓存纛色含关系。瓣魏，e e p 之潮 的独立性较好，几乎每个e e p 都为分类提供了新鲜的知识。由于e e p 是e p s 边界表示的左边界，选撵e e p 构造分蹙器就是使用e e p 来代表包含它的所有趟 嶷蘑于分类。彼蕉e e p 分豢霹隘减少分类过程中傻嚣瓣e p 并且强失缀少盼信惑。 基本显露模式的挖掘算法 另外，较短的e p 意味着在分类过程中使用较少的属性，因此利用这样的e e p 建 立分类器不但可以大量压缩分类过程中使用的e p 的数量，而且增加了分类器的 抗噪声能力。 2 4e p s 的边界挖掘算法 前面我们对e p s 和e e p s 的定义进行了介绍，本节将讨论有关e p s 的挖掘问题 主要讲述e p s 的边界挖掘算法口5 1 。 2 4 1e p s 的挖掘问题描述 e p s 的挖掘问题就是在给定增长率闽值的情况下找出所有的p - e p s 。图2 1 的 二维支持度平面有助于我们对挖掘e