异常值处理学习教案.pptx

《异常值处理学习教案.pptx》由会员分享，可在线阅读，更多相关《异常值处理学习教案.pptx（78页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、会计学1异常异常(ychng)值处理值处理第一页，共78页。1.数据数据(shj)的标准的标准化概述化概述n n数据的标准化（数据的标准化（normalizationnormalization）是将数据按比例缩）是将数据按比例缩放，使之落入一个小的特定区间。在一些放，使之落入一个小的特定区间。在一些(yxi)(yxi)比较和评价的指标处理中经常会用到，去除数据的比较和评价的指标处理中经常会用到，去除数据的单位限制，将其转化为无量纲的纯数值，便于不同单位限制，将其转化为无量纲的纯数值，便于不同单位或量级的指标能够进行比较和加权。单位或量级的指标能够进行比较和加权。第1页/共78页第二页，共78页

2、。数据数据数据数据(shj)(shj)的标准化方法的标准化方法的标准化方法的标准化方法 总和总和总和总和(zngh)(zngh)(zngh)(zngh)标准化。分别求出各要素所对应的标准化。分别求出各要素所对应的标准化。分别求出各要素所对应的标准化。分别求出各要素所对应的数据的总和数据的总和数据的总和数据的总和(zngh)(zngh)(zngh)(zngh)，以各要素的数据除以该要，以各要素的数据除以该要，以各要素的数据除以该要，以各要素的数据除以该要素的数据的总和素的数据的总和素的数据的总和素的数据的总和(zngh)(zngh)(zngh)(zngh)，即，即，即，即 这种标准化方法所得到的

3、新数据满足这种标准化方法所得到的新数据满足这种标准化方法所得到的新数据满足这种标准化方法所得到的新数据满足第2页/共78页第三页，共78页。标准差标准化，即标准差标准化，即标准差标准化，即标准差标准化，即 由这种标准化方法由这种标准化方法由这种标准化方法由这种标准化方法(fngf)(fngf)所得到的新数据，各要素的平均值为所得到的新数据，各要素的平均值为所得到的新数据，各要素的平均值为所得到的新数据，各要素的平均值为0 0，标，标，标，标准差为准差为准差为准差为1 1，即有，即有，即有，即有第3页/共78页第四页，共78页。极大值标准化，即极大值标准化，即极大值标准化，即极大值标准化，即 经

4、经经经过过过过这这这这种种种种标标标标准准准准化化化化所所所所得得得得的的的的新新新新数数数数据据据据(shj)(shj)，各各各各要要要要素素素素的的的的极大值为极大值为极大值为极大值为1 1，其余各数值小于，其余各数值小于，其余各数值小于，其余各数值小于1 1。极差的标准化，即极差的标准化，即极差的标准化，即极差的标准化，即 经经经经过过过过这这这这种种种种标标标标准准准准化化化化所所所所得得得得的的的的新新新新数数数数据据据据(shj)(shj)，各各各各要要要要素素素素的的的的极极极极大大大大值值值值为为为为1 1，极极极极小小小小值值值值为为为为0 0，其其其其余余余余的的的的数数数

5、数值值值值均均均均在在在在0 0与与与与1 1之之之之间。间。间。间。第4页/共78页第五页，共78页。2.缺失数据缺失数据(shj)的处理的处理2.1 2.1 数据缺失的机制：数据缺失的机制：将数据集中不含缺失值的变量（属性）称为完全变量，数据集中含将数据集中不含缺失值的变量（属性）称为完全变量，数据集中含有缺失值的变量称为不完全变量，有缺失值的变量称为不完全变量，Little Little 和和 Rubin Rubin定义了以下三种定义了以下三种不同的数据缺失机制：不同的数据缺失机制：1 1）完全随机缺失：数据的缺失与不完全变量以及完全变量都是无）完全随机缺失：数据的缺失与不完全变量以及完

6、全变量都是无关的。关的。2 2）随机缺失：数据的缺失仅仅依赖于完全变量。）随机缺失：数据的缺失仅仅依赖于完全变量。3 3）非随机、不可）非随机、不可(bk)(bk)忽略缺失：不完全变量中数据的缺失依赖忽略缺失：不完全变量中数据的缺失依赖于不完全变量本身，这种缺失是不可于不完全变量本身，这种缺失是不可(bk)(bk)忽略的。忽略的。第5页/共78页第六页，共78页。2.2 缺失缺失(qu sh)数据预处理思想数据预处理思想n n1 1）直接丢弃含缺失数据）直接丢弃含缺失数据(shj)(shj)的记录的记录n n2 2）补缺）补缺n n A.A.用平均值来代替所有缺失数据用平均值来代替所有缺失数据

7、(shj)(shj)n n B.K-B.K-最近距离邻居法：先根据欧式距离或相关分析来确定距离具有缺失最近距离邻居法：先根据欧式距离或相关分析来确定距离具有缺失数据数据(shj)(shj)样本最近的样本最近的K K个样本，将这个样本，将这K K个值加权平均来估计该样本的缺个值加权平均来估计该样本的缺失数据失数据(shj)(shj)。n n C.C.用预测模型来预测每一个缺失数据用预测模型来预测每一个缺失数据(shj)(shj)：该方法最大限度地利用已：该方法最大限度地利用已知的相关数据知的相关数据(shj)(shj)，是比较流行的缺失数据，是比较流行的缺失数据(shj)(shj)处理技术。处理

8、技术。第6页/共78页第七页，共78页。（一）个案（一）个案（一）个案（一）个案(n)n)剔除法剔除法剔除法剔除法(Listwise Deletion)(Listwise Deletion)n n最常见、最简单的处理缺失数据的方法，也是很多统计软件（如最常见、最简单的处理缺失数据的方法，也是很多统计软件（如SPSSSPSS）默）默认的缺失值处理方法。认的缺失值处理方法。n n如果缺失值所占比例比较小，这一方法十分有效。至于具体多大的缺失比如果缺失值所占比例比较小，这一方法十分有效。至于具体多大的缺失比例算是例算是“小小”比例，专家们意见也存在较大的差距。有学者认为应在比例，专家们意见也存在较大

9、的差距。有学者认为应在5%5%以以下，也有学者认为下，也有学者认为20%20%以下即可。以下即可。n n这种方法却有很大的局限性。它是以减少样本量来换取信息的完备，会造这种方法却有很大的局限性。它是以减少样本量来换取信息的完备，会造成资源的大量浪费，丢弃了大量隐藏在这些对象中的信息。当缺失数据所成资源的大量浪费，丢弃了大量隐藏在这些对象中的信息。当缺失数据所占比例较大，特别是当缺数据非随机分布时，这种方法可能占比例较大，特别是当缺数据非随机分布时，这种方法可能(knng)(knng)导致导致数据发生偏离，从而得出错误的结论。数据发生偏离，从而得出错误的结论。第7页/共78页第八页，共78页。（

10、二）均值（二）均值（二）均值（二）均值(jn zh)(jn zh)替换法替换法替换法替换法(Mean Imputation)(Mean Imputation)n n缺失值是数值型的：平均值来填充该缺失的变量值n n缺失值是非数值型的，众数来补齐该缺失的变量值。n n均值替换法也是一种简便、快速的缺失数据处理方法。使用均值替换法插补缺失数据，对该变量的均值估计不会产生影响(yngxing)。但这种方法是建立在完全随机缺失（MCAR）的假设之上的，而且会造成变量的方差和标准差变小。第8页/共78页第九页，共78页。（三）热卡填充（三）热卡填充（三）热卡填充（三）热卡填充(tinchng)(tinc

11、hng)法（法（法（法（HotdeckingHotdecking）n n在数据库中找到一个与最相似在数据库中找到一个与最相似(xin(xin s)s)的对象，然后用这个相似的对象，然后用这个相似(xin(xin s)s)对象的值对象的值来进行填充。来进行填充。n n不同的问题可能会选用不同的标准来对相似不同的问题可能会选用不同的标准来对相似(xin(xin s)s)进行判定。进行判定。n n变量变量Y Y与变量与变量X X相似相似(xin(xin s)s)，把所有个案按，把所有个案按Y Y的取值大小进行排序。那么变量的取值大小进行排序。那么变量X X的的缺失值就可以用排在缺失值前的那个个案的数

12、据来代替了。缺失值就可以用排在缺失值前的那个个案的数据来代替了。n n与均值替换法相比，利用热卡填充法插补数据后，其变量的标准差与插补前比较接与均值替换法相比，利用热卡填充法插补数据后，其变量的标准差与插补前比较接近。但在回归方程中，使用热卡填充法容易使得回归方程的误差增大，参数估计变近。但在回归方程中，使用热卡填充法容易使得回归方程的误差增大，参数估计变得不稳定，而且这种方法使用不便，比较耗时。得不稳定，而且这种方法使用不便，比较耗时。第9页/共78页第十页，共78页。（四）回归（四）回归（四）回归（四）回归(hugu)(hugu)替换法替换法替换法替换法(Regression Imputa

13、tion)(Regression Imputation)n n回归替换法首先需要选择若干个预测缺失值的自变量，然后建立回归方程估计缺失值，即用缺失数据的条件期望值对缺失值进行替换。n n该方法也有诸多(zhdu)弊端，第一，容易忽视随机误差，低估标准差和其他未知性质的测量值，而且这一问题会随着缺失信息的增多而变得更加严重。第二，研究者必须假设存在缺失值所在的变量与其他变量存在线性关系，很多时候这种关系是不存在的。第10页/共78页第十一页，共78页。（五）多重替代法（五）多重替代法（五）多重替代法（五）多重替代法(Multiple Imputation)(Multiple Imputation

14、)n n由Rubin等人于1987年建立起来的作为简单估算的改进产物。n n首先，用一系列可能的值来替换(t hun)每一个缺失值，以反映被替换(t hun)的缺失数据的不确定性。n n然后，用标准的统计分析过程对多次替换(t hun)后产生的若干个数据集进行分析。n n最后，把来自于各个数据集的统计结果进行综合，得到总体参数的估计值。第11页/共78页第十二页，共78页。异常异常(ychng)数据处理数据处理n n异常挖掘(wju)及其应用n n异常数据挖掘(wju)方法简介n n基于统计的方法n n基于距离的方法n n基于密度的方法n n基于聚类的方法n n未来研究展望第12页/共78页第

15、十三页，共78页。什么什么(shn me)是异常是异常(Outlier)？n nHawkinsHawkins的定义：异常是在数据集中偏离大部分数据的数据，使人怀疑的定义：异常是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由随机因素产生这些数据的偏离并非由随机因素产生(ch(ch nshng)nshng)，而是产生，而是产生(ch(ch nshng)nshng)于完全不同的机制。于完全不同的机制。n nWeisbergWeisberg的定义：异常是与数据集中其余部分不服从相同统计模型的数的定义：异常是与数据集中其余部分不服从相同统计模型的数据。据。n nSamuelsSamuels

16、的定义：异常是足够地不同于数据集中其余部分的数据。的定义：异常是足够地不同于数据集中其余部分的数据。n nPorkessPorkess的定义：异常是远离数据集中其余部分的数据的定义：异常是远离数据集中其余部分的数据第13页/共78页第十四页，共78页。异常数据异常数据(shj)具有特殊的意具有特殊的意义和很高的实用价值义和很高的实用价值 n n 现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在在许多应用领域中，异常数据通常作为噪音而忽略，许多数据挖掘算法许多应用领域中，异常数据通常作为噪音而忽略，许多数据挖掘算法试图降低或消除

17、异常数据的影响。而在有些应用领域识别异常数据是试图降低或消除异常数据的影响。而在有些应用领域识别异常数据是许多工作的基础和前提，异常数据会带给我们新的视角。许多工作的基础和前提，异常数据会带给我们新的视角。n n如在欺诈检测中，异常数据可能意味欺诈行为的发生如在欺诈检测中，异常数据可能意味欺诈行为的发生(fshng)(fshng)，在，在入侵检测中异常数据可能意味入侵行为的发生入侵检测中异常数据可能意味入侵行为的发生(fshng)(fshng)。第14页/共78页第十五页，共78页。异常异常(ychng)检测的应用领域检测的应用领域n n电信、保险、银行中的欺诈检测与风险分析电信、保险、银行中

18、的欺诈检测与风险分析 n n发现电子商务中的犯罪行为发现电子商务中的犯罪行为n n灾害气象预报灾害气象预报n n税务局分析不同团体交所得税的记录，发现异常模型和趋势税务局分析不同团体交所得税的记录，发现异常模型和趋势 n n海关、民航等安检部门推断哪些人可能有嫌疑海关、民航等安检部门推断哪些人可能有嫌疑 n n海关报关海关报关(bo gun)(bo gun)中的价格隐瞒中的价格隐瞒n n营销定制：分析花费较小和较高顾客的消费行为营销定制：分析花费较小和较高顾客的消费行为n n医学研究中发现医疗方案或药品所产生的异常反应医学研究中发现医疗方案或药品所产生的异常反应n n计算机中的入侵检测计算机中

19、的入侵检测n n运动员的成绩分析运动员的成绩分析n n应用异常检测到文本编辑器，可有效减少文字输入的错误应用异常检测到文本编辑器，可有效减少文字输入的错误 n n第15页/共78页第十六页，共78页。什么是异常什么是异常什么是异常什么是异常(ychng)(ychng)挖掘？挖掘？挖掘？挖掘？(Outlier mining(Outlier mining，Exception mining)Exception mining)n n异常挖掘可以描述为：给定(i dn)N个数据对象和所期望的异常数据个数，发现明显不同、意外，或与其它数据不一致的前k个对象。n n异常挖掘问题由两个子问题构成：n n(1)

20、如何度量异常；n n(2)如何有效发现异常。第16页/共78页第十七页，共78页。为什么会出现异常数据为什么会出现异常数据(shj)？n n测量、输入错误或系统运行测量、输入错误或系统运行(ynxng)(ynxng)错误所致错误所致n n数据内在特性所决定数据内在特性所决定n n客体的异常行为所致客体的异常行为所致n n由于异常产生的机制是不确定的，异常挖掘算法检测出的由于异常产生的机制是不确定的，异常挖掘算法检测出的“异常数据异常数据”是否真正对应实际的异常行为，不是由异常挖掘算法来说明、解释的，是否真正对应实际的异常行为，不是由异常挖掘算法来说明、解释的，只能由领域专家来解释，异常挖掘算法

21、只能为用户提供可疑的数据，以只能由领域专家来解释，异常挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。理方式也取决于应用，并由领域专家决策。第17页/共78页第十八页，共78页。异常异常(ychng)数据实例数据实例n n一个人的年龄为一个人的年龄为-999-999就可能是由于就可能是由于(yuy)(yuy)程序处理缺省数程序处理缺省数据设置默认值所造成的据设置默认值所造成的 ；n n一个公司的高层管理人员的工资明显高于普通员工的工资可一个公司的

22、高层管理人员的工资明显高于普通员工的工资可能成为异常数据但却是合理的数据能成为异常数据但却是合理的数据(如平安保险公司如平安保险公司20072007年年 5 5位高管税后收入超过了位高管税后收入超过了10001000万元万元)；n n一部住宅电话的话费由每月一部住宅电话的话费由每月200200元以内增加到数千元可能就元以内增加到数千元可能就因为被盗打或其它特殊原因所致；因为被盗打或其它特殊原因所致；n n一张信用卡出现明显的高额消费也许是因为是盗用的卡。一张信用卡出现明显的高额消费也许是因为是盗用的卡。第18页/共78页第十九页，共78页。n n异常数据与众不异常数据与众不同但具有相对性：同但

23、具有相对性：n n 高与矮，疯子高与矮，疯子与常人。与常人。n n类似术语：类似术语：Outlier mining，Exception mining:异常挖异常挖掘、离群挖掘、掘、离群挖掘、例外例外(lwi)挖挖掘和稀有事件挖掘和稀有事件挖掘掘。第19页/共78页第二十页，共78页。异常检测异常检测(jin c)方法分类方法分类第20页/共78页第二十一页，共78页。从使用的主要从使用的主要(zhyo)技术路线角度分类技术路线角度分类n n基于统计的方法n n基于距离的方法n n基于密度(md)的方法n n基于聚类的方法n n基于偏差的方法n n基于深度的方法n n基于小波变换的方法n n基于

24、神经网络的方法第21页/共78页第二十二页，共78页。从类标号从类标号从类标号从类标号(正常或异常正常或异常正常或异常正常或异常(ychng)(ychng)可以利用的程度分类可以利用的程度分类可以利用的程度分类可以利用的程度分类n n无监督的异常检测方法n n在实际情况下，没有(mi yu)提供类标号n n有监督的异常检测方法n n要求存在异常类和正常类的训练集n n半监督的异常检测方法n n训练数据包含被标记的正常数据，但是没有(mi yu)关于异常对象的信息 第22页/共78页第二十三页，共78页。从面向对象的特殊性角度从面向对象的特殊性角度(jiod)分类分类n n面向高维数据(shj)

25、的方法n n面向时间序列的方法n n面向数据(shj)流的方法n n面向空间数据(shj)的方法n n面向Web 数据(shj)的方法第23页/共78页第二十四页，共78页。异常检测(jin c)中需要处理的几个问题第24页/共78页第二十五页，共78页。(1)用于定义用于定义(dngy)异常的属异常的属性个数性个数n n一个对象只有单个属性n n一个对象具有多个属性：n n可能某个属性异常，某个属性正常n n如：对于男生而言，n n 身高1.6m，体重(tzhng)55kg，这个很正常；n n 身高1.6m，体重(tzhng)75kg，这个有点异常；n n 身高1.8m，体重(tzhng)7

26、5kg，基本正常。n n若对于女生，则三组值可能都不太正常。n n所以，定义异常需要指明如何使用多个属性的值确定一个对象是否异常？第25页/共78页第二十六页，共78页。(2)全局全局(qunj)观点和局部观观点和局部观点点n n一个对象(duxing)可能相对于所有对象(duxing)看上去异常，但它相对于它的局部近邻不是异常的n n例如：身高1.85m对于一般人群是不常见的，但对于职业篮球运动员不算什么第26页/共78页第二十七页，共78页。(3)点的异常点的异常(ychng)程度程度n n某些技术方法是以二元方式来报告对象是否异常的，即：异常或正常n n但，这不能反映某些对象比其他对象更

27、加极端异常的基本事实(shsh)n n所以：可以通过定义对象的异常程度来给对象打分，如都为异常的情况下，也还有分高和分低的区别。异常点得分(outlier score)第27页/共78页第二十八页，共78页。(4)评估评估(pn)n n如果可以使用类标号来识别异常和正常数据:n n可以利用分类性能(xngnng)度量来评估异常检测方案的有效性。n n也可以使用如精度、召回率等度量方法来度量n n如果不能使用类标号，则评估是困难的。第28页/共78页第二十九页，共78页。(5)有效性有效性n n各种异常检测方案的计算开销是显著(xinzh)不同的n n例如：n n基于分类的方案需要相当多的资源(

28、训练数据和测试数据)来创建分类模型，但是这个模型一旦建立好了，使用时的开销通常很小n n而基于邻近度的方法，其时间复杂度通常为O(n2)第29页/共78页第三十页，共78页。异常检测的挑战(tio zhn)和前提n n挑战：n n数据中有多少异常点?n n方法(fngf)应该是无监督的，就像在干草堆中寻找一根针n n前提假设:n n假定数据集中被认为正常的点数远远超过被认为异常的点数第30页/共78页第三十一页，共78页。基于统计基于统计(tngj)的的异常检测异常检测第31页/共78页第三十二页，共78页。基于统计的异常基于统计的异常(ychng)检测检测这类方法大部分是从针对不同分布的异常

29、检验方法发展起来的，通常这类方法大部分是从针对不同分布的异常检验方法发展起来的，通常用户使用分布来拟合数据集。用户使用分布来拟合数据集。假定所给定假定所给定(i dni dn)的数据集存在一个分布或概率模型的数据集存在一个分布或概率模型(例如，正态例如，正态分布或泊松分布分布或泊松分布)，然后将与模型不一致，然后将与模型不一致(即分布不符合即分布不符合)的数据标的数据标识为异常数据。识为异常数据。第32页/共78页第三十三页，共78页。基于统计的异常基于统计的异常(ychng)检测检测n n假定用一个参数模型来描述数据的分布(fnb)(如正态分布(fnb)n n应用基于统计分布(fnb)的异常

30、点检测方法依赖于n n数据分布(fnb)n n参数分布(fnb)(如均值或方差)n n期望异常点的数目n n (置信度区间)第33页/共78页第三十四页，共78页。异常异常(ychng)点的概率定义点的概率定义n n异常点的概率定义(dngy)：n n异常点是一个对象，关于数据的概率分布模型，它具有低概率n n概率分布模型通过估计用户指定的分布的参数，由数据创建。n n例：如果假定数据具有高斯分布，则基本分布的均值和标准差可以通过计算数据的均值和标准差来估计，然后可以估计每个对象在该分布下的概率。第34页/共78页第三十五页，共78页。实例：检测一元实例：检测一元实例：检测一元实例：检测一元(

31、y yun)(y yun)正态分布中的异常点正态分布中的异常点正态分布中的异常点正态分布中的异常点n n下面利用统计学中最常使用的分布之一下面利用统计学中最常使用的分布之一:高斯高斯(正态正态)分布，来介绍分布，来介绍一种简单的统计学异常点检测一种简单的统计学异常点检测(ji(ji n c)n c)方法。方法。n n正态分布用记号：正态分布用记号：N(N(，)表示，表示，表示均值，表示均值，表示方差。表示方差。第35页/共78页第三十六页，共78页。cN(0,1)的10.31731.50.133620.04552.50.012430.00273.50.000540.0001来自N(0,1)分布

32、的对象(值)出现在分布尾部的机会很小。例如，对象落在 3标准差的中心区域以外的概率仅有0.0027。更一般地，如果x是属性值，则|x|=c的概率随c增加而迅速(xn s)减小。设=p(|x|c)。表6-1显示当分布为N(0,1)时c的某些样本值和对应的值。注意：离群值超过4个标准差的值出现的可能性是万分之一。实例：检测一元实例：检测一元(y yun)正态分布中正态分布中的异常点的异常点第36页/共78页第三十七页，共78页。对对某某一一长长度度(chngd)L测测量量10次次，其其数数据如下：据如下：试试用用拉拉依依达达准准则则(zhnz)剔剔除除坏值。坏值。解：解：20.33用用拉拉依依达达

33、准准则则(zhnz)剔除剔除次数1234567891011L(cm)10.3510.3810.310.3210.3510.3310.3710.3110.3420.3310.37第37页/共78页第三十八页，共78页。定义定义(dngy)n n定义定义 设属性设属性x x 取自具有取自具有(jy(jy u)u)均值均值0 0 和标准差和标准差1 1 的高斯分布。如的高斯分布。如果属性值果属性值x x 满足：满足：P(|x|c)=P(|x|c)=，其中，其中c c 是一个选定的常是一个选定的常量，则量，则x x以概率以概率1-1-为异常点。为异常点。n n为了使用该定义，需要指定为了使用该定义，需

34、要指定 值。从不寻常的值值。从不寻常的值(对象对象)预示来自不预示来自不同的值的观点来说，同的值的观点来说，表示我们错误地将来自给定分布的值分类为表示我们错误地将来自给定分布的值分类为异常点的概率。从异常点是异常点的概率。从异常点是N(0,1)N(0,1)分布的稀有值的观点来说，分布的稀有值的观点来说，表表示稀有程度。示稀有程度。第38页/共78页第三十九页，共78页。基于统计方法基于统计方法基于统计方法基于统计方法(fngf(fngf)异常点检测技术的优异常点检测技术的优异常点检测技术的优异常点检测技术的优缺点缺点缺点缺点n n优点：优点：n n异常点检测的统计学方法具有坚实的基础，建立在标

35、准的统计学技术异常点检测的统计学方法具有坚实的基础，建立在标准的统计学技术(如分布参数的估如分布参数的估计计)之上。之上。n n当存在充分当存在充分(chngfn)(chngfn)的数据和所用的检验类型的知识时，这些检验可能非常有效。的数据和所用的检验类型的知识时，这些检验可能非常有效。n n缺点：缺点：n n大部分统计方法都是针对单个属性的，对于多元数据技术方法较少。大部分统计方法都是针对单个属性的，对于多元数据技术方法较少。n n在许多情况下在许多情况下,数据分布是未知的。数据分布是未知的。n n对于高维数据对于高维数据,很难估计真实的分布。很难估计真实的分布。第39页/共78页第四十页，

36、共78页。基于基于(jy)距离的异距离的异常检测常检测第40页/共78页第四十一页，共78页。基于基于(jy)距离的异常检测距离的异常检测n n基于距离的异常检测方法，其基本思想如下：n n一个对象是异常的，如果它远离大部分其它对象。n n优点：确定数据集的有意义的邻近性度量比确定它的统计分布更容易，综合了基于分布的思想，克服(kf)了基于分布方法的主要缺陷。第41页/共78页第四十二页，共78页。基于基于(jy)距离的方法距离的方法有两种不同的策略有两种不同的策略 n n第一种策略是采用给定邻域半径，依据点的邻域中包含的对象多少来判定第一种策略是采用给定邻域半径，依据点的邻域中包含的对象多少

37、来判定异常；异常；n n如果一个如果一个(y(y )点的邻域内包含的对象少于整个数据集的一定比例则标识点的邻域内包含的对象少于整个数据集的一定比例则标识它为异常，也就是将没有足够邻居的对象看成是基于距离的异常。它为异常，也就是将没有足够邻居的对象看成是基于距离的异常。n n利用利用k k最近邻距离的大小来判定异常最近邻距离的大小来判定异常 。n n使用使用k-k-最近邻的距离度量一个最近邻的距离度量一个(y(y )对象是否远离大部分点，一个对象是否远离大部分点，一个(y(y )对对象的异常程度由到它的象的异常程度由到它的k-k-最近邻的距离给定最近邻的距离给定 。n n这种方法对这种方法对k

38、k的取值比较敏感。如果的取值比较敏感。如果k k太小太小(例如例如1)1)，则少量的邻近异常点可，则少量的邻近异常点可能导致较低的异常程度。如果能导致较低的异常程度。如果k k太大，则点数少于太大，则点数少于k k的簇中所有的对象可能的簇中所有的对象可能都成了异常点。都成了异常点。第42页/共78页第四十三页，共78页。到到k-最近邻的距离最近邻的距离(jl)的计算的计算n nk-最近邻的距离：n n一个对象的异常点得分由到它的k-最近邻的距离给定。n n异常点得分的最低值为0，最高值是距离函数(hnsh)的可能最大值-如无穷大第43页/共78页第四十四页，共78页。基于距离的异常基于距离的异

39、常(ychng)点检点检测测 例例1请问该二维数据集中，当请问该二维数据集中，当k=5时，哪个点具有最高时，哪个点具有最高的异常的异常(ychng)点得分点得分？第44页/共78页第四十五页，共78页。基于基于(jy)距离的异常点检测距离的异常点检测 例例2请问该二维数据集中，当请问该二维数据集中，当k=5时，哪个点具有最高时，哪个点具有最高的异常的异常(ychng)点得分点得分？第45页/共78页第四十六页，共78页。基于距离的异常基于距离的异常(ychng)检测检测的优缺点的优缺点n n优点：优点：n n基于距离的异常点检测方案简单基于距离的异常点检测方案简单 n n缺点：缺点：n n时间

40、复杂度时间复杂度O(m2)O(m2)，不适用于大数据集，不适用于大数据集n n不能处理不同密度不能处理不同密度(md)(md)区域的数据集，因为它使用全局阈值，区域的数据集，因为它使用全局阈值，不能考虑这种密度不能考虑这种密度(md)(md)的变化的变化第46页/共78页第四十七页，共78页。不能处理不能处理(chl)(chl)不同密度区域不同密度区域的数据集的数据集CDAB当k=5时，哪个点具有(jyu)最高的异常点得分,B的异常点得分和D的异常点得分哪个低？例：例：第47页/共78页第四十八页，共78页。基于密度的异常基于密度的异常(ychng)检测检测第48页/共78页第四十九页，共78

41、页。2/26/2023基于密度(md)的异常检测 n n当数据集含有多种分布或数据集由不同当数据集含有多种分布或数据集由不同(b tn(b tn)密度密度子集混合而成时，数据是否异常不仅仅取决于它与子集混合而成时，数据是否异常不仅仅取决于它与周围数据的距离大小，而且与邻域内的密度状况有周围数据的距离大小，而且与邻域内的密度状况有关。关。n n密度的两种不同密度的两种不同(b tn(b tn)理解：理解：n n 到第到第k k个最近邻的距离大小；个最近邻的距离大小；n n 到第到第k k个最近邻邻域内的对象的个数；个最近邻邻域内的对象的个数；定义定义1 1 对于正整数对于正整数k,k,对象对象p

42、 p到它的第到它的第k k个最近邻个最近邻o o的距离的距离k-distance(p)k-distance(p)定义为定义为:(1)(1)至少有至少有k k个对象满足个对象满足(mnz)(mnz)(2)(2)至多至多k-1k-1个对象满足个对象满足(mnz)(mnz)第49页/共78页第五十页，共78页。使用相对使用相对(xingdu)密密度的异常点检测度的异常点检测(LOF)n n对每个点对每个点,计算它的局部邻域计算它的局部邻域(ln y)(ln y)密度密度n n计算样本计算样本p p的局部异常因子的局部异常因子(LOF)(LOF)，把它作为样本，把它作为样本p p的平均密度比率和的平均

43、密度比率和近邻密度近邻密度n n异常点为具有最大异常点为具有最大LOFLOF值的点值的点 p2 p1 在基于距离(jl)的方法中,p2 不是异常，而在LOF 方法中p1 和p2 都被判定为异常。第50页/共78页第五十一页，共78页。n n定义3(1)对象的局部(jb)邻域密度 n n(2)相对密度n n其中，是包含x的k-最近邻的集合，是该集合的大小，y是一个最近邻。簇内靠近核心点的对象的相对密度(md)(LOF)接近于1，而处于簇的边缘或是簇的外面的对象的LOF相对较大。第51页/共78页第五十二页，共78页。相对密度异常点检测相对密度异常点检测(jin c)算算法法 n n1 1：kk是

44、最近邻个数是最近邻个数 n n2 2：for all for all 对象对象x dox don n3 3：确定确定x x的的k-k-最近邻最近邻N(x,k)N(x,k)。n n4 4：使用使用x x的最近邻的最近邻(即即N(x,k)N(x,k)中的对象中的对象)，n n 确定确定x x的密度的密度density(x,k)density(x,k)。n n5 5：end forend forn n6 6：for all for all 对象对象x dox don n7 7：由定义由定义(6-3)(6-3)，n n 置置outlier score(x,k)=relative density(x,k

45、)outlier score(x,k)=relative density(x,k)。n n8 8：end for end for n n9:9:对对outlier score(x,k)outlier score(x,k)降序排列降序排列(pili)(pili)，确定异常点得分高的若干对象，确定异常点得分高的若干对象 第52页/共78页第五十三页，共78页。基于密度的异常基于密度的异常(ychng)检测检测的不足的不足n n结果对参数k的选择很敏感，尚没有一种简单而有效的方法来确定合适的参数k；n n时间复杂度为 ，难以用于大规模数据集；n n需要有关(yugun)异常因子阈值或数据集中异常数据

46、个数的先验知识，在实际使用中有时由于先验知识的不足会造成一定的困难。第53页/共78页第五十四页，共78页。基于聚类的异常基于聚类的异常(ychng)检测检测第54页/共78页第五十五页，共78页。2/26/2023基于(jy)聚类的异常检测方法 物以类聚相似的对象聚合在一起。基于聚类的方法有两个共同特点：(1)先采用特殊的聚类算法处理输入(shr)数据而得到聚类，再在聚类的基础上来检测异常。(2)只需要扫描数据集若干次，效率较高，适用于大规模数据集。第55页/共78页第五十六页，共78页。2/26/2023基于聚类的异常基于聚类的异常(ychng)(ychng)检测检测方法方法n n静态数据

47、的异常检测n n第一阶段对数据进行聚类n n第二阶段计算对象或簇的异常因子，将异常因子大的对象或簇中对象判定为异常。n n动态数据的异常检测n n第一步，利用(lyng)静态数据的异常检测方法建立异常检测模型n n第二步，利用(lyng)对象与已有模型间的相似程度来检测异常n n关键问题：距离的定义、异常程度的度量第56页/共78页第五十七页，共78页。基于基于(jy)对象异常因子的方法对象异常因子的方法(1)n n首先聚类所有对象，然后评估对象属于(shy)簇的程度。n n如果一个对象不强属于(shy)任何簇，则称该对象为基于聚类的异常点。n n对于基于原型的聚类，可以用对象到它的簇中心的距

48、离来度量对象属于(shy)簇的程度。n n对于基于目标函数的聚类技术，可以使用该目标函数来评估对象属于(shy)任意簇的程度。n n特殊地，如果删除一个对象导致该目标的显著改进，则将该对象分类为异常点。第57页/共78页第五十八页，共78页。基于对象异常基于对象异常(ychng)因子的因子的方法方法(2)n n在与具有目标函数的聚类方法一起使用时，这种基于聚类的异常点定义是基于模型的异常定义的特殊(tsh)情况。n n对于基于密度的聚类，一个对象不强属于任何簇，如果它的密度太低；n n对于基于连接度的聚类，一个对象不强属于任何簇，如果它不是强连接的。n n基于原型的聚类，评估对象属于簇的程度的

49、方法有多种。一种方法是度量对象到簇原型的距离，并用到它作为该对象的异常程度得分。第58页/共78页第五十九页，共78页。基于对象基于对象(duxing)异常因子的异常因子的方法方法(3)n n定义定义4 给定簇给定簇C，C的摘要信息的摘要信息CSI(Cluster Summary Information)定义为：定义为：n n 其中其中n为簇为簇C的大小，的大小，Cluster为簇为簇C中对象标识的集合，中对象标识的集合，Summary由分类属性中不同取值由分类属性中不同取值的频度信息和数值属性的质心两的频度信息和数值属性的质心两部分构成，即：部分构成，即：n n定义定义5 设设 是数据集是数

50、据集D的分解表示，即的分解表示，即 ，对象对象p的异常因子的异常因子(ynz)OF(p)定义为定义为p与所有簇间距离的加权与所有簇间距离的加权平均值：平均值：第59页/共78页第六十页，共78页。n n引理引理 如果随机变量如果随机变量(su j bin lin)服从服从正态分布正态分布 ，则有：，则有：第60页/共78页第六十一页，共78页。n n两阶段异常挖掘方法TOD描述如下：n n第一步，对数据集D进行采用一趟聚类算法进行聚类，得到聚类结果n n第二步，计算数据集D中所有(suyu)对象p的异常因子OF(p)，及其平均值Ave_OF和标准差Dev_OF，满足条件：n n n n 的对象