（计算机软件与理论专业论文）基于倾斜时间窗口的频繁项集挖掘算法研究.pdf

- c l a s s i f i e di n d e x ： 曲 u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo f m e n g a nr e s e a r c ho nm i n i n g f r e q u e n t i t e m s e t s a l g o r i t h m b a s e do nt i t l e d - t i m ew i n d o w c a n did a t e ：x uy a n h o n g s u p e r v i s o r ：z h a n gj i a n p e i a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e ci a lit y ：c o m p u t e rs o f t w a r ea n dt h e o r y d a t eo fs u b m i s s i o n ：j a n u a r y ，2 0 1 0 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：行开够2 日期：衣9 加年罗月心日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：孝寰j 鼋零 日期：i 印年多月世日 导师c 签字，爹坼 醴咖年乡月店日 哈尔滨t 程大学硕十学位论文 摘要 当今的信息社会的中，人们每天都要处理各种各样的信息和数据。随着 信息的爆炸式增长，许多应用中需要处理的数据规模也越来越大，这些数据 以快速的、大量的、按时间顺序连续到达，这种数据模式就是数据流。由于 数据流的流动性和无限性的特点，原有频繁项集挖掘算法已很难完成基于数 据流上的挖掘任务。这些挑战吸引了许多人对数据流中频繁项集挖掘进行了 大量研究。现在，数据流中频繁项集挖掘已成为数据挖掘中的热点之一。 f p s t r e a m 算法可以实现在线挖掘多时间粒度的频繁项集。作为一个经典 的挖掘算法，f p s t r e a m 算法具有较好的时间效率。但它的不足之处在于：算 法使用f p g r o w t h 算法来生成频繁项集和计算支持数，需要很大的内存开销 和时间开销；整个挖掘过程中，所有的历史信息数据都存于内存中，随着时 间的推移内存空间将急剧的膨胀。所以，内存开销巨大是f p s t r e a m 算法最 大的缺点。 针对上述问题，本文将在原算法的基础之上，采用一种新的数据结构 ( l r t i l e 树及树结点) 来存储频繁项集及其对应的倾斜时间窗口。同时引入 了垂直的二进制向量表示法存储事务数据以提高时空效率。由于构造了新的 树结点结构，可以方便地完成l r t i l e 树的线性存储和结点查询。另外将 l r t r i e 树分割为若干子树并以文件的形式存储，在内存中建立项和文件的索 引表，按需调入文件，极大地减少了内存消耗。实验表明，改进后的算法在 不明显降低原算法时间效率的前提下，提高了内存空间利用率。该算法适用 于对时间要求不高，但对内存空间要求较高的应用。 关键词：数据流：频繁项集：二进制向量；l r t i l e 树；内存开销 k 、 o i a b s t r a c t i i lt h ei n f o r m a t i o ns o c i e t y , p e o p l eh a v et op r o c e s sv a r i o u si n f o r m a t i o na n d d a t at o d a y a st h ee x p l o s i v ei n c r e a s eo fi n f o r m a t i o n ，t h es c a l eo ft h ed a t at ob e p f o c e s s e db e c o m e sl a r g e ra n dl a r g e ri nm a n yp r a c t i c a la p p l i c a t i o n s t h e s ed a t a c o n t i n u a l l ya r r i v ew i t hh i g hs p e e d ，h u g ev o l u m ea n di nt i m eo r d e nt h i sd a t a m o d u l ei sc a l l e dd a t as t r e a m t r a d i t i o n a lf r e q u e n ti t e m s e tm i n i n gi s d i f f i c u l tt o c o m p l e t em i n i n gt a s ki nd a t as t r e a mf o ri t s c h a r a c t e r i s t i co fh i g hf l o ws p e e da n d p o t e n t i a l l yi n f i n i t ee l e m e n t sn u m b e r t h e s ec h a l l e n g e sh a v ea t t r a c t e dc o n s i d e r a b l e a t t e n t i o no fm a m m y p e o p l et od o al a r g en u m b e ro fr e s e a r c h e so nf r e q u e n ti t e m s e t m i m n g n o wf r e q u e n ti t e m s e tm i n i n gh a sb e c o m e o n eo ft h em o s th e a t e dt o p i c sm t h ef i e l do fd a t as t r e a m f p s t r e a mi sa no n l i n ea l g o r i t h mw h i c hc a nm i n ef r e q u e n ti t e m s e ta tm u l t i p l e t i m eg r a n u l a r i t i e s a sac l a s s i cm i n i n ga l g o r i t h m ，i th a sg o o dp e r f o r m a n c eo n t i m e b u tt h ed e f i c i e n c yi nt h ea l g o r i t h mi sa sf o l l o w s ：f i r s t ，f p g r o w t ha l g o r i t h mi s u s e dt og e n e r a t ef r e q u e n ti t e m s e t sa n dt h e i rs u p p o r tc o u n t ，w h i c hw i l lc o n s u m e a g r e a td e ：a lo fm a i nm e m o r ya n dr u nt i m e ；s e c o n d ，i n t h ew h o l em i n i n gp r o c e s s ，a l l l l i s t o r i c a ld a t ai ss t o r e di n m a i nm e m o r ya n dt h e n e e do fm e m o r yw i l l e x p o n e n t i a l l yi n c r e a s e a st i m eg o i n go n s o ，t h eb i g g e s td e f i c i e n c y i nt h e a l g o r i t h mi sh u g e c o s to fm a i nm e m o r y a c e o r d i n gt o t h ea b o v e m e n t i o n e dp r o b l e m ，i nt h i sp a p e ran e wd a t a s t r u c t u r e ( l r t r i et r e ea n dt r e en o d e ) i su s e dt o s t o r ef r e q u e n ti t e m s e t sa n dt h e i r t i l t e d t i m ew i n d o wt a b l eb a s e do no r i g i n a la l g o r i t h m a tm e a n t i m e ，t h ea p p r o a c h o fv e r t i c a lb i tv e c t o re x p r e s s i o ni s i n t r o d u c e dt os t o r et r a n s a c t i o nd a t a f o r i m p r o v i n ge f f i c i e n c yo ft i m ea n dm e m o r y d u e t on e ws t r u c t u r eo ft r e en o d e ，d a t a q u e r y i n ga n ds t o r i n gi ns e q u e n c e a r ec o m p l e t e dc o n v e n i e n t l y i na d d i t i o n ，l r - t r i e t r c ei sd i v i d e di n t os o m ed i f f e r e n tf i l e ss t o r e di nd i s ka n dt h ei n d e xl i s tf o rt h e i t e ma n dt h ef i l ei sc r e a t e d w ec a ni m p o r tt h ef i l ea c c o r d i n gn e e ds ot h a tt h ec o s t 哈尔滨丁程大学硕十学位论文 o fm a i nm e m o r yi ss u b s t a n t i a l l yr e d u c e d a sr e s e a r c hs h o w st h a tt h ei m p r o v e d a l g o r i t h mc a na t t a i nh i g h e rs t o r a g eu t i l i z a t i o na tn oc o s ti nm u c hm o r ee x e c u t i o n t i m e s o ，t h ea l g o r i t h mi sw o r k i n gw e l lf o rt h ec a s et h a tt h es y s t e mh a sh i g h “d e m a n do nm a i nm e m o r yb u td on o to nt i m e k e y w o r d s ：d a t as t r e a m ；f r e q u e n ti t e m s e t ；v e r t i c a lb i tv e c t o r ；l r - t r i et r e e ；m a i n i m e m o r yc o s t k _ - r 哈尔滨t 程大学硕十学位论文 目录 第1 章绪论1 1 1 论文研究的目的和意义1 1 2 国内外研究现状2 1 3 课题的研究内容”4 1 4 本文的组织结构4 第2 章数据流及相关技术概述”6 2 1 数据流概述6 2 1 1 数据流的概念及特点”6 2 1 2 数据流处理模型8 2 2 数据流挖掘算法9 2 2 1 数据流分类1 0 2 2 2 数据流聚类1 2 2 2 3 数据流频繁项集挖掘1 3 2 3 数据流频繁项集挖掘的算法1 4 2 3 1 基本概念和性质1 4 2 3 2 常用数据结构1 5 2 3 3 经典算法研究与评析1 9 2 4 本章小结2 1 第3 章基于倾斜时间窗口的频繁项集挖掘算法2 2 3 1f p s t r e a m 算法2 2 3 1 1f p s t r e a m 算法简介”2 2 3 1 2f p s t r e a m 算法描述2 3 3 1 3f p s t r e a m 算法不足2 4 3 2 改进的挖掘算法”2 5 3 2 1 算法改进思想2 5 3 2 2 相关数据表示2 6 1 - 疆 - r 哈尔滨t 程大学硕十学位论文 3 2 3 相关数据结构”2 9 3 2 4 查询更新算法”3 1 3 2 5 批量插入算法”3 5 3 2 6 结点删除算法3 8 3 2 7l r t i l e 树构造算法4 1 3 3 算法整体描述”4 3 3 4 本章小结“4 4 第4 章实验及分析4 5 4 1 数据集介绍4 5 4 2 实验环境介绍”4 6 4 3 实验结果及分析”4 6 4 4 本章小结5 1 结论”5 2 参考文献”5 3 攻读硕士学位期间发表的论文和取得的科研成果5 7 致谢5 8 - i 哈尔滨t 程大学硕十学位论文 第1 章绪论 1 1 论文研究的目的和意义 在当今的信息社会中，人们每天都要处理大量的信息和数据。随着信息 的爆炸式增长，现今许多应用中需要处理的数据规模也越来越大，这些应用 中的数据以快速的、大量的及不可预测和无限的流动方式连续到达。如某网 络流量数据、商场的物品销售记录、股票的交易数据、w e b 点击流、入侵监 测数据等n ，。这样，一种新的数据处理模型也就应运而生：即数据流。数据流 是一个按时间次序不断到达的有序数据序列。它与传统数据库中的静态数据 有很大不同，数据流是连续的、潜在无限的，通常以很高的速率到来而且随 着时间的推移数据模型的特征也在不断变化幢- 。 在数据流中发现频繁项集的过程称为基于数据流的频繁项集挖掘。作为 数据挖掘的基本问题，频繁项集挖掘具有重要的理论意义和应用价值，其相 关的研究成果也已经广泛地应用到很多问题中，如关联规则挖掘、序列模式 挖掘、分类等n ，。在数据流挖掘领域中，频繁项集挖掘在许多应用中也有着非 常重要的意义，例如：在网络流量监控中，频繁项集可能意味着网络堵塞， 而这也就可能是网络受到攻击的征兆，及时发现问题可以避免网络更大的损 失；在大型超市的商品交易记录中，频繁项集可能意味着超市中几种最畅销 的物品间存在着某种联系，可以依此来重新安排货品和货架摆放以达到促销 的目的，。 但是，由于数据流的不间断流动性和潜在无限性的特点，决定了要求系 统能够实时响应查询和处理概念漂移等问题哺，这都使原有频繁项集挖掘算法 难以完成数据流上的挖掘任务。一方面原有传统挖掘算法虽然可完成海量数 据挖掘，但它们无法实现增量式更新，另一方面对于数量潜在无限的流数据 来说数据存储是难以解决的问题之一。所以，为了适应数据流挖掘任务的需 求，挖掘算法不但要吸取传统挖掘算法精髓，而且要不断创新、提出新思想、 哈尔滨_ t 程大学硕十学位论文 选择适当存储结构、融入其他领域的新成果、新技术等，从各个方面全面提 升算法的时空效率。面对这些挑战，许多研究人员已经对数据流中频繁项集 挖掘进行了大量研究。目前，数据流中频繁项集挖掘已成为数据挖掘中的热 点之一。 1 2 国内外研究现状 频繁项集挖掘在理论上已经取得了非凡的成果，而且在很多领域也被广 泛地应用，反过来又促进了理论的研究和发展。所以频繁项集挖掘一直被人 们所关注，出现了许多经典算法，如a p r i o r i 、f pg r o w t h 、c l o s e t 、c h a r m 算法1 。但如前所述，这些传统算法已经不适合数据流挖掘。因为挖掘频繁项 集是一系列连接操作的集合，只有得到了数据集中的全部数据，项集的挖掘 才能正确实现。而事实上，数据流中的事务数据随着时间不断变化，频繁项 集的挖掘和更新也变得很困难 ，。这些问题引起了很多人的兴趣和关注，国内 外的许多研究人员被吸引到此领域中进行不断的研究和创新。因此，此领域 出现了许多具有学习意义和实用价值的研究成果。 1 国内研究现状 张听等提出f p i l - s t r e a m 算法，运用了启发式算法思想。算法中使用了 一种改进的字典序树( i l - t r e e 树) 结构，结合了倾斜时间窗口策略来更新 和生成新频繁项集，其结构可以更细粒度地记录各频繁项集及其历史信息， 也具有不错的时间性能哺，。 刘学军等人提出了f p d s 算法，这实际上也是一种基于f p g r o w t h 算法 的改进算法。算法在保证了挖掘误差小于支持度误差的情况下，实现了对非 频繁项集的大量剪枝，节省了时间和空间n 。 李国徽，陈辉提出了m s w 算法，也是运用了启发式算法思想。算法使 用滑动窗口树随时获取数据流上的信息生成频繁项集，每隔一段时间自动删 除当前窗口中过期的项集和转变为不频繁的项集，很好地降低了内存开销，。 该算法可以实现在一遍扫描的情况下挖掘项集，同时还可以挖掘数据流中任 意大小的滑动窗口内频繁项集。同时，该方法运用了时间衰减模型，对不同 时间的项集其支持度计数赋予了不同的权重，所以近期的事务数据对挖掘结 2 哈尔滨丁程大学硕十学位论文 果的影响更大，更符合实际的需要。 2 国外研究现状 目前在数据流挖掘方面，国外有两个比较有影响的研究小组：一个是 s t a n f o r d 大学的r m o t w a n i 教授领导的研究小组，主要负责数据流管理、查 询等方面的研究；另一个是u i u c 的c a g g a r w a l 和j h a n 教授领导的研究小 组，主要从事数据流分析、聚类、分类、频繁项集挖掘等方面的研究工作n ”。 许多国外学者在数据流挖掘领域进行了深入的研究，并提出了自己的算 法或改进思想。 g u r m e e ts i n g hm a n k u 和r a j e e vm o t w a n i 提出了l o s s yc o u n t i n g 算法，它 是第一个计算数据流频繁度的算法，并且扩展了l o s s yc o u n t i n g 算法来挖掘 数据流中的频繁项集，。l o s s yc o u n t i n g 算法将数据流分成事务数相等的若干 批数据( 桶) ，在每批的边界处对该结构进行更新，删除不频繁的项目，求得 数据流上本批次的频繁项和频繁项集“”。 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 算法。算法中使用了哈希 操作，由于操作快速可以将项目直接映射到s k e t c h 结构中，在时间性能表现 非凡n ”。 g i a n n e l l a 和h a r t 等人提出了f p s t r e a m 算法，运用了批处理的思想，把 数据流分成若干数据段“，。该算法使用了一种倾斜时间窗表格( t i l t e d t i m e w i n d o wt a b l e ) 的数据结构来保存不同时间粒度下的模式信息“”，可以满足时间 敏感的项集挖掘。 h i d b e r 提出的c a r m a 算法，它是基于f p s t r e a m 改进算法。其优点是可 以子模式的频数来估计新产生模式的频数。它通过二次扫描数据来保证算法 的正确性和可靠性，时间性能不高n ”。 c h a n g 等人提出了e s t d e c 算法。算法为每个事务赋予一个权重，该权重 随着时间指数进行衰减，保证了最近发生的频繁项集可以被优先挖掘。算法 采用了字典树结构进行存储，同时引入了c a r m a 算法的估计频数思想n ”。 综上所述，目前关于数据流频繁项集挖掘算法正在被不断地发展和创新， 同时也看到各种算法都有自己的适用范围和不足之处，在算法改进的同往往 又会引入不少新问题。所以，数据流频繁项集挖掘算法的研究有待进一步深 入和讨论。 3 哈尔滨丁程大学硕十学位论文 1 3 课题的研究内容 如上节所述，国内外已经有很多人员对数据流上的频繁项集挖掘算法进 行了研究和探讨并取得了大量的成果。但由于数据流自身的特点，传统算法 在时空上不能很好地适应数据流上的挖掘，而新算法在处理数据流的高速率、 大数据量和准确性问题时又往往处于两难的境地。所以，数据流上的挖掘任 务仍具有挑战性。 本文主要研究数据流上的频繁项集挖掘算法。主要针对经典算法 f p s t r e a m 进行深入研究，力求保持原算法优点的同时克服其不足。实践证明， f p s t r e a m 算法具有较好的时间效率，非常适用于时间敏感的项集挖掘。但它 也有不足之处：算法使用f p g r o w t h 算法来生成频繁项集和计算支持度计数， 需要很大的时空开销，而且整个挖掘过程全部数据都存于内存，随着时间的 推移内存空间将急剧的膨胀。所以内存空间占用巨大是f p s t r e a m 算法最大 的缺点。本文将在原算法的基础之上，采用一种新的数据结构来存储倾斜时 间窗口框架，引入了垂直的二进制表示法存储事务数据以提高时空效率，同 时将倾斜时间窗框架应用于线性存储的l r t r i e ( t r i eb a s e do nl i n e a r r e p r e s e n t a t i o n s ) 树结构。将l r t d e 树分割为若干子树以文件的形式存储，建 立项目与文件的索引表，根据需要将文件调入内存，全面提高空间利用率。 1 4 本文的组织结构 本文总共有4 章，组织结构如下： 第1 章介绍了本课题的研究的目的、意义以及到目前为止一些国内外相 关的研究现状，最后介绍了本文研究的主要内容和文章的组织结构。 第2 章首先对该课题的研究对象数据流做了相关的知识介绍，包括数据 流的概念，特点、模型，数据流挖掘技术分类等。最后较详细地介绍了数据 流上频繁项集挖掘原理：相关概念、技术及经典的算法研究与评价。 第3 章首先针对f p s t r e a m 算法进行深入研究，分析算法不足，并提出 了一种改进的思想。接着对算法的思想、相关数据表示、具体的挖掘算法步 4 哈尔滨下程大学硕十学佗论文 骤进行详细的介绍。 第4 章通过二个方面的实验结果和对比分析，验证l r s t r e a m 算法在内 存空间利用率上的优越性，以及算法的适用范围。 结论部分对全文进行总结并对未来工作进一步展望。 5 哈尔滨t 程大学硕+ 学位论文 第2 章数据流及相关技术概述 2 1 数据流概述 当今的信息社会中，由于实际应用的需要，系统往往需要处理大规模的 数据，这些应用中的数据以快速的、大量的及不可预测和无限的流动方式连 续到达，这种新数据模型就是数据流。 数据流种类很多，在许多行业中都有重要的应用价值。例如：商场销售 货物数据流、由卫星实时监测到的地球海洋表面的数据流、网络中基于网页 的点击流、某地区的电话记录数据流、 流量实时监测等等“”。在网络监测中， 某网站基于时间、事件序列对的网络 研究数据流可以及时发现网络堵塞或 网络异常的征兆，使网络免受进一步的攻击或损失；在商场销售中，研究数 据流可以发现畅销商品之间的关联，对货品采购、摆放陈列都提供了重要的 信息资料。这些数据流都与传统数据库中数据特点不同：增长迅速、按序到 达、随时间变动、数据无限等m ，。可见，流数据与传统的静态数据大不相同， 要考虑到更多因素。 数据流往往意味着有大量的潜在的无限数据，数量巨大，所以系统常常 无法保存数据流的全部数据；而且，数据流中的数据以瞬时的、连续的流入 方式到来，对时间要求高，所以系统必须在流数据到达时及时读取和处理， 不能像传统数据库一样将数据全部存储后，在封闭的数据库上进行挖掘“”。 总之，数据流应用广泛但又难以用传统的数据挖掘方法进行处理。及时 高效地处理数据流并从中挖掘有价值的信息，这对许多应用领域都有重要意 义。 2 1 1 数据流的概念及特点 数据流是由一系列按时间连续到达的数据元素组成，每个数据元素可以 6 哈尔滨t 程大学硕十学何论文 包含若干不等的数据项。数据流的形式化定义如下：如果令t 表示任一时间 戳，玉表示在t 时刻到达的数据元素，则数据流就可以表示为无限的集合s ， s = t a ，t 2 ，t n ，一。 数据流与传统数据库中的静态数据不同，大量数据元素数按序连续到达， 要求d b m s 高效及时的处理不断到来的数据。传统的d b m s 应用中，数据 存于外存磁盘上，所以在任何时间都可以随机的访问这些数据。相反，数据 流既不能保存在磁盘上，也不能在全部的流数据中进行随机存取。数据流有 其自身的特点：数据到达连续性；潜在数量无限性；数据到达高速性；数据 分布动态变化性。 由于数据流的以上特点，决定了数据流处理与传统数据处理的不同伫l j ( 1 ) 在线挖掘。传统数据库中的数据是存储在磁盘等外存中，可供用户 随时访问和处理；但数据流中的数据是连续到达无法全部存储，必须在线及 时处理。 ( 2 ) 不能预知所要处理的数据量。数据流中的数据是大量的、潜在无限 的，这与传统数据库中的有限数据是不同，不可能预知数量的大小。 ( 3 ) 查询结果的近似性。由于传统数据库上的数据是封闭的，不会随着 时间流入和流出，所以查询结果可以很准确。而数据流上的查询只能得到近 似的结果，因为随着时间的增长，数据流挖掘的结果会有所变化：如频繁项 集可以变成不频繁的，非频繁的也可能变为频繁的，这都与查询的时间有着 密切的关系。 ( 4 ) 一遍扫描。由于数据流中的数据以高速率连续到达，既没有足够的 空间存储全部数据，也没有时间再次扫描存储的数据；而传统的数据挖掘大 多是在静态数据库上进行多次扫描完成的。 ( 5 ) 旧数据不可再现性。对于数据流的每个数据元素，一旦流过处理结 点就不可能再次访问。 这些数据流所表现的独有特点，使得传统的挖掘技术和算法都难以适应 数据流挖掘。这对数据流处理技术提了新的挑战：低时间复杂度，高空间利 用率，查询结果的准确性，数据模型的自适应调整等等。 7 哈尔滨下程大学硕十学位论文 2 1 2 数据流处理模型 由于数据流是一个潜在无限、按序连续到达的数据序列，所以在进行数 据挖掘时不可能针对数据流中全部数据进行挖掘，这也是无法实现的。数据 挖掘前的首要工作便是确定挖掘对象。通常的做法是根据需求选取某个连续 时间段内的流数据序列作为处理对象，即数据流的一个子序列。数据处理模 型便是对数据流中数据进行子序列的划分、选择、挖掘的模型。通常根据所 确定的时间段将数据流处理模型分为三类：界标模型、时间衰退模型和滑动 窗口模型。 1 界标模型 界标窗口模型首先要标记称为“界标的时间点。界标模型挖掘的处 理对象为从“界标 时间点开始到当前时间为止范围内数据流子序列，对这 个范围内的流数据信息挖掘频繁项集。很明显，该模型中所记录的历史数据 处于相同地位，无“是否更重要”的区分。所以对那些只关心最近信息的用 户来说，这个数据处理模型就不适用。 2 时间衰退模型 时间衰退模型也被成为快照模型。首先要标记固定的起始点和结束点， 模型将这两个时间点范围内的数据流子序列作为处理对象恤，。该模型中，数 据流中的每一个流数据都有一个相应的权重，新到来的数据其权重值就大， 而旧有数据的权重值随着时间的推移越来越小。这就是说，新到来的数据对 挖掘的影响较大，而旧数据对数据挖掘的影响较小。如果当前的信息对用户 来说更具有使用价值，则这种基于时间权重的考虑是十分必要的。由此可知， 这种模型的处理结果适合于那些非常关心最近信息而对过于久远的历史信息 不感兴趣的用户查询。 3 滑动窗口模型 滑动窗口模型不同于以上二个模型，它既不标记“界标 点也不标记特 殊的起点和结束点。但它需要首先定义窗口的大小，这个窗口的大小通常指 的是挖掘的数据对象所包含的数据元素个数，也可以指数据对象所跨越的时 间间隔大小伫“。这个可以根据应用或系统需求视具体情况而定。当窗口大小 8 哈尔滨t 程大学硕十学位论文 确定后，以窗口范围内的流数据为挖掘对象开始挖掘操作。当数据流的流数 据流入窗口时，处理结点对其进行存储和处理。随着新数据不断的流入，流 入窗口的数据量将达到窗口的上限，这时就开始针对窗口中的数据进行挖掘 操作。当再有新数据到达时，就会发生数据溢出。通常的做法是按先进先出 的原则将多余的旧数据移出窗口，也就是丢弃过期的数据。因为这些数据已 过期，对当前的信息挖掘影响不大，所以滑动窗口本身也体现了时间权重的 思想。总之，该模型挖掘和维护当前窗口内的频繁项集。该模型在数据流挖 掘中应用非常广泛。 这几种模型是相互关联的。一种模型往往是另一种模型在某些情况下的 特例或转化：例如界标窗口模型加上适当的限制条件就可以转变为另外两种 模型；如果在界标窗口模型上加上时间衰退函数，它就转变为时间衰退模型； 如果在界标窗口模型中加一个滑动窗口，在窗口中记录和处理流数据，那么 该模型变为一个滑动窗口模型。 另外，几种模型都有自己的适用范围，例如，在一个商场购物篮数据分 析中，就很难确定用户感兴趣的挖掘时段，因为许多物品的销售都具有季节 性如冰激凌，所以不同的挖掘模型和不同的窗口大小都会影响项集挖掘的准 确性“”。所以，应该根据实际的应用来选择合适的处理模型，这样才能发挥 模型自身的优点。更具体地说，就是选择哪个时间范围的数据流序列作为挖 掘对象应视具体的应用需求而定。 从实际应用来看，以上三种模型中的界标模型和滑动窗口模型被广泛使 用，因为它们以增量方式不断处理新到来的数据，近似程度更高，更接近于 真实应用。 2 2 数据流挖掘算法 数据挖掘就是从大量的数据中挖掘出有用的信息，即从大量的、不完全 的、有噪音的、模糊的、随机的实际应用数据中发现隐含的、规律性的、人 们事先未知的、但又是潜在有用的并且最终可以理解的信息和知识的非平凡 过程汹，。它是一个综合性的学科，整合了很多领域的技术和理论，如数据库、 统计学、模式识别，人工智能、机器学习、离散数学等m 。数据流挖掘是数 9 哈尔滨t 程大学硕十学位论文 据挖掘的重要研究课题，它是从蕴含大量有用信息的流数据序列中挖掘出未 知的、有价值的模式或规律，数据流挖掘技术的潜在应用也是十分广泛的汹，。 如2 1 1 章节所述，传统数据挖掘能以离线方式随机访问数据，而基于数 据流的挖掘过程是在线动态完成的，它必须具有实时高效的处理性能。面对 这些挑战，众多研究者表现出浓厚的兴趣。现在数据流挖掘已经出现了很多 技术和方法。从挖掘功能的角度考虑，目前数据流挖掘大致包括：数据流分 类、数据流聚类和频繁项集挖掘等啪，。 2 2 1 数据流分类 数据分类是一种典型的有监督的机器学习方法。分类就是这样一个过程： 首先提出一个分类函数或分类模型即通常所说的分类器，然后通过分类器将 数据对象映射到某一个已知的类别中啪，。这个过程可由两步完成： ( 1 ) 建立分类模型，这步是有监督的学习过程，。在建立模型前先要选 定训练数据集，集合中的每个数据的所属类别都是它的已知属性，之后通过 对训练集中的数据进行分析和处理形成能反映该数据集自身特点的一个数学 或函数模型( 规则集) ，通常分类学习所获得的模型可以表示为分类规则形式、 决策树形式、数学公式形式等。建模过程如图2 1 所示。 图2 1建模过程 ( 2 ) 使用模型对数据进行分类操作忙”。这里的数据包括测试集数据和新 数据。测试数据集中每个数据的分类标记也是已知的，而新数据集中数据分 类标记未知。算法的最终目的就是根据可信度高的分类模型预测出新数据集 中各数据的类标识。所以，先用与训练集数据不同的测试集来对模型进行检 测，观察模型的分类预测结果与测试集中数据的实际分类之间的差异，进而 评估模型的预测准确度。如果模型准确度可以接受，就可以用它预测新数据 集中的各数据分类了。这个过程如图2 2 所示。 1 0 哈尔滨下稃大学硕+ 学位论文 图2 2 模型测试与使用 与传统数据分类概念相对应，数据流分类可以描述为：通过不断到来的 流数据提出一个分类模型( 或函数) ，持续地将数据通过分类模型映射到某一 已知类别。虽然传统的分类挖掘算法有很多：如决策树算法、贝叶斯算法、 人工神经网络法、k 近邻分类算法、遗传算法、粗糙集等等。但是在这些方 法有一个共同前提，就是数据库中的数据是静态的，而不是动态流动的。传 统分类模型构建是以批处理形式对静态测试数据集执行分类的结果，而对于 数据流来说是分类过程都是在线连续处理完成的。数据流到达速率快，数量 大而无法完全存储，所以传统方法中的多次遍历训练集的做法在数据流挖掘 中是不可行的。如何将传统的分类方法高效地应用于数据流挖掘有待研究。 除此之外，概念漂移也是一个必要考虑的问题。所谓概念漂移就是指随着数 据流中新数据不断到达流入，原有分类模型将发生改变。 目前数据流分类算法中，主要是基于传统决策树算法的改进如h o e f f d i n g 树算法，快速决策树算法和概念自适应快速决策树算法。其次还有一些分类 器系统算法，采取投票的方法考虑多个分类器汹，。 h o e f f d i n g 树算法是比较早地用于解决数据流分类问题的决策树算法。它 的思想为：小样本通常足以选择最佳分裂属性。在处理数据流方面， h o c f f d i n g 树算法优点有：小样本准确率高、对同一数据不会重复扫描、增量 处理方式。由于采用增量处理方式，所以随着流数据的不断流入预测结果更 准确。算法的缺点是时空效率不高，重要的是没有解决概念漂移问题汹，。 v f d t 算法是基于h o e f f d i n g 树进行的分类算法，它使用恒定的时间和内 存空间来处理数据，提高了处理速度和减少了内存开销，满足了数据流高速 处理的要求n ”。算法利用h o c f f d i n g 不等式来确定叶结点进行划分所需要的样 本数目 3 0 。v f d t 算法优点：处理效率表现良好、速度和准确率比传统算法 有很大提高、可以连续处理数据、可以处理大规模的数据。但算法仍不能解 决概念漂移问题，无法反映数据随时问变化的趋势。 c v f d t 算法是在v f d t 算法的基础上，引入滑动窗口技术，并加以改 1 1 哈尔滨t 程大学硕十学位论文 进，实现了对数据分类模型趋势的检测和响应，考虑到了概念漂移问题，时 效性也得到了提高“”。当发生概念漂移时，会生成一棵替代子树并且会随着 新数据不断到达而增长。当替代子树优于原子树时将替换原子树。算法优点： c v f d t 算法准确率高，时间效率高；算法缺点：由于存在子树替代过程，所 以更新较复杂，同时算法不能处理非线性的概念和非线性的概念漂移m ，。 2 2 2 数据流聚类 在现实生活中，人们经常把事物分门别类地加以区分，把特性、性质相 近的事务划分为同一个类别，聚类的任务就在于此。在今天的信息社会中， 针对大量混杂数据进行的聚类分析也有着重要的应用意义。聚类分析是无监 督的学习，它需要同时考虑两个因素：不同对象间的相异度与同类象间的相 似度m ，。相异度可以根据描述对象的属性值计算得出，对象间的距离是最常 采用的度量指标。聚类所生成的簇是一组数据对象的集合，同一个簇中的数 据对象相似度很高，不同簇中的数据对象相似度却非常低即相异度高。基于 簇这样的特征，往往可以将一个簇中的数据对象可以看作一个整体使用c 酊，。 聚类分析的应用范围也很多：如模式识别，图像处理，市场研究等等。 通过聚类，能识别密集的和稀疏的区域，因而发现全局的分布模式，以及数 据属性之间的有趣的相互关系b u 。 与数据流分类算法类似，由于数据流的特点，要求聚类算法能跟上数据 流到达的速率，快速有效的处理流数据。数据流随时间不断变化，这就要求 数据流聚类算法快速增量地处理新数据，方便简单地表示同簇中的相似性与 不同簇中的相异性。 在传统的针对大规模数据集而只进行一次扫描的聚类算法中，有些可直 接应用数据流上的聚类分析：如s q u e e z e r 算法，和b l r c h t 圳算法。s q u e e z e r 算法不需要事先知道聚类的个数，通过一次扫描数据集将数据分割为若干半 径几乎相同的超球体。b l r c h 算法采用聚类特征树来( c f 树) 表示聚类， c f 树是高度平衡树，它实际上是一种层次划分法，。b l r c h 算法包括两个 阶段：第1 阶段一次扫描数据集，构建c f 树；第2 阶段应用算法对c f 树的 叶结点进行聚类提高聚类的准确度旧，。 1 2 哈尔滨t 程大学硕十学位论文 s t r e a m 算法n 和c l u s t r e a m 算法m ，是针对数据流而提出经典聚类算法。 s t r e a m 算法使用的是批处理思想，处理的每批数据大小与内存大小相近， 并且采用了分级聚类的方法。它基于k - m e a n s 算法，使用质心和权值( 类中 数据个数) 表示聚类n ”。处理每批数据时，算法把每批中的数据点分成k 个 簇，并且仅仅保留k 个簇中心点( 而丢弃其余的数据) 来汇总桶中的所有数 据n 们。与传统数据的聚类算法相比，s t r e a m 算法具更好的性能，聚类结果 的可靠性和准确性也有很大提高。但是，s t r e a m 算法没有考虑到过期数据 和近期数据应该具有不同的权重，聚类的结果受过期数据的影响也较大。 c l u s t r e a m 算法一个增量式的处理过程，它把数据流看成是一个随时间不 断变化的数据序列，所以算法的扩展性好、聚类结果质量高。与s t r e a m 算 法相比，c l u s t r e a m 算法使用了倾斜时间窗口框架，可以保存频繁模式树中各 频繁项集及其支持度计数的历史信息，倾斜时间窗口以不同的时间粒度对数 据流信息进行存储和处理，较近的数据变化以较细的时间粒度刻画，而较远 的数据以较粗的时间粒度刻画，可以满足用户对不同时期频繁项集的查询。 该算法由在线和离线两部分构成，在线部分用m i c r o c l u s t e r 定时存储数据流 的摘要信息，对数据的处理和更新是增量式的；离线部分m a c r o c l u s t e r 通过 对在线部分保存的中间结果进行查询操作，得到用户感兴趣的不同时间范围 内数据流的聚类结果n 们。 2 2 3 数据流频繁项集挖掘 频繁项集的挖掘是数据挖掘问题中的基础任务，同时也是研究的热点问 题阳，。快速有效的频繁项集挖掘具有广泛的应用。例如：关联规则挖掘，