演示文稿数据挖掘第九章离群点挖掘_第1页
演示文稿数据挖掘第九章离群点挖掘_第2页
演示文稿数据挖掘第九章离群点挖掘_第3页
演示文稿数据挖掘第九章离群点挖掘_第4页
演示文稿数据挖掘第九章离群点挖掘_第5页
已阅读5页,还剩74页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

演示文稿数据挖掘第九章离群点挖掘2023/4/20现在是1页\一共有79页\编辑于星期五数据挖掘第九章离群点挖掘ppt课件现在是2页\一共有79页\编辑于星期五主要内容离群点挖掘的概述离群点数据挖掘方法简介基于统计的方法基于距离的方法基于密度的方法基于聚类的方法现在是3页\一共有79页\编辑于星期五什么是离群点(Outlier)?Hawkins的定义:离群点是在数据集中偏离大部分数据的数据,使人怀疑这些数据的偏离并非由随机因素产生,而是产生于完全不同的机制。Weisberg的定义:离群点是与数据集中其余部分不服从相同统计模型的数据。Samuels的定义:离群点是足够地不同于数据集中其余部分的数据。Porkess的定义:离群点是远离数据集中其余部分的数据现在是4页\一共有79页\编辑于星期五离群点的特殊意义和实用价值

现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中,离群点通常作为噪音而忽略,许多数据挖掘算法试图降低或消除离群点的影响。而在有些应用领域识别离群点是许多工作的基础和前提,离群点会带给我们新的视角。如在欺诈检测中,离群点可能意味欺诈行为的发生,在入侵检测中离群点可能意味入侵行为的发生。现在是5页\一共有79页\编辑于星期五实例:例如我们设儿童上学的具体年龄总体服从正态分布,所给的数据集是某地区随机选取的开始上学的20名儿童的年龄具体的年龄特征如下:

年龄={6,7,6,8,9,10,8,11,7,9,12,7,11,8,13,7,8,14,9,12}

那么.相应的统计参数是:均值=9.1;标准差=2.3。

如果选择数据分布的阈值为:阈值=均值±2×标准差

故在[4.5,13.7]区间以外的数据都是潜在的离群点,将最大值取整为13。所以年龄为14的孩子可能是个例外。而且由均值可知,此地的孩子普遍上学较晚.教育部门以后可据此作一些政策上的改进。现在是6页\一共有79页\编辑于星期五案例:孤立点挖掘在高等学校科技统计数据分析中的应用

孤立点实验数据源:(选自全国普通高等学校科技统计数据上报基表中的数据)

甘肃省2010年科技统计上报数据中的一所高校数据

对基表中的数据,如选取科技人员职称和学历作为最终测试对象,因职称只有院士、正高、副高、讲师、助教和其它职称共六种职称,而学历只有高中以下、中专、大专、本科、硕士和博士共六种职称,职称和学历跨度小,检测出来的孤立点孤立程度相对较低,故选取跨度较大的出生年月作为测试对象。选取三个指标:出生年月、学位和职称作为检测属性。 现在是7页\一共有79页\编辑于星期五实验及结果分析用DS算法时,取M=20,算法返回距离的值最大的20个教师信息如表1所示。通过分析,可以发现孤立点数据中存在两种典型的孤立点类别:

(1)孤立点数据远远偏离于正常值的范围

序号1-4(噪声)(2)孤立点数据偏离于正常值的范围

可能是录入错误,可能是真实数据序号出生年月学历职称1198907大学本科正高级2198510硕士研究生副高级3196008博士研究生初级4197909专科副高级5196002博士研究生中级6195511博士研究生副高级7198109硕士研究生副高级8197408博士研究生初级9198109硕士研究生副高级10198206博士研究生副高级11198301博士研究生副高级12195706博士研究生副高级13195712博士研究生副高级14197302硕士研究生正高级15197211大学本科正高级16195001硕士研究生正高级17197304硕士研究生副高级18195011硕士研究生副高级19196911硕士研究生初级20197002硕士研究生初级现在是8页\一共有79页\编辑于星期五离群点检测的应用领域电信、保险、银行中的欺诈检测与风险分析发现电子商务中的犯罪行为灾害气象预报税务局分析不同团体交所得税的记录,发现异常模型和趋势海关、民航等安检部门推断哪些人可能有嫌疑

海关报关中的价格隐瞒营销定制:分析花费较小和较高顾客的消费行为医学研究中发现医疗方案或药品所产生的异常反应计算机中的入侵检测应用异常检测到文本编辑器,可有效减少文字输入的错误

……现在是9页\一共有79页\编辑于星期五离群点挖掘(Outliermining)离群点挖掘问题由两个子问题构成:。(1)定义在一个数据集中什么数据是不一致或离群的数据;(2)找出所定义的离群点的有效挖掘方法。离群点挖掘问题可以概括为如何度量数据偏离的程度和有效发现离群点的问题。现在是10页\一共有79页\编辑于星期五为什么会出现离群点?测量、输入错误或系统运行错误所致数据内在特性所决定客体的异常行为所致由于离群点产生的机制是不确定的,离群点挖掘算法检测出的“离群点”是否真正对应实际的异常行为,不是由离群点挖掘算法来说明、解释的,只能由领域专家来解释,离群点挖掘算法只能为用户提供可疑的数据,以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用,并由领域专家决策。现在是11页\一共有79页\编辑于星期五离群点挖掘中需要处理的几个问题

(1)全局观点和局部观点

离群点与众不同,但具有相对性。(2)点的离群程度

可以通过定义对象的偏离程度来给对象打分——离群因子(OutlierFactor)或离群值得分(OutlierScore),即都为离群点的情况下,也还有分高和分低的区别。(3)离群点的数量及时效性

正常点的数量远远超过离群点的数量,离群点的数量在大规模数据集中所占的比例较低,小于5%甚至1%现在是12页\一共有79页\编辑于星期五离群点实例一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的;一个公司的高层管理人员的工资明显高于普通员工的工资可能成为离群点但却是合理的数据(如平安保险公司2007年5位高管税后收入超过了1000万元);一部住宅电话的话费由每月200元以内增加到数千元可能就因为被盗打或其它特殊原因所致;一张信用卡出现明显的高额消费也许是因为是盗用的卡。现在是13页\一共有79页\编辑于星期五离群点与众不同但具有相对性:

高与矮,疯子与常人。类似术语:

Outliermining,Exceptionmining:异常挖掘、离群挖掘、例外挖掘和稀有事件挖掘。现在是14页\一共有79页\编辑于星期五离群点检测方法分类现在是15页\一共有79页\编辑于星期五从使用的主要技术路线角度分类基于统计的方法基于距离的方法基于密度的方法基于聚类的方法基于偏差的方法基于深度的方法基于小波变换的方法基于神经网络的方法…现在是16页\一共有79页\编辑于星期五从类标号(正常或异常)利用的程度分类无监督的离群点检测方法在实际情况下,没有提供类标号有监督的离群点检测方法要求存在离群点类和正常类的训练集半监督的离群点检测方法训练数据包含被标记的正常数据,但是没有关于离群点对象的信息现在是17页\一共有79页\编辑于星期五离群点检测中需要处理的问题现在是18页\一共有79页\编辑于星期五(1)用于定义离群点的属性个数一个对象只有单个属性一个对象具有多个属性:可能某个属性异常,某个属性正常如:对于男生而言,身高1.6m,体重55kg,这个很正常;身高1.6m,体重75kg,这个有点离群;身高1.8m,体重75kg,基本正常。若对于女生,则三组值可能都不太正常。所以,定义离群点需要指明如何使用多个属性的值确定一个对象是否离群?现在是19页\一共有79页\编辑于星期五(2)全局观点和局部观点一个对象可能相对于所有对象看上去离群,但它相对于它的局部近邻不是离群的例如:身高1.85m对于一般人群是不常见的,但对于职业篮球运动员不算什么现在是20页\一共有79页\编辑于星期五(3)点的离群程度某些技术方法是以二元方式来报告对象是否离群点,即:离群点或正常点但,这不能反映某些对象比其他对象更加极端偏离的基本事实通过定义对象的离群程度来给对象打分,如都为离群点的情况下,也还有分高和分低的区别。——离群点得分(outlierscore)或离群因子(OutlierFactor)现在是21页\一共有79页\编辑于星期五离群点检测的挑战和前提挑战:数据中有多少离群点?方法应该是无监督的,就像在干草堆中寻找一根针前提假设假定数据集中被认为正常的点数远远超过被认为离群的点数现在是22页\一共有79页\编辑于星期五基于统计的离群点检测现在是23页\一共有79页\编辑于星期五基于统计的离群点检测这类方法大部分是从针对不同分布的离群点检验方法发展起来的,通常用户使用分布来拟合数据集。假定所给定的数据集存在一个分布或概率模型(例如,正态分布或泊松分布),然后将与模型不一致(即分布不符合)的数据标识为离群数据。现在是24页\一共有79页\编辑于星期五基于统计的离群点检测假定用一个参数模型来描述数据的分布(如正态分布)应用基于统计分布的离群点检测方法依赖于数据分布参数分布(如均值或方差)期望离群点的数目

(置信度区间)现在是25页\一共有79页\编辑于星期五离群点的概率定义离群点的概率定义:离群点是一个对象,关于数据的概率分布模型,它具有低概率概率分布模型通过估计用户指定的分布的参数,由数据创建。例:如果假定数据具有高斯分布,则基本分布的均值和标准差可以通过计算数据的均值和标准差来估计,然后可以估计每个对象在该分布下的概率。现在是26页\一共有79页\编辑于星期五实例:检测一元正态分布中的离群点下面利用统计学中最常用的分布--高斯(正态)分布,来介绍一种简单的统计学离群点检测方法。正态分布用记号:N(μ,σ)表示,μ表示均值,σ表示方差。现在是27页\一共有79页\编辑于星期五cN(0,1)的α10.31731.50.133620.04552.50.012430.00273.50.000540.0001来自N(0,1)分布的对象(值)出现在分布尾部的机会很小。例如,对象落在3标准差的中心区域以外的概率仅有0.0027。更一般地,如果x是属性值,则|x|>=c的概率随c增加而迅速减小。设α=p(|x|≥c)。表6-1显示当分布为N(0,1)时c的某些样本值和对应的α值。注意:离群值超过4个标准差的值出现的可能性是万分之一。实例:检测一元正态分布中的离群点现在是28页\一共有79页\编辑于星期五定义定义设属性x取自具有均值0和标准差1的高斯分布。如果属性值x满足:P(|x|≥c)=α,其中c是一个选定的常量,则x以概率1-α为离群点。为了使用该定义,需要指定α值。从不寻常的值(对象)预示来自不同的值的观点来说,α表示我们错误地将来自给定分布的值分类为离群点的概率。从离群点是N(0,1)分布的稀有值的观点来说,α表示稀有程度。现在是29页\一共有79页\编辑于星期五如果(正常对象的)一个感兴趣的属性的分布是具有均值μ和标准差σ的正态分布,即

分布,则可以通过变换z=(x-μ)/σ转换为标准正态分布N(0,1),通常μ和σ是未知的,可以通过样本均值和样本标准差来估计。实践中,当观测值很多时,这种估计的效果很好;另一方面,由概率统计中的大数定律可知,在大样本的情况下可以用正态分布近似其它分布。现在是30页\一共有79页\编辑于星期五在该图中,中心线μ是观测值的预测值,μ3σ对应上下控制线,μ2σ对应上、下警告线。根据3σ原则,99.73%的观测值将落在上下控制线的区间内,仅有0.27%的观测值落在此区间之外。质量控制示意图μ+3σxtμ-3σμ-2σμ+2σμ现在是31页\一共有79页\编辑于星期五对于观测样本X:(1)如此点在上、下警告线之间区域内,则测定过程处于控制状态,生产过程或样本分析结果有效;(2)如果此点超出上、下警告线,但仍在上、下控制线之间的区域内,提示质量开始变劣,可能存在“失控”倾向,应进行初步检查,并采取相应的校正措施;(3)若此点落在上、下控制线之外,表示生产或测定过程“失控",生产的是废品或观测样本无效。应立即检查原因,予以纠正。质量控制示意图

tμ+3σxμ-3σμ-2σμ+2σμ现在是32页\一共有79页\编辑于星期五基于统计的离群点检测方法的优缺点优点:离群点检测的统计学方法具有坚实的基础,建立在标准的统计学技术(如分布参数的估计)之上。当存在充分的数据和所用的检验类型的知识时,这些检验可能非常有效。缺点:大部分统计方法是针对单个属性的,对于多元数据技术方法较少。在许多情况下,数据分布是未知的。对于高维数据,很难估计真实的分布。这类方法不适合混合类型数据现在是33页\一共有79页\编辑于星期五基于距离的离群点检测现在是34页\一共有79页\编辑于星期五基于距离的离群点检测基于距离的离群点检测方法,其基本思想如下:一个对象是离群的,如果它远离大部分其它对象。优点:确定数据集的有意义的邻近性度量比确定它的统计分布更容易,综合了基于分布的思想,克服了基于分布方法的主要缺陷。现在是35页\一共有79页\编辑于星期五基于距离方法的两种不同策略第一种策略是采用给定邻域半径,依据点的邻域中包含的对象多少来判定离群点如果一个点的邻域内包含的对象少于整个数据集的一定比例则标识它为离群点,也就是将没有足够邻居的对象看成是基于距离的离群点。利用k最近邻距离的大小来判定离群使用k-最近邻的距离度量一个对象是否远离大部分点,一个对象的离群程度由到它的k-最近邻的距离给定。这种方法对k的取值比较敏感。k太小(例如1),则少量的邻近离群点可能导致较低的离群程度。k太大,则点数少于k的簇中所有的对象可能都成了离群点。现在是36页\一共有79页\编辑于星期五到k-最近邻的距离的计算k-最近邻的距离:一个对象的离群点得分由到它的k-最近邻的距离给定。离群点得分的最低值为0,最高值是距离函数的可能最大值----如无穷大定义6-2对于正整数k,对象p的k最近邻距离k-distance(p)定义为:(1)除p外,至少有k个对象o满足(2)除p外,至多k-1个对象o满足现在是37页\一共有79页\编辑于星期五2023/4/20定义6-3点x的离群因子定义为:这里是不包含x的k-最近邻的集合,

是该集合的大小。现在是38页\一共有79页\编辑于星期五基于距离的离群点检测算法输入:数据集D;最近邻个数k输出:离群点对象列表1:forall对象xdo2:

确定x的k-最近邻集合N(x,k)3:

确定x的离群因子OF1(x,k)4:endfor5:对OF1(x,k)降序排列,确定离群因子大的若干对象6:return应注意:x的k-最近邻的集

包含的对象数可能超过k。现在是39页\一共有79页\编辑于星期五选择合适的离群因子阈值一种形式上简单的方法是指定离群点个数;这里介绍另一种确定OF1(x,k)分割阈值的方法:对OF1(x,k)降序排列,选择OF1(x,k)急剧下降的点作为离群值、正常值的分隔点,如图6-3所示,在该图中,有两个点判定为离群点。现在是40页\一共有79页\编辑于星期五例6-1例6-1在图6-4所示的二维数据集中,当k=2时,P1、P2哪个点具有更高的离群点得分?(使用欧式距离)xy1213112122236824325752现在是41页\一共有79页\编辑于星期五例6-1解答:对P1点进行分析:k=2;最近邻的点为P3(5,7),P2(5,2),distance(P1,P2)与distance(P1,P3)分别为6.08,1.41,平均距离为:对P2点进行分析:k=2;最近邻的点为P3,P4,同理有:因为OF1(P1,K)>OF1(P2,K),因此,P1点更有可能是离群点。现在是42页\一共有79页\编辑于星期五基于距离的离群点检测例6-2在图6-5所示的二维数据集中,当k=5时,哪个点具有最大的离群因子,B的离群因子和D的离群因子哪个小?CDAB解答:图所示的二维数据集主体由一个紧密的簇和一个松散的簇组成,下图以灰度图显示了各点的离群因子情况,D的离群因子低于松散簇中部分点的离群因子。点C的离群因子最大,B点的离群因子大于D点的离群因子。这个例子说明,当数据集包含不同密度的区域时,基于距离的离群点检测方法不能很好地识别离群点。CDAB离群点得分递增现在是43页\一共有79页\编辑于星期五基于距离的离群检测的优缺点优点:基于距离的离群点检测方案简单缺点:(1)检测结果对参数k的选择较敏感(2)时间复杂度为

,难以用于大规模数据集,这里n为数据集的规模;(3)需要有关离群因子阈值或数据集中离群点个数的先验知识,在实际使用中有时由于先验知识的不足会造成一定的困难。(4)因为它使用全局阈值,不能处理不同密度区域的数据集。现在是44页\一共有79页\编辑于星期五基于相对密度的离群点检测现在是45页\一共有79页\编辑于星期五2023/4/20基于密度的离群点检测

当数据集含有多种分布或数据集由不同密度子集混合而成时,数据是否离群不仅仅取决于它与周围数据的距离大小,而且与邻域内的密度状况有关。这里使用每个对象到第k个最近邻的距离大小来度量密度。现在是46页\一共有79页\编辑于星期五定义6-4(1)对象的局部邻域密度(2)相对密度其中,是不包含x的k-最近邻的集合,是该集合的大小,y是一个最近邻。基于相对密度的离群点检测方法通过比较对象的密度与它的邻域中的对象平均密度来检测离群点。簇内靠近核心点的对象的相对密度接近于1,而处于簇的边缘或是簇的外面的对象的相对较大。定义相对密度为离群因子:现在是47页\一共有79页\编辑于星期五相对密度离群点检测算法1:{k是最近邻个数}2:forall对象xdo3:确定x的k-最近邻N(x,k)。4:使用x的最近邻(即N(x,k)中的对象),确定x的密度density(x,k)。5:endfor6:forall对象xdo7:确定x的相对密度relativedensity(x,k),并赋值给OF2(x,k)。8:endfor9:对OF2(x,k)降序排列,确定离群点得分高的若干对象现在是48页\一共有79页\编辑于星期五例6-3:给定二维数据集,表6-2给出了点的坐标,可视化的图形如图6-7所示(对象间的距离采用曼哈顿(Manhattan)距离计算)。(1)取k=2,计算点P4,P15的局部邻域密度

及相对密度

,哪个点更可能是离群点?(2)取k=2,按照基于距离的离群点检测,P4,P15哪个点更可能是离群点?P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15P16X1112222333344455Y2341234123412301现在是49页\一共有79页\编辑于星期五(1)对于P4,k最近邻邻域包含两个对象:

对于P15,k最近邻邻域包含2个对象:P12,P16的密度均为1,相对点P4,点P15更可能是离群点。现在是50页\一共有79页\编辑于星期五(2)对于k=2P4的k最近邻邻域为

,k最近邻距离均值为1。P15的k最近邻邻域为

,k最近邻距离均值为1.5。经过比较可以看出,点P15的离群程度要高。现在是51页\一共有79页\编辑于星期五例6-4模拟图6-8中类似数据,K取2,3,5时,以表格方式给出所有点的局部邻域密度及相对密度、基于距离的离群因子。(采用欧式距离)解答:K取2,3,5时,所有点的局部邻域密度、相对密度、基于距离的离群因子表所示。点的坐标

k=2

k=3

k=5

x

y局部邻域密度相对密度距离离群因子局部邻域密度相对密度距离离群因子局部邻域密度相对密度距离离群因子45950.070.8814.000.060.8716.330.040.9022.6060960.051.3420.500.041.1522.330.041.1127.0051800.060.9617.000.050.9618.330.050.8020.6038900.080.9113.000.060.9416.330.040.9623.8039770.070.9814.500.061.0417.670.041.0225.0069790.041.2122.500.041.3325.670.031.3531.801511690.131.398.000.131.168.000.101.079.801451630.131.568.000.111.409.330.091.2711.401511560.141.367.000.121.208.670.101.0910.401531630.171.046.000.150.876.670.140.767.401611540.121.118.500.091.4911.330.071.4913.601511610.220.704.500.180.705.670.140.767.401571670.131.178.000.111.409.330.091.2411.201611590.121.448.500.101.209.670.091.1410.801121860.027.0056.000.027.9958.670.026.6860.80502380.015.85131.000.015.66138.000.015.52146.60现在是52页\一共有79页\编辑于星期五基于聚类的离群点检测现在是53页\一共有79页\编辑于星期五2023/4/20基于聚类的离群点检测方法

物以类聚—相似的对象聚合在一起。基于聚类的方法有两个共同特点:

(1)先采用特殊的聚类算法处理输入数据而得到聚类,再在聚类的基础上来检测离群点。

(2)只需要扫描数据集若干次,效率较高,适用于大规模数据集。现在是54页\一共有79页\编辑于星期五2023/4/20基于聚类的离群点检测方法静态数据的离群点检测第一阶段对数据进行聚类第二阶段计算对象或簇的离群因子,将离群因子大的对象或簇中对象判定为离群点。动态数据的离群点检测第一步,利用静态数据的离群检测方法建立离群检测模型第二步,利用对象与已有模型间的相似程度来检测离群点关键问题:距离的定义、离群程度的度量现在是55页\一共有79页\编辑于星期五基于对象离群因子的方法首先聚类所有对象,然后评估对象属于簇的程度如果一个对象不强属于任何簇,则称该对象为基于聚类的离群点。对于基于原型的聚类,可以用对象到它的簇中心的距离来度量对象属于簇的程度。现在是56页\一共有79页\编辑于星期五基于对象离群因子的方法定义6-5

给定簇C,C的摘要信息CSI(ClusterSummaryInformation)定义为:其中n为簇C的大小,Summary由分类属性中不同取值的频度信息和数值属性的质心两部分构成,即:定义6-6

假设据集D被聚类算法划分为k个簇对象p的离群因子(OutlierFactor)OP3(p)定义为p与所有簇间距离的加权平均值:现在是57页\一共有79页\编辑于星期五引理如果随机变量服从正态分布,则有:现在是58页\一共有79页\编辑于星期五两阶段离群点挖掘方法TOD描述如下:第一步,对数据集D进行采用一趟聚类算法进行聚类,得到聚类结果第二步,计算数据集D中所有对象p的离群因子OF3(p),及其平均值Ave_OF和标准差Dev_OF,满足条件:

的对象判定为离群点。

通常取

现在是59页\一共有79页\编辑于星期五例6-5基于聚类的离群点检测示例1对于图所示的二维数据集,比较点P1(6,8),P2(5,2),哪个更有可能成为离群点。假设数据集经过聚类后得到聚类结果为C={C1、C2、C3},图中红色圆圈标注,三个簇的质心分别为:C1(5.5,7.5)、C2(5,2)、C3(1.75,2.25),试计算所有对象的离群因子。现在是60页\一共有79页\编辑于星期五例6-5基于聚类的离群点检测示例1解答:根据定义6-6,公式对于P1点有:

对于P2有:可见,点P1较P2更可能成为离群点。现在是61页\一共有79页\编辑于星期五例6-5基于聚类的离群点检测示例1同理可求得所有对象的离群因子,结果如表所示。xyOF3122.2132.3112.9212.6221.7231.9685.9242.5322.2574.8523.4进一步求得所有点的离群因子平均值Ave_OF=2.95,标准差Dev_OF=1.3,假设

;则阈值E=Ave_OF+*Dev_OF=2.95+1.3=4.25离群因子大于4.25的对象可视为离群点,P1与P2都是离群点,但相对而言,P1更有可能成为离群点。现在是62页\一共有79页\编辑于星期五基于簇的离群因子的方法(1)在某种度量下,相似对象或相同类型的对象会聚集在一起,或者说正常数据与离群数据会聚集在不同的簇中;(2)正常数据占绝大部分,且离群数据与正常数据表现出明显不同,或者说离群数据会偏离正常数据(也就是大部分数据)。介绍簇的离群因子概念,利用簇的离群因子将簇区分为正常簇和离群簇。现在是63页\一共有79页\编辑于星期五定义6-7给定簇C,C的摘要信息CSI(ClusterSummaryInformation)定义为:其中kind为簇的类别(取值‘normal’或‘outlier’),为簇C的大小,Cluster为簇C中对象标识的集合,Summary由分类属性中不同取值的频度信息和数值型属性的质心两部分构成,即:现在是64页\一共有79页\编辑于星期五定义6-8假设据集D被聚类算法划分为k个簇,簇离群因子(OutlierFactor)定义为簇其它所有簇间距离的加权平均值:如果一个簇离几个大簇的距离都比较远,则表明该簇偏离整体较远,其离群因子也较大。度量了簇偏离整个数据集的程度,其值越大,说明偏离整体越远。现在是65页\一共有79页\编辑于星期五基于聚类的离群挖掘方法(CBOD)CBOD方法由两个阶段构成:第一阶段是利用一趟聚类算法对数据集进行聚类;第二阶段是计算每个簇的离群因子,并按离群因子对簇进行排序,最终确定离群簇,也即确定离群对象。现在是66页\一共有79页\编辑于星期五CBOD算法描述如下:第一阶段,聚类:对数据集D进行聚类,得到聚类结果;第二阶段,确定离群簇:计算每个簇的离群因子,按递减的顺序重新排列,求满足:

的最小,将簇标识为‘outlier’类(即其中每个对象均看成离群),而将标识为‘normal’类(即其中每个对象均看成正常)。现在是67页\一共有79页\编辑于星期五例6-6基于聚类的离群点检测示例2对例6-5中的数据集,聚类后得到三个簇C={C1、C2、C3},簇心分别为:C1(5.5,7.5)、C2(5,2)、C3(1.75,2.25)。簇之间的距离分别为进一步计算三个簇的离群因子,具体如下:现在是68页\一共有79页\编辑于星期五例6-6基于聚类的离群点检测示例2可见簇C1的离群因子最大,其中包含的对象判定为离群点,与例6-5得到的结论相同。现在是69页\一共有79页\编辑于星期五基于聚类的动态数据的离群点检测

基本思想如下:

在对训练集聚类的基础上,按照簇的离群因子排序簇,并按一定比例将簇标识为”normal”或”outlier”,以标识的簇作为分类模型,按照对象与分类模型中最接近簇的距离判断它是否离群点。

现在是70页\一共有79页\编辑于星期五基于聚类的动态数据的离群点检测第一步,聚类:对训练集进行聚类,得到聚类结果;第二步,给簇作标记:计算每个簇的离群因子,按递减的顺序重新排列,求满足:

的最小b,将簇标识为离群簇,而将标识为正常簇。第三步,确定模型:以每个簇的摘要信息,聚类半径阈值r作为模型。(1)模型建立现在是71页\一共有79页\编辑于星期五(2)模型评估利用改进的最近邻分类方法INN(ImprovedNearestNeighbor)

评估测试集中的每个对象。INN方法具体描述如下:对于测试集中对象p,计算p与每个簇的距离若,则说明p是已知类型的行为,将簇的标识作为p的标识,否则说明p是一种新的行为,将p标识为可疑对象——候选离群点。现在是72页\一共有79页\编辑于星期五(3)模型更新对于测试集中对象p,按照前面聚类的方式,对新增对象进行增量式聚类更新用建立模型同样的方法对所有簇重新标记其类别。现在是73页\一共有79页\编辑于星期五6.6离群点挖掘方法的评估

可以通过下表所示混淆矩阵来描述离群点挖掘方法的检测性能。在离群点检测问题中,并不关注预测正确的normal类对象,重点关注的是正确预测的outlier类对象。预测类别outliernormal实际类别outlier预测正确的outlier预测错误的outliernormal预测错误的normal预测正确的normal现在是74页\一共有79页\编辑于星期五离群点检测方法准确性的两个指标检测率(Detectionrate)表示被正确检测的离群点记录数占整个离

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论