（计算机应用技术专业论文）分布式序列模式挖掘算法研究.pdf

7 8 扬州大学硕士学位论文 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 学位论文作者签名： 签字日期：a g 年s 月达日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。 本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学 技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 学位论文作者签名：狐渤 签字日期谤醇年月妇 导师签名： 签字日期：御萨f 月巧日 ( 本页为学位论文末页。如论文为密件可不授权，但论文原创必须声明。) 张长海；分布式序列模式挖掘算法研究 摘要 目前信息主导的时代，海量数据存储在数据库或者数据仓库中。面对这种“信 息爆炸 的现实，如何从海量数据中提取有价值的信息已显得尤为重要。数据挖 掘技术的出现和发展为人们解决了这一难题。所谓数据挖掘技术是利用各种分析 工具从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取潜 在有用的信息和知识的过程。 。 在本文中，我们对序列模式挖掘技术做了深入研究。序列模式挖掘是数据挖 掘研究的一个重要课题，挖掘基于时间或者其他顺序出现频率高的模式，是对关 联规则挖掘的迸一步推广，但克服了关联规则中不能反映事件在时间顺序上的前 后相关性。序列模式挖掘技术已在顾客购买行为的分析、网络访问模式分析、科 学实验的分析、疾病治疗的早期诊断、自然灾害的预测、d n a 序列模式的分析等 方面广泛应用。 在研究现有的单机和分布式序列模式挖掘算法的基础上，本文围绕着单机下 基于位图序列模式挖掘、分布式序列模式挖掘以及分布式多维序列模式的近似挖 掘等几方面做了深入研究，主要创新点如下： 1 ) 基于传统序列模式挖掘方法不能有效地解决候选序列费时难题，本文提出 一种基于位图的序列模式挖掘方法s m b r ( s e q u e n t i a lp 舭n l si i l i i 血1 9 b a s e do n b i t i i l 印r q ) r e s e m a t i o n ) 。s m b r 算法采用一种简化的位图表示结构表示数据库的方 法。该方法首先由序列扩展和项扩展产生候选序列，然后通过原序列位图和被扩 展项位图位置快速运算生成频繁序列，有效地获得序列模式。 2 ) 由于分布式环境下挖掘全局序列模式常常产生过多候选序列，加大了网络 通信代价。为此提出一种基于分布式环境下的挖掘全局序列模式算法f m g s p ( f 奴 m i r l i n go f g l o b ds e q u e n t i a lp 删。f m g s p 算法将各站点得到的局部序列模式压缩 到一种语法序列树上，避免了重复的序列前缀传输；基于合并树中结点序列规则、 简单的特点，提出一种i s e ( n e me x t e n s i o n 锄ds e q u e n c ee x t e n s i o n ) 剪枝策略，有效 地约减了候选序列，减少了网络传输量，从而快速生成全局序列模式。 2 扬州大学硕士学位论文 3 ) 提出一种多维序列模式近似挖掘算法a m s p ( a p p r o x i m a t em i n i n go fg l o b a l m u l t i d i m e n s i o i l a js e q u e n t i a lp a 仳e m s ) ，以解决分布式环境中大型数据库中多维序列 模式挖掘问题。该方法不同于传统的分布式多维序列模式挖掘方法，具备较好的 伸缩性。首先将维度信息嵌入相应序列中，使多维序列模式挖掘转化为序列模式 挖掘；然后在各分站点对转换后序列聚类、概化和分析，采用有效的近似挖掘方 法获得局部模式；最后集中所有局部模式，通过高频度序列模式模型挖掘全局多 维序列模式，有效地解决通信代价大、维度高等难题。 关键词：数据挖掘；分布式序列模式；多维信息；近似挖掘 张长海：分布式序列模式挖掘算法研究 3 a b s t r a c t c u r r e i l t l y n 瑚s 纰h 弱b e e ns t o r e di i i t 1 1 ed a t a b 硒e0 rd a ：t a 、a r e h o u s ei nt h e i l l f 0 加 1 a t i o n - d o m i i l a t e de r 氖h lm ef a c eo ft l l i ss i t u a t i o no f ”i n f o n n a t i o ne x p l o s i o n ，h o w e x 舰c t em ev a l 珑i b l ei l l f o r m a t i o n 丘l o mt h em 鹤s i v ed a ：t ah 嬲b e c o m ep a r t i c u l a d y i i i 驴r t 趾t w i mt h ee m e 玛e n c e 龇l dd e v e l o p m e mo fd a t am i i l i n gt e c l l i l i q u e s ，t i l i s p r o b l e mh a sb e e ns o l v e df o r l ep e o p l e a n dp o t e n t i a l 觚du s e f i l li n f o 衄a t i o n s 锄d h 1 0 、讥e 起e s a r ee x t m c t e d 丘o mm em 嬲s i v e ，i i l c o n l p l e t e ，n o i ，f h z 巧觚d 眦l d o m p m c t i c a ld a ：t ab yal 鹕em l i i l b e ro f 觚a l l y t i c a lt o o l s h lt l l i sp a p e r ，t l l ec o n t e n t m a i l l l yi i l c l u d e st h ei n i i l i i 玛s e q u e n t i a lp a t t e m s s e q u e n c e p a t t e mm i i l i n gi s 锄i i 玎印r t a n tr c s e a r c ht o p i cf o rd a 协m i i l i 】唱，m i n e st h el l i g l l 舭q u e n c y 彤吡e n l sw i m t i i l l er e l a t e ，觚ds o l d 也ep r o b l 锄t l l a tt l l e 嬲s o c i a t i o nm l e sd o e sn m r e n e c tt l l ec o r r e l a t i o no ft l l ee v e n t si nc h r o n o l o g i c a lo r d e r s e q u c l n c ep a t t e mm i i l i i 培 t e c l l i 】i o l o g yh a sb e e n u s e de x t e 】 1 s i v e l y i n l ec u s t o n 嘲? b u y i n gb e h a ：v i o r 锄a l y s i s ， m 铆o r ka c c e s sm o d e l 锄觚y s i s ， t 1 1 e 锄a l y s i so fs c i e n t i f i ce x p d ，t l l ee a j l y d i a 弘o s i so fd i a s e s ，i l 乏m l r a jd i 翰s t e r s 南r e c a s t d n as e q u e n c e 锄m y s i so fp a t t e m s t h em 抽r e s e a r c hc o n t e ：n ti i l c l u d e ：m u l t i d i m e i l s i o n a ls e q u e n t i a lp a t t e n 塔n l i l l i n 吕 d i s t r i b u t e ds e q u 训a lp a t t e m sm i i l i i 唱a i l dt l l e a p l ，r o x i m a t em i i l i i 玛f 0 rd i s t r i b u t e d m l l l t i d i i n e 璐i o i l a ls e q l 崩1 1 t i a lp a t t e n 坞锄d o n 船吣i n gt h ee x i t e dm e t l l o d sf 0 r 蛐gs e q u e n t i a lp a 吮m s t h em 咖c o n t r i b u t i o 璐锄di i l 】n o v a t i o 璐o ft l l i sd i s s e r t a t i o n a r ea sf 0 l l o 、) l ，s ： 1 ) t h eh i g l lc o s to fc a l l d i 拙e9 e q u e n c ep r o b l e m sc a nb en o ta d d r e ss _ e de 肫c t i v e l y b yt l 呛缸a d i t i o n a l m e 1 0 d sf o r m i i l i n gs e q u e n c e s ， s 0an e w 1 1 1 i n i n g m 酬吣d s m b i q l l e n t i a lp a t 胁sm i i l i i 唱b 嬲e do nb i n n a pr e p r e s e n t a t i o n ) b 硒e do nb i 缸n 印i s p r o p o s e d t h ed a t a _ b a u s ei sr e p r e s e n t e db yb i t m a p si 1 1t h em e t h o 也锄das i r n p l i f i e d b i n i l a p 姗t u r ei sp r e s e n t e d f i r s tt t l ea l g o r i m mg e 鹏m ：t ec a r l d i d a t es e q l l e n c e sb y s e ( s e q u e n c ee x 溉s i o n ) a n di e ( i t e me x t e n s i o n ) ，a n dm e no b t a i na l l6 嘲u e n t q u e n c e s 4 扬州大学硕士学位论文 b yc o m p a r i n gm eo r i g i 脚b i t r i l 印锄dm ee x t e n d e di t e mb i 仃1 1 a p a n dq u i c l 【l yp r 0 h 如c e s 丘e q u e n tc o 呲b ya ne f r e c t i v es 眦g yt 0o b t a i nm u l t i d i m e n s i o n a ls e q u e n t i a lp a n e m s 2 ) n o ws o m ed i s t r i b u t e ds e q u e m i a lp a n e m m i i l i n ga l g o r i t l l m sg e n e r a ：t et o om u c h c 觚d i d a ：t es e q u e n c e s ，i i l c r e a c o 舢眦l i l i c a t i o no v e r h e a d i n l i sp 印e r ，an e w a l g o r i t l l 】m f m g s p ( f 缸m i 血培o fg l o b a ls e q u e n t i a lp a l t e m ) o nd i s 仃i b u t e ds y s t e mi sp r o p o s e d t h ei d e ao fn l i sa l g o r i l mi st 0c o m p r e s sl o c a l6 e q u e n t q u e m i a lp a t k m l si i l _ t oas i m p l e l e x i c o g 唧l l i cs e q u e n c e 仃e e ，a v o i d 仃a n s l i l i s s i o no fr e p e a t e dp r e f i x e s b a s i n go nm e 阳g u l a ra n ds i i l l p l es e q u e n c e so fm e 玛e d 仃s ，an e w i 培m 甜l o dt h a ti s e ( i t e m e ) ( t e n s i o na n ds e q u e n c ee x t e n s i o n ) p r i l i l i n gi sp r e s e m e dt 0p m n ec a n d i i i a t es e q u e n c e s e 虢c t 叫l y t h e r e f o r e ，c o i n m u l l i c a t i o no v e r h e a di sr e d u c e dg r e a t l yt 0g e i l c m t eg l o b a l q u e m i a lp a 位e n 塔e a e c t i v e l y t h et h e o 巧锄de x p e r i m e n t ss h o w l 砒t h ep e r f l o m l 锄【c e o ff m g s pi sp r c d o i i l i l l 觚t ，趾di ti se 虢c 砌w h e nm m g l o b a l q u e n t i a lp a t t e n l sf o r h u g e 锄。眦t o f 3 ) w | ep r e s e n tad i s t r i b u t e d 印p r o x i m a t em i i l i i 玛a l g o r i t h mf o rm u l t i d i m e n s i o n a l q u e n t i a lp a n 肌坞c a l l e da m s p ( a p p r o x i i i l a t em i i l i l l go fg l o b a lm m t i d i m e n s i o 试 s e q u e n t i a lp a t b e 玎峪) t 0s o l v et l l ep r o b l e mo fm i i l i r 培t h en m l t i d i m e n s i o n a l q u e m i a l p a t t e n 塔i l ll 鹕e 出以b 硒e si nt h ed i s t r i b u t e de n v i r o m n e n t f i r s t ，t h em u l t i d i m e n s i o r l a l m f o m l a t i o ni se m b e d d e di r l t 0m ec o 仃e s p o n d i n gs e q u e n c e si no r d e rt 0c o n v e nt l l e m i l l i n go nm em u h i d i i i l e i l s i o n a ls e q u e n t i mp a 舵r n st os e q u e n t i a lp a n e m s t h e nt t l e q u e i l c e sa r ec l l l s t e r e d ，鲫i i i 】啪a r i z e d ，觚d 锄a l y z e do nm ed i s t r i b u t e ds i t e s ，砒l dt h el o c a l p 舭c o i l l db eo b t a i n e db ym ee 仃e c t i v e 印p r o x i m a t es e q u e n t 诫p a t t e mm 询皿g m e t h o d f i i i a l l y n l eg l o b a lm u l t i d i m e l l s i o n ms e q u e n t i a lp a t t e m sc o u l db em i n e dv i at l l e m o d e lo fl l i 曲v o t e 辩q u e 而mp a 舵m 啦e rc o l l e c t i n ga l lt h el o c a lp a t t e 傩0 no n es i t e b 础t l l et l l e o r i e s 锄dm ee x p e r i m e n t ss h o wt h a tt 1 1 i sm e m o dc o u l ds i i n p l i 匆t l l ep r o b l e m o fm i i l i n g l em u l t i d i m e l l s i o n a l q u e n t i a lp a ：t t e n 塔趾da v o i dm i l l i i 培t ：h e 陀d u n d a n t i n f o m 斌i o n 7 1 1 1 eg l o b a ls e q u e n t i a lp a ：t t e r 璐c o u l db eo b t a i n e de 毹c t i v e l yb yt h es c a l a b l e m e m o d 加r e d u c i i l gm ec o s to fc o m m u n i c a t i o n k 叻啊o r d s ： d a ：t a m i n i i 增； d i s t r i b u t e d s e q u e n t i a lp a t t e n 塔； m u l t i d i i n e n s i o l l a l i l l f o m l a t i o n ；印p r o x i m a ：t em i l l i n g 张长海：分布式序列模式挖掘算法研究 5 第一章引言 数据挖掘【l 】就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提 取隐含在其中的、人们事先不知道的但又是潜在有用的信息和知识的过程。数据 挖掘是一种从大型数据库或数据仓库中提取隐藏的预测性信息的新技术。它能开 采出潜在的模式，找出最有价值的信息，指导商业行为或辅助科学研究。数据挖 掘是一门广义的交叉学科，它汇聚了不同领域的研究者尤其是数据库、人工智能、 数理统计、可视化、并行计算等方面的学者和工程技术人员。因此有必要了解数 据挖掘的技术、方法、过程和步骤，并探索其对生物信息数据挖掘的潜在应用或 应用领域。 1 1 研究背景 在信息技术主导的时代，随着数据库技术的不断发展和数据库管理系统的广 泛应用，人们积累的数据越来越多。数据的丰富带来了对强有力的数据分析工具 的需求，大量的数据被描述为“数据丰富，但信息贫乏 。快速增长的海量数据 收集、存放在大型和大量数据库中，没有强有力的工具，结果收集在大型数据库 中的数据变成了“数据坟墓 。于是数据挖掘技术应运而生，并得以蓬勃发展。 数据挖掘工具进行数据分析，可以发现重要的数据模式，对商务决策、知识库、 科学和医学研究做出了巨大贡献。数据和信息之间的鸿沟要求系统地开发数据挖 掘工具，将数据坟墓转换成知识：“金块 。在信息时代来临、互联网高速发展 的今天，随着科技的不断创新，各式各样的数据库系统得到了研究与开发，如一 些时间序列数据库、空间数据库、多媒体数据库等等。尽管目前的数据库系统可 以高效地实现数据的录入、查询、统计等功能，但由于数据量庞大以及数据库系 统中分析方法的严重缺乏，使得它无法发现数据中隐藏的相互联系，更无法根据 当前的数据去预测未来的发展趋势。因此，迫切需要一种从大量数据中提取出隐 藏在其中的有用信息，正是为了这种满足，将机器学习应用于大型数据库中的数 6 扬州大学硕士学位论文 据挖掘技术得到了长足的发展。数据挖掘【2 1 ( d a t am i n i n g 简称d m ) ，有成数据库 中的知识发现( k n o w l e d g ed i s c o v e 巧d a t a b 弱e ，简称k d d ) 是指从大型数据库或者 数据仓库【3 ，4 j 中提取隐含的、未知的、非平凡的及有潜在应用价值的信息或者模式。 例如，某零售业可能积累了大量的原始数据，运用数据挖掘【5 ，6 】技术可以从这些看 似无用的数据中发现规律，找到商机。零售业的利润和风险是共存的，为了保证 利润的最大化和风险的最小化，必须对有关顾客的数据进行科学的整理、分析和 归。采取相应的游魂措施来留住能给商家带来较大经济效益的顾客群，或者根据 顾客的消费模式预测何时为顾客提供何种服务或商品。通过挖掘商家的历史数据： 商品、销售时间、销售地点及商品摆放位置等，对这些数据进行分析，发现其数 据模式及其特征，然后可能发现某类顾客、消费群体的消费兴趣和习惯以及预测 消费市场的变化趋势。 近年来，序列模式挖掘【7 ，8 】成为了数据挖掘的一大研究课题，其应用广泛，包 括顾客购买行为的分析、网络访问模式分析、科学实验的分析、疾病治疗的早期 诊断、自然灾害的预测、d n a 序列模式的分析等等。序列模式挖掘问题是由 s & 埘t 和a g 】认w a l 最早提出的：给定一个序列集，其中每一个序列由项集 构成，然后给定由用户确定的最小支持度阈值( m i n i i n u ms u p p o r t 慨s h o l d ) ，序列模 式挖掘【9 】就是挖掘所有的频繁子序列，即这些子序列的出现频率不小于给定的最小 支持度。例如，“一位顾客买了一台笔记本电脑，一个月内他很有可能买几张光 盘 ，这就是序列模式【l o 】的一个例子。由于很多行业如：电信行业，金融行业， 天气数据等大都与时间相关，即大都是时间序列数据，在针对这些时间相关的数 据分析中，序列模式挖掘很有用途，且非常有前景。然而，现实应用中有很多的 数据是分布式存在的，如：跨区域的大型购物中心数据存储等。因此，分布式序 列模式挖掘【ll 】近年来得到广泛应用。 1 2 课题引出 “知识发现 ( i d ) 一词是1 9 8 9 年在美国底特律召开的第一届l d 国际会 议上正式形成的，随着k d d 在学术界和工业界的影响越来越大，国际i d 组委 会于1 9 9 5 年把专题讨论会更名为国际会议，在加拿大召开了第一届知识发现与数 张长海：分布式序列模式挖掘算法研究 7 据挖掘国际会议。国内研究数据挖掘则起步较晚，目前进行的大多数研究项目是 由政府资助的，如国家自然科学基金、8 6 3 计划、“十五”计划等。 序列模式挖掘是对关联规则挖掘【1 2 ，1 3 1 的进一步推广，很多关联规则挖掘【i 4 ，1 5 】 研究都有助于挖掘序列模式或者与时间相关的频繁模式【1 6 】。r s 蛐和r a g 删对序列规定了时间限制、滑动时间窗口和用户规定的分类，并在该文中总 结了序列模式的定义，提出了一种基于a p r i o r i 的改进算法g s p 【r 飞g e l l e r 试i z e d s e q u e n t i a lp a 吮m s ) 算法。后来m z a l 【i 等人提出了一种基于垂直格式存储的序列模 式挖掘方法s p a d e 算法【1 8 j ，这个算法是由基于垂直格式的频繁项目集挖掘演化而 来。近几年j h a 坞j p e i 等人又提出了一种基于投影的模式增长的算法f 玎e e s p 锄 算法【1 9 1 ，这个算法改进后为p r e f i x s p 觚算法【2 0 】，性能进一步提高。h m 锄i l a 等人 提出了挖掘频繁片段序列问题【2 l 】，后来又提出基于规则表达式约束的序列模式挖 掘【2 2 ，2 3 洲，为了减少冗余模式，j h 肌等人闭项集挖掘【2 5 ，2 6 】的基础上提出了挖掘闭 项序列模式问题【2 7 ，2 8 刎。对于海量数据，挖掘模式可以选取代表模式，于是有人提 出关于序列模式近似挖掘的问题，还有关于用垂直位图表示数据库的序列模式挖 掘研究。近来关于最大项目集挖掘算法【3 叼1 】的研究也不少，如：m a x m 衙、 d e t l p r o j e c t 、m a f 认和g e i n 订a x 等，基于最大项目集挖掘有人提出了挖掘最大序 列模式口2 3 3 川。2 0 0 1 年h p i n t 0 等人提出的u n i s e q 算法能有效地挖掘多维序列模 式。主要思想就是将原来序列勺l 龙，驴添加丰富信息，转换成为呈( t i d ， a l ，a 曲，s ) 格式，其中t i d 是主键，a l ，a 衄是维度，s 表示序列。但在维度较高时 其挖掘性能就会下降。后来同作者又提出p s f p 和h y b d 算法来挖掘多维序列 模式【3 5 3 6 册，有效地解决了高维度问题。基于这种多维序列模式挖掘，后人又提出 了很多相关的挖掘算法来解决相应问题。但由于分布式环境中数据量大且分散， 挖掘全局多维序列模式这些算法性能不高，只有分布式或者并行数据挖掘技术 【3 8 3 9 删才能解决效率问题。为此，s c z l 姗g 等人提出了基于分布式的多数据库挖 掘，随后多数据源中挖掘全局关联规则和全局异常模式也被提出，近来由h c k l m 又提出了多数据库中挖掘全局序列模式。其中，对序列模式附加权重信息 【4 1 ，4 2 】，比如：挖掘超市购物可以附加价格作为权重，即所谓的权重序列模式挖掘【4 3 1 。 对超市购物例子，可能过短时间要添加新商品m ，4 5 】，为此，单机和分布式环境下 8 扬州大学硕士学位论文 序列模式挖掘算法更新问题，4 7 ，4 8 1 同样具有重要意义。 近来为了解决分布式环境下序列模式挖掘这一问题，人们也提出了一系列相 关的研究。如在树投影基础上提出的几种新的基于分布存储的并行挖掘序列模式 算法【4 9 j ：s t p f 算法和d t p f 算法，r a g r a l w a l 等人提出了c d 算法，该算法实质 是对a p r i o r i 算法的并行化来挖掘关联规则1 5 0 】。为了避免过多的冗余信息，国内有 人提出了全局最大项目集的挖掘，该算法在不丢失信息的情况下减少了数据量。 d wc h e u l l g ，j h a i l 等人提出了f d m ( f 奴d i 嘶b u t e do fm i i l i n ga s s o c i a t i o nr u l e s ) 算 法，用来解决分布式环境下关联规则挖掘的问题。基于f d m 算法有人提出 f d m s p ( f 奴d i s t r i b u t e d1 1 1 i i l i n go fs e q u e n t i a lp a t t e m s ) 算法，该算法吸取f d m 算法的 精华，采用序列模式前缀指定选举站点来统计全局计数，从而获得全局序列模式， 为决策者提供有价值信息。2 0 0 5 年j h a l l 等人提出了并行挖掘闭项序列模式，这 大大提高了挖掘的效率。目前很多专家已着手对并行与分布式数据挖掘技术【5 l ，5 2 】 进行研究，从而使基于分布式环境下海量数据的序列模式挖掘也将成为今后数据 库领域的研究热点之一。 不过分布式序列模式挖掘有着它自身的挑战性，因为在各站点很容易挖掘局 部序列模式，但是这些局部序列模式并不一定是决策者想要的全局序列模式，并 且序列元素是有序的，由此产生的候选序列数目也是惊人的。目前与分布式序列 模式挖掘相关的研究也不少，文献 4 9 】中vg l l r a l i l i k 在树投影基础上提出了几种新 的基于分布存储的并行挖掘序列模式算法：s t p f 算法和d t p f 算法。j s p a r k 提 出了p d m 算法，文献【5 0 中r a 删提出的c d 算法，该算法实质是对a p r i 耐 算法的并行化来挖掘关联规则。为了避免过多的冗余信息，j p l u 等人提出了全 局最大项目集的挖掘，该算法在不丢失信息的情况下减少了数据量。d w c h e u i l g 又提出了f d m ( f 破d i g t r i b u t e do fm i l l i n g 勰s o c i a t i o nm l e s ) 算法【5 3 l ，用来解决分布式 环境下关联规则挖掘的问题。后来，m 培等人提出了f m a g f 算法，它采用传 送条件频繁模式树或条件模式基来挖掘全局频繁项目集，有效地减小了网络通信 量。近来人们又提出了f d m s p ( f ；波d i s t r i b u t e d 血n i n go f q u e m i a lp a t t e m s ) 算法， 该算法吸取f d m 算法的精华，采用序列模式前缀指定选举站点来统计全局计数， 从而获得全局序列模式。但是该算法在各分站点的序列被分配到选举站点时需要 张长海：分布式序列模式挖掘算法研究 9 传输的数据量相当大，而且合并子树后经过全局约减的候选序列数量也是相当大。 为此，本文中提出了解决分布式数据挖掘的方法。 1 3 论文的主要工作 在论文中我们首先介绍了序列模式相关概念及其应用，展望了当前序列模式 挖掘的研究热点和研究现状。然后对分布式序列模式作了具体的介绍，在借鉴国 内外在序列模式和数据挖掘处理方面的已有成果的基础上，设计优化的分布式序 列模式挖掘算法，以解决分布式环境下挖掘序列模式冗余数据大而导致的传输速 度慢而且网络通信代价高的难题。对其中局部序列模式挖掘和压缩、候选序列剪 枝、近似序列挖掘、多维序列模式挖掘等热点问题进行研究，提出自己见解或者 解决方案，为分布式环境挖掘序列模式提供实际可用的办法。 本文的主要研究工作及成果如下： 1 ) 如何在大型事务数据库中挖掘有价值的序列数据已成为当前研究的热点。 为此，提出一种基于位图挖掘算法s m b r ( q u e n t i a lp a 仕e m sm i n i n gb 嬲e d0 nb i 缸i l a p r 印r e s e n t a t i o n ) 以解决序列模式挖掘问题。算法s m b r 采用位图表示数据库的方法， 提出一种简化的位图表示结构。该算法首先由序列扩展和项扩展产生候选序列， 然后通过原序列位图和被扩展项位图位置快速运算生成频繁序列。在大型事务数 据库中，该方法不仅有效地提高了挖掘效率，而且挖掘处理过程中产生的临时数 据所需的内存大大降低，能够高效地挖掘序列模式，具备可行性。 2 ) 分布式环境下降低网络通信代价是挖掘全局序列模式的关键。为此，提出 一种基于分布式环境下的挖掘全局序列模式算法f m g s p ( f 弧m i i l i 】n go fg l o b a l s e c l 啪t i a lp a t 胁) 。f m g s p 算法首先采用模式增长的方式挖掘局部序列模式，然后 将各站点得到的局部序列模式压缩到一种语法序列树上，避免了重复的序列前缀 传输；并且基于合并树中结点序列规则、简单的特点，提出一种剪枝策略，有效 地约减了候选序列，能够快速生成全局序列模式。有效地降低了网络传输量。 3 ) 为了解决分布式环境中挖掘多维序列模式通信代价大、维度高等难题，本 文提出一种近似挖掘序列模式的算法a m s p ( a p p r o x h a t em i r 衄o fg l o b a l m u l t i d i m e n s i o r 谢s e q u e n t i a lp a 慨加s ) 。该方法不同于传统的分布式多维序列模式挖 1 0 扬州大学硕士学位论文 掘方法，具备较好的伸缩性。首先将维度信息嵌入相应序列中，使多维序列模式 挖掘转化为序列模式挖掘；然后在各分站点对转换后序列聚类、概化和分析，采 用有效的近似挖掘方法获得局部模式；最后集中所有局部模式，通过高频度序列 模式模型挖掘全局多维序列模式，能够有效地生成全局多维序列模式。 1 4 论文组织 以下章节内容组织如下： 第二章主要介绍了数据挖掘和序列模式挖掘的基本概念。 第三章给出了基于位图序列模式挖掘的解决方案。 第四章提出分布式序列模式挖掘算法f m g s p ( f 弧tm i 毗唱o fg l o b 出q u e m i a l p a t t e n l ) 。 第五章给出了分布式序列模式的近似挖掘解决方a m s p 算法( a p p r o x i i i l a 钯 m i i l i n go fg l o b a l lm u l t i d 妇e 1 1 s i o n a ls e q u e n t i a lp 龇锄1 s ) 。 最后，第六章是论文的总结和研究工作的展望。 张长海：分布式序列模式挖掘算法研究 1 1 第二章基本理论 帚一早昼令埋了匕 本章首先介绍序列模式挖掘相关基本概念及基本思想，在此基础上扩展到多 维序列模式挖掘和基于位图序列模式挖掘。然后基于分布式序列模式挖掘需求， 介绍分布式频繁项目集挖掘和分布式序列模式挖掘的相关概念和基本思想，为在 分布式环境下挖掘序列模式奠定基础。 2 1 序列模式挖掘问题描述 2 1 1 序列模式挖掘 目前的主要序列模式挖掘算法可以分为三类：第1 类是基于a p r i o r i 的候选码生 成测试的方法，第2 类是基于垂直格式的候选码生成一测试的方法，第3 类是基于模 式增长的方法酬。前2 类方法产生巨大候选序列致使挖掘代价剧增，而模式增长方 法避免候选序列产生，但是挖掘较长模式1 5 5 】效率不高。 关于序列模式挖掘基本概念如下： 设，= f l ，屯，厶) 是一个项目集合，项目集或者项集( i t e m s ) 就是各种项目组成 的集合，即i 的所有子集。一个序列就是若干个项目集的有序列表，一个序列s 可表示为勺l 也，驴，其中研为项集，也称作s 的元素。元素由不同的项目组成， 可表示为 l 规，而) 。当元素只包含一项时，一般省去括号。如他) 一般表示为砣 元素之间是有顺序的，但元素内的项是无序的，一般定义为词典序。序列包含项 的个数称为序列的长度，长度为的序列记为三序列。序列数据库就是元组 ( t u p l e s ) 和户 ，当且仅当l g i ，2 q 蜘且口l 互易l ，眈如，的时候，称序列声为序列的超序列，序列a 为序列的子序列，又称序列包含序列仅，记作a s 。如表2 1 所示。 这个序列，其中 、 都是 的子序列， 是 ， 的超序列。 定义2 2 序列数据库d 是元组 s i d ，p 的集合，s i d 为序列标识号。如果序列r 是s 的子序列( 即延s ) ，称元组 s i d ，p 包含序列乃则序列丁在序列数据库d 中 的支持数是数据库中包含r 的元组数，即s z 印口仍= i s i d ，p i i ， 记作s 卿d 仞。 定义2 3 给定一个最小支持度阈值册泐妒，如果序列j 的支持度不小于 聊协妒，则称序列s 为频繁序列模式，所有的频繁序列模式集合记作殿。如表2 1 所示。 这个序列分别在l o 和4 0 序列出现2 次，所以其支持数为2 。假设用 户规定m 泐矿2 ，可知 序列是频繁序列模式。 定义2 4 假定每个元素中的项目是按照词典序来排列的，给定序列a = 勺l ，p 2 ，p 户妒心1 7 ，p2 ，p 如) ，如果p 角f ( 脚1 ) ，并且( 一p ) 中 的项目均需在p 中项目的后面，则称声是a 的前缀。 定义2 5 给定序列a 和，如果是a 的子序列，则n 关于j 6 f 的投影需要 满足厣是的前缀，是a 的满足上述条件的最大子序列。 定义2 6 序列a 关于子序列伊：勺l ，p 2 ，pm - 1 7 ，移的投影为止pl ，p 2 ，p 户 ( 睑聊) ，则序列口关于子序列的后缀为 ，习f b = l 。 性质2 1( a p r i o r i 性质) 如果一个序列s 的支持度小于聊f 凇印，也就是不频 繁的序列模式，那么该序列s 的任何超序列都是不频繁的序列。 如表2 1 所示。假设用户设定的最小支持度为2 ，表2 1 中序列 仅在 s i d 为1 0 的序列出现一次，所以非频繁。由性质2 1 可知：其超序列 ， 等都是非频繁的。利用这一性质可以减少搜索空间。 关于三类序列模式挖掘算法思想： 1 ) a g r a l w m 和s r i k 锄t 所提出的大多数序列模式挖掘算法都是基于a p r i 嘶的 广度优先算法，即基于a 面o r i 性质。例如a p r i o r i 灿l 、g s p ( g e 鹏m l i z e d q u e r l c i a l p a 仕e m ) 算法等等。本章主要介绍g s p 算法，其思想如下： 第一步：扫描数据库一次，找出所有的频繁1 序列。 第二步：利用频繁1 序列来产生候选2 序列，再次扫描数据库给候选序列计 数，找出满足最小支持度的频繁2 序列。 第三步：用频繁k 序列( k 2 ) 来产生候选k + 1 序列，扫描数据库找出频繁k + l 序列。 第四步：重复第三步，直到没有候选序列产生为止。 这类算法有其本身固有的三大缺点：一 第一，大型数据库中会有相当多的候选序列产生。因为序列中的元素是有序 的，所以不同元素的交换就会产生很多不同的序列。 第二，挖掘过程中要多次扫描数据库。候选序列的长度每增加为一，就需要 扫描一次数据库。 第三，挖掘较长模式的时会产生很多候选序列。 1 4 扬州大学硕士学位论文 2 ) 基于垂直格式的候选码生成测试的典型算法s p a e d 算法，在2 0 0 1 年由 z a k i 提出。该算法为了便于挖掘序列模式将垂直序列数据库影射为一些i d 1 i s t s 。 其思想如下： 第一步：首先需要扫面数据库一次，找出所有的候选1 序列，然后用s i d 和 e i d 来标示每一个候选1 序列，从而产生长度为1 的i d 1 i s t ，关于a 和b 的i d 1 i s t s ， 在图中简单地清点每一元素行数就可得知其支持度，从而产生频繁1 序列。 第二步：对于候选2 序列生成利用任意两个频繁1 序列i d 号的简单链接来产 生候选2 序列，同样计数产生频繁2 序列。 第三步：依次执行，一直到不产生候选序列为止。 该类算法的最大优点就是扫描数据库次数大大减少以及计数快捷简单。整个 挖掘过程仅需要扫描三次数据库。数据库格式转换和产生频繁1 序列时分别扫描 一次，挖掘2 序列时，数据库需要从垂直格式再转换为水平格式，还需要一次扫 描。不过此类算法基本遍历方法仍然是广度优先遍历，且忍受着巨大候选码的代 价。 3 ) 模式增长方法是由j p e i 、j h 孤等人提出的，这类算法是一种基于投影的、 分治的和模式增长的方法，也就是序列数据库被投影为很多小投影数据库，然后 在小投影数据库中进行递归挖掘。最早提出的f r e e s p a n 算法，该算法由于投影数据 库的尺寸迅速减小，在这些小的数据库上进行工作简单易行，相比基于a 研o r i 性 质的g s p 算法有着明显的优势。f r e e s p a i l 算法将大的序列数据库根据已挖掘出的频 繁序列递归地投影为一组小的数据库，再继续挖掘子序列。f r e e s p a i l 算法的缺点就 是该算法可能要产生许多非平凡的投影数据库。如果一个模式在序列数据库中每 个序列都出现，其投影数据库就不会缩小( 去掉非频繁项除外) 。另外，因为l k 子序列可能在序列的任意位置增长，所以对l ( 1 【+ 1 ) 序列的搜索将需要检查所有的可 能位