（计算机应用技术专业论文）序列模糊概念格模型及其分布处理研究.pdf

袁运浩：序列模糊概念格模型及其分布处理研究 摘要 随着社会经济与科学技术的发展，信息技术得到了广泛的应用，许多领域积 累了大量的数据，迫切需要一种新技术与工具来帮助人们快速地从海量的数据中 找出重要的有价值的信息，数据挖掘技术就是基于这种背景应运而生。而作为数 据挖掘的一个重要研究内容一序列模式挖掘，已经得到了许多研究，提出了许多 有关序列模式挖掘的算法，如a p r i o r i a l l 算法、s p a d e 算法以及p r i f i x s p a n 算法等 等，而且序列模式挖掘在许多领域得到了广泛的应用，如顾客购买行为分析、w e b 访问模式分析以及d n a 序列分析等等。 但是，目前已经提出的许多序列模式挖掘算法仅仅是挖掘出满足用户指定的 最小支持度m i n s u p 的序列模式，并没有考虑序列模式的重要性，即虽算法挖掘出 的所有的序列模式都满足用户指定最小支持度m i n s u p ，但用户可能更关注比较重 要的序列模式，它们虽然不能满足用户指定最小支持度，但是这些序列对用户来 说比较有价值；相反地，有些序列模式可能对用户来说重要程度并不是很大，并 不需要挖掘，这就需要算法能够自适应地调整以挖掘出符合用户需求的序列模式， 但已提出的挖掘算法没有考虑这种特征，无法挖掘出这样的序列模式。 由于形式概念分析中的概念格模型只需访问一次数据库就可构建成功，并且它 的知识与层次表达能力强，将序列引入概念格中，只需存储最大公共子序列，减 少了冗余序列的产生。为此，本文对序列模式挖掘与模糊概念格的结合进行了系 统的研究，主要研究成果如下： ( 1 ) 针对目前概念格构造算法在较大规模稀疏的数据集或分布式的数据集上， 生成概念时仍然需要耗费大量的时间，本文提出了一种基于i e t r e e ( i n t e n s i o na n d e x t e n s i o nt r e e ) 与特征空间划分的概念生成算法i e t r e e c s ( c o n c e p ts e tb a s e do n i n t e n s i o na n de x t e n s i o nt r e e ) 。i e t r e e c s 算法首先将形式背景转为i e t r e e ，减少了 数据集的存储量；然后该算法在i e t r e e 的基础上进行了特征空间的描述与划分， 最后给出了完整的i e t r e e c s 算法。实验结果表明该算法在较大规模稀疏的数据集 或分布式的数据集上性能优越，有明显地提高。同时，i e t r e e c s 算法也为序列模 2 扬州大学硕士学位论文 糊概念格的构建提供了算法支持。 ( 2 ) 为了组织与挖掘有价值的满足多需求的序列模式，本文提出了一种序列 模糊概念格模型，并给出了序列模糊概念格的构造算法s e q f u z c l ( s e q u e n c ef u z z y c o n c e p tl a t t i c e ) 。在传统的模糊形式背景的基础上，本文将其在序列上进行了扩展， 定义了序列模糊形式背景；利用扩展的序列模糊形式背景，定义了概念的g a l o i s 闭包连接、序列模糊概念及其格结构，最后给出了序列模糊概念格的构建算法 s e q f u z c l 。通过实验表明，序列模糊概念格模型不仅可以方便有效的组织自适应 序列模式，在时间与空间上都具有良好的性能，而且还可以在序列模糊概念格上 挖掘传统意义下的序列模式，同时，为进一步挖掘自适应序列模式提供了理论支 持。 ( 3 ) 由于在实际应用中，许多大型数据库是以分布式的形式存在的，为了能 够有效与方便地处理分布环境下的序列，本文在序列模糊概念格的基础上提出了 分布序列模糊概念格模型及其构建算法d s e q f u z c l ( d i s t r i b u t e ds e q u e n c ef u z z y c o n c e p tl a t t i c e ) 。在分布序列模糊概念格模型上，不仅可以有效挖掘分布序列模式， 而且还可以挖掘满足用户多需求的特殊分布序列模式，如分布加权序列模式等。 通过实验证明，本文提出的分布序列模糊概念格构建算法d s e q f u z c l 具有良好的 时间与空间性能。 ( 4 ) 在序列模糊概念格的基础上，利用序列权重与序列的重要度阈值，本文 定义了序列自适应系数及其自适应序列模式s a s p ( s e l f - a d a p t i v es e q u e n c ep a t t e r n ) ， 给出了基于序列模糊格的自适应序列模式的发现算法s a s e q p ( s e l f - a d a p t i v e s e q u e n c ep a t t e r n ) 。它可以自适应地调整用户指定的最小支持度m i n s u p ，以挖掘出 满足用户需求的特别有价值的序列模式。 关键词：形式概念分析；概念格；模糊形式背景；模糊概念格；数据挖掘； 序列模式挖掘；分布序列模式 袁运浩：序列模糊概念格模型及其分布处理研究 3 a b s t r a c t w i t ht h ed e v e l o p m e n to fs o c i o - e c o n o m i ca n ds c i e n c et e c h n o l o g y , i n f o r m a t i o n t e c h n o l o g ya c q u i r e se x t e n s i v ea p p l i c a t i o n s m a n yf i e l d sh a v ea c c u m u l a t e da b u n d a n t d a t a ；t h e r e f o r e ，p e o p l en e e dan e wt e c h n o l o g ya n dt o o lt oh e l pt h e md i s c o v e rt h e i m p o r t a n ta n dv a l u a b l ei n f o r m a t i o n i nt h i sc a s e ，d a t am i n i n gt e c h n i q u ei sp r e s e n t e dt o s o l v et h ea b o u t - m e n t i o n e dp r o b l e m a sa ni m p o r t a n tr e s e a r c ho fd a t am i n i n g ，s e q u e n c e p a t t e r nm i n i n gh a sg a i n e dl o t so fr e s e a r c h e s a tp r e s e n t ，m a n ys c h o l a r sa th o m ea n d a b r o a dh a v ep r e s e n t e dv a r i o u sa l g o r i t h m st od e t e c ts e q u e n c ep a t t e r n s f o re x a m p l e ， a p r i o r i a ua l g o r i t h m ，s p a d ea l g o r i t h ma n dp r i f i x s p a na l g o r i t h m ，a n ds oo n a n d s e q u e n c ep a t t e r nm i n i n gh a sb e e nw i d e l ya p p l i e di nt h ea c t i o na n a l y s i so fc u s t o m e r b u y i n g ，a n a l y s i so fn e t w o r kv i s i t i n g ，a n a l y s i so fd n as e q u e n c ep a t t e r n s ，a n do t h e r f i e l d s h o w e v e r ，c u r r e n ta l g o r i t h m sf o rm i n i n gs e q u e n c ep a a e m sa l eo n l ya b l et od i s c o v e r t h ef r e q u e n ts e q u e n c e ss a t i s f y i n gt h em i n i m u ms u p p o r tt h r e s h o l dm i n s u p n e v e r t h e l e s s ， t h e s em e t h o d sd o n tc o n s i d e rt h ei m p o r t a n c eo fs e q u e n c e sa n di t e m s ，i e ，m o s to ft h e f r e q u e n ts e q u e n c e sw h i c ha b o v e - m e n t i o n e da l g o r i t h m sd e t e c tm a yb eu n i m p o r t a n tf o r u s e r s a t t e n t i o n t h o u g hs o m es e q u e n c e sd o n ts a t i s f yt h em i n i m u ms u p p o r tt h r e s h o l d m i n s u p ，t h e ya l ev e r yv a l u a b l ef o ru s e r s c o n t r a r i l y , s o m es e q u e n c ep a t t e r n sa r en o ts o i m p o r t a n tf o ru s e r s d e m a n dt h a tt h e yd o n tn e e dt ob ed e t e c t e d t h e r e f o r e ，i ti sv e r y e s s e n t i a lf o ra l g o r i t h m sm i n i n gs e q u e n c ep a t t e r n st oa d j u s ts e l f - a d a p t i v e l yt od e t e c t s e q u e n c ep a t t e m so fs a t i s f y i n gu s e r s r e q u i r e h o w e v e r , c u r r e n te x i s t i n gm i n i n g a l g o r i t h m sd o n tt a k ea c c o u n to ft h ef e a t u r en o tt om i n et h ef r e q u e n ts e q u e n c e sm e e t i n g u s e r s n e e d s b e c a u s et h ec o n c e p tl a t t i c ei nf o r m a lc o n c e p ta n a l y s i so n l ys c a n so n c ei nd a t a b a s e t os u c c e s s f u l l yc o n s t r u c tl a t t i c es t r u c t u r e a n di tm a ys t r o n g l yd e s c r i b ek n o w l e d g ea n d h i e r a r c h i c a lr e l a t i o nb e t w e e nc o n c e p t i o n s i to n l yn e e d st os t o r et h em a x i m a lc o m m o n 4 扬州大学硕士学位论文 s u b s e q u e n c ei nc o n c e p tl a t t i c e a sar e s u l t ，c o n c e p tl a t t i c em a yr e d u c et h eg e n e r a t i o no f r e d u n d a n ts e q u e n c e st os a v em u c hs p a c e t h e r e f o r e ，t h i sp a p e rc o n d u c t sas y s t e m a t i c s t u d yf o rt h ec o m b i n a t i o no fs e q u e n c ep a t t e r nm i n i n ga n df u z z yc o n c e p tl a t t i c e t h e m a i nr e s e a r c hr e s u l t sa r ea sf o l l o w s ： ( 1 ) f o rc u r r e n ta l g o r i t h m sf o rb u i l d i n gc o n c e p tl a t t i c es t i l lc o n s u m em u c ht i m et o g e n e r a t ec o n c e p t si nt h el a r g e s c a l es p a r s ed a t as e t so rd i s t r i b u t e dd a t as e t s ，t h i sp a p e r p r e s e n t san e wa l g o r i t h mc a l l e di e t r e e c s ( c o n c e p ts e t sb a s e do ni n t e n s i o na n d e x t e n s i o nt r e e ) b a s e do nt h e i e t r e e ( i n t e n s i o na n d e x t e n s i o nt r e e ) a n dt h e c h a r a c t e r i s t i cs p a c ep a r t i t i o n t h ei e t r e e c sa l g o r i t h mf i r s t l yd e f i n e sa ni e t r e e ，t h e ni t c o n v e r t sf o r m a lc o n t e x ti n t oi e t r e et or e d u c et h es t o r a g eo fd a t as e t s ，i e ，t h ei e t r e e c a nr e d u c et h es t o r a g eo ft h ef o r m a lc o n t e x t a n dt h e nt h ei e t r e e c sa l g o r i t h mg i v e sa d e f i n i t i o na b o u tt h ec h a r a c t e r i s t i cs p a c ea n dd e s c r i b e sh o wt op a r t i t i o nac h a r a c t e r i s t i c s p a c eo nt h eb a s i so ft h ei e t r e e a tl a s t ，t h ep a p e rp r e s e n t st h ei n t e g r a t e di e t r e e c s a l g o r i t h mt h a tg e n e r a t e sa l lc o n c e p t sf r o mab i n a r yr e l a t i o n t h ee x p e r i m e n t a lr e s u l t s s h o wt h a tt h ei e t r e e c sa l g o r i t h mp e r f o r m sm o r ee f f i c i e n tt h a nt h en e x t c l o s u r ea n d s s p c ga l g o r i t h m sf r o mt h el a r g e - s c a l es p a r s ed a t as e t so rd i s t r i b u t e dd a t as e t s s i m u l t a n e o u s l y , i e t r e e c sa l g o r i t h mp r o v i d e sa l g o r i t h m i cs u p p o r tf o rc o n s t r u c t i n g s e q u e n c ef u z z yc o n c e p tl a t t i c e ( 2 ) f o rt h es a k eo fo r g a n i z i n ga n dm i n i n gv a l u a b l es e q u e n c ep a t t e r n ss a t i s f y i n g u s e r sv a r i o u sr e q u i r e s ，t h i sp a p e rp r e s e n t san e ws e q u e n c ef u z z yc o n c e p tl a t t i c em o d e l b a s e do nt r a d i t i o n a lf u z z yf o r m a lc o n t e x t ，w ee x t e n di tt oe x p r e s ss e q u e n c e si nb r i e f , a n dg i v eo u tad e f i n i t i o no fs e q u e n c ef u z z yf o r m a lc o n t e x t m a k i n gu s eo ft h es e q u e n c e f u z z yf o r m a lc o n t e x t ，g a l o i sc o n n e c t i o n , s e q u e n c ef u z z yc o n c e p t i o na n ds e q u e n c ef u z z y c o n c e p tl a t t i c ea r ed e f i n e di nt h ep a p e r a tl a s t ，t h i sa r t i c l ep r e s e n t st h ei n c r e m e n t a l c o n s t r u c t i o na l g o r i t h ms e q f u z c l ( s e q u e n c ef u z z yc o n c e p tl a t t i c e ) o ft h es e q u e n c e f u z z yc o n c e p tl a t t i c e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h ms e q f u z c lc a n e f f e c t i v e l ye x p r e s ss e l f - a d a p t i v es e q u e n c ep a t t e m si nt h el a t t i c e ，a n dh a se x c e l l e n t p e r f o r m a n c eo nt h et i m e - s p a t i a lc o m p l e x i t y s i m u l t a n e o u s l y , t h em o d e lp r o v i d e s t h e o r e t i cs u p p o r tf o rm i n i n gs e l f - a d a p t i v es e q u e n c ep a t t e r n s 袁运浩：序列模糊概念格模型及其分布处理研究 5 ( 3 ) a c t u a u y , al a r g en u m b e ro fl a r g ed a t a b a s ea r es t o r e di nt h ed i s t r i b u t e ds y s t e m t h u s ，s e q u e n c e sa l s oe x i s t i nt h ed i s t r i b u t e dc o n d i t i o n i no r d e rt oh a n d l ed i s t r i b u t e d s e q u e n c ee f f i c i e n t l ya n dc o n v e n i e n t l y , t h i ep a p e rp u t sf o r w a r dad i s t r i b u t e ds e q u e n c e f u z z yc o n c e p tl a t t i c em o d e lo nt h eb a s i so fs e q u e n c ef u z z yc o n c e p tl a t t i c ea n dp r e s e n t sa b u i l d i n ga l g o r i t h md s e q f u z c l ( d i s t r i b u t e ds e q u e n c ef u z z yc o n c e p tl a t t i c e ) i n d i s t r i b u t e ds e q u e n c ef u z z yc o n c e p tl a t t i c e ，a l g o r i t h md s e q f u z c lc a l ln o to n l yd i s c o v e r d i s t r i b u t e ds e q u e n t i a lp a t t e r n s ，b u ta l s om i n i n gs p e c i f i cd i s t r i b u t e ds e q u e n t i a lp a t t e m s s a t i s f y i n gu s e r sv a r i o u sd e m a n d s ，f o ri n s t a n c e ，w e i g h t e ds e q u e n c ep a t t e r n s t h e e x p e r i m e n t a lr e s u l t ss h o wt h a ta l g o r i t h md s e q f u z c lh a se x c e l l e n tp e r f o r m a n c eo n t h e t i m e - s p a t i a lc o m p l e x i t y ( 4 ) o nt h eb a s i so fs e q u e n c ef u z z yc o n c e p tl a t t i c e ，t h i sp a p e rd e f i n es e l f - a d a p t i v e c o e f f i c i e n ta n ds e l f - a d a p t i v es e q u e n c ep a t t e r n ss a s p ( s e l f - a d a p t i v es e q u e n c ep a t t e m ) ， a n dt h e nw ep r e s e n tan e wa l g o r i t h ms a s e q p ( s e l f - a d a p t i v es e q u e n c ep a t t e r n ) f o r m i n i n gs e l f - a d a p t i v es e q u e n c ep a a e m sb a s e do ns e q u e n c ef u z z yc o n c e p t l a t t i c e a l g o r i t h ms a s e q pm a yd y n a m i c a l l ya d j u s tt h em i n i m u ms u p p o r tt h r e s h o l dm i n s u pb y s e l f - a d a p t i v ec o e f f i c i e n tt od i s c o v e rv e r yv a l u a l es e q u e n t i a lp a t t e m sf o ru s e r s k e y w o r d s ：f o r m a lc o n c e p ta n a l y s i s ；c o n c e p tl a t t i c e ；f u z z yf o r m a lc o n t e x t ；f u z z y c o n c e p tl a t t i c e ；d a t am i n i n g ；s e q u e n c ep a t t e mm i n i n g ；d i s t r i b u t e ds e q u e n c ep a t t e m 袁运浩：序列模糊概念格模型及其分布处理研究 1 0 3 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 撇签名薏主讫 签字日期：年月z 日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。 本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学 技术信息研究所将本学位论文收录到 ：中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 。叶 糊一躲需艺汔名：专多 签字日期：、筘穸年莎月力日 签字日期： 。j 年6 月砂日 | 、 ( 本页为学位论文采页。如论文为密件可不授权，但论文原创必须声明。) 袁运浩：序列模糊概念格模型及其分布处理研究 7 第一章绪论 1 1 论文研究背景与选题依据 随着社会经济与科学技术的发展，信息技术得到了广泛的应用，数据库作为 信息技术的重要组成部分，在各个领域也得到了大量的使用。近年来，数据库的 规模与数量获得了急速增长，在这个过程中，许多领域积累了大量的数据，迫切 需要一种新技术与工具来帮助人们快速地从海量的数据中找出重要的有价值的信 息，数据挖掘技术就是基于这种背景应运而生。 数据挖掘【l j 作为数据库中知识发现k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 中最核心的部分，是根据决策需要，采用具体的算法，从数据库中抽取隐含的、 以前未知的、具有潜在应用价值的信息的过程。目前，数据挖掘的研究主要集中 在分类、聚类、规则发现、异常和趋势发现等方面，其中序列模式挖掘 2 1 已是数据 挖掘研究的热点内容之一。 序列模式挖掘( s e q u e n t i a lp a t t e mm i n i n g ) 问题是由r s r i k a n t 与r a g r a w a l 在 文献【2 】中最先提出的：给定一个序列集，其中每一个序列由项集构成，然后给定由 用户确定的最小支持度阈值m i n s u p ，序列模式挖掘就是去发现所有满足最小支持 度m i n s u p 的频繁子序列，即从序列数据库中发现频繁子序列以作为模式，它是挖 掘基于时间或者其它顺序的出现频率较高的模式。 在数据库的知识发现中，序列模式经常隐藏着有价值的信息，如对超市而言， 根据顾客的购物清单，可以推断出购物者的某些购买习惯，进而指导超市的销售 策略；在天气预报领域中，分析某地区多年来的历史气象资料，可以发现一些气 候变化规律，进而对天气进行预测；又如在证券市场上，交易价格随时间的变化 存在着某些规律，发现这些规律可以指导证券交易者等。因此序列模式挖掘是非 常有用并且重要的，它具有广阔的应用领域，如顾客购买行为分析、w e b 访问模 式发现、科学实验分析、疾病治疗的早期诊断、自然灾害的预测以及d n a 序列模 式分析等。 8 扬州大学硕士学位论文 近些年来，序列模式挖掘已经得到了许多学者的关注与研究。目前，已经提 出了许多序列模式的挖掘算法，就算法采用的挖掘策略大体可将序列模式挖掘算 法分为两类。一类是基于候选码生成测试的挖掘算法：1 9 9 5 年r s r i k a n t 与 r a g r a w a l 在文献 2 】中最早提出序列模式挖掘问题，并给出了一个序列模式挖掘的 经典算法a p f i o d a l l 。这个算法主要分为三步：算法首先找出所有的频繁项集，然 后转换交易数据库，将交易数据库中所有的事物代之以对应的频繁项集，最后在 转换后的数据库中挖掘所有的序列模式。随后，r s r i k a n t 与r a g r a w a l 又提出了一 个更有效的挖掘算法g s p t 3 1 。m z a k 在1 9 9 8 至2 0 0 2 年期间发表了许多关于序列模 式研究的论文【4 】【5 嗣，并提出了s p a d e 算法【4 】。s p a d e 算法引入格结构来存储序 列模式，并在其中存储序列的i d 表，使用相应的格搜索技术与基于时间的连接操 作，通过三次扫描数据库挖掘所有的序列模式，降低了i o 的数据量。另外还有使 用哈希树组织候选序列的p s p t 7 】算法。 这类基于候选码生成测试的挖掘算法虽然能够发现所有的序列模式，但算法 需要多次扫描数据库，并会产生大量的候选序列，时空复杂度很大。为此以j h a n 与j p e i 等人为代表的学者提出了另一类无须生成候选序列的基于模式增长的发现 算法。如f r e e s p a n 算法【8 】【9 】、p r i f i x s p a n 算法【1 0 1 ，这类算法的基本思想是在数据库 上采用了投影技术，将数据库投影成更小的一组数据库，直接在前缀对应的投影 数据库上挖掘序列模式。 上述两类算法着重挖掘所有的序列模式，这就必然引起挖掘结果呈现指数级 增长，针对这种情况，文献 1 1 1 2 1 研究了只挖掘最大序列与闭序列模式的问题。 此外，算法i s e i l 3 1 与i s m t l 4 1 研究了序列模式的增量更新以及文献 1 5 对分布式序列 模式发现算法进行了研究。 然而上述有关序列模式挖掘算法大多数都需要多次扫描数据库，并且挖掘出 的序列模式之间没有明显的层次性，难于查找用户真正感兴趣的模式。虽然文献 1 3 】 1 4 研究了增量更新的问题，但依然需要访问原有数据库，增加了i o 开销。 形式概念分析【1 6 】( f o r m a lc o n c e p ta n a l y s i s ) 是研究知识表示的领域，它的核 心数据结构一概念格( c o n c e p tl a t t i c e ) ，是对概念以及概念之间关系的描述，它在 一定程度上是对客观世界的一种高度简化的描述形式。这种简化的最大优点是其 袁运浩：序列模糊概念格模型及其分布处理研究 9 具有良好的数学性质。w i l l e 教授在文献 1 6 中基于这种简化，系统地研究了概念 的有序性质、格代数性质以及概念格与形式背景的同构性质，开创了形式概念分 析领域。 由于形式概念分析中的概念格具有鲜明的层次性、简洁的更新操作与良好的 数学性质，使用户能够很方便的组织概念，并且只需访问一次数据库就可构建成 功，因此非常适合于序列模式的组织与挖掘，并可以在其上迅速地查找到用户需 求的序列模式。目前，在国内外的些研究【1 7 】【1 8 1 1 9 j d p ，己将概念格引入到了序列 模式挖掘中。文献【1 7 】【1 8 研究了概念格与序列模式的结合，利用最大公共子串作 为序列概念的内涵，但此方法不能生成自适应或用户真正需求的序列模式，更不 能应用于分布序列模式的表示与挖掘；文献 1 9 提出了另外一种基于概念格的序列 模式挖掘算法，这个算法首先利用( c 协，死d ) 对每个交易进行标识，然后构造概 念格，在得到的概念格中生成频繁1 序列，然后再利用a p r i o r i a u 算法迭代生成频 繁尽序列( p 1 ) ，但实质上该算法生成的概念格并不能表示序列模式。除此之外， 文献【2 0 】也做了类似的研究。文献【2 1 】基于分布式概念格研究了分布式序列模式的 发现，但其构建的概念格不能够真正表示序列，在格上仅能输出频繁1 序列，其 他频繁序列的获得需要借助a p r i o r i a l l 、p r i f i x s p a n 等算法，因此，从严格意义上 考虑，其仍然没有有效解决分布序列模式的挖掘。文献 2 2 2 3 】提出了一种多维概 念格，它是对概念格的延伸与泛化，在此结构上提出了增量式多维序列模式挖掘 算法，但其本质上还是在对单机上的单一关系序列进行简单操作，并不能处理分 布环境下的复杂序列模式。 实际上，序列概念格具有良好的数学性质与鲜明的层次性，可以利用它表示 或挖掘出一些满足用户指定的最小支持度的序列模式。但遗憾的是，目前大部分 已提出的序列概念格【17 】瞄1 仅能表示或挖掘传统意义上的序列模式( 即仅满足用户 指定的最小支持度的序列模式) 。在现实中，一方面，用户对序列挖掘的要求往往 不是一个变量参数就可以完全描述刻画出的，即用户的多种需求( 多参数) 同时 存在；另一方面，由于i n t e m e t 的发展，利用网络连接的分布式系统也已经得到了 广泛的应用，许多数据已是分布的存储在不同地方的计算机上，在这些实际情况 下，大部分已提出的序列概念格【1 7 】【2 2 1 已不能够给予很好的表示或组织具有不同重 1 0 扬州大学硕士学位论文 要程度的自适应的或分布环境下的序列模式，而序列概念格已经具备了最基本的 描述功能和严密的数学性质，这就是说，应当可以对之进行合理地扩展以更好地 适合描述现实世界的序列形式，以使其具有更好的表达能力，从而实现与真实世 界的接近。 自然科学中的许多学科的发展也都经历了这样的过程，即对现实世界高度抽 象和简化，以形成数学性质良好的模型，然后再对这个模型进行扩展，以逼近和 模拟真实世界。同样，序列概念格模型也可以进行合理地扩展，使其形成新的扩 展模型，这样就与现实世界更加接近了。因此序列概念格的扩展模型、构建及分 布处理研究必然会有广阔的前景。 总之，当前对形式概念分析、序列模式挖掘以及序列概念格的研究非常活跃， 但序列模式挖掘过程中自身呈现的问题需要更好的模型去解决，而与概念格结合 不仅可以解决此类问题，而且还会方便的更新、扩展序列模式。虽然已经有部分 研究将概念格应用到了序列模式挖掘中，但其构建的模型表达能力较弱或根本无 法在概念格上表示分布环境下的序列模式，因此，对构建一套带有良好数学性质 的序列概念格扩展模型以满足不同的应用，以及研究基于扩展模型的具有良好效 率的序列模式挖掘算法还是十分必要且具有重要实际意义的。为此，本文针对序 列概念格的不足之处，提出了序列概念格的扩展模型、构建算法、分布处理以及 应用等研究，从而为复杂序列模式挖掘问题提供了一条新的解决途径和新的研究 方向。 1 2 论文主要内容与创新 本文根据当前的实际需要并结合国内外在序列模式挖掘与形式概念分析方面 的研究情况，对序列模式挖掘与模糊概念格的结合进行了系统的研究。本文首先 阐述了形式概念分析中的有关理论、概念格的基本概念以及构建算法，接着给出 了传统序列模式的相关概念、挖掘算法及其应用，然后研究了在大规模稀疏数据 集或分布式数据集上的概念格构造算法，在此基础上，提出了序列模糊概念格及 其分布序列模糊概念格模型，以及它们相应的构建算法，最后提出了自适应序列 模式的挖掘问题，并给出了相应的发现算法，为序列模式的挖掘提供了新的途径 袁运浩：序列模糊概念格模型及其分布处理研究 l l 与技术。 总的来说，本文的主要研究内容与成果如下： ( 1 ) 针对目前概念格构造算法在较大规模稀疏的数据集或分布式的数据集上， 生成概念时仍然需要耗费大量的时间，本文提出了一种基于i e t r e e 与特征空间划 分的概念生成算法i e t r e e c s 。i e t r e e c s 算法首先将形式背景转为i e t r e e ，减少了 数据集的存储量；然后该算法在i e t r e e 的基础上进行了特征空间的描述与划分， 最后给出了完整的i e t r e e c s 算法。实验结果表明该算法在大规模稀疏的数据集或 分布式的数据集上性能优越，有明显地提高。同时，i e t r e e c s 算法也为序列模糊 概念格的构建提供了算法支持。 ( 2 ) 为了组织与挖掘有价值的满足多需求的序列模式，本文提出了一种序列 模糊概念格模型，在传统的模糊形式背景的基础上，本文将其在序列上进行了扩 展，定义了序列模糊形式背景；利用扩展的序列模糊形式背景，定义了概念的g a l o i s 闭包连接、序列模糊概念及其格结构，最后给出了序列模糊概念格的构建算法。 通过实验表明，序列模糊概念格模型不仅可以方便有效的组织自适应序列模式， 在时间与空间上都具有良好的性能，而且还可以在序列模糊概念格上挖掘传统意 义下的序列模式，同时，为进一步挖掘自适应序列模式提供了理论支持。 ( 3 ) 由于在实际应用中，许多大型数据库是以分布式的形式存在的，为了能 够有效与方便地处理分布环境下的序列，本文在序列模糊概念格的基础上提出了 分布序列模糊概念格模型。在分布序列模糊概念格模型上，不仅可以有效挖掘分 布序列模式，而且还可以挖掘满足用户多需求的特殊分布序列模式，如分布加权 序列模式等。通过实验证明，本文提出的分布序列模糊概念格模型具有良好的时 间与空间性能。 ( 4 ) 在序列模糊概念格的基础上，利用序列权重与序列的重要度阈值，本文 定义了序列自适应系数及其自适应序列模式s a s p ，给出了基于序列模糊格的自适 应序列模式的发现算法s a s e q p 。它可以自适应地调整用户指定的最小支持度 m i n s u p ，以挖掘出满足用户需求的有特别价值的序列模式。 1 2 扬少i 1 大学硕士学位论文 1 3 论文内容组织 本文各章节的详细设置情况如下： 第一章主要阐述了论文的研究背景与选题依据，并给出了论文的主要研究内 容与成果。 第二章系统概述了形式概念分析与序列模式挖掘的基本定义与有关概念，介 绍了概念格的批处理与渐进式构建算法，例如g o d i n 算法、b o r d a t 算法等；阐述 了序列模式挖掘中的两类挖掘算法，即基于候选码测试与基于模式增长的发现算 法，例如a p r i o r i a l l 算法、g s p 算法以及p r e f i x s p a n 算法等。同时，列举了概念格 与序列模式挖掘中的一些成熟应用。 第三章研究了形式概念分析中形式背景对应的i e t r e e 模型，定义i e t r e e 结 构与其生成算法，并给出了在其上特征空间的基本概念、划分以及有关定理，最 后，在大规模稀疏的或分布式的数据集上提出了一种基于i e t r e e 与特征空间划分 的概念生成算法i e t r e e c s 。 第四章研究并定义了一种序列模糊概念格模型，并给出该模型的渐进式构造 算法一s e q f u z c l 算法。该模型能够有效地组织序列模式，通过设置不同的参数、 阈值来满足用户不同的需求，也为进一步挖掘自适应序列模式提供了理论支持。 第五章在分布式环境下，研究了分布序列模糊概念格模型，并提出了分布序 列模糊概念格构建算法d s e q f u z c l ，为分布序列模式的挖掘提供了良好的理论基 础。 第六章在序列模糊概念格的基础上，利用序列权重与序列的重要度阈值，定 义了序列自适应系数及其自适应序列模式，给出了基于序列模糊格的自适应序列模 式的发现算法s a s e q p 。 第七章评价和总结了论文的工作与研究成果，并提出了一些有待于进一步研 究的问题。 袁运浩：序列模糊概念格模型及其分布处理研究 1 3 第二章概念格理论与序列模式挖掘 2 1 概念格模型 形式概念分析f c a ( f o r m a lc o n