《时间戳数据库上的时态关联规则挖掘》由会员分享，可在线阅读，更多相关《时间戳数据库上的时态关联规则挖掘（3页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 2 V 0 1 2 9 N 0 - 8 ( 增刊)时间戳数据库上的时态关联规则挖掘D i s c o v e r i n gT e m p o r a lA s s o c i a t i o nR u l e sO nT i m e s t a m pD a t a b a s e任家东任东英高伟 ( 燕山大学计算机科学与工程系秦皇岛0 6 6 0 0 4 )A b s t r a c tT e m p o r a lc h a r a c t e ri sa ni m p o r t a n ta s p e c to ft r a n s a c t i o n s
2、 ，b u tp e o p l ei g n o r ei td u r i n g m i n i n ga s s o c i a t i o nr u l e sb e f o r e I nt h i sp a p e rw ep r o p o s e dt h ed i s c o v e r i n gt e m p o r a la s s o c i a t i o nr u l e sp r o b l e ma n dt h ec o r r e s p o n d i n gs o l u t i o n T h ep r o b l e mo fd i s c o
3、v e r i n gt e m p o r a la s s o c i a t i o nr u l e sc a nb ed i v i d e di n t o3s u b p r o b l e m ：p a r t i t i o n i n g ，d i s c o v e r i n g ，e x p r e s s i n g I nt h i sp a p e rw ep r o p o s e dh o wt op a r t i t i o nt h ed a t a b a s ew i t hc l u s t e r i n gm e t h o d ，h o w
4、t od i s c o v e rt e m p o r a la s s o c i a t i o nr u l e sw i t hi m p r o v e da l g o r i t h mA p r i o r ia n dh o wt oe x p r e s st h ed i s c o v e r i n gr e s u l t sw i t hg r a p h K e y w o r d sD a t am i n i n g ，A s s o c i a t i o nr u l e s ，T e m p o r a la s s o c i a t i o n
5、r u l e s1引言自从A g r a w a l 等人提出关联规则挖掘问题 1 至今，人们已经提出了很多高速有效的关联规则挖掘 算法，通过在销售业等数据库上应用这些算法，发现了一些有价值的关联规则。但是，人们大都忽视了关 联规则的时态信息 2 ，而时态信息对于关联规则是十分重要的。让我们来看下面这个例子：我们在对一 个超市五年的销售数据库上进行关联规则挖掘，设定置信度阈值为0 7 ，我们发现只有2 0 买糯米的人也买莲子、红枣。但是当我们对每年的1 2 月和次年1 月进行关联规则挖掘发现，买糯米同时也买莲子和 红枣这条规则在4 个岁末年初的置信度均高于7 0 。由此可见，包含时态信息的关
6、联规则对于辅助决策具有更大的现实意义 3 。 关联规则最典型的应用是发现销售业事务数据库中的关联规则，销售业的时态特点就是销售业务 只发生在某一时间点。为了挖掘其中的时态关联规则，我们可以给事务数据库增加一个时间戳域，记录该事务发生的时间，在本文中，我们称这种含有一个 时间戳域的事务数据库为时间戳数据库。挖掘时态关联规则的问题可以分成三步。第一步，将事务数据库先划分为几个分区；第二步，在每个分区上进行时态关联规则的挖掘l 第三步，将得到的规则和用户希望考察的频繁数据项集表示出来，以利于用户观察规则和频繁数据项集的变化情况。 其中关键的问题在于第一步和第三步。对于大部分事务，从时间维来看所要挖掘
7、的数据的发生情况可以发现：在有的时间段，事务发生的频率很高，而在有的时间段，很少有事务发生。所以 如果使用通常的人为划分方法：接季节 1 ，按星期 4 ，按月将不利于规则的发现，并对观察关联 规则的时态特征产生不利影响。为此，我们在本文中 提出了如何使用聚类的方法对时间戳数据库进行分区。在分区上进行时态关联规则挖掘与进行无时态 关联规则挖掘的区别之处在于确定规则的生存时间。本文以无时态关联规则挖掘最典型的A p r i o r i 算法为例，讲解了如何改进无时态关联规则的挖掘 算法以使其能在分区上进行时态关联规则挖掘。在实际应用中，不仅时态关联规则本身，它生存的有效时间范围、它的各种参数随时间
8、的变化情况 以及其中可能蕴涵的周期性规律、某些频繁项目集中项目的增减情况及其支持度变化情况等对于决策 支持也都有很大的帮助作用。为了使用户能够更好 地观察这些变化，我们介绍了如何用图形表示法解决这个问题。2 问题定义设I = i 。，i 。，i 。) 是项目集合。给定一个时间 戳数据库D ，D 中的每个事务t 包括事务标识域( t i d ) 、项目域( i t e m s ) 、事务发生时间域( t i m e s t a m p )三个域，即t 可以表示为 T i d ，( A 。，A 。，A 。 ，T i m e s t a m p ) ，项目A i I ( i 一1 ，P ) 。由于t
9、 i m e s t a m p 域记载的是事务发生时间的时间戳信息，所以 D 中的所有事务就是按照事务发生时间的先后自动排序的。至于时间戳域的基本时间粒度( 小时，分钟，秒等) 是由用户自行决定的，在D 内是统一的。以后 文中提到的所有时间单位都是D 的时间戳域的基本时间粒度。 时间戳数据库D 在时间区间T I ( s t a r t t i m e T I e n d t i m e ) 上的部分记为D T I ，D T l 一 tI s t a r t t i m e 6 5 t t i m e s t a m p e n d t i m e ) ，D 1 1 也是按照事务发生时间的先后
10、顺序自动排序的。定义1如果对于I 的一个子集A 和D 中的一个事务t 有A 兰t i t e m s ，则称事务t 包含项集A ，或 事务t 支持项集A 。定义2 在D T 。上包含项集A 的事务集合中，首 先发生的事务t 的t t i m e s t a m p 称为T I 上项集A的生存时间的起点，记为A t s ，最后发生的事务t 的t t i m e s t a m p 称为T I 上项集A 的生存时间的终点，记为A t e 。定义5在D T t 上的关联规则X 净Y 的生存时间的起点为S t s ( S X n Y ) ，终点为S t e 。 定义4 在某个时间段T I 上，定义了生
11、存时间 的关联规则X 寺Y 称为时态关联规则，记为( X 净Y ， t s ，t e ) ，其中X 净Y 称为该时态关联规则的规则部分。 上面给出了时态关联规则以及相关内容的定义，弥补了传统的关联规则定义在时态方面的不足。5 在时间戳数据库上挖掘时态关联规则5 1对时间戳数据库进行分区为了在D 上找到事务发生次数足够多，并且发生的时间相对集中的各个不相互交叠的分区，我们可以使用如下的分区方法。 定义5设在D 一 t i ：1 i N 的时间戳域t i m e s t a m p 上的分区G i = ( t i ：1 s i q N ( i = 1 ，2 ，n ) 。G i 的直径d 是事务在时
12、间域上的平均成对距离。d ( G i ) 一k ；乏k ，8 x ( t i t i m e s t a m p - ，t i - t i m e s t a m p - 1 ) ( q s + 1 ) ( q s )其中的淑可以是任何一个对分区行之有效的 距离函数。通常使用的有欧几里得( E u c l i d e a n ) 距离函数和曼哈坦( M a n h a t t a n ) 距离函数。 定义6 一个聚类分区G i 的密度，就是G i 内事务的个数。 在一个时间轴X 上，X 上的单元格就是D 上的基本时间粒度。将D 中的每个事务t 按照t t i m e s t a m p 标识在
13、轴上，形成一个时间轴X 轴，分区就是要根据用户指定的区域直径d 。和区域密度s 。，利用聚类算法，例如B I R C H 算法【引，找出X 轴上符合条件的不相互重叠并尽可能相邻的各个区段，然后将相应区段内的事务存入相应的G t ( i = 1 ，2 ，n ) 。利用聚类分区方法，我们可以在事务发生时间 的自然分布基础上按照用户给定的参数找到事务集中发生的分区，然后再在找到的分区上进行时态关联规则挖掘，这比以前的按照时间区段划分的方法更利于发现有价值的时态关联规则。6 6 。5 2 挖掘时态关联规则 在每个分区G 上挖掘时态关联规则的问题与挖掘无时态关联规则的问题一样可以分解为下列两个子问题：(
14、 1 ) 找出分区内所有的频繁项集，并确定每个频繁项集的生存时间范围。( 2 ) 应用频繁项集产生关联规则。为了解决问题( 1 ) ，我们可以通过改进任何一个 解决关联规则挖掘的算法，为其加上确定每个频繁项集的生存时间范围的功能即可。下面我们给出了关联规则挖掘最典型的A p r i o r i 算法的改进方法。首先，我们使用g e n l a r g e l i t e m ( G i ) 函数来 取代a p r i o r i 算法中的生成频繁1 项集的部分。函数名：g e n l a r g e l 一i t e m输入：G i 输出：L 。 f u n c t i o ng e n l
15、a r g e l - - i t e m ( G i )C 1 一巾： f o ra l lt r a n s a c t i o n st G id o f o ra l lc td o ( i f ( c 奄C 1 ) t h e n ( C 1 一c l U c ) ： C 1 t s 0 1 t e 。t t i m e ： c c o u n t = 1 ： e l s e C c o u n t + + ： c t e m - t t i m e ： D 中的事务按照发生的先后顺序排列 L 1 = c c 1 I c c o u n t m i n s u p e n df u
16、n c t i o n然后，我们在A p r i o r i 算法的最后，添加一个计算每个频繁项目集的生存时间的过程c a l c l i f e t i m e 。p r o c e d u r ec a l c l i f e t i m e f o r ( k Z ；h 巾；k + + ) f o ra l ll L kd o 1 t s = 1 中各项目的t s 的最大值； I t e l 中各项目的t e 的最小值； ) e n dp r o c e d u r e问题( 2 ) 的解决就比较简单了，可以参照参考文 1 中的方法。所不同的是需要增加对时态关联规则的规则部分生存时间的求解过程。总之，利用上述类似方法改进原有关联规则挖掘算法，为它们增加频繁项集的生存时间计算过程，即可以解决时态关联规则的挖掘
