论文部分内容阅读
在实际生活中,各个领域都包含大量的时间序列数据,例如心电数据、脑电数据、工厂传感器数据、网络流量数据以及金融数据等。这些数据中的重要信息往往体现在少数数据中,且这部分少数数据具有与其他大部分数据不一致的特征,在数据挖掘领域内把这些不一致的、少数的数据称为异常数据。而在时间序列数据中,异常数据又可分为异常点和异常子序列。在本课题中,主要研究异常子序列的检测,异常子序列即为与其他大部分非自身匹配子序列不同的子序列。目前,异常子序列检测算法可以直接针对原始时间序列,也可针对原始时间序列的其他表示方式,如符号聚集近似、分段聚合近似、分段聚合模式等。由于时间序列常为高维数据,在原数据上的异常子序列检测往往需要较大的时间开销;虽然在降维数据上的算法可以提升检测效率,但会在一定程度上丢失了时间序列的趋势信息,导致异常子序列检测准确度下降。本课题提出了两种异常子序列检测算法,在不损失时间序列趋势信息的前提下,可以提升算法的检测效率和检测效果。算法如下:1)通过分析相似子序列的特征:相似子序列必然有大部分的数据点是相似的,首先提出了基于时间点集合的时间序列表示方式;把时间序列的数值空间划分为若干等概率的数值区间,统计位于每个数值区间的数据点对应的时间点集合;然后采用区间表(Interval Table,ITable)的数据结构来表示计算出的时间点集合。相似子序列必然有相似的区间表,通过合并数据集中的每个子序列对应的区间表可以得到一个扩展区间表(Extended Interval Table,EITable);基于EITable可以计算子序列是否符合其他大多数非自身匹配子序列的分布,进而判断子序列的异常情况。2)通过分析动态时间弯曲(Dynamic Time Warping,DTW)算法计算时间序列相似性流程以及DTW算法处理时间偏移问题的思路,提出了基于动态局部密度估计的异常检测算法。首先把子序列随机划分为不相交的动态时间片段;然后采用多个随机哈希函数快速估计每个数据点在对应的动态时间片段具有相似关系的数据点,具有相似关系的数据点数量即为数据点的局部密度;通过数据点的局部密度以判断其异常情况,进而判断子序列在时间序列中的异常情况。本文选取一系列数据集来验证提出的算法是否可以准确检测出异常子序列。通过设计多组对比实验,验证了本课题提出方法的有效性。