数据流聚类分析算法

论文摘要

近年来，许多应用中的数据是以流的形式产生的，例如网络流，传感器数据，以及网页点击流等。分析和挖掘这类数据日益成为一个热点问题。作为一种基础的数据挖掘手段，聚类分析在数据流环境下得到了学术界和工业界的广泛关注。与传统数据库不同，数据流具有如下特点：（1）数据总量的无限性；（2）数据到达的快速性；（3）数据到达次序的无约束性；（4）除非可以保存，每个元素均只能被处理一次。数据流的上述特点对数据流上的聚类挖掘提出了如下要求：首先，算法必须能够进行实时在线挖掘，快速处理每一个元组，并实时输出挖掘处理结果。其次，相对于无限规模的数据流内存通常是有限的，算法的空间复杂度要低，往往需要在数据量的对数范围内。再次，由于算法实时在线挖掘以及对空间复杂度的限制，算法往往只能得到近似解，且需要具有一定的精确度保证。最后，算法要具有较强的适应性，包括对数据流不断进化的底层模型的适应性，处理离群点的能力，以及挖掘任意形状簇的能力等。学术界已经对数据流上的聚类分析问题进行了不少研究工作，但仍存在许多问题尚待研究和解决。本文研究了滑动窗口内的数据流聚类分析问题，数据流中具有任意形状簇的挖掘问题，利用图形处理器加速数据流聚类问题以及分布式数据流的数据聚类问题，旨在为现有的数据流系统提供更为多样的聚类分析功能。本文的主要贡献有如下四个方面：1．本文提出了一种新算法CluWin来解决滑动窗口内数据流聚类分析问题。我们设计了一种新的概要结构—聚类特征指数直方图—来保持滑动窗口中簇的统计信息。CluWin算法仪需要维护O（k/∈log（∈[N/k]））个时间聚类特征结构，就能够估算长度为N的滑动窗口中所有记录的聚类结果，且窗口最大相对差不超过∈。此外，它还被扩展用于解决N-n窗口（滑动窗口扩展模型）数据聚类问题。2．本文提出了一种新算法DenStream用于挖掘进化数据流中具有任意形状的簇。我们引入一种“密”微簇称为核心微簇（core-micro-cluster）用于描述数据流中任意形状的簇，并提出潜在核心微簇（potential core-microcluster）和离群微簇（outlier micro-cluster）结构分别用于维护并区分数据流中潜在的簇和离群点。DenStream基于这些概念包含了一种新颖的淘汰策略，该策略可利用次线性空间的内存维护并保证各微簇权值的精度。3．本文利用性能强大、日趋廉价且在数据流领域尚未引起足够重视的图形处理器（GPU）处理数据流聚类挖掘问题。我们提出一类基于GPU的快速聚类方法，包括基于k-means的基本聚类方法，基于GPU的数据流聚类以及数据流簇进化分析方法。这些方法的共同特点就是充分利用GPU强大的处理能力和流水线特性。与以往具有独立框架的数据流聚类算法不同，基于GPU的聚类算法具有同一框架和多种聚类分析功能，为数据流聚类分析提供了统一平台。4．本文提出了一个分布式聚类处理框架CluDistream。该框架可高效地实时处理分布式数据流中海量数据，有噪声、有损或不完整数据记录，以及有交叠的数据集。在CluDistream基于期望最大化（Expectation Maximization）的算法中，每个数据记录可以以不同的隶属度属于不同的簇。这种软聚类方式能较好地反映簇的交叠性。对有噪声、损坏的或不完整的数据记录，算法可通过最大化数据簇的似然度来学习数据流的底层分布。此外，CluDistream算法中测试后聚类的策略可有效地减少算法的平均处理代价，这对分布式数据流的在线实时聚类挖掘非常有效。总之，本文研究了数据流聚类分析的四个基本问题并分别提出了新的解决方案。滑动窗口是处理数据流的基本模型之一，如何在滑动窗口内对数据流进行聚类分析是一个基本问题；具有任意形状簇相对于球形簇是更为一般的数据簇模型，如何挖掘任意形状的簇也是一个基本问题；如何提高数据流聚类算法的处理速度是一个基本问题，这是由数据流聚类算法实时在线挖掘的特点所决定的；分布式数据流的数据聚类问题，其基础性在于现实应用中数据流往往是在分布式环境中产生的。本文算法是对现有数据流上的聚类分析技术的有益补充和改进。理论分析和实验结果表明本文算法能够高效地解决相应问题，与现有数据流聚类方法相比，本文算法在存储空间开销、挖掘处理速度以及结果准确性上具有优势。

论文目录

• 中文摘要
• 英文摘要
• 图目录
• 表目录
• 第一章 引言
• 1.1 数据流挖掘概述
• 1.1.1 研究背景
• 1.1.2 数据流挖掘与传统数据挖掘的不同
• 1.1.3 数据流计算模型
• 1.2 面临的挑战
• 1.3 本文的主要贡献
• 1.4 本文的组织结构
• 第二章 数据流挖掘研究进展
• 2.1 基本技术
• 2.1.1 抽样（Sampling）
• 2.1.2 梗概（Sketch）
• 2.1.3 概要数据结构（Synopsis Data Structures）
• 2.1.4 近似算法（Approximation algorithms）
• 2.1.5 概率统计（Probabilistic）
• 2.2 数据流挖掘算法
• 2.2.1 数据流聚类算法
• 2.2.2 其它数据流挖掘算法
• 2.2.3 多数据流的监测与挖掘
• 2.3 数据流分析挖掘系统
• 2.4 本章小结
• 第三章 基于滑动窗口的进化数据流聚类
• 3.1 引言
• 3.2 聚类特征指数直方图
• 3.2.1 纳伪聚类特征指数直方图
• 3.2.2 拒真聚类特征指数直方图
• 3.2.3 聚类特征指数直方图的合并
• 3.2.4 与金字塔时间框架进行比较
• 3.3 基于滑动窗口的聚类
• 3.3.1 聚类特征指数直方图组的维护
• 3.3.2 聚类结果的生成和优化
• 3.3.3 N-n窗口聚类
• 3.3.4 进化分析
• 3.4 理论分析
• 3.5 性能评价
• 3.5.1 实验设置
• 3.5.2 实验结果与分析
• 3.6 相关工作
• 3.7 本章小结
• 第四章 基于密度的进化数据流聚类
• 4.1 引言
• 4.2 基本概念
• 4.2.1 核心微簇
• 4.2.2 潜在核心微簇与离群微簇
• 4.3 DenStream聚类算法
• 4.3.1 微簇维护
• 4.3.2 理论分析
• 4.3.3 最终簇的生成
• 4.4 算法技术细节讨论
• 4.4.1 微簇的受限半径
• 4.4.2 微簇的交叠
• 4.5 实验评估
• 4.5.1 数据集和评价指标
• 4.5.2 实验结果与分析
• 4.6 相关工作
• 4.7 本章小结
• 第五章 基于图形处理器的数据流快速聚类
• 5.1 引言
• 5.2 数据流聚类算法分析
• 5.3 图形处理器简介
• 5.3.1 图形处理流水线
• 5.3.2 数据表示与多纹理贴图
• 5.3.3 子素程序与多遍渲染
• 5.3.4 模板测试
• 5.4 基于图形处理器的聚类
• 5.4.1 距离计算
• 5.4.2 基于K-means的聚类
• 5.4.3 数据流聚类算法
• 5.4.4 加速其它传统聚类算法
• 5.5 实验分析
• 5.5.1 算法实现和评价
• 5.5.2 基于k-means的聚类比较
• 5.5.3 数据流聚类比较
• 5.5.4 簇进化在线聚类性能比较
• 5.6 相关工作
• 5.7 本章小结
• 第六章 分布式数据流聚类
• 6.1 引言
• 6.2 问题定义
• 6.2.1 分布式数据流网络结构
• 6.2.2 经典期望最大化算法
• 6.3 分布式数据流聚类框架
• 6.3.1 远程站点处理
• 6.3.2 测试后聚类的理论依据
• 6.3.3 协调站点处理
• 6.3.4 接收到更新时的处理
• 6.3.5 减少通讯代价
• 6.4 扩展解决相关问题
• 6.5 性能评价
• 6.5.1 实验设置
• 6.5.2 实验结果与分析
• 6.6 相关工作
• 6.7 本章小结
• 第七章 总结与展望
• 7.1 本文工作的总结
• 7.2 未来工作的展望
• 参考文献
• 攻读博士期间发表论文
• 致谢