基于同步的数据流分层压缩研究

摘要

数据流已成为当前大数据时代数据的主要表现形式之一，如传感器数据、轨迹数据、社交数据、交通数据等都能以数据流形式体现。如何有效地分析和挖掘数据流已成为当前数据挖掘和机器学习研究的重点和难点问题。有别于传统的静态数据，数据流数据具有实时、海量、连续、演化等特征，使得数据流上的挖掘任务比传统数据的挖掘要面临更多的问题和挑战。针对数据流中数据的海量性和实时性，数据流挖掘任务需要在有限的时间和空间下进行。因此，如何有效的对数据流中的数据进行压缩成为数据流挖掘领域的一个重要研究课题。目前传统的数据流压缩方法如采样、投影、降维、聚类等，几乎都针对数据流中数据的海量性或实时性进行研究，往往忽略了数据流的演化特征。因此，如何对具有概念漂移的数据流进行聚类和压缩成为研究的难点，具有重要的理论和实践意义。
　　针对目前数据流压缩存在的问题，本文将聚焦概念漂移下基于同步聚类的数据流压缩算法研究。具体而言，针对数据流的演化性，研究首先提出了一种在概念漂移下基于同步的数据流聚类算法。有别于传统的数据流聚类，新提出的算法提出一种基于同步的微簇结构。该结构不仅能有效的保存数据本身的簇结构，而且可以支持不同粒度的数据聚类。在同步数据流聚类的基础上，进一步提出了基于同步聚类的数据流压缩方法。鉴于同步聚类的优势，压缩算法可以支持不同尺度的压缩率，且可以根据参数估计和聚类参数对压缩后的数据进行重构。因此，本文的研究以基于同步的数据流聚类以及在此基础上的压缩算法构成全文的核心内容。主要的贡献如下：
　　（1）提出了在概念漂移下基于同步的数据流聚类算法。不同于传统的基于簇特征的聚类方法，新提出的算法SyncTree能对数据流中的簇结构进行更好的封装，从而支持更高质量的聚类。更重要的是，基于同步的微簇能有效处理不同形状的簇，同时能有效的对数据流中的聚类演化进行跟踪和描述。此外，为了适应不同存储空间的要求，SyncTree支持不同粒度的聚类。实验结果表明，SyncTree相比目前流行的数据流聚类算法具有更好的性能，尤其是拥有较好的处理数据流演化的能力。
　　（2）提出了基于同步聚类的数据流压缩算法。不同于传统数据流压缩算法，新提出的算法在压缩后能有效保持数据流数据本身的结构信息，将数据按压缩粒度从密集到稀疏存储在一个树形结构上，并根据压缩需求调整树形结构上数据的压缩粒度。同时，提出基于泛化指数幂分布模型对簇进行参数估计，使得压缩算法可以对压缩后的数据进行有效重构。实验表明，所提出的压缩算法不仅具有较高的压缩比，且失真率和重构误差小。

目录

第一个书签之前

摘要

Abstract

第一章 绪论

1.1 研究背景与意义

1.2.1 数据流压缩

1.2.2 概念漂移

1.2.3 小结

1.3 研究主要内容及创新

1.3.1 研究主要内容

1.3.2 创新与贡献

1.4 论文的结构安排

1.5 本章小结

第二章 关键理论基础

2.1 数据流压缩

2.1.1 采样

2.1.2 草图

2.1.3 窗口模型

2.1.4 数据流聚类

2.2 概念漂移

2.3 本章小结

第三章 概念漂移下基于同步的聚类算法

3.1 相关工作

3.2 基于同步的数据流聚类

3.2.1 同步微簇

3.2.2 在线的微簇维护