（计算机科学与技术专业论文）时间序列中的知识发现：基于频繁模式发现的分类和聚类方法研究.pdf

j i i i i ii q 1 l l l l l l l li l l li ii iii111 y 17 6 0 5 3 2 ad o c t o r a ld i s s e r t a t i o ni nc o m p u t e rs c i e n c ea n dt e c h n o l o g y k n o w l e d g ed i s c o v e r yi nt i m es e r i e s ： r e s e a r c h e so nc l a s s i f i c a t i o na n d c l u s t e r i n gb a s e do nf r e q u e n tp a t t e r n d i s c o v e r y b y w a nl i s u p e r v i s o r ：p r o f l i a oj i a n x i n b e i j i n gu n i v e r s i t yo f p o s t sa n dt e l e c o m m u n i c a t i o n s a u g u s t2 0 0 9 弋 ，岭毒 j 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：彳亿 日期： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在 年解密后适用本授权书。 本人签名：趔 导师签名： 嗍兰! 笙丝丝 日期：蚀罗：罗：丝 一客i 粤 ) ， 北京邮电人学博十学位论文 摘要 摘要 随着数据库技术、因特网、电信技术等信息技术的飞速发展，时间序列数据 在现实生产和生活的各个领域中广泛存在( 如电信运营、金融市场、工业过程、 科学实验、医疗、气象、生物信息等) ，且存储规模呈现爆炸式增长。如何从海 量时间序列数据中发现能够帮助人们决策且以前不知道或不易知道的模式、信息 和知识是人们现阶段最急切的需求，也是时间序列数据挖掘研究的核心问题。目 前时间序列数据挖掘的研究尚处于起步阶段，很多研究问题还极富挑战性，很多 挖掘算法还有待扩充和完善。 本文从预测、分类、聚类、搜索和频繁模式发现五个方面对时间序列数据挖 掘的研究现状进行了综述，对目前各个研究方向的主要方法进行总结和评价，在 频繁模式发现和动态复杂网络社区划分两个方面进行了深入研究。最后在总结全 文的基础上，指出有待本文深入研究的问题。本文的创新性工作主要包括以下内 容： ( 1 ) 提出一种频繁模式挖掘算法f p m ( f r e q u e n tp a t t e mm i n i n g ) ，该算法充 分考虑频繁模式在时间序列中出现次数和分布，能从时间序列数据中挖掘出只在 “某个”时间段内频繁出现的“异常”事件序列和在“整个”时间序列中频繁出现的 “序列”事件。基于这些不同分布的频繁模式扩展m a m c ( m i x e dm e m o r y a g g r e g a t i o nm a r k o vc h a i n ) 模型得到f m a m c ( f r e q u e n tp a r e mb a s e dm i x e d m e m o r ya g g r e g a t i o nm a r k o vc h a i n ) 模型。f m a m c 描述了时间序列中不同类型 频繁模式之间的时序关联关系。实验表明，f p m 算法时间性能优于p r e f i x s p a n ( p r e f i x - p r o j e c t e ds e q u e n t i a lp a t t e r nm i n i n g ) 和，w i n m i n e r 算法，f m a m c 模型能 够比m a m c 模型更准确的预测时间序列中的事件。 ( 2 ) 提出一种基于频繁模式的时间序列分类框架，该框架分为特征提取、 特征选择和分类模型训练三个阶段：首先利用本文提出的m n o e ( m i n i n g n o n o v e r l a pe p i s o d e ) 算法挖掘时间序列中的非重叠频繁模式，基于非重叠频繁 模式提出e g m a m c ( e p i s o d eg e n e r a t e dm i x e dm e m o r ya g g r e g a t i o nm a r k o vc h a i n ) 模型描述时间序列。然后，根据似然比检验原理，从理论上推导出频繁模式在时 间序列中出现的次数和e g m a m c 模型是否能显著描述时间序列之间的关系；根 据信息增益定义，选择能显著描述时间序列并且信息增益大于给定阈值的频繁模 式作为时间序列特征输入传统分类算法训练分类模型。实验表明，选择频繁模式 作为特征进行分类的结果优于不选择频繁模式作为特征的结果。 ( 3 )提出特征流的概念描述频繁模式实例在时间序列中的分布情况，根 据特征流的频谱特征将相应的频繁模式分为三种类别，并分别与时间序列中隐藏 的不同类型的事件相对应。提出e d p a ( e v e n td e t e c t i o nb yp a r e ma g g r e g a t i o n ) 算法，将紧密关联的频繁模式聚合在一起，每个聚类中的频繁模式构成一个事件。 实验表明，选择显著非重叠频繁模式输入e d p a 算法进行事件探测的准确率高于 选择其它类型频繁模式。 ( 4 ) 提出一系列基于极大团的复杂网络静态和动态社区划分方法：首先 提出一种复杂网络中极大团挖掘算法c l i m ( c l i q u em i n i n g ) ，该算法利用复杂 网络中节点聚集系数高的特点设计剪枝策略。实验表明，c l i m 算法计算大规模 复杂网络和节点聚集系数较高的随机网络中极大团的时间性能明显优于 北京邮电人学膊l j 学位论文摘要 i m p r o v e db k ( b r o n k e r b o s c h t ) 算法。基于极大团及其重叠关系定义社区核心和 附属节点组成社区。提出一种重叠社区划分算法c d p m ( c l i q u ed i r e c t e d p e r c o l a t i o nm e t h o d ) 。c d p m 算法采用作者提出的结构轮廓系数s s c ( s t r u c t u r e s i l h o u e t t ec o e f f i c i e n t ) 衡量复杂网络社区划分质量，s s c 越大，社区划分越优， 算法最终输出使得s s c 最大的社区划分。实验表明，c d p m 算法和c p m ( c l i q u e p e r c o l a t i o nm e t h o d ) 、g n ( g i v e n n e w m a n ) 算法相比能够更准确的划分社区， 其f m e a s u r e 和v a d ( v e r t e xa v e r a g ed e g r e e ) 值更高。同时考虑复杂网络链接 结构和节点附属属性信息，提出信息图社区划分算法j c c m ( j o i n tc l u s t e r i n g c o e f f i c i e n tm e t h o d ) ，首先采用启发式方法计算出由极大团结构重叠而成的社区 核心，然后算法采用本文提出的j c c ( j o i n tc l u s t e r i n gc o e f f i c i e n t ) 系数为目标函 数将社区核心和附属节点聚合在一起，采用不同的距离函数度量附属节点到社区 核心中不同地位节点间的距离。实验表明，j c c m 算法划分信息图中社区的效果 优于只考虑网络结构信息或节点属性信息的算法。在静态社区划分算法的基础上， 定义相邻时刻静态社区间的演化关系并提出一种新的动态社区划分算法d c i ( d y n a m i cc o m m u n i t yi d e n t i f i c a t i o n ) 。d c i 算法首先利用本文提出的基于最短描 述长度原则( m d l ：m i n i m u md e s c r i p t i o nl e n g t h ) 的划分算法划分静态网络社 区。然后，将相邻时刻静态社区及其成员间的重叠关系抽象为一个二分图，将动 态社区演化问题抽象为二分图划分问题。提出一种基于m d l 的算法划分二分图。 实验证明，d c i 算法能够比g s ( g r a p h s c o p e ) 、g c ( g r o u p c o l o r i n g ) 算法更加 准确的划分出动态网络中的动态社区，并且具有较好的时间性能。 ( 5 ) 将信息在社会网络中的传播过程抽象为节点按一定转移概率依次出 现的半马氏过程。提出“空状态”的概念扩展多维半马氏过程，在此基础上提出社 会网络信息流模型。社会网络中的成员和模型状态空间中的状态一一对应，社会 成员间信息交互的概率即模型中状态间的转移概率，转移概率的大小由社会成员 自身特性和所属的社会网络子结构所决定。提出基于社会网络结构的回报函数， 并构造有偿半马氏模型计算用户价值。在信息流模型和有偿半马氏模型的基础上， 综合考虑社会网络和用户自身偏好对资源选择的影响，提出协同过滤算法s m r r ( s e m i m a r k o va n dr e w a r dr e n e w a l ) 。实验表明，s m r r 算法的预测准确率优于 传统的余弦算法和p d f ( r a t ei n f o r m a t i o nf l o w ) 算法。 关键字：时间序列；数据挖掘；频繁模式发现：复杂网络；社区划分 一 t 鼙 d o c t o r a ld i s s e r t a t i o no fb e i j i n gu n i v e r s i t yo fp o s t sa n dt e l e c o m m u n i c a t i o n s a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fd a t a b a s e ， s e r i e sd a t aa p p e a r sw i d e l yi nr e a lw o r l dl i f e ， i n t e r n e ta n dt e l e c o mt e c h n i q u e ，t i m e s u c ha st e l e c o m m u n i c a t i o nb u s i n e s s ， f i n a n c i a im a r k e t ，m a n u f a c t u r ep r o c e s s ，s c i e n c ee x p e r i m e n t ，m e d i c a lc a r e ，m e t e o r o l o g y , b i o i n f o r m a t i o ne t c a n dt h es c a l eo fd a t ai sh u g ea n de x p l o d i n g h o wt oh e l pu s e r st o d i s c o v e rh i d d e np a t t e r n i n f o r m a t i o na n dk n o w l e d g ef r o ml a r g et i m es e r i e sd a t ai n o r d e rt os u p p o r td e c i s i o ni sar a r i n gd e m a n d i t sa l s ot h ec o r er e s e a r c ht o p i ci nt i m e s e r i e sd a t am i n i n g r e c e n t l y , r e s e a r c h e r si u s ts t a r tt oc o n c e r nt i m es e r i e sd a t am i n i n g ， m a n yt o p i c sa r ec h a l l e n g i n g ，m a n ya l g o r i t h m sn e e dt ob ee x t e n d e da n dp e r f e c t e d t h i sp a p e rr e v i e w e dt i m es e r i e sd a t am i n i n gf r o mp r e d i c t i o n ，c l a s s i f i c a t i o n ， c l u s t e r i n g s e a r c ha n df r e q u e n tp a t t e r nd i s c o v e r yf i v ea s p e c t s t h em a i nm e t h o d si n e a c ha r e aa r es u m m a r i z e da n dr e v i e w e d t h e nw ef o c u so nt h er e s e a r c ht o p i c si n f r e q u e n tp a t t e r nd i s c o v e r ya n dc o m m u n i t yi d e n t i f i c a t i o n i nd y n a m i cc o m p l e x n e t w o r k sd e e p l y f i n a l l yb a s e do nt h ec o n c l u s i o no ft h i sp a p e r , w ep r o p o s e ds o m e r e s e a r c hd i r e c t i o n si nf u t u r e t h ec o n t r i b u t i o n so ft h i sp a p e ra r ea sf o i l o w s ： ( 1 ) p r o p o s e daf r e q u e n tp a t t e r nd i s c o v e r ya l g o r i t h mf p m ( f r e q u e n tp a t t e r n m i n i n g ) ，t h i sa l g o r i t h mc o n s i d e r e dn o to n l yt h es u p p o r t sb u ta l s ot h ed i s t r i b u t i o n so f f r e q u e n tp a t t e r n s i tc a nd i s c o v e rt h e “e x c e p t i o n s f r e q u e n t l ya p p e a r si nas p e c i a lt i m e s e g m e n ta n dt h es e q u e n t i a le v e n tf r e q u e n t l ya p p e a r si nt h ew h o l et i m es e r i e s b a s e d o nt h e s ef r e q u e n tp a t t e r n sw i t hd i f f e r e n td i s t r i b u t i o n s w ee x t e n dm a m c ( m i x e d m e m o r ya g g r e g a t i o nm a r k o vc h a i n ) m o d e lt of m a m c ( f r e q u e n tp a t t e r nb a s e d m i x e dm e m o r ya g g r e g a t i o nm a r k o vc h a i n ) m o d e l f m a m cd e s c r i b e dt h et e m p o r a l c o r r e l a t i o n sa m o n gd i f f e r e n tt y p e so ff r e q u e n tp a t t e r n si nt i m es e r i e s e x p e r i m e n t s d e m o n s t r a t ef p mp e r f o r m sb e t t e rt h a n p r e f i x s p a n ( 旦鱼选一p r o j e c t e ds e q u e n t i a l o a t t e r nm i n i n g ) a n dw i n m i n e ra l g o r i t h m s 。f m a m cm o d e lc a np r e d i c tt i m es e r i e s m o r ea c c u r a t e l yt h a nm a m cm o d e l ( 2 ) p r o p o s e daf r e q u e n tp a t t e r nb a s e dt i m es e r i e sc l a s s i f i c a t i o nf r a m e w o r k ，i t i n c l u d e df e a t u r ee x t r a c t i o n f e a t u r es e l e c t i o na n dc l a s s i f i c a t i o nt h r e ep h a s e s ：t h e p r o p o s e dm n o ea l g o r i t h me x t r a c t sn o n o v e r l a pf r e q u e n tp a t t e r n sf r o mt i m es e r i e s a n dp r o p o s e de g m a m c ( e p i s o d eg e n e r a t e dm i x e dm e m o r ya g g r e g a t i o nm a r k o v c h a i n ) m o d e lb a s e do nt h e s en o n o v e r l a pe p i s o d et od e s c r i b et i m es e r i e s a f t e rt h a t a c c o r d i n gt or a t i ol i k e l i h o o dt e s t w ei n d u c e dt h es u p p o r tt h a tc a ng u a r a n t e et h e s i g n i f i c a n c eo fn o n - o v e r l a pe p i s o d e f i n a l l y , a c c o r d i n gt ot h ed e f i n i t i o no fe n t r o p y , w es e l e c t e dt h es i g n i f i c a n tn o n o v e r l a pe p i s o d ew h o s ee n t r o p yo fd i s t r i b u t i o ne x c e e d as p e c i f i e dt h r e s h o l dt ot r a i nc l a s s i f i c a t i o nm o d e l e x p e r i m e n t sd e m o n s t r a t et h a t s e l e c tf r e q u e n tp a t t e r n sa sf e a t u r e sc a ni m p r o v ec l a s s i f i c a t i o nm o d e l se f f e c t i v e l y ( 3 ) p r o p o s e dt h ec o n c e p to ff e a t u r ef l o wt od e s c r i b et h ed i s t r i b u t i o n so f f r e q u e n tp a t t e r n si nt i m es e r i e s ，w ec a t e g o r i z e dt h ef r e q u e n tp a t t e r ni n t ot h r e et y p e s a c c o r d i n gt ot h e i rs p e c t r u mo ff e a t u r ef l o w sa n dm a pd i f f e r e n tt y p e so ff r e q u e n t p a t t e r n st od i f i e r e n tt y p e so fe v e n th i d d e ni nt i m es e r i e s w ep r o p o s e de d p a ( e v e n t d e t e c t i o nb yp a t t e r na g g r e g a t i o n ) a l g o r i t h mt oa g g r e g a t et i g h t l yc o r r e l a t e df r e q u e n t d o c t o r a ld i s s e r t a t i o no fb e i j i n gu n i v e r s i t yo fp o s t sa n dt e l e c o m m u n i c a t i o n s a b s t r a c t p a t t e r n s ，e a c h c l u s t e ro f f r e q u e n tp a t t e r n sr e p r e s e n t s a n e v e n t e x p e r i m e n t s d e m o n s t r a t et h a t i n p u t t i n gm a x i m a ls i g n i f i c a n tn o n 。o v e r l a pf r e q u e n tp a t t e r n si n t o e d p aa l g o r i t h mt od e t e c te v e n tc a ng e tm o r ea c c u r a t er e s u l tt h a ns e l e c t i n go t h e rt y p e s o ff r e q u e n tp a t t e r n s ( 4 ) p r o p o s e daf a m i l yo fs t a t i cc o m m u n i t yi d e n t i f i c a t i o na l g o r i t h m sb a s e d o nm a x i m a lc l i q u e sa n dad y n a m i cc o m m u n i t yi d e n t i f i c a t i o na l g o r i t h m ：f i r s t l y , t h i s p a p e rp r o p o s e da na l g o r i t h mc l i m ( c l i q u em i n i n 9 1t od i s c o v e rm a x i m a lc l i q u e si n c o m p l e xn e t w o r k s w ed e s i g n e dt h ep r u n es t r a t e g yo fe l i mb a s e do nt h eo b s e r v a t i o n t h a tt h ec l u s t e r i n gt o e f f i c i e n to fm o s to ft h ev e r t i c e si nc o m p l e xn e t w o r ki s l a r g e e x p e r i m e n t sd e m o n s t r a t ee l i mp e r f o r m sb e t t e rt h a ni m p r o v e db k ( b r o n k e r b o s c h t ) a l g o r i t h mo nc o m p l e xn e t w o r ka n dr a n d o mg r a p h sw i t hh i g hc l u s t e r i n gc o e f f i c i e n t b a s e do nt h em a x i m a lc l i q u e sf o u n db ye l i m t h i sp a p e rd e f i n e dac o m m u n i t y c o n s i s t so fc o m m u n i t yc o r ea n dp e r i p h e r a lv e r t i c e sa n dp r o p o s e dac o m m u n i t y i d e n t i f i c a t i o na l g o r i t h mc d p m ( c l i q u ed i r e c t e dp e r c o l a t i o nm e t h o d ) b a s e do n o v e r l a p p i n gm a x i m a lc l i q u e s c d p mu t i l i z e dt h ep r o p o s e ds s c ( s t r u c t u r es i l h o u e t t e c o e f f i c i e n t ) a so b j e c t i v ef u n c t i o nt oi d e n t i f yc o m m u n i t i e si nc o m p l e xn e t w o r k s t h e v a l u eo fs s ci s l a r g e rt h ec o r r e s p o n d i n gc o m m u n i t yi d e n t i f i c a t i o ni sb e t t e n e x p e r i m e n t sd e m o n s t r a t et h a tc d p ma l g o r i t h mp e r f o r m sb e t t e rt h a nc p m ( c l i q u e p e r c o l a t i o nm e t h o d ) ，g n ( g i v e n n e w m a n ) a l g o r i t h m se v a l u a t e db yf m e a s u r ea n d v a d ( v e r t e xa v e r a g ed e g r e e ) b yc o n s i d e r i n gl i n ks t r u c t u r e sa n da t t r i b u t e sa t t a c h e d o nv e r t i c e si nc o m p l e xn e t w o r k s ，t h i sp a p e rp r o p o s e daj c c m ( j o i n tc l u s t e r i n g c o e f f i c i e n tm e t h o d ) a l g o r i t h mt oi d e n t i f yc o m m u n i t i e si ni n f o r m a t i v eg r a p h f i r s t l y , i tu t i l i z e dh e u r i s t i cm e t h o dt oc a l c u l a t ec o m m u n i t yc o r e sf o r m e db yo v e r l a p p i n g m a x i m a lc l i q u e s t h e nj c ci su s e da st h eo b j e c t i v ef u n c t i o nt oa g g r e g a t ec o m m u n i t y c o r e sa n dp e r i p h e r a lv e r t i c e st o g e t h e r , d i f f e r e n td i s t a n c ef u n c t i o n sa r eu s e dt om e a s u r e t h ed i s t a n c eb e t w e e nv e r t i c e si nd i f f e r e n tp o s i t i o n s e x p e r i m e n t sd e m o n s t r a t ej c c m p e r f o r m sb e t t e rt h a ne x i s t i n ga l g o r i t h m sw h i c hd on o tc o n s i d e rs t r u c t u r ei n f o r m a t i o n a n da t t r i b u t e sa t t a c h e do nv e r t i c e sc o o p e r a t i v e l y b a s e do nt h es t a t i cc o m m u n i t y i d e n t i f i c a t i o n a l g o r i t h m s ，b yd e f i n i n ge v o l v i n g r e l a t i o n s h i p sa m o n g s t a t i c c o m m u n i t i e sa ta d j a c e n tt i m e p o i n t s ，t h i sp a p e rp r o p o s e dad y n a m i cc o m m u n i t y i d e n t i f i c a t i o na l g o r i t h md c i ( d y n a m i cc o m m u n i t yi d e n t i f i c a t i o n ) d c iu t i l i z e da m d l ( m i n i m u md e s c r i p t i o nl e n g t h ) b a s e dm e t h o dt oi d e n t i f yc o m m u n i t i e si ns t a t i c c o m p l e xn e t w o r k s t h e n ，w ea b s t r a c tt h ec o m m u n i t i e si na d j a c e n tc o m p l e xn e t w o r k s a n dt h e i r o v e r l a p p i n gr e l a t i o n s h i p a sb i g r a p h sa n dr e d u c et h ee v o l u t i o n so f c o m m u n i t i e si f la d j a c e n ts t a t i cc o m p l e xn e t w o r k si n t oab i g r a p hp a r t i t i o np r o b l e m a m d lb a s e dm e t h o di sa l s op r o p o s e dt op a r t i t i o nb i g r a p h s e x p e r i m e n t sd e m o n s t r a t e t h a td c ia l g o r i t h mc a ni d e n t i f yc o m m u n i t i e sm o r ea c c u r a t e l ya n dr u nf a s t e rt h a ng s ( g r a p h s c o p e ) ，g c ( g r o u p c o l o r i n g ) a l g o r i t h m s ( 5 )a b s t r a c tt h ep r o c e s so fi n f o r m a t i o nt r a n s i t i o ni nas o c i a ln e t w o r ka sa s e m i m a r k o vp r o c e s sm o d e li nw h i c hv e r t i c e sa p p e a rf o l l o w i n gs o m et r a n s i t i o n p r o b a b i l i t y w ep r o p o s e d “i d l es t a t e ”t oe x t e n dm u l t i - d i m e n s i o n a lm a r k o vp r o c e s s a n dp r o p o s e ds o c i a ln e t w o r ki n f o r m a t i o nf l o wm o d e lb a s e do ni t e a c hs t a t ei ns t a t e s p a c eo fi n f o r m a t i o nf l o wm o d e lr e p r e s e n t sa na c t o ri nas o c i a ln e t w o r k ，t r a n s i t i o n p r o b a b i l i t yi ni n f o r m a t i o nf l o wm o d e li st h ep r o b a b i l i t yt h a tt w oa c t o r se x c h a n g e i v 月 囊 一 川 j l l 世 d o c t o r a ld i s s e r t a t i o no fb e i j i n gu n i v e r s i t yo fp o s t sa n dt e l e c o m m u n i c a t i o n s a b s t r a c t i n f o r m a t i o n t h i st r a n s i t i o np r o b a b i l i t yi sd e t e r m i n e db yt h ec h a r a c t e r i s t i co fa c t o r s a n dt h es u b s t r u c t u r e so fs o c i a ln e t w o r ka c t o r si n v o l v e di n w ep r o p o s e dr e w a r d f u n c t i o nb a s e do ns o c i a ln e t w o r ks t r u c t u r ea n dc o n s t r u c tr e w a r dm a r k o vm o d e lt o c a l c u l a t ec u s t o m e rv a l u e b a s e do ni n f o r m a t i o nf l o wm o d e la n dr e w a r dm a r k o v m o d e l ，w ep r o p o s e dac o l l a b o r a t i v ef i l t e r i n ga l g o r i t h ms m r r ( s e m i m a r k o va n d r e w a r dr e