基于小波变换的流数据压缩算法研究

摘要

近几年来,随着网络通信技术的快速发展滋生了大量的流数据。许多实时的应用系统面对的都是在线的、持续的数据流。流数据海量无限的特性决定了我们无法用传统的存储方式将其完全保存,此外不经处理完全传输这些数据会占用大量有限的网络带宽,造成网络阻塞。因此,对流数据进行压缩处理显得尤为重要,具有现实意义。
　　 本文围绕数据流时间序列错位相似性、聚类压缩、多小波变换三个方面进行了深入研究。主要成果包括:
　　 (1)基于动态时间弯曲技术的数据流处理方法。将一段时间内采集到的流数据作为一个时间序列来进行处理。由于同一时间段内数据流变化的影响因素基本相同,导致一些数据流变化存在错位相似,具体表现为数据流形状大致相同,但在时间上有所超前或延迟。对于这种错位相似的数据流采用常用的欧几里得测度法是无法识别的,而采用动态时间弯曲技术却可以很好地判断数据流的这种相似性。本文在采用动态时间弯曲路径法得到两个时间序列对应点的基础上提出了用预测法估计两个时间序列的关系,从而确定时间序列最佳匹配点的算法。
　　 (2)基于多元时间序列相似性聚类压缩算法。首先采用动态时间弯曲距离分析数据流之间的相似关系,根据相似程度进行模糊聚类,接着选取各聚类中心作为特征流时间序列,最后保存每个聚类的数据流编号、特征数据流序列的小波系数和其它数据流序列与特征流序列的匹配点对和关系系数作为压缩数据。之后结合上一章的最佳匹配点算法给出了数据还原的算法。从仿真实验结果可以看出,该算法能有效压缩数据流,较采用欧式距离测度能更好地提高数据压缩的精度。
　　 (3)基于多小波变换的流数据压缩算法。将多属性数据流进行多小波变换后原数据流被分解为四个不同空间方向和不同分辨率的子数据矩阵,每个子矩阵又可以进一步进行多小波变换分解,流数据能量绝大部分汇聚于低频矩阵。根据这一特点对变换后的小波系数进行编码压缩从而达到压缩数据流的目的。从实验结果看,该算法压缩率高,并且能够很好地保存数据特征,还原后的数据能基本再现原数据流。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪论

1.1 课题背景

1.2 研究意义

1.3 国内外流数据研究现状

1.3.1 数据流模型

1.3.2 数据流管理系统

1.3.3 流数据挖掘技术的研究

1.3.4 流数据的压缩

1.4 论文主要研究内容

1.5 论文的组织结构

第2章 小波分析理论研究概述

2.1 引言

2.2 小波理论发展概述

2.3 小波变换基本概念及预备知识

2.3.1 小波及小波基函数

2.3.2 Haar小波

2.3.3 连续小波变换

2.3.4 离散小波变换

2.3.5 离散小波变换的Mallat算法

2.4 小波变换能量守恒

2.5 基于小波变换的数据压缩

2.5.1 基于小波阈值的数据压缩方法

2.5.2 基于小波系数编码的数据压缩方法

2.6 本章小结

第3章 基于动态时间弯曲技术的流数据处理方法

3.1 时间序列的概念

3.2 动态时间弯曲技术

3.3 动态时间弯曲路径及距离的计算

3.4 确定时间序列的最佳匹配点

3.4.1 动态时间弯曲路径的点对关系

3.4.2 时间序列预测法确定最佳匹配点

3.5 本章小结

第4章 多元时间序列相似性聚类压缩算法研究

4.1 多元时间序列

4.2 多元时间序列的相似性聚类

4.2.1 基于动态弯曲距离的时间序列相似性测度

4.2.2 模糊聚类

4.2.3 多元时间序列的模糊聚类分析

4.3 多元时间序列相似性聚类压缩算法

4.3.1 多元时间序列相似性聚类压缩算法

4.3.2 多元时间序列相似性压缩数据重构算法

4.4 仿真实验

4.4.1 实验环境

4.4.2 节点内数据压缩规整

4.4.3 簇头节点多元时间序列相似性聚类压缩

4.4.4 压缩比

4.4.5 误差分析——均方差(mse)

4.5 本章小结

第5章 基于多小波变换的流数据压缩算法研究

5.1 多小波发展概述

5.2 多小波理论

5.3 向量信号的多小波变换

5.4 流数据的多小波变换

5.4.1 多小波变换预处理

5.4.2 行方向的多小波变换

5.4.3 列方向的多小波变换

5.5 数据压缩编码

5.6 仿真实验分析

5.7 本章小结

结论

参考文献

致谢

附录A 攻读学位期间所发表的学术论文目录

附录B 攻读学位期间参加的科研项目