数据流频繁项挖掘与聚类分析的研究

论文摘要

随着科学技术的高速发展和信息技术的广泛应用引发了一类新型应用,包括计算机网络流量控制、网络安全监控、金融应用、环境监测和日志分析等。在这些新型的应用中,数据以流的形式产生,它实时、持续、有序地到达。这种由一系列连续且有序的数据组成的序列被称为数据流。与传统数据库不同,数据流具有如下特点:无限性;不可再现性;数据到达速率极快;数据的到达次序不受应用约束。分析和挖掘数据流已成为热点研究问题。数据流挖掘即在流式数据上提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据流挖掘主要是通过挖掘频繁项（集）、分类分析、聚类分析、异常分析等知识发现活动,以寻找数据流中的关联规则、分类规则、聚类模式、异常模式等类型的知识。如挖掘数据流中的频繁项可应用于基于流量的网络计费、网络交通阻塞控制、网络安全监控等。对数据流进行聚类分析可应用于监测网络入侵、在线新闻组过滤、话题识别与跟踪、对交通拥塞与地理环境等进行实时监控、对大型公司中不同顾客群进行划分、检测金融欺诈等。由于存储空间的有限性与数据流的无限性,使得存储数据流中的全部数据以提供精确的挖掘结果是不实际的。因此,在数据流处理模型中,数据流处理算法只存储数据流的概要信息,并随着流中数据不断到来,不断更新流概要,同时根据用户的查询要求,利用所维护的数据流概要信息,为用户提供近似的查询结果。由于频繁项挖掘与聚类分析在网络数据流分析中有着重要的应用,我们主要进行数据流环境下的频繁项挖掘与聚类分析方法的研究。在网络数据流及大量的其它应用领域中,数据类型多种多样,它们不仅包括数值型数据,而且包括非数值型数据,且这些数据经常会有几十甚至几百个属性,使得研究混合属性数据流的聚类及高维属性数据流聚类均具有重要的理论价值与实际意义。以生物系统的机理为基础设计算法和系统是近代研究的热点,并已取得了瞩目成效。而人工免疫系统（AIS）结合了分类器、神经网络和机器推理等系统的一些优点,具有提供新颖的问题解决方法的潜力。同时AIS在数据流聚类中也已有了初步研究,本文针对现有基于AIS的数据流聚类存在的不足,研究新的基于AIS的数据流聚类算法。本文的研究内容和创新工作可概括为以下四个方面。（1）数据流频繁项挖掘算法的研究本文在Bloom Filter的基础上,提出空间效率高、可支持表达庞大数据集及较高查找效率的数据结构—可扩展Bloom Filter,并基于该数据结构提出基于界标窗口模型的数据流频繁项挖掘算法（FI-ESBFL）,同时通过理论证明只需比同类算法中更少的计数器数目即可达到相同的精度与置信度要求。FI-ESBFL可以根据数据流中数据的不同分布及不同的数据项的多少动态调整所使用的内存空间,从而大大减少了内存空间的浪费。实验证明FI-ESBFL具有更高的空间效率与较高的时间效率。本文在FI-EBFSL的基础上还提出了基于衰减窗口模型的数据流频繁项挖掘算法—FI-ESBFD及基于滑动窗口模型的数据流频繁项挖掘算法—FIS-EBFS。FIS-EBFSD具有在一般情况下比同类算法有更高的时间与空间效率。FIS-EBFS具有高效的时间性能。（2）混合属性数据流聚类分析算法的研究本文提出两种不同的基于熵的混合属性数据对象间相似性度量,并在此基础上提出两类混合属性数据流聚类算法——CNCE-Stream与CNCDE-Stream。其中CNCDE-Stream同时利用欧式距离与熵来定义混合属性数据对象间的相似性。在算法CNCE-Stream中,利用单一的量——熵度量混合属性数据对象间的相似性,提出数据流环境下概率密度函数的估计方法—S核方法和带混合属性的类的期望熵计算方法。实验结果表明,CNCDE-Stream与CNCE-Stream均具有较高的聚类质量,且CNCDE-Stream具有很高的时间效率。（3）高维数据流子空间聚类分析算法的研究针对大部分现有的数据流聚类算法只适合于待聚类的数据含有的维度较低的情况及现有数据流子空间聚类算法的不足,本文提出基于网格与密度的高维数据流子空间聚类算法—SOStream。SOStream在线维护一个所有密集网格单元的超集,并提出延迟插入潜在密集网格单元与定期修剪非密集（稀疏）网格单元策略,提高了算法的时间与空间效率。当用户请求时,利用在线维护的密集网格单元生成最终类结构。我们通过实验证明了本算法的有效性。（4）基于人工免疫原理的数据流聚类分析算法的研究本文根据人工免疫系统可动态适应外部环境的变化,提出一种新的基于人工免疫网络的数据流聚类算法—AIN-Stream。AIN-Stream利用外部抗原（流数据）对B细胞的激励作用定义B细胞的激励度,并通过为B细胞创建特征向量,利用统计分析的方法自动确定基于人工免疫聚类算法的关键参数—B细胞识别区域,保证了聚类结果的稳定性。同时,AIN-Stream利用B细胞特征向量中的统计信息更有效地去除冗余B细胞,进一步提高了算法效率。在生成聚类结果时,AIN-Stream无需指定类数,可真正实现无监督聚类。实验表明,AIN-Stream能够动态适应数据流的变化,并具较高的聚类质量,且具有更高的空间效率与明显的时间效率提高。本文提出的算法是对现有数据流上的频繁项挖掘技术与聚类分析技术的补充与改进,理论分析与实验结果表明本文算法能够较为有效地解决相应问题。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 数据流概述
• 1.2.1 数据流模型
• 1.2.2 数据流处理模型
• 1.2.3 数据流处理系统
• 1.3 数据流挖掘
• 1.4 本文研究内容
• 1.5 本文结构
• 第二章 数据流挖掘研究进展
• 2.1 引言
• 2.2 基本技术
• 2.2.1 抽样（Sampling）
• 2.2.2 直方图（Histogram）
• 2.2.3 梗概（Sketch）技术
• 2.2.4 Load Shedding
• 2.2.5 小波方法
• 2.2.6 近似算法
• 2.3 数据流挖掘算法
• 2.3.1 数据流频繁项挖掘算法
• 2.3.2 数据流聚类分析算法
• 2.3.3 其它数据流挖掘算法
• 2.4 数据流挖掘系统
• 2.5 本章小结
• 第三章 数据流频繁项挖掘算法的研究
• 3.1 引言
• 3.2 基于界标窗口模型的数据流频繁项挖掘
• 3.2.1 可扩展的Bloom Filter（ESBF）
• 3.2.2 FI-ESBFL算法
• 3.2.3 理论分析
• 3.2.4 FI-ESBFL算法分析
• 3.3 基于衰减窗口模型的数据流频繁项挖掘
• 3.3.1 FI-ESBFD算法
• 3.3.2 FI-ESBFD算法分析
• 3.4 基于滑动窗口模型的数据流频繁项挖掘
• 3.4.1 FIS-EBFS算法
• 3.4.2 FIS-EBFS算法分析
• 3.5 实验与性能评价
• 3.5.1 FI-ESBFL算法性能
• 3.5.2 FI-ESBFD算法性能
• 3.5.3 FIS-EBFS算法性能
• 3.6 相关工作
• 3.7 本章小结
• 第四章 基于熵的混合属性数据流聚类算法
• 4.1 引言
• 4.2 基于距离与熵的混合属性数据流聚类算法
• 4.2.1 熵
• 4.2.2 CNCDE-Stream算法
• 4.2.3 CNCDE-Stream算法分析
• 4.3 基于熵的混合属性数据流聚类算法
• 4.3.1 传统概率密度函数估计方法
• 4.3.2 S-核方法
• 4.3.3 数据流环境下混合属性数据集合期望熵的计算
• 4.3.4 CNCE-Stream算法
• 4.3.5 CNCE-Stream算法分析
• 4.4 算法实验与性能评价
• 4.5 相关工作
• 4.6 本章小结
• 第五章 基于子空间的数据流聚类算法
• 5.1 引言
• 5.2 基于网格与密度的聚类
• 5.3 基于子空间的数据流聚类算法
• 5.3.1 概念与定义
• 5.3.2 SOStream算法
• 5.4 SOSTREAM算法分析
• 5.5 SOSTREAM算法实验结果与性能评价
• 5.6 相关工作
• 5.7 本章小结
• 第六章 基于人工免疫原理的数据流聚类算法
• 6.1 引言
• 6.2 相关概念
• 6.3 基于人工免疫网络的数据流聚类算法（AIN-STREAM）
• 6.3.1 B细胞特征向量（BCF）结构的维护
• 6.3.2 聚类结果的生成
• 6.4 AIN-STREAM算法分析
• 6.5 AIN-STREAM实验结果与性能分析
• 6.6 相关工作
• 6.7 本章小结
• 第七章 总结与展望
• 7.1 本文工作的总结
• 7.2 未来工作的展望
• 参考文献
• 攻读博士学位期间参与的科研项目及主要成果
• 致谢