《异常值处理.课件》由会员分享，可在线阅读，更多相关《异常值处理.课件（78页珍藏版）》请在金锄头文库上搜索。
1、异常值处理异常值处理1.数据的标准化概述数据的标准化概述l数据的标准化（normalization）是将数据按比例缩放，使之落入一个小的特定区间。在一些比较和评价的指标处理中经常会用到，去除数据的单位限制，将其转化为无量纲的纯数值，便于不同单位或量级的指标能够进行比较和加权。数据的标准化方法数据的标准化方法 总和标准化。分别求出各要素所对应的数据的总和，以各要素的数据除以该要素的数据的总和，即 这种标准化方法所得到的新数据满足 标准差标准化，即 由这种标准化方法所得到的新数据，各要素的平均值为0，标准差为1，即有 极大值标准化，即 经过这种标准化所得的新数据，各要素的极大值为1，其余各数值小于
2、1。 极差的标准化，即 经过这种标准化所得的新数据，各要素的极大值为1，极小值为0，其余的数值均在0与1之间。2. 缺失数据的处理缺失数据的处理2.1 数据缺失的机制：l 将数据集中不含缺失值的变量（属性）称为完全变量，数据集中含有缺失值的变量称为不完全变量，Little 和 Rubin定义了以下三种不同的数据缺失机制：l 1）完全随机缺失：数据的缺失与不完全变量以及完全变量都是无关的。l 2）随机缺失：数据的缺失仅仅依赖于完全变量。l 3）非随机、不可忽略缺失：不完全变量中数据的缺失依赖于不完全变量本身，这种缺失是不可忽略的。2.2 缺失数据预处理思想缺失数据预处理思想l1）直接丢弃含缺失数
3、据的记录l2）补缺l A. 用平均值来代替所有缺失数据l B. K -最近距离邻居法：先根据欧式距离或相关分析来确定距离具有缺失数据样本最近的K个样本，将这K个值加权平均来估计该样本的缺失数据。l C.用预测模型来预测每一个缺失数据：该方法最大限度地利用已知的相关数据，是比较流行的缺失数据处理技术。（一）个案剔除法（一）个案剔除法(Listwise Deletion)l最常见、最简单的处理缺失数据的方法，也是很多统计软件（如SPSS）默认的缺失值处理方法。l如果缺失值所占比例比较小，这一方法十分有效。至于具体多大的缺失比例算是“小”比例，专家们意见也存在较大的差距。有学者认为应在5%以下，也有
4、学者认为20%以下即可。l这种方法却有很大的局限性。它是以减少样本量来换取信息的完备，会造成资源的大量浪费，丢弃了大量隐藏在这些对象中的信息。当缺失数据所占比例较大，特别是当缺数据非随机分布时，这种方法可能导致数据发生偏离，从而得出错误的结论。（二）均值替换法（二）均值替换法(Mean Imputation)l缺失值是数值型的：平均值来填充该缺失的变量值l缺失值是非数值型的，众数来补齐该缺失的变量值。l均值替换法也是一种简便、快速的缺失数据处理方法。使用均值替换法插补缺失数据，对该变量的均值估计不会产生影响。但这种方法是建立在完全随机缺失（MCAR）的假设之上的，而且会造成变量的方差和标准差变
5、小。 （三）热卡填充法（三）热卡填充法（Hotdecking）l在数据库中找到一个与最相似的对象，然后用这个相似对象的值来进行填充。l不同的问题可能会选用不同的标准来对相似进行判定。l变量Y与变量X相似，把所有个案按Y的取值大小进行排序。那么变量X的缺失值就可以用排在缺失值前的那个个案的数据来代替了。l与均值替换法相比，利用热卡填充法插补数据后，其变量的标准差与插补前比较接近。但在回归方程中，使用热卡填充法容易使得回归方程的误差增大，参数估计变得不稳定，而且这种方法使用不便，比较耗时。 （四）回归替换法（四）回归替换法(Regression Imputation)l回归替换法首先需要选择若干个
6、预测缺失值的自变量，然后建立回归方程估计缺失值，即用缺失数据的条件期望值对缺失值进行替换。l该方法也有诸多弊端，第一，容易忽视随机误差，低估标准差和其他未知性质的测量值，而且这一问题会随着缺失信息的增多而变得更加严重。第二，研究者必须假设存在缺失值所在的变量与其他变量存在线性关系，很多时候这种关系是不存在的。 （五）多重替代法（五）多重替代法(Multiple Imputation)l由Rubin等人于1987年建立起来的作为简单估算的改进产物。l首先，用一系列可能的值来替换每一个缺失值，以反映被替换的缺失数据的不确定性。l然后，用标准的统计分析过程对多次替换后产生的若干个数据集进行分析。l最
7、后，把来自于各个数据集的统计结果进行综合，得到总体参数的估计值。异常数据处理异常数据处理l异常挖掘及其应用l异常数据挖掘方法简介基于统计的方法基于距离的方法基于密度的方法基于聚类的方法l未来研究展望什么是异常什么是异常(Outlier)？lHawkins的定义的定义：异常是在数据集中偏离大部分数据偏离大部分数据的数据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。lWeisberg的定义：异常是与数据集中其余部分不服从相同统计模型的数据。lSamuels的定义：异常是足够地不同于数据集中其余部分的数据。lPorkess的定义：异常是远离数据集中其余部分的数据异常数据
8、具有特殊的意义和很高异常数据具有特殊的意义和很高的实用价值的实用价值 l 现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中，异常数据通常作为噪音而忽略，许多数据挖掘算法试图降低或消除异常数据的影响。而在有些应用领域识别异常数据是许多工作的基础和前提，异常数据会带给我们新的视角。 l如在欺诈检测中，异常数据可能意味欺诈行为的发生，在入侵检测中异常数据可能意味入侵行为的发生。 异常检测的应用领域异常检测的应用领域l电信、保险、银行中的欺诈检测与风险分析 l发现电子商务中的犯罪行为l灾害气象预报l税务局分析不同团体交所得税的记录，发现异常模型和趋势 l海关、民航等安检部门推
9、断哪些人可能有嫌疑 l海关报关中的价格隐瞒l营销定制：分析花费较小和较高顾客的消费行为l医学研究中发现医疗方案或药品所产生的异常反应l计算机中的入侵检测l运动员的成绩分析l应用异常检测到文本编辑器，可有效减少文字输入的错误 l什么是异常挖掘？什么是异常挖掘？ (Outlier miningOutlier mining，Exception miningException mining)l异常挖掘可以描述为：给定N个数据对象和所期望的异常数据个数，发现明显不同、意外，或与其它数据不一致的前k个对象。 l异常挖掘问题由两个子问题构成： (1)如何度量异常； (2)如何有效发现异常。为什么会出现异常数
10、据？为什么会出现异常数据？l测量、输入错误或系统运行错误所致l数据内在特性所决定l客体的异常行为所致由于异常产生的机制是不确定的，异常挖掘算法检测出的“异常数据”是否真正对应实际的异常行为，不是由异常挖掘算法来说明、解释的，只能由领域专家来解释，异常挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。异常数据实例异常数据实例l一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的 ；l一个公司的高层管理人员的工资明显高于普通员工的工资可能成为异常数据但却是合理的数据(如平安保险公司2007年 5位
11、高管税后收入超过了1000万元)； l一部住宅电话的话费由每月200元以内增加到数千元可能就因为被盗打或其它特殊原因所致； l一张信用卡出现明显的高额消费也许是因为是盗用的卡。l异常数据与众不同但具异常数据与众不同但具有相对性：有相对性： 高与矮，疯子与常人。l类似术语：类似术语： Outlier mining，Exception mining:异常挖掘、离群挖掘、例外挖掘和稀有事件挖掘 。异常检测方法分类异常检测方法分类从使用的从使用的主要技术路线主要技术路线角度分类角度分类l基于统计的方法l基于距离的方法l基于密度的方法l基于聚类的方法l基于偏差的方法l基于深度的方法l基于小波变换的方法l
12、基于神经网络的方法从从类标号类标号(正常或异常正常或异常)可以利用的程可以利用的程度度分类l无监督的异常检测方法l在实际情况下，没有提供类标号l有监督的异常检测方法l要求存在异常类和正常类的训练集l半监督的异常检测方法l训练数据包含被标记的正常数据，但是没有关于异常对象的信息 从从面向对象的特殊性面向对象的特殊性角度分类角度分类l面向高维数据的方法l面向时间序列的方法l面向数据流的方法l面向空间数据的方法l面向Web 数据的方法异常检测中需要处理的几个问题(1)用于定义异常的属性个数用于定义异常的属性个数l一个对象只有单个属性l一个对象具有多个属性：l可能某个属性异常，某个属性正常如：对于男生
13、而言， 身高1.6m，体重55kg，这个很正常； 身高1.6m，体重75kg，这个有点异常； 身高1.8m，体重75kg，基本正常。若对于女生，则三组值可能都不太正常。 l所以，定义异常需要指明如何使用多个属性的值确定一个对象是否异常？(2)全局观点和局部观点全局观点和局部观点l一个对象可能相对于所有对象看上去异常，但它相对于它的局部近邻不是异常的l例如：身高1.85m对于一般人群是不常见的，但对于职业篮球运动员不算什么(3)点的异常程度点的异常程度l某些技术方法是以二元方式来报告对象是否异常的，即：异常或正常l但，这不能反映某些对象比其他对象更加极端异常的基本事实l所以：可以通过定义对象的异
14、常程度来给对象打分 ，如都为异常的情况下，也还有分高和分低的区别。异常点得分(outlier score)(4)评估评估l如果可以使用类标号来识别异常和正常数据:l可以利用分类性能度量来评估异常检测方案的有效性。l也可以使用如精度、召回率等度量方法来度量l如果不能使用类标号，则评估是困难的。(5)有效性有效性l各种异常检测方案的计算开销是显著不同的l例如：l基于分类的方案需要相当多的资源(训练数据和测试数据)来创建分类模型，但是这个模型一旦建立好了，使用时的开销通常很小l而基于邻近度的方法，其时间复杂度通常为O(n2)异常检测的挑战和前提l挑战：l数据中有多少异常点?l方法应该是无监督的，就像
15、在干草堆中寻找一根针l前提假设:l假定数据集中被认为正常的点数远远超过被认为异常的点数基于统计的异常检测基于统计的异常检测基于统计的异常检测基于统计的异常检测l这类方法大部分是从针对不同分布的异常检验方法发展起来的，通常用户使用分布来拟合数据集。l假定所给定的数据集存在一个分布或概率模型(例如，正态分布或泊松分布)，然后将与模型不一致(即分布不符合)的数据标识为异常数据。 基于统计的异常检测基于统计的异常检测l假定用一个参数模型来描述数据的分布 (如正态分布)l应用基于统计分布的异常点检测方法依赖于l数据分布l参数分布 (如均值或方差)l期望异常点的数目 (置信度区间)异常点的概率定义异常点的
16、概率定义l异常点的概率定义：l异常点是一个对象，关于数据的概率分布模型，它具有低概率l概率分布模型通过估计用户指定的分布的参数，由数据创建。l例：如果假定数据具有高斯分布，则基本分布的均值和标准差可以通过计算数据的均值和标准差来估计，然后可以估计每个对象在该分布下的概率。实例：检测一元正态分布中的异常点实例：检测一元正态分布中的异常点l下面利用统计学中最常使用的分布之一:高斯(正态)分布，来介绍一种简单的统计学异常点检测方法。l正态分布用记号：N (，)表示，表示均值，表示方差。来自N(0,1)分布的对象(值)出现在分布尾部的机会很小。例如，对象落在 3标准差的中心区域以外的概率仅有0.002
17、7。更一般地，如果x是属性值，则|x|=c的概率随c增加而迅速减小。设= p (|x| c)。表6-1显示当分布为N(0,1)时c的某些样本值和对应的值。注意：离群值超过4个标准差的值出现的可能性是万分之一。实例：检测一元正态分布中的异常点实例：检测一元正态分布中的异常点对某一长度对某一长度L测量测量10次，其数据如下：次，其数据如下：试用拉依达准则剔除坏值。试用拉依达准则剔除坏值。解：解：20.33用用拉拉依依达达准准则则剔除剔除定义定义l定义 设属性x 取自具有均值0 和标准差1 的高斯分布。如果属性值x 满足： P(|x|c)=，其中c 是一个选定的常量，则x以概率1-为异常点。 l为了
18、使用该定义，需要指定值。从不寻常的值(对象)预示来自不同的值的观点来说，表示我们错误地将来自给定分布的值分类为异常点的概率。从异常点是N(0,1)分布的稀有值的观点来说，表示稀有程度。基于统计方法异常点检测技术的优缺点基于统计方法异常点检测技术的优缺点l优点：l异常点检测的统计学方法具有坚实的基础，建立在标准的统计学技术(如分布参数的估计)之上。l当存在充分的数据和所用的检验类型的知识时，这些检验可能非常有效。l缺点：l大部分统计方法都是针对单个属性的，对于多元数据技术方法较少。l在许多情况下, 数据分布是未知的。l对于高维数据, 很难估计真实的分布。基于距离的异常检测基于距离的异常检测基于距
19、离的异常检测基于距离的异常检测l基于距离的异常检测方法，其基本思想如下：l一个对象是异常的，如果它远离大部分其它对象。l优点：确定数据集的有意义的邻近性度量比确定它的统计分布更容易，综合了基于分布的思想，克服了基于分布方法的主要缺陷 。基于距离的方法有两种不同的策略基于距离的方法有两种不同的策略 l第一种策略是采用给定邻域半径，依据点的邻域中包含的对象多少来判定异常；l如果一个点的邻域内包含的对象少于整个数据集的一定比例则标识它为异常，也就是将没有足够邻居的对象看成是基于距离的异常。l利用k最近邻距离的大小来判定异常 。l使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的异常程度由到
20、它的k-最近邻的距离给定 。l这种方法对k的取值比较敏感。如果k太小(例如1)，则少量的邻近异常点可能导致较低的异常程度。如果k太大，则点数少于k的簇中所有的对象可能都成了异常点。到到k-最近邻的距离的计算最近邻的距离的计算lk-最近邻的距离：l一个对象的异常点得分由到它的k-最近邻的距离给定。l异常点得分的最低值为0，最高值是距离函数的可能最大值-如无穷大基于距离的异常点检测基于距离的异常点检测 例例1请问该二维数据集中，当请问该二维数据集中，当k=5时，哪个点具有最高时，哪个点具有最高的异常点得分？的异常点得分？基于距离的异常点检测基于距离的异常点检测 例例2请问该二维数据集中，当请问该二
21、维数据集中，当k=5时，哪个点具有最高时，哪个点具有最高的异常点得分？的异常点得分？基于距离的异常检测的优缺点基于距离的异常检测的优缺点l优点：l基于距离的异常点检测方案简单 l缺点：l时间复杂度O(m2)，不适用于大数据集l不能处理不同密度区域的数据集，因为它使用全局阈值，不能考虑这种密度的变化不能处理不同密度区域的数据集不能处理不同密度区域的数据集CDAB当k=5时，哪个点具有最高的异常点得分,B的异常点得分和D的异常点得分哪个低？例：例：基于密度的异常检测基于密度的异常检测7/23/2024基于密度的异常检测 l当数据集含有多种分布或数据集由不同密度子集混合而成时，数据是否异常不仅仅取决
22、于它与周围数据的距离大小，而且与邻域内的密度状况有关。l密度的两种不同理解： 到第k个最近邻的距离大小； 到第k个最近邻邻域内的对象的个数；定义定义1 1 对于正整数k,对象p到它的第k个最近邻o的距离k-distance(p)定义为:(1) 至少有k个对象满足(2) 至多k-1个对象满足使用相对密度的异常点检测使用相对密度的异常点检测(LOF)l对每个点, 计算它的局部邻域密度l计算样本p的局部异常因子(LOF)，把它作为样本p的平均密度比率和近邻密度l异常点为具有最大LOF值的点 p2 p1 在基于距离的方法中, p2 不是异常，而在LOF 方法中p1 和p2 都被判定为异常。l定义3 (
23、1) 对象的局部邻域密度 l(2) 相对密度l其中， 是包含x的k-最近邻的集合， 是该集合的大小，y是一个最近邻。 簇内靠近核心点的对象的相对密度(LOF)接近于1，而处于簇的边缘或是簇的外面的对象的LOF相对较大。相对密度异常点检测算法相对密度异常点检测算法 l1：k是最近邻个数l2：for all 对象x dol3： 确定x的k-最近邻N(x,k)。l4： 使用x的最近邻(即N(x,k)中的对象)， 确定x的密度density(x,k)。l5：end forl6：for all 对象x dol7： 由定义(6-3)， 置outlier score(x,k)= relative densi
24、ty(x,k)。l8：end for l9:对outlier score(x,k)降序排列，确定异常点得分高的若干对象 基于密度的异常检测的不足基于密度的异常检测的不足l结果对参数k的选择很敏感，尚没有一种简单而有效的方法来确定合适的参数k；l时间复杂度为 ，难以用于大规模数据集；l需要有关异常因子阈值或数据集中异常数据个数的先验知识，在实际使用中有时由于先验知识的不足会造成一定的困难。基于聚类的异常检测基于聚类的异常检测7/23/2024基于聚类的异常检测方法 物以类聚物以类聚相似的对象聚合在一起。 基于聚类的方法有两个共同特点： (1)先采用特殊的聚类算法处理输入数据而得到聚类，再在聚类的
25、基础上来检测异常。 (2)只需要扫描数据集若干次，效率较高，适用于大规模数据集。7/23/2024基于聚类的异常检测方法基于聚类的异常检测方法l静态数据的异常检测第一阶段对数据进行聚类第二阶段计算对象或簇的异常因子，将异常因子大的对象或簇中对象判定为异常。l动态数据的异常检测第一步，利用静态数据的异常检测方法建立异常检测模型第二步，利用对象与已有模型间的相似程度来检测异常关键问题：距离的定义、异常程度的度量基于对象异常因子的方法基于对象异常因子的方法(1)l首先聚类所有对象 ，然后评估对象属于簇的程度。l如果一个对象不强属于任何簇，则称该对象为基于聚类的异常点。l对于基于原型的聚类，可以用对象
26、到它的簇中心的距离来度量对象属于簇的程度。 l对于基于目标函数的聚类技术，可以使用该目标函数来评估对象属于任意簇的程度。 l特殊地，如果删除一个对象导致该目标的显著改进，则将该对象分类为异常点。 基于对象异常因子的方法基于对象异常因子的方法(2)l在与具有目标函数的聚类方法一起使用时，这种基于聚类的异常点定义是基于模型的异常定义的特殊情况。 l对于基于密度的聚类，一个对象不强属于任何簇，如果它的密度太低；l对于基于连接度的聚类，一个对象不强属于任何簇，如果它不是强连接的。l基于原型的聚类，评估对象属于簇的程度的方法有多种 。一种方法是度量对象到簇原型的距离，并用到它作为该对象的异常程度得分。基
27、于对象异常因子的方法基于对象异常因子的方法(3)l定义定义4 给定簇C，C的摘要信息CSI(Cluster Summary Information)定义为： 其中n为簇C的大小，Cluster为簇C中对象标识的集合，Summary由分类属性中不同取值的频度信息和数值属性的质心两部分构成，即：l定义定义5 设 是数据集D的分解表示，即 ，对象p的异常因子OF(p)定义为p与所有簇间距离的加权平均值：l引理引理 如果随机变量 服从正态分布 ，则有：l两阶段异常挖掘方法TOD描述如下：第一步，对数据集D进行采用一趟聚类算法进行聚类，得到聚类结果第二步，计算数据集D中所有对象p的异常因子OF(p)，及
28、其平均值Ave_OF和标准差Dev_OF，满足条件： 的对象判定为异常。 通常取 基于簇的异常因子的方法基于簇的异常因子的方法l(1)在某种度量下，相似对象或相同类型的对象会聚集在一起，或者说正常数据与异常数据会聚集在不同的簇中；l(2)正常数据占绝大部分，且异常数据与正常数据表现出明显不同，或者说异常数据会偏离正常数据(也就是大部分数据)。 介绍簇的异常因子概念，利用簇的异常因子将簇区分为正常簇和异常簇。定义定义l给定簇C，C的摘要信息CSI (Cluster Summary Information)定义为： 其中kind为簇的类别(取值normal或outlier)， 为簇C的大小, Cl
29、uster为簇C中对象标识的集合，Summary由分类属性中不同取值的频度信息和数值型属性的质心两部分构成，即：定义定义l设 是数据集D的分解表示，即 ，簇Ci的异常因子(Outlier Factor) 定义为Ci与所有簇间距离加权幂平均值： l这里 是对应于簇 的权值，常见的有 ， 及x=1的特殊情况。定义定义6-8l令 ,n个非负数 关于w的加权x-幂平均(WPM)定为: 取 ,则 : 为算术平均。定理定理l若 ，则有 ，特别地 。l若xy,则 ，当且仅当 ， 。 l ， l根据幂平均的性质(定理)可知，x=1,时异常因子对应简单算术平均值，每个距离对异常因子的影响权值是相同的，而当x1，
30、特别x1时越大的距离对异常因子的影响越大，而一个簇偏离整个数据集的程度主要由离得近的类所决定，因此，应取 。实验结果表明，-8x-1时检测结果稳定性较好 。基于聚类的异常挖掘方法基于聚类的异常挖掘方法(CBOD)lCBOD方法由两个阶段构成：l第一阶段是利用一趟聚类算法对数据集进行聚类；l第二阶段是计算每个簇的异常因子，并按异常因子对簇进行排序，最终确定异常簇，也即确定异常对象。 CBOD算法描述如下：算法描述如下：l第一阶段，聚类：对数据集D进行聚类，得到聚类结果 ；l第二阶段，确定异常簇：计算每个簇 的异常因子 ，按 递减的顺序重新排列 ，求满足： 的最小 ，将簇 标识为outlier类(
31、即其中每个对象均看成异常)，而将 标识为normal类(即其中每个对象均看成正常)。CBOD算法的优点算法的优点lCBOD方法的时间复杂度与数据集大小成线性关系，与属性个数以及最终簇的个数成近似线性关系l具有好的扩展性，可用于大规模数据集中的异常挖掘。 CBOD算法参数的影响及选择算法参数的影响及选择参数r和数据输入顺序对检测结果的影响l聚类算法中参数r将影响聚类的结果和算法的时间效率。l数据输入顺序可能会影响聚类的结果，因而进一步影响异常挖掘的结果。 参数r的选择l采用抽样方法确定参数r的范围，在EX-0.25DX与EX+0.25DX之间。 参数对检测结果的影响l 实际上是异常数据所占比例的
32、近似值， 越小，检测率越低，同时误报率也越低，通常取在之间。 基于聚类的动态数据的异常检测基于聚类的动态数据的异常检测 l该方法分为两步：l第一步，利用静态数据的异常检测方法建立异常检测模型l第二步，利用对象与已有模型间的相似程度来检测异常基本思想如下：基本思想如下：l在对训练集聚类的基础上，按照簇的异常因子排序簇，并按一定比例将簇标识为”Normal”或”Outlier”，以标识的簇作为分类模型，按照对象与分类模型中最接近簇的距离判断它是否异常。 基于聚类的动态数据的异常检测(1)模型建立l第一步，聚类：对训练集 进行聚类，得到聚类结果 ；l第二步，给簇作标记：计算每个簇 的异常因子 ，按
33、递减的顺序重新排列 ，求满足： 的最小b，将簇 标识为异常簇，而将 标识为正常簇。l第三步，确定模型：以每个簇的摘要信息，聚类半径阈值r作为模型。(2) 模型评估模型评估l利用改进的最近邻分类方法INN(Improved Nearest Neighbor) 评估测试集中的每个对象。INN方法具体描述如下：l对于测试集 中对象p，计算p与每个簇的距离 若 ，则说明p是已知类型的行为，将簇 的标识作为p的标识，否则说明p是一种新的行为，将p标识为可疑对象候选异常对象 。(3) 模型更新模型更新l对于测试集 中对象p，按照前面聚类的方式，对新增对象进行增量式聚类更新l用建立模型同样的方法对所有簇重新标记其类别。异常挖掘的未来研究展望异常挖掘的未来研究展望l异常的解释和可视化 l面向高维数据集、时间序列、数据流和空间-时态数据集算法以及并行算法 l有效、准确定义各种不同类型数据对象之间的距离以提高检测算法的性能l有效的异常程度度量方法
