（数量经济学专业论文）时态数据挖掘及其应用.pdf

内容摘要 时态数据挖掘中，由于数据对象不仅规模庞大而且内容复杂，研究重点一直都放在 方法的可行性上，已有的挖掘方法大多限于如何挖掘出数据内部规律的表现特征，鲜有 关于如何挖掘出数据本质规律的论著。经过查阅大量国内外文献，作者发现时态数据挖 掘领域的研究尚处于起步阶段。为改变这一现状，提高时态数据挖掘的效率和效果，本 文进行了一系列的研究工作。主要的创新可归结为以下几点。 首先，创新地提出了持续事件序列的概念，建立了规范统一的时态数据格式，完全 保留了时态数据内在的时域结构。与已有研究不同，持续事件具有两个显著特点：( 1 ) 事件的发生并非瞬间完成，而是在一定的时间段内保持发生状态；( 2 ) 以个体为基本单 位，并将相关的指标作为条件事件集一并记录。 其次，本文提出了一系列的时态数据挖掘方法。在规则挖掘中，本文重新整合了数 据挖掘中的关联规则的定义，进一步提出了时态规则挖掘，使其能够适应时域特征更为 复杂的时态数据；在聚类分析中，利用粗糙集理论的“等价关系”概念，创新地提出高维 数据的粗糙集聚类方法，完全避免了高维数据聚类中的维数灾问题；而在模型挖掘中， 借鉴风险模型的建模思想，提出了时态数据的模型化挖掘技术，使数据挖掘具备了捕捉 时态数据内在规律的能力。 最后，本文还对这三类时态数据挖掘方法分别进行了实例分析。对于手机用户的月 度消费数据，我们分别进行了时态规则挖掘和粗糙集聚类两类最主要的挖掘方法；上市 公司s t 事件的时态数据合并了2 0 0 0 年至2 0 0 5 年间的所有中国a 股股票的财务报表和 市场表现。尽管所涉及的数据规模较大，本文利用模型挖掘，仍然成功的完成了挖掘任 务。 本文所得的主要结论有：( 1 ) 在现阶段，时态数据挖掘可以完全采用本文提出的持 续事件序列格式进行表示。持续事件序列为时态数据挖掘提供了一个统一规范的数据对 象格式，不仅有利于方法论研究，更有利于算法设计和比较；( 2 ) 时态规则挖掘显著优 内容摘要 于静态规则挖掘。这主要是因为时态规则可以提取出事务在时域上的顺序和并发关系， 而静态规则挖掘却不能；( 3 ) 粗糙集的等价关系从知识分类的观点给出了一种全新的类 的定义，借鉴这一观点，本文提出的粗糙集聚类方法可以高效率的完成高维数据分类分 析任务，实例分析的结果也同样很有说服力。( 4 ) 对于具有复杂内容的时态数据，模型 挖掘的优势非常明显，并且模型挖掘的提出极大地开拓了复杂数据挖掘的研究思路。 关键词；时态数据；时态规则挖掘；粗糙集；模型挖掘 a b s t r a c t d u et ot h el a r g es c a l ea n dc o m p o u n dc o n t e n t so fm o d e r nt e m p o r a ld a t a b a s e ，c o n c e r n i n gm o r eo nt h ef l e x i b i l i t yo f t h em i n i n gt o o l s ，m o s tr e c e n tm i n i n gt o o l sa r es a t i s f i e d w i t hs o m ee x p e r i e n t i a lr e s u l t s n o tg o i n gt ou n v e i lt h er u l e sb e h i n dt h e s er e s u l t s a f t e r s u r v e y i n go v e ri n t e r n a t i o n a la n dn a t i o n a lr e s e a r c h e s ，if i n dt e m p o r a ld a t am i n i n gi sj u s t a tt h ep r i m a r ys t a g ei no r d e rt oi m p r o v et h ea c c u r a c ya n dr e l i a n c eo fm i n i n gt e c h n i q u e s ih a v ed o n e1 0 t so fr e s e a r c h e s a n dt h em a i ni n n o v a t i o n sa r el i s t e da sf o l l o w s f i r s t l y ，t h i sd i s s e r t a t i o ni n i t i a t et h ec o n c e p t i o no fd u r a t i v ee v e n ts e r i e s ，a n db u i l d af o r m a lf r a m e w o r kf o rt h et e m p o r a ld a t a ，b yw h i c ht h et i m es t r u c t u r ea r ek e p ti n t a c t d u r a t i v ee v e n ts e r i e sh a st w oc r u c i a la t t r i b u t e s ：( 1 ) e v e n tm u s tn o tf i n i s hi n s t a n t a n e o u s l y b u tk e e ph a p p e n i n gs t a t u si nac e r t a i nt i m es p a n ；( 2 ) t h ei n d i v i d u a li st h eb a s i cu n i ti n d n r a t i v ee v e n ts e r i e s ，a n dr e l a t i v ev a r i a b l e sa r er e c o r d e da sa d d i t i o n a li n f o r m a t i o n s e c o n d l y ，t h i sd i s s e r t a t i o na d v a n c e das o r to fm i n i n gt o o l sf o rt e m p o r a ld a t a i n r u l em i n i n g ，w er e i n t e g r a t et h ec o n c e p t i o no fa s s o c i a t i o nr u l e ，a n dp r o p o s eo n ek i n d o ft e m p o r a lr u l em i n i n gt o o l s ；i nc l u s t e r i n ga n a l y s i s ，w ei n v i t et h ei d e n t i t yr e l a t i o n s h i p f r o mr o u g h s e tt h e o r y ，a n da d v a n c eac r e a t i v ec l u s t e r i n gt e c h n i q u e ，w h i c hi sv o i do ft h e p r o b l e mo fc u r s eo fd i m e n s i o n a l i t y ；a n di nm o d e lm i n i n g ，u n d e rt h em i n do fh a z a r d m o d e l ，am o d e lm i n i n gt e c h n i q u ei sd e v e l o p e df o rf u r t h e rr e s e a r c h f i n a l l y ，w ea c c o m p l i s h e dt h r e er e a ld a t aa n a l y s e s b a s e do nt h ec e l lp h o n ec o n s u m p t i o nd a t a s e t w ec o n d u c tt e m p o r a lr u l i n gn f i n i n ga n dr o u g h s e tc l u s t e r i n g ；a n do nt h e c o m p o u n dd a t a b a s eo fs te v e n t so fa s h a r el i s t e dc o m p a n yo fc h i n as t o c k ，c o n s i s t i n go f 2 0 0 0 2 0 0 5y e a r l yf i n a n c i a lr e p o r t sa n dc o n t e m p o r a n e o u sm a r k e tp e r f o r m a n c e s ，t h em o d e l m i n i n gb r o u g h tu pi nt h i sd i s s e r t a t i o nc o m p l e t e st h ea n a l y s i st a s ke f f i c i e n t l y m a i nr e s u l t sa r ec o n c l u d e da sf o l l o w e d ( 1 ) d u r a t i v ee v e n ts e r i e si s c u r r e n t l yt h e b e s td a t af o r m a tf o rt e m p o r a ld a t am i n i n g ，w h i c hs u p p o r t sau n i f i e dd a t ap l a t f o r mf o r b o t hm e t h o d o l o g i c a lr e s e a r c ha n da l g o r i t h md e s i g n m e n ta n dc o m p a r i s o n ；( 2 ) t e m p o r a l r u l em i n i n ge c l i p s e ss t a t i cr u l em i n i n g ，f o ri tc a ne x t r a c tt h es e q u e n t i a lr e l a t i o na n dp a r - a l l e lr e l a t i o na m o n gt r a n s a c t i o n s ；( 3 ) f r o mt h ev i e wo fk n o w l e d g ec l a s s i f i c a t i o n ，i d e n t i t y r e l a t i o n s h i pg i v e su san e w d e f i n i t i o no fc l u s t e r ，w h i c hc o n t r i b u t e st ot h ei d e ao fr o u g h s e t c l u s t e r i n gi nh i g hd i m e n s i o n a ld a t a b a s e ；( 4 ) a st ot e m p o r a ld a t ac o m p o s e do fc o m p o u n d c o n t e n t s ，m o d e lm i n i n ge x c e l sa n yo t h e rm i n i n gt o o l s ，a n da l s oi l l u m i n a t e st h ei d e ao f c o m p o u n dt e m p o r a ld a t am i n i n g k e y w o r d s ：t e m p o r a ld a t a ；t e m p o r a lr u l em i n i n g ；r o u g h s e tt h e o r y ；m o d e lm i n i n g 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人 在论文写作中参考的其他个人或集体的研究成果，均在文中以明确方式标 明。本人依法享有和承担由此论文产生的权利和责任。 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有 权保留并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查 阅，有权将学位论文的内容编入有关数据库进行检索，有权将学位论文的 标题和摘要汇编出版。保密的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在 年解密后适用本授权书。 2 、不保密( “ ( 请在以上相应括号内打“，) 作者签名：汞叶竭 导师签名： 日期：) 一6 年妒月j 日 日期： 年月同 第一章引论 本章主要介绍了时态数据挖掘、时态数据的类型等基本概念，以及时态数据挖掘的 缘起和发展。由此总结归纳了时态数据挖掘存在的三个主要问题，并明确指出了本文的 研究目的。 第一节问题的背景 一时态数据挖掘的产生 信息技术的发展极大的提高了人们产生、搜集和存储数据的能力。从企业、科研机 构到政府部门，从金融行业、零售行业到机械制造行业，从通讯、医疗到保险，社会各 个部门、经济系统和专业领域每时每刻都在生产和累积大量数据。面对着浩如沿海的数 据，人们如何才能不被数据海洋所淹没? 如何才能从中发现有用的信息，并形成可供数据 使用者进行管理或决策时的知识? 在这种“数据爆炸，知识贫乏”的困境中，数据挖掘 ( d a t am i n i n g ) 技术应运而生，并迅速发展成为一门新兴的交叉学科，包括了统计学、机 器学习、人工智能以及模式识别等在内的自然科学领域的最新研究成果。 数据挖掘的根本任务就是发现数据的表现特征、内在规律以及产生机制，并用于指 导和辅助用户做出正确的决策和管理行为【1 ，2 | 。由于数据挖掘并不限定其研究对象的具 体形式，无论是事务性数据、时间序列数据、网站访问日志数据或是地理信息数据、生命 科学研究数据等，都可以进行数据挖掘。但这并不是说数据挖掘就是万能的，而是说由 于其研究对象的广泛性使得数据挖掘这一方法论学科也必须要广泛的吸收和借鉴相关领 域的专业理论和研究方法，并根据实际情况加以适当的修正或改进。 数据挖掘中，与时间有关的数据统称为时态数据( t e m p o r a ld a t a ) 。由于时态数据越 来越普及，可以预见，时态数据挖掘( t e m p o r a ld a t am i n i n g ) 将会是今后数据挖掘发展的 一个非常自然而又十分重要的方向( 3 3 。当前，时态数据挖掘主要可以分为时态模式挖掘 和相似性研究两个部分。其中的时态模式挖掘包含了序列模式挖掘、规则挖掘等；而相 似性研究主要是以非结构化数据库的查询语言设计为主。 一l 一 时态数据挖掘及其应用 二时态数据的主要类型 在已有的研究中，根据基本元素的特点可将时态数据分为时间序列、事务序列和事 件序列三类 4 】。狭义的时间序列中的基本元素是数值型变量的观测值，如股价的历史 数据。而广义上的时间序列指任何按时间排列的数据集；事务序列中的基本元素是事务 f t r a n s a c t i o n ) ，例如某客户在某段时间内在超市所购买的商品记录序列；而事件序列的 事件( e v e n t ) 是基本元素，例如网络通信的故障发生等。 其中，事件序列( e v e n ts e r i e s ) 是一类非常重要的时态数据。最初是采用时态关联规 则( t e m p o r a la s s o c i a t i o nr u l e ) 加以研究的m 】，而m a n n i l a ，h 等( 1 9 9 5 ) 的研究【7 8 j 可 以认为是事件序列挖掘的开始。文中把每一类通讯故障的发生都作为不同的瞬间完成的 离散点事件，将这类事件的时序记录称为事件序列( s e q u e n c e ) ，在此基础之上进行序列 模式( s e q u e n c ep a t t e r n ) 挖掘。该研究的创新之处在于充分考虑了不同事件之间的时间 间隔，将事件序列定义为三类：顺序型、并发型以及混合型，并在指定的滑动时间框内 寻找频繁模式( f r e q u e n tp a t t e r n ) 。v i l l a f a n e ：r 等( 2 0 0 0 ) 认为除了应该考虑事件之间 的时间间隔之外，还应该考虑事件发生时所持续的时间长度【9 1 。c h a n g ，y 等( 2 0 0 2 ) 还 在事务性数据库中，增加了项目的展示时间( e x h i b i t i o np e r i o d ) 因素，并提出了相应的时 态关联规则挖掘算法 1 0 】。而对于传统的时间序列问题，事件序列的一般方法就是将其 离散化为不同的符号事件( 1 l 】，在此基础之上进行事件序列的挖掘。 事件序列为时态数据挖掘提供了一个全新的思路，将原本结构复杂的时态数据简化 为有限个事件组成的序列，把对复杂数据规律的分析转化为事件序列的频繁模式挖掘。 这种转化不仅极大的简化了分析难度，也有利于各种规则挖掘算法的设计和实现。因此 在现阶段，就数据对象的角度而言，事件序列挖掘完全等同于时态数据挖掘。 三存在的问题 但事件序列挖掘的研究才刚开始，相关的研究也并不成体系，我们在已查阅的文献 中总结出了以下几个方面的问题： 第一，数据格式混乱。事件序列是从静态数据中发展出来的一种动态数据，由于其 一2 一 第一章引论 来源的广泛性，导致了事件序列的形式多种多样。例如连续观测的事务数据 7 、传统的 时间序列【1 2 】等都被称为时态数据。 第二，事件的定义不统一。例如m a n n i l a ，1 4 等( 1 9 9 5 ) 的研究【7 】中，笼统地将所有可 能有关的变量观测值异常都定义为事件，基本没有考虑事件之间的相关性和因果关系。 而在时间序列的研究中m ，观测值被区间化为不同的符号事件，这种符号化本身就带 有一定的主观性，同时时间序列微观的结构信息也被丢失。因此仅能作为宏观上的趋势 分析，而无法进行高频时序挖掘。 第三，研究方法不成体系。这一领域自m a n n i l a ，h 的开创性研究m 】以来，迄今 仍处于起步阶段。研究方法也基本可以分为“改造旧方法”和“创立新方法”两大类。 具体而言，改造旧方法比较容易，其主要思想就是先分解出事件序列的时间特征，然后 再套用旧方法m ，”_ ”_ 1 “。显然时间特征的识别和分解技术是关键，争议也最多；而后 者主要借鉴模式识别领域的技术方法，但由于时态数据的时域特征极其复杂而难以被捕 捉，所得结果不够理想 7 - 9 , 1 1 , 1 2 。 第二节研究的目的 选择一个全新的领域为题进行研究是一犹冒险，但也可能取碍突破性的进展。为改 变时态数据挖掘的研究现状，提高时态数据挖掘的效率和效果。在反复思考后，作者为这 一领域的理论生命力和实用前景所激励并决定就以此为题，结合自己所学的专业知识， 尝试在这一全新而又充满挑战的领域的基础性研究中做出一点贡献。 本文以下部分的结构和内容为：第二章给出持续事件序列的定义，并详细的分析和 讨论了常见的三种持续事件序列。第三章和第四章分别介绍了关联规则挖掘和时态数据 的规则挖掘，第五章用实例验证了时态规则挖掘的效果和实用性；第六章提出时态数据 的粗糙集聚类，成功的避免了高维聚类中的维数灾问题，实证的结果也相当令人满意； 第七章引入风险模型，作为时态数据模型化的理论基础，并在第八章成功地对上市公司 s t 事件的时态数据进行了模型挖掘。 3 第二章持续事件序列 本章提出了持续事件序列的定义，并将三类主要的时态数据格式归入持续事件序列。 本章认为，就目前而言，持续事件序列完全可以作为规范统一的时态数据的数据对象格 式。最后从事件持续性、个体差异性和事件定义等方面对持续事件序列和三类时态数据 格式进行了横向比较。 第一节时态数据 时态数据( t e m p o r a ld a t a ) 的兴起与发展，一方面是因为数据存储自身的特点。数据 存储方式主要有时间和空间两种：时间方式存储，就是在时间域上的观测数据的累积， 其最大的特点就是每个观测记录都有一个时间标记且具有时间顺序，如股票价格数据； 空间方式存储就是指增加个体的空间位置数据，这类数据主要集中在地理科学研究中， 因超出本文论述范围，故不讨论。 另一方面是应用领域对于数据挖掘要求的提高。以往的数据挖掘仅研究某一时点上 的静态数据并关注如何挖掘出有效的整体信息，这就忽略了个体差异性。现在越来越多 的行业都要求数据挖掘能够提供有关个体行为的特征和规律，以直接用于管理和决策。 这就要求以个体为基本单位进行挖掘，为了有效识别出个体行为就需要对个体在时间维 度上进行足够多次的观测。这样时态数据挖掘开始成为一个极富有生命力的研究热点。 时态数据，泛指一切按照时间顺序排列的数据集合。按照已有研究中时态数据的具 体形式可将时态数据分为时间序列、事务序列和事件序列三类。 一时问序列 时间序列的基本元素是数值型时序变量的观测值，转化为事件序列后具有式( 2 1 ) 的 格式， = i t t )( 2 1 ) 其中t 表示有序的时间标签集，e 表示事件集。现以单维时间序列为例说明如何将其 5 时态数据挖掘及其应用 转化为事件序列例如股票的每个收盘价( c p ) 都有唯一的日期( 表2 1 ) ，可根据研究目 的用不同的基本时问单位分割时间维o ，如季度、月份和同等。 表2 1 ：股价的历史数据 s t k c dd a t ec p q t r n 3 0 n w e e k d a y r e t u r nr e a e v e l 0 0 0 0 0 12 0 0 3 1 2 1 0 0 31 14 0 0 0 0 0 l2 0 0 3 1 - 31 00 2115。00 9 9 8d 0 0 0 0 0 12 0 0 3 一l 一61 0 0 6l1l0 3 9 8 4c 0 0 0 0 0 1 2 0 0 3 1 71 00 4112 0 1 9 9 0 e 0 0 0 0 0 12 0 0 3 1 81 0 5 31134 7 6 5 1a 0 0 0 0 0 12 0 0 3 2 1 01 1 3 112100 2 7 9d 0 0 0 0 0 1 2 0 0 3 2 ，1 11 1 3 8122 0 0 0 6 2 c 0 0 0 0 0 12 0 0 3 2 ，1 21 1 4 21230 0 0 3 5c 0 0 0 0 0 1 2 0 0 3 2 ，1 31 1 2 4i24 0 0 1 5 9d 0 0 0 0 0 12 0 0 3 2 ，1 41 1 3 312500 0 8 0c 转化为过程中先要对时间序列的目标观测值离散化，例如要得到对数日收益率( r e - t u r n ) ，可先按阈值( 一2 ，一1 ，0 ，1 ，2 ) 依次分为等级f 至a 六个等级( r e a e v e l ) 。 所以对数日收益率的事件序列为 ， ，一， ，- 一) 二事务序列 事务序列的基本元素是事务( t r a n s a c t i o n ) 。事务序列沿用了事务数据库的定义，只 是将商品项是否购买当做事件。事务序列具有式( 2 2 ) 的格式，c i d 为客户代码集，t i d 为对应客户的事务标签集，7 为时间标签集，_ e 为赡物事件集。 = i i c i d j t i d ( i )( 2 2 ) 其中，t i d ( 2 ) = j l j = 1 ，2 ，l t i d ( i i 表示第i 个客户所发生的事务标签集。为了使事 务序列的格式更精练，我们约定在同一个时间标签上只能发生一个事务。这就相当于假 定在给定的单位时刻只进行一次观测，在观测间隔中发生的多次事务将被累加到观测点 。有些文献称为时间粒度( t i m eg r a n u l a r i t y ) ，指按某一时间单位将时间划分为离散的时间段 n u l l 表示该时刻没有观测值，在本例中由于周末有两天法定假日，故有两天的事件为n u l l 一6 一 第二章持续事件序列 的事务上，作为一个事务看待。这样事务序列可以简记为 = l i c i dj = 1 ，2 ，| 丁( 2 | ) ( 23 ) 其中，t ? 表示客户i 的第j 个事务的时i b 7 标签，r ( t 1 为第i 个客户的时间标签集。当 然有t = t ( 。ii c i d 。 例如某一客户( c i d = 1 4 0 * 1 ) ，在2 0 0 3 年8 月至1 0 月期间所购买商品( g 1 一g 1 3 ) 的记录( 表2 2 ) 。 表2 2 ：客户购买商品的事务数据 d a t et i dg 1 g 2g 3g 4g 5 g 6g 7 g 1 2g 1 3 2 0 0 3 8 5 1 535 2 0 0 3 8 92 2 0 0 3 8 1 23 2 0 0 3 8 1 9 4 2 0 0 3 8 2 75 1 05 2 0 0 3 8 2 96444 2 0 0 3 9 77 1 0 2 0 0 3 一l o 一1 3811 55 2 0 0 3 1 0 一1 9911 55 2 0 0 3 1 0 2 21 0l5 2 0 0 3 一l o 一2 41 1 1 0 注：事务项中的负号表示客户退货 显然该事务数据的最小时间单位是天，日间隔事务序列为 4 0 4 0 4 0 2 0 0 3 8 2 0 0 3 8 2 0 0 3 9 g g g 二,g6，舟12九 事务序列的一个重要特点就是事务的发生都是在基本时间单位点上“瞬间完成”的。 一般，这类事件序列挖掘都是以所有客户的交易记录进行的。显然不考虑客户个体的交 易行为的差异性将会对数据挖掘构成不利的影响，甚至导致错误的结论 三事件序列 在事件序列中，事件是基本元素。在已有的研究中仅根据研究需要来定义事件例 7 时态数据挖掘及其应用 如表2 3 是一批按月记录的手机消费数据，包括用户类型( t ) 、实际营收( r ) 、本地话 费( ”1 ) 、长途话费扣2 ) 、漫游费( u 3 ) 、国际话费( ”4 ) 、信息费( ”5 ) 和特服费( 6 ) 。 通过简单的阈值划分就可将原始数据转换为一个事件序列数据，例如v l = l 定义为唪 地话费低”事件，v 4 = y 定义为“发生国际话费”事件。这里并不要求连续的属性观 测值，仅当用户发生行为时才记录用户在相应属性上的观测值。通过符号化之后就可以 得到与用户该次行为相对应的事件集，而累积记录下同一用户在不同时刻上发生的事件 集就构成了事件序列。 表2 3 ：移动通讯话费事件记录 u i dd a t etrv lv 2v 3v 4v 5v 6 12 0 0 1 。9amulln yn 1 2 0 0 1 1 0 ahllmnyn 12 0 0 1 1 1alu ulnny 1 2 0 0 1 一1 2bh u lhnn n 12 0 0 2 1allllnn n 22 0 0 1 - 9amlllnnn 22 0 0 1 1 0 a l llhnnn 22 0 0 1 1 1alllmnn n 22 0 0 1 1 2alllln yy 2 2 0 0 2 1 a l lllnn n 一般事件序列中的事件都可以用式( 2 4 ) 的二元组形式表示，t 为时间标签集，e 为事件集。 = i t j tj = 1 ，2 ，i r l ( 2 4 ) 事件序列并不要求时间标签集丁为等间隔，允许事件发生的时间间隔不等。例如表23 中如果仅考虑属性( 口1 ) ，则编号( u i d ) 为1 的用户，其事件序列为 ， ，一， ，- 1 由于时间按月等间隔划分，也可简单记为 m ，日，l ，h ，l ，) 。 若考虑多属性，只需在e 项中增加所要考察的属性事件。本例属性集1 ， 2 ，”6 ) 8 第二章持续事件序列 对应的事件序列为 f 2 0 0 1 一 l 2 0 0 1 一 l = 饼叫 川 川 叫 啪 眦 堕查塑塑堡塑垦基堕旦 持续事件：指在一定时间内，变量( 或属性) 的观测值持续落入特定的取值区间。例 如股价数据中收益率持续n 天保持在c 级，则认为c 事件持续。天；事务数据库中相 邻两次购买4 商品的事务间隔卢天可定义为4 事件持续卢天。 二目标事件与条件事件 目标事件：在特定挖掘任务中，都有一个目标变量。其所对应的事件就定义为目标 事件。例如股价数据中的收益率事件、事务数据库中的交易额以及手机月度消费数据中 的月度营收事件。 条件事件：相对于目标事件，和目标变量相关的条件变量所产生的事件。类似应变 量与解释变量的关系，条件事件是对目标事件的约束，其目的是为了更好的解释目标事 件的发生规律。 三持续事件序列 持续事件序列( d u r a t i v ee v e i l ts e r i e s ，d e s ) 指以个体为考察单位，并记录个体所产 生事件的起止时刻的一组数据。d e s 必须具有三个要素：个体标识集( i n d e xs e t ) ，事 件持续时段集( t i m es p a ns e t ) 以及事件集( e v e n tl i s t ) 。 而从数据对象格式上定义，持续事件序列是指具有以下形式的三元组 = 1 i js p 则)( 25 ) 其中，表示个体标识集，s = s ik = 1 ，2 ，i s ( z i 一1 ) 表示个体i 所发生 的时段集合，s g = 障1 肄，) 为个体i 的第奄个时段区间，( s 2 1 ) 为个体i 在第k 个时 段s 譬。所发生的事件集。 持续事件序列( 以下简称d e s ) 的定义包含了以上三类时态数据，并给出统一的时 态数据格式( 见表2 4 ) 。 d e s 的事务集中也可以分成目标事件集d 和条件事件集c ，即e = c | u d ，一般 d 为单一目标事件 - - - - _ ( l i is g ( 2 6 ) 1 n 一 第二章持续事件序列 表2 4 ：采用d e s 数据格式规范的时态数据 时态数据类型d e s 格式备注 时间序列 v iei i 为任一个体 s # = i t ，t + 1 ) 1 ，k t t 时域等间隔划分 e ( s ) = e ( t ) l 机、_ t如 1 为排序后时间标签 事务序列 i 垒ic i d 垒i s g = ，t 辨。) b t ( t )s ：表示第个时间间隔 e ( s g ) = e ( t l 脚 事件序列 v i i i 为任一个体 s | = f ) = t ，t j + 1 ) l 埘t j t 时域不要求等间隔划分 e ( s g ) = e ( ，) i j ：自 由于本文将事件序列扩展为持续事件序列，并将d e s 作为统一规范的时态数据格 式，所以在本文所论述的范围内，d e s 挖掘和时态数据挖掘具有共同的数据对象本文 以下将这两个概念等同看待，不做区分。 第三节持续事件序列的特点 从d e s 的定义以及与其他时态数据之间的对应关系可以发现，d e s 数据主要有以 下几个特点( 表2 5 ) 。 表2 5 ：d e s 与其他时态数据的比较 时态数据类型时间序列 事务序列事件序列d e s 有无考虑时态因素有有有有 时态结构处理 离散化离散化离散化完全保留 时域是否分割是是是否 是否考虑个体差异否否否是 事件是否持续否否否是 有无目标事件无无无有 有无条件事件无无无有 一事件持续性 d e s 中的事件发生的起止时间标签允许事件在时间维上分布的连续性。同时起止时 间标签突出了事件的持续性。不必要求事件必须“瞬时发生”，这使得d e s 更加符合实 际，同时还能将已有的时态数据同一规范化。 一1 1 时态数据挖掘及其应用 二个体差异性 以往的研究都是以挖掘出频繁模式为目标，必须要在大量数据中进行搜索，基本不 考虑个体差异对于事件序列的影响。这一方面是因为研究方法的不完善，另一方面是因 为对于个体差异性的不够重视。 d e s 就是以个体作为基本数据单位定义的数据对象，非常有利于考虑个体差异性的 挖掘任务，同时还可以全面兼容以事务、记录等为基本数据单位的挖掘任务。 三目标事件与条件事件 目标事件和条件事件的明确将更有利于d e s 挖掘的任务目标和方法设计，并且条件 事件也可以是相关的解释变量，虽然已有的研究中都将变量简化为符号事件，不区分目 标事件和条件事件，但作者认为这主要是因为没有合适的方法来处理变量。一旦将建模 思想引入，例如本文将风险模型引入d e s 挖掘中，就可以很方便的处理变量、事件以及 两者混合的各种情形。 1 2 第三章关联规则挖掘 关联规则( a s s o c i a t i o nr u l e ) 作为最早的时态数据研究方法，主要被用于事务数据库挖 掘。f 面我们将从关联规则基本概念和算法设计入手，回顾关联规则挖掘的沿革1 ， 并有选择的介绍一些重要的前沿方向，为下一章的时态规则挖掘做好铺垫。 第一节关联规则的定义 关联规则挖掘是指在数据库中挖掘出“某些特定组合的事件反复发生”的规则。这 里，事件的发生被定义为特定属性值的出现或者不出现。关联规则中涉及到的概念有以 下的一些： 1 项、项集、基本项集与k 一项集 项( i t e m ) 是相对于具体应用的概念，由不同的研究对象和用户要求决定。包含若干 项的集合称为项集( i t e m s e t ) 。对于一项具体的关联规则挖掘任务来说，存在基本项集 = i t ，j 2 ， ，其中，每个如( 1 女m ) 称为基本项。包含k 个项的集合称为 项集( k - i t e m s e t ) ，为项集的大小( s i z e ) 。 2 事务、事务数据库 事务t 是由基本项集中若干个基本项构成的集合，即t ，。事务数据库则是 一个有限的事务集合。在事务数据库中每个记录代表一个事务，每个事务有一个唯一标 识( t i d ) 和一个组成该事务的项的列表，即有 的二元组形式，其 中i t e m l i s t 为一个项集。 3 项集频数、频繁项集与频繁k 一项集 包含某一项集的事务在整个事务数据库中的出现次数称为该项集的项集频数，项集的 频数等价于项集支持度。若项集满足最小支持度m 扎一s u p ，则称它为频繁项集( f r e q u e n t i t e m s e t ) 。频繁集( c o l l e c t i o no ff r e q u e n ti t e m s e t s ) 是频繁项集的集合o 。若某频繁集中 的所有子集都是大小为k 的频繁项集，称为频繁n 项集。 o 为避免混淆，文中“频繁集”均指1 频繁项集的集合”，“频繁项集，指t 岫项梅成的集合， 一1 3 一 堕查墼堡笙堡墨基鏖旦 设基本项集，= i l ，i s i ，。) ，d 为事务性数据库，事务t 。若aci ，当 且仅当a ，时，称事务t 包含a 。 关联规则就是具有“a _ b ”形式的蕴涵式，令4 ，b ，且anb = 0 。 令l t a u b l 为数据库中包含aub 的事务数，f 珏为数据库中包含a 的事务数，i 乃l 为 数据库的事务数。则a - - + b 在d 中的支持度s ( a _ b ) 和可信度c ( a _ b ) 分别为 跗一+ b ) = p ( a u b ) = 剖 c ( a - b ) = p ( b 1 4 ) = 可i r a u b i 第二节关联规则的算法基础 f 31 ) ( 3 2 ) 从定义看，要得到关联规则a _ b ，必须要先生成频繁集“和“口”。因此， 关联规则挖掘分为两步：先由数据库生成频繁集，再由频繁集生成关联规则。有关研究 主要集中在如何快速有效的得到频繁集的算法。其中，最早提出且最具代表性的算法是 a p r i o r i 2 0 , 2 1 】。这一算法基于命题：如果项集l 的任一( 1 1 项- t - 集非频繁，则l 也 非频繁。这被用于进行候选集修剪，其逆否命题则被用于由生成候选集。a p r i o r i 算法每 次扫描数据库只搜索相同大小的频繁集，然后逐层搜索直至无法得到新的频繁集为止。 为了摆脱逐层递归的“候选集h 频繁集”的冗余，a g a r w a l ，r 等( 2 0 0 0 ) 和h a n ， j 等( 2 0 0 0 ) 分别提出了t r e e p r o j e c t i o n 2 2 1 和f p g r o w t h 算法 2 3 ，都是创建了一种树 形数据结构来压缩存储频繁项集信息。频繁项集树建立之后对树进行遍历搜索，既可得 到所有的关联规则。该类算法可以有效减少数据库访问的次数提高算法效率。但树形数 据结构都很复杂算法实现困难，且开始阶段需要大量的内存空间来生成树形结构对硬件 要求较高，实用中受到很大的限制。 现仅举例简要说明a p r i o r i 算法的原理。设将事务数据库d ( 表3 1 ) 中的所有项集按 大小由小到大逐层堆放为倒树结构。则除最底层为大小为l 的单项集结点之外，其他层 的项集结点都是由其下层的项集结点逐层合并而来( 见图3 1 ) 。而频繁集就是那些满足 支持度阈值的项集结点的集合。 1 4 第三章关联规则挖掘 表3 1 ：事务数据库d t i d a bcdef 1 010ll1l 2 0110010 3 00o1011 4 0 1 0110 l 3 00010l1 a b e d b 国 b d ) ( a c d ) c d 麟措戮u 固l 纠uu u 图3 - 1 ：逐层堆放的倒树结构( 部分) a p r i o r i 第1 次只扫描最底层，得到候选集c = 。：3 ) ， 6 ：1 ) ， c ：4 1 ， d ： 2 ) ， e ：4 ) ， 厂：4 1 。若设支持度阈值4 0 ( 即支持度计数为2 ) ，由于b 的计数为1 ，可确 定任何包含b 的项集都非频繁，在图3 1 中用灰色圈表示。频繁集l 1 = o ，c ，d ，e ， ，再对 l 1 连接得c 2 = 。c ，c d ，d e ，e ，) ；第2 次扫描得到工2 = o c ，a d ，e ，) ， 再连接得到g ，依次重复至无法生成新的频繁项集。本例最大频繁项集大小为4 ，频繁 集l = n ，c ，a c d l ) 。 第三节关联规则的最新发展 虽然现在已有大量形式各异的关联规则算法，他们分别适用于不同形式的数据对象。 若从关联规则分析的过程考虑，其算法层面仍然是面对定性数据属性的基于“支持度 可信度”结构的基础算法过程。但其方法层面的研究大为拓展。这是由于：( 1 ) 数据集 的规模巨大会导致关联规则数量过多，可理解性差；( 2 ) 数据属性多样化，需要转化为 定性属性或者布尔属性，数据才能进入算法；( 3 ) 在关系型数据库中，属性( 字段) 是最 重要的组成部分，属性项的处理直接关系到关联挖掘的最终结果。而总结已有的研究发 o a ：3 ) 表示项集a 的支持度计数为3 ，以下同 一1 5 时态数据挖掘及其应用 现有基于复杂数据属性和基于复杂数据组织形式这两大主要发展方向。 一复杂数据属性 早期关联规则的研究都是针对布尔型属性展开，没有考虑数据属性的特点。而在实 际中由于数据属性的多样性，关联规则也具有多种形式。 按属性取值类型可分为布尔( b o o l e a n ) 关联规则和数值( n u m e r i c ) 关联规则，数值 关联规则又分为定量( q u a n t i t a t i v e ) 关联规则和定类( c a t e g o r i c a l ) 关联规则。按谓 词( 维度) 可分为只有一个谓词的维内( i n t r a d i m e n s i o n a l ) 关联规则，包含两个或两个以 上的不同谓词的多维( m u l t i d i m e n s i o n a l ) 关联规则。没有重复的多维关联规则称为维间 ( i n t e r d i m e n s i o n a l ) 关联规则，否则称为混合关联规则。在同一个维度的多个属性间会存 在概念上的隶属关系，这就形成了多层次( m u l t i l e v e l ) 关联规则。由于属性分类的多 样性和复杂性，各类关联规则之间也会有交叉和重复。 1 数值关联规则 数值关联规则问题首先由s r i k a n t ，r 等( 1 9 9 6 ) 提出并给出了形式化的定义 2 4 。处 理数值属性的基本思想是先将定量或者定类属性映射为布尔型属性，然后采用一般算法 完成关联规则挖掘。因而如何将数值属性区间化就成为这类研究的关键。 s r i k a n t ，r 等( 1 9 9 6 ) 考虑将数值属性等间隔划分，并使用偏完整度( m e a s u r eo f p a r t i a lc o m p l e t e n e s s ) 度量分区的信息损失和决定分区个数。当某一个分区的支持度小于 r a i n s u p ，就与邻近的分区合并。同时给出了置信度的降低程度，部分解决了置信度过 低问题。f u k u d a ，t 等( 1 9 9 6