高维数据流聚类分析及离群点检测研究

摘要

数据挖掘是在海量数据中提取隐含的、未知的、潜在有用的知识或信息模式的决策支持方法，是20世纪90年代初解决“数据丰富、知识贫乏”问题应运而生的一种新技术．十多年来，众多学者围绕数据挖掘这一主题开展深入而系统的研究与探索工作，并已出现诸多研究成果．特别是近几年来，随着计算机技术深入应用擞据流(Data Stream)作为一类新的数据模型，对现有的数据挖掘技术研究提出了新的要求擞据流广泛出现在诸如金融应用、网络监视、通信数据管理、Web 应用以及传感器网络数据处理等众多领域．由于数据流具有快速、无限、连续、只能一遍扫描等特点，因而对基于数据流模型的数据挖掘技术提出了更高的要求，数据流数据挖掘算法亦已成为重要的研究课题． 在众多的数据挖掘任务中，聚类分析和离群点检测由于其在知识发现中所发挥的重要作用而得到重视和深入研究．目前，针对大规模高维数据的聚类分析和离群点检测问题，研究人员业已提出了一些有效的算法，其中子空间技术是解决其“维数灾难”的方法之一但是高维数据流的数据挖掘算法的研究刚刚起步，“维数灾难”以及数据流数据本身所固有的特性，使得这一研究更具有其特有的难度． 针对数据流中聚类分析的需求以及现有数据流聚类算法无法有效处理高维数据流的不足，本论文首先提出了基于Hoeffding界的高维数据流的子空间聚类发现及维护算法．该算法将数据流分段(分段长度由Hoeffding界确定)，在数据流分段上进行子空间聚类，通过迭代逐步得到满足聚类精度要求的聚类结果．同时针对数据流的动态性，算法对聚类结果进行调整和维护；其次，研究了数据流的聚类演化分析，针对现有算法的局限性，提出了相应的改进算法，并进行理论和实验上的讨论．内容主要包括金字塔时间结构的改进，子空间密集网格的计数方法以及聚类演化分析的策略等；最后针对考察特定时间周期内数据流数据的应用需求，提出了基于时间相关滑动窗口的高维数据流聚类算法．该算法能够有效处理Turnstile型数据流的聚类问题，着重讨论了子空间网格的内存保存机制，滑动窗口中数据的更新方式以及对于Turnstile型数据流的适应性． 本论文还针对高维类别属性数据流离群点检测问题，首先提出了基于加权频繁模式离群因子(WFPOF)的数据流离群点检测算法．该算法利用WFPOF能够有效度量高维数据离群度的特点，结合可适应离群点检测处理需求的数据流频繁模式发现维护方法，快速检测离群点．同时通过数据衰减系数的设定，可以有效的处理数据流数据中的概念转移问题．该算法还对数值属性和混合属性的数据流的处理、数据离群原因的解释以及类离群点检测问题进行了深入讨论．本论文进一步将离群点检测问题扩展到分布式数据流环境下，提出了基于时间相关滑动窗口和WFPOF的高维分布式数据流离群点检测算法．该算法将不同站点的数据流放在同等地位上，将它们作为全局数据流的子集，在每个分布站点上维护本地数据流的频繁模式，并在此基础上由中心站点生成全局频繁模式，而各分布站点利用全局频繁模式计算WFPOtF值，检测本地的离群点．算法对分布环境下站点间的协调通信以及局部频繁模式和全局频繁模式的维护等问题进行了详细的讨论，并通过实验验证了算法的可行性和有效性． 综上，高维数据流中的聚类分析和离群点检测是一类重要的数据挖掘方法，本论文针对与此相关的问题，提出并实现了一系列改进算法．这些新算法在一定程度上完善并丰富了这一领域的研究内容同时将其应用到聚类分析和离群点检测中，获得了比较满意的效果．

目录

文摘

英文文摘

声明

第一章序论

1.1选题依据及意义

1.2数据挖掘研究的理论基础

1.3基于数据流模型的数据挖掘算法

1.4本论文的主要研究内容和组织结构

1.4.1主要研究内容

1.4.2本论文的组织

第二章相关概念与技术

2.1数据流模型及其处理模型

2.1.1数据流模型

2.1.2数据流处理模型

2.2数据流管理系统及挖掘算法研究现状

2.2.1数据流管理系统

2.2.2数据流挖掘算法

2.3聚类分析

2.3.1聚类分析的定义

2.3.2聚类分析的主要方法

2.3.3基于静态数据集的聚类分析研究现状

2.3.4基于数据流数据的聚类分析研究现状

2.4离群点检测

2.4.1离群点的定义

2.4.2离群点检测的主要方法

2.4.3基于静态数据集的离群点检测研究现状

2.4.4基于数据流数据的离群点检测研究现状

2.5维数灾难

2.5.1高维数据对聚类分析的影响

2.5.2高维数据对离群点检测的影响

2.5.3降维处理

2.6数据索引结构

2.7概要数据结构生成方法

2.8本章小结

第三章高维数据流子空间聚类发现及维护

3.1相关工作

3.2相关概念与结论

3.2.1网格单元与选择度

3.2.2 Hoeffding界

3.3 SHStream算法

3.3.1子空间聚类发现算法

3.3.2子空间聚类维护算法

3.4算法性能分析与实验结果

3.4.1复杂度分析

3.4.2实验结果

3.5本章小结

第四章高维数据流聚类演化分析

4.1 CEA-Stream算法及其构造

4.1.1主要思路

4.1.2相关概念

4.1.3在线网格单元统计

4.1.4离线聚类演化分析

4.2算法性能分析与实验结果

4.2.1复杂度分析

4.2.2实验结果

4.3本章小结

第五章基于时间相关滑动窗口的高维数据流聚类

5.1问题描述及相关定义

5.2 CluHSWin算法及其构造

5.2.1时间相关滑动窗口

5.2.2主要思路

5.2.3网格单元信息的保存

5.2.4 CluHSWin的构造

5.3算法性能分析与实验结果

5.3.1复杂度分析

5.3.2实验结果

5.4本章小结

第六章基于频繁模式的高维类别属性数据流离群点检测

6.1相关工作

6.2问题描述及相关定义

6.3 FODFP-Stream算法及其构造

6.3.1动态发现和维护频繁模式

6.3.2 FODFP-Stream算法

6.3.3讨论

6.4算法性能分析与实验结果

6.4.1复杂度分析

6.4.2实验结果

6.5本章小结

第七章分布环境下的高维类别属性数据流离群点检测

7.1相关工作

7.2问题描述及相关定义

7.3 FOD-DStream算法及其构造

7.3.1分布站点上的局部频繁模式发现与维护

7.3.2中心站点上的全局频繁模式发现与维护

7.3.3离群点检测

7.3.4分布站点与中心站点的交互

7.4算法性能分析与实验结果

7.4.1复杂度分析

7.4.2实验结果

7.5本章小结

第八章总结和展望

8.1本文工作的总结

8.2进一步的研究工作

致谢

参考文献

攻读博士期间发表相关文章列表