（计算机软件与理论专业论文）基于时序和极大团的关联规则数据挖掘方法的研究.pdf

独创性声明 97 4 4 2 7 本人声明所呈交的学位论文是我个人在导师指导下进 行的研究工作及取得的研究成果。尽我所知，除文中已经标 明引用的内容外，本论文不包含任何其它个人或集体已经发 表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：l 了 厶一古年占月o 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文 的规定，即：学校有权保留并向国家有关部门或机构送交论 文的复印件和电子版，允许论文被查阅和借阅。本人授权云 南师范大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文。 学位论文作者签名：翌雪 山年f 月，o 日 指导教师签名：7 夏砂蚋 枷6 年占月。日 摘要 关联规则挖掘是数据挖掘中最活跃的研究方法之一。最早是由a g r a w a l 等人提出的( 1 9 9 3 年) 。 最初提出的动机是针对购物篮分析( b a s k e la n a l y s i s ) 问题提出的其目的是为了发现交易数据库 ( t r a n s a c t i o nd a t a b a s e ) 中不同商品之间的联系茬则。交易数据库可以把顾客的相关交易( 如所购 物品项目等) 存储f 来。通过对这些数据的智能分析，可以获得有天颐客购买模式的一般性规则。 这些规则刻画了顾客的购买行为模式，可以用来指导商家科学地安排进货、库存以及货架设计等。 一关联规则在其它领域也可以得到广泛讨论，如目录设计商品广告邮寄分析、追加销售、仓库规划、 网络故障分析、市场规则，广告策划、分类设计等关联知识( a s s o c i a t i o n ) 反映一个事件和其它 ， 。 事件之间的依赖或关联，关联可分为简单笑联、对序( t i m es e r i e s ) 笑联，因果关联、数量天联等 这些关联并不总是事先知道的，而是通过数据库申数据的关联分析得到的，因而对商业决策具有新 价值。 大多数算法得到的关联规则事实上假殴其是永远有效的，但是时间是现实世界的重要属性大 电 容量数据集中的时间属性对用户来说可能是很关键的。用户关心的往往是某一时间区域的数据而不 是整个数据，而特定时间区域的数据又可能导致特定的数据间的关联规则解决这一问题的方法就 是在算法中考虑时间因素，囡此，数据库中表的字段要至少包括事务号、时态区间和项目序列三个 字段。这里的时态区间反映了对应的项目序列发生或被收集的时间范围。关联规则的挖掘可以利用 时态约束来进行预处理等工作，可以过滤掉用户不关心的时段上的数据。过滤数据库以减少扫描空 间、降低输入输出代价、减少内存需求进而提高挖掘效率的关键。如果数据库中的每个元组均有其 时态约束的规则，那么就可以更好的描述客观情况，因而更有价值。 目前，大部分的工作都集中在时间并u ，的范胃内进行考虑的，显然和时间并u ，相关的所有事 务中的所有项目在时间并u ，中都是必然发生的但在时间交n ，中却不一定，换言之，在时间并u f 中，如果事务中某些项目的组合构成了频繁项目集，但在时间交n ，中至少包含该频繁项目集的概 率和p 却不同根据专家知识给此概率和一个阈值口。，当p = 口。时，其p 所在的时间交n r 就称 j 为黄金时间段假设把黄金时间段的思想应用型超市的话，那么在时间交n ，这些黄金时间段内， i商家应根据不同的黄金时间段内出现的极大的频繁商品的不同而有的放矢的更准确的准备充足的货 f 源，以供顾客购买很显然，对于黄金时间段的研究也是一个很有意义的课题。 由于计算机在处理海量的数据项的过程中，梅是对内存的极大考验，而通过已经学过的极人团 的特点，将关联性最强、项目之间最容易产生极大有序频繁项目集的项生成一个极大团，这样就可 以把原来海量的数据项进行了有效的划分，缓解了内存不足的问题。 本研究是将时序逻辑、极丈团和数据挖掘的知识有效的结合在一起，针对上述问题提出了9 个 算法，并给出了算法复杂度的分析。主要成果与创新：在时间并u ，内求极大有序频繁项目集； 求至少包含出现在时间并u ，内的那些极人有亭频繁项目集同时发生相戍的时问交n ，的概率 和p ；如果处理的事务中所涉及的项过多，对内存形成极大考验的时候，则如何利用极大团来解 决的问题；在时f y f u ，内的关联规则等问题。并针对等概率和不等概率的情况分别提出了该概 率的数学模氆，且给予证明为解决问题，在论文中给出的定义、定理和推论如下：对定义2 2 ( 时间区间变量操作) 毛国君等，2 0 0 5 进行补充，给出了定义2 2 a 一2 2 9 ：定义2 3 ( 基于时序 的事务模式m 的定义) ；定义2 4 ( 基丁时序的事务模式m 的频繁项目集) ；定义2 5 ( 墓f 时 序的事务模式m 的极大频繁项目集) ；定义2 6 ( 黄金时间段) 。定理4 3 ( 在等概率的情况下， 两个事务概率的数学模型) ；定理4 4 ( 在等概率的情况下，r ( r 2 ) 个事务概率的数学模型) ； 定理4 5 ( 在不等概率的情况下，该概率的数学模型) ；推论4 i 一4 4 ( 在等概率的情况下，不 同情况的概率数学模型) 关键词：数据挖掘关联规则时序逻辑 极大团 黄金时间段概率 、 i a b s t r a c t t h ea s s o c i a t i o nr u l em i n i n gi so n eo ft h em o s ta c t i v er e s e a r c ht e c h n i q u e si nt h ed a t am i n i n g i tw a sm o s te a r l yp r o p o s e db ya g r a w a i ( i n1 9 9 3 ) a tf i r s t , t h ep r o p o s e dm o t i v ea i m sa tt h e q u e s t i o no fs h o p p i n gb a s k e ta n a l y s i s ( b a s k e ta n a l y s i s ) ，a n di t sg o a li st od i s c o v e rt h ed i f f e r e n t c o m m o d i t yr e l a t i o n r u l eb e t w e e nt h et r a n s a c t i o n d a t a b a s e ( t r a n s a c t i o nd a t a b a s e ) t h e t r a n s a c t i o nd a t a b a s em a ys a v ec u s t o m e r sr e l a t e dt r a n s a c t i o n s ( f o re x a m p l es h o p p i n gp r o j e c ta n d s oo n ) b yt h e s ed a t ai n t e l l i g e n ta n a l y s e s ，w em a yo b t a i nt h eg e n e r a lr u l ec o n c e r n e dc u s t o m e rt o p u r c h a s et h ep a h e r u t h e s er u l e sh a v ep o r t r a y e dc u s t o m e r sp u r c h a s eb e h a v i o rp a t t e r n ，w em a y u s et h e mt oi n s t r u c tt h em e r c h a n ts c i e n t i f i c a l l yt oa r r a n g et oi m p o r tg o o d s ，t h es t o c ka sw e l la s g o o d sd e s i g na n ds oo n t h ea s s o c i a t i o nr o l ea l s om a y o b t a i nt h ew i d e s p r e a dd i s c u s s i o ni no t h e r d o m a i n s ，l i k et h et a b l eo fc o n t e n t sd e s i g n ，t h ec o m m o d i t ya d v e r t i s e m e n tm a i l st h ea n a l y s i s ， s u p p l e m e n t ss a l e s ，t h ew a r e h o u s ep l a n , t h en e t w o r kf a u l ta n a l y s i s ，t h em a r k e tr u l e , t h e a d v e r t i s e m e n tp l a n s ，t h ec l a s s i f i e dd e s i g na n ds oo n t h ea s s o c i a t i o nk n o w l e d g e ( a s s o c i a t i o n ) r e f l e c t st h ed e p e n d e n c eo rt h ea s s o c i a t i o nb e t w e e na ne v e n ta n dt h eo t h e re v e n t , t h ea s s o c i a t i o n m a y d i v i d ei n t ot h es i m p l ea s s o c i a t i o n ，t h et i m es e r i e s ( t 1 ：m es e r i e s ) a s s o c i a t i o n , t h ec a u s e sa n d e f f e c t sa s s o c i a t i o n , t h eq u a n t i t ya s s o c i a t i o na n ds oo n t h e s ea s s o c i a t i o n sa r en o ta l w a y sk n e w b e f o r e h a n d ，b u tt h e ya r et h ed a t aa s s o c i a t i o na n a l y s i so b t a i n st h r o u g ht h ed a t a b a s e ，t h u st h e y h a v et h en e wv a l u et ot l l eb u s i n e s sd e c i s i o n i nf a c t , w es u p p o s et h ea s s o c i a t i o nr u l e so b t a i n e db yt h em a j o r i t ya l g o r i t h ma r ee f f e c t i v e f o r e v e r , b u tt h et i m ei st h ei m p o r t a n ta t t r i b u t ei nt h er e a lw o r l d , t i m ea t t r i b u t eo ft h el a r g e c a p a c i t yd a t as e t si sp o s s i b l yv e r ye s s e n t i a lf o rt h eu s e r s ，w h a tt h eu s e r sc a r eo f t e ni st h es o m e r e g i o nd a t ab u tn o tt h ee n t k ed a t af o raw h i l e ，b u tt h ed a t ai nt h es p e c i f i ct i m er e g i o np o s s i b l y c a u s e st h ea s s o c i a t i o nr u l ed u r i n gt h es p e c i f i cd a t a t h em e t h o do fs o l v i n gt h i sq u e s t i o ni st h e c o n s i d e r a t i o nt i m ef a c t o ri nt h ea l g o r i t h m ，t h e r e f o r et h et a b l em u s ti n c l u d et h r e ef i e l d sa tl e a s t m t r a n s a c t i o nn u m b e r , t h et e n s es e c t o ra n dt h ei t e m si nt h ed a t a b a s e t h et e n s es e c t o rh e r eh a s r e f l e c t e dt h ec o r r e s p o n d i n gi t e ms e q u e n c ew h i c ho c c u r so rt h et i m es c o p ew h i c hi sc o l l e c t e d t h e a s s o c i a t i o nr u l em i n i n gm a yb ep r e t r e a t m e n tu s i n gt h et e n s er e s t r a i na n ds oo na n df i l t e rt h et i m e i n t e r v a ld a t at h a ti sn o tc o n c e r n e db yt h eu s e r s f i l t e r i n gt h ed a t a b a s ei st or e d u c et h es c a n n i n g s p a c e ，t or e d u c et h ei n p u ta n do u t p u tp r i c e , t h er e d u c e dm e m o r yd e m a n d , t h e ne n h a n c e st h ek e y i i i o fm i n i n ge f f i c i e n c y i fe a c ht u p l ei nd a t a b a s eh a si t sr u l eo ft h et i m er e s t r a i n tc o n d i t i o n ，i tc a n b e u e rd e s c r i b eo b j e c t i v es i t u a t i o n ，t h u si th a st h ev a l u e a tp r e s e n t ，t h em a j o r i t yo fw o r ka l lc o n c e n t r a t ei nt i m eu n i o nu ri nt h es c o p ec a r r i e so nt h e c o n s i d e r a t i o n ，o b v i o u s l ya l li t e m so fa l lt r a n s a c t i o n si nc o r r e l a t i o nw i t ht i m eu n i o nu ，o c c u r i n e v i t a b l y , b u ta r ea c t u a l l yu n c e r t a i ni nt i m ej u n c t i o n ik i no t h e rw o r d s ，i nt i m eu n i o n o r ，i f s o m ei t e m sc o m b i n a t i o n sc o n s t i t u t e dt h ef r e q u e n ti t e ms e t si nt r a n s a c t i o n s ，b u tt h ep r o b a b i l i t yp ： i sa c t u a l l yd i f f e r e n ti nt i m ej u n c t i o n fk a c c o r d i n gt o e x p e r tk n o w l e d g e , l e tt h ep r o b a b i l i t y t h r e s h o l dv a l u eb eo 一，w h e np = 口班，t i m ej u n c t i o nr l ra b o u tpi sc a l l e dt h eg o l d e n - t i m e i f w el e tt h et h o u g h to ft h eg o l d e n - t i m ea p p l yt ot h es u p e r m a r k e t , t h e nd u r i n gt h eg o l d e n - t i m e ，t h e m e r c h a n ts h o u l d p r e p a r e s u f f i c i e n td i f f e r e n ts o u r c eo f g o o d sa c c o r d i n g t ot h ed i f f e r e n t g o l d e n - t i m e o b v i o u s l y , t h er e s e a r c ho ft h eg o l d e n - t i m ei sav e r ym u c hs i g n i f i c a n c et o p i c w h e nt h ec o m p u t e rp r o c e s st h em a g n a n i m o u sd a t ai t e m s ，i tw i l lb ca ne n o r m o u st e s t t o m e m o r y , b u tw em a y u s et h em a x i m u mc l i q u e sc h a r a c t e r i s t i ct h a tw eh a v ea l r e a d ys t u d i e da n d p r o d u c eam a x i m u mc l i q u eb yt h ei t e m st h a ta r e t h es t r o n g e s tr e l a t e d n e s sa n dt h em o s te a s i e s t p r o d u c e dt h em a x i m u ma n df r e q u e n ti t e ms e t si nt h ei t e m s ，t h e nw ec a nd i v i d ee f f e c t i v e l yt h e o r i g i n a lm a g n a n i m o u sd a t ai t e m sa n da l l e v i a t et h eq u e s t i o nw h i c ht h em e m o r yw a si n s u f f i c i e n t t h i sr e s e a r c hi st oe f f e c t i v e l yu n i f yt h et i m es e r i e sl o g i c , t h em a x i m u mc l i q u ea n dt h ed a t a m i m n gk n o w l e d g ei nt o g e t h e r p r o p o s e9a l g o r i t h m sa n dg e tt h ea n a l y s i so fa l g o r i t h mc o m p l e x i t y m a i na c h i e v e m e n ta n di n n o v a t i o n ：( 1 ) g e tt h em a x i m u ma n df r e q u e n ti t e ms e t si nt i m ej u n c t i o n f0 ；( 2 ) g e tt h ep r o b a b i l i t ypa b o u tt h ei t e m st h a tc o n s i s to ft h em a x i m u ma n df r e q u e n ti t e ms e t s i nt i m eu n i o nu ra n da r ei n c l u d e di nt i m ej u n c t i o nika tl e a s t ；( 3 ) i ft h ei t e m so ft r a n s a c t i o n s a r et o om u c ha n df o r me n o r m o u s l yt e s tt ot h em e m o r y , t h e nh o wt os o l v et h eq u e s t i o nu s i n gt h e m a x i m u mc l i q u e ；( 4 ) s o l v et h eq u e s t i o no fa s s o c i a t i o nr u l e p r o p o s et h ep r o b a h i f i t ym a t h e m a t i c a l m o d e la c c o r d i n gt ot h ee q u a lp r o b a b i l i t ya n dt h eu n e q u a lp r o b a b i l i t ys i t u a t i o na n dg i v et h ep r o o f s i no r d e rt os o l v et h ep r o b l e m ，w ep r o d u c et h ed e f i n i t i o n s , t h et h e o r e m sa n dt h ed e d u c t i o n si nt h e 。p a p e r a sf o l l o w s ：( 1 ) t os u p p l ed e f i n i t i o n2 2 ( t i m es e 虻t o rv a r i a b l eo p e r a t i o n ) 【m a og u o j u n ， 2 0 0 5 】a n dp r o d u c ed e f i n i t i o n2 2 a - 2 2 9 ；( 2 ) t od e f i n e2 3 ( b a s e do nt h ed e f i n i t i o no ft h et i m e s e r i e st r a n s e c t i o np a u e r nm ) ；( 3 ) t od e f i n e2 4 ( b a s e do nt h ef r e q u e n ti t e ms e t so ft h et i m es e r i e s t r a n s a c t i o np a t t e r nm ) ；( 4 ) t od e f i n e2 5 ( b a s e do nt h em a x i m u m f r e q u e n ti t e ms e t so ft h et i m e s e r i e su a n s a c t i o np a h e r nv o ；( 5 ) t od e f i n e2 6 ( t h eg o l d e n t i m e ) ；( 6 ) t h e o r e m4 3 ( 2t r a n s a c t i o n s w i t ht h ep r o b a b i l i t ym a t h e m a t i c a lm o d e li ne q u a lp r o b a b i l i t ys i t u a t i o n ) ；( 7 ) t h e o r e m4 4 ( r ( r 2 ) t r a n s a c t i o n sw i t ht h ep r o b a b i l i t ym a t h e m a t i c a lm o d e li ne q u a lp r o b a b i l i t ys i t u a t i o n ) ；( 8 ) t h e o r e m 4 5 ( rp - - 2 ) t r a n s a c t i o n sw i t ht h ep r o b a b i l i t ym a t h e m a t i c a lm o d e li nu n e q u a lp r o b a b i l i t y s i t u a t i o n ) ；( 9 ) d e d u c t i o n s4 1 - 4 4 ( d i f f e r e n ts i t u a t i o n sp r o b a b i l i t ym a t h e m a t i c a lm o d e li ne q u a l p r o b a b i l i t ys i t u a t i o n ) k e yw o r d s ：d a t am i n i n g g o l d e n 4 i m e a s s o c i a t i o nr o l et i m es e r i e sl o g i c m a x i m u mc l i q u e p r o b a b i l i t y ， 一 一一一 一一 v 第一幸慨述 第一章概述 1 1k d d 的简介 自2 0 世纪6 0 年代以来数据库和信息技术已经系统地从原始的文件处理演化刘复杂的功能强 大的数据库系统自7 0 年代以来，数据库系统的研究和开发已经从层次和网状数据库系统发展到开 发关系数据库系统，数据建模工具、索引和数据组织技术。自8 0 年代开始数据库技术得到了广泛 的普及和应用。随着数据库容鼍的膨胀，特别是数据仓库以及w e b 等新犁数据源的日益普及，人们 面临的主要问题是“数据丰富，但信息贫乏”，即面对浩瀚的数据海洋，却不翱该如何有效的利用这 些数据。面对这一问题的挑战，数据挖掘和知识发现技术应运而生，并显示出强大的生命力 谈到数据挖掘，就应该先介绍一下另一个名词数据库中的知识发现( 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 ) j a w e ih a n ，2 0 0 4 ，1 9 8 9 年8 月在美国底特律召开的第十一屠国际人工智能联合会 议的专题讨论会上首次出现k d d 这个术语随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行了k d d 专 题讨论会。汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、海晕数据分折算法 知识表示、知识运用等问题。从1 9 9 5 年开始k d d 国际会议发展成为年会1 9 9 8 年在美国纽约举 行的第四届知识发现与数据挖掘国际学术会议不仅进行了学术讨论，并且有3 0 多家软件公司展示了 他们的数据挖掘软件产品1 9 9 9 年在美国圣地亚哥举行的第五届k d d 国际学术大会，参加人数近 千人此外，i e e e , a c m ，i f i s ，v l d b ，s i g m o d 等其它学会，学刊也纷纷把数据挖掘知识发现列为会 议议题或出版专刊，成为当前国际上的一个研究热点 1 2 关联知识挖掘 关联知识( a s s o c i a t i o n ) 反映一个事件和其它事件之间的依赖或关联，关联可分为简单关联、 时序( t i m es e r i e s ) 关联、因果关联、数量关联等这些关联并不总是事先知道的，而是通过数据 库中数据的关联分析得到的，因而对商业决策具有新价值。 关联规则挖掘是数据挖掘中最活跃的研究方法之一。最早是由a g r a w a l 等人提出的( 1 9 9 3 年) a g r a w a lr 1 9 9 3 1 。最初提出的动机是针对购物篮分析( b a s k e ta n a l y s i s ) 问题提出的。其目的是为 了发现交易数据库( t r a n s a c t i o nd a t a b a s e ) 中不同商品之间的联系规则交易数据库可以把颐客的 相关交易( 如所购物品项目等) 存储下来通过对这些数据的智能分析，可以获得有关顾客购买模 式的一般性规则这些规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货、库存以 及货架设计等。关联规则在其它领域也可以得到厂泛讨论，如目录漫计、商品广告邮寄分析、追加 销售、仓库规划、网络故障分析、市场规则，广考策划、分类没计等。 南师范夫学颂i 研究生学位论立堆f 时卑和撒人团的关联规则数据挖掘方法的研究 1 2 1 基本概念和问题描述 定义1 i j a w e ih a n ，2 0 0 4 】设i - i 1 ，b ，i 。 是项的集合。设任务相天的数据d 是数据库事务的集合， 其中每个事务t 是项的集合，使得t i 每一个事务有一个标识符，称作t i d 设a 是一个项集。 事务t 包含a 当且仅当a t 定义1 2 j a w e i h a n ，2 0 0 4 关联规则形如a = b 的蕴涵式，其中a c i ，b c i ，并且a a b = o 规则a = b 在事务集d 中成立，具有支持度s ，其中s 是d 中事务包含a u b ( 即a 和b 二者) 的百分比，它是概率 p ( a u b ) 规则a = y b 在事务集d 中具有置信度c ，如果d 中包含a 的事务同时也包含b 的百分比是 ， c 这是条件概率p ( bj a ) ，即是 s u p p o r t ( a - - b ) ：p ( t u b ) = ia o b i i d l 。 c o n f i d e n c e ( a - b ) = p ( b i a ) = la u b i i a i 其中fa u b f 是包含项集 u b 的事务数，i a i 是包含项目集a 的事务数，f d i 是包含数据库中的所有 事务数 定义i 3 j a w e it h n ，2 0 0 4 同时满足最小支持度阈值( m i n - s u p ) 和最小置信度阚值( m i n - c o n f ) 的规则称作强关联规则，否则称为弱关联规则 定义i 4 j a w e ih a n ，2 0 0 4 】项的集合称为项集( i t e m s e t ) ，包括k 个项的项集称为k 一项集。如集 合 c o m p u t e r , s o f t w a r e ) 是一个2 一项集。如果项集满足最小支持度，则称它是频繁项集( f r e q u e n t i t e m s e t ) 频繁k 一项集的集合通常记l k 一 定义l5 j a w e ih a r t ，2 0 0 4 在频繁项目集中挑选出所有不被其它元素包含的频繁项目集称为最人 频禁项目集。( m a x i m u mf r e q u e n ti t e m s e t s ) 1 2 2 关联规则挖掘的一般过程 1 )找出所有频繁项集，也就是支持度丈丁：等于给定最小支持度的项集； 2 )由频繁项目集产生强关联规则：根据定义，这些规则必须满足晟小支持度和最小置信度。 这两步中。对于第二步而言，也许在每个极大频繁项目集中逐一匹配规则并进行c o n f i d e n c e 0 1 = 1 2 ) = m i n c o n f i d e n c e 的测试是必需的，因此，这部分工作是相对比较成熟的子问题而第一步是 近年来关联规目挖掘算法研究的重点 毛国君等，2 0 0 5 】许多算法已经被提出，在综述中将对作者 已阅读过的相关算法进行阐述千宁。2 0 0 + 。 1 2 3 关联规则的技术标准 关联规则是数据挖掘中一个很重要的研究领域。自1 9 9 3 年a g r a w a l 提出此概念后，已出现了 许多有放的挖嵇l | 算法这訾算法大都集中如何提高算法的效率，而对挖掘出来的规则是否有用或 2 奢；一审溉述 者说用户是否感兴趣却研究的不多。最初的算法中求天联规则。人部分都以满足最小支持熏同时义 要满足最小置信度为标准来求关联规则的，但是往往会有虚假的天联规则在里面。 目前有很多的新算法对最初的支持度一置信度框架提出不足，并有所改进，基本都是义加入新 的约束条件，以降低虚假信息的产生从技术角度引进几条选择关联规m 9 的标准，即支持度( s u p p o r l , 也称广泛度，普遍度) 、置信度( c o n f i d e n c e ，也称为预测度，) 、增益度( 1 i f t ，也称兴趣度) 、坚信度 ( c o n v i c t i o n ) j o c h e nt t i p p ，2 0 0 2 。 - 3 - 商岬托大学硕仁研究生学位论文 犟于时字和极大圈的关联艇9 1 【f 数据挖掘方法的研究 第二章时序逻辑及其模式 约束的关联规则挖掘是将来研究的主要问题但是，由于涉及的范围很广，目前的研究和时间 丈多集中在某种形态的约束或特定的问题上。大多数算法得到的关联规则事实上假漫其永远有效的， 但是时间是现实世界的重要属性丈容苗数据集中的时间属性对用户来说可能是很荚键的用户关 心的往往是菜一时间区域的数据而不是整个数据，而特定时间区域的数据又可能导致特定的数据间 的关联规则解决这一问题的方法就是在算法中考虑时间因素，因此，数据库中表的字段要包括事 务号、时煮沤闻和项目序列三个字段这里的时态区间反映丁对应的项目序列发生或被收集的时问 范围。关联规则的挖掘可以利用时态约束来进行预处理等工作，可以过滤掉用户不关心的时段上的 数据过滤数据库以减少扫描空间、降低输入输出代价，减少内存需求进而提高挖掘效率的关键 如果数据库中的每个元组均有其时态约束的规则，那么就可以更好的描述客观情况，因而更有价值 所考虑的时态语义是所谓的有效时间，即在某段时间内，某元组是有效的或合法的为此在关 联模式中增加了一个有效时间属性t i m e ，规定每个元组都必须首先判断附加该有效时间属性于是， 当判断某元组是否支持某属性时。由于属性是附加有效时间约束的，所以，必须首先判断该元组的 有效时间是否与属性的有效时间匹配，只有两者是匹配的，才能进一步考虑是否支持的问题也就 是说须将某元组是否支持某属性的问题分解成两个步骤解决：第一步，元组的有效时间与属性的 有效时间是否匹配；第二步。若匹配的情况下，可以把元组考虑成朱附加有效时间的普通元组进行 判断，看是否支持该属性 2 1 数据库的预处理 因为所研究的数据库中的事务是有三个属性即t i d 、i t e m ，t i m e 。其中t i d 为事务标识号，全局 唯一：i t e m 是一个项集f i ，i 。，i n ，其中i 属丁= 项集中的元素；t i m e 为 i 一，i + ) 是相应的有效 时间因此，为了提高算法的效率，本文在数据库预处理的过程中主要工作有：、所有的事务都 是以时间的起始时间i 一的递增进行排序；二二、如果i 一相同，则以i + 的递增进行排序；三、如果i 一、i + 都相同，则以事务标识号递增排序；四、每条事务的项都是递增排序因此，在本论文中， 统称为有序项目集。 2 2 基本概念和描述 定义2 1 ( 时态区间格) 毛国君等，2 0 0 5 一个时态耳闻格空间可以用三元组t ：( t i ，t d ，t 0 ) 来刻 画，其中含义如f ： 时态耳间变颦集t i ：一个时态区间变晕形如，- 【，。，+ 】其中。+ ，和，f + ( i 4 第二章时序逻辑歧儿模式 = i ，2 ，。n ) 是定义在t d 上的时间点变量； 时态解释域t d ：所涉时态区间变域对应的时间点定义范围， 即 v ，j 【l i ，i i + 】e t i ，。，t + t d ，e t d x t d ； 变量问操作集t o ：定义在t d 上的关于时态区问变量的操作集。 其中时态区间有两个基本操作；时态交和时态并 定义2 2 ( 时闻区间变量操作) 【毛国君等，2 0 0 5 设，l - 【i l - , ，l + 】和，2i p 2 - , 1 2 + 】是定义在某个 时态解释域上的两个时态区间变量，它们的时态交( n ，) 、时态并( u ，) 运算定义如f ： 时态交( n t ) ：如果f l + 1 2 - 或j 2 + 1 1 。，则j l n r1 2 - 妒i 否则j l n f1 2 一p ，f ，+ 】， 其中1 3 4 - 脚 ，l 。，2 ，1 3 + - m i n i , + ，2 + ) 时态井( u r ) ：如果，i + ，2 或j 2 + i i ，则，1 u r1 2 - 妒；否则，lu r1 2 - 【1 3 ，+ 】， 其中1 3 im i n i , - , 1 2 - ，l + 一脚“+ ，j r 2 + 两个时间区间和，2 的所有情况的定义如下： 定义2 2 a 定义2 2 b 若，l + i z 或，2 + ，l 。，则l u f ，2i 爹，1 1 n r ，2 - 驴； 若1 1 + i ，2 一或，2 + - ，l 。，则1 1 u r ，2 - 【l 一，1 3 + 】，其中 1 3 。i m i n i , - , 1 2 - ，l + - 朋般p l + ，j 2 + ) n r ，2i 【l ，1 3 + 】t 即是一个点，则 l - 1 3 + i + - 1 2 - 或j ，3 + 一，2 + - ，i 一； 定义2 2 c 【：2 ：a 若。，：。+ 。，：+ 或，：。，。，：+ 。 + ，。 l u fl - i f , 1 3 + 】，其中j ，一朋z j l ，2 。) ，1 3 + 一 阴z ，l + ，2 + ，。n r ，2 - 【，3 ，厶+ 】， 、 其中l 。一m a x i , - , j r 2 。) ，j 3 + - 朋z p l + ，j 2 + ) ； “ 定义2 2 d 若，l 。i ，2 。+ - ，2 + ，则u f ，2 - 【，3 一，3 + 1 。其中 1 3 。i 一，2 ，3 + 。，l + - ，2 + j l n fj 2 - 【，3 。，j ，+ 】，其中j 3 。一，l 。一，2 ，l + - l + 一j 2 + ； 定义2 2 e ：；! j ! ! ：j 丑若，。，：。，：+ 。，l + 或，：。，。一。，。，：+ ，则 ，。u r ，2 - i f , ，3 + 1 ，其中，3 。- m i n i , - , j 2 。 ，+ 翻 ，l + ，j 2 + ) ；，。n ，2 一【，3 ，l + 】， 5 厶南帅范人学颀f 研究生学位论史堆十时宁柙栈人圈的关联觇则数据 毫撺疗沾的研，兜 其中，3 一- m a x i ( , ，2 一 ，+ - m i n i i * , ，：+ ； 定义2 2 f ( ：! ! ! ! ! ! ! ! ! ! a 若1 i - 1 2 - - l 。l ，卜l ，则循环执行步骤h f 6 一m