（计算机应用技术专业论文）不确定时态信息表达模型的研究与应用.pdf

摘要 摘要 在研究不断变化着的现实世界时，时间是一个非常重要的因素。我们常以时 间为依据来解释各种事实和数据，因为各种事件和实体间的潜在关系常常蕴涵在 时态信息中。时态信息表达和时态推理问题涉及计算机科学、哲学、语言学等学 科，在计算机科学研究中，这是信息系统、人工智能和其它过程建模等领域的核 心问题。目前对时态信息处理的研究多集中于确定时态，然而在现实的许多情况 下，事件的时间往往很难精确判定，所以，建立一个能全面且方便地描述各类事 件的不确定时态信息、又具备一定时态推理能力的不确定时态信息表达模型，具 有十分重要的意义。同时，模型的表达方法还要有利于存储和索引不确定时态信 息，以使其能应用于数据库和数据挖掘等领域，发现有用的时态知识和规律。 本文是对不确定时态信息表达模型的理论和应用的研究。本文的研究始终以 不确定时态信息处理为主线，以不确定时态信息表达模型的建立和应用两部分为 主要内容，提出适于表示不确定时态信息的模型，并基于此模型提出针对不确定 时态信息的推理、索引、挖掘的新技术和新方法。本文的研究沿着此思路进行： ( 1 ) 仔细研究表示不确定时态信息的方法，提出统一的表达模型，分析模型的各类 性质和时态推理能力；( 2 ) 提出适合该模型的不确定时态索引方法，便于在数据库 系统中存储和处理不确定时态数据；( 3 ) 研究不确定时态信息表达模型的应用：在 不确定时态数据存储和索引的基础上，提出新的时态数据挖掘( 不确定时态关联规 则) 算法对时态数据进行挖掘，以发现有价值的时态知识。 本文在上述几个方面展开研究，主要的创新点如下： 1 提出了一个统一的时态信息表达模型，不仅可以表示确定和不确定时态信 息，而且还能描述定性和定量的时态关系。该模型定义了三种不确定时态元素( 时 间点、时区和时距) ，规定了各时态元素的定性关系和定量约束，并将三种时态元 素统一用于表示事件的时态性质。因此，该模型能描述各种类型的不确定时态信 息。在模型中，确定时态是不确定时态的一种特殊情况。 2 对不确定时态信息表达模型进行了理论分析。讨论了模型中各类时态关系 的传递性，并给出时态关系间的传递关系表，提出了利用该表解决时态约束满足 问题的方法；在模型上扩展了新的时态运算符，时态运算符的扩展使其能支持不 确定时态信息的处理，同时证明了扩展后的时态运算符满足运算封闭性和布尔运 算的基本性质。 3 提出了一种结合线性逻辑和时间p e t ri 网的不确定时态推理方法。根据线性 逻辑与时间p e t r i 网的内在类同性，将线性逻辑用于描述时间p e t r i 网结构，并将 两者结合用于表示不确定时态信息和时态关系，进行时态推理。主要解决了三个 问题：用基于线性逻辑的时间p e t r i 网表示不确定时态信息表达模型中的时态元素 华南理工大学博士学位论文 和时态关系；用基于线性逻辑的时间p e t r i 网模型定义了各种不确定时态推理规 则；提出了在时间p e t r i 网中运用推理规则进行不确定时态推理的方法。相关的定 理和例子表明了结合线性逻辑和时间p e t r i 网，在不确定时态信息表达模型上进 行定量和定性时态推理方法是可行且有效的。 4 提出并实现了一种基于r 牛树的不确定时态索引技术。改造了空间索引技术 中的r 木树索引技术，将其用于时态索引，并根据不确定时态数据的特征，对其进 行了优化，从而在索引时减少比较的次数，更加精确地获得搜索结果，提高了索 引的性能。另外，实现了一个基于聃树时态索引和关系数据库的原型系统，不仅 实现了索引架构的主要功能，还实现了索引的存储功能，保证了该原型系统能够 满足实际应用的需要。性能测试的结果表明，该原型系统不但在功能上得到了扩 展而支持不确定时态数据，而且在性能上也优于已有的时态索引技术。 5 提出了一种基于参考度的不确定时态关联规则挖掘算法。首先研究了关联规 则的评价标准，并根据现有评价标准存在的问题提出了一种新的评价标准“参考 度”，应用该标准的关联规则挖掘算法不仅能更有效筛选有价值的关联规则，而且 能挖掘负关联规则。提出了适于不确定时态数据的时区延展和归并算法，并在此 基础上提出了一种不确定时态关联规则挖掘算法，由于结合了“参考度”评价标 准，该算法能得到负时态关联规则。实验结果表明了该算法的良好性能。 6 根据本文研究的成果，设计并实现了一个时态数据挖掘系统，成功地将其 应用于肺癌预警的课题研究中。该系统可以存储和索引确定或不确定的时态数据， 实现了数据预处理、时态关联规则挖掘等算法，可以完成一个完整的时态数据挖 掘过程，包括时态数据储存索引、预处理、时态关联规则发现、结果评估、结果 展示等模块。该系统是本文提出的不确定时态信息表达模型和各种时态信息处理 方法的具体应用。结合医疗数据进行肺癌预警课题( 得到广东省重大科技攻关项目 a 1 0 2 0 1 0 3 和广州市科技攻关项目2 0 0 0 一j 一0 0 6 一0 1 的资助) 的研究结果表明了本文 提出的不确定时态信息表达模型和各种处理不确定时态信息方法的有效性和实用 价值。 关键词：不确定时态；时态表达；时态推理：时态索引；时态关联规则 中图法分类号：t p 3 9 1文献标识码：a i i a b s t r a c t t i m ei sav e r yi m p o r t a n tf a c t o rw h i l er e s e a r c h i n go nt h ec h a n g i n gw o r l d w e a l w a y se x p l a i n “1k i n d so fr e a l i t i e sa n dd a t ab yt i i n e ，b e c a u s et h ep o t e n t i a l r e l a t i o n s h i p sa m o n g e v e n t sa n de n t i t i e sa r eo f t e n i m p l i c a t e d i nt h e t e m p o r a l i n f o r m a t i o n t h ep r o b l e mo f r e p r e s e n t i n gt e m p o r a lk n o w l e d g e a n d t e m p o r a l r e a s o n i n ga r i s e si nw i d er a n g eo fd i s c i p l i n e s ，i n c l u d i n gc o m p u t e rs c i e n c e ，p h i l o s o p h y ， l i n g u i s t i c sa n de t c i nt h ef i e l do fc o m p u t e rs c i e n c e ，i ti sac o r e p i o b l e mi n i n f o r m a t i o ns y s t e m s ，a ia n do t h e ra r e a si n v o l v i n gp r o c e s sm o d e l i n g u pt on o w ，m o s t r e s e a r c h e so nt e m p o r a l i n f o r m a t i o nf o c u so nc e r t a i n t yt e m p o r a l i n f o r m a t i o n h o w e v e r i ti sh a r dt od e t e r m i n et h ep r e c i s et i m eo fe v e n t si nm o s tp r a c t i c a ls i t u a t i o n s i ti s n e c e s s a r yt ob u i l da nu n c e r t a i n t yt e m p o r a lr e p r e s e n t a t i o nm o d e l ，w h i c hc a nb eu s e dt o d e s c r i b eu n c e r t a i n t yt e m p o r a li n f o r m a t i o no fe v e n t sg e n e r a l l ya n dc o n v e n i e n t l y t h e m o d e ls h o u l dh a v et h ec a p a b i l i t yo ft e m p o r a lr e a s o n i n ga n db ep r o p i t i o u st ot e m p o r a l i n d e xa n dt e m p o r a ls t o r a g ef o r t h ea p p l i c a t i o n so nd a t a b a s ea n dd a t am i n i n g t h i sd i s s e r t a t i o ni sm er e s e a r c ha n da p p l i c a t i o no n u n c e r t a i n t yt e m p o r a l r e p r e s e n t a t i o nm o d e l t h i sd i s s e r t a t i o nf o c u s e so nu n c e r t a i n t yt e m p o r a ii n f o r m a t i o n m a n a g e m e n t ， r e s e a r c h e sa n da p p l i c a t i o n s i nt h i sd i s s e r t a t i o n ，as e r i e so fn o v e l c o n c e p t sa n da l g o r i t h m sf b rt e m p o r a lr e a s o n i n g ，i n d e xa n dd a t am i n i n gb a s e do nt h e p r o p o s e dt e m p o r a lm o d e la r ep r e s e n t e d t h ec o n t e n t so ft h i sd i s s e r t a t i o ni n c l u d e ：( 1 ) b a s e do nt h ea n a l y s i so ft e m p o r a li n f o r m a t i o nm a n a g e m e n t ，au n i f i e dt e m p o r a l r e p r e s e n t a t i o nm o d e li sp r e s e n t e d t h ep r o p e r t ya n dc a p a b i l i t yf o rt e m p o r a lr e a s o n i n g o ft h i sm o d e la r ea l s oa n a l y z e d ；( 2 ) a nu n c e r t a i n t yt e m p o r a li n d e xt e c h n o l o g yi s p r o p o s e d t h i sm e t h o dc a nb eu s e dt os t o r ea n di n d e xu n c e r t a i n t yt e m p o r a ld a t a ；( 3 ) t h e a p p l i c a t i o n s o f u n c e r t a i n t yt e n l p o r a lr e p r e s e n t a t i o n m o d e l ： b a s e do nt h e u n c e r t a i n t yt e m p o r a ld a t as t o r a g ea n di n d e x ，an e wt e m p o r a ld a t am i n i n g ( u n c e r t a i n t y t e m p o r a la s s o c i a t i o nr u l em i n i n g ) a l g o r i t h mi sp r e s e n t e df o rf i n d i n go u tt h ev a l u a b l e t e m p o r a lk n o w l e d g e t h em a i nw o r k so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 au n i f i e dt e m p o r a lr e p r e s e n t a t i o nm o d e li sp r o p o s e d ，w h i c hc a nb eu s e dt o r e p r e s e n tc e r t a i n t ya n du n c e r t a i n t yt e m p o r a li n f o r m a t i o n ，a n dd e s c r i b eq u a l i t a t i v ea n d q u a n t i t a t i v et e n l p o r a lr e l a t i o n s h i p s f i r s t l y ， t h r e e u n c e r t a i n t yt e m p o r a l e n t i t i e s ( t e m p o r a lp o i n t ，t e m p o r a li n t e r v a la n dt e m p o r a ld i s t a n c e ) a r ed e f i n e dt or e p r e s e n t t e m p o r a li n f o r m a t i o n o fe v e n t sa n dd e s c r i b ea l l“n d so f u n c e r t a i n t yt e m p o r a l i n f o r m a t i o n t h eq u a l i t a t i v ea n d q u a n t i t a t i v er e l a t i o n s h i p sa m o n gt h et e m p o r a l i 华南理工大学博士学位论文 e n t i t i e sa r ea l s od e f i n e d i nt h i sm o d e l ，c e r t a i n t yt e m p o r a l i n f o r m a t i o ni so n es p e c i f i c s i t u a t i o no fu n c e r t a i n t yo n e 2 b a s e do nt h er e s e a r c ho nt h et r a n s i t i v i t yo ft h et e m p o r a lr e l a t i o n s h i p sa m o n g t e m p o r a le n t i t i e s ，s e v e r a lt e n l p o r a lt r a n s i t i v i t yt a b l e sa r ep r o p o s e d t h e yc a n b eu s e d t os o l v e t e m p o r a l c o n s t r a i n ts a t i s f a c t i o n p r o b l e m n e wt e m p o r a lo p e r a t o r sa r e e x t e n d e dt os u p p o r tu n c e n a i nt e m p o r a lo p e r a t i o n s t h e s et e m p o r a lo p e r a t i o n sa r e p r o v e dt ob ec l o s e da n ds a t i s f yt h eb a s i cp r o p e r t i e so fb o o l e a no p e r a t i o n s 3 c o m b i n i n gw i t ht i m e dp e t r in e ta n dl i n e a rl o g i c ，a na l g o r i t h mf o ru n c e r t a i n t y t e m p o r a lr e a s o n i n gi sp r o p o s e d ，a c c o r d i n gt ot h ea n a l o g o u s n e s sb e t w e e nl i n e a rl o g i c a n dt i m e dp e t r in e t ，t h es t r u c t u r e so ft i m e dp e t r in e ta r ed e s c r i b e db y1 i n e a rl o g i c t h e ya r ea l s ou s e dt or e p r e s e n tu n c e r t a i n t yt e m p o r a li n f o 珊a t i o na n dr e l a t i o n s h i p s t h r e em a i np r o b l e m sa r es o l v e dh e r e ：u s i n gt i m e dp e t r in e tt or e p r e s e n tt e m p o r a l e n t i t j e sa n d1 e l a t i o n s h i p so fu n c e n a i n t yt e m p o r a lr e p r e s e n t a t i o nm o d e jb a s e do n l i n e a rl o g i c ；s o m eu n c e r t a i n t yt e m p o r a lr e a s o n i n gr u l e sa r ed e f i n e db yt i m e dp e t r i n e tb a s e do nl i n e a r1 0 9 i c ；am e t h o df o ru n c e n a i n t yt e m p o r a lr e a s o n i n gi sp r e s e n t e d w i t ht i m e dp e t r in e t f i n a l l y ，a ne x a l p l es h o w st h a tc o m b i n i n gw i t hl i n e a rl o g i ca n d t i m e dp e t r in e t ，t h eq u a n t i t a t i v ea n dq u a l i t a t i v et e m p o r a lr e a s o n i n gw i t hu n c e r t a i n t y t e m p o r a lr e p r e s e n t a t i o nm o d e la r ef 色a s i b l ea n de f f 色c t i v e 4 at e m p o r a li n d e xm e t h o db a s e do nr 8 一t r e ei sp r o p o s e d t h er 4 一t r e es p a t i a l i n d e xt e c h n o l o g yi sa d a p t e dt ot e m p o r a ld a t a a c c o r d i n gt 0t h ec h a r a c t e r i s t i c so f u n c e r t a i n t yt e m p o r a ld a t a ，t h en e wi n d e xi so p t i m i z e dt oi m p r o v et h ep e r f o r m a n c e a p r o t o t y p ew i t hr 木- t r e ei n d e xa n dr a t i o n a ld a t a b a s ei sb u i l tt os a t i s f yt h er e q u i r e m e n t o fa p p l i c a t i o n s p e r f o r m a n c et e s t sp r o v et h a tt h i s p r o t o t y p ee x c e l st h o s ee x i s t i n g s y s t e m sn o to n l yi nt h ef u n c t i o ne n h a n c e m e n tb u ta l s ot h ei n d e xp e r f o r m a n c e 5 an o v e lu n c e r t a i n t y t e m p o r a l a 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 mb a s e do n c o n s u l tm e a s u r ei sp r e s e n t e d f i r s t l y ，b a s e do nt h ea n a l y s i so fe x i s t i n ge v a l u a t i o n m e a s u r e s ，an e wm e a s u r en a m e dc o n s u l ti sp r o p o s e dt os c r e e no u tv a l u a b l er u l e s m o r ee f f e c t i v e l y t h ec o n s u l tm e a s u r ec a nb eu s e dt om i n en e g a t i v ea s s o c i a t i o nr u l e s b o t ht h en o v e im e t h o d sf o re x t e n d i n ga n dm e 蟾i n gu n c e r t a i n t yt e m p o r a ii n t e r v a l sa n d t h en e wd i s c o v e r ya l g o r i t h mf o rt e m p o r a la s s o c i a t i o nr u l e sa r ed e s i g n e d t h i sn e w a l g o r i t h mc a nm i n en e g a t i v et e m p o r a la s s o c i a t i o nr i l l e s ，f o r i ta d o p t st h ec o n s u l t m e a s u r e e x p e r i m e n t a lr e s u l t ss h o wt h ee m c i e n c yo ft h i sa p p r o a c h 6 b a s e do nt h ea c h i e v e m e n t sa b o v e ，at e m p o r a ld a t am i n i n gs y s t e mi sd e s i g n e d a n db u i l t i th a sb e e na p p l i e dt ot h er e s e a r c ho ns e a r c h i n gr j s kf a c t o r sf o rl u n gc a n c e r s u c c e s s f u l l y t h i ss y s t e mc a ns t o r eb o t hc e r t a i n t ya n du n c e r t a i n t yt e m p o r a ld a t a i t c o n t a i n st h ea l g o r i t h m sf o rd a t ap r e p r o c e s s i n g ，t e m p o r a la s s o c i a t i o nr u l em i n i n ga n d e t c aw h o l ed a t am i n i n gp r o c e s sc a nb ea c c o m p l i s h e dw i t ht h es y s t e m ，i n c l u d i n g t e m p o r a ld a t as t o r a g e ，p r e p r o c e s s i n g ， a s s o c i a t i o nr u l e sm i n i n g ，r e s u l te v a l u a t i o n ， r e s u l td e m o n s t r a t i o na n do t h e rm o d u l e s t h i ss y s t e mi st h ea p p l i c a t i o n so fu n c e r t a i n t y t e m p o r a lr e p r e s e n t a t i o nm o d e la n dt h en o v e lt e m p o r a li n f o r m a t i o nm a n a g e m e n t t e c h n o l o g i e sp r o p o s e da b o v e t h er e s e a r c hr e s u l t so ns e a r c h i n gr i s kf a c t o r sf o rl u n g c a n c e r ( s u p p o r t e db yg u a n g d o n gk e yt e c h n o l o g i e sr & dp r o g r a ma 1 0 2 0 1 0 3a n d g u a n g z h o uk e yt e c h n o l o g i e sr & dp r o g r a m2 0 0 0 一j 0 0 6 一0 1 ) s h o wt h ee f f e c t i v ea n d p r a c t i c a b i l i t yo ft h eu n c e r t a i n t yi n f o r m a t i o nm a n a g e m e n tt e c h n o l o g i e sp r e s e n t e di n “b j sd i s s e r t a t i o n k e y w o r d s ：u n c e r t a i n t yt e m p o r a l ； t e m p o r a lr e p r e s e n t a t i o n ；t e m p o r a lr e a s o n i n g ； t e m p o r a li n d e x ；t e m p o r a la s s o c i a t i o nr u l e v 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：旧瘫嘉f 盈日期：跏，年月9 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权华南理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于， 不保密哦 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 铆岳宜 叫k 日期：喇? 年6 月f 7 日 ， 日期：训蛑6 月厂7 日 第一章绪论 第一章绪论 1 1 引言 在研究不断变化着的现实世界时，时间是一个非常重要的因素。大量现实的 数据都带有时间特性。医疗、通信、经济等各个领域随处可见包含时态信息 ( t e m p o r a li n f o r m a t i o n ) 的数据，股市市场每日波动、产品动态加工过程、银行的 交易记录、w 曲页的访问日志、科学实验，这些都是比较常见的例子。我们常以 时间为依据来解释各种事实和数据，因为各种事件和实体间的潜在关系常常蕴涵 在时态信息中。事件在特定的时间发生，事件与事件的关系也存在于特定的时间 内。对这些时态信息进行分析，从中获取蕴涵的系统演化规律，预测系统的变化 和系统对外来行为的反应，具有重要的价值和意义。在许多基于知识的问题求解 过程中，时态是一个极为重要的概念，如规划、预测与决策、诊断、自然语言理 解、程序正确性证明及并行计算等。 虽然在哲学上，人们对于时间本质等问题( 如时间是否有界、是离散还是连续 的) 的理解有很多争议和矛盾，可是在日常生活中，人们并没有因此而导致疑惑， 相反，很多事情恰恰需要引入时间才能清楚地描述。人类很早就有认知时间的能 力，我们能意识到周围世界的变化并且探求变化的规律。作为一个基本的元素， 时间在变化和行为的推理过程起着重要的作用。当我们说某个事物变化了的时候， 我们其实是指该事物所处的状态或条件变化了，而事物的这些不同状态或条件变 化正是通过时态( t e m p o r a l ) 关系联系起来的。对时间的多种不同观点，导致了时 态信息表达和应用等方面的研究存在多种出发点和观点，有着不同的适用领域。 时态信息表达和时态推理问题涉及到计算机科学、哲学、语言学等学科。而 在计算机科学研究中，这是信息系统、人工智能和其它过程建模等领域的核心问 题。例如在人工智能的规划问题中，给定某时刻的世界状态描述和一系列动作 ( a c t i o n ) ，规划者要设计一组动作序列，使得世界能从初始状态变迁到目标状态， 如移动积木、绕开障碍等。在整个规划过程中，规划者就需要一些基于时间的信 息表达方法，在此之上进行推理，从而得到解决问题的方案。 总之，时间在我们的现实生活中扮演着一个十分重要的角色，对推理、信息 处理、知识发现等的研究不可避免要涉及到时态信息。本文是对时态信息处理方 法的研究，着重于研究不确定时态信息表达模型的理论和应用。本章的内容安排 如下：1 2 节介绍时态信息研究的背景及意义；1 3 节介绍时态信息研究相关理论， 包括现有的各种理论和方法的国内外现状；1 4 介绍本课题的研究思路及主要研 究工作。 华南理工大学博士学位论文 1 2 时态信息研究的背景及意义 在计算机学科中，时态信息的表达、时态推理方法和技术【l ，2 】一直是人工智能 领域研究的热点，也是时态数据库研究中的基本问题。日益广泛的数据库应用不 仅要求管理事件的历史性信息。还需要管理系统中元事件的时态信息，因此需要 迫切解决两个问题：一是管理事件的历史性信息，从中探寻事物发展的本质规律； 二是管理数据库系统中元事件的时态信息，如增删、查改的时刻和时间区间，这 些数据有助于提高数据库系统的可靠性和效率。二十世纪九十年代兴起的数据挖 掘研究，也逐渐融合了有关时态信息表达的方法，形成了面向时态数据的时态数 据挖掘研究热点。相对时态数据库，时态数据挖掘注重于从时态数据中提取时态 模式。 在这些研究和应用中，时态信息表达模型的建立十分关键。时态模型不仅要 能全面且方便的描述各类事件的时态信息，具有一定的时态推理能力，而且还要 有利于存储和索引时态信息，以使其能作为数据库和数据挖掘应用的基础，便于 发现有用的时态知识和规律。也就是说，以时态数据存储和索引为基础，建立一 个既有一定时态推理能力、又能应用于时态数据库和时态挖掘的时态信息表达模 型，具有重要的意义。 在实践中，由于时间是现实世界事物本身固有的因素，所以在数据中常常存 在时态语义。这些时态数据的出现使我们有必要在知识发现过程中考虑时间因素。 现实世界中存在着多种类型的时态数据，这些类型还将因不同的具体应用而进一 步多样化。描述现实世界数据的时态语义对时态信息模型的建立特别有用。现实 世界数据库中常见的几种典型时态数据有【4 】： ( 1 ) 快照数据( s n a p s h o td a t a ) 。数据的当前值，表示数据集在某一个时刻 的状态，其中可能包括用户定义的时态值，如日期字段等等。 ( 2 ) 交易数据( t r a n s a c ti o nd a t a ) 。具有时间标记的交易记录的集合，其中 所有交易都是独立的，如超市中销售交易数据。 ( 3 ) 交易数据序列( s e r ia it r a n s a c t io nd a t a ) 。具有时间标记的交易记录 的集合，其中一个或多个交易与某个特别的实体相关，如超市中某位顾客的交易 序列，病员的医疗检查数据序列。 ( 4 ) 时间序列数据( t i m es e r i e sd a t a ) 。在某段时间内连续记录的某属性值 序列。例如气象、水文数据。 ( 5 ) 时间片数据( t i m es i i c e0 a t a ) 。表达在某时间点的模型化实体状态的 一个或多个数据集( s l i c e ) 。这种数据机制在片与片之间也可能是不同的，例如在 1 5 年期间的3 个时间点所获得的民意调查数据。 ( 6 ) 时间立方数据( t i m ec u b i cd a t a ) 。在数据库或模型化实体历史中的任 2 第一章绪论 意给定时间点上的若干数据属性值的实况表达，即既有数据输入数据库的时间， 又有其在现实世界中相应的时间值，例如时态数据库。 以上这些是在数据库应用中常见的时态数据，现实中还有很多非数据库的时 态数据和时态事件，如工作流、作业调度等过程产生的数据。因此，时态信息的 表达、时态推理和时态挖掘方法不能只立足于时态数据库中的数据，而要具备一 定的通用性，能描述现实生活中各种事件之间的时态约束和时态关系。尽管近年 来有关时态数据库的研究有了很大进展5 ，6 1 ，也有很多应用性方面的报道文献n 8 1 ， 然而现在还没有一个真正完善的时态数据库产品。所以，在时态知识发现的过程 中，时态数据库并不是必要的，时态规则是可以在一些静态数据集序列中挖掘出 来的2 1 。 对现实世界中的大量时态数据进行研究的主要目的是为了发现蕴涵在数据中 的有价值的时态知识。一般来说，我们期望利用时态模型和推理、挖掘等方法从 数据中发现以下几种主要类型的时态知识【4 】。 ( 1 ) 时态关联。时态关联是事件之间在时间上的次序和关系，如某事件在时 间上紧随着另一事件发生，某事件和另一事件重叠发生。虽然两事件发生时间的 先后并不意味着两者存在因果关系，但是作为一种关联关系仍然是值得关注的时 态知识。某些情况下，事件序列中的事件存在着一定的前提后继关系，或者一些 事件会自然地同时发生，这些都是在时态推理中需要注意并且力求发现的。对于 时态数据挖掘来说，从事件的时态关联可以探测行为模式，比如顾客在不同时间 的购物行为关联。 ( 2 ) 时态约束。相关事件之间往往存在着许多约束条件，事件在时间上的相 互制约关系称为时态约束。由于时间本身的特点，当某个约束条件加到事件的时 态关系上中时，会对其它的时态关系产生影响，通常称为时态约束传播( t e p o r a l c o n s t r a i n tp r o p a g a t i o n ) 。由于约束传播现象，因此存在时态推理的问题f 9 】。例 如在时间规划问题中，事件各种时间约束都是从不同角度引入的，它们之间不可 能都能保证是一致的，事件集中不同事件间的时态约束关系可能会产生矛盾。如 何检测事件之间关系一致性，或者在多种可能关系中寻找满足一致性的解是一个 n p 完全问题【”。在解决时态约束满足问题方面比较著名的是r d e c h t e r ，i m e i r i 和j p e a r l 提出的时态限制网模型【1 0 】，近年来还有一些更深入的研究 。对于 时态数据挖掘来说，时态约束主要体现在规则的时态语义上。在现实中，附加上 某种时态约束的规则可以更好地描述规则的时效性，因而更有价值。这种时态约 束可以表明规则何时变得合法，何时又被认为非法，也可以表明目前已知非法的 规则在过去或者将来是否合法，对决策支持来说，带有时态约束的规则是十分有 价值的。 ( 3 ) 因果关系。之所以把因果关系单独列出来，是因为因果关系研究是在时 3 华南理工大学博士学位论文 态知识发现中得到最广泛研究和应用的课题之一【1 2 ，3 】，在数据集中发现因果关系 是时态数据挖掘的固有问题。因果关系在医学领域特别有用，医学人员经常要探 寻导致某一疾病或病症的原因。值得注意的是，因果关系要求要有被考察是正确 的实在证据，因而数据挖掘工具主要用于探测原始因果关系规则，所发现的规则 随后还要进行充分的测试和检验【4 j 。 ( 4 ) 周期和趋势。事件变化的周期或趋势规律的发现可以对未来进行预测， 指导决策工作。事件某些性质随时间变化的模式有时会呈现一定的周期性，即周 期模式，如季节、潮汐和每日交通流量模式等都具有一定的周期性。这些周期性 并非严格的数学意义上的周期现象，它们可能在时间上发生了不规则的伸缩，在 幅度上迭加了干扰信号。有关时间序列的周期模式发现和趋势预测的研究【1 4 1 5 1 已 经有很多，也有比较成熟的技术和理论，包括序列数据的表达、序列相似性的定 义和针对具体挖掘问题的应用，而在离散时态数据方面( 如交易数据) 的周期和趋 势研究却比较少见。 相对于数据挖掘较成熟的部分而言( 如分类、关联挖掘) ，时态数据挖掘的研 究是数据挖掘发展的一个较新方向。目前在国际上，时态数据挖掘的研究正逐渐 成为一个新的热点，国外的研究重点在于逐步将人工智能中有关时态信息表达和 逻辑推理方面的理论用于时态数据挖掘中，国内在这方面的研究文献比较重要的 有1 9 9 8 年欧阳为民等【”、2 0 0 2 年张保稳等 1 6 1 从理论框架的角度对时态数据挖掘 做的介绍和分析。然而，目前对时态信息处理的研究多建立在确定时态的基础上， 在现实中的许多情况下，事件的时间往往很难精确判定。我们常常无法很明确地 知道事件发生的时间，只知道事件大概是什么时候发生的。例如，我们大概知道 这件事情发生在“下午2 点到4 点之间”、“上周的某个时间”、“大概在四月 的中旬”。一般来说，不确定时态信息的产生主要有以下几种原因 ”】。 ( 1 ) 时间粒度。在大多数情况下，记录数据时间的粒度跟事件发生的确切时 间粒度不一致。比如一个事件发生在某秒内，然而由于系统的时间粒度只是精确 到天，所以最终在系统中该事件发生的时间是以天作为标记。 ( 2 ) 时间测定技术。许多时间测定技术本身就不精确，导致测出的时间数据 有误差，例如采用c a r b o n 一1 4 来测定时间。 ( 3 ) 未来计划时间。项目计划完成的时间往往都是不确定的。例如，这个项 目将会在三到六个月之后完成。 ( 4 ) 未知或不精确的事件时间。一般来说，事件发生时间可以是未知或者不 精确的。例如，假设我们不知道某人出生的时间，那么在数据库中，该人的出生 时间就会被记录为未知( 出生时间是从时间开始到现在之间) 或不精确( 出生时间 是从1 5 0 年前到现在之间) 。 由于不确定时态信息的广泛存在，时态数据库管理系统有必要支持不确定时 4 第一章绪论 间。然而，表示不确定时间信息，是时态数据库中目前仍缺少的一个重要的功能， 这一缺陷极大地约束了时态数据库的应用范围，影响了时态数据库的进一步推广。 因此，如何表示不确定时态信息，是进行更深层次的时态推理和完善时态数据库 的一个重要前提条件，在以往的研究中，已经有人提出了一些表示不确定时态信 息的方法f 1 引，但是没有能够提出一个较统一的模型，也没能在实现层面上支持这 些表示方法，所以，这些方法依然无法得到进一步的实际应用。 因此，建立一个适应时态推理、时态数据库存储和索引、时态数据挖掘等应 用需要的统一的不确定时态信息表达模型，将有助于时态信息研究工作的进一步 开展。由于支持不确定时态，这样的模型也更贴近于现实世界的时态数据，又由 于支持了推理、存储索引和挖掘方法，能方便地扩展各类应用。所以，对统一的 不确定时态信息表达模型和应用进行研究和探讨，具有十分重要的意义。 1 3 时态信息研究相关理论 不确定时态信息的表达方法会影响到时态推理、时态数据存储索引和时态数 据挖掘等方面。目前这几个方面的研究大多基于确定时态，虽然已有一定的研究 和应用成果，但各个方面的研究仍然比较独立，没有较好的统一起来。因此，新 的