论文摘要
在实时监控、联机分析等应用领域,包括网络监控、股市分析、传感器网络、无线射频识别等等,需要对大量的动态数据进行连续的数据收集与分析处理。这些持续到达的数据具有多样性、快速性、实时性和时变性等特点,形成了难以预测的无界数据流。传统的数据库技术很难对其进行有效的管理,于是产生了数据流这一新型技术。近年来,有关数据流处理的研究得到了越来越多的关注。面对源源不断到达的数据流,挖掘隐藏的相关关系,寻找潜在的客观规律,是数据流分析与挖掘的重要目标,而相似性查询是达到这一目标的重要手段,同时也是聚类、分类、频繁模式挖掘和异常检测等数据挖掘技术的基础。本文采用相关性系数作为相似性查询的度量标准,提出了一系列在多个时间序列数据流中进行快速相关性分析的算法；同时,对于以事件为特征的数据流,建立了相应的相似性分析模型,提出了以事件为中心的相似性分析方法。主要工作包括以下几点：(1)提出一种基于布尔表示的数据流压缩方法。将原始序列转换为反映数值升降的布尔序列,这样用一个较长的二进制数就可以表示复杂的数据流序列的变化趋势,继而利用高效的布尔运算来快速地获取分析结果。(2)提出一种基于分层布尔表示的相关性检测算法HBR。首先将原始序列转换为反映其主体趋势的宏布尔序列,通过计算宏布尔序列的相关性,获取宏候选集；再将宏候选集中的序列转换为反映细节信息的微布尔序列,计算微布尔序列的相关性得到最终的候选集,从而大幅度降低运算开销。理论证明,对于任意两个时间序列,其皮尔逊相关性系数和转换后的布尔相关性系数具有一致性。(3)提出一种基于布尔表示的数据流周期性探测技术。利用计算布尔自相关系数来快速地获取原始序列的周期特征。理论分析证明,布尔自相关系数曲线与原始序列自相关系数曲线极值点的对应位置几乎相同,完全可以从布尔自相关系数曲线中获取原始序列的周期信息。(4)提出一种滑动窗口大小可自适应调整的相关性分析算法WACA。根据数据流序列的周期将多个数据流分成若干个可以有交集的组,将组中序列的平均周期作为该组滑动窗口的大小,然后再采用HBR算法进行同步相关性分析。当多个数据流的周期特性发生变化时,动态地重新分组以实现窗口大小的自适应调整。(5)提出一种基于布尔表示的滞后相关性分析技术。首先将流序列转换为布尔序列,然后在任意两个布尔序列之间进行滞后相关性探测。理论分析证明,有限长序列的滞后相关系数与布尔滞后相关系数具有特定的函数关系,其单调性完全一致,通过后者就可以确定原始序列的滞后相关性；同时,对于两个具有滞后相关性的序列,原始序列的滞后相关系数曲线和布尔滞后相关系数曲线具有相同的变化趋势,对应一致的滞后时间,因此可以通过布尔滞后相关方法快速获取滞后时间。(6)提出一种基于滞后相关的多数据流约减与重构方法。根据滞后相关性的探测结果,将多个数据流进行“对齐”,然后采用主成分分析对“对齐”的数据流进行降维处理。针对多个数据流中存在的重要数据,可以用较少的主成分对原始数据流序列进行重构。(7)针对以事件为特征的流数据,建立了事件流相似性分析模型,提出一种基于事件片段共享度的事件流相似性分析算法EOS。本文首先分析了事件流的特点及应用需求,从相似的事件流一定会分享很多相同的事件片段这一基本事实出发,考虑事件片段的出现频率、权重和位置等因素,提出了基于事件片段共享度的相似性分析算法,大大减小了候选集的大小,提高了事件流相似性的检测效率。总之,本文研究了有关数据流相关性检测和事件流相似性分析的几个基本问题,并且分别提出了新的解决方案。理论分析和实验报告表明,与现有数据流相应的分析方法相比,上述算法不仅满足精度要求,而且在时间和空间复杂度上具有明显的优势。
论文目录
相关论文文献
标签：数据流论文; 时间序列论文; 布尔表示论文; 自相关论文; 滞后相关论文; 自适应论文; 事件流论文; 共享度论文;