数据流频繁模式挖掘及预测技术研究_陈辉著.pdf

书书书数据流频繁模式挖掘及预测技术研究陈辉著江西高校出版社书书书图书在版编目(C I P)数据数据流频繁模式挖掘及预测技术研究/陈辉著 南昌:江西高校出版社，2010 6ISBN 978 7 81132 932 2.数 .陈 .数据采集 研究.TP311 13中国版本图书馆 CIP 数据核字(2010)第 113664 号出 版 发 行社址邮 政 编 码总编室电话销 售 电 话网址印刷照排经销开本印张字数版次印数书号定价江西高校出版社江西省南昌市洪都北大道 96 号330046(0791)8504319(0791)8513417www juacp com南昌市光华印刷有限责任公司江西太元科技有限公司照排部各地新华书店850mm 1168mm1/324 875130 千字2010 年 6 月第 1 版第 1 次印刷1 200 册ISBN 978 7 81132 932 218 00 元赣版权登字 07 2010 12版权所有侵权必究前言在过去的几年里，数据流(Data Stream)广泛出现在传感器网络、金融证券管理、网络监控、Web 日志以及通信数据在线分析等应用领域中。由于数据流中数据的规模一般都十分庞大、且增长迅速，因此，有限的存储空间根本无法完整地保存数据流的全部数据，这给数据流的数据处理带来了巨大的挑战。此外，由于数据流数据的连续性与流动性，随着流数据连续到达，数据流所包含的知识信息总是在连续不断地变化。而对于实际的数据流应用而言，挖掘出数据流上知识的变化趋势往往比挖掘知识本身更为重要。因此，人们往往更希望挖掘出数据流上最近的某个滑动时间窗口内交易数据所包含的知识信息。挖掘数据流上的频繁模式对于数据流的应用有着重要研究意义，例如，在网络监控中，对应于异常流量的频繁模式可能意味着存在网络攻击或者网络拥塞;在商业销售记录中，频繁模式总是反映那些热门销售的产品以及它们之间的关联关系;而在传感器网络数据管理中，挖掘其中的频繁数据集可以有助于去估计那些丢失的数据值。然而，由于流数据的特点，传统的静态数据库挖掘方法不可能直接应用流数据的频繁模式挖掘，而必须研究新的数据流频繁模式挖掘方法。此外，很多数据流应用不仅要分析数据流上当前的模式信息，还要能够预测和评估数据流未来流数据的模式信息，研究适合数据流的预测查询算法也是数据流研究中的重要工作之一。本书分七章来研究数据流频繁模式挖掘及预测查询算法。第一章为绪论，介绍数据流产生的背景及特点，重点介绍数据流管理及数据流挖掘的国内外研究现状，最后还通过一系列的实际应用来阐述了数据流研究的应用意义。第二章介绍数据流处理模型及数据流处1前言理算法所必备的技术特点，归纳数据流处理的常用技术、数据流的窗口模型及常见的频繁模式挖掘方法，提出流数据频繁模式挖掘存在的技术难点，并对本书中所用到的专有名词进行定义与解释。第三章讨论一种快速挖掘数据流上最近的频繁模式的方法，该方法应用保守计算策略计算滑动时间窗口内模式的近似支持数，由于保守计算策略得到的近似支持数总大于或等于模式的真实支持数，因此，方法总能够保证模式挖掘的正确性。第四章研究一种挖掘大小可调的滑动时间窗口内频繁模式的方法，该方法应用时间衰减模型逐渐减小数据所包含模式支持数的权重，并以此来区分新产生流数据与历史流数据所包含的模式。为了保证模式挖掘的覆盖率和精度，方法还分析时间衰减模型对模式支持数的影响，并给出衰减因子在保证模式挖掘正确性条件下的临界值。当滑动时间窗口的大小改变时，仅需重新设定合适的衰减因子的值即可重新保证在新的滑动时间窗口下模式挖掘的正确性。第五章研究一种频繁模式支持度门限不定条件下挖掘滑动时间窗口内 Top K 频繁模式的方法，该方法应用Chernoff 边界理论估计窗口内第 K 频繁模式的支持度，并将其用于动态维护窗口内潜在频繁的模式信息;根据理论分析，Chernoff 边界理论能够为模式挖掘的正确性提供了概率保证。第六章研究一种基于马尔可夫模型的数据流预测查询算法，该方法将大小可能无限的流数据空间映射到一个有限的流数据状态空间中，从而将流数据变化序列转变成为一个流数据状态变迁序列。通过使用数据流状态变迁有向图(SSTD)维护流数据状态变迁序列的统计信息，可以得到流数据状态变迁的概率矩阵，从而应用马尔可夫模型可以去预测数据流在未来时刻的可能值。第七章总结全书的工作，并对未来研究工作进行展望。本书由陈辉独立撰写，书中的部分实验内容得到了张琛硕士的大力相助。在写作与出版过程中，得到了江西财经大学科研处各位领导与老师的大力支持，也得到了杨兵博士、程远国博士、向军博士、陈刚博士、魏霞博士等老师和朋友的帮助，在此表示衷心的感谢。还2数据流频繁模式挖掘及预测技术研究要感谢江西财经大学软件与通信工程学院的各位领导和老师，尤其要感谢夏家莉院长、尹爱华副院长、张弛副院长、刘细发博士、黄茂军博士等老师，感谢他们的关心和帮助。由于作者学术水平有限，书中难免存在疏漏和错误，诚恳希望读者批评指正。陈辉2010 年 4 月3前言目录符号11绪论31 1数据流产生背景31 2数据流的特点41 3数据流管理系统现状51 4数据流挖掘技术现状71 4 1数据流聚类技术现状71 4 2数据流分类技术现状91 4 3数据流频繁模式挖掘技术现状101 4 4流数据预测查询技术现状121 5数据流研究的意义122数据流处理技术152 1数据流处理模型152 2数据流挖掘算法特点172 3常用数据流处理技术172 3 1抽样(Sampling)182 3 2小波方法(Wavelet)192 3 3梗概(Sketching)202 3 4直方图(Histogram)222 2 5概率统计(Probabilistic)232 4数据流时间窗口模型242 4 1快照式窗口(Snapshot Window)241目录2 4 2界标式窗口(Landmark Window)242 4 3滑动式窗口(Sliding Window)252 4 4时间衰退(Damped Windows)模型252 5频繁模式挖掘方法252 5 1经典的静态集合的频繁模式挖掘方法252 5 2数据流频繁模式挖掘算法272 6滑动时间窗口频繁模式挖掘282 6 1主要挑战282 6 2基本概念282 7小结303基于保守策略的频繁模式挖掘算法313 1引言313 2保守的频繁模式挖掘策略分析333 2 1流数据窗口333 2 2支持度计算策略343 3保守的频繁模式挖掘策略设计353 3 1RFP tree 结构设计363 3 2增量更新 RFP tree373 3 3RFP tree 树剪枝383 3 4频繁模式输出443 4实验分析453 4 1实验环境453 4 2基本性能分析453 4 3性能比较分析473 5小结494基于衰减机制的频繁模式挖掘算法504 1引言502数据流频繁模式挖掘及预测技术研究4 2基于衰减策略的频繁模式挖掘算法分析514 2 1时间衰减模型514 2 2模型正确性分析524 3基于衰减策略的频繁模式挖掘算法设计574 3 1SW tree 结构设计574 3 2增量更新 SW tree604 3 3SW tree 剪枝614 3 4频繁模式输出634 4实验分析654 4 1实验环境654 4 2基本性能分析664 4 3性能比较分析714 5小结745Top K 频繁模式挖掘算法765 1引言765 2Top K 频繁模式挖掘算法分析785 2 1问题描述与思路785 2 2Chernoff 边界理论795 2 4Top k 频繁模式挖掘815 2 4动态选择 Supk845 3Top K 频繁模式挖掘算法设计845 3 1SWTP tree 结构设计845 3 2动态维护 SWTP tree885 3 3Top k 频繁模式输出935 4实验分析955 4 1实验环境955 4 2性能对比分析965 5小结1033目录6基于马尔可夫模型的预测查询算法1046 1引言1046 2马尔科夫预测模型设计与分析1056 2 1模型设计1066 2 2模型分析1086 3基于马尔可夫模型的预测算法设计1106 3 1动态构建 SSTD1116 3 2数据预处理1126 3 3基于马尔可夫模型的数据预测1156 4实验分析1206 4 1实验环境1206 4 2基本性能分析1216 4 3性能对比分析1266 5小结1287总结与展望1297 1本书总结1297 2研究展望131主要参考文献1324数据流频繁模式挖掘及预测技术研究书书书符号序号符号含义1DS数据流2NDS数据流的大小3SW数据流滑动时间窗口4N数据流滑动时间窗口的大小5A数据流数据项的集合6I模式7l模式 I 中所包含数据项的个数8Ilp模式 I 中长度为 l 的前缀模式9T流数据，也称事务10L流数据 T 中所包含数据项的个数11Ti数据流上第 ith到达的流数据12Tc当前流数据13一种确定的全序排列关系14T事务 T 按照全序关系的投影15最小支持度门限16最大许可误差17sup(I)模式 I 的支持数18freq(I)模式 I 的支持度19TDM时间衰减模型1符号序号符号含义20f衰减因子21supd(I)模式 I 衰减后的支持数22freqd(I)模式 I 衰减后的支持度23DW数据窗口24CDW当前的数据窗口25PDW当前数据窗口之前的那个数据窗口26RFP tree数据流上最近的频繁模式树27SW tree数据流上的滑动时间窗口树28SWTP tree数据流滑动时间窗口内的 Top k 频繁模式树29node数据流频繁模式树节点30IIT数据项索引表31e数据项索引表表项32Root数据流频繁模式树根结点33可信度参数，为大于 0 小于 1 的数34supk数据流滑动时间窗口内第 kth频繁模式的支持数35pr概率36p概率矩阵37SSTD统计状态变迁图38R实数集39N整数集2数据流频繁模式挖掘及预测技术研究1绪论1 1数据流产生背景自 20 世纪 70 年代以来，数据库技术得到了迅速的发展和广泛的应用，传统数据库获得了巨大的成功。但是到了 20 世纪末，随着信息技术的飞速发展，一种新的称为数据流(data stream)1 的应用模型却对它提出了有力的挑战。这种应用模型广泛出现在众多应用领域中，例如金融数据管理、网络监控、通信数据管理、传感器网络等。这类数据的共同特点是:数据连续不断地产生且在时间维度上严格有序，数值不断地变化，数据的规模一般都很庞大且增长迅速1，2。利用传统的数据库技术管理这种数据，需要将数据全部保存在物理介质中，然后再进行各类操作。但是，由于数据流数据源源不断，在有限的存储空间中无法保存数据流的全部数据;而且，数据流应用对数据处理的实时性往往要求很高，这也决定了不可能将数据完全地保存下来，然后再进行处理。因此，现有的数据库技术无法有效处理数据流数据，必须研究新的数据流处理技术3。数据挖掘、联机分析处理、内存数据库、实时数据库、主动查询处理技术和数据库近似查询等技术是数据库领域中当前最为活跃的研究方向。这些技术大都依然以传统数据库为研究基点，适用于持久稳固的数据存储。在数据库管理系统中，插入、更新、删除等操作都没有查询发生频繁，查询结果反映了当前的数据库状态。但是这样的存储方式以及对基于时间的数据非常有限的管理能力无法满足数据流应用的需求。数据流系统中的数据有量大、快速和时变的特点，31绪论所以不能仅仅采用传统方式来处理它们。简单地将数据放到传统的数据库中并对其进行操作是不切实际的，因为大量的数据会造成数据库无法正常使用，而且大部分数据可能很快就会被删除，不需要永久保存，数据更新和查询的效率也非常低，因此如何对数据流进行有效的管理与挖掘是当前亟待解决的问题。自 2000 年以来，数据流管理技术已经引起了数据库界的广泛关注。许多著名的研究机构和大学都开始了这方面的研究，提出了一系列的理论、方法和技术，有力地推动了数据流管理技术的发展。目前的研究工作主要包括两个方面: