硕士论文网/国内首批论文服务机构
离群点检测未来研究技术方向综述
时间:2021-09-26 15:06 | 栏目:文献综述 | 浏览:次
硕士论文网第2021-09-26期，本期硕士论文写作指导老师为大家分享一篇文献综述文章《离群点检测未来研究技术方向综述》，供大家在写论文时进行参考。
以上论文内容是由硕士论文网为您提供的关于《离群点检测未来研究技术方向综述》的内容，如需查看更多硕士毕业论文范文，查找硕士论文、博士论文、研究生论文参考资料，欢迎访问硕士论文网文献综述栏目。
离群点被定义为一个显著不同于其他数据分布的数据对象，通过分析离群点数据分布特征，可以从海量数据中挖掘异常信息、提取兴趣模式等。因此离群点检测(outlier detection)成为数据挖掘领域的研究热点之一[1], 离群点检测目的是通过数据挖掘方法找出不同于大规模数据中的异常点，并发现潜在的、有意义的知识。目前其广泛应用于欺诈检测、医疗处理、公共安全、环境卫生、图像处理、异常行为模式检测、轨迹异常检测等领域。 传统离群点的检测方法众多, 一般，经典的离群点检测方法通常分为 4 大类: 基于统计学的、基于聚类的、基于分类的和基于邻近性的[1]。传统检测技术主要考虑检测过程中的时间性能和准确性能。然而，随着云计算、大数据技术的发展，传统通过单一节点计算方式挖掘异常节点信息已经无法满足日益增长的数据计算需求。因此，将传统方法运用于分布式环境下，以提高运行的时间效率是目前研究的重点但也是难点。此外，以深度学习技术为代表的人工智能技术为离群点检测提供了新的研究方向。目前，通过深度学习方法相结合构造混合模型的方法在近年不断应用于实际场景。因此，改进传统方法，并提出其扩展方法是近年来学者研究的关注点之一。 本文拟通过综述离群点检测方法包括传统离群点检测方法和目前前沿主流检测方法，为科研工作人员提供较为系统化离群点检测技术总结。目前，薛安荣等人[2]对传统的离群点检测方法作出了系统化的综述，但由于该工作所完成时间很早，因此缺乏最近十年的新方法新应用的介绍。最近，吴镜锋等人[3]在概述了传统方法后，以有监督和无监督学习的角度重点介绍了基于深度学习的离群点检测方法。与上述工作不同的是，对于已有相关工作的传统方法，本文侧重介绍近年新的变种算法及其性能，以及新的应用。本文同时也以方法论和新的应用领域两方面对基于深度学习的方法做了介绍。此外，本文也对分布式的离群点检测方法进行了阐述，目前没有对基于分布式的方法做过类似的总结工作。
1 离群点概述
离群点可以定义为如孤立点、异常点、新颖点、偏离点、例外点、噪声、异常物等即一个显著不同于其他数据分布的数据对象。产生离群点的原因以及挖掘离群点大体分为 a) 数据来源异常，这类离群点往往意味着异常情况的产生，例如某一时刻或时段不寻常的网络访问，往往意味着网络攻击的发生；不寻常的信用卡消费记录，往往意味着诈骗行为的发生，对于这类离群点，其产生的原因明确，挖掘此类离群点可以帮助人们及时处理异常情况。 b) 其外在表现同样为异常数据的产生，所不同的是其产生的原因具有很高的学术研究价值，属于主观上受欢迎的离群点。对于这样的离群点，其发现的数量越多，越具有学术价值。例如绝症的罕见自愈等，通过对其原因的研究，可以帮助人们加深对该疾病的认识。 c) 数据测量和收集误差, 主要是由于人为错误、测量设备故障或存在噪声。由于这类离群不提供有趣或有用的信息, 只会降低数据和其后数据分析的质量, 因此目标是消除这类离群。例如传感器故障造成的误报警等。 d) 产生离群点的原因不明。例如射电望远镜接收到的异常宇宙信号。因其产生机理与人类现有科技水平相去甚远，因此对于这样的离群点挖掘以记录为主，为之后持续的理论研究提供有用数据。
2 传统离群点检测方法
2 传统离群点检测方法
2.1 基于统计学的离群点检测方法
离群点检测最早出现在统计领域。基于统计学的离群点检测方法的一般思想是：以给定数据集的生成模型为前提条件，然后将该模型中低概率区域中的对象判定为离群点。而如何得到数据集的生成模型，一般分为两种方法：参数法和非参数法。 a) 参数法假定正常的数据对象被一个以 Θ 为参数的参数分布产生。该参数分布的概率密度函数 f(x, Θ)给出对象 x被该分布产生的概率。该值越小，预示着 x 越不可能由该分布产生。文献[4]针对不同的数据分布提出了 100 多种离群点检测方法。根据属性数量的不同，所使用的概率模型也不同，例如一元高斯分布，χ2(卡方分布)，混合高斯分布模型等。 b) 非参数法的原理为数据模型是由已知数据集学习而来，而非由经验提前假定(如专家经验、人工标记等)，典型的方法如直方图可视化方法。其在入侵检测[5]和缺陷检测[6]领域应用广泛。
2.2 基于聚类的离群点检测方法
在离群点检测一般通过无监督学习获取数据分布特征，因此常见的聚类算法做修改后都能应用于离群点检测，其方法主要通过考虑对象与簇之间的关系检测离群点。比较经典的算 法有 DBSCAN[7]、 CLARANS[8]、 CHAMELEON[9]、BIRCH[10] 、 STING[11] 、 WaveCluster[12] 、 CLIQUE[13] 和FindCBOLF[14]等。 基于聚类的离群点检测算法优点显著。首先，无监督学习的特点决定了数据无须类标签，因此对许多数据都有效。可以把簇看做是正常数据的分布结果，一旦聚类得到簇，则可以将对象与簇进行比较，依此判定离群点。 然而，基于聚类的离群点检测算法的也带来不足与劣势，首先其有效性对具体算法依赖较高，在执行具体任务时，根据数据集本身的特点，以及对离群点在该问题中的定义，都应审慎考虑，然后凭先验如专家经验选取合适的算法。其次，基于聚类的离群点检测算法一般通过经典聚类算法及其算法优化获得数据分布特征，因此，算法本身可能对离群点检测而言不是最优的检测策略，往往需要针对具体应用场景、数据本身特征进行算法调整，并设计有效的检测模型，这增加了应用的难度。此外，对于大型数据集，聚类方法其计算开销大也是难点。 因此，文献[14, 15]使用一种线性时间技术 fixed-width clustering 用于一些离群点检测方法，以克服计算开销大的问题。近年，Jobe 等人[16]提出了一种基于聚类的多元数据离群点检测方法，该方法结合了 Rousseuw 最小协方差行列式方法的重加权版本和一种基于多步聚类的算法，有效克服了当多 个 离 群 点 存 在 于 感 兴 趣 的 多 元 数 据 集 中 时 Squared Mahalanobis 距离统计量的检测能力显著降低的缺点。此外，文献[17]利用基于聚类的离群点检测算法对医疗数据库中的错误、丢失属性、无效的数据进行清洗，展现了比基于距离方法更好的性能。
2.3 基于分类的离群点检测方法
对于具有类标签的数据集，可以训练一个区分“正常”数据和离群点的分类器。然而对离群点检测问题，数据集往往高度有偏。虽然可以使用现有的分类算法检测离群点，但离群点训练样本数严重不足，很难构建一个准确率较高的分类模型。因此，通常的做法是构建单分类模型(one-class model)，即只使用正常数据训练模型，这样不属于正常类的数据点判定为离群点。在一些具体应用中，也可能将正常数据分为几个类，而不属于这几类的数据判定为离群点。 基于分类的方法在网络入侵检测中有广泛使用。文献[18]在网络入侵检测中使用了多分类方法。近年来，Hadd 等人[19]在物联网骨干网中推荐了一个两层的降维二分类模型，以检测用户到根(U2R)和远端到本地(R2L)两类攻击。 刘忠宝等人[20]提出基于模糊大间隔最小球分类模型的离群数据挖掘方法，该方法利用部分一般样本和离群样本建立最小球模型，并在此基础上引入模糊技术，通过降低噪声的权重，尽量减少噪声的影响。该方法在通过对光谱数据分析发现一些新的、特殊的天体方面取得了比传统分类模型如C-SVM、SVDD 和 KNN 更好的效果。
2.4 基于邻近性的离群点检测方法
基于邻近性的方法其核心思想是定义出数据之间的“邻近性”度量，并根据此度量的值判定离群点。其中比较典型的方法是基于距离的方法以及基于密度的方法，即前者以“距离”体现邻近性，后者以“密度”体现邻近性。 文献[21~23]引入了基于距离的离群点概念和挖掘方法，有效处理了五维以上的大数据集的离群点挖掘问题。由于该方法的实现需要使用嵌套循环，所以该方法的时间复杂度为O(n2) ，但实际的 CPU 运行时间与数据集的大小却表现为线性的，原因在于大多数数据点属于正常点，所以算法运行中内循环都提前结束。因此，造成数据集只有一小部分被考察。同时该算法时间复杂度是可以被接受。但当面对大数据集时，因为整个对象不能一次放入内存中，因此由页面置换引起的I/O 开 9500 大约为2(( ) )nbO ，其中 b 为一页所存对象数。 为了克服上述缺点，可以尝试根据对象的邻近性进行分组，进行逐组检测。基于以上思想，文献[23]提出基于网格的方法，文献[24]提出一种使用固定主存，通过 3 次数据库扫描，发现所有的基于距离的离群点。如果内存较大，则只需1 次或 2 次扫描。基于网格以及基于多次扫描的方法都体现了拆分数据集，分批次检测的思想。 基于距离的离群点从全局考虑数据集，挖掘的是全局离群点，因此当数据点邻近于稠密簇和稀疏簇时，则会出现漏检。如图 1 中的 O1和 O2。
3 基于分布式架构的离群点检测方法
随着数据尺度和维度的增加，离群点检测技术对服务器 CPU、IO 的吞吐都是严峻的考验，不论是处理速度、存储空间、容错性，还是在访问速度等方面，传统的技术架构和仅靠单台计算机基于串行的方式越来越不适应当前大数据处理的要求。2003 年 Google 推出了 MapReduce 并行计算编程模型，随后，越来越多的学者提出了基于分布式架构的离群点检测方法。 文献[32]利用 MapReduce 架构设计了一种在分类数据集上 快 速 检 测 离 群 点 的 方 法 MR-AVF(MapReduce-attribute value frequency)。假设数据一共有 m 个属性，则对象 O 的AVF 值通过下列方式计算：分别求出对象 O 每个属性在数据集中出现的次数并求和，最后除以属性个数 m 得到 AVF。显然，AVF 值越小，则说明对象 O 的属性在数据集中出现的平均次数越少。就分类数据本身的特点而言，这说明了 O 应该判定为离群点。首先通过编写 map 和 reduce 函数，实现计算AVF 第一阶段的任务：抽取属性值；再编写第二对 map 和reduce 函数，计算 AVF。最后实验证明了经与集中式环境比较，性能有很大提升。 He 等人[33]提出了一种基于 MapReduce 框架的结合 kd-tree 算法的离群点挖掘方法 PKDTree(parallel KD-tree)。实验证明了其在大尺寸，高维度数据集中的有效性。Otey 等人[34]提出了一种混合了类标号属性以及连续属性的数据的离群点定义，然后设计出一种分布式方法挖掘离群点。该方法的第一步是首先定义一个离群度，然后计算每个对象的局部离群度；第二步，使用基于全局考虑的机制重新计算那些局部离群度大于阈值的对象的离群度，判定出离群点。其方法的特点是扩展性好，也能应用在动态的流式数据中。Angiulli 等人[35]提出了一种分布式环境下的 Top-n 离群点检测方法。在第一次迭代中，每个 salve 节点随机选择 n 个元组并将其传递给主节点。在主节点中，计算这些元组的邻域，并选择 top-n 元组过滤出 salve 节点中的局部元组。在第二次迭代中，每个 salve 节点中的另外 n 个元组被随机选择并转移到主节点。主节点重新计算 top-n 元组并使用它们对局部元组进行剪枝。此过程将重复进行，直到所有局部元组都被剪枝完。该方法比较复杂，需要多次迭代。此外，大多数计算都发生在主节点上，这将成为大尺度数据计算时的瓶颈。文献[36]他们采用主从(master–slave)结构实现了 LOF[25]方法的并行计算。在从节点中，独立计算每个元组的局部邻域。然后将所有元组及其邻域转移到主节点，并在主节点上计算最终结果。因为最终所有的元组被转移到主节点，主节点上的工作负载相当繁重。因此，当数据尺度较大时，这种方法性能急剧下降。在[36] 基 础 上 ， Bai 等 人 [37] 提 出 了 一 种 采 用 一 个 协 调 器(coordinator)和多个计算节点(datanode)架构。协调器负责整个分配安排。每个计算节点存储多个数据子集，并计算数据子集中数据点的 LOF。经过比较，该架构中的协调器只负责调度，所有的实际计算都分配给数据节点。因此，如果数据规模很大，协调器就不会成为瓶颈，如图 2 所示。
本文从离群点算法挖掘效率作为落脚点，综述了各类经典方法及其变种算法，总结了各方法的优势和局限性，并介绍了离群点检测算法在分布式架构下的实现方法，最后对离群点检测领域近年来的研究重点特别是深度学习领域做了介绍。 未来离群点检测研究的重点主要集中于提高算法的时间效率和准确率上，典型的如处理流数据，数据即时到达，需要快速有效的模型以应对。若单一使用传统的方法，其检测的时间效率和准确率都普遍低于基于深度学习的方法。但是在分布式环境中，传统的方法仍能获得良好的时间效率，近年来将各种经典离群点检测算法布置在分布式环境中的研究也是热点之一。但由于各类离群点检测算法在原理和方法上有很大差异，目前，没有一种通用模型可以将各类经典算法迅速布置到分布式环境中。此外，采用深度学习与传统技术相结合的方法，也是当前研究的热点之一。因此对于传统方法的扩展以及改进算法的研究也是未来关注领域之一。基于深度学习的离群点检测方法是当前运用最广泛的方法，近年来的研究以及相关文献众多，但都集中于具体的应用领域，且根据所处理的数据类型不同，需要巧妙选择甚至订制模型，增加了通用性模型应用的难度，因此扩展和更新更多成熟的技术尤其是研究更具可用性的通用模型也是离群点检测关注的研究内容之一。感谢在本文工作中给与支持与建议的老师和同学。
参考文献：
[1] Han Jiawei, Kamber M, Pei Jian, 等. 数据挖掘: 概念与技术 [M]. 范明, 孟小峰, 译. 3 版. 北京: 机械工业出版社, 2012: 186-188. (Han Jiawei, Kamber M, Pei Jian, et al. Data mining: concepts and techniques [M]. Fan Ming, Meng Xiaofeng, 3nd ed. Beijing: China Machine Press, , 2012: 186-188.)
[2] 薛安荣, 姚林, 鞠时光, 等. 离群点挖掘方法综述 [J]. 计算机科学, 2008, 35 (11): 13-18. (Xue Anrong, Yao lin, Ju Shiguang, et al. Survey of Outlier Mining [J]. Computer Science, 2008, 35 (11): 13-18.)
[3] 吴镜锋, 金炜东, 唐鹏. 数据异常的监测技术综述 [J]. 计算机科学, 2017 (S2): 34-38. (Wu Jingfeng, Jin Weidong, Tang Peng. Survey on Monitoring Techniques for Data Abnormalities [J]. Computer Science, 2017 (S2): 34-38.)
[4] Barnett V, Lewis T, Abeles F. Outliers in Statistical Data [M]. Outliers in statistical data. 3nd ed. New York: John Wiley and Sons, 1994 [5] Eskin E. Anomaly Detection over Noisy Data using Learned Probability Distributions [C]// Proc of the Seventeenth International Conference on Machine Learning (ICML 2000) , Stanford, CA, USA: Stanford University, 2000.
[6] Fawcett T, Provost F. Adaptive Fraud Detection [J]. Data Mining & Knowledge Discovery, 1997, 1 (3): 291-316.
以上论文内容是由硕士论文网为您提供的关于《离群点检测未来研究技术方向综述》的内容，如需查看更多硕士毕业论文范文，查找硕士论文、博士论文、研究生论文参考资料，欢迎访问硕士论文网文献综述栏目。
上一篇：交通标志识别方法文献综述之我见