（计算机软件与理论专业论文）数据流频繁模式挖掘算法研究.pdf

哈尔滨工稃大学硕十学伊论文 摘要 近年来，随着信息技术的高速发展，数据流广泛出现在多种应用领域中， 如传感器数据处理、金融证券管理、网络故障监测、电子商务记录等，这些 数据数量巨大，而且增长迅速超出人们的想象。数据流应用的出现，带动了 相关技术的发展，特别是数据流频繁模式挖掘技术的发展。然而传统的频繁 模式挖掘算法大多需要多次扫描数据集，无法直接将它们应用到数据流挖掘 领域，高效的数据流频繁模式挖掘研究是一个新兴的研究热点，在数据流挖 掘任务具有举足轻重的作用。 本文首先对传统的数据挖掘相关理论进行了全面深入的研究，对数据流 处理技术和数据流挖掘中的关键问题进行了系统地分析和归纳；同时，研究 了采样、界标模型、滑动窗口等经典的频繁模式挖掘算法，指出了以往频繁 模式挖掘算法在固定支持度阈值和固定时间区间上挖掘的缺点和不足，在此 基础上提出并实现了一种在整个数据流上基于支持度阈值可变情况下的频繁 模式挖掘算法，即s v f p 算法。该算法利用数据结构a f i 和s e g 对历史模式 的信息进行存储，通过s t r f i 树对数据流中的频繁模式进行存储和挖掘，因 此s v f p 算法可以实现在任意时间段进行频繁模式挖掘。最后，搭建了实验 环境，对s v f p 算法在各种参数下进行实验，实验结果表明采用支持度阈值 可变的方法是有效的，算法在时间和空间上保持着较高的效率。 关键词：数据流；数据挖掘；频繁模式；s t r f i 树 哈尔滨t 稃大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，d a t a s t r e a m sh a v ea p p l i e di nt h ew i d ev a r i e t y a p p l i c a t i o n s ，s u c h a ss e n s o rd a t a p r o c e s s i n g ，f i n a n c i a la n ds e c u r i t i e sm a n a g e m e n t ，n e t w o r kf a u l tm o n i t o r i n ga n d r e c o r d so fe c o m m e r c e t h eh u g en u m b e ra n dt h er a p i dg r o w t ho ft h e s ed a t ah a s e x c e e d e dt h e i m a g i n a t i o n o fp e o p l e t h e e m e r g e n c e o fd a t a s t r e a m i n g a p p l i c a t i o n sh a sl e di nt h ed e v e l o p m e n to fr e l a t e dt e c h n o l o g i e sa n de s p e c i a l l yi n t h et e c h n o l o g yi nm i n i n go ff r e q u e n tp a t t e r no v e rd a t as t r e a m h o w e v e r ，t h e t r a d i t i o n a lm i n i n ga l g o r i t h m so ff r e q u e n tp a t t e r nn e e ds c a nt h ed a t as e t sm a n y t i m e s ，s ot h e yc a nn o tb ed i r e c t l ya p p l i e dt ot h ef i e l do fm i n i n gi nd a t as t r e a m s i t i sa ne m e r g i n gr e s e a r c hf o c u st h a tw es t u d yt h ee f f i c i e n tm i n i n go ff r e q u e n t p a t t e r ni nd a t as t r e a m s i tp l a y sad e c i s i v er o l ei nt h ed a t am i n i n gt a s k f i r s t ，w es t u d yt h et r a d i t i o n a lr e l a t e dt h e o r yo fd a t am i n i n gd e e p l ya n da n a l y z e a n ds u m m a r i z et h ep r o c e s s i n gt e c h n o l o g yi nd a t as t r e a ma n dt h ek e yi s s u e so nt h e m i n i n gi nd a t as t r e a m ss y s t e m a t i c a l l y a tt h es a m et i m ew es t u d ys o m ec l a s s i c a l a l g o r i t h m s ，s u c ha ss a m p l i n g ，l a n d m a r kw i n d o w ，s l i d i n gw i n d o w ，a n dp o i n to u tt h e t h es h o r t c o m i n g sa n di n a d e q u a c i e so nt h ep r e v i o u sa l g o r i t h mf o rm i n i n gf r e q u e n t p a t t e r n si naf i x e ds u p p o r tt h r e s h o l da n di naf i x e dt i m ei n t e r v a l w ep r o p o s e da n d i m p l e m e n t e dt h ea l g o r i t h m o ft h em i n i n go ff r e q u e n tp a t t e mi nd a t as t r e a m b a s e do nt h ev a r i a b l es u p p o r tt h r e s h o l d n a m e l ya l g o r i t h ms v f p t h ea l g o r i t h m u s e st h ed a t as t r u c t u r e sa f ia n ds e gt os t o r et h ei n f o r m a t i o no fh i s t o r i c a l p a t t e r n s t h ea l g o r i t h ms t o r e da n dm i n e df r e q u e n tp a t t e r ni nd a t as t r e a mb yt h e s t r f it r e e s v f pa l g o r i t h mt h e r e f o r ec a na ta n yt i m em i n ef r e q u e n tp a t t e r n f i n a l l y ，w es e tu pt h ee x p e r i m e n te n v i r o n m e n t ，w ed ot h ee x p e r i m e n tu n d e rt h e v a r i o u sp a r a m e t e r si nw i t ht h es v f pa l g o r i t h m e x p e r i m e n t a lr e s u l t ss h o wt h a t t h ev a r i a b l es u p p o r tt h r e s h o l dm e t h o di se f f e c t i v e ，a n dt h ea l g o r i t h mi nt i m ea n d s p a c em a i n t a i nar e l a t i v e l yh i 曲e f f i c i e n c y k e yw o r d s ：d a t as t r e a m ；d a t am i n i n g ；f r e q u e n tp a t t e r n ；s t r f it r e e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：戴如氏哼 日期：砂哆年多月莎日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：氨山民啼导师( 签字) 酬 日期：纠年歹月扩日 2 叫年石月p 日 ” 哈尔滨t 程大学硕十学伊论文 第1 章绪论 1 1 课题的背景 数据流是近几年以来国内外研究的一个热点，广泛地存在于多种领域， 包括传感器网络、电信通话记录、气象监测与分析、股票分析、邮件过滤、 网络监控与安全、日志分析，以及大规模科学计算的数据分析等方面。数据 流【l 。】是一种潜在无限的、连续快速的、随时间不断变化的数据序列。由于众 多应用领域的需求，近几年来对数据流处理问题特别是数据流挖掘问题己受 到越来越多研究人员的关注。 传统的数据挖掘所面向的对象是静态的、有限的数据，挖掘算法通过将 数据从磁盘读入内存进行分析和处理来挖掘其中的有用知识。数据流中的数 据是具有一次扫描的特点，无法将数据全部保存下来，并且对数据流的查询 要求实时处理。由于受到时间、内存和c p u 等资源的限制，传统的数据挖掘 方法不再适用，因此，数据流挖掘面临着重大的挑战。 频繁模式挖掘无论在理论还是应用方面均得到了广泛的研究并取得了一 定的成果，出现了许多经典算法，但是这些算法难以增量式更新，不适合数 据流挖掘【4 。5 】。因为挖掘频繁模式是一系列连接操作的集合，在所有过去和将 来的数据到来之前，任何项集的计算不可能完整地完成，使得在数据流环境 中挖掘和更新频率模式变得困难。与静态数据集的挖掘相比，数据流有更多 信息要追踪和更复杂的情况要处理，频繁项集会随时间而变化( 或者说是时 间敏感的) ，非频繁项集在后来可能成为频繁项集，因此存储结构需要动态调 整以反映频繁项集随时间进化的情况。 1 2 国内外数据流频繁模式挖掘现状研究 在数据流频繁模式挖掘方面，国外研究的比较早，取得了一些研究成果， 相应的思想和方法也比较成熟。第一个计算数据流项集频繁度的算法l o s s y c o u n t i n g 6 】是由m a n k u 和m o t w a n i 提出的，算法将数据流分成事务数相等的 桶，桶的大小受误差参数控制，在桶的边界处对结构进行更新，删除频率过 哈尔滨t 程大学硕十学佗论文 低的项。但是由于产生的候选项集数量巨大，而且将数据存储在辅存中，致 使算法效率不高。g i a n n e l l a 和j i a w e i h a n 7 等将其扩展到流数据的时间窗1 2 1 模型上，提出了在任意时间间隔上挖掘频繁项集的近似算法，该算法通过把 流数据分成等长的数据段，对流数据进行批量处理，然后把历史数据保存在 倾斜时间窗口中，实现对任意时间段的数据进行查询。该算法采用f p s t r e a m 瞵j 数据结构在内存中保存频繁项，由于是对流数据进行批处理，实现了多时间 粒度，但不能实时的对流数据进行处理。算法采用倾斜时间窗口技术来维护 和更新f p s t r e a m 结构的有效算法，提出了计算和维护所有频繁模式并动态 更新。建立一个框架来挖掘带近似支持度的时间敏感模式，为每个模式在多 时间粒度上增量维护一个倾斜时间窗口，在这种框架下可以构建和回答感兴 趣的查询。y u n c h i 提出基于滑动窗口的频繁闭项集挖掘算法【9 j ，采用c e t 数 据结构存储流数据中的所有项集，根据滑动窗口数据的变化实时更新c e t 中 四种不同的项集，但项集的历史信息没有保存。虽然在滑动窗口的频繁挖掘 领域己经出现一些算法【l o 1 1 】，但其研究仍然不够深入。有一种利用有限存储 空间通过一趟扫描来估计数据流中最大频繁项集的算法，该算法采用了称为 “c o u n ts k e t c h 的数据结构 1 2 】，使得可在流中可靠地估计频繁项集的 频率。 关于流数据的研究，国内开展的比较晚，已有一些学者从事这方面研究， 现有的主要频繁项挖掘算法都是占算法，其中都不为o 。复旦大学的周傲英 【1 3 】等提出了流数据频繁模式历史计数的有效保存方法o 万算法，该算法置 e = 0 ，能有效的控制了内存的消耗。东南大学的刘学军等提出了f p d s 算法 【1 4 1 ，算法采用数据分段的思想，逐段挖掘频繁模式，可以连续在线获得当前 的频繁项集，有效地挖掘所有的频繁项集，适合长频繁项集的挖掘。通过引 入误差，裁减了大量的非频繁项集，减少了数据的存储量，也能保证整个 数据集中项目支持度误差不超过。东北大学的张听在改进的字典树结构 i l t r e e ( i m p r o v e dl e x i c o g r a p h i ct r e e ) 的基础上提出了一种新的启发式算法 f p i l s t r e a m t l 5 】，该算法采用了了一种启发式倾斜窗口方法，当生成新的模式 时，可以更为准确地估计相应的窗口，并可以提供更细的窗口粒度，降低了 2 哈尔滨t 稃大学硕十学位论文 数据的平均处理时间，提高了查询结果的精确性。还有很多大学正在做这方 面的研究工作，关于流数据的频繁模式挖掘还属于比较新的研究领域，值得 广大学者进行深入研究。虽然当前已经出现了一些比较经典的数据流频繁模 式挖掘算法，但在这个领域仍然存在一些方面需要进一步改进和提高，设计 这类算法的目标是尽可能获得更高的空间效率和时间效率。 1 3 论文的组织结构 本论文分为五个章节。 第l 章绪论介绍了课题的相关背景以及国内外研究的现状。 第2 章研究了数据挖掘的相关理论知识以及数据流的处理技术，介绍了 频繁模式挖掘的概念以及分类，按结果分为完全挖掘模式和部分挖掘模式。 第3 章主要对数据流中频繁项集挖掘算法进行了介绍和总结。 第4 章提出了可变支持度的相关内容以及s t r f i t r e e 的结构，深入研究 了相关历史信息存储的方法后提出了概要数据结构保持用来计算过去事务的 支持度的统计数据。重点提出了s v f p 算法，该算法实现了数据流中任意时 间区间可变支持度的频繁模式挖掘。通过大量的建于各种参数设定的实验， 指出用可变支持度阈值的方法是有效的并且能够在数据流中交互地挖掘频繁 项集。 哈尔滨t 程大学硕十学位论文 第2 章数据流和频繁模式挖掘 2 1 数据挖掘 2 1 1 数据挖掘定义及挖掘过程 数据挖掘技术是数据库技术发展与广泛应用的结果，整个发展过程经历 了数据搜集、数据访问、数据仓库与决策支持、数据挖掘几个阶段。随着计 算机与信息技术的飞速发展，人们面临着快速扩张的数据海洋，如何有效利 用这一丰富数据海洋的宝藏为人类服务，已经成为广大信息技术工作者所关 注的焦点之一。与日趋成熟的数据管理技术与软件工具相比，人们所依赖的 数据分析工具功能，却无法有效地为决策者提供其决策支持所需要的相关知 识，为有效解决这一问题，自二十世纪8 0 年代开始，数据挖掘技术逐步发展 起来。进入9 0 年代，数据库技术进入了一个崭新的发展阶段，联机分析处理、 多维数据库得到广泛应用。数据挖掘技术是人们长期对数据库技术进行研究 和开发的结果。起初各种商业数据是存储在计算机的数据库中的，然后发展 到可对数据库进行查询和访问，进而发展到对数据库的即时遍历。数据挖掘 使数据库技术进入了一个更高级的阶段，它不仅能对过去的数据进行查询和 遍历，并且能够找出过去数据之间的潜在联系，从而促进信息的传递。现在 数据挖掘技术在商业应用中已经可以马上投入使用。数据挖掘涉及多种学科 的相关技术，包括数据库技术、概率与数理统计、机器学习、高性能计算、 数据可视化等。其中数据库技术是数据挖掘的基础，因为数据库为数据挖掘 提供数据来源，而数据挖掘则为数据库提供智能化的分析手段。与机器学习 等其他人工智能技术相比，数据挖掘有其自身的特点。数据挖掘通常并不产 生精确的结果，而是基于概率的统计规律。这意味着有些被发现的模式并非 对数据库中的所有数据都成立，通常每个被发现的模式带有一个确定性或“可 信性度量。 所谓数据挖掘，就是从存放在数据库、数据仓库或其它信息库中的大规 模数据集合中自动抽取出新的、有意义的、可理解的有用模式或模型【1 6 q 9 1 。 4 哈尔滨t 稃大学硕+ 学位论文 数据挖掘过程包括如下几个步骤：选择抽取、预处理、转换、挖掘、表达与 分析评价。 2 1 2 数据挖掘任务的分类 按照挖掘功能，数据挖掘任务可以分为预测与描述两大类，如图2 1 所 示。预测挖掘( p r e d i c t i o n ) ：预测挖掘依据已知的数据，构造可以预测未来 或未知数据值的模型，又可以进一步分为分类、回归分析、预测挖掘、时间 序列数据分析等。描述挖掘( d e s c r i p t i o n ) 则是发掘现有数据的特性，而不 是预测新的属性，又包括聚类、汇总、关联规则、序列挖掘等。其中分类、 聚类、关联规则是重要的挖掘类型，举例说明如下： r 分类与预测 厂预测煳士嚣篇未析 il 预测挖掘 数据挖掘1广聚类分析 卜汇总厂频繁项集 l 描述挖掘十关联规则十频繁序列 频繁模式挖掘 卜序列模式l 频繁子结构j 卜孤立点分析 l 数据特征化与区分 2 2 数据流 2 2 1 数据流概念及特点 图2 i 数据挖掘的分类 随着信息技术的发展，现在越来越多的应用中数据以流的形式出现，例 如，网络监控、股票交易、w e b 日志记录、传感器网络等，这些数据大都是 连续的数据流，与过去的那种单次查询相反，用户需要长期的、连续的查询， 这就对数据库系统以及数据的处理算法等提出了新的挑战【2 们。 数据流1 2 l 】是一种潜在无限的、连续快速的、随时间不断变化的数据序列。 形式化表示如下：令t 表示任一时间戳，巩表示在该时间戳到达的数据，数 5 哈尔滨丁程大学硕十学位论文 据流可以表示成 ，a t - l a t ，a t + l ， 。 与传统关系型数据相比，数据流具有无限性、未知性和不可再现性等特 点【2 2 1 。 1 无限性 数据流是不断到来的，若要将其全部存储，需要的存储空间是无限的。 传统数据形式的数据量也可以是非常巨大的，但是数据流在数据量大的同时， 还强调了这些数据的到来可能是无限的，即你无法判断最终的数据量的大小。 2 未知性 数据流的数据值是不断改变的，利用预测方法也不能准确地预测下一时 刻将到来的数据值。数据流管理系统d s m s 无法知道下个到达的数据是什么， 甚至在同一个数据流中，d s m s 也无法控制待处理的数据记录顺序。 3 不可再现性 对于数据流上的数据，一旦流过处理节点就不会再次出现。由于数据流 的特点，数据量太大、数据产生的速度太快，所以算法不能随机地访问数据， 而且只能一遍扫描所有的数据。如果要完整、详细地收集这些数据，清洗后 将其储存在数据库中，再交由计算机仔细处理已成为不可能完成的任务。需 要新的数据挖掘算法、新的查询检索方法来分析和管理数据流信息。 2 2 2 数据流处理技术 现在己经有一些技术通过计算和统计理论来解决数据流挖掘过程中产生 的问题和挑战。这些处理技术可以总结为基于数据的和基于任务的处理技术。 在基于数据的处理技术中，主要思想是通过检测整个数据集的一个子集或者 将数据变换成一个合适大小的代表性的数据集。在基于任务的处理技术中， 采用计算理论来得到时间和空间有效的解决方案。 基于数据的技术通过概括整个数据集或者选择到来的数据流的一个子集 进行分析。概要数据结构【2 3 和聚集技术代表了前者，采样、降载、略图技术 代表了后者。 1 概要数据结构 概要数据结构( s y n o p s i sd a t as t r u c t u r e s ) 是在流数据处理系统中，由于数 6 哈尔滨丁程大学硕十学伊论文 据量远大于可用内存，系统无法在内存中保存所有扫描过的数据，而流数据 查询与挖掘经常会要求读取这些数据。为了避免代价昂贵的磁盘存取，流数 据处理系统必须在内存维持一个概要数据结构，以保留扫描过的信息。已经 提出的概要数据结构有直方图、小波变换。由于概要数据结构不能代表数据 集的所有特性，所以当使用概要数据结构时产生的结果是近似的。 直方图【2 4 之6 】是将一个大数据集划分为很多个连续的桶( b u c k e t ) ，即小数 据集，每个桶都由一个数字来代表其特征。直方图表示法直观、简洁，能够 很好地表示大数据集的轮廓，因此广泛地应用于一些商业数据库。传统的直 方图包括等宽直方图、等深直方图和v - 优化直方图等。等宽直方图最简单， 把整个值域分成等宽长度的桶，等深直方图每个存储桶中的元组数据相同，v 优化直方图使存储桶中的差分最小，每个桶的宽度可以是不相等的。数据流 环境中使用比较有效的直方图是等深直方图和v - 优化直方图。 小波变换【2 7 渤】是函数信号分层分解的数学工具，是一种通用的数字信号 处理技术。类似于傅立叶变换，小波分析根据输入的模拟量或数字量，变换 成一系列的小波参数，并且少数几个小波参数就拥有大部分能量。根据这个 特性，可以选择少数小波参数，近似还原原始信号。小波变换可用t 范围查 询的选择性估计，另外小波变换可以提高随机采样和直方图的效率。 2 聚集 聚集( a g g r e g a t i o n ) 试图通过计算一些统计度量，诸如平均数和方差等 来概括当前的数据流，是一个计算统计过程的方法。不过类似所有统计学的 方法，它不适合速率高度摇摆和分布式的数据流，但它仍然是数据流挖掘中 的重要工具。聚集所产生的一个问题是，不能很好的代表数据分布高度变化 的数据集，己经有算法对合并在线的聚集进行离线挖掘进行了研究。 3 采样 采样【3 0 】技术( s a m p l i n g ) 从数据集中抽取小部分数据代表整个数据集， 并根据该样本集合获得查询结果。采样方法可以分成均匀采样( u n i f o r m s a m p l i n g ) 和偏倚采样( b i a s e ds a m p l i n g ) 两种。在均匀抽样方法中，数据集中各 元素以相同的概率被选取到样本集合中；而在偏倚抽样方法中，不同元素的 哈尔滨t 程大学硕十学位论文 入选几率可能不同。采样技术是一种使用了很长时间的统计技术，最简单的 一种采样技术是随机采样。使用采样技术来进行数据流分析的一个问题是数 据集的大小是未知的，此外，在对数据流进行不规则或者监督分析时使用采 样技术将会出现问题，采样技术不能解决数据分布变化的情况。 4 降载 降载技术( l o a ds h e d d i n g ) 在负载过大时直接丢弃一些数据项。当输入 速率超过系统处理能力时，系统会产生过载且性能下降，为了解决这一问题， 降载技术是有效的途径之一。降载技术是丢弃数据流中的一系列数据的处理 过程，成功的应用于数据流的查询中。然而，降载用于挖掘还存在一些问题， 因为抛弃的数据可能要用于挖掘模型的构建。对于时间序列分析来说，这可 能意味着抛弃一个有用的模式。 5 略图 略图技术对数据作垂直取样，使用很小的空间来描述数据的分布，将数 据流中的数据映射到建立的数据结构中。略图技术已经被应用于比较不同的 数据流和聚集查询中，主要缺点是精度比较差。 基于任务的技术是修改现存技术或发明新的技术解决数据流中计算的处 理方法。基于任务的技术主要有近似算法、窗口和算法输出粒度。 1 近似算法 近似算法( a l g o r i t h ma p p r o x i m a t i o n ) 近似算法能够在保证近似结果误 差范围内为n p 难题提供一些计算代价较小的近似解，其根源于算法设计，用 于解决复杂的计算问题，能够在一定的错误范围内给出近似的答案。在资源 受限的数据流环境下，近似算法在降低计算复杂度方面具有举足轻重的地位。 由于数据流的连续性和无限性，使得计算数据流查询的一个精确答案所需的 存储空间可能也会无限增长，这在现实中是不可行的，所以只能用有限的空 间来计算查询值。但当临时空间受到限制时，又不可能总能够计算查询的精 确值，这时可以使用近似值来代替精确值。假定一个近似算法的返回结果为 随机变量，希望得到该随机变量尾概率的界。 2 窗口 哈尔滨丁程大学硕士学位论文 窗口技术( w i n d o w ) 是基于用户对最近产生的数据更感兴趣而产生的， 该技术详细分析了最近的数据项集并且总结了以前的数据项集。窗口技术在 输入数据流上开窗口，然后对窗口内的数据进行访问。滑动窗口基于人们对 最近到达的数据更感兴趣的事实设计而成。滑动窗口详细分析最近的一些数 据而对过去的数据仅做一些概括。其基本思想是：仅仅基于最近的数据做出 决策，而不是对目前为止看到的所有数据或对某个样本进行计算。 窗口技术可以用来近似查询，除此之外，许多用户也会在查询中显式指 明要求对数据流开窗，用以完成一些与时间相关的查询。 3 算法输出粒度 算法输出粒度( a l g o r i t h mo u t p u tg r a n u l a r i t y ，a o g 缩写) 是指把若干个 相似的数据聚成一个颗粒后进行处理，能在一定的时间范围内利用有限的内 存和处理速度来处理波动的高速数据，a o g 在有限资源的机器上接收数据流 进行数据分析。a o g 有三个主要阶段：根据计算资源聚成颗粒，挖掘，内存 耗尽时合并挖掘出的知识。 2 3 频繁模式挖掘 2 3 1 频繁模式挖掘的基本概念 频繁模式挖掘或者叫频繁项集挖掘，是指在给定事务数据库中找出所有 满足最小支持度阈值( 由用户定义) 的模式问题，是许多数据挖掘任务中最 基本、最重要、也是最关键的一步。 设i = ，之，乙) 是由m 个不同的项目( i t e m ) 所组成的集合， 每一个项目可以是- - 并d e 商品或一个网页，不同的项目所组成的集合称为项集 【3 2 】，由k 个项目所组成的集合称为k 项集。d 代表一个事务数据库，简称为 数据库，d 中的一条事务t 是i 中一组项目的集合，即r ，。每个事务有一 个标识符，称作t i d 。一条事务t 包含项集x 当且仅当xs 丁。项集x 在d 中的覆盖( c o v e r ) 是由d 中包含项集x 的所有事务的t i d 组成的集合： c o v e r ( x ，d ) = t i dxtid(2-1) 项集x 在d 中的支持度( s u p p o r t ) 是d 中包含项集x 的事务数占d 中事 0 哈尔滨t 稃大学硕十学位论文 务总数的比例： s u pp 。( x ，d ) ： c o ve 示r ( x r , d 一) ( 2 2 ) l l 因为i d i 的值是一定的，为了方便有时也用i c o y e r ( x ，d ) i 表示支持度。满 足最小支持度阈值的项集被称为频繁项集。最小支持度阈值。是由用户指 定的一个阈值，0 。1 ，代表用户认可的频繁项集的最低出现频率。 从频繁模式挖掘领域中众多的研究来看，在数据库中挖掘频繁模式有以 下特征： ( 1 ) 涉及的数据库对象往往很大，挖掘时间很长； ( 2 ) 返回的频繁模式数量很大，存在大量兀余； ( 3 ) 用户为得到合适的频繁模式，需要不断调整最小支持度阈值： ( 4 ) 数据库处在有规律的更新之中，频繁模式也随之发生变化。 这些都给频繁模式的挖掘和维护带来了极大的挑战。因此，要想使频繁 模式挖掘技术切实可行，必须解决以下三个关键问题： ( 1 ) 设计并实现高效的挖掘算法来提高效率； ( 2 ) 研究频繁模式的无损压缩技术来减少冗余； ( 3 ) 设计并实现高效的算法来更新、维护和管理己经发现的频繁模式。 频繁模式挖掘的问题可以看作是一个搜索问题，目标是在数据库空间中 以尽可能高的效率搜索频繁模式。频繁模式挖掘的搜索空间并不等同于数据 库空间，数据库空间是物理数据空间，而搜索空间是逻辑数据空间。频繁模 式挖掘算法的搜索空间大小取决于许多因素，主要有： 1 数据库记录的数目：以记录为单位的数据库规模是决定搜索空间大小的 最主要因素。 2 数据库包含的项目数：数据库记录的属性即是数据库记录包含的项目。 数据库中可能的频繁模式数与数据库记录包含的项目数之间呈指数关系。 3 数据库记录和频繁模式的长度：在数据库记录数目一定的前提下，数 据库记录和频繁模式的平均长度越长，频繁模式挖掘算法的搜索空间就越大。 4 数据库的类型：尽管没有严格的界定方式，在频繁模式挖掘的实践中， 1 0 哈尔滨t 稃大学硕十学伊论文 人们仍然将数据库分为两种，即稠密数据库和稀疏数据库。 5 搜索的策略：对于同样的数据库，算法采用的策略方式不同，搜索的 空间也有很大差别。 对数据库中存在的频繁模式进行挖掘是数据挖掘中的一个重要方向。频 繁模式挖掘是关联规则、序列模式、因果关系、最大模式、多维模式等众多 挖掘问题的核心，已成为近年数据挖掘领域的研究热点。 频繁模式挖掘通常用于进一步产生关联规则，或直接作为决策支持的辅 助信息，主要应用于分类设计、交叉购物等。典型的例子是购物篮分析，通 过了解哪些商品频繁地被顾客同时购买，可以帮助零售商制订营销策略。 2 3 2 频繁模式挖掘的分类 根据频繁模式挖掘的结果集，可以分为完全频繁模式挖掘和部分频繁模 式挖掘。完全频繁模式挖掘得到数据库中包含的全部频繁模式，在最小支持 度阈值较小的情况下，结果集的规模可能会很大，使用户无法从中得到有价 值的信息。部分频繁模式挖掘得到一个比较小的结果集。目前部分频繁模式 挖掘主要有最大频繁模式挖掘和频繁闭项集挖掘。如果模式p 是最大频繁模 式，则包含p 的任何模式都是非频繁的模式。而如果模式p 是频繁闭项集， 则包含p 的任何模式的支持度都小于p 的支持度。显然，频繁闭项集是频繁 模式的子集，而最大频繁模式又是频繁闭项集的子集。 1 完全频繁模式挖掘 项目集合完全频繁模式挖掘的事务数据库通常用关系数据库中的一个二 维表来表示，这个表的每一行代表一个事务，每个事务都有一个t i d 作为其 标号，事务中包含的项目作为表的属性。在频繁模式挖掘的实践中，通常从 两个不同角度来看待这个二维表，又称为事务数据库的两种不同的布局。一 种布局是从水平方向来看二维表，表的每一行代表一个事务，每个事务都有 一个t i d 作为其标号，称为事务数据库的水平布局。另一种布局是从垂直方 向来看二维表，表的每一行代表一个项目，称为事务数据库的垂直布局。 2 部分频繁模式挖掘 部分频繁模式挖掘的结果集只包含全部频繁模式的一部分，目前主要有 1 1 哈尔滨t 稃大学石页十学位论文 最大频繁模式挖掘和频繁闭项集挖掘。 2 3 - 3 频繁模式挖掘面临的挑战 ( 1 ) 频繁项集挖掘算法的效率还有待进一步提高 虽然与经典的a p r i o r i 算法【33 】相比，近年来出现的算法在效率上已经不可 同日而语，但是从应用的意义上来看，提高算法的效率仍然是频繁项集挖掘 算法研究的首要目标。限制算法效率进一步提高的主要因素是人们对基于内 存算法的认识问题，由于有了对a p r i o r i 算法缺点的认识，近年来出现的算法 几乎都是基于内存的。基于内存的算法已经将i o 开销减少到了最低限度， 因此要进一步提高算法效率，只能通过提高数据在内存中被处理的速度来实 现。一些学者试图通过设计复杂的算法来实现提高算法效率的目标，这使得 近年来出现的算法呈现出一种复杂化的趋势，一些算法甚至很难被读懂。 虽然其中的一些算法确实提高了效率，但却很难进一步改进。算法的复 杂化意味着c p u 要执行更多的操作，过于复杂的算法不可能将时间和空间复 杂性降低到一个令人满意的程度。只有过程简单的算法才有进一步扩展的空 间，事实上，具有开创意义的经典算法，如a p r i o r i 算法和f p g r o w t h t 3 4 】算法 都是过程简单的算法。因此，应当致力于开发过程简单而又高效的算法，除 了算法的效率之外，还应将算法过程的复杂性作为衡量算法优劣的一个标准。 为了将数据库压缩于内存，人们提出了多种新颖的数据结构。r a g r a w a 提出的t r e e p r o j e c t i o n 算法是一种基于内存的算法，采用字典树( l e x i c o g r h i c t r e e ) 将数据库压缩于内存【3 5 1 。t r e e p r o j e c t i o n 算法采用广度优先的策略建 立字典树，并与深度优先的策略相结合进行事务投影和计数。在频繁模式的 计算过程中，还利用矩阵进行支持度计算，该算法比a p r i o r i 算法快了一个数 量级。 ( 2 ) 对基于内存算法所使用的数据结构的研究不够 基于内存算法的核心是使用一种特殊的数据结构将数据库保存在内存 中，目前基于内存算法中常见的数据结构有f p t r e e 、集合枚举树、t i l e 、位 图等。人们将注意力更多地集中在了算法的过程上，而忽略了对这些特殊数 据结构本身的研究。 1 2 哈尔滨工程大学硕十学伊论文 2 4 数据流挖掘 2 4 1 数据流挖掘模型 挖掘算法设计和概要数据结构的设计成为影响整个数据流挖掘过程的关 键要素，其性能的优劣直接影响算法的时间和空间复杂度。在数据流处理中， 由于存储空间的限制，算法的空间复杂度尤为重要，是评价其性能优劣的重 要指标。由此可知，数据流处理的重点就是设计有效的概要数据结构，使其 能够满足数据的近似处理要求，得到误差可控的结果【3 6 】，数据流挖掘模型见 图2 2 。 口 口 m i n gd a t as t r e a m a l g o r i t h m 口 图2 2 数据流挖掘模型 2 4 2 数据流挖掘特点 数据流挖掘算法和传统挖掘算法相对比有其特殊的地方。无论是分类、 聚类还是频繁模式挖掘，数据流上的算法注重的都是一遍扫描数据集，并尽 可能对结果集压缩存储。所有的分类和聚类算法注重模型的定义及再建立， 以取得更好的匹配效果，使得分类或聚类的效果更好，而时间效率并不太关 心；在数据流上进行分类或聚类算法则注意动态的适应数据的变化，尽可能 及时地调整模型，算法的执行速度要达到一定要求，而建模的精确程度没有 过多研究。 数据流实时、连续、有序、快速到达的特点对数据流挖掘算法提出了诸 多挑战，数据流对其算法的要求通常如下： 哈尔滨t 程大学硕十学佗论文 ( 1 ) 单次遍历 数据流数据有着严格的时序关系，这就要求算法必须能够按数据流中数 据流入的次序读取数据，又因为数据流的快速且数据规模无限大，这使得算 法只能读取数据一次。 ( 2 ) 近似控制 由于一次遍历以及时间与空间效率的限制，读取或存储数据流中全部数 据是不可能或者代价昂贵的。近似控制的作用，就是在理论上保证数据流挖 掘的结果在可控制的范围内，并且近似程度达到实际应用环境的要求。 ( 3 ) 自适应性 数据流数据本身所呈现的现象与概念不是一成不变的，随着数据流产生 数据的现象可能在不断地变化。算法的自适应性是指当数据流内容或流速受 各种因素的影响而发生改变时，算法能够根据这些改变自动调整计算策略与 计算结果。 ( 4 ) 低时间复杂度 数据流挖掘算法是在线处理算法，数据流的流速非常快，为了适应数据 流的速度，客观上要求算法必须快速处理，对数据流中每个数据控制在较短 的时间范围内。算法的时间复杂度通常以每个数据项到来时，更新概要数据 结构或目标计算结果所需要的时间来衡量，理想的情况是算法处理每个数据 项的时间为常数。 ( 5 ) 低空间复杂度 数据流算法可用的空间是有限的，算法的空间复杂度不能随数据量无限 增长。对于算法的空间复杂度，理想的情况是它与数据流长度无关。 基于以上数据流挖掘的特点，传统的数据挖掘方法如果不改进多数不适 合在数据流上挖掘。例如：在数据流中挖掘关联规则时，用基于频集理论的 a p r i o r i 算法获取最大频繁项集，就不能直接应用于数据流上。因为该算法必 须经过多次扫描事物数据库，才能获取最大频繁项集，进而产生关联规则。 还有由于数据流随着时间的变化，新数据将被不断地读入，许多算法在处理 数据时并不能将流入的所有数据堆积处理，即便算法有这样的能力，数据也 1 4 哈尔滨 i 稃大学硕十学位论文 是随着时间的变化不断更新，所以挖掘到的结果也在随时间不断地变化，也 使得挖掘的结果不能是绝对精确的。这就要求数据流的挖掘算法要有一定的 修改能力，即伸缩性。而且基于数据流的高速流入和数据流中的数据量极大 的特点，要求算法的时间复杂度必须较低，必须能够在内存中实现，不能进 行内外存数据交换，因为这样将耗费大量的时间，但由于资源有限算法所占 用的内存也不能过大。综上所述，针对数据流上的挖掘必须使用新的方法， 或者是对传统的方法做出某些改进，使其能适合对流式数据进行挖掘。 2 4 3 数据流挖掘算法 数据流具有以下几种性质：数据快速持续地到达、数据海量、数据到达 有序。在传统的数据挖掘过程中一个重要的问题在于数据获取困难，从而导 致在小样本上出现过配；而如今大量数据迅速到达样本获取不再困难但处理 时的资源消耗成为主要的瓶颈：而且对数据流进行分析时不能忽略另一个重 要性质：数据经过处理后，除非有其特殊价值，否则不进行保存，这主要是 因为内存有限而使用外存增加处理时间。为了和数据流模型相适应，对应的 数据挖掘算法需要能够只需要单遍扫描样本子集就能有效地快速地进行学 习。另外和现实数据相关的数据流还有一些不可以忽略的性质，例如数据分 布可能随时间变化而改变等，这就需要对一定时间内子样本进行学习的结果 进行更新，这样的算法才能自适应数据分布的变化相对于普通的数据挖掘算 法，数据流的算法时空复杂度小，但是大多得到的是相对于普通算法的次优 解，于是对数据流挖掘算法和普通算法差异的界的讨论也是必要的。 1 数据流分类算法 r d o m i n g o s 等人提出了v f d t 算法，v f d t 使用了h o e f f d i n gt r e e ，可以 使用部分子样本快速地建立决策树。不同于普通批处理式方法，h o e f f d i n gt r e e 只是一种近似解决方案，r d o m i n g o s 等人同时证明了其相对于一般决策树的差 异存在一个界。v f d t 使用信息嫡选择属性，通过建立h o e f f d i n g 树来进行决 策支持，并使用h o e f f d i n g 约束来保证高精度地处理高速数据流。既可连续处 哈尔滨t 程大学硕十学伊论文 理数据，也可通过二次抽样，重新扫描数据集，因此可以处理非常庞大的数据 集。v f d t 的另一个特点是增量式学习及随时可用性，所以是一个实时算法， 在学习最初的一些样本之后，就提供一个随时可用、不断优化的决策树。 2 数据流聚类算法 尽管聚类问题在数据库、数据挖掘和统计等领域得到了广泛研究，流数 据的分析仍为聚类算法提出了前所未有的挑战，由于完整甚至部分地存储过 去数据的方法不可行，需要能够只使用新数据就能够追踪聚类变化的算法， 这就要求算法必须是增量式的，对聚类表示要简洁，对新数据的处理要快速， 对噪音和异常数据要稳健。因为数据流可看成是随时间不断变化的无限过程， 其隐含的聚类可能随时间动态地变化而导致聚类质量降低。 3 数据流频繁模式算法 关于流数据的频繁模式算法的挖掘效率和查询精度与两方面有关：模式 的存储结构和历史数据的记录方式。目前较好的解决方法是采用字典树和时 间标签窗。 字典树( 1 e x i c o g r a p h i c t r e e ) 是一种压缩存储结构，在基于字典树的启发式 频繁模式挖掘算法中，判断模式被字典树包含的条件之一是其所有的子模式 都已包含于树中。但在判断时，除了父节点，只能对树进行遍历查找p 的其 余子模式。尽管由于存在关系，只需遍历部分子树，但效率仍然很低。另外， 字典树结构通常较宽，其更新现有模式时横向查找耗时较多。 时间标签窗策略是根据现实中人们对旧知识兴趣度较低、对新知识兴趣 度高的假设，以不同粒度压缩存储历史数据，这样既保留了历史细节，又节 省了空间。批处理方法的流数据分批如果过小，挖掘模式总数会大量增长， 而固定阈值下的频繁模式集不变，因此执行效率很低。 2 4 4 数据流挖掘的关键问题 频繁项集挖掘是找出支持度大于给定支持度的所有项集。由于流数据的 连续性、无限性、高速性及数据分布随时间不断改变这些特性，传统的频繁 项集挖掘方法不再完全适用，这就使得在进行流数据中频繁项集的挖掘时需 1 6