基于遗忘特性的数据流概要结构及其应用研究

随着计算机网络和各类电子设备应用的越来越广泛,越来越多的数据以连续的流的形式出现,如网络路由信息,传感器网络采集的实时信号,证券交易、信用卡交易、商场购物交易等的实时记录,因特网网站点击流,电信网络的电话呼叫业务记录,聊天室、短信等的实时文本流等,均产生连续不断的各类数据。这些数据被称为流数据或数据流。因为数据流和传统数据库等系统中处理的数据的巨大差别,迫使研究人员对数据流模型和处理方法进行深入研究。 数据流处理的关键是应用单趟数据扫描算法,建立流数据的概要结构,以便随时能根据该结构提供数据流的近似处理结果。数据遗忘是数据流的一种重要特性,在数据流概要结构构造中应充分考虑这种遗忘特性。本文工作利用这种遗忘特性,提出了一种基于数据流遗忘特性的概要结构的框架,称为分层遗忘概要（Hierarchical AmnesicSynopses,简称HAS）。应用HAS结构,可将原来不考虑遗忘特性的概要结构构造方法改造为结合了数据流遗忘特性的方法。本文工作将HAS结构应用于直方图、抽样、小波、sketch、随机投影等主要的数据流概要结构中,并给出了几个典型应用。 本文主要贡献包括: （1）提出了一种数据流概要结构的通用框架,HAS结构。该框架嵌入了数据流的遗忘特性,并且具有遗忘速度和重构误差控制的能力。利用该框架,可将现有的多种典型数据流概要结构改造成具有数据流遗忘特性处理能力。 （2）实现了基于小波数据压缩的HAS结构（W-HAS）,提出了小波概要的归并方法,并讨论了在基于误差平方和（sse）和基于最大绝对误差（maxabs）两种误差度量标准下的W-HAS,以及如何进行W-HAS中的重构误差控制的方法。 （3）讨论了基于加权随机抽样的HAS结构（WS-HAS）,分别对有放回和无放回加权随机抽样设计了WS-HAS概要结构的维护算法。 （4）提出了结合HAS结构和直方图数据压缩方法的H-HAS结构,讨论了等宽直方图下的H-HAS结构的实现,用动态规划方法实现了最优直方图下的H-HAS结构。 （5）基于数据流的W-HAS结构,讨论了数据流之间的近似距离和聚类中心的计算,并进而提出了适合并行多数据流的K-means聚类方法:W-HAS-clustering。同时,利用数据流的遗忘特性,应用随机投影,构造了基于随机投影的数据流分层概要结构RP-HAS,并设计了规范化后数据流的RP-HAS结构维护的方法。提出了基于RP-HAS结构的适合并行多数据流的聚类方法RP-HAS-clustering。 （6）讨论了高维数据流中HAS结构的实现,并将其应用到数据流的分类和聚类中。 （7）提出了一种基于sketch的数据流概要结构EFM sketch,并用EFM sketch来估算集合的相似度。在HAS结构的基础上,应用EFM sketch分析数据流上数据的相似度和演化。