《基于粒计算的时序数据流关联规则挖掘模型研究》由会员分享，可在线阅读，更多相关《基于粒计算的时序数据流关联规则挖掘模型研究（4页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 7 V 0 1 3 4 N o 8 A 基于粒计算的时序数据流关联规则挖掘模型研究 R e s e a r c ho nG r a n u l a rC o m p u t i n gb a s e dT i m eS e r i e sD a t aS t r e a m sA s s o c i a t i o nR u l eM i n i n gM o d e l 朱小栋黄志球王磊程亮沈国华 ( 南京航空航天大学信息科学与技术学院南京2 1 0 0 1 6 ) A b s t r s dD a t at a k e st h ef o r l T lo fc o
2、n t i n u o u sd a t as t r e a m sr a t h e rt h a nt r a d i t i o n a ls t o r e dd a t a h a s e si nag r o w i n gr n 皿一 b e to fa p p l i c a t i o n sw h i c hi n c l u d e s e n s o rn e t w o r k s ，n e t w o r kt r a f f i cm o n i t o r i n g ，n e t w o r ki n t r u s i o nd e t e c t i o
3、 ne t c C o m p a r i n gw i t hm u c hw o r ko na l g o r i t h m sd e v e l o p i n g ，t h e r ei sl i t t l ew o r kp a i do nm o d e l i n gd a t am 访访ga sw e l la s d a t as t r e a z l 强r n m L 嘻I nt h i sr e p o r t ，w ep r e s e n t e da g r a n u l a rc o m p u t i n gh a s e da s s o c i a
4、 t i o nr u l em i n h - 1 9m o d e li nl a r g e t i m es e r i e sd a t as t r e a n i s - W ed e t a i l e d l yd e s c r i b e dt i m es e r i e sd a t as t r e a m sa n da s s o c i a t i o nr u l em i n i n gp r o c e s si nd a t a s t r e a m 地S o m ee x a m p l ea n de x p e r i m e n t sw e
5、 r ea 1 5 0i l l u s t r a t e dt ov a l i d a t et h i sm o d e LT h em o d e li su s e f u lt Of u r t h e r u n d e r s t a n dt h ep r o c e s so fr u l e se x t r a c t i n ga n dd e v e l o pa s s o c i a t i o nr u l em i n i n ga l g o r i t h m s K e y w o r d sG r a n u l a rc o m p u t i
6、n g tD e c i s i o nl o g i cl a n g u a g e ，D a t as t r e a m s ，D a t am i n i n g ，A s s o c i a t i o nr u l e 1 引言 如果说数据挖掘是智能数据分析发展的一个发 展阶段，则数据流挖掘成为近年智能数据分析发展 的一个新的研究阶段。不仅因为许多应用领域如传 感器网络、互联网的访问、计算机网络监控、股市、电 话记录产生大量高速实时的数据流，使得传统的数 据挖掘技术不能适应这种新的数据形式，而且，对数 据流进行数据挖掘已成为这些领域的迫切需要。 对数据流挖掘的算法研究有很多，但针
7、对数据 流的数据挖掘建模目前的研究较少 1 一】。粒计算作 为一个新的信息和知识处理的方法近年来已经被许 多研究者所重视，以及在许多领域中得到应用。z a d e h 首先提出信息粒化的概念，带来对粒计算的新 的研究兴趣 3 。Y a o ，L i u ，L i n 等做了许多关于粒计 算的工作，并提出了一些基于粒计算的数据挖掘建 模方法，例如信息表，粗糙集，领域系统等 1 4 一 。 关联规则是数据挖掘的一个核心课题，本文基 于粒计算的理论，提出一种时序数据流中关联规则 挖掘的模型，并通过实验验证模型的正确性和有效 性。在此模型上，数据流的数据挖掘能够得到很好 的解释，并且该模型有助于时序数
8、据流的关联规则 挖掘算法的进一步开发； 文章余下部分组织结构如下。第2 节给出数据 流的信息系统模型。第3 节提出一种面向时序数据 流的决策逻辑语言D S - D L ，该语言采用T a r s k i 意义 下的模型和可满足性。第4 节给出基于D S - D L 语 朱小栋博士生，研究方向为数据仓库与数据挖掘粒计算，模糊推理。 1 5 2 言的粒计算方法，并解释数据流的关联规则挖掘过 程。第5 节通过一个网络监测数据流的实验来验证 模型的正确性和有效性。最后是本文的总结和进一 步的工作。 2 数据流的信息系统模型 2 1 数据流的概念 时序数据流；以下简称数据流，是一个不断出现 的项目序列
9、6 l 。与传统的静态数据相比，数据流是 连续、潜在无边界的，通常高速地出现。数据流里的 数据称之为流数据，随着对数据流的应用领域不断 增加，对数据流进行数据挖掘已成为数据挖掘的研 究热点。 我们发现当前的数据流形式至少有如下特征： 首先，进行数据流处理的输入数据不是固定在 磁盘或者存储器上的，而是连续的大量的随机出现 的数据流。其次，数据流的大小是潜在的无限大的。 相比大量的数据流来说，主存或者磁盘空间的容量 太小，不能作为数据流的存储器。再次，数据流是不 断出现的，因此我们要不断地对数据流挖掘的结果 进行实时更新，即提供连续的结果。最后，我们不能 控制数据流的项目序列到来的顺序，这些项目序
10、列 是以流的形式随机到来的。 2 2 数据流的信息系统模型 信息系统或者信息表是描述数据的一个方便有 效的形式化方法。我们假设数据流是连续无边界的 信息表也就是说，信息表里的对象是无界的。为了 方便处理流式数据，我们引入一个时间窗口( t i m e w i n d o w s ) 来处理流数据。许多文献用到了基于时 间窗口的数据流处理技术 6 | 。 定义1 数据流是六元组：D S = 丁，T ，A t ， L ， V aI a A t ) ， kJ a a A t 。 这里T w 是一个时间窗口，可以设置为一秒 钟、一分钟或其它等等。一个T w 可以决定具体的 数据流的信息表D S 的长度
11、。T 是一个具体的T w 里的事务集合( t r a n s a c t i o ns e t s ) ，T 中的一个事务 又称为对象。我们用时间戳( t i m es t a m p ) 标记T 中 的一个事务，这个时刻即事务被记录的时刻。D S 的长度等于集合T 的基数，我们用D S L e n g t h 来 表示。A t 是某一个属性的非空有限集合。L 是一 个使用A t 集合的属性上定义的语言，下一节里我 们会进行解释。V a 是对于a A t 的属性值的非空 集合。儿是一个从T 到V a 上的信息映射。 3 面向数据流的决策逻辑语言 波兰学者P a w l a k 的粗糙集理论对决
12、策逻辑 ( D L ) 语言进行了详细的讨论 7 。简单地说，决策 逻辑语言是一种特殊的经典谓词逻辑，其语义采用 T a r s k i 意义下的模型和可满足性：信息系统J S 是 模型，对符号以及公式进行解释；如果对象z 在模 型j S 的解释下满足公式乒，则记作工I - 壬。Y a o 借助Z a d e h 提出的广义约束给出带有语义限制的 逻辑语言 8 3 ，并将其作为一种粒计算的模型。 下面我们提出一种面向数据流的决策逻辑语言 D S - D L ，其语义采用T a r s k i 意义下的模型和可满足 性。定义1 给出了该语言基于的模型，以下讨论该 语言的可满足性。 定义2 采用下
13、面的规则确定D S - D L 的公式： ( 1 ) 是原子公式，a A t 且o V a ； ( 2 ) 若9 I 和9 是公式，则- 7 拳，声A P ，乒V P ，5 9 ，庐量驴是公式； ( 3 ) 只有有限次利用规则( 1 ) ( 2 ) 得到的是公式。 形如乒 9 和( 乒V9 ) 一c t ，被称为合式公式，原 子公式和合式公式统称为公式。 定义3 在给定的数据流信息系统D S 和数据 流决策逻辑语言D & D L 下，事务z 的可满足性归纳 的定义为： ( 1 ) 工卜I ( 口，可 当且仅当I a ( 工) = 口 ( 2 ) 工 - 一拳当且仅当非z 垂 ( 3 ) z 卜
14、I A 妒当且仅当T 卜乒并且z 卜9 ( 4 ) z 卜V 够当且仅当z 卜乒或者z 卜l9 ( 5 ) z 卜I ，I 一妒当且仅当zF - 一乒V 9 ( 6 ) z 卜声兰够当且仅当z 卜多一9 并且z 卜9 一声 定义4T 在公式乒上是可满足的当且仅当存 在z T 且z 卜西。 定义5 对于T 中任何事务z ，如果它满足公 式牵，那么我们称这个公式巾在当前T w 下是真。 定义6 庐是数据流信息系统D S 中公式，则 的意义集定义为m ( 乒) = z Tz 卜壬 。 定理1 夺和中是D S 的公式，则我们有下面的 性质： m ( ( n ，口) ) = z TII a ( z )
15、= 口) 研( 7 夺) = T - - m ( 争) 优( 夺A 妒) = m ( 书) n m ( 币) 扰( 卡V 甲) 5 仇( 夺) U m ( 9 ) 班( 卡一9 ) 2 优( 一7 事V 9 ) 研( 牵兰9 ) = m ( 夺一9 ) nm ( 矿+ 壬) 定理2 如果数据流信息系统D S 中T 在公式 拳上是可满足的，则m ( j I ) 非空；如果公式，I 在当前 T w 下是真，则m ( 拳) 是T 自身。 定义7 时间窗口T W 是一个二元组( 而，r e ， r 6 称为该T W 的起始时间，邪称为该时间窗口的终 止时间。一些无线传感器网络领域产生的数据流是 随机发
16、生，这些时间戳是不均匀的。而有些数据流 如股市数据流等能够按照固定的时间产生数据，这 种情况下，可以将时间窗口细分为均匀的时间刻度， 数据流则每隔一个时间刻度产生一个事务。 4 基于D D L 的粒计算 4 1 粒的描述 基于粒计算的问题可以被分成两个相关的方 面，粒的构造和粒计算。前者是处理粒的形成，表示 和解释，后者则是利用粒进行问题求解。在D D L 中，一个公式乒的意义集m ( 壬) 被称为一个粒。 在一个时间窗口中，事务是不变的，可以看作一 个静态数据集。但是，在时序数据流中，随着时间的 推移，事务数据集存在更新。从时间窗口的角度看， 这个事务数据的更新可以分解为事务的增加和删 除。如果增加了事务数据，则某个公式壬的意义集 m ( 壬) 可能会增大，相反，如果删除了事务数据，则公 式的意义集棚( 9 1 ) 可能会减小。 4 2 关联规则的解释 数据挖掘产生的关联规则和其他的规则如决策 规则代表j ，知识。规则可以分为两类，
