数据异常剔除方法.docx

发布时间：2022-05-31 发布人：admin 分类：说明书资料大小：0.35M 资料格式：docx 举报版权申诉

mning_master0-10867638-4744300845373100713.docx.pdf-第1页.png

第1页 / 共12页

mning_master0-10867638-4744300845373100713.docx.pdf-第2页.png

第2页 / 共12页

mning_master0-10867638-4744300845373100713.docx.pdf-第3页.png

第3页 / 共12页

mning_master0-10867638-4744300845373100713.docx.pdf-第4页.png

第4页 / 共12页

mning_master0-10867638-4744300845373100713.docx.pdf-第5页.png

第5页 / 共12页

mning_master0-10867638-4744300845373100713.docx.pdf-第6页.png

第6页 / 共12页

mning_master0-10867638-4744300845373100713.docx.pdf-第7页.png

第7页 / 共12页

mning_master0-10867638-4744300845373100713.docx.pdf-第8页.png

第8页 / 共12页

1.1.1 基于统计的异常点检测算法

1.1.2 基于距离的异常点检测算法

1.1.3 基于密度的异常点检测算法

1.1.4 基于深度的异常点检测算法

1.1.5 基于偏移的异常点检测算法

1.1.6 高维数据的异常点检测算法

1.2.1 时间序列相关背景

1.2.2 基于离散傅立叶变换的时间序列相似性查找

1.1.1 完全匹配查找算法

拉依达方法、肖维勒方法、一阶差分法 1、拉依达准则法（3δ）：简单，无需查表。测量次数较多或要求不高时用。是最常用的异常值判定与剔除准则。但当测量次数《=10 次时，该准则失效。如果实验数据值的总体 x 是服从正态分布的，则式中，μ与σ分别表示正态总体的数学期望和标准差。此时，在实验数据值中出现大于μ＋3σ或小于μ—3σ数据值的概率是很小的。因此，根据上式对于大于μ ＋3σ或小于μ—3σ的实验数据值作为异常值，予以剔除。 2. 肖维勒方法（等置信概率）（w 倍的δ，变化的 w,根据样本数量）肖维勒准则法（Chauvenet）：经典方法，改善了拉依达准则，过去应用较多，但它没有固定的概率意义，特别是当测量数据值 n 无穷大时失效

1、用移动平均滤波，会比较好的去除掉类似点(高光谱不太可取？？)

1. 111 基于统计的异常点检测算法 2. 112 基于距离的异常点检测算法 3. 113 基于密度的异常点检测算法 4. 114 基于深度的异常点检测算法 5. 115 基于偏移的异常点检测算法 6. 116 高维数据的异常点检测算法 7. 121 时间序列相关背景 8. 122 基于离散傅立叶变换的时间序列相似性查找 9. 10. 111 完全匹配查找算法 1.1 常见异常点检测算法在数据库中包含着少数的数据对象，它们与数据的一般行为或特征不一致，这些数据对象叫做异常点 (Outlier) ，也叫做孤立点。异常点的检测和分析是一种十分重要的数据挖掘类型，被称之为异常点挖掘 [28 ] 。对于异常数据的挖掘主要是使用偏差检测，在数学意义上，偏差是指分类中的反常实例、不满足规则的特例，或者观测结果与模型预测值不一致并随时间的变化的值等等。偏差检测的基本目标是寻找观测结果与参照值之间有意义的差别，主要的偏差技术有聚类、序列异常、最近邻居法、多维数据分析等。除了识别异常数据外，异常数据挖掘还致力于寻找异常数据间隐含模型，用于智能化的分析预测。对于异常数据分析方法的研究是论文的重要内容之一，通过研究异常数据，找到适合出口企业产品质量深入分析和有效监管的方法和策略。 1.1.1 基于统计的异常点检测算法从 20 世纪 80 年代起，异常检测问题就在统计学领域里得到广泛研究，通常用户用某个统计分布对数据点进行建模，再以假定的模型，根据点的分布来确定是否异常。许许多多针对不同分布的异常测试 (Discordancy Test) 方法发展起来，它们分别适用于不同的情形： ①数据分布状况；②数据分布参数是否已知；③异常数据数量；④异常数据类型 ( 高于或低于一般抽样值 ) 。这方面比较有代表性的有 1967 年 Mikey ， Dunn & Clark 提出的基于“均数漂移”模型的单点诊断量， 1970 年 Gentleman &Wilk 提出的群组诊断量， 1972 年 Tietjen &Moore 提出的单样本 k 个离群点的统计量 E k ， 1985 年 Marasinghe 提出的改进的 E k 统计量 F k ， 1989 年 Rosner 提出的单样本多个离群检测算法 ESD(Generalized Extreme Studentized Deviate) 方法， 1991 年 Paul & Fung 改进了 ESD 方法参数 k 选择的主观性，提出了回归分析的 GESR (Generalized Extreme Studentized DeviateResi2dual) 方法。近年来，多样本的离群检测方法也得到了一定的发展，总的思路是先尽量得到一个不含离群点的“干净集”，然后在此基础上对剩余的其他数据点进行逐步离群检测 [29 ] 。目前利用统计学研究异常点数据有了一些新的方法，如通过分析统计数据的散度情况，即数据变异指标，来对数据的总体特征有更进一步的了解，对数据的分布情况有所了解，进而通过数据变异指标来发现数据中的异常点数据。常用的数据变异指标有极差、四分位数间距、均差、标准差、变异系数等等，变异指标的值大表示变异大、散布广；值小表示离差小，较密集。

基于统计的方法检测出来的离群点很可能被不同的分布模型检测出来，可以说产生这些离群点的机制可能不唯一，解释离群点的意义时经常发生多义性，这是基于统计方法的一个缺陷。其次，基于统计的方法在很大程度上依赖于待挖掘的数据集是否满足某种概率分布模型，模型的参数、离群点的数目等对基于统计的方法都有非常重要的意义，而确定这些参数通常都比较困难。为克服这一问题，一些人提出对数据集进行分布拟合，但分布拟合存在两个问题： ①给出的分布可能不适合任一标准分布。②即使存在一个标准分布，分布拟合的过程耗时太孤立点是数据集中到第 k 个最近邻居的距离最大的 n 个对象 [37 ] 。孤立点是数据集中与其 k 个最近邻居的平均距离最大的 n 个对象 [38 ] 。长。此外，基于统计的离群检测算法大多只适合于挖掘单变量的数值型数据，目前几乎没有多元的不一致检验，对于大多数的应用来说，例如图像和地理数据，数据集的维数却可能是高维的。实际生活中，以上缺陷都大大限制了基于统计的方法的应用，使得它主要局限于科研计算，算法的可移植性较差。 1.1.2 基于距离的异常点检测算法用什么标准判定一个数据对象是孤立点呢？即便是对给定的距离量度函数，对孤立点也有不同的定义，以下是使用较多的几个： l 基于距离的离群点最早是由 Knorr 和 Ng 提出的，他们把记录看作高维空间中的点，离群点被定义为数据集中与大多数点之间的距离都大于某个阈值的点，通常被描述为 DB ( pct ， d min ) ，数据集 T 中一个记录 O 称为离群点，当且仅当数据集 T 中至少有 pct 部分的数据与 O 的距离大于 d min 。换一种角度考虑，记 M =N × (1 - pct) ，离群检测即判断与点 O 距离小于 d min 的点是否多于 M 。若是，则 O 不是离群点，否则 O 是离群点 [4 ][36 ] 。 l l 基于距离的离群点定义包含并拓展了基于统计的思想，即使数据集不满足任何特定分布模型，它仍能有效地发现离群点，特别是当空间维数比较高时，算法的效率比基于密度的方法要高得多 [39 ] 。算法具体实现时，首先给出记录间距离的度量，常用的是绝对距离 ( 曼哈顿距离 ) 、欧氏距离和马氏距离[40 ] 。在给出了距离的度量并对数据进行一定的预处理以后，任意给定参数 pct 和 d min 就可以根据离群的定义来检测离群。 Rastogi 和 Ramaswamy 在上面基于距离的离群点定义的基础上，提出改进的基于距离的 k 最近邻 (k － NN ) 离群检测算法 [37 ][41 ][42 ] 。基于距离的离群检测方法中，算法需要事先确定参数 pct 和 d min ，对于不同的数据集这往往是一件比较困难的事情，特别是 d min ，不同聚类密度的数据集 d min 会有很大的差异，而这一般没有规律可循，因此，对于给定的不同 d min ，异常检测结果通常具有很大的不稳定性 [43 ] 。另一方面，基于距离的方法理论上能处理任意维任意类型的数据，当属性数据为区间标度等非数值属性时，记录之间的距离不能直接确定，通常需要把属性转换为数值型 [37 ][44 ] ，再按定义计算记录之间的距离。当空间的维数大于三维时，由于空间的稀疏性，距离不再具有常规意义，因此很难为异常给出合理的解释。针对这个问题，一些人通过将高维空间映射转换到子空间的办法来解决数据稀疏的问题，此方法在聚类算法中用得比较多 [45 ][46 ] ，Agarwal R. [45 ] 等人曾试着用这种投影变换的方法来挖掘离群。总的来说，基于距离的离群检测方法具有比较直观的意义，算法比较容易理解，因此在实际中应用得比较多。目前比较成熟的基于距离的异常点检测的算法有： 1 ．基于索引的算法 (Index-based) ：给定一个数据集合，基于索引的算法采用多维索引结构 R- 树， k-d 树等，来查找每个对象在半径 d 范围内的邻居。假设 M 为异常点数

据的 d 领域内的最大对象数目。如果对象 O 的 M+l 个邻居被发现，则对象 O 就不是异常点。这个算法在最坏情况下的复杂度为 O(k*n 2 ) ，k 为维数，n 为数据集合中对象的数目。当 k 增加时，基于索引的算法具有良好的扩展性 [44 ] 。 2 ．嵌套循环算法 (Nested-loop) ：嵌套一循环算法和基于索引的算法有相同的计算复杂度，但是它避免了索引结构的构建，试图最小化 I/O 的次数。它把内存的缓冲空间分为两半，把数据集合分为若干个逻辑块。通过精心选择逻辑块装入每个缓冲区域的顺序， I/O 效率能够改善 [44 ] 。 3 ．基于单元的算法 (cell-based)[47 ] ：在该方法中，数据空间被划为边长等于 d /(2*k 1/2 ) 的单元。每个单元有两个层围绕着它。第一层的厚度是一个单元，而第二层的厚度是 [2*k 1/2 -1] 。该算法逐个单元地对异常点计数，而不是逐个对象地进行计数。对于一个给定的单元，它累计三个计数：单元中对象的数目 (cell_count) 、单元和第一层中对象的数目 (cell_+_1_layer_count) 单元和两个层次中的对象的数目 (cell_+_2_layers_count) 。该算法将对数据集的每一个元素进行异常点数据的检测改为对每一个单元进行异常点数据的检测，它提高了算法的效率。它的算法复杂度是 O(c k +n ) ，这里的 c 是依赖于单元数目的常数， k 是维数。它是这样进行异常检测的：若 cell_+_1_layer_count>M ，单元中的所有对象都不是异常；若 cell_+_2_layers_count<=M ，单元中的所有对象都是异常；否则，单元中的某一些数据可能是异常。为了检测这些异常点，需要逐个对象加入处理。基于距离的异常点检测方法要求用户设置参数 P 和 d ，而寻找这些参数的合适设置可能涉及多次试探和错误。基于距离的方法与基于统计的方法相比，不需要用户拥有任何领域知识，与序列异常相比，在概念上更加直观。更重要的是，距离异常接近 Hawkins 的异常本质定义。然而，三种类型的基于距离的离群检测算法中，基于索引的算法和循环——嵌套算法需要 O (k *n 2 ) 的时间开销，因此在大数据集中还有待于改进；而基于单元的算法，虽然与 n 具有线性的时间关系，但是它与 k 成指数关系，这限制了它在高维空间中的应用，此外，基于单元的算法还需要事先确定参数 pct ， d min 以及单元的大小，这使得算法的可行性比较差；高维空间中，基于索引的方法由于需要事先建立数据集的索引，建立与维护索引也要花大量的时间。因此三种方法对于高维空间中的大数据集，算法的效率都不高 [44 ] 。 1.1.3 基于密度的异常点检测算法基于密度的离群检测算法一般都建立在距离的基础上，某种意义上可以说基于密度的方法是基于距离的方法中的一种，但基于密度的异常观点比基于距离的异常观点更贴近 Hawkins 的异常定义，因此能够检测出基于距离的异常算法所不能识别的一类异常数据 ——局部异常。基于密度的方法主要思想是将记录之间的距离和某一给定范围内记录数这两个参数结合起来，从而得到“密度”的概念，然后根据密度判定记录是否为离群点。 Breunig 等人提出的基于局部离群因子的异常检测算法 LOF 是基于密度方法的一个典型例子。它首先产生所有点的 MinPts 邻域及 MinPts 距离，并计算到其中每个点的距离；对低维数据，利用网格进行 k －NN 查询，计算时间为 O (n ) ；对中维或中高维数据，采用如 X2 树等索引结构，使得进行 k2NN 查询的时间为 O (logn ) ，整个计算时间 ) 。然后为 O (nlogn ) ；对特高维数据，索引结构不再有效，时间复杂度提高到 O ( n 2 计算每个点的局部异常因子，最后根据局部异常因子来挖掘离群。 LOF 算法中，离群点被定义为相对于全局的局部离群点，这与传统离群的定义不同，离群不再是一个二值属性 ( 要么是离群点，要么是正常点 ) ，它摈弃了以前所有的异常定义中非此即彼的绝对异常观念，更加符合现实生活中的应用。

LOF 算法中充分体现了“局部”的概念，每个点都给出了一个离群程度，离群程度最强的那几个点被标记为离群点。此外， Aggarwal 也提出了一个结合子空间投影变换的基于密度的高维离群检测算法。 1.1.4 基于深度的异常点检测算法基于深度的离群点检测算法的主要思想是先把每个记录标记为 k 维空间里的一个点，然后根据深度的定义 ( 常用 Peeling Depth Contours 定义 ) 给每个点赋予一个深度值；再根据深度值按层组织数据集，深度值较小的记录是离群点的可能性比深度值较大的记录大得多，因此算法只需要在深度值较小的层上进行离群检测，不需要在深度值大的记录层进行离群检测。基于深度的方法比较有代表性的有 Struyf 和 Rousseeuw 提出的 DEEPLOC 算法。虽然，理论上基于深度的识别算法可以处理高维数据，然而实际计算时，k 维数据的多层操作中，若数据集记录数为 N ，则操作的时间复杂度为Ω (N [k/2 ] ) 。因此，当维数 k ≤ 3 时处理大数据集时还有可能是高效的，而当 k ≥ 4 时，算法的效率就非常低。也就是说，已有的基于深度的离群点检测算法无法挖掘高维数据，只有当 k ≤ 3 时计算效率才是可接受的。 1.1.5 基于偏移的异常点检测算法基于偏移的离群检测算法 (Deviation-based Outlier Detection) 通过对测试数据集主要特征的检验来发现离群点。目前，基于偏移的检测算法大多都停留在理论研究上，实际应用比较少。以下三种是比较有代表性的 : ① Arning 采用了系列化技术的方法来挖掘离群，由于算法对异常存在的假设太过理想化，因此并没有得到普遍的认同，对于现实复杂数据，其效果不太好，经常遗漏了不少的异常数据 ; ② Sarawagi 应用 OLAP 数据立方体引进了发现驱动的基于偏移的异常检测算法 ; ③ Jagadish 给出了一个高效的挖掘时间序列中异常的基于偏移的检测算法。虽然，基于偏移的离群检测算法理论上可以挖掘各种类型的数据，但是由于要事先知道数据的主要特征，而现实世界中的数据集一方面由于数据量比较大，另一方面由于属性比较多，因此这方面的特征往往不容易发现，当确定记录之间的相异度函数时，如果选择不合适，则得到的离群挖掘结果很可能不尽人意，所以本方法在实际问题中应用得比较少。基于偏移的异常点检测不采用统计检验或者基于距离的度量值来确定异常对象，它是模仿人类的思维方式，通过观察一个连续序列后，迅速地发现其中某些数据与其它数据明显的不同来确定异常点对象，即使不清楚数据的规则。基于偏移的异常点检测常用两种技术：序列异常技术和 OLAP 数据立方体技术。我们简单介绍序列异常的异常点检测技术。序列异常技术模仿了人类从一系列推测类似的对象中识别异常对象的方式。它利用隐含的数据冗余。给定 n 个对象的集合 S ，它建立一个子集合的序列， {S 1 ， S 2 ， … ， Sm} ，这里 2<= m< =n ，由此，求出子集间的偏离程度，即“相异度”。该算法从集合中选择一个子集合的序列来分析。对于每个子集合，它确定其与序列中前一个子集合的相异度差异。光滑因子最大的子集就是异常数据集。这里对几个相关概念进行解释： 1 ．异常集：它是偏离或异常点的集合，被定义为某类对象的最小子集，这些对象的去除会产生剩余集合的相异度的最大减少。 2 ．相异度函数：已知一个数据集，如果两个对象相似，相异函数返回值较小，反之，相异函数返回值较大；一个数据子集的计算依赖于前个子集的计算。

3 ．基数函数：数据集、数据子集中数据对象的个数。 4 ．光滑因子：从原始数据集中去除子集，相异度减小的两度，光滑因子最大的子集就是异常点数据集。基于偏差的异常点数据的检测方法的时间复杂度通常为 O(n ) ，n 为对象个数。基于偏差的异常点检测方法计算性能优异，但由于事先并不知道数据的特性，异常存在的假设太过理想化，因而相异函数的定义较为复杂，对现实复杂数据的效果不太理想。 1.1.6 高维数据的异常点检测算法以上几种异常检测算法一般都是在低维数据上进行的，对于高维数据的效果并不是很好。与低维空间不同，高维空间中的数据分布得比较稀疏，这使得高维空间中数据之间的距离尺度及区域密度不再具有直观的意义 [48 ] 。基于这个原因， Aggarwal 和 Yu 提出一个高维数据异常检测的方法。它把高维数据集映射到低维子空间，根据子空间映射数据的稀疏程度来确定异常数据是否存在。（4- ） 1 高维数据的异常点检测的主要思想是：首先它将数据空间的每一维分成小个等深度区间。 = 1/ 的数所谓等深度区间是指将数据映射到此一维空间上后，每一区间包含相等的 f 据点。然后在数据集的 k 维子空间中的每一维上各取一个等深度区间，组成一个 k 维立方体，则立方体中的数据映射点数为一个随机数毛。设 n(D) 为 k 维立方体 D 所包含点数， N 为总的点数。定义稀疏系数 s(D) 如（ 4- 1 所示： s(D) 为负数时，说明立方体 D 中数据点低于期望值， s(D) 越小，说明该立方体中数据越稀疏。数据空间的任一模式可以用 ml m2 … mi … 表示。 mi 指此数据在第 i 维子空间映射区间，可以取值 1 到，或者 *( 牢表示可以为任意映射值 ) 。异常检测问题可以转化成为寻找映射在 k(k 作为参数输入 ) 维子空间上的异常模式以及符合这些异常模式的数据。如 4 维空间中一个映射在 2 维子空间上的模式 ( = 10 ) *3*90 高维数据中寻找异常模式是非常困难的。一个简单办法是对所有数据维进行组合，来搜索可能异常模式，但是效率极其低下。 1.2 出口产品质量异常检测的思路和算法分析检疫检疫局监管出口企业生产批质量数据的过程是：首先检验检疫局下发给企业产品出口标准和参数，企业的质量控制人员可以参考此标准和参数组织生产活动，同时将出口产品的某一批次定位生产批，在产品的生产过程，将生产批的质量监控数据上报到检疫检疫局。此生产批将与后期在检验检验局出口报检产品建立对应关系，这样如果出口产品出现问题，检疫检疫执法机构可以通过此种模式的回溯机制定位到此产品生产过程的质量参数。目前企业上报的生产批数据主要是企业自身的质量控制人员手工录入的，数据录入过程中人为因素很大。出口电子监管系统中建立了一套复杂的基于规则标准的监管体系，检疫检疫局认可通过出口电子监管系统综合评定的企业上报的生产批数据，但是对于一些有意钻漏洞的企业，如果其一旦掌握了电子监管系统的评定规则，将对出口产品的质量安全带来新的危险。出口产品质

分享到：

赞收藏

资料库

数据异常剔除方法.docx

相关推荐

人工智能

热门标签

最新资料