异常检测算法综述PPT学习教案.pptx

异常检测算法综述 异常检测算法是数据挖掘和机器学习中的一个重要问题，旨在识别数据集中与众不同的数据点，这些数据点可能是噪声、错误或真正的异常。异常检测算法可以应用于各种领域，如财务、医疗、网络安全等。 根据Hawkins（1980）的定义，异常是指在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。 聚类算法对异常的定义为：异常是聚类嵌于其中的背景噪声。而异常探测算法对异常的定义是：异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同。 异常探测方法可以分为五大类：基于统计的方法、基于距离的方法、基于偏差的方法、基于密度的方法和高维数据的异常探测。 基于统计的方法假设给定的数据集服从一个随机分布（如正态分布等），用不一致性测试（discordancy test）识别异常。但是，这种方法存在问题，因为用户并不知道这个数据分布，而现实数据也往往不符合任何一种理想状态的数学分布。 基于距离的方法是根据数据点之间的距离来判断哪些点是异常的。Knorr和Ng（VLDB’1998）提出了一个基于距离的异常探测方法，定义了DB(p, D)-outlier的概念，即数据集S中的一个对象O称为DB(p, D)-outlier，如果它满足下列性质：数据集S中至少p*100%的对象与O的距离大于距离D。 基于距离的算法可以分为三类：基于索引的算法、嵌套循环算法和基于单元的方法。基于索引的算法可以通过对最近邻查询或以O为中心的范围查询的回答来实现，而嵌套循环算法可以将内存缓冲区空间划分成相等的两部分，数据集分成几个大小和每部分缓冲区相等的逻辑块。基于单元的方法可以将数据空间被划分为边长为D/(2k1/2)的单元，每个单元有两个包围层。 基于距离的算法小结是：由于索引建立的开销很大，简单索引算法没有竞争性；当k<=4时，基于单元的算法在N越大时优越性越明显；当k>=5之后，嵌套循环算法开始显现出优势。 然而，基于距离的算法也存在缺陷，例如输入参数p与D很难确定，并且对于不同参数，结果有很大不稳定性。这就需要用户反复输入p与D进行测试，以确定一个满意解；不能给定异常的程度；算法的复杂度较高。 Rastogi和Ramaswamy（SIGMOD’2000）提出了一个新的基于距离异常定义Dnk异常，用Dk(p)表示点p和它的第k个最近邻的距离，给定d维空间中包含N个点的数据集，参数n和k（自然数），如果满足Dk(p’) > Dk(p)的点p’不超过n-1个，那么称p为Dnk。 异常检测算法是数据挖掘和机器学习中的一个重要问题，旨在识别数据集中与众不同的数据点。各种异常检测算法可以应用于不同的领域，但是每种算法都存在其优缺，需要根据实际情况选择合适的算法。