论文部分内容阅读
随着计算机与网络通信技术的飞速发展和应用领域的不断扩大,在传感器网络管理、金融风险分析、互联网流量管理和网络入侵检测等诸多领域里,处理的数据不再是有限存储的数据集合,而是短时间内大量到达,随时间动态变化的演化数据流。传统的数据库技术无法使用有限空间来快速处理这种海量、高速的数据流从而获取实时的有用信息。如何对这些场景中大量的数据流实时准确地进行异常检测以达到相关的应用需求已成为当前数据流挖掘的研究热点。由于演化数据流具有快速到达只能一次遍历的特征,数据流异常检测的最大挑战在于如何快速捕获数据流的实时变化并及时响应,从而得到近似的检测结果。本文综述了目前国内外关于数据流异常检测的研究成果;在分析现有研究成果的基础上,针对数据流的不同应用场景,分别提出了解决方法。针对中低维的集中式数据流,采用LOF算法和SR树索引结构结合的方法设计了SR IncLOF算法,特别针对高维的集中式数据流场景,提出了基于张量分解的异常检测算法;对于分布式数据流场景,构建了一个分布式的数据流异常检测模型,设计了结合核密度和微簇树数据结构的异常检测算法。通过不同类型数据集的实验验证了本文算法的异常检测性能相比其他同类算法都有较大的提高。本文的研究内容包括以下几个方面:针对基于密度的LOF算法所存在的不足进行改进,提出一种结合SR索引树的异常检测优化算法SR IncLOF算法,能够解决集中式的低中维数据流异常检测问题。该算法通过SR索引树来快速查找每个数据点的KNN集和KRNN集,采用局部异常因子LOF刻画异常程度,不但能够快速地增量更新,有效地解决了数据流的快速演化和一次遍历等问题,而且复杂度较低,支持实时要求非常高的数据流异常检测。针对高维的集中式数据流异常检测问题,分析了基于张量分解的高维索引技术,提出了基于张量分解的异常检测算法。该算法以张量的视角来模拟演化数据流,对此进行张量分解,基于张量分析来近似数据流的分布,并且通过自适应采样能得到关于数据流的最佳近似矩阵,易于实施。针对分布式数据流场景,提出基于核密度的分布式异常检测技术,提出了两种新的异常点定义,分别对应于基于距离和基于密度的异常分布。针对此问题提出两种有效的算法,第一个算法基于核密度估计技术来快速近似的获取数据流的分布,同时采取指数衰减技术解决数据流的时间演化;第二个算法结合微簇(micro-cluster)技术处理数据的划分问题。综上所述,本文针对演化数据流的不同应用场景,分别提出了不同的解决方案,通过理论分析和模拟数据集的实验表明,本文提出的算法具有较高的精度和反馈率,并且时间复杂度和空间复杂度较低,更加适用于演化数据流场景。