（计算机应用技术专业论文）数据流中topk项频繁闭合模式挖掘研究.pdf

武汉理工火学硕士学位论文 摘要 数据流模型的出现给传统的数据挖掘技术带来的巨大的挑战。由于数据流 连续不断的到来，已有的数据处理技术难以对这些潜在无限的、变化的数据进 行有效的管理和挖掘，因此，必须对数据环境下的数据处理技术进行研究。目 前数据流管理和挖掘技术已经引起了国内外研究人员的广泛关注，成为了当前 的一个研究热点。对于这两方面技术研究不仅具有重要的理论价值，而且在很 多应用领域，如传感器网络、气象的监测与分析，网络监控与安全，w e b 日志 分析等，有着巨大应用前景。本文在对数据流挖掘领域若干问题进行探讨的同 时，主要研究了数据流中t o pk 项频繁闭合项集问题，提出了相应的解决算法并 结合实验结果做了必要的分析。概括地说，本文主要涉及到如下几方面内容： ( 1 ) 对比传统挖掘中使用的大小固定的数据集，分析了数据流的特点。介绍 了目前存在的几种数据流模型以及常用的数据流处理技术。数据流本身的特点 也对数据流挖掘算法提出了一些要求。 ( 2 ) 分析和总结几个传统的频繁模式挖掘算法和数据流中的频繁模式挖掘 算法了解挖掘过程中涉及到的数据集的压缩方法，历史信息的存储结构和存 储方法，新数据到来时数据结构的维护与更新，剪枝策略，结果集输出等方面 内容； ( 3 ) 频繁闭合模式包含频繁项集的完整信息，由它能够得到所有的频繁模式 及其支持度信息，并且数量往往比频繁模式小几个数量级，在实际应用中更容 易理解和应用。本文研究了动态数据流环境下t o pk 项长度不小于给定值的频繁 闭合模式挖掘问题，提出了基于滑动窗口技术挖掘算法，来挖掘最近一段时间 内用户感兴趣的数据中的频繁信息，将用户期望的k 个最频繁的闭合项集显示 给用户，考虑到一些长模式的挖掘，它们子集模式可能由于具有不同的支持度 也成为了闭合项集，且子项集的支持数较高，则子模式较易被输出，为避免输 出结果都是些较短的模式，给定参数m i nl 以设定输出模式的最小长度。算法具 有较好的灵活性和可扩展性，用户可以根据需要，通过调整给定的参数值，让 算法在执行效率和挖掘结果之间取得平衡。 关键词：频繁模式，闭合模式，数据挖掘，数据流 a b s t r a c t t h ee m e r g e n c eo ft h ed a t as t r e a mm o d e lp o s e st r e m e n d o u sc h a l l e n g e s t o t r a d i t i o n a ls k i l l s i nd a t am i n i n g b e c a u s ed a t as t r e a mi sa r r i v i n gc o n t i n u o u s l y ，t o m a n a g ea n dm i n et h e s ep o t e n t i a l l yu n l i m i t e da n dd y n a m i c d a t as t r e a mi sd i f f i c u l tf o r e x i s t i n gd a t ap r o c e s s i n gt e c h n i q u e s ，p e o p l em u s tm a k eas t u d yo fm i n i n gs k i l l s s u i t a l b l ef o rt h ee n v i r o n m e n to fd a t as t r e a m r e c e n t l yt h em a n a g e m e n ta n dm m m g t e c h n i q u e sf o rd a t as t r e a mh a sc a u s e dw i d e l ya t t e n t i o nf r o mr e s e a r c h e r s a th o m ea n d a b r o a da n dh a sb e c o m eah o ts p o ti nt h ef i e l do fs t u d y i ti sm u c hv a l u a b l et os t u d y a b o v e m e n t i o n e dt e c h n i q u e sn o to n l yi nt h e o r yb u ta l s oi nag r e a tm a n ya p p l i c a t i o n a r e a sw h e r ei th a sc h e e r f u lp r o s p e c t ，s u c ha ss e n s o rn e t w o r k ，w e a t h e rm i n i t o r i n ga n d a n a l y s i s ，n e t w o r km i n i t o r ya n ds e c u r i t y ，w e bl o ga n a l y s i sa n ds oo n i nt h i st h e s i s ，w e e x p l o r es e r v a lk e yi s s u e so v e rd a t as t r e a mm i n i n g m e a n w h i l e ，w ep r i m a r i l yr e s e a r c h o nt h ep r o b l e mo fm i n i n gt o pkf r e q u e n tc l o s e dp a t t e m s i ns u m m a r y ，t h i st h e s i s m a i n l yi n v o l v e sf o l l o w i n ga s p e c t s ： ( 1 ) c o m p a r e dt of i x e ds i z e dd a t a s e tu s e di nt r a d i t i o n a ld a t am i n i n g ，w ea n a l y z e t h ec h a r a c t i c so fd a t as t r e a m s ，a n dt h e ni n t r o d u c es e v e r a le x i s t i n gd a t as t r e a mm o d e l s a n dp r o c e s s i n gt e c h n i q u e s 。t h ec h a r a c t e r i s t i c so fd a t as t r e a mi t s e l fh a v ep u tf o r w a r d m a n yc l a i m st om i n i n ga l g o r i t h m so f d a t as t r e a m ( 2 ) w ea n a l y z ea n ds u m m a r i z eaf e wf r e q u e n tp a t t e mm i n i n ga l g o r i t h m su s e di n t h ef i x e dd a t a s e t sa n di nd a t as t r e a m s ，a n dt h e na c q u a i n t eo u r s e l v e s 诚mf o l l o w i n g a s p e c t si n v o l v e di nm i n i n gp r o c e d u r e ，s u c ha st h es t o r a g es t r u c t u r e sa n dm e t h o d so f h i s t o r yi n f o r m a t i o n h o wt om a i n t a i na n du p d a t ed a t as t r u c t u r ew h e nn e wd a t ai s c o m i n g ，t h es t r a t e g i e so fp r u n i n gb r a n c h e s ，t h eo u t p u to f r e s u l ts e ta n ds oo n ( 3 ) f r e q u e n tc l o s e dp a t t e r n sc o n t a i nc o m p l e t ei n f o r m a t i o na b o u ta l lf r e q u e n t p a r e m s ，t h a ti s ，a l lf r e q u e n tp a a e m sa n dt h e i rr e s p e c t i v es u p p o r t sc o u l db ec o m p u t e d t h r o u g hf r e q u e n tc l o s e dp a t t e r n s ，a n dt h en u m b e ri sc o m m o n l yo r d e r so fm a g n i t u d e s m a l l e rt h a nt h a to ff r e q u e n tp a r e r n s t h e nf r e q u e n tc l o s e dp a r e r nt e n d st ob ee a s i e r t ou n d e r s t a n da n db em o r es u i t a b l et oa p p l i c a t i o n si nr e a ll i f e t om i n et o pkf r e q u e n t i i 武汉理工大学硕士学位论文 c l o s e dp a t t e r nw i t ht h e i rl e n g t hn ol e s st h a nag i v e np a r a m e t e rm i n 1i nd a t as t r e a m e n v i r o n m e n ti ss u g g e s t e da n ds t u d i e di n t h i st h e s i s t h e nw ep r o p o s ea na l g o r i t h m b a s e do ns l i d i n gw i n d o wt e c h n i q u et om i n ef r e q u e n ti n f o r m a t i o ni nt h ed a t aw h i c h u s e ri si n t e r e s t e di na tat i m ei m m e d i a t e l yb e f o r et h ep r e s e n t t h ee x p e c t e dt o pkm o s t f r e q u e n tc l o s e di t e m s e t sa l es h o w nt ou s e r i nc o n s i d e r a t i o no fs o m el o n gp a t t e m m i n i n g ，al o n gp a t t e r nm a yc o n t a i ns o m es u b s e t sw h i c ha rel i k e l yt ob e c o m ec l o s e d i t e m s e t sw h e nt h e yh a v ed i f f e r e n ts u p p o a sa n dt h es u p p o r t so ft h e s es u b s e t sa r e g r e a t e rt h a nt h e i rs u p e r s e t ( s ) u n d e rt h i sc i r c u m s t a n c e ，s u bp a r e r n sa r ep r o n et ob e d i s p l a y e d t op r e v e n to u t p u tp a t t e r n st o os h o r t e r ，w eo f f e rap a r a m e t e rm i n lt o r e s t r i c tt h em i n i m u ml e n g t h ，a n dt h el e n g t h so fa l lo u t p u tp a t t e m sm u s tb eg r e a t e r t h a no re q u a lt ot h e m i n 一1 v a l u e t l l i sa l g o r i t h mh a v eg o o df l e x i b i l i t ya n d e x t e n s i b i l i t y ，a c c o r d i n gt ot h en e e do fu s e r s ，t h eb a l a n c eb e t w e e ne f f i c i e n c ya n d e x p e c t e df i n a lr e s u l tc a nb eo b t a i n e dt h r o u g ha d j u s t i n ge i t h e rt h ek v a l u eo rt h em i n 一1 v a l u eo rb o t h k e y w o r d s ：f r e q u e n tp a t t e r n ，c l o s e dp a t t e r n ，d a t am i n i n g ，d a t as t r e a m s i i i 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 研究生( 签名) ： 酶i 盏宣 日期2 盟2 ：f 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ： 塾连堕 导师( 签名) ： 日期一啦 武汉理工大学硕七学位论文 1 1 课题研究背景 第1 章绪论 现代网络、电信和传感网络技术的迅速发展，产生了种新兴且日益流行 的数据存在方式一数据流。它广泛存在于多种应用领域中，包括环境和天文监 测、计算机网络监控、金融股票交易、网页搜索日志分析、电信数据管理等。 对于它的概念，不同的文献给出了大致相同意思的定义。如数据流是一种连续、 高速、无限、时变的有序序列。通常我们认为，按时间顺序先后到达的数据序 列都可以看作是数据流。在研究领域中，人们通常研究具有连续性、高速性、 数据量无限性、数据随时间而改变等特征的数据流。在这些数据流中蕴含着大 量的知识和有用的信息，人们迫切需要获取这些知识和信息，因而数据流的分 析和挖掘日益成为一个研究热点。 经过近十几年的发展，数据挖掘技术得到了广泛的研究。作为数据挖掘研 究中的基础任务，频繁模式挖掘一直是一个热点问题，得到了广泛而深入的研 究，并被广泛应用于关联规则发现、冰山查询、分类和聚类等工作中。结合目 前广泛存在的数据流环境，研究频繁模式挖掘在许多领域有着非常重要的意义， 例如在网络监控和通信工程中，频繁模式可能意味着网络堵塞，而这可能是网 络受到攻击的征兆，通过挖掘频繁模式，能够检测网络异常并找出原因( 诸如 硬件错误、黑客入侵等 以实现快速修复；在商品交易中，频繁模式对应着几 种最畅销的商品以及它们之间可能存在的联系；在w e b 中发现频繁模式，可优 化网站结构，提高网站性能；在传感器网络数据流中发现频繁模式，可灵活组 织传感器，以发现最大量有用数据等等。 频繁模式挖掘无论在理论上还是实际应用方面均得到了广泛的发展并取得 了很多成果，出现了许多经典的算法，但是这些算法难以增量更新，不适合数 据流的挖掘。数据流中的数据量巨大且连续不断的到来，对算法的实时性、自 适应性和空间复杂度都提出了更高的要求。这就给研究人员带来了机遇和挑战。 近年来，数据流中的频繁模式挖掘已成为数据挖掘领域中的热点问题，许多研 究结构和组织都对这一方面进行了研究。 武汉理工大学硕士学位论文 1 2 国内外研究现状 数据流是一个较新的研究领域，国外的许多大学和研究机构已经对其做了 比较深入的探讨，并取得了很多成果。国内对这方面的研究较晚些，但目前 已有一些相关的研究成果及论文出现在各类刊物中。 近年来国内外许多著名的大学和研究机构都开始对数据流方面的问题开展 了研究，提出了一系列的方法、技术及理论。目前的研究内容主要包括以下两 个方面【l 】：数据流管理系统d s m s ( d a t as t r e a mm a n a g e m e n ts y s t e m s ) 和数据流挖 掘( d a t am i n i n go ns t r e a m s ) 。前者侧重于数据流管理系统的开发和相关的技术实 现，如数据流的连续查询、内存管理和系统调度等，研究人员已经对这些内容 进行了研究，并构建出了一些数据流管理系统，如s t r e a m t 2 l ，a u r o r a t 3 】等。 数据流挖掘主要侧重于数据流的在线分析，从聚类、分类、频繁模式挖掘以及 可视化方面做了大量的工作。研究人员已经提出了许多适用于数据流挖掘算法， 并开发出了一些数据流挖掘系统，如u i u c 的m a i d s ( m i n i n ga l a r m i n gi n c i d e n t s f r o md a t as t r e a m s ) ，它是一个集查询、聚类、分类、频繁项挖掘、处理结果可视 化为一体的数据流挖掘系统1 4 】。 在数据流中频繁项集的挖掘方面，许多国外的学者进行了深入的研究并提 出了自己的算法。m a n k u 等提出的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 算法【5 l 是用来挖掘数据流中的频繁项集的两个代表性的算法。m o s e sc h a r i k a r 等借助 于c o u n ts k e t c h 数据结构提出一个通过单次扫描数据来挖掘数据流中频繁项的 算法1 6 j 。g r a h a mc o r m o d e 等提出了c o u n t m i ns k e t c h 数据结构【7 】，该结构可以快 速的进行点查询。g i a r m e l l a 等人等提出了种f p s t r e a m 算法来挖掘数据流上多 个时间粒度的频繁模式。该方法利用倾斜时间窗口策略以较细的时间粒度保存 数据流中最近的频繁模式信息，而以粗糙的时间粒度保存历史数据中的频繁模 式。c h a n g 等提出了e s t d e c 算法【8 j 来挖掘数据流上最近的频繁模式，该方法采用 时间衰减机制逐步减少历史模式的支持数来区分最近事务中的频繁模式和历史 事务中的频繁模式。另外一些研究人员提出了许多改进的算法，并对数据流中 频繁项挖掘的关键技术和理论进行了总结和探讨。 对于t o p k 模式挖掘研究较早的有f u 等人提出了的i t e m s e t l o o p l 9 1 算法。 它挖掘产生长度小于用户自定义长度m 的最频繁的k 个项集。l 0 0 p b a c k 和 b o m 0 1 1 0 】是基于f p t r e e 的t o p k 模式挖掘算法，实验表明 i o i l o o p b a c k 和 2 武汉理丁大学硕士学位论文 b o m o 性能优于i t e m s e t - l o o p 。在此基础上，研究人员又对数据流中t o p k 频繁 项集挖掘问题进行了研究，提出了一些相关算法【叫3 1 。 国内对于数据流领域的研究工作开展得较晚些，但可以看到目前一些研究 人员已经在数据流中频繁项集挖掘方面取得了一定的成果。 周傲英教授等提出并实现了0 万算法【l4 1 ，该算法能够有效的控制内存的消 耗问题。张昕等提出了一种新的启发式算法f p i l s t r e 锄f l 引。该算法结合了倾斜 窗口策略，在及时处理数据流的前提下，降低了数据的平均处理时间，提供了 更细粒度的查询。刘学军等在f p g r o w t h 算法的基础上，提出了f p d s 算法【1 6 】。 算法采用分段的思想逐段挖掘频繁项集。该算法可以有效挖掘所有频繁项集， 尤其适合长频繁项集的挖掘。他们还提出了挖掘滑动窗口中频繁闭合项集 d s c f i 算法【1 7 1 。同样使用滑动窗口技术，李国徽等提出了种m s w 方法【1 8 1 来 挖掘任意滑动时间窗口内频繁模式的。潘云鹤等对数据流中频繁项集挖掘进行 研究和分类，并给出一些相关的研究方向1 1 9 1 。 另外，其他一些研究单位的研究人员也在对数据流中的频繁项挖掘技术进 行研究。 1 3 本文所做的工作 本文首先介绍了数据流中频繁模式挖掘的研究背景和现状，然后概括总结 了数据流的特点及其处理技术。接着对经典的静态频繁模式挖掘算法和数据流 中的频繁模式挖掘算法进行了分析和总结，并选择了v i s u a lc + + 6 0 开发平台实 现了其中几种比较经典的算法。通过以上工作，熟悉和理解频繁模式和频繁闭 合模式的挖掘中所涉及的处理步骤、存储结构、挖掘策略、结果显示等方面的 内容。另外，频繁闭合模式不仅能够决定所有频繁模式的支持度，而且数量比 频繁模式集小得多，在实际应用中往往更容易理解和使用。且由于最小支持度 阈值的设置也是一项困难的任务，研究人员因此提出了t o pk 频繁模式挖掘任务。 虽然对于满足特定约束条件的频繁模式挖掘早有研究，但数据流环境下的这方 面的研究目前尚且不多。在现有的研究成果的基础上，本文研究并提出了数据 流中t o p - k 项频繁闭合模式挖掘方法，采用相应的结构来记录频繁项集和结果集 的动态变化，有效地挖掘了t o p k 项频繁闭合模式。 武汉理工大学硕士学位论文 1 。4 论文组织结构 第一章：对数据流及数据流中频繁模式挖掘的研究背景和现状做了概括和 总结，明确了本文研究的具体目标和任务。 第二章：对数据流的基础知识和处理技术进行总结和分析，同时介绍了目 前常用的数据流挖掘方法和挖掘算法的设计要求。 第三章：介绍了静态频繁模式挖掘算法和数据流中的频繁模式挖掘算法的 设计思想，为接下来的研究奠定理论基础。 第四章：在d s c f i 算法的基础上，设计实现了数据流中满足特定约束条件 的t o p k 项频繁闭合模式挖掘算法，分析其存储方式，更新策略，结果输出，闭 合项集检测等方面的内容。 第五章：根据第四章所讨论的挖掘过程，利用v i s u a lc + + 6 0 开发平台实现 数据流环境下的t o p k 项频繁闭合模式挖掘算法，比较分析实验结果。 第六章：对本文进行简要总结，对今后自己在数据流环境下的频繁模式挖 掘方面的研究工作提出展望。 1 5 本章小结 本章主要讨论课题的研究背景及其意义，介绍数据流中频繁模式挖掘的研 究现状。最后，阐述了本课题所做的研究工作和内容，论文的组织结构，从总 体上明确了接下来研究的具体目标和任务。 4 武汉理工大学硕士学位论文 2 1 数据流 第2 章数据流中的数据挖掘 2 1 1 数据流及其特点 数据流( d a t as t r e a m s ) 是实时的、连续的、有序的项的序列，由到达时间 隐含表示或显示地由时间戳制定。按照固定的次序，这些数据项只能被读取一 次。因此，按照数据项到达的顺序，将数据完整地存储到内存中是不可能的。 在现实世界中，数据流应用非常广泛，例如，网络监控和安全工程、电信 通信纪录、金融业务流、传感器网络、网络日志和网页点击流等。 从数据流形式的数据不同于传统的基于集合的相对静止的数据，归纳起来 有以下几个方面的特点：( 1 ) 连续性数据流中的数据连续不断的到来；( 2 ) 无 限性数据流中的数据是大量的甚至是无限的：( 3 ) 高速性数据流中的数据是 以某种速度不断到来的： ( 4 ) 未知性数据流中的数据随时间不断的变化，采 用预测方法也不能准备地预测下一时刻将到来的数据；( 5 ) 不可再现性对于 数据流上的数据，一旦流过处理节点就不会再次出现。 基于数据流的上述特点，我们可以看出，与传统的关系模型相比，数据流 模型具有以下不同： 1 在数据流模型中，处理的数据不再是能从磁盘和内存中随机访问读取的 数据，而是一个或多个连续的、无穷的数据项组成的时间序列。 2 数据流中数据是实时到达的，而数据库中的数据是存储在磁盘中的。 3 数据流中的数据是按序流过的，不受应用系统所控制。一般只能对数据 进行顺序访问，而磁盘中的数据可以随机访问。 4 数据流中的数据是无限的，而数据库中的数据是有限的。 5 由于在有限的存储空间无法存储无限数据流的全部数据，因此数据流中 的大部分是数据在处理后被丢弃，除非特意保存，否则不能被再次取出处理， 或者再次使用代价昂贵。所以数据流上的查询多数一般只得出近似的查询结果， 而数据库上的查询则可以得到精确的结果。 武汉理工大学硕士学位论文 2 ，1 2 数据流模型 目前，在数据流研究领域中有多种数据流模型，不同的模型有不同的适用 范围，也就需要设计出不同的处理算法。 设输入流口1 ，a ，按下标递增的顺序到达，它们描述了一个信号a ，按照a ， 描述信号的方式，可将数据流模型分为以下几类【2 叫： 1 时间序列( t i m es e r i e s ) 模型 每个a i 等于a i 并且以i 的增序出现，这是 一个对时间序列数据适合的模型，例如，每5 分钟一i p 链接的通信量，或者 n a s d a q 股市每分钟交易量。 2 。现金登记( c a s hr e g i s t e r ) 模型这里a i 代表的是a i j 的增量。令a i = ( j ，i i ) ， i i 2 0 ，意味着a i d = a i 1 j 】+ i i ，其中，a i 是在得到了流数据中的第i 个项之后的 函数状态。多个a i 随着时间推移增加到a i j 。例如，监视访问w e b 服务器i p 地 址，由于同一个i p 地址可能会访问服务器多次或发送多个包流。 3 十字转f - j ( t u r n s t i l e ) 模型此时a i 是a d 】的更新。这里与现金登记模型有 所不同，更新意味着这个值可以是负值。令a j = ( j ，u 0 ，意味着a i j = a i 1 d 】+ u i ， 这里a i 是在得到了数据流中的第i 个项之后函数的状态，u i 可以是正值也是可 以是负值。我们可以看出，与前两个模型相比，这是更一般的模型。它是从繁 忙的地铁站获得的灵感，十字转门模型能够跟踪模拟人们持续到达和离开的过 程，是动态插入和删除的模拟，但是在这个模型中获得有意义的边界是困难。 对于有些细节，如在某些情况下。对于所有的f ，4 f 【，】0 ，这时称其为严格的 十字转门模型。直观地来看，人们只能通过他们进入车站的那个十字转门离开， 这个约束十分强烈，但是它满足许多应用。如在数据库中，某些用户只有删除 自己所插入的记录的权限。另外，有一些十字转门模型是不严格的，即对于某 些i ，a i d 】 0 。如当两个不同的收银机流出现在模型中时，就得到了一个非十字 转门模型。 在这三种模型中，十字转门模型是最具一般性的数据流模型，其适用范围 最广，也最难处理。数据流分类与聚类通常使用的是时序模型，它们将数据流 中的每一项看作一个独立的对象。若将a 啪记为信号j 出现的次数，则流数据频 繁模式挖掘通常使用的是收银机模型，只允许数据的插入。也有算法研究了同 时存在数据插入和删除时的数据流频繁模式挖掘问题。此时算法应用的是数据 6 武汉理工人学硕士学位论文 流的十字转门模型。 2 2 数据流处理技术 数据流环境下海量的数据不断地到来，使得处理数据的时间和空间相对有 限。现有的一些技术主要通过计算和统计理论来解决数据流挖掘过程中所遇到 的问题。这些处理技术可以总结为基于数据的和基于任务的处理技术1 2 1 1 。在基 于数据的处理技术中，主要思想是通过检测整个数据集的一个子集或者将数据 变换成一个合适大小的代表性的数据集。在基于任务的处理技术中，采用计算 理论来得到时间和空间有效地解决方案。 2 2 1 基于数据的技术 基于数据的技术通过概括整个数据集或者选择到来的数据流的一个子集进 行分析。概要数据结构( s y n o p s i sd a t as t r u c t u r e s ) 和聚集( a g g r e g a t i o n ) 技术代表 了前者，采样( s a m p l i n g ) 、降载( l o a ds h e d d i n g ) 、略图( s k e t c h ) 技术代表了后者。 这一小节主要介绍这些技术。 概要数据结构( s y n o p s i sd a t as t r u c t u r e s ) 概要数据结构指的是各种可将数据流进行概括统计的数据结构。己提出的概 要数据结构有直方图( h i s t o g r a m s ) 、小波分析( w a v e l e ta n a l y s i s ) 等。由于概要数 据结构不能代表数据集的所有特性，所以当使用概要数据结构时产生的结果是 近似的。 直方图可用来有效地表示数据集的数据分布，它为原始数据创建多个