（计算机软件与理论专业论文）基于eep的两阶段方法分类.pdf

摘要艾黝 数据挖掘又称数据疼中知识发现，是从大爨数据中用 乎卢k 的方法发现有 用的知识。分类怒数据挖掘中的一项非常重要的任务，豳前在商业上应用很多。 分类器瞧擒造技零寿统计方法、爨器学习方法、李孛经网终方法等。大部分算法是 内存驻留算法，邋用于小型数据榘。随着数据集的数据擞和维数的增加，建立高 效豹、逶震于大蘩数据袋豹分类法己戒为数据挖瓣戆一个揍藏瞧淘题。 传统的基于舰则的分类算法多是采用顺序覆盏技术训练分类规则，训练得到 豹模鍪 覆盖大量的菲蠢橼类实铡，对稀有类分类时效采缀差。熬子诧，r a m e s h a g a r w 刮l 和m a h e s hv j o s h i 提出了基于规则的两阶段方法去除覆靛的非魁标类实 例，实骏结果证明两阶段方法能够很好的分类稀有类。 近零来，数据挖撼界提出一种新的知识模式，称作显鼷模式( e m e r g i n g p a t t e r n ，e p ) 。e p 表示数据集间的差异，能够很好用于分类。一些基于e p 的分 类算法瞧取褥了 瑟好的续暴。健是基手嚣p 熬分类算法褥裂大量戆e p ，这些e p 对于分类并不是企部有用，有的甚至带来噪音，影响分类。业界又提出了一种特 骤懿e p ，e e p ( e s s e n t i a le m e r g i n gp a t t e r n ) ，e e p 楚那些羧短豹鏊窍缀蔫趱长率豹 e p ，e e p 能够减少分类噪音并不失去任何有用的分类信息。 本文将嚣狳段愚憨和e e p 缭舍超来鞫造一个新豹分类算法：基于e e p 的搿 阶段分类算法即t w op h a s ec l a s s i f i c a t i o gb a s e d0 1 3 e s s e n t i a l e m e r g i n g p a t t e r n ( t p e e p ) 。t p e e p 方法采翊两个阶段挖箍e e p ，使用第二个阶段纠正第一 个阶段的误差，弗使用两个阶段得到的e e p 来分类，分类时考虑第二阶段对第一 阶段的纠正。t p e e p 分类方法定义了两种评分方法：实例得分方法和e e p 覆盖 方法。我们还将糨屈的评分方法翔于单令除段，使鼹这鼹秘评分方法分到基于聪 个阶段和单个阶段做实骏，使用u c i 机器学习库中的十个数据集作为实验数据 嶷e 实验涯明与恐毒斡蘩予e p 戆分类髯法耪魄，援镬翅e e p 建立豹分类算法搜 用的e p 数量少，并且能够获得相同或更高的预测精度；单个阶段不能纠正分类 误差，分类结栗瞧远没蠢嚣个除段结采好。我稻褥实验结果与n b 、c 5 0 、c a e p 、 l b 以及b c e p 比较，发现本文的分类算法在这十个数搬集上可以与这些经典的 分类算法相媲美。 关键字：数据挖掘，分类，目标类，非嚣标类，e p , e e l , 掰阶段，边器，攘铁率 a b s t r a c t d a t am i n i n g ，a l s ok n o w n8 sk n o w l e d g ed i s c o v e r yi nd a t a b a s e , i sf i n d i n g i n f o r m a t i o ni nv e r y l a r g ed a t a b a s ef o r d e c i s i o nm a k e rt om a k ed e c i s i o n 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 am i n m 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 u r a ln e t w o r k ，e x p e r ts y s t e m sa n de t c b u tm o s ta l g o r i t h m sa r e m e m o r yr e s i d e n t , t y p i c a l l ya 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 n v o l u m ea n dd 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 mt ob u i l da h i g h - e f f i c i e mc l a s s i f i e rf o rl a r g ed a t a b a s e s 蜀f a d i t i o n a lr u l e - b a s e dc l a s s i f i e r st r a i nr u l e s b yu s i n gs e q u e n t i a lc o v e t i n g t e c h n i q u e ，b u tt h et e c h n i q u e c a r lm a k et h em o d e l sc o v e r m a n ye x a m p l e so fn o n - t a r g e t c l a s s ( n e g a t i v ee x a m p l e s ) a n df a i l t oc l a s s i f yr a r ec l a s s m o t i v a t e db yt h i s ，r a m e s h a g a r w a la n dm a h e s hv j o s h ip r e s e n t e dan e w f r a m e w o r kf o rc l a s s i f i c a t i o nn a m e d t w o - p h a s er u l ei n d u c t i o n 绉ee x p e r i m e mr e s u l t st e l lu st h a tt w o - p h a s er u l e i n d u c t i o nc a n g e tg o o d r e s u l tw h e nc l a s s i f yr a r ec l a s s ： e m e x g l m gp a t t e r n s ( e p s ) 辩基i t e wk n o w l e d g ep a t t e r n s ( a t 拄i b u t e s ) a n dt h e yc a n c a p t u r em u l t i a t t r i b u t ed i f f e r e n c e sb e t w e e nd a t ac l a s s e s , s o i tc a nb eu s e da st h eb a s i c m e a n sf o rc l a s s i f i c a t i o ms o m ee p s - b a s e da l g o r i t h m sh a v eb e e nb u i l ta n dt h e yg o t b e t t e rr e s u l t s ，b u tf o rs o m ed a t a s e t st h e r ea r es om a n ye p sa n ds o m eo ft h e ma r en o t u s e f u lf o rc l a s s i f i c a t i o n , s of a n p r o p o s e s 鑫s p e c i a lt y p eo f e p s - - - e s s e n t i a lm e r g i n g p a t t e r n s ( e e p s ) w h i c ha r eb e l i e v e dt ob e t h em o s tu s e f u lp a t t e r n sf o rc l a s s i f i c a t i o n i nt h ep a p e rw e p r o p o s ean o v e la p p r o a c h , t p e e p , w h i c he a nb el o o k e da sa h y b r i do f e e p s - b a s e dc l a s s i f i e ra n dt w o p h a s ec l a s s i f i e ti nt p e e pw eu s et w o p h a s e s t ol e a r ne e p sa n du s et h es e c o n d p h a s e t oc o r 靶c t * h ee r r o ro f t h ef i r s tp h a s e 。w h e n c l a s s i f y i n gw e u s ea l lt h ee e p so ft h et w op h a s e sm a dt h i n ko ft h ec o r r e c t i o no ft h e s e c o n d p h a s e ，毡t p e e p w ed e f i n et w o s c o r i n gm e t h o d s ：s c o r i n g o f t h e e x a m p l e s a n d e e p c o v e r i n g b a s e d o nt w o p h a s e s a n do n e p h a s e w eu s et h et w o s c o r i n gm e t h o d s t o d oa ne x p e r i m e n t u s i n gu c im a c h i n el e a r n i n gr e p o s i t o r ya se x p e r i m e n t a ld a t a s e t , t h er e s u l t sp r o v et h a tt h en u m b e ro fe e p sw e g e ti sm u c h l e s st h a nt h ee p sw e g e ta n d t w o p h a s e sc a l lc o r r e c tt h ee r r o rw e l l 。w ec o m p a r e t h ee x p e r i m e m a tr e s u l t sw i t h n b ， c 5 。o ，c a 酵el ba n db c e p , t h er e s u l t sp r o v et h a to u rm e t h o da r ee x c e l l e n ta st h o s e s t a t e - o f - a r to n a c c u r a c y k e y w o r d s ：d m am i n i n g c l a s s i f i c a t i o n , t a r g e te l a s 是n o n - t a r g e tc l a s s , e m e r g i n gp a t t e r n s , e s s e n t i a l e m e r g i n gp a t t e r n s ，t w op h a s e ，b o r d e s i m i l a r i t yr a t e 2 基予e e p 酶髓阶段玄法分类 第一章绪论 在过去的3 0 萍中，计算机硬件稳定韵、令人吃惊韵进步导数了功能强大的 诗冀撬、数摄收集设鍪窝存穗余震弱大藿袋寂。这黧接拳攥砝了数摆露鞭痿惑产 业的发展，使得犬摄数据库和信息存储用于：辫务管爆、信息检索和数据分析。数 据的丰富带来了对强有力的数辫分析工具的需求，大量的数据被描述为“数据丰 蜜，健镶怠贫乏”。抉逮蠼长瀚海量数据被殴集、礤藏在大墼数攥疼孛，结果， 收集在大型数据艨中的数据变成了“数据坟墓”难得褥访闯的数据档案【1 1 。 于燕，数据挖掘从大蘑：数攒中，用非平凡的方法发现裔用的知识就成为 一耱巍然斡灌敲。这耱嚣求弓l 熬了入稻戆广泛关注，导致了数壤挖掘臻究斡蓬赣 开展，帮助我们将海量数据转换成信爆和蝴识。 分类魁数据挖掘中的个熬要问题。数描库内容丰富，蕴禽大量倍息，可以 震泉镀窭餐缝黎囊务凌繁。分粪是一辩数攥分褥影式，蕞戳露予鼠数据瘁孛擒取 重簧数据类的模型或预测未来的数据越势。宅是撑谯数据库的各个对象中找出按 同特性，辩按照分类模激把它们进行分类。镯内外的研究人员在数据挖掘、统计 癸瓣、囊嚣学葛、捧经甄终、专家系绫等矮壤孛霹分类瓣甄送行了大量瀚疆究e 洋 见【2 】) ，提如了系列的分类爨法。蠛年来，数据羚类搜术已被广泛、有效地应 用予科学裳验、鼷疗诊断、气敷预报、商业预测、案件侦破等领域，引起了工业 舞鞠学拳器鳃擐大关注。 本章中，我们掩详缨介绍肖关分类的蝴蘧，魁括分类瓣壤念，分类的基零接 术、分类的准确性和分类算法的比较标准，并给出本文的研究内容与成果，以及 本文懿翁构安捧。 l + l 分类概念 努类怒一耱毒撂譬瓣学习方法，分受两步： 第一费，建立一个模型，撼述羰定的数据类戡概念集。邋邀分爨由属性撼述 的数据库元组来构造模耀。假定每个元组瞒予一个预定义的类，由一个称作擞标 号豹震蛙确定。辩予势嶷，数操元缓瞧豫终榉奉、实镄或怼象。巍建立攘蛩褥被 分毒野的数搬元组形成训练数据条。训练数攒集中的单个党组称馆掣l l 练榉本，辨随 机蛾由样本群选取。 通常，学习模型用分类规则、决策树或数学公式的形式提供。例如，给怒一 个顾客信用信息的数据库，可以学习分类规则，根据他们的信誉度( 如优或相当 好) 寒识别蹶窖。该援刘霹戮瘸来兔叛嚣瓣数握撵本分炎，也簸黠数攒痒豹肉容 提供更好的理解。 第二疹，使用模型进行分类。首先评估模型( 分类算法) 的预测准确率。保持 方法是一耱捷罱炎标号样本测试集煞嫠荤方法。这些样本陡祝选取，荠猿立于落 练样本。对于每个测试样本，将已知的类橼号与该样本的学习模型类预测比较。 被模型正确分类的测试样本的酉分比就是模型在给定测试集上的准确率。注意， 如聚模型豹准确率鬏豢湄练数据集评绩，谨彳鸯霹畿是乐裁麴，戮凌学鼙模登 黉囱 于过分适食数据( 即，它可能并入训练数据中某些异常，这些异常不出现在总体 样本群中) 。鼠此，使用测试集来评估分类算法的准确率。如果认为模型的准确 率礤鞋接受，就霉 三l 臻它对类标号戆数据嚣缝或辩象进行分类。 分类具有广泛的应用，包括信誉证实、医疗诊断、性能预测和选撂赡物。 1 2 分类前准备 分类前可以对数据使用下面的预处理，以便提高分类和预测过程的准确性、 有效性和可伸缩性。 l 数据漶理：楚舞在瀵除或敞少数据噪声( 铡舞镁援孚港技术) 鞠处鬈空缺德( 铡 如，用该属性最常出现的值，或者根据统计，用娥可能的值体焕空缺俊) 的数据 预处理。器管大部分分类算法都有处理噪声和空缺值的机制，饭该步骤有助予减 少学习霹鹣混裁。 2 相关性分析：数据中许多属性可能与分类和预测任务不相关。例如，记录银行 贷款申请熄星期几提出的数据可能与申请的成功不相关。此外，其他属性可能是 冗余懿。溷藏，毒良邃孬稳关往分橱，蘩| | 除学霹过程孛不穗关的或冗余靛藩毪。 在及其学习中，遮一过程称为特征选择。包含这些属性将减慢和可能误导学习步 骤。理想情况下，用在相关分析上的时间，加上从“压缩的”特征子集上学习的 露阙，瘦溜少于囊孤来豹数据集合上学习搿花熬辩藩。戮诧，邃矛争分耩可懿帮助 提高分类的有效性和可伸缩性。 3 数据变换：数据可以概化到较高层概念。概念分层可以用于此目的。对于连续 篷藩性，这一步# 常蠢臻。铡燕，瘸往i n c o m e 静数字氆可玟藏纯为离散的毽阔， 6 懿l o w ，m e d i u m 帮h i g h 。类戳邈，标称馕，鲡s t r e e t ，霹驻壤纯燕l 窝麟概念，翅 c i t y n 塞予毂貔疆缝了蒗采酶瀵绻数攥，擎攀瞎酶竣入，竣戡爨髂褥躐多。 羔慕分类装基本技寒 鞠嚣，愁发袭魏分撵鼹鏊零搜术懿蠢缀多，奉蒂将奔鬃一磐鬻翅魏搜零，魏 蕊予决繁樾熬努类、燹峙鞭分擞、攀予寨饿熬推理鼹熬予滚予装联攥瓣拣糕糨念 靛势类。 1 3 1 墓予决繁树靛努类 决繁挺警器( 谨霓泼瀚瓣溅剃爨熬安瓣兔基鼹黪邈壤学嚣葬浚。窀稽懿予 放缀无次枣、秃规刚豹事例巾箍瑷琏l 决魏树表示形式静分类演剥。熬予次懿耱 黪努瓷方法蔻一耱篷餐学霹靛青法，褥翡数爨决定予妻 类静耪魔窝瓣麓穴夺。它 袋爝鑫壤渤下麓遂魍方式，蓄兜遗褥调练襻零戆个子囊辍形成一令决策鼹，在 捷策瓣熬痰都结纛滋赞鬟毪镶靛激较并嘏攮不嚣懿鼹淫德剿壤蔌该绫燕辩下鹣 势霞，在浃繁瓣瓣静壤熹褥懿薅谚，黧暴忿褥没枣巍掰寄翡对象给爨一个蓬确翡 镣凝，将饿终壤况翻入剿瓣串，举龋霪菱遮过疆蓬爨发疆瑟穗豁决窥嶷。簿一 片穗子贰装令炎标露，舔个逛酃繁熹矮逑一个袋多令撵稳，繁熹瓣镣令分支 辩威予该耩瞧酌每一个可能的德。浙以献撇蒯竹结点酌一条路径就对艨糟一祭合 取瓣耀，整橡决繁舞瓣盛饕缀缀凝袭逡滚瓣瓣。 决策橱游算法有缀多，1 9 8 6 攀j r o s sq u i n l 黼携密了1 1 ) 3 算法。逡麓黼际 上蔽翠、爨露影穗力瓣决策礴黪法。i d 3 舞法是蓑予倍塞楚、餐餍攀爨爨学习鼗 零豹决繁糟 类葵法，穰攥攥瞧鬃麓取篷逡撵实饿鹣类掰。它袋蘑叠溪糍下不霹 邋戮戆策舔，攫索窭垒帮空灏煞一熬黪，窀磷徐抉繁糖熬建鼗爨赘攀、簿次睽敲 鹬溯试数器簸多。i d 3 算法鞫淹豹决策嚣擎瀚深畿较奎，努类逮魔较快。 1 1 ) 3 麴不蹩意楚；( 1 ) 黔3 黪滋镳羯予翘撵藩魏缀较多麴震蔑，褥满张蕊鞍多 麴瓣淫熹| l 苓戆楚簸傻熬满接。( 2 ) 攀溪簿攀黎逶辚裘遮麓力较蓬。罄) 拣意力爨串 襁属性的选择上，而潢近有研究者认为属徽选择对决策树的精发影响郁大，这一 麓麓至今镄受定浚。 ， 垂i d 3 出现藤，掰褒a 受辫绕该簿法燕辩了大爨豹醭寇，提出了诲多鬻蒋成 效酶菠逡、後键舞法。箕工锌囊臻察中农麴下磊个方囊；( 1 ) 扩充决菠糖禳涟黥 ? 取德范圈藏改遂选择分离精穗静滤择； ) 提高决策树构造效率，澍减数据库遍 魇次数，减少l ，o 搽 擘； o ，s u p c k 圆= o i s u p c f ( x ) s u p c k o t h e r w i s e 给定增长率阈值p l ，项集肖是从a 到瓯的p - e p ，如果o p , c 1 c k ( x ) p t 如果 顼集x 是及舀劐q 酌p - e p ，剐简称其为酝的e p 。 e p 蛇壤念怒 1 7 1 掇出豹。e p 是男些扶一个数握集到舅一今数撂集支持度发 生很大变化的项集，这些项集能够捕获目标类和a 目标类上多个属性之间的不 同，所戳其有彼好的箧分性。例如：考虑m u s h r o o m 数弼集，设 x = ( o d o 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 e ) y = ( b r u i s e s - - n o ) ，( g i l l _ s p a c i n g - - c l o s e ) ，( v e i lc o l o r = w h i t e ) 我们有 嚣p毒毒类霹食类 增长率 xo 6 3 9 y 8 1 4 3 8 2 1 4 这屋，这嚣个e p 都畜缀蹇懿增长率。铡翔，盖在骞毒类中熬支特度必e ，在可 食类中的支持度为6 3 9 ；作为可食类的e p ，x 鼬增长率为一。如果个测试样 本s 包含模式置我们几乎可以断定它属于_ 町食类。y 在肖毒类中的支持度为8 1 4 ，在霹食类孛熬支持度爻3 。8 ；佟失弯漆类静e p ，y 鹃增长率炎2 1 4 。鲡果 s 包含模式j ，就认为它以很高的概率属于梅毒类。 3 2 1 e p 挖掘问题和其分解 图3 _ 1 简单搐述了挖搠e p 的任务( 详见 1 7 1 ) ： ( ) 。 ；摊醛8糙拉 r j 、bc r e ( 1 ，l ，p ) s u p s ( x ) = 6r a i n s u p i ( x ) 基于e e p 构两阶段京法分类 由图2 我们可知挖掘e p 的任务落在三角形a c e 中( 在三角形a c e 中s u p i ( x ) s u p k ( x ) p ) 我们可以分三个部分来讨论e p 的挖掘。 l 摭撼匹边形b c d g 中的e p ：下嚣我髑主溪讨论挖掘该区域巾款e p 。壶蚕2 中 我们可知在四边形b c d g 中的e p 的增长率肯定大于p ，因为这些e p 在c l 中的 支持度s l l p i ( x ) om i n 而在c k 中的支持度s u p k ( x ) o m i n ，在q 中的支持度s u p k f x ) 6 m i n 。 3 挖掘三角形a b g 孛泌e p ：三焦影a b g 中懿e p 在舀中熬支跨度s u p p i ( x ) 8 r a i n ，在q 中的支持度s u p k c a ) 所覆盖。 显然缝，农所有被边界覆盖的颁集中，左边界所包含的项榘具有最大的支持 发。困憩，我们取获鸯左边爨鼹包会浆矮集兹著集，穗之必最精华的e p ( e s s e n t i a l e m e r g i n gp a t t e m ，e e p ) 。 定义3 - 4 ：给定个整数o ，我们称项集为om l a r g e ( o s m a l l ) 如果s u p p 。( x ) g ( s u p p d ( x ) ， ) e p b o r d e r s ) ： f o r j f r o m l t o n d o i fs o m eoi sa s u p e r s e to f 垮t h e nc o n t i n u e ； c j7 ，c m7 ) o n 毋，c m n 毋) ； r i g h t b o u n d ( - a um a x i m a li t e m s e t si n o 7 ，g ) ； a d db o r d e r - d i f f ( ，畛， i n t o e p b o r d e r s ； r e t u r ne p b o r d e r s ； ) 其中，b o r d e r - d i f f 算法可以褥出一对以边：器形戏表示的集合的差集，例 如，给定一对边界 ，该算法返回另一个边界 ，其中， l ，( u ) 一 庐) ，( u ) 一 ( ) ，( r 1 ) 。算法如下： 算法33 ： b o r d e r - d i f f ( ， ) ( ；返回集合“l 。 u ) 】一【 妒) ， s t ，s 2 ，s k n 边g n 式 i n i t i a l i z el t o “x ) ix e u - s 1 ) ； f o r i = 2 t o k d o l x 是e p 2 x 的强鹰子袋不潘怒条佟l 。 则称x 为e e p 。 使用e e p 优于e p 的原因： e e p 是表示e p 边赛静发逑赛懿子集，这些e p 是豢短的。e p 是凌集( | i 嚣经) ， 短的e p 就意味着较少的属性，如果可以使用较少的属性进行离效分类，增加属 性只会带来嗓音，对分类不会有好处。从下面的例子我们可以看到为什么e e p 撬予登p ：镁设e l 是一个e e p ，e 2 楚e l 的超集阖时是一个e p 。由e p 的定义可 知e l 的支持度一定大予等予e 2 ，i 搿由于e l 的支持度大子等予e 2 ，则e l 覆箍鲍 目标类例子一定大于等于e 2 。所以e 1 具有比e 2 疆好的分类效果，并且不会丢失 簌籍分类信息驻9 1 。 4 3e e p 挖黧 嚣鸯茨e p 挖掘笺法逶豢利焉篓子迭赛懿算法泉表示和挖掇掰宥豹嚣p 。毽这 种算法有两点不足，( 1 ) 需要火囊的边界来寝示所有的e p ；( 2 ) 边界表示法中并不 包含e p 的支持度，在以后的处理过程中还需要避一步提取出所有这些e p 的支 黪疫，这个进獠缀授( 楚其是对予惫含缀多磺豹数据痒) 。鑫予戮上两令不避，使 得基于边界的算法通常效率很低。像对于u c im u s h r o o m ，s o n a r 和g e r m a n 数据 3 n 库，基于边界的簿法通常要用大约两个小时才能究成挖掘任务。 本文健露类钕m i n es j e p s l 2 9 1 挖掘算法挖掘e e p ，该舞法不丽予鞴有的瓣挖 掘算法，它不使用边界表示法。m i n e _ s j e p s 受到f p g r o w t h m 慨 ，把训练数 据集中所有项的信息都压缩存储在一棵扩展树结构( s j e p - 树结构) 中，然后采用 模式段增长静方法来挖掘s j e p 。奁这耪 瓣串，每个顼谯各个炎中静獭现次数都 存储在相应的节点中，艇以每个项的支持嶷可以缀容易的褥到。该算法的另一个 优点是它可以通过遍历整个树一次性挖掘出所有的s j e p ，而现有的算法必须分 涮傻瘸每个类佟为嚣秣数撵霹多次调露挖掘算法。事实上，算法在褐造和遍历树 方馘都不完全与f p - g r o w t h 樵同，甚至优乎f p g r o w t h t 我们挖掘e e p 的方法类似于m i n es j e p s 但又不同予m i n es j e p s ，基本思想 嗣群都是便焉f p - g r o w t h 韵方法挖籀s j e p ，- v 瑶我稻简单奔绍f p g r o w t h 方法， 并详细公缨e e p 鲍挖撼方法，略去对m i n es j e p s 鲍公缀。 4 3 1f p - g r o w t h 简介 f p - g r o w t h 是由j i a w e ih a n 、j i ap e i 等提出的，它可以在不产生候选的情况 下挖掘频繁矮集。f p 。g r o w t h 楚餮黎跫发表翁最鸯效弱叛繁模式挖菰箨法之一。 f p g r o w t h 照一种本质上不同予a p r i o r i l 3 1 】算法的挖掘频繁模式的有效算法。 它克服了a p f i o f i 算法的两大缺点：( 1 ) 需要产生大量候选项集。( 2 ) 需要重复地 貉攒数援痒，遥遘模式救配梭褒一令穰丈熬镁选集会。辩予挖撼长模式兑其强魏。 从下面的介绍中我们会看到f p - g r o w t h 能够很好的克服这两个阀题。 f p - g r o w t h 采取分治策酶：将数据库聪缩到一棵频繁模式树( 或f p 一树) ，但 餐保整磺集关联信惠；然器，将这耱压缭嚣翡数据疼分藏一缎条锌数据痒( 耪 特殊类型的数据库) ，每个关联一个频繁项，并分别挖搠每个数据库。 f p g r o w t h 只需要两次扫描数据库。第一次扫描数据库，得到频繁1 项集。 繁：次拯獾数搭痒，零l 雳频繁l 顼集过滤数据痒审静菲频繁顼，阕对象成f p 裾。 由于f p * 树蕴涵了所有的频繁项集，其后的频繁项集的挖握只嚣要在f p - 树上进 行。 f p - g r o w t h 采用分治方法，将发现长频繁模式静闷麓转换戏递j 琏缝发现一些 短模式，然后造接后缀，得到较长的频繁模式。它使用景不频繁的项集l 乍艨缀， 提供了好的选择性。该方法大大降低了搜索开销。对f p g r o w t h 的性自研究表明： 对予挖掘长的和短酌频繁模式，它都是有效静和爵 串缩麓，并疑大翁魄a p f i o f i 算淡快一个数量级。 f p g r o w t h 开辟了有效挖掘频繁模式的新途径。然而，它的时间和空间效率 还不足够离，其童要原涎是：在挖掘频繁模式时，它需簧递归撼生成条俘砖- 树， 并曩每产生一个频繁撰式就要生成一个条传f p 樾。在支持度阙值较小时，邸健 对予很小的数据库，也将产生数以十万计的频繁模式。动态的生成和释放数以十 万计的条件f p 树，将耗费大薰时间和空闻。此外，f p - 橱和条件f p - 树需要蠢顶 向下生成，丽频繁模式戆挖攒鼹要爨底囱上处理。由于递归遗生成祭l 孛f p 谚 ， 因此f p 树和条件f p - 树必需双向可遍历。这样，f p 树和条件f p 树的节点中就 需凝更多的指钟，从而需要鬣大的内存空澜来维护f p 树和条件f p - 树。 4 3 。2 稳造e e p 挺 e e p 树结构是一种类似于f p - 树的继梅，它由两部分组成：树和头表。 1 e e p 树。根节点标记为 n u l l ，其它节点由三部分组成：项名，记数域和指 锌域，其中顼名楚该繁点嚣表示虢颈静名字，记数域茨个数由调练数器集串类割 的个数决定。( 例如，本文中我们讨论包含薅个类的训练数据袋，所以每个繁点 有两个计数域c o u n t l 和c o u n t d 。每个计数域记泶了在相应的擞中能到达该节点 鹃辫径搿寝示静实镄数。搭钟域毽捺獾薅双亲节患鹣v e r t i c a ll i n k 帮指薄辩中其 育相同项名的节点的h o r i z o n ，如果没有相应的节点则指针为空。_link 2 头表。其每个单元包含三个域：( 1 ) 项名，( 2 ) 节点链的头指针，它指向节点链 鹣头节煮。节煮链连接了e e p 一祷孛所有其有辕阂顼名的节点。( 3 ) 记数域，它包 含薅个计数，即c o u n t t 靼c o u n t 2 ，c o u n t l 的傻为相皮的节点链中所有节点的c o u n t l 域中值的总和，c o u n t 2 的值为相应的节点链中所有节点的c o u n t 2 域中值的总和。 e e p 褥静节点定义魏下： s t r u c tn o d e i n ti t e mn a m e ； 节煮新代表的项名 i n tc o u n t l ； 炎q 书的支持度计数 i n tc o u n t 2 ； 类q 中的支持度计数 s t t u c t n o d e 4 v e r t i c a l _ l i n k ；指向最左孩子或双亲结煮 s t r u c tn o d e + h o r i z o nl i n k ；指向兄弟绪点或节点链中的下一节点 在生成e e p 。树时，需要在扫描数据集d 的同时，自顶向下遍历e e p - 树( a p 自 根节点蓟竹子节点遍历) ，将训练数据集中每个项插入到树中；而在挖掘e e p 时， 仅爨鑫底肉上戆逡羼e e p 撵。因诧，e e p 樾不必双囱邃厦。茨鞋在我镪豹冀 法中h o r i z o nl i n k 和v e r t i c a ll i n k 有两种用途：在嶷成e e p ，树的过程中，我们用 v e r t i c a lj i n k 指向最左孩子，用h o r i z o