（信号与信息处理专业论文）在线挖掘数据流闭合频繁项集算法的研究.pdf

在线挖掘数据流闭合频繁项集算法的研究摘要近年来，随着计算机存储和网络通信技术的快速发展，数据流逐渐出现在日常生活中的各个领域，比如大型商场的售货记录，环境温度的检测数据，交易所的股票价格信息等。人们需要对海量的动态数据进行实时连续的收集与分析，进而挖掘数据流上的频繁模式得到越来越多的关注。与传统静态数据库相比，数据流具有持续不断、高速运行、无限到达的特点。数据流中的数据随时问的推移不断更新，而用户通常只关注近期有价值的模式。本文研究的是数据流频繁项集挖掘的一个主要方面：数据流闭合频繁项集挖掘。它是针对数据流频繁项集挖掘中得到大量冗余的频繁项集，造成内存过多的消耗和挖掘速度的极大下降而提出的。闭合频繁项集包括了挖掘出的所有频繁项集的完全集，从而避免了冗余频繁项集的产生，可以大大节省存储空间，提高挖掘效率，但是又不会丢失任何有用信息。数据流快速无限的特点及其应用领域的不断扩增，使数据流的在线挖掘技术越来越具有挑战性。提出了一种新的c m n l s w 挖掘算法( c l o s e d 丛a pa n d n u ml i s t s l i d i n gw i n d o w ) ，它沿用m o m e n t 算法的滑动窗口技术和c f i s t r e a m 算法只维持闭合项集信息的方法，但与之不同的是，c m n l s w 算法不需产生事务的子集，也不需搜索每个子集的超集。算法使用数据结构c l o s e dm a p 存储挖掘到的闭合项集和n u ml i s t 存储所有不同项的序号，通过对添加新事务和删除旧事务包含的项序号进行简单的并集和该事务与之相关已经挖掘到的闭合项集进行交集运算来更新当前滑动窗口，使之能够根据用户任意指定的支持度阈值实时输出数据流上闭合频繁项集信息。通过理论分析和对真实数据集m u s h r o o m 、r e t a i l c h a i n 以及人工合成数据集t 4 0 1 1 0 d 1 0 0 k 的挖掘结果表明，提出的算法在时空效率上明显优于同类经典算法m o m e n t 和c f i s t r e a m ，并且随着数据流上处理事务数的递增和快速改变有很好的稳定性。关键词：频繁项集；闭合频繁项集；数据流挖掘；滑动窗口；在线挖掘在线挖掘数据流闭合频繁项集算法的研究a b s t r a c ti nr e c e n ty e a r s ，a l o n gw i t ht h eh i g h - s p e e dd e v e l o p m e n to ft h ec o m p u t e rm e m o r ya n dn e t w o r kc o m m u n i c a t i o n a lt e c h n o l o g y ，t h ed a t as t r e a ma p p e a r e dg r a d u a l l yi nt h ed a i l yl i f ee a c hd o m a i n ，f o ri n s t a n c el a r g e s c a l es u p e r m a r k e tv e n d i n gr e c o r d ，a m b i e n tt e m p e r a t u r ee x a m i n a t i o nd a t a ，e x c h a n g es t o c kp r i c ei n f o r m a t i o na n ds oo n t h ep e o p l en e e dt oc a r r yo nr e a l - t i m e ，t h ec o n t i n u a lc o l l e c t i o na n dt h ea n a l y s i st ot h em a g n a n i m o u sd y n a m i cd a t a ，a n dt h e no n l i n em i n i n gf r e q u e n tp a a e r no v e rd a t as t r e a mo b t a i n sm o r ea n dm o r ea u e n t i o nc o m p a r e sw i t ht h et r a d i t i o n a ls t a t i cs t a t ed a t a b a s e ，t h ed a t as t r e a mh a st h ec h a r a c t e r i s t i cw h i c ht h ei n c e s s a n c y , t h eh i g hs p e e dm o v e m e n t ，i n f i n i t ea r r i v e d a t ar e n e w su n c e a s i n g l ya l o n gw i t ht h ep a s s a g eo ft i m e ，b u tt h eu s e ro n l yw i l lu s u a l l yp a ya t t e n t i o nt ot h ev a l u a b l ep a t t e r no ft h en e a rf u t u r e w h a tt h i sa r t i c l es t u d i e si sap r i n c i p a la s p e c to fm i n i n gf r e q u e n ti t e m s e to v e rd a t as t r e a m ：m i n i n gc l o s e df r e q u e n ti t e m s e t i tw a sp r o p o s e dt oa i mi nm i n i n gf r e q u e n ti t e m s e to v e rd a t as t r e a mt oo b t a i nt h em a s s i v er e d u n d a n c yf r e q u e n ti t e m s e t s ，c r e a t e sm e m o r ye x c e s s i v e l ym a n yc o n s u m p t i o n sa n dt h em i n i n gs p e e de n o r m o u sd r o p t h ec l o s e df r e q u e n ti t e m s e ti n c l u d e sa l lf r e q u e n ti t e m s e t s c o m p l e t ec o l l e c t i o nw h i c hm i n e d ，t h u sa v o i d st h er e d u n d a n c yf r e q u e n ti t e m s e t sp r o d u c t i o n ，m a ys a v et h es t o r a g es p a c eg r e a t l y ，r a i s e st h em i n i n ge f f i c i e n c y , b u tw i l ln o tl o s ea n yu s e f u li n f o r m a t i o n t h ed a t as t r e a mf a s ti n f i n i t ec h a r a c t e r i s t i ca n da p p l i c a t i o nd o m a i n su n c e a s i n gi n c r e a s i n g ，e n a b l e so n l i n em i n i n gt e c h n o l o g yo v e rd a t as t r e a mt oh a v et h ec h a l l e n g i n gm o r ea n dm o r et h i sa r t i c l ep r o p o s e so n ek i n do fn e wm i n i n ga l g o r i t h mc a l l e dc m n l s w ( c l o s e dm a pa n dm u ml i s t - s l i d i n gw i n d o w ) ，i tc o n t i n u e st ou s et h es l i d i n gw i n d o wt e c h n o l o g yi nt h em o m e n ta l g o r i t h ma n dt h em e t h o dt h a to n l ym a i n t a i n st h ec l o s e di t e m s e ti n f o r m a t i o ni nt h ec f i s t r e a ma l g o r i t h m ，b u tw h a ti sd i f f e r e n tw i t hi t ，t h ec m n l s wa l g o r i t h md o e sn o tn e e dt op r o d u c tt r a n s a c t i o n ss u b s e t ，a l s od o e sn o tn e e dt os e a r c ht h es u p e r s e to fe a c hs u b s e t o nc o n c r e t ea l g o r i t h mu s ed a t as t r u c t u r ec l o s e dm 印t os t o r et h ec l o s e di t e m s e tm i n e da n dn u ml i s ts a v ea l ld i f f e r e n ti t e m s s e r i a ln u m b e r s ，v i at h es i m p l eu n i o no fi t e mn u m b e rc o n t a i n e dw i t h i nan e wa r r i v i n go ra no l dd e l e t i n gt r a n s a c t i o na n di n t e r s e c t i o nw i t hc e r t a i np r e v i o u sc l o s e di t e m s e t so n c e ，i ti n c r e m e n t a l l yu p d a t e st h ec u r r e n ts l i d i n gw i n d o wt h a tm a k e st h ec l o s e df r e q u e n ti t e m s e t sc a nb eo u t p u ti nr e a lt i m eb a s e do na n yu s e r ss p e c i f i e dt h r e s h o l d s t h e o r e t i c a la n a l y s i sa n dt h ee x p e r i m e n t a lr e s u l t so ft h er e a ld a t a s e t sm u s h r o o m 、哈尔滨二 程大学硕士学位论文r e t a i l c h a i na n da r t i f i c i a l l ys y n t h e s i z e dd a t a s e tt 4 0 110 d10 0 ks h o wt h a tt h ep r o p o s e dm e t h o di ss u p e r i o rt ot h a to fs t a t e o f - t h e a r ta l g o r i t h mm o m e n ta n dc f i s t r e a mi nt e r m so ft i m ea n ds p a c ee f f i c i e n c y , a n dh a sg o o ds c a l a b i l i t ya st h en u m b e ro ft r a n s a c t i o n sp r o c e s s e di n c r e a s e sa n da d a p t sv e r yr a p i d l yt ot h ec h a n g ei nd a t as t r e a m s k e yw o r d s ：f r e q u e n ti t e m s e t ；c l o s e df r e q u e n ti t e m s e t ；d a t as t r e a mm i n i n g ；s l i d i n gw i n d o w ；o n l i n em i n i n g第1 章绪论第l 章绪论1 1 课题研究的背景1 1 1 在线数据流挖掘技术的由来当今社会，伴随着网络通信技术和计算机的普及应用，数据库管理系统的应用范畴也不断扩大。近年来数据仓库里储存的数据剧烈增多，比如，美国国家航空航天局轨道卫星上的观测系统每分钟会向地球发回大约l o g b 的图像数据；全球著名零散销售超市沃尔玛每个月产生6 0 亿左右的交易数据记录；国家数据库项目人类基因研究小组已搜集到了g b 数量级的基因编码数据等等。诸多行业领域的数据分别存放在对应的数据库中，导致数据库的规模逐渐扩增。诸多数据信息给人们提供了便利，随之也带来了繁杂的难题，例如，信息容量太大，超越了研究人员消化和掌握的能力；很多信息难辨真伪，正确利用这些信息是很困难的；信息组建方式的混乱，加大了对信息进行统一分析的难度等。面对海量数据库和大量繁杂信息，如何才能从中提取出有价值的知识，进一步提高信息的利用率，由此衍生出了一种新的科研课题，研究人员称之为知识发现，它是以数据库相关学科为理论基础的；除此之外还开展了数据挖掘领域相关技术的探讨。所谓数据挖掘，科研人员给出了明确的定义，它是指数据库管理员从海量的，残缺不全的，概率的实际应用数据中，汲取蕴涵在其问的，用户本来未掌握的，然而又是可能有利用价值的知识和信息的一个步骤。数据挖掘是好几个专业相交混合的科研范畴，汇总了传统数据库技术，智能识别、知识发现，概率论以及数据可视化等最新技术的科研结晶【l 2 j 。从上世纪七十年代算起，传统数据库技术得到了迅猛的发展和宽阔的运用，国内外数据库研究人员在数据库技术领域取得了硕大的成果。然而，自从1 9 9 5 年以来，商业计算机和网络通信以及信息存储技术的发展，在许多应用领域，如传感器网络，金融市场，电讯数据管理，股票交易所等等，这些行业领域每天产生的和准备处理的数据集合不再是静态的，相反是在时间空间里按照严格的序列，在数值上持续不断发生变化的无限序列形式。由于这类数据不是静止的而是流动的，持续到达不问断，而且数据流量不是有限的，所以用有限的磁盘保存全部的流动数据是不太现实的；再者，流动数据的使用对用户查询要求很高的实时性，因此在对这种数据分析和处理时需要是实时的、在线的。所以，先前使用的数据库挖掘技术已经达不到这种流动数据类型特征的要求，针对流动数据的管理和查询一切将都会是无效的，这种背哈尔滨工程大学硕二 ：学位论文景下，需要开发和创造出新的满足流动数据特征的操作技能，以便能够对数据进行更有效的操作和整理。世界诸多著名研究机构的潜心钻研之后，对外公布了一种全新的可以生动阐述此类流动类型数据的总体模型，称之为数据流模型。对流动数据进行实时挖掘称为在线数据流挖掘技术。目前，针对在线实时挖掘数据流算法的科研有很多分支，但大部分囊括在聚类分析，频繁模式挖掘，序列模式挖掘，检测离群点以及各种行业数据流的变化监测的方向中【2 3 j 。1 1 2 挖掘闭合频繁项集的意义数据挖掘以及后续提到的数据流挖掘技术中有一个很重要的方向，即挖掘关联规则，其蕴涵着n 个事件之间( n 1 ，n 为整数) 联系或依存的信息。假若超过两项的集合属性间存在着某些关联，则其中必定有一项的属性值就能够按照其它属性值来预报和估测。而挖掘频繁项集是最基础也是最关键的步骤，是数据流挖掘中一个活跃的研究领域。它可应用于购物篮分析，指导超市商品货物摆放和捆绑促销，客户流失分析；挖掘网页点击日志，设置个性化网页，引导用户快速浏览；在股票交易的事务处理中，由于上市公司之间存在竞争，某些股票价格在一定时问内会出现相似或相反的趋势，挖掘这些数据或股票之间的关联规则，可以指导投资者了解各种股票的走势，做出正确决策；除此之外，应用最广泛的是监控网络，例如，分布于各地的温度传感器构成的温度检测网络，分布于电网上的传感器构成的电网检测系统，通过这对这些系统产生数据流关联规则的挖掘可以发现其中有趣的模式，帮助做出正确的决策，应用于气象领域天气预报，调整电网的负荷等等。生活中有相当多的数据挖掘任务中需要用到频繁项集挖掘的结果，所以挖掘频繁项集起着举足轻重的作用，但是挖掘结束获得的频繁项集和关联规则的数目很多很大，更关键的是人们不理解什么意思，也无法运用。为了解决这个弊端，在2 0 世纪末年，n i c o l a sp a s q u i e r 最早创新了闭合项集的定义和说法【4 】，接下来闭合频繁项集挖掘的任务得到大量学者的科研。本课题研究的是基于滑动窗v i 在数据流上完成闭合频繁项集的实时挖掘，也就是说，针对数据流模型进行频繁项集的挖掘往往会获得大批繁琐的项集集合，从而导致计算机操作平台上内存消耗效率的大幅度降低而提出的。闭合频繁项集在全局上只是频繁项集总体的某个子集，但是它却囊括了全部频繁模式的完整信息和知识，全部频繁项集和与之对应的支持度阈值全部可以通过闭合频繁项集直接导出，但是就结果数目来讲，闭合频繁项集比频繁项集降低了很多，最多可能达到两个或三个数量级别，很大程度上缩小了运算代价。第1 章绪论1 2 课题国内外研究现状从1 9 9 3 年a g r a w a l 等人首次提出挖掘布尔型关联规则频繁项集算法a p r i o r i 【6 j ，到1 9 9 9 年n i c o l a sp a s q u i e r 提出闭合项集的概念；从1 9 9 5 年美国计算机年会上提出数据挖掘的概念到至今数据流挖掘方面的研究，各国数据库相关领域研究人员就陆续不断的提出了多种形式的运作平台和算法，从千差万别的侧重面和视界创作出了崭新的优化算法和观点。1 2 1 国外研究现状早在2 0 世纪七八十年代外国尤其是美国研究学者在数据挖掘以及数据流挖掘领域就开始了讨论和科研，得到的研究成果形式很多，该专业的项目工作进展也比较迅速。现在，在数据挖掘或者数据流挖掘领域有比较知名的研究成员和小组有两个，其中一个是r m o t w a n i 博士以及由他带头的科研小组，他们学习和就职于美国斯坦福大学；还有一个是由两个人领导的科研小组，他们是美国伊利伊诺大学的a g g a r w a l 和j h a n 博士。前者重点研究数据流管理系统( d s m s ) ，其内容包含了数据流查询处理的各个方面；后者主要侧重点是数据流挖掘和实时查询算法，其中包括聚类分析，决策树分类，频繁模式挖掘，在很多方向做了工作发展项目，并且国家自然科学协会和美国军事机构为他们提供了基金资助【2 i 。在数据库中挖掘频繁模式是从1 9 9 3 年开始的，a g r a w a l 在研究购物篮分析时首次提出了关联规则挖掘，并且当时他设计了a p r i o r i 算法【5 】，其精华是所有频繁项目集的子集( 空集除外) 必定也都是频繁的项目集合。作者利用基于频繁项集性质和原理的先验理论知识，运用迭代的方式逐渐按层次进行挖掘。为减小搜索空间，n i e h o l a sp a s q u i e r等提出了闭合频繁模式的概念，1 9 9 8 年提出c l o s e 算法，并在1 9 9 9 年提出了改进的a c l o s e 算法【6 j ，以逐层方式构造生成子集合，计算生成子的支持度，修剪掉无用的生成子；查找出全部有利用价值的生成子集，这样就能容易的解出全部闭合频繁项集。本节提到的算法在遍历数据库的次数上都比经典算法a p r i o r i 要少的多。c l o s e 算法迭代一次就必须相应的计算此次的闭包来检查项( 项集) 的闭合性，计算量相当大。其改进算法a - c l o s e 扫描数据库的次数要比它多一次，多出来的这次专门用于计算闭合性。2 0 0 0年，由j h a n 等人提出了一种全新的f p g r o w t h 算法【7 1 ，它彻底脱离a p r i o r i 算法必须产生候选项集的传统方式，建立了基于f p t r e e 结构的不产生候选项集的思想，开辟了频繁项集挖掘的新思路。该算法具有较高的数据压缩性，与a p r i o r i 算法相比大大的降低了搜索丌销。但是它必须遍历所有投影库以及事务数据库两次，如果处理事务较小的数3哈尔滨工程大学硕士学位论文据库代价还可以接受，但是事务庞大的数据库，要付出巨大的代价。随后，j p e i 等提出c l o s e t 算法【8 1 和在此基础上改进的c l o s e t + 算法【9 1 是基于f p 。t r e e 的闭合频繁模式挖掘算法，提出了很多优化技术改善挖掘性能，针对稠密型数据库使用物理树，该树的投影是自顶向上的；对稀疏型数据库使用伪树，该树的投影是自顶向下的。这两个算法的内存消耗比例，平均运行时间以及稳定性权值都超过起初介绍的挖掘闭合频繁项集的很多算法。之前算法只适用于传统数据库或者快照窗口处理数据流模型，不论是挖掘频繁项集还是闭合频繁项集，并没有提出涉及数据流特点有针对性的策略【10 1 。在数据流频繁项集挖掘领域，大批外国研究人员和学者展开了较深刻的探讨并且创新了属于个人的方法和论证。m a n k u 和r m o t w a n i 两位知名教授研究出s t i c k ys a m p l i n g 算法以及l o s s yc o u n t i n g 算法用以数据流的频繁项集挖掘10 2 0 0 4 年，由j h a n等人提出了基于倾斜时间窗v i 挖掘数据流频繁项集的f p s t r e a m 算法【l2 1 ，它使用f p g r o w t h 算法建立基本窗v i ，对每个模式使用多种时间粒度递增维持指数倾斜时间窗口。它不但存储了当前最新的频繁模式，而且记录了所有流过的数据信息，支持根据用户对某一个时期频繁项集信息感兴趣的近似查询。该算法虽然可以保存和查询历史信息，但却增大了内存开销。对于稠密型大数据集的处理代价很高，而且查询得到的是相当模糊的信息。2 0 0 5 年，c h i 等人员构成的领导小组设计的m o m e n t 算法是利用滑动窗口技术实时挖掘数据流闭合频繁项集算法的里程碑1 3 】，它是一种只关注最近的闭合频繁项集的挖掘算法。因为该算法消除了对历史闭合频繁项集信息的储存，因此数据结构中存储的闭合频繁项集的数目按照指数级别递减的。2 0 0 6 年，n j i a n g 等人提出的c f i - s t r e a m 是- , e e比较有新意的挖掘闭合频繁项集的算法，该算法运用的也是滑动窗v 1 技术固定挖掘目标对象的界限【1 4 】，它和先前提到的m o m e n t 算法作比较，其优点是将直接输出并及时更新闭合频繁项集的信息，而不是必须通过对多种结点形式判定和识别，算法并不需要存储其它任何形式的项集及支持度信息，而仅是存储闭合频繁项集就足够了，因此此类算法较大程度上降低了时间和空间复杂度。1 2 2 国内研究现状由于2 0 世纪9 0 年代我国计算机和网络通信技术发展还不是太迅速，在数据挖掘和数据流挖掘领域的科研活动开展的相对较晚，但是也涌现了一批这方面的学者和研究员，他们在国外提出经典算法的基础上进行数据结构的优化，发表了有关挖掘数据流闭4第1 章绪论合频繁项集的论文。但所做的研究也只是局限于理论验证，并没有付诸于行业真实数据集的实践与运用。比如，东南大学的刘学军，徐宏炳等人提出了一种发现滑动窗口中闭合频繁模式的新方法d s c f i l l 5 】。他们设计的算法是基于以下思想的：首先将滑动窗! e l 划分成许多个基础窗口，以基础窗口作为更新单元，运用创新的挖掘闭合频繁项集的算法统计每一个基础窗口隐含的闭合频繁项集数量，然后创建了一种新颖的数据结构d s c f i t r e e 存储这些闭合频繁项集以及它们的子集。它能够增量更新并且可以快速的挖掘滑动窗口中的所有闭合频繁模式。国防科技大学敖富江，杜静等人提出了f p c f i d s 挖掘算法i l 创，它首先建立f p t r e e结构，和j h a n 提出的类似，不同点是在头表的每一项和前缀树的每一个结点中包含了事务i d 的总和。然后建立g c t 结构，该结构由前缀树和哈希表组成，存在两类结点：闭合项集结点和通向闭项集结点的中间结点。并采用了不同的搜索空问项顺序策略和剪枝技术。该算法对稠密数据集或支持度较小时，性能优于m o m e n t 算法。台湾开南大学李华福等人针对m o m e n t 算法的弊端提出了n e w m o m e n t 算法【l7 1 ，它利用位序列表示在当前窗口的每个项，假如一个项x 出现在当前窗口的第f 个事务，那么b i t ( x ) 的第f 位就设置为l ，否则，设置为0 。另外建立一个n e w c e t 树结构维持闭合项集信息。树中结点类似于c f i s t r e a m 算法中的存储结构，不过除了闭合项集，它还存储了当前窗口所有1 项集的位序列。所以建立第一个基本窗口的时间很大。中南大学的毛伊敏等人提出了m c f i s w 算法【1 引，它使用c f p t r e e 存储三种结点：频繁项集、过渡项集、非频繁项集。像f p s t r e a m 算法一样除了设置最小支持度阈值外还设置了最大支持度阈值误差。相比于f p t r e e ，它使用字典序存储项集，另外除了存储项集，支持度计数，和结点链之外还存储了代表结点形式的项标号。由于c f p t r e e 类似f p t r e e ，在挖掘时采用了c l o s e t + 中所讲到的算法。另外对树结构进行剪枝。实验表明该算法性能优于n e w m o m e n t 算法。综上所述，目前，关于数据流挖掘闭合频繁项集的研究主要是基于传统的数据挖掘进行扩展，使之适应数据流实时、海量的特点。出现的各种算法只能解决某些方面的弊端，但又会带来新的问题。这方面的研究有待于进一步深入和完善。随着互联网的兴起，基于互联网的数据流挖掘应用必然成为未来的研究风向标。1 3 论文的研究内容和组织结构这篇文章是在剖析了当前已经提出的在数据流模型闭合频繁项集挖掘算法的优势5哈尔滨丁程火学硕士学位论文和弊端后，创新设计出一种利用滑动窗口技术在线实时挖掘数据流环境下闭合频繁项集的c m n l - s w 算法( 一c l o s e dm a pa n d n u ml i s t s l i d i n gw i n d o w ) ，包括以下几个方面：( 1 ) 重点研究并且在新算法中沿用了m o m e n t 算法中使用的滑动窗口技术，保证挖掘信息的实时性。由于用户大都关注的是近期有价值的数据信息，因此我们并不保存那些没有任何存储意义的过往信息，真正完成了实际意义上的实时挖掘满足用户在线查询请求。本文采用基于事务的挖掘思想，事先设置固定的滑动窗口尺寸，随着新产生的一条事务进入窗口，最旧的一条事务从窗口中移除，实时更新挖掘到的闭合频繁项集信息。( 2 ) 沿用c f i s t r e a m 算法中只存储闭合项集的思想，不再存储除此之外的中间结点和过渡结点，这种思想在设置的支持度阈值很小或者数据集稠密的时候有较高的效率，正好符合现代各行业领域所产生数据的特征以及用户的需求。( 3 ) 设计出一种新颖的算法就必然有相匹配的独特的数据结构，数据结构的简洁与否是判断能甭有效的降低时间和空间复杂度的保证。c m n l s w 算法使用c l o s e dm a p存储挖掘到的闭合项集和n u ml i s t 存储所有不同项的序号，通过对添加新事务和删除旧事务包含的项序号进行简单的并集和该事务与之相关已经挖掘到的闭合项集进行交集运算来更新当前滑动窗口，使之能够根据用户任意指定的支持度阈值在线输出数据流上闭合频繁项集信息。本文总共有5 章，框架结构分为以下几个部分：第一章是绪论，主要描述研究本课题的背景、意义以及分别介绍了外国和我国的研究发展现状，说明了本文的科研工作包含哪些内容。第二章详细讲解了数据( 流) 模型以及涉及到的数据流挖掘技术。说明了频繁项集的概念，讨论了挖掘数据流频繁项集的几个经典算法。第三章探讨了闭合( 频繁) 项集和频繁项集的区别、联系，系统的列举出目前基于滑动窗口技术挖掘数据流闭合频繁项集的几个经典算法，重点是m o m e n t 和c f i s t r e a m算法的优点和弊端。因为本文提出的算法沿用了其中的思想。第四章详细叙述了本文提出的一种新的在线挖掘数据流闭合频繁项集算法，包括添加新事务和删除旧事务更新滑动窗口的过程。第五章进行算法的性能评估和比较，对于模拟数据集和真实数据集给出算法挖掘出的实验结果。并且验证了新算法适应快速增加数据流的稳定性。最后总结全文。对论文的研究工作进行了总结和归纳，并分析了所存在的不足。第2 章数据流模型及相关数据流挖掘技术第2 章数据流模型及相关数据流挖掘技术数据挖掘技术是适应信息处理新需求和社会发展各方面的迫切需要而发展起来的。它是为了数据库的种类多元化和应对信息的激增而产生的，数据积累的越多，隐藏在数据背后的信息和知识就越多。数据挖掘技术是针对传统静态数据库的，随着各行业领域产生数据速度增大，出现了一种高速运行、持续不断到达的数据形式，为了应对这种变化，数据流挖掘技术应运而生。本章将介绍从数据挖掘到数据流挖掘的演变过程，重点是数据流模型和提出新算法所用到的相关挖掘技术。2 1数据挖掘数据挖掘是利用某种算法从海量数据仓库中汲取对用户有价值的信息，这些信息是事先隐藏在库中的、对用户来说是有新意的、并且是他们感兴趣的知识，汲取的信息是用规则、项集、约束、概念以及可视化等多种形式表达的【1 1 9 】。上述定义蕴藏着以下几层意义：( 1 ) 数据必须来源于真实世界、大批的；( 2 ) 最终获得的是有用处的、人们感兴趣的知识；( 3 ) 挖掘的信息是可理解的、可接受的、可利用的；( 4 ) 发现的信息仅要求支持特定的业务，并不要求放之四海而皆准。2 1 1 数据挖掘的基本功能数据挖掘有很多功能，但主要体现在两个方面：预测、描述。前一个挖掘任务在即时数据上进行判断，以此用来预测。第二个挖掘任务主要阐述数据库中数据的综合特性。数据挖掘的功能与挖掘的目标数据类型是相关的。要想确定数据挖掘需要完成什么任务，必须多重考虑要挖掘数据的表现形式和数据挖掘功能以及用户是否感兴趣。下面介绍几种重要的功能。2 1 1 1 概念描述概念描述就是说对同一种类型对象相互关联数据的汇集、解析和对比，然后对此种类型对象的内含进行描绘和阐述，并且总结该类型对象的相关特点。有多种方法可以实现概念描述，例如将数据特征化、对数据分区。特征化阐述的是某些类型对象的相同特点，产生此类的特征概括，该概括只牵涉该类对象中全部个体的共性。它的输出形式很多，包括曲线，柱状图，多维数据立方体，饼图，含交叉表的多维图表等，并且得到的7哈尔滨一1 ：程大学颂士学位论文结果也能用规则形式或者概要关系来表示。数据区分阐述的是非同类型对象间的差异，它是将目标类型对象与n 个洲 1 ) 对比类型对象的综合特征进行对比，然而此类比较的充分必要条件是两个或多个类之间具备可比性。数据区分和数据特征化的输出相差不大，但是前者必须包含对比度量，用以辅助区分对比类和目标类。2 1 1 2 关联分析关联分析就是说从大批的数据里边查找项集和项集间有趣的联系、因果结构和项集的频繁模式。数据问有趣的联系是数据库重要的知识，假如针对n 个( n 1 ) 变量的取值能够从中发掘一定的规律可循，表明这几个变量就是互相关联的。关联可分割为三种形式：因果关联、简单关联和时序关联。变量的某些关联规则往往隐含在数据库中，关联分析的任务就是找出这种规则。挖掘关联规则在数据挖掘领域至关重要，举个例子，关联规则好比“主机，显示屏一 音箱” 可信度6 7 的形式，这个例子可以解释为“买了主机和显示屏的买家中，有6 7 的人顺便也买了音箱”。我们清晰的看到这种关联规则影射了买家的购买习惯。假如卖家充分掌握和利用类似的购买惯性行为，就可以制定销售策略以用来打开销路，提高营业利润。挖掘关联规则最主要的方面是针对以单条事务持续出现的数据记录库，尤其是零售业得售货数据，假如商家对过往历史事务数据进行处理和分析，那么提供的数据信息对顾客的某种购买行为是很有用处的。比如，商品在上架的时候可以根据用户经常一起购买的来摆放；帮助计划市场需求，避免库存商品积压，针对供应变化提供相应的预测。至此我们可以看出，挖掘事务型数据库发现的某些关联规则，对于创新零售行业等商业活动的策略相当重要。在事务型数据库中隐含着如此之多的关联规则，现实生活中，研究人员综合相关领域知识和技能，选择恰当的挖掘方法汲取某些符合特定的支持度和可信度的关联规则是很便利和很有价值的。2 1 1 3 分类分类完成的任务在数据挖掘中也是很重要的，在商业领域运用较广泛。分类的最终目标是查找可以阐述数据集合的函数或典型特征的组合，利用这种方法就可以简捷的识别出未知数据的类别或隶属。分类的模型可以通过数据挖掘分类算法从训练样本数据组合中学习获得。回归和分类都能用来预测。预测的目的是从过往数据记录中自动导出既定数据的广泛描述，这样就能预测未来的数据形式。数据分类的实质就是发现数据库对象之间的共同特性，并且把数据对象区分为不同类属的过程，其目标起初是分析训练数据，利用数据的一些特征和属性，提供每一个类第2 章数据流模型及相关数据流挖掘技术的完整描述，也就是分类法则，随后利用上边的描述，对其他数据完成分类。一般分类过程按两步走：1 、先创建模型，描述给定的数据集合；2 、然后运用模型进行分类。建立模型是以分析训练数据集后得到的结果为基础的。用到的模型能够用好几种形式来表示，其中包括判定树，分类规则以及数学公式等。举个例子，假如通过训练数据得到的规则如下。i f 年龄= “3 3 4 5 ”a n d 薪水= “较高”t h e n 信用程度= “良好”这个规则的涵义就是，年龄在3 3 到4 5 岁之间，收入较高的情况下，这类顾客群的信用程度被认为是“良好”的。2 1 1 4 聚类聚类是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。聚类和分类的方法相比有所差异，分类是在给定划分情况下分析的，而聚类分析没有，它是依照信息相似度进行知识聚集的办法。因此，聚类分析的目标数据集是未标任何记号对象的组合。聚类的任务是按照一定的法则，恰当的分组，并用暴露或者隐藏的方法阐述有差异的类别。因为聚类分析能够运用迥异的算法，因此针对同样的数据组合或许有不同的划分结果。在机器学习范畴，聚类是无指导学习的单个例子，分类是有指导学习的单个例子。聚类和分类所利用的办法相差很大，而且在时间复杂度上聚类要比分类大的多得多。2 1 2 数据挖掘的过程开始进行数据挖掘时，预先制定好方案是必要的。例如，有几个步骤，每个步骤都完成哪些工作，实现什么样的目标。制订详细周全的计划方能保障数据挖掘的整个程序按部就班的进行并且获得有效的成果。目前数据挖掘系统有很多种，但大致可以总结为两类：f a y y a d 总结提出的过程模型、遵循c r i s p d m 标准的过程模型。下面以前者为基础，对数据挖掘过程作概要性的介绍。( 1 ) 确定挖掘目标。了解相关领域的经验知识，站在用户需求的角度出发确定数据挖掘的目标，这一步相当于系统分析。必须考虑的因素有：该领域的瓶颈问题是什么?哪些工作由系统自动完成，哪些工作需要人工处理? 追求什么样的性能指标? 等等。( 2 ) 创建目标数据集。首先从已经搜集到的数据库筛选出那些与此次分析任务相关的数据。然后按照挖掘目标，从最原始的数据中选择关联的数据集合，将几个来源不同的数据集汇总。数据挖掘使用的平台和操作系统以及数据来源和类型不同所产生的格式差异是这个阶段必须解决的问题。9哈尔滨工程大学硕十学位论文( 3 ) 数据抽取和预处理。第二个步骤中难免的存在着一些残缺、错位、模糊的数据，称之为杂乱无章的“肮脏数据”形式。选取好数据后需要运用该学科专业知识清洗“肮脏数据”，得到容易让后续步骤处理的干净数据。( 4 ) 数据降维和转换。前者是说在顾及了数据的固定形式或者发现了数据的固定表达形式的先决条件下，尽量减少涉及变量的总体数目，并想方设法把数据转移到某个更容易求出解的空间里。数据转换需要考虑三方面的因素，包括挖掘任务和挖掘操作处理及相关挖掘技术。( 5 ) 合适的挖掘算法。这个步骤是运用高效的数据挖掘算法对数据进行分析，第一步先确定完成目标挖掘任务的数据挖掘功能，第二步挑选适宜的算法用以搜索模式，科研人员已经公布的有决策树和模糊集以及遗传算法等等。( 6 ) 模式解释和评估。按照用户最后的决策要求评估发现的模式，评估性能指标的优劣。将有价值和用户感兴趣的模式用可视化技术传递给用户观看和使用i l9 i 。2 2 数据流及数据流挖掘模型2 2 1 数据流的特点数据流是一种有序序列，它是隐藏的、无限的、大量的、连续的数据。人们现实生活中有不少数据流方面的例子，例如电信公司的通话记录，网络交换机的i p 数据等。和传统静态数据库相比，数据流有如下特点：( 1 ) 不可预知。在数据流挖掘模型中，处理的数据是一个或多个连续且无限的数据项组成的有时间特性的序列，而不再是从磁盘或内存设备中随机读取的静态数据。( 2 ) 无限到达。数据流的数据值是不断改变的，利用预测方法也不能准确的预测下一时刻即将到达的是什么类型的。动态数据流中的数据是无限的，而静态数据库中的数据是有限的。( 3 ) 不可再现。系统会删除掉那些已经分析和处理过的流动数据中很多的数据，这是因为固定不变的磁盘内存来储存无限流动数据的所有数据是不现实的，也正是因为这个，基本在数据流环境下的实时在线查询请求最终得到的结果都是近似数值，传统数据库上的查询结果正好与之相反。( 4 ) 高速运行。数据流中数据的形式是伴随着新数据源源不断的到来并不断更新的，其频率取决于数据流产生的速度。很明显，数据流的更新频率要很大程度上超过静态数据库中数据更新的频率。所以，在面对数据流模型相关处理技术时，简单的根据处理传统数据库中的数据那1 0第2 章数据流模型及相关数据流挖掘技术样将数据存储在静态数据库中，接下来随时、任意多次扫描处理是行不通的。总而言之，传统的数据处理技术已经无法应付数据流相关处理，必须创造出一种新的数据流处理方式和方法【2 0 】。2 2 2 数据流挖掘模型数据流挖掘是对数据挖掘的扩展，除了数据流本身的特点之外，挖掘思想与传统数据挖掘有些类似，但是数据流挖掘是以查询为中心的，需要将用户的查询要求提前放入处理系统中。然后系统中的数据流挖掘引擎对到来的数据流实时、高效的处理，并将处理的结果实时地输出。数据挖掘模型和数据流挖掘模型分别如图2 1 和2 2 所示。图2 1 数据挖掘模型图2 2 数据流挖掘模型针对数据流的特点，数据流挖掘系统应满足以下几个标准：( 1 ) 算法处理每一条事务数据的时间要尽量的少，否则快速产生的数据堆积导致不能得到实时挖掘；( 2 ) 由于各行业领域数据量很大，系统最多对每条事务处理一次，处理过的历史数据就会被转存到固定设备上，第二次访问的难度非常大；( 3 ) 数据流挖掘系统所在的计算机平台内存是相对固定的，而数据量是源源不断的，这在处理海量数据时是至关重要的；( 4 ) 由于用户随时都可能查询来获得有价值的信息，所以该系统必须满足在线挖掘，即时提供有效信息，而不是等处理完所有的数据一并公布；( 5 ) 数据流是连续不断产生的，挖掘系统必须在任何时候都能维持最新的数据信息，既能完整提供数据中新颖的模式，并且又不丢弃未过时的知识；因为数据产生如此之快，而且内存相对于数据量又是非常有限的，所以满足前三项是相当困难的。因此，许多研究重点探讨了在结果的准确性可以接受的前提下，尽量减少实际处理的数据的量，其中最常用的方法是滑动窗口技术【2 1 , 2 3 】。哈尔滨： 二程大学硕士学位论文2 3 数据流挖掘相关技术和应用挖掘数据流比传统的数据挖掘方式要复杂的多，这是由数据流的特点决定的，因而通常在进行数据流挖掘时必然事先解决以下几个关键技术难题1 2 2 】：( 1 ) 提出的算法占用挖掘平台系统的内存要尽可能小。数据流框架下的数据是持续不断到达的，需求的内存较大，只能在线实时的进行处理，因此设计挖掘算法的时候需要用有限的空间完成无限的挖掘任务，这样才能保证每一次都可以处理较多的数据。( 2 ) 提出的算法挖掘速度要快。进行数据流挖掘时，存储设备里存放的数据总是都是最近产生的，系统需要在这些数据还没被后续到来的数据覆盖前结束对它们的挖掘。所以设计出高效的算法是必要的，以求在尽可能用最简短的时间完成数据的分析和处理。( 3 ) 提出的算法必须在挖掘时是一趟完成的。数据流是持续不断时刻都在产生的，现在的技术达不到能够暂时阻塞数据流产生的情况，除非关闭数据接收系统。所以只能扫描一次流过的所有数据，这种限制就需要我们创新出一种挖掘算法，它是一趟的，而不是多次重复的对某条事务进行处理。2 3 1 滑动窗口技术传统数据库中的静态数据是固定有边界的，因此各种各样的查询请求能够处理所有数据，而流动数据往往是无界的和动态的，系统没有办法一次就挖掘完所有数据，但是很多场合的查询行为要求挖掘的目标对象是有界限的，所以如果在数据流上进行查询操作的话，一般是基于窗口的。设置的窗口是切割的流动数据产生时间序列的某个片段，它是挖掘平台实时在线处理的数据目标对象【24 | 。对数据的实时性要求比较高的行业领域适合应用窗口技术，它实现的是在线挖掘，细致的处理了最近产生的事务数据，同时适当的修剪过往的、陈旧的数据项集。因为在现实生活中，新到来的数据往往比已经流走的数据更重要和更具有价值，用户也比较有兴趣。在动态数据流环境下，查询窗口大致可分为以下三类：( 1 ) 快照窗口