（计算机应用技术专业论文）一种扩展的否定关联规则形式及其挖掘算法.pdf

摘要 数据挖掘，又称为数据库中的知识发现( k d d ) ，出现于“信息丰富而知识贫乏” 的二十世纪八十年代后期之后，倍受关注，并得到广泛研究 关联规则作为数据挖掘中的一种重要模式，在1 9 9 7 年由r a g r a w a l 等人首次提 出【1 】，其对应的挖掘算法a p r i o r i 2 1 也被提出最初提出的关联规则是不带联结词 “一”的正关联规则，而且目前大部分工作都集中在正关联规则的研究上近来，否定 关联规则挖掘引起人们的注意，并证明是有用的 1 9 9 7 年，s b r i n 等人在( 5 】中首次提及否定关联据我们所知，自那以后人们提 出了三种有代表性的否定关联规则形式，并提出了三种对应的挖掘方法但这三种形 式都不够一般化，比如它们都不能表达形如“n 书 一( c ad ) 一e a 、， ，( 9 h z ) ” 的规则形式而且，三种挖掘方法在挖掘能力、精确性和效率上存在一些缺陷。 本文提出了一种扩展的否定关联规则形式，并提出了一种相应的挖掘算法a m e n a r 以挖掘扩展的否定关联规则这种扩展形式比以往提出的形式更一般化并具有 更强的表达能力，因为以往的形式都是扩展形式的特例a m e n a r 是一种基于内 存的算法我们选取一种高度压缩的数据结构p a t r i c i at i r e 将原始数据库存放在内存 中整个挖掘过程在内存中的p a t r i c i at r i e 上执行，而且只需扫描两遍数据库另外， a m e n a r 算法删除了有冲突的规则和两类冗余规则我们将a m e n a r 算法和以往 的两种算法运行在两个数据集上实验结果表明： a m e n a l l 算法在挖掘能力、精 确性、空间效率上都优于以前的挖掘方法而且，当用在稀疏、简单数据库上，当 m i n s u p 值高到一定程度时，a m e n a r 算法具有更高的时间效率我们的工作将把 否定关联规则的相关应用推广到更宽的领域 关键词：数据挖掘，否定关联规则，扩展形式，p a t r i c i at i r e a b s t r a c t d a t am i n i n g ，a l s oc a l l e dk n o w l e d g ed i s c o v e r yi nd a t a b a s e s ( k d d ) ，e m e r g e di nt h e s i t u a t i o no f “d a t ar i c hh u ti n f o r m a t i o nf k n o w l e d g e lp o o r ”i nt h el a t e1 9 8 0 s s j n e e t h e n ，i th a sa t t r a c t e dag r e a td e n lo fa t t e n t i o na n dh a sb e e ne x t e n s i v e l ys t u d i e d a s s o c i a t i o nr u l e ，a sa ni m p o r t a n tp a t t e r ni nd a t am i n i n g ，w a sf i r s tp r o p o s e db y r a g r a w a le ta 1 i n1 9 9 3 1 】a n dac o r r e s p o n d i n gm i n i n ga l g o r i t h ma p r i o r i 【2 】w a s p f e s e n t e dt h eo r i g i n a l l yp r o p o s e da s s o c i a t i o nr u l ei sp o s i t i v ea s s o c i a t i o nr u l e w i t h o u tt h ec o n n e c t i v e “ 1 1a n dm o s to fe x i s t i n gw o r kh a sc o n c e n t r a t e do np o s i t i v e a s s o c i a t i o n s r e c e n t l y , m i n i n gn e g a t i v ea s s o c i a t i o nr u l e sh a sb e e ng i v e ns o m e a t t e n t i o na n dh a sp r o v e dt ob eu s e f u l n e g a t i v ea s s o c i a t i o ni na s s o c i a t i o nr u l e sw a sf i r s tp o i n t e do u tb ys b r i ne ta 1 i n1 9 9 7 5 s i n c et h e n ，t ot h eb e s to fo u rk n o w l e d g e ，t h r e et y p i c a lf o r m sf o rn e g a t i v e a s s o c i a t i o nr u l e sa n dt h r e ec o r r e s p o n d i n gm i n i n gm e t h o d sh a v eb e e np r o p o s e d ，b u t n o n eo ft h ef o r m si sg e n e r a le n o u g ht or e p r e s e n ts u c hag e n e r a lf o r ma s “aa _ - 6 - - ( c d ) ea 一- ，a 一、( 9ah z ) ”，a n dt h ec o r r e s p o n d i n gm i n i n gm e t h o d sh a v es o m e i m i t a t i o n so nm i t r i n gp o w e r ，a c c u r a c ya n de f f i c i e n c y t h i st h e s i sp r o p o s e sa ne x t e n d e df o r mf e f lf o rn e g a t i v ea s s o c i a t i o nr u l e s ，a n d p r e s e n t sac o r r e s p o n d i n gm i n i n ga l g o r i t h mf o z m i n i n ge x t e n d e dn e g a t i v ea s s o c i a t i o n r u l e ( a m e n a r ) t h ee fi sm o r eg e n e r a la n dm o r ee x p r e s s i v et h a np r e v i o u sf o r m s ， s i n c ea lj p r e v i o u sf o r m sf a 】1w i t h i ns p e c i a lc a s e so ft h ee f a m e n a rj 8am e m o r y b a s e da l g o r i t h mah i g hc o m p a c td a t as t r u c t u r ep a t r i c i at r i ei sc h o s e nt os t o r e o r i g i n a ld a t a b a s ei nm a i nn l e l t l o rv t h cw h o l em i n i n gp r o c e s si sp e r f o r m e do f tt h e p a t r i c i at r i ei nn l a i nm e m o r y ，a n do n l yt w os c a n so ft h ed a t a b a s ea r e r e q u i r e d i n a d d i t i o n ，c o n f l i c t i n gr u l e sa n dt w ok i n d so fr e d u n d a n tr u l e sa r ep r u n e di na m e n a r a m e n a r ，a n dt w op r e v i o u sm i n i n gm e t h o d sa r ec o n d u c t e do nt w od a t a s e t s e x ， p e r i m e n t a r e s u l t ss h o wt h a ta m e n a ro u t p e r f o r m st h ep r e v i o u sm i n i n gm e t h o d s i nm i n i n gp o w e r ，a c c t i a c ya n ds p a c ee f f i c i e n c y , a n di sm o r ee f f i c i e n to ns p a r s ea n d s i m p l ed a t a s e t , sw h e nm i n s u pi sh i g ht os o m ed e g r e e o u rw o r kw i l le x t e n dr e l a t i v e a p p l i c a t i o n so fn e g a t i v ea s s o c i a t i o nr u l e st oab r o a d e rr a n g e k e y w o r d s ：d a t am i n i n g , n e g a t i v ea s s o c i a t i o nr u l e s ，e x t e n d e df o r m ，p a t r i c i at r i e c h a p t e r1 i n t r o d u c t i o n s i n c ei t se m e r g e n c ei nt h el a t e1 9 8 0 s ，d a t am i n i n gh a sa t t r a c t e dag r e a td e a lo f a t t e n t i o na n dh a sb e e ne x t e n s i v e l ys t u d i e d 1 1w h a ti sd a t am i n i n g ? d a t am i n i n g ，a l s oc a l l e dk n o w l e d g ed i s c o v e r yi nd a t a b a s e s ( k d d ) ，i st h ep r o c e s s o fe x t r a c t i n go r “m i n i n g ”i m p l i c i t ，p r e v i o u s l yu n k n o w na n dp o t e n t i a l l yu s e f u lk n o w l e d g ef r o ml a r g ea m o u n t so fd a t a i ti s am u l t i d i 8 c i p l i l l a r yf i e l d ：d r a w i n gw o r kf r o m a r e a si n c l u d i n gd a t a b a s et e c h n o l o g y ，a r t i f i c i a li n t e l l i g e n c e m a c h i n el e a r n i n g ，n e u r a l n e t w o r k s ，s t a t i s t i c s ，k n o w l e d g ea c q u i s i t i o n ，i n f o r m a t i o nr e t r i e v a l ，h i g hp e r f o r m a n c e c o m p u t i n g ，a n dd a t av i s u a l i z a t i o n 1 6 m a n yp e o p l et r e a td a t am i n i n ga sas y n o n y mf o rk d d a l t e r n a t i v e l y ，o t h e r sv i e w d a t am i n i n ga 8s i m p l yn i le s s e n t i a ls t e pi nt h ep r o c e s so fk d d a ss h o w ni nf i g 13 ， k d dc o n s i s t so ft h ef o l l o w i n gs t e p s ： - d a t ac l e a n i n g ( t or e m o v en o i s eo ri r r e l e v a n td a t a ) d a t ai n t e g r a t i o n ( w h e r em u l t i p l ed a t as o u r c e sm a yb ec o m b i n e d ) d a t as e l e c t i o n ( w h e r ed a t ar e l e v a n tt ot h ea n a l y s i st a s ka r er e t r i e v e df r o mt h e d a t a b a s e ) d a t at r a n s f o r m a t i o n ( w h e r ed a t aa r et r a n s f o r m e do rc o n s o l i d a t e di n t of o r m s a p p r o p r i a t ef o rm i n i n gb yp e r f o r m i n gs u m m a r yo ra g g r e g a t i o no p e r a t i o n s ) d a t am i n i n g ( a ne s s e n t i a lp r o c e s sw h e r ei n t e l l i g e n tm e t h o d sa r ea p p l i e di no r d e r t oe x t r a c td a t ap a t t e r n s ) 。p a t t e r ne v a l u a t i o nft oi d e n t i f yt h et r u l yi n t e r e s t i n gp a t t e r n sr e p r e s e n t i n gk n o w l e d g eb a s e do ns o m ei n t e r e s t i n g n e s sm e a s u r e s ) l c h a p t e rj i n t r o d u c t i o n 2 k n o w l e d g ep r e s e n t a t i o n ( w h e r ev i s u a l i z a t i o na n dk n o w l e d g er e p r e s e n t a t i o nt e c h n i q u e sa r eu s e dt or e p r e s e n tt h em i n e dk n o w l e d g et ot h eu s e r ) f i g u r e11 ：d a t am i n i n g0 8 ap r o c e s so fk d d 1 2w h a tm o t i v a t e dd a t am i n i n g ? n e c e s s i t yi s t h em o t h e ro i n v e n t i o n d a t am i n i n ge m e r g e di nt h e s i t u a t i o no f “d a t ar i c hb u ti n f o r m a t i o n ( k n o w l e d g e ) p o o r ”i nt h e1 9 8 0 s ，t h ef a s t g r o w i n g ， t r e m e n d o u sa m o n l t to fd a t a ，c o l l e c t e da n ds t o r e di nl a r g ea n dn u m e r o u sd a t a b a s e s ， f a re x c e e d e do u rh u m a na b i l i t yf o rc o m p r e h e n s i o n a sar e s u l t ，w ew e r es u b m e r g e d i nl a r g ea m o u n t so fd a t aa n ds h o r to fi n f o r m a t i o na n dk n o w l e d g et h ew i d e n i n g g a pb e t w e e nd a t aa n dk n o w l e d g ec a t bf o rt e c h n o l o g i e sw h i r l c a ne x t r a c to r “m i n e ” k n o w l e d g ef r o ml a r g ea m o u n t so fd a t aa ss h o w ni nf i g 1l f r o mt h ea n g l eo ft h eh i s t o r yo fd a a b a s et e c h n o l o g yd e v e l o p m e n t ，d a t am i n i n g c a 【1b ev i e w e da sar e s u l to ft h en a t u r a le v o l u t i o no fd a t a b a s et e c l m o l o g ya sf i g 1 2 s h o w s c h ap t e r1 i n t r o du c t i o n 一 am o u n t a i no fd a t a f i g u r el2 ：d a t am i n i n g 1 3d a t am i n i n g o nw h a tk i n do fd a t a ? 3 a ss h o w ni nf i g1 3 ，d a t am i n i n gi sp e r f o r m e do i ld a t aw a r e h o u s e si np r i n c i p l e ，d a t a m i n i n gs h o u l db ea p p l i c a b l et oa n yk i n d o fi n f o r m a t i o nr e p o s i t o r y t h i si n c l u d e s d a t aw a r e h o u s e s 、r e l a t i o u a ld a t a b a s e s ，t r a n s a c t i o n a ld a t a b a s e s ，w o r l d w i d ew e b ， a n da d v a n c e dd a t a b a s e s s u c ha so b j e c t o r i e n t e dd a t a b a s e s ，s p a t i a ld a t a b a g e s ，t i m e s e r i e sd a t a b a s e s ，t e x td a t a b a s e s ，a n dm u l t i m e d i ad a t a b a s e s t h r e et y p i c a ld a t a b a s e s a r ei 【1 t r ( 1 d 1i c e da s b u o w s 1 3 1r e l a t i o n a ld a t a b a s e s ar e l a t i o h a ld a t a b a s ei sac o l l e c t i o no ft a b l e s e a c ht a b l ei sat w o d i m e n s i o n a lt a b l e w h i c hc o n s i s t so fas e to fa t t r i b u t e s ( c o u m n so rf i e l d s ) a n du s u a l l ys t o r e sal a t g e n u m b e ro ft u p l e s ( r o w so rr e c o r d s ) e a c ht u p l ei nar e l a t i o n a lt a b l er e p r e s e n t sa n o b j e c ti d e n t i f i e db yau n i q u ek e ya n dd e s c r i b e db yas e to fa t t r i b u t e sv a l u e s 1 3 2d a t aw a r e h o u s e s ad a t aw a r e h o u s ei sar e p o s i t o r yo fi n f o r m a t i o nc o l l e c t e df r o mn m l t i p l es o u r c e s ，s t o r e d u n d e rau n i f i e ds c h e m a ，a n dw h i c hu s u a l l yr e s i d e sa tas i n g l es i t e d a t aw a r e h o u s e s a r ec o n s t r u c t e dv i aap r o c e s so fd a t ac l e a n i n g ，d a t at r a n s f o r m a t i o n ，d a t ai n t e g r a t i o n ， d a t al o a d i n g a n dp e r i o d i cd a t ar e f r e s h i n g ad a t aw a r e h o u s ei su s u a l l ym o d e l e d b yam u l t i d i m e n s i o n a ld a t a b a s es t r u c t u r e w h e r ee a c hd i m e n s i o nc o r r e s p o n d st oa n a t t r i b u t eo ras e to fa t t r i b u t e si nt h es c h e m a a n de a c hc e l ls t o r e st h ev a l u eo fs o m e a g g r e g a t em e a s u r es u c ha sc o u n to rs a l e sa m o u n t t h ea c t u a lp h y s i c a ls t r u c t u r eo f ad a t aw a r e h o u s er n a vb ear e l a t i o n a ld a t as t o r eo ram u l t i d i m e n s i o n a ld a t ac u b e i t p r o v i d e sam u l t i d i m e n s i o n a lv i e wo fd a t aa n da l l o w st h ep r e c o m p u t a t i o na n d 阻s t e h a p t e r1 。i n t r o du c t i o n f i g u r e13 ：t h ee v o l u t i o no fd a t a b a s et e c h n o l o g y a c c e s s i n go fs u m m a r i z e dd a t a 1 3 3 叶a n s a c t i o n a ld a t a b a s e s at r a n s a c t i o n a ld a t a b a s ec o n s i s t so faf i l ew h e r ee a c hr e c o r dr e p r e s e n t sat r a n s a c t i o n at r a n s a c t i o nt y p i c a l l yi n c l u d e sau n i q u et r a n s a c t i o ni d e n t i t yn u m b e r ( t i d ) ，a n da l i s to ft h ei t e m sm a k i n gu pt h et r a n s a c t i o n ( s u c ha si t e m sp u r c h a s e di nas t o r e ) ，t h e t r a n s a c t i o n a ld a t a b a s em a yh a v ea d d i t i o n s lt a b l e sa s s o c i a t e dw i t hi t ，w h i c hc o n t a i n o t h e ri n f o r m a t i o nr e g a r d i n gt h es a l e ，s u c ha st h ed a t ao ft h et r a n s a c t i o n ，t h ec u s t o m e r i dn u m b e r ，t h ei dn u m b e ro ft h es a l e sp e r s o n ，a n do ft h eb r a n c ha tw h i c ht h es a l e o c c u r r e da n ds oo n t a b l e1 1s h o w sa ne x a m p l eo ft r a n s a c t i o n a ld a t a b a s ef o ra s u p e r m a r k e t c h a p t e r1 i n t r o d u c t i o n t a b l el h f r a g m e n tofatransactionald a t a b a s ef o ras u p e r m a r k e t t i di t e m sb o u g h t 0 1 0 2 z 1 ) 2 4 】z 7 2 2 ，2 5 1 4t h ep a t t e r n st h a tc a nb em i n e d t h ek n o w l e d g em i n e di nd a t am i n i n gc a nb ec l a s s i f i e di n t os e v e r a lp a t t e r n s d i f f e r e n t p a t t e r n sa r es u i t a b l ef o rd i f f e r e n ts i t u a t i o n s f i v et y p i c a lp a t t e r n sa r es h o w nb e l o w 1 4 1a s s o c i a t i o nr u l e s a s s o c i a t i o na n a l y s i si st h ep r o c e s so fd i s c o v e r i n gi m p l i c i ta n di n t e r e s t i n ga s s o c i a t i o n s a m o n gi t m e si nad a t a b a s e a s s o c i a t i o na n a l y s i si sw i d e l yu s e df o rn l a lk e tb a s k e t a n do t h e rt r a n s a c t i o nd a t aa n a l y s i s i ta n a l y z e sc u s t o m e r s b u y i n gh a b i t sb yf i n d i n g a s s o c i a t i o n sa m o n gd i f f e r e n ti t e m st h a tc u s t o m e r sp l a c ei nt h e i r “s h o p p i n gb a s k e t s ” at y p i c a le x a m p l ei s “b e e r _ d i a p e r ”w h o s ei n t u i t i v em e a n i n gi st h a tp e o p l ew h o b u yb e e ra l w a y sb u yd i a p e r 1 4 2c l a s s i f i c a t i o na n dp r e d i c t i o n c l a s s i f i c a t i o ni st h ep l o c e s 8o ff i n d i n gas e to fm o d e l s ( o rf u n c t i o n s ) w h i c hd e s c r i b e a n dd i s t i n g u i s hd a t ac l a s s e so rc o n c e p t s ，f o rt h ep u r p o s eo fb e i n ga b t et ou s et h e m o d e lt op r e d i c tt h ec l a s so fo b1 e c t sw h o s ec l a s s1 a b e lj su n k n o w n i nm a n ya p p l i c a t i o n s o n em a yl i k et op r e d i c ts o m em i s s i n go ru n a v a i l a b l ed a t a v a l u e sr a t h e rt h a ac l a s sl a b e l s ，t h i si su s u a l l yt h ec a s ew h e nt h ep r e d i c t e dv a l u e sa r e n u m e r i c a l a n di so f t e ns p e c i f i c a l l yr e f e r r e dt oa 8p r e d i c t i o n ，a l t h o u g hp r e d i c t i o nm a y r e f e rt ob o t hd a t av a l u ep r e d i c t i o na n dc l a s sl a b e lp r e d i c t i o n i ti su s u a l l yc o n f i n e d t od a t av a l u ep r e d i c t i o na n dt h u si sd i s t i n c tf r o mc l a s s i f i c a t i o n 1 4 3 c l u s t e r i n ga n a l y s i s c l u s t e r i n gi st h ep r o c e s so fg r o u p i n gas e to fp h y s i c mo ra b s t r a c to b j e c t si n t oc l a s s e s o fs i m i l a ro b l e c t s ac l u s t e ri sac o l l e c t i o no fd a t ao b e c t 8t h a ta r es b n i l a it oo n e a n o t h e rw i t h i nt h es a m ec l u s t e ra n dd i s s i m i l a rt ot h eo b i e c t si no t h e rc l u s t e r sa c l u s t e ro fd a t ao b j e c t sc a nb et r e a t e dc o l l e c t i v e l ya so n eg r o u pi nm a n ya p p l i c a t i o n s c l u s t e ra n a l y s i sh a sb e e nw i d e l yu s e di nm a n ya p p l i c a t i o n s i nb u s i n e s s ，c l u s t e r i n g m a yh e l pm a r k e t e r sd i s c o v e rd i s t i n c tg r o u p si nt h e i rc u s t o m e rb a s e sa n dc h a r a c t e r i z e c u s t o m e rg r o u p sb a s e do np u r c h a s i n gp a t t e r n s c h a p t e r1 i n t r o d u c t i o n t a b l e 1 , 2 ：t r a n s a c t i o n a l d a t a b a s e f o r c o m p u t e r i t e m s 一 t i d i t e m sb o u g h t 一一 叭i b mh o m ec o m p u t e r ，s o n yb wp r m t e r 0 2 m i c r o s o f te d u c a t i o n a ls o f t w a r e ，h pc o l o rp r i n t e r 0 3 l b ml a p t o pc o m p u t e r ，e p s o nc o l o rp r i n t e i 1 4 4o u t l i e ra n a l y s i s 6 o u t l i e r sa r et h o s ed a t ao b j e c t sw h i c ha r ed i f f e r e n tf r o mg e n e r a ld a t ao nb e h a v i o ra n d m o d e l s a l t h o u g ho u t l i e r sa r ed i s c a r d e da sn o i s e so ra b n o r m i t yi nm o s ta p p l i c a t i o n s ， i ns o m ea p p l i c a t i o n s ( s u c ha sc h e a td e t e c t i n g ) ，p e c u l i a rt h i n g sa r em o r ei n t e r e s t i n g t h e ng e n e r a lo n e s o u t l i e ra n a l y s i si si n t e n d e df o rf i n d i n gt h ea b n o r m a la l l ( tp c ( ；u l i a i 1 4 5e v o l u t i o na n a l y s i s d a t ae v o l u t i o l la n a l y s i sd e s c r i b e sa n dm o d e l sr e g u l a r i t i e so rt r e n d sf o ro b j e c t sw h o s e b e h a v i o rc h a n g e so v e rt i m e i ti n c l u d e st i m e s e r i o u sd a t aa n a l y s i s ，s e q u e n c eo i 、p e r i o d i c i t yp a t t e i nm a t c h i n g a n ds i m i l a r i t y b s s e dd a t aa n a l 3 s i s 1 5c l a s s i n c a t i o no fa s s o c i a t i o nr u l e s a s s o c l a t i o nr u l e sc a nb ec l a s s i f i e di n t os e v e r a lt y p e sb a s e do nd i f f e r e n tc r i t e r i a t h e c l a s s i f i c a t i o nw i l lb ei l l u s t r a t e db ya ne x a m p l ea sf o l l o w s e x a m p l e1 5 1 w ef o c u so ns a l e sa tac o m p u t e rd e p a r t m e n to f a ns u p c r r n a t 齿e t t h e m n s o c t i o n a 2d a t a b a s ei nt a b l ej2s h o w st h ei t e m sp u r c h a s e d1 0 re a c ht r a n s a c t i o n t i d a d d i t i 。礼。ft a b l e sf o rt h ec u s t o m e r s i n f o r m a t i o n ，w h i c hi sa s s o c i a t e dw i t ht h e t r w a s a c t z o n a ld a t a b a s e ，a r eo m i t t e d t h ec o n c e p th i e r a r c h yf o rt h ei t e m si ss h o w ni n f i gi 。0d i f f e r e n tt y p e so fa s s o c i a t i o nr u l e sc a nb eg e n e r a t e df r o mt h ed a t a b a s ed b o o l e a nv s q u a n t i t a t i v e ：b a s e do nt h et y p e so fv a l u e sh a n d l e di n t h e n l l e s 、a s s o c i a t i o n sc a r lb ec l a s s i f i e di n t ob o o l e a na n dq u a n t i t a t i v eab o o l e a n a s s o c i a t i o ns h o w sr e l a t i o n s h i p sb e t w e e nd i s c r e t e ( c a t e g o r i c a l ) o b j e c t s ，s u c ha s b w s ( x ，c o m p u t e r ) 一b u y s ( x ，s o f t w a r e ) aq u a n t i t a t i v ea s s o c i a t i o ni s a na s s o c