（计算机系统结构专业论文）基于互信息网络模型的时间序列数据库知识发现.pdf

摘要 本文提出了一种新的、完整的时间序列数据库知识发现方法。该方法是基 于s h a n n o n 信息理论中的互信息理论、概率统计方法、v o r o n o i 图滤波及模糊逻 辑等理论上，包含了对时间序列数据库进行知识发现的般步骤：时陋j 序列数据 库构建，清洗和过滤时间序列数据，特征提取，构造互信息网络并提取规则，和 模糊方法解决规则冲突并简约规则。知识发现的结果规n - i 以用来预测时阳j 序列的未来行为。 论文首先介绍了时间序列数据库与一般数据库的差别及定义，说明时间序 列数据库的在用于知识发现的目标：趋势分析，相似性搜索和序列模式挖掘。讨 论并分析了专门数据库的不同构建方法，在此基础上，引出如何把现有的数据库 重组成时间序列数据库。 接着，文章提出了一种多层次互信息网络，用它来进行知识发现。文章从 s h a n n o n 信息理论的互信息概念和意义出发，利用事件集的先验熵( 独立事件集 信息量) 和后验熵( 条件信息量) 之间的差( 也就是互信息) 来检测输入属性和 目标属性之间的关联程度，逐层构造和控制网络的结构，从而推导出输入属性和 目标属性之怕j 的关联规则。 r 峙上述基础上，文章叙述了如何利用互信息网络模型对时问序列数据库进 行知识发现的系统方法。1 ) 分析用来滤波的移动平滑技术及其缺点，为了克服 这些缺点，提出了用v o r o n o i 图进行滤波的方法，阐述该方法的进行自适应滤波 的优点；2 ) 对于提取特征属性，本文介绍了两种时徊j 序列数据的重要特征属性： 趋势段( 用于发现事件) 和信噪比：3 ) 说明用互信息网络进行时问序列知i = 发 现的详细步骤：4 ) 在结果处理上，用模糊逻辑对互信息网络中提取的规则进行 冲突处理和归约，提高结果的可解释性。 我们利用浙江电信时间序列数据进行实验和验证，结果表明基于互信息网 络模型的时间序列数据库知识发现是有效的。文章最后指出时脚序列知识发现的 重要应用意义和进一步发展方向。、 7 关键字：时间序列数据库、互信息、v o r o n o i 、特征属性、模糊逻辑、知识发现 abst ract t h i st h e s i ss u g g e s t san o v e l ，c o m p l e t ea p p r o a c ht ok n o w l e d g ed i s c o v e r y ( k d ) i nt i m es e r i e sd a t a b a s e ( t s d b ) t h ea p p r o a c hb a s e du p o nm u t u a li n f o r m a t i o no f s h a n n o n si n f o r m a t i o nt h e o r y ，p r o b a b i l i s t i ca n ds t a t i s t i c a lm e t h o d s ，f i l t e r i n gw i t h v o r o n o ig r a p h ，a n df u z z yl o g i c t h eg e n e r a lk ds t a g e si nt s d mi n c l u d e ： c o n s t r u c t i o no ft s d b ，c l e a n i n ga n df i l t e r i n go ft i m es e r i e sd a t a ，f e a t u r ee x t r a c t i o n c o n s t r u c t i o na n dr u l ed e d u c t i o no fm u t u a l i n f o r m a t i o nn e t w o r km o d e l ( m i n m ) ，a n d f u z z yl o g i cf o rr u l ec o n f l i c t i o na n dr e d u c t i o n t h er e s u l t so fk di nt s d ba r er u l e s ， w h i c hc a nb eu s e dt op r e d i c tt i m es e r i e sb e h a v i o ri nt h ef u t u r e f i r s t ，t h et h e s i sp o i n t so u tt h ed i f f e r e n c eb e t w e e nt s d ba n dg e n e r a ld a t a b a s e a n dd e f i n i t i o no ft s d b ，e x p l a i n i n gt h eo b j e c t i v e so ft s d bf o rk d ：t r e n da n a l y s i s s i m i l a r i t ys e a r c h i n ga n ds e r i e sm o d e lm i n i n g o nd i s c u s s i n ga n da n a l y z i n gd i f f e r e n t c o n s t r u c t i o no fs p e c i a ld a t a b a s e ，w h i c hi n c l u d e st s d b ，w ei n t r o d u c eh o wt o r e m o d e lt s d bf r o mg e n e r a ld a t a b a s e t h e n ，t h ep a p e rd e t a i l e dt h ec o n s t r u c t i o no fm i n m ，w h i c hi su s e dt od i s c o v e r k n o w l e d g e a f t e rc o n c e p to fs h a n n o n si n f o r m a t i o nt h e o r ya n dm u t u a li n f o r m a t i o n b e i n gi n t r o d u c e d ，u s i n gd i f f e r e n c eb e t w e e np r i o r ie n t r o p ya n dp o s te n t r o p yt od e t e c t t h ea s s o c i a t i n gd e g r e eb e t w e e ni n p u ta t t r i b u t e sa n dt a r g e ta t t r i b u t e s ，w h i c hc o n t r o l s t h en e t w o r kc o n f i g u r a t i o n t h en e t w o r k ，w h i c hc o n s i s t so fs e v e r a li n p u tl a y e r sa n da t a r g e tl a y e r ，c a nb eu s e dt od e d u c ta s s o c i a t i n gr u l e sb e t w e e ni n p u ta t t r i b u t e sa n dt a r g e t a t t r i b u t e s u p o nt h ec o n t e n t sd i s c u s s e da b o v e ，t h et h e s i ss p e c i f i e ss e v e r a ls t e p so fu s i n g m i n mt od i s c o v e rk n o w l e d g ei nt s d b 1 1a n a l y z i n gt h ee x p o n e n t i a ls m o o t h i n g t e c h n o l o g ya n di t ss h o r t c o m i n gw h e nu s e dt of i l t e r i n g ，t h ep a p e rp r o p o s e san e w t i m e s e r i e sf i l t e r i n gm e t h o d ，w h i c hc a no v e r c o m et h es h o r t c o m i n go nb a s eo fi t sa d a p t i v e v i r t u e s 2 ) t r e n ds e g m e n ta n ds i g n a lt on o i s er a t i o ( s n r ) a r ei m p o r t a n tf e a t u r e si n t i m es e r i e s w es h o wt h em e t h o d so fg e t t i n gt h e mf r o mf i l t e r e dt i m es e r i e s 3 ) d e t a i l e ds t e p so fk n o w l e d g ed i s c o v e r y i nt i m es e r i e s 4 ) i nt h ep o s t p r o c e s s i n gs t e p f u z z yc o n c e p t sa r eu s e dt or e s o l v ec o n f l i c t i o nb e t w e e nr u l e sd e d u c t e df r o mm i n 4 a l s o ，w es h o wt h a tt h en u m b e ro fr u l e sc a l le a s i l yb er e d u c e db yi n t r o d u c i n gf u z z y c o n c e p t w ed e s i g n e da l le x p e r i m e n tw i t ht h eh e l po fz h e j i a n gt e l e c o mt i m es e r i e s d a t a b a s et ov a l i d a t eo u rm e t h o d i t sr e s u l ts h o w st h ee f f e c t i v e n e s so fm i n mf o r k n o w l e d g ei nt s d b a tt h ee n do f t h i st h e s i s ，w ep o i n t e do u tt h ei m p o r t a n to fk di n t s d bi nv a r i o u sa r e a sa n dd i r e c t i o ni nt h ef u t u r e k e y w o r d ：t s d b ，k n o w l e d g ed i s c o v e r y , m u t u a li n f o r m a t i o n ，v o r o n o i ，f e a t u r e e x t r a c t i o n ，f u z z yl o g i c 5 1 引言 本文的研究是从知识发现技术中发展出来的。随着自动数据收集工具、数据 库系统和数据仓库技术的高速发展，不管是科研机构、政府部门，还是大型企业， 都想从大量的历史数据中发现和挖掘隐藏的信息( 也称数据挖掘) 。许多企业和 政府部门都保存了带有时间标识的数据，也就是时间序列数据，因此，研究和丌 发能够从这些时间序列数据中挖掘出有用知识的方法和工具是非常重要的。一个 时间序列可以定义为：“一组实际的数掘序列，每个数据表示在某一时间点的 值”。时间序列数据集在新的数据库应用中显得越来越重要，比如数据库知识发 现和数据库管理等。我们很希望能够从时间序列数据库中提取有趣的知识一一比 如，以规则形式表示的知识( 这正是本文所研究的目标) 。在本章中，首先简要 介绍时间序列数据集和数据库技术，接着说明相关研究的状况，及本文的组织。 1 1 数据挖掘和数据库技术 一般来说，知识发现的目标就是为了支持决策，数据库的进一步发展目标也 是为了提供支持决策，数据仓库的发展正好体现了这一精神：帮助用户作出更好 和更快的决策。这几年，我们看到数据库技术的飞速发展，用束支持决策的大型 数据库已经成功的应用到许多行业中：制造业、零售业、金融业、运输业、电信 业等等。 用于知识发现的时间序列数据库应该具有如下特点：有目的的，随时间变 化的和稳定的( n o n v o l a t i l e ) ，提供在线分析和决策支持。数据库应该保存长期 历史的、多粒度的和经过加工整理的数据。这样的数据库容量可能达到上百g ， 相应的，需要提供浏览、连接、聚集等更加复杂的存驳和搜索方法。这些功能大 部分都能由现有的数据仓库实现，但是，在对时间序列进行知 ： 发现中很重要的 一个步骤数据清洗和滤波，数据仓库并不能提供很好的、与知识发现目标相 一致的方法。因此，我们这里并不用数据仓库，而用专门时间序列数据库。我们 可以在第二章看到，由一般的关系数据库经过组织以后的时间序列数据库很容易 实现。 知识发现工具是对数据库进行查询分析的前端工具。 从数据库中挖掘发现信息和知识并不是个新的领域，已经被许多公司所接 受和认定为对于管理、决策成功的重要领域。 随着数据库中数据的膨胀增长，其中隐藏着能够为用户提供参考的知识。 然而，这些隐减的信息并不能出传统的统计方法所能解决。解决办法就是：知识 发现。数据库知识发现技术揭示隐藏在数据库中的信息，这已经成为一个越来越 重要的研究领域。这些信息比如趋势、关联规则可以用来提高决策的有 效性。 1 2 时间序列数据库知识发现现状 时间序列数据库管理系统( t s m s ：t i m es e r i e sm a n a g e m e n ts y s t e m ) 与一 般的数据库管理系统( d b m s ：d a t a b a s em a n a g e m e n ts y s t e m ) 区别的特殊属性 在w d r e y e r 等的文献 3 2 】中研究过。对于一个t s m s 数据模型，一个时间序列 包括事件( 随时间变化的) 数据和与之相关的数据头部。例如，事件数据可以是 一个股票的丌盘价和收盘价是事件数据，而数据头部可以是不随时例变化的( 如 公司名称) ，也可以是变化的( 如：平均收盘价) 。某一时问点和该点的事件。i j 以 是一对一的关系，也可以是一对多的关系。 j h a n 等用数据挖掘的方法处理时间序列数据库中的周期段和部分周期模 式 3 3 】，他们是基于数据挖掘的关联规则方法，目的在于发现时间序列摸式( 按 时问排序的事件组) ，而不是时间规则( 事件间的原因一结果关系) 。另外， h m a n n i l a 等也对事件间的关联( 片段) 进行研究 3 4 ，片段也表示事件序列只是 局限在一个窗口中。频繁出现的片段是研究的重点，对于发现的片段数目可以由 用户设定的窗口大小和片段频繁出现的显著程度来限制。 预测和检测事件的发生是时间序列数据库研究的另一个方向。g m w e i s s 等 住 3 5 中提出了一种从时问序列模式中预测事件的学习方法可以作为代表。一个 事件定义为对未来时间点的观测，描述为一组属性一一值对，而不是预测下一个 事件来临的准确时间，这在带噪音的时间序列中是非常困难的。这个系统能够在 预测的时间段内对即将发生的事件发出警告。因此，如果被预测的事件落在检测 时矧段内，则认为是f 确的。转折点意味着时间序列中重要的事件，是时白j 序列 中的时间点，代表着时间模型参数的变化，甚至模型本身产生变化。 3 6 】对于 发现转折点的研究中提出了一种监测算法，该算法按照相似性标准对时削序列进 行分段，线性回归用来对每一段进行拟合。 时间序列的相似搜索在t s m s 中是一个重要组成部分，现在有许多研究相 似搜索的方法。m o a v r i l o v 等人在 3 7 1 q u 提出了时间序列相似性度量方法。这些 度量方法是在对股票数据的基础上进行的，原始序列以两种方法进行维度归约： 基本成分分析和把时间域聚集在定长的窗口中。 3 7 的结论是：一个5 维的时间 序列可以提取出9 7 6 2 的重要信息。 1 3 本文的组织结构 在本文中，我们将展示一个完整的时间序列数据库通用知识发现算法。按照 u s a m am f a y y a d 等人给出的多处理阶段过程模型，数据库中知识发现的基本步 骤( 图1 2 ) 包括： 1 数据选择：根据用户的要求从数据库中提取与k d d 相关的数据，k d d 将主要从这些数据中进行知识提取，在此过程中，会利用一些数据库操 作对数据进行处理。 2 数据预处理：主要是对阶段2 产生的数据进行再加工，检查数据的完整 性及数据的一致性，对其中的噪音数据进行处理，对丢失的数据可以利 用统计方法进行填补。并确定k d d 的预测属性和目标属性；根掘目标 属性确定k d d 是发现何种类型的知识，因为对k d d 的不同要求会在具 体的知识发现过程中采用不同的知识发现算法。 3 数据缩减：对经过预处理的数据，根据知识发现的任务对数据进行再处 理，主要通过投影或数据库中的其他操作减少数据量。 4 确定k d d 的目标：根据用户的要求，确定k d d 是发现何种类型的知识。 因为对k d d 的不同要求会在具体的知识发现过程中采用不同的知识发 现算法。 5 确定知识发现算法：根据阶段5 所确定的任务，选择合适的知识发现算 法，这包括选取合适的模型和参数，并使得知识发现算法与整个k d d 的评判标准相一致。 6 数据挖掘( d a t am i n i n g ) ：运用选定的知识发现算法，从数据中提取出用 户所需要的知识，这些知识可以用一种特定的方式表示或使用一些常用 的表示方式，如产生式规则等等。 7 模式解释：对发现的模式进行解释，在此过程中，为了取得更为有效的 知识，可能会返回前面处理步骤中的某些步以反复提取，从而提取出更 有效的知识。这期阳j 也包含对知识的一致性的检查，以确信本次发现的 知识不与以前发现的知识相抵触。 图1 2 知识发现过料步骤 本文的余下部分将按照上述步骤以如下形式进行组织： 第二部分叙述时i 可序列数据库( t s d b ) 的概念和组织。首先讨论当前普遍 应用的关系型数据库的特点；接着，探讨关系型数据库在对时间序列方面进行知 识发现时存在的局限。最后，针对时间序列知识发现的特点，对关系型数据库进 行改造，建立时序特征属性数据库。特征属性分为统计属性和应用属性。( 这部 分包含上述l 、2 步骤) 。 第三部分，按照第二部分建立的时序数据库，提出了一种通用的时间序列数 据库中知识发现的建模方法：互信息网络模型( m i n m ：m u t u a li n f o r m a t i o n n e t w o r km o d e l ) 。m i n m 可以用于发现时间序列中的关联规则。 第四部分，在上述基础上，文章叙述了如何利用互信息网络模型对时间序列 数据库进行知识发现的系统方法( 这部分包含上述3 、4 步骤) 。 第五部分，实验部分。该部分是第二部分和第三部分的应用，通过浙江电信 数据库，建立时间序列数据库，并对其进行知识发现。来验证m i n m 模型的有 效性。最后，通过该实验评价m i n m 模型。 作。 第六部分，结论和未来工作。探讨时间序列数据挖掘的几个方向以及未来工 2 时间序列数据库 在生产和科学研究等过程中，总要记录一组变量z ( f ) 进行观察测量，在一系 列时刻t l ，f 2 ，f 。( t 为自变量且t i t 2 r 。) 得到的离散的有序数集合 x ( r ) ，x ( t ：) ，x ( t ) ，x ( t 。) ，我们都称为离散时间序列( 本文只讨论离散的情 况，简称时间序列) 。在实际问题中，要记录的观测量往往很多，并且，自变量 f 除代表时间外，也可以具有各种不同的物理意义，例如代表长度、温度、速度 或其它单调递增地取值的物理量，这都需要保存下来。随着时间的过去，数据积 累越多，需要有专门的数据库来管理这些数据，以利于考察研究对象的变化规律。 这就产生了时| 白j 序列数据库。 2 1 时间序列数据库与普通数据库的区别 在大多知识发现问题中，一个规范的、静态的数据库包含记录( r e c o r d ) 的 集合，每个记录都由若干个属性( a t t r i b u t e ) 组成。记录的顺序( o r d e r i n g ) 在静 态数据库中没有多大的意义，至少从数据挖掘的角度来说是无关的。相反，一个 时间序列数据库( t s d b ：t i m es e r i e sd a t a b a s e ) 包含的记录集中的部分属性跟 时间戳( t i m e s t a m p ) 相关联。 例如，一个时间序列数据库可能是一个包含股票信息的数据库，其中的每 条记录不仅包含静态的属性( 如：股票名称等) ，还包含一些动念的属性( 如： 收盘价和交易量) ，这些动念数据是与某一天相关联的。其它类型的时问序列数 据库还可能是在线监测系统，零售店的销售交易或者网页浏览数据。 静态数据库和动态数据库( 时间序列数据库) 的一个主要区别在于每个属 性所载的信息。在静态的数据库中，一个记录的每个属性与其它的记录的属性是 互相独立的；也就是说一个电录的属性改变不会影响到其它记录的属性值。而在 时间序列数据库中，一些属性只有在特定的时间段下才有意义。例如，一个电信 时间序列数据库，我们对一段时间内的客户业务量的行为特性感兴趣，而不是某 一天的时洲业务量。 从上述讨论中可以得出时间序列数据库的定义： 定义2 - j ? 一个时间序列数据库( t s d b ) 是一个记录的集合 ，每个记 录包含若干个属性和一个时间属性，= “，口：，口。，t ，) 。 这里，每个属性可以是实数值a r 或取离散的值a n ，可以跟一个时 问值相关联，也可以不相关。如果与时剧相关联，则它是动态( d y n a m i c ) 的， 否则，称之为静念的( s t a t i c ) 。其中时间属性f 按照应用的目标不同来确定其 时间范围，如天，月或年等。 动态性是时间序列数据库区别于其它普通数据库的重要特性。 2 2 时间序列数据库知识发现的目标 时间序列数据库中知识发现一般进行“趋势分析”，“相似搜索”，“挖掘序列 模式”等。 2 2 1 趋势分析 时序变量y ，例如表示股票市场中的某股的每同收盘价，它可以表示为时间 ，的函数，即y = f ( f ) 。此函数可以图示为一个时序图，它描述了一个点随时间 变化的情况。目前一般有四种主要的变化和成分用于特华时序数据： 长期或趋势变化( 1 0 n g - t e r mo rt r e n dm o v e m e n t ) ：用于反映一般的变化方 向，其时序图是在较长时间间隔上的数据变化。这种变化反映为一种趋 势线或趋势曲线。确定趋势线或趋势曲线的方法包括加权移动平均方法 和最小二乘法。 循环变动或循环变化( c y c l i cm o v e m e n to rc y c l i cv a r i a t i o n ) ：主要指循环 性，即趋势线或趋势曲线在长期时间内呈摆动现象，它可以是也可以不 是周期性的。即在等时间间隔之间，循环不需要沿着同样的模式演进。 季节性变动或季节性变化( s e a s o n a lm o v e m e n to rs e a s o n a lv a r i a t i o n ) ：它 反映的是每年都重复出现的事件，例如某节日前后，某种商品的销售会 突然增加。也就是说，季节性变动是指同一或近似同一的模式，在连续 几年的有关月份重复出现。 非规则或随机变化( i r r e g u l a ro rr a n d o mm o v e m e n t ) ：反映的是由于随机 或偶然事件引起的零星时序变化。 以上有关趋势的、循环的、季节性的和非规则性的变动，可以分别用变量 t , c s , i 表示。时序分析也可以指将时序分析分界为以上4 各基本运动的分析。时 序变量y 可以表示4 个变量的积，或4 个变量的和。其选择通常都是凭经验的。 2 2 2 相似搜索 相似性搜索是要找出与给定查询序列最接近的数据序列。子序列匹配是找出 与给定序列相似的所有序列，而整体序列匹配是找出彼此相似的序列。它在金融 市场、医疗诊断分析和科学与工程数据库分析等方面都有很多的用处。 7 数据变换：从时间域到频率域的变换。对时序数据的相似分析，通常采 用欧氏距离作为计算的依掘。许多数据分析技术需要数据来自频率域。 因此，保持距离不变的工f 交变换经常用于从时间域到频率域的变换。两 个常见到的数据变换是离散傅立叶变换矩阵和离散小波变换。 增强相似搜索方法，处理偏移和振幅中的间隙和差异：大部分实际应用 并不一定要求匹配的子序列在时削轴上完全一致，而只要求两个序列具 有相同的形状，但在序列内存在间隙和在偏移或振幅中存在差异。一种 改进的相似模型，是允许用户或专家晚明一些参数，如滑动移动窗口尺 寸，最大间隙、匹配片断等等。 相似搜索的索引方法：为在大型数据库中改进相似搜索的效率，人们提 出了各种索引的方法。例如：r 树，r 一树用语存储最小边界矩形以加 速相似搜索。另外，还有后缀树等。 有关时间序列的查询语言：用来查询相似序列和其它更加复杂的查询。 2 2 3 序列模式挖掘 我们这罩重点讨论与本文相关较大的序列模式方面的挖掘。 启义2 2 7 时间序列模式知识发现( t s p k d ：t i m i n gs e q u e n c ep a t t e r n k n o w l e d g ed i s c o v e r y ) 是指在动态数据库( 记录随时问属性变化两改变状态) 发现，挖掘相对时间或其它模式出现频率高的模式。 序列模式的一个例子就是“一个9 个月前买了一台p c 的顾客有可能在一个 月内买一个新的c p u ”。很多数据都是这种时间序列形式的，我们就可以用它柬 市场趋势分析，客户保留和天气预测等等。 许多有关序列模式挖掘的研究主要针对符号模式( s y m b o l i cp a t t e r n ) ，因为 数字曲线模式通常属于统计时序分析中的趋势分析和预测范畴。 对序列模式挖掘，存在一些参数，其取值如何，将严重影响挖掘效果。第一 个参数是时间序列的持续时间( d u r a t i o n ) t ，持续时问可以是数据库中的整个守 列，或由用户选择的一个子序列，如对应于1 9 9 9 年的予序列。序列模式挖掘因 此是限定在特定的持续时剧内挖掘的。持续时间还可定义为一组分割的序列，如 每年，或股票暴跌后的每周，或火山喷发前后的的每周等。在这些情形中，可以 发现周期模式( p e r i o d i cp a t t e m ) 。 第二个参数是事件重叠窗口( e v e n tf o l d i n gw i n d o w ) w 。在指定的时问周期 内出现的一组事件，可以视为某一分析中一起出现的事件。若w 设为与持续时 问r 相同的值，则找出的是与时i 甸无关的模式即是一些基本的相关模式。若 w 取值为0 ( 即没有时间序列折叠) ，则找出的序列模式中的每个时问出现在不 同的时削值。若w 设为之间的值，则考虑同一周期内出现的交易，分析序列被 折叠。 第三个参数是被发现的模式中时间间隔( i m e r v a l ) i n t 。此参数可取如下值： i n t = o ：表示没有时间间隔：即是，所找出的是严格连续的序列，如序列模 式a l - i a d 。，其中a ，在时间i 出现的事制：。事1 ，| ：折叠窗口w 同此情形。例如如事件折叠 窗口设为一周，将找山连续儿周内出现的模式。 r a i ni n t e r v a l g n t _ m a xi n t e r v a l ：表示要找山晟小间隔为m i ni n t e r v a l 而最人间隔为 m a x 一i n t e r v a l 的模式。 i n t = c # o ：用户可以找出具有确定时削间隔胁，的模式。例如，查询“每当股 市指数下降5 ，两天后会发生什么事情? ”，将搜索间隔i n t = 2 ( 天) 的序列模 式。 用户可以在要挖掘的序列模式上指定约束，方法是提供“模式模板”，其情 形可以使系列片段( s e r i a le p i s o d e ) ，并行片段( p a r a l l e le p i s o d e ) ，或正则表达式。 系列片段是一组在总序列中出现的事件，而并行片段则是一组与出现次序无关的 事件。设记号( e ，f ) 表示发生在时间t 的时间类型e 。考虑数据( 4 ，) ，( c ， 2 ) ，( b ，j ) ，具有宽度为2 的事件折叠窗口，其中系列片段彳一b 和并行片段 a & b 都出现在数据库中。用户还可以正则表达示说明约束，如( a i b ) c * ( d i e ) 它表示用户希望查处这样的模式：事件a 和b 先出现( 但二者的次序无关紧要) ， 之后示一个或一组事件c ，再之后是事件d 和e ( d ，e 无先后) 。注意，其它事 件可以出现再正则表达式说明的序列中。 2 3 时间序列数据库模型 2 3 1 专门数据库构建方法 时问序列数据库( t i m e s e r i e sd a t a b a s e ) 是一种专门数据库( s p e c i a l d a t a b a s e ) ，构建一个专门数据库可以有多种方法。可以是重新按照客户的情况 构建客户化数据库，可以是用一个数据库管理系统工具包或发生器( d b m s t o o l k i t g e n e r a t o r ) 或者在现有的普通关系数据库上重新组织数据( 参见图2 1 ) 。 客户层 工具包 发生器 存储层 客户层 普通关系 数据_ | 荦 ( a ) ( b )( c ) 嘲2 1 构建专门数据库的不同方法 地理信息系统g i s ( g e o g r a p h i ci n f o r m a t i o ns y s t e m ) 是以( a ) 方法构建的专门 数据库，g i s 依赖于特殊的数据结构，比如栅格数据，向量数据等，这些数据结 构不能存储在普通的数据库中。为了重新建立数据库，可以应用专门的存储机制 实现一个更加优化的系统。当然，这种方法花费很大，并且缺少现有d b m s 的 支持，比如，考虑到数据的并发控制和数据恢复等等。 方法( b ) ，数据库引擎用的是扩展数据库管理系统( e d b m s ：e x t e n s i b l e d b m s ) ，设计成工具包或发生器的形式。这样的e d b m s 通常是建立在存储层 上面的。这些t o o l k i t g e n e r a t o r 把d s m s 分成不同的几个模块，比如数据模块， 事务处理模块，查询语言模块和分布式模块。 应用t o o l k i t 方法我们只要重新实现部分的模块，其它的可以选择现有的 模块，并加以扩展或修改。这些t o o l k i t s 提供了数据库工程师所需要的数据库机 制，比如专门的程序语言和各种独立的库。当用到g e n e r a t o r 方法时，需要用公 布的语言( d e c l a r a t i v el a n g u a g e ) 详细漉明各模块。它的目标是对数据模型、事 务模型和完整性限制进行详细说明。 ( c ) 方法，也就是我们所要采用的方法，它是依赖于现有的完备的数据库 管理系统。我们只对研究领域所要用到的数据进行重新组织，以达到加快数据存 取的目的。也可以在数据存进数据库的同时，对数据进行相应的处理，并以指定 的形式存储。这对数据库知识发现效率有很大的作用。 2 3 2 时间序列数据库组织 数据库用于知识发现的组织是不周于操作型数据库。操作型数据太琐碎， 难以用于发现知识，因此需要体构汇总和汇集机制，并在不同的粒度级别上存储 和管理信息。普通数据库一般采用实体一关系( e r ) 模型，我们采用的模型跟 数据仓库中的模型一致：星型或雪花模型。 在进一步讨论为什么要用星型或雪花模型之前，我们要先来说明在知识发 现方法中常用到的一种数据：属性数据( a t t r i b u t e ) 。其实，我们在意义2 j 已经 用到了属性：数据库记录就是由一组属性组成。在知识发现算法中，可以利用现 有的属性数据，但是大部分的属性是需要重新计算和分析出来的，比如在某时间 点附近的数据波动和斜率等，我们都称为属性。 我们把属性分为两种：应用属性( a p p l i c a t i o na t t r i b u t e ) 和统计属性( s t a t i s t i c a l a t t r i b u t e ) 。应用属性是指与对象相关的一些特有的属性，它就是指一般关系数据 库中的各记录所包含的属性，是现有的。而统计属性是指为了算法需要而产生的 由统计方法计算出来的属性，比如：波动率、斜率。我们在后面还将用到各属性 的域( d o m a i n ) 。如果属性数据是连续的，还要将属性域划分为区问，称之为离 散化。区间的标号可以代替实际的数据值，很多算法( 如判定树) 对于属性值数 量的减小都有好处。 我们从上述分析中可以看出，一个时间序列是由静念属性( s t a t i ca t t r i b u t e ) 、 应用属性和各应用的统计属性组成( 如图2 2 ) 。 图2 2 时间序列数据组成 我们举个例子。假如有一个年降水量的时间序列数据库。有如下属性 1 、静态属性：地区名称，隶属气候带，地形地貌，森林覆盖率等等： 2 、应用属性：年最高、低温度，比去年降水量提高降低比率等等； 3 、统计属性：该点所属分段斜率，波动等等。 如果数据库以图2 2 的形式组成，每个表都将很庞大，并且由过多的冗余。 我们以星型模式( s t a rs c h e m a ) 来组织这样的多维数据( 我们经常把属性称为维) 。 组织后的结构如图2 3 所示。 静态属性表时序数据表应埘属性表 时间序列数据还存在一个数据粒度的问题，数据粒度越大，数据聚集的程 度越高，越表现整体的特征；反之，数据聚集程度越小，越表现数据的细节。这 体现在时间戳的单位上，如果时间戳的单位最小，没有比它更小单位的数据，则 粒度数据最小，如降水量以天为单位的数据是最细的数据，而以月份为单位的数 据则数据的粒度比以天来计算的数据粒度大。相应的应用属性和统计属性也要改 变，而且应用属性会变成统计属性。如最高气温将由该月的最高温度柬衡量。这 样就建立了多层的序列数据层次( 如图2 4 ) 。 静态属性表数据表l虑h j 属性表 幽2 3 多粒度的时序数据库组织 2 3 3 时间序列数据库一些定义 我们在进行时序数据属性形式化定义时，是以图2 2 的形式来说明的。因 为图2 3 只是它在数据库中的数据组织形式，两者在意义上是一致的。这些形式 化定义在后面将用到。 定义2 0 ，时间序列数据库中记录的第f 个属性是以时间函数的形式表达的： 口，( f ：) = a ，0 ，3 ，0 ( 2 1 ) 其中： 口：属性f ； r ，：数据库中的第_ ，个记录； f ，： 该记录的时间戳。 詹火2 - 彳? 时间间隔 ，。，f ：】内的特征是指属性函数a ，( ，) 可以被另外一个函 数庐( f ) 在相同时间段内所逼近。如： 口。( f ) 2q b ( t ) ，v t i t l ，t 2 】( 2 2 ) 显然，逼近有不同的方法，依据不同问题所要求的误差范围。如： 1 a i ( f ) 一( r ) i 2 0 0 0 ) ，宽裕( 1 2 0 0 2 0 0 0 ) ，普通( 8 0 0 1 2 0 0 ) ， 简朴( 4 0 0 8 0 0 ) ，寒酸( 4 0 0 ) ；也可以用底层的概念，如具体的数值表示( 如 图3 ，1 ) 。这说明离散化后的概念分层可以用来归约数据，尽管细节丢失了，但概 念化后的数据更有意义、更容易解释；在分析时所需要的内存空间比原数据少， i o 操作减少了，并且效率更高。 圈2 1 属性p r i c e 的一个概念分层 属性域的离散化由多种不同的方法，可以由用户或领域专家人工地离散化， 适合于人的概念。然而人工离散化是乏味的、耗时的任务。然而，许多概念化蕴 含在数据库中，并且可以在模式级定义，可以通过数据分句的统计分析动态地加 以离散化。这晕介绍一种直方图的分析方法。对于不同的情况在后面的章节还会 提到。 图3 1 给出了一个直方图，显示某给定数据集p r i c e d e 数据分稚。例如，频 率最高的消费大约在5 0 0 7 0 0 。可以使用划分规则定义值的范围。例如，在等 宽值方图中，将值划分成相等的部分或区间( 如：( 1 0 0 3 0 0 ) ，( 3 0 0 5 0 0 ) ，( 2 3 0 0 2 5 0 0 ) ) 。在等深值方图中，值被划分使得每一部分包括相同个 数的样本。值方图算法递归地用于每一部分。自动地产生多级概念分成，直到达 到预先设定地概念层数，过程终止。也可以对每一层使用最小区间长度来控制递 归过程。最小区间长度设定每层每部分地最小宽度，或每层每部分的最小数目。 幽3 1 显示p r i c e 属性值分布的直方图 3 2 3m i n m 结构 互信息网络结构模型如图3 2 所示。其组成部分描述如下： 1 ) 川一网络的层次数目。每个层与个输入属性相关，表示该属性与前面 层次的输入属性的交； 2 ) n o d e 。 z d 】一第f 层的第1 d 个节点： 3 ) 厶一第i 层节点集： 4 ) 足一目标属性i 的取不同值( _ ，；1 , 2 ，m ，) 的个数； 5 ) w ! 一第f 层的节点i d 与目标节点的连接权。 3 。2 4 舡的工作方式 不失一般性，这里在介绍m 甜m 工作方式时，构造的m i n m 多层网络结构 只显示一个目标属性4 。在实际应用中。对另外的目标属性也以同样的方法构 造( 步隳4 开始) 。 莎露：给定按照3 2 1 描述的数据集r ，及给定的属性域d 。把属性分成 候选属性集c 和目标属性集0 。这里的属性集不仅包含数据库中已有的属性， 还包括特征属性集( 见4 _ 3 2 特征属性提取) 。离散化每个属性域。 步錾黟2 ：设定一个互信息显著程度等级口( 缺省值：口= 0 9 5 ) ，用来判定 是否需要分裂网络中的节点，继续进行检测。控制网络的扩张。 步骤3 ：读取数据集r 数据记录。如果记录存在无效的属性值，或者属性 值丢失，要么用缺省属性值替代，要么忽略该记录。 其中 属性层1 ( 第1 个输 入属性：3 个 属性值) 属性层2 ( 第2 个输 入属性：3 个 属性值) 属性层陋i ( 第删个输 入属性：2 个 属性值) 幽3 2 m i n m 网络结构 步蓦窘4 ：对于每个目标属性a 。0 计算其先验熵日( 4 ) ： 目标属性层 ( 一个属性： 足个属性值) h ( a ) = 一尸( ) l o g p ( v q ) ：一珏。等 9 ) g ： 数据集r 中目标第i 个目标属性4 属性每的记录个数 ：数据集r 中所有记录的个数： 片c 一4 j ，。毒p c 口：， 芸今争l 。g 等 、 。， i - l，i j ，、 一鲥鲁嘲1 爿 一l 尸( 口：) 等o g 等f = 一姜等山s 等一 一警善 即小等t o s 鲁 。1 2 条件熵日( 彳，a ：) ( 七= l ，2 ，i 彳j 1 ) 。如果 h ( a 。a ：n o d e = p ( 玩) h ( a ，) 一善鬈眠, n o d e l , h ) l o g