数据挖掘第九章离群点挖掘实用课件

数据挖掘第九章离群点挖掘数据挖掘第九章离群点挖掘1数据挖掘第九章离群点挖掘ppt课件数据挖掘第九章离群点挖掘ppt课件2主要内容主要内容n离群点挖掘的概述n离群点数据挖掘方法简介n基于统计的方法基于统计的方法n基于距离的方法基于距离的方法n基于密度的方法基于密度的方法n基于聚类的方法基于聚类的方法主要内容离群点挖掘的概述3什么是离群点什么是离群点(Outlier)？nHawkins的定义的定义：离群点是在数据集中偏离大部分数偏离大部分数据的数据据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。nWeisberg的定义：离群点是与数据集中其余部分不服从相同统计模型的数据。nSamuels的定义：离群点是足够地不同于数据集中其余部分的数据。nPorkess的定义：离群点是远离数据集中其余部分的数据什么是离群点(Outlier)？Hawkins的定义：离群点4离群点的特殊意义和实用价值离群点的特殊意义和实用价值 n 现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中，离群点通常作为噪音而忽略，许多数据挖掘算法试图降低或消除离群点的影响。而在有些应用领域识别离群点是许多工作的基础和前提，离群点会带给我们新的视角。n如在欺诈检测中，离群点可能意味欺诈行为的发生，在入侵检测中离群点可能意味入侵行为的发生。离群点的特殊意义和实用价值 现有数据挖掘研究大多集中于发现5n实例：n例如我们设儿童上学的具体年龄总体服从正态分布，所给的数据集是某地区随机选取的开始上学的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的孩子可能是个例外。而且由均值可知，此地的孩子普遍上学较晚.教育部门以后可据此作一些政策上的改进。实例：6n案例：孤立点挖掘在高等学校科技统计数据分案例：孤立点挖掘在高等学校科技统计数据分析中的应用析中的应用 孤立点实验数据源：孤立点实验数据源：（选自全国普通高等学校科技统计数据上报基表中的数据）甘肃省甘肃省2010年科技统计上报数据中的一所高校数据年科技统计上报数据中的一所高校数据 对基表中的数据，如选取科技人员职称和学历作为最终测试对象，因职称只有院士、正高、副高、讲师、助教和其它职称共六种职称，而学历只有高中以下、中专、大专、本科、硕士和博士共六种职称，职称和学历跨度小，检测出来的孤立点孤立程度相对较低，故选取跨度较大的出生年月作为测试对象。选取三个指标:出生年月、学位和职称作为检测属性。案例：孤立点挖掘在高等学校科技统计数据分析中的应用7n实验及结果分析实验及结果分析 用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硕士研究生初级实验及结果分析序号出生年月学历职称1198907大学本科正高8离群点检测的应用领域离群点检测的应用领域n电信、保险、银行中的欺诈检测与风险分析 n发现电子商务中的犯罪行为n灾害气象预报n税务局分析不同团体交所得税的记录，发现异常模型和趋势 n海关、民航等安检部门推断哪些人可能有嫌疑 n海关报关中的价格隐瞒n营销定制：分析花费较小和较高顾客的消费行为n医学研究中发现医疗方案或药品所产生的异常反应n计算机中的入侵检测n应用异常检测到文本编辑器，可有效减少文字输入的错误 n离群点检测的应用领域电信、保险、银行中的欺诈检测与风险分析 9表在KDDCUP99数据集上的检测性能训练数据包含被标记的正常数据，但是没有关于离群点对象的信息用DS算法时，取M=20，算法返回距离的值最大的20个教师信息如表1所示。对基表中的数据，如选取科技人员职称和学历作为最终测试对象，因职称只有院士、正高、副高、讲师、助教和其它职称共六种职称，而学历只有高中以下、中专、大专、本科、硕士和博士共六种职称，职称和学历跨度小，检测出来的孤立点孤立程度相对较低，故选取跨度较大的出生年月作为测试对象。这里 是不包含x的k-最近邻的集合，基于聚类的离群点检测方法在P1上建立模型，然后用P2更新模型，再在P3上检测。参数分布(如均值或方差)使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的离群程度由到它的k-最近邻的距离给定。基于相对密度的离群点检测离群点检测中需要处理的问题3：确定x的离群因子 OF1(x,k)离群因子(Outlier Factor)定义为簇 其它所有簇间距离的加权平均值：一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的；(1)先采用特殊的聚类算法处理输入数据而得到聚类，再在聚类的基础上来检测离群点。定为离群点，与例6-5得到的结论相同。基于密度的离群点检测定义6-2 对于正整数k，对象p的k最近邻距离k-distance(p)定义为:(1)对于P4，k最近邻邻域包含两个对象：离群点挖掘离群点挖掘(Outlier miningOutlier mining)n离群点挖掘问题由两个子问题构成：。n(1)定义在一个数据集中什么数据是不一致或离群的数据；n(2)找出所定义的离群点的有效挖掘方法。离群点挖掘问题可以概括为如何度量数据偏离的程度和有效发现离群点的问题。表在KDDCUP99数据集上的检测性能离群点挖掘(Outli10为什么会出现离群点？为什么会出现离群点？n测量、输入错误或系统运行错误所致n数据内在特性所决定n客体的异常行为所致客体的异常行为所致 由于离群点产生的机制是不确定的，离群点挖掘算法检测出的“离群点”是否真正对应实际的异常行为，不是由离群点挖掘算法来说明、解释的，只能由领域专家来解释，离群点挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。为什么会出现离群点？测量、输入错误或系统运行错误所致11离群点挖掘中需要处理的几个问题离群点挖掘中需要处理的几个问题n(1)全局观点和局部观点全局观点和局部观点离群点与众不同，但具有相对性。n(2)点的离群程度点的离群程度可以通过定义对象的偏离程度来给对象打分离群因子(Outlier Factor)或离群值得分(Outlier Score)，即都为离群点的情况下，也还有分高和分低的区别。n(3)离群点的数量及时效性离群点的数量及时效性正常点的数量远远超过离群点的数量，离群点的数量在大规模数据集中所占的比例较低，小于5%甚至1%离群点挖掘中需要处理的几个问题(1)全局观点和局部观点12离群点实例离群点实例n一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的；n一个公司的高层管理人员的工资明显高于普通员工的工资可能成为离群点但却是合理的数据(如平安保险公司2007年 5位高管税后收入超过了1000万元)；n一部住宅电话的话费由每月200元以内增加到数千元可能就因为被盗打或其它特殊原因所致；n一张信用卡出现明显的高额消费也许是因为是盗用的卡。离群点实例一个人的年龄为-999就可能是由于程序处理缺省数据13n离群点与众不同但具有离群点与众不同但具有相对性：相对性：高与矮，疯子与常人。n类似术语：类似术语：Outlier mining，Exception mining:异常挖掘、离群挖掘、例外挖掘和稀有事件挖掘。离群点与众不同但具有相对性：14离群点检测方法分类离群点检测方法分类离群点检测方法分类15从使用的主要技术路线角度分类从使用的主要技术路线角度分类n基于统计的方法基于统计的方法n基于距离的方法基于距离的方法n基于密度的方法基于密度的方法n基于聚类的方法基于聚类的方法n基于偏差的方法n基于深度的方法n基于小波变换的方法n基于神经网络的方法从使用的主要技术路线角度分类基于统计的方法16从类标号从类标号(正常或异常正常或异常)利用的程度分类利用的程度分类n无监督的离群点检测方法无监督的离群点检测方法q在实际情况下，没有提供类标号n有监督的离群点检测方法q要求存在离群点类和正常类的训练集n半监督的离群点检测方法q训练数据包含被标记的正常数据，但是没有关于离群点对象的信息 从类标号(正常或异常)利用的程度分类无监督的离群点检测方法17离群点检测中需要处理的问题离群点检测中需要处理的问题离群点检测中需要处理的问题18(1)用于定义离群点的属性个数用于定义离群点的属性个数n一个对象只有单个属性n一个对象具有多个属性：q可能某个属性异常，某个属性正常如：对于男生而言，身高1.6m，体重55kg，这个很正常；身高1.6m，体重75kg，这个有点离群；身高1.8m，体重75kg，基本正常。若对于女生，则三组值可能都不太正常。n所以，定义离群点需要指明如何使用多个属性的值确定一所以，定义离群点需要指明如何使用多个属性的值确定一个对象是否离群？个对象是否离群？(1)用于定义离群点的属性个数一个对象只有单个属性19(2)全局观点和局部观点全局观点和局部观点n一个对象可能相对于所有对象看上去离群，但它相对于它的局部近邻不是离群的q例如：身高1.85m对于一般人群是不常见的，但对于职业篮球运动员不算什么(2)全局观点和局部观点一个对象可能相对于所有对象看上去离群20实例：检测一元正态分布中的离群点6m，体重55kg，这个很正常；9:对OF2(x,k)降序排列，确定离群点得分高的若干对象例6-5 基于聚类的离群点检测示例1这个例子说明，当数据集包含不同密度的区域时，基于距离的离群点检测方法不能很好地识别离群点。假设数据集经过聚类后得到聚类结果为C=C1、C2、C3，图中红色圆圈标(1)检测结果对参数k的选择较敏感对基表中的数据，如选取科技人员职称和学历作为最终测试对象，因职称只有院士、正高、副高、讲师、助教和其它职称共六种职称，而学历只有高中以下、中专、大专、本科、硕士和博士共六种职称，职称和学历跨度小，检测出来的孤立点孤立程度相对较低，故选取跨度较大的出生年月作为测试对象。医学研究中发现医疗方案或药品所产生的异常反应解答：K取2，3，5时，所有点的局部邻域密度、相对密度、基于距离的离群因子表所示。表6-1显示当分布为N(0,1)时c的某些样本值和对应的值。一个公司的高层管理人员的工资明显高于普通员工的工资可能成为离群点但却是合理的数据(如平安保险公司2007年 5位高管税后收入超过了1000万元)；某些技术方法是以二元方式来报告对象是否离群点，即：离群点或正常点要求存在离群点类和正常类的训练集定义6-4(1)对象的局部邻域密度年龄=6,7,6,8,9,10,8,11,7,9,12,7,11,8,13,7,8,14,9,12可能是录入错误，可能是真实数据电信、保险、银行中的欺诈检测与风险分析(3)点的离群程度点的离群程度n某些技术方法是以二元方式来报告对象是否离群点，即：离群点或正常点q但，这不能反映某些对象比其他对象更加极端偏离的基本事实q通过定义对象的离群程度来给对象打分，如都为离群点的情况下，也还有分高和分低的区别。离群点得离群点得分分(outlier score)或离群因子或离群因子(Outlier Factor)实例：检测一元正态分布中的离群点(3)点的离群程度某些技术方21离群点检测的挑战和前提离群点检测的挑战和前提n挑战：q数据中有多少离群点?q方法应该是无监督的，就像在干草堆中寻找一根针n前提假设q假定数据集中被认为正常的点数远远超过被认为离群的点数离群点检测的挑战和前提挑战：22基于统计的离群点检测基于统计的离群点检测基于统计的离群点检测23基于统计的离群点检测n这类方法大部分是从针对不同分布的离群点检验方法发展起来的，通常用户使用分布来拟合数据集。q假定所给定的数据集存在一个分布或概率模型(例如，正态分布或泊松分布)，然后将与模型不一致(即分布不符合)的数据标识为离群数据。基于统计的离群点检测24基于统计的离群点检测n假定用一个参数模型来描述数据的分布(如正态分布)应用基于统计分布的离群点检测方法依赖于q数据分布q参数分布(如均值或方差)q期望离群点的数目 (置信度区间)基于统计的离群点检测假定用一个参数模型来描述数据的分布(如25离群点的概率定义离群点的概率定义n离群点的概率定义：q离群点是一个对象，关于数据的概率分布模型，它具有低概率n概率分布模型通过估计用户指定的分布的参数，由数据创建。q例：如果假定数据具有高斯分布，则基本分布的均值和标准差可以通过计算数据的均值和标准差来估计，然后可以估计每个对象在该分布下的概率。离群点的概率定义离群点的概率定义：26实例：检测一元正态分布中的离群点实例：检测一元正态分布中的离群点n下面利用统计学中最常用的分布-高斯(正态)分布，来介绍一种简单的统计学离群点检测方法。q正态分布用记号：N(，)表示，表示均值，表示方差。实例：检测一元正态分布中的离群点下面利用统计学中最常用的分布27cN(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个标准差的值出现的可能性是万分之一。实例：检测一元正态分布中的离群点实例：检测一元正态分布中的离群点cN(0,1)的10.31731.50.133620.04定义定义n定义 设属性x 取自具有均值0 和标准差1 的高斯分布。如果属性值x 满足：P(|x|c)=，其中c 是一个选定的常量，则x以概率1-为离群点。q为了使用该定义，需要指定值。从不寻常的值(对象)预示来自不同的值的观点来说，表示我们错误地将来自给定分布的值分类为离群点的概率。从离群点是N(0,1)分布的稀有值的观点来说，表示稀有程度。定义定义 设属性x 取自具有均值0 和标准差1 的高斯分布29n如果(正常对象的)一个感兴趣的属性的分布是具有均值和标准差的正态分布，即 分布，则可以通过变换z=(x-)/转换为标准正态分布N(0,1)，通常和是未知的，可以通过样本均值和样本标准差来估计。n实践中，当观测值很多时，这种估计的效果很好；另一方面，由概率统计中的大数定律可知，在大样本的情况下可以用正态分布近似其它分布。如果(正常对象的)一个感兴趣的属性的分布是具有均值和标准差30n在该图中，中心线是观测值的预测值，3 对应上下控制线，2对应上、下警告线。根据3原则，99.73%的观测值将落在上下控制线的区间内，仅有0.27%的观测值落在此区间之外。质量控制示意图+3xt-3-2+2在该图中，中心线是观测值的预测值，3 对应上31对于观测样本对于观测样本X：n(1)如此点在上、下警告线之间区域内,则测定过程处于控制状态，生产过程或样本分析结果有效；n(2)如果此点超出上、下警告线，但仍在上、下控制线之间的区域内，提示质量开始变劣，可能存在“失控”倾向,应进行初步检查，并采取相应的校正措施；n(3)若此点落在上、下控制线之外，表示生产或测定过程“失控，生产的是废品或观测样本无效。应立即检查原因，予以纠正。质量控制示意图t+3x-3-2+2对于观测样本X：质量控制示意图t+3x-3-232基于统计的离群点检测方法的优缺点基于统计的离群点检测方法的优缺点n优点：q离群点检测的统计学方法具有坚实的基础，建立在标准的统计学技术(如分布参数的估计)之上。q当存在充分的数据和所用的检验类型的知识时，这些检验可能非常有效。n缺点：q大部分统计方法是针对单个属性的，对于多元数据技术方法较少。q在许多情况下,数据分布是未知的。q对于高维数据,很难估计真实的分布。q这类方法不适合混合类型数据基于统计的离群点检测方法的优缺点优点：33基于距离的离群点检测基于距离的离群点检测基于距离的离群点检测34基于距离的离群基于距离的离群点检测检测n基于距离的离群点检测方法，其基本思想如下：q一个对象是离群的，如果它远离大部分其它对象。n优点：确定数据集的有意义的邻近性度量比确定它的统计分布更容易，综合了基于分布的思想，克服了基于分布方法的主要缺陷。基于距离的离群点检测基于距离的离群点检测方法，其基本思想如下35基于距离方法的两种不同策略基于距离方法的两种不同策略n第一种策略是采用给定邻域半径，依据点的邻域中包含的对象多少来判定离群点q如果一个点的邻域内包含的对象少于整个数据集的一定比例则标识它为离群点，也就是将没有足够邻居的对象看成是基于距离的离群点。n利用k最近邻距离的大小来判定离群q使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的离群程度由到它的k-最近邻的距离给定。q这种方法对k的取值比较敏感。k太小(例如1)，则少量的邻近离群点可能导致较低的离群程度。k太大，则点数少于k的簇中所有的对象可能都成了离群点。基于距离方法的两种不同策略第一种策略是采用给定邻域半径，依据36到到k-最近邻的距离的计算最近邻的距离的计算nk-最近邻的距离：q一个对象的离群点得分由到它的k-最近邻的距离给定。q离群点得分的最低值为0，最高值是距离函数的可能最大值-如无穷大定义6-2 对于正整数k，对象p的k最近邻距离k-distance(p)定义为:(1)除p外，至少有k个对象o满足(2)除p外，至多k-1个对象o满足到k-最近邻的距离的计算k-最近邻的距离：定义6-2 对于正372024/6/17定义6-3 点x的离群因子定义为：这里 是不包含x的k-最近邻的集合，是该集合的大小。2023/8/10定义6-3 点x的离群因子定义为：这里38 基于距离的离群点检测算法基于距离的离群点检测算法n输入：数据集D；最近邻个数kn输出：离群点对象列表n1：for all 对象x don2：确定x的k-最近邻集合N(x,k)n3：确定x的离群因子 OF1(x,k)n4：end forn5：对OF1(x,k)降序排列，确定离群因子大的若干对象n6：return应注意：x的k-最近邻的集 包含的对象数可能超过k。基于距离的离群点检测算法输入：数据集D；最近邻个数k39选择合适的离群因子阈值选择合适的离群因子阈值n一种形式上简单的方法是指定离群点个数；这里介绍另一种确定OF1(x,k)分割阈值的方法：对OF1(x,k)降序排列，选择OF1(x,k)急剧下降的点作为离群值、正常值的分隔点，如图6-3所示，在该图中，有两个点判定为离群点。选择合适的离群因子阈值一种形式上简单的方法是指定离群点个数；40例例6-1n例6-1 在图6-4所示的二维数据集中，当k=2时，P1、P2哪个点具有更高的离群点得分？(使用欧式距离)xy1213112122236824325752例6-1例6-1 在图6-4所示的二维数据集中，当k=2时，41例例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点更有可能是离群点。例6-1解答：42离群因子(Outlier Factor)定义为簇 其它所有簇间距离的加权平均值：可以通过下表所示混淆矩阵来描述离群点挖掘方法的检测性能。一张信用卡出现明显的高额消费也许是因为是盗用的卡。注，三个簇的质心分别为：C1(5.年龄=6,7,6,8,9,10,8,11,7,9,12,7,11,8,13,7,8,14,9,12用DS算法时，取M=20，算法返回距离的值最大的20个教师信息如表1所示。当存在充分的数据和所用的检验类型的知识时，这些检验可能非常有效。用建立的模型在P3上进行测试，检测率结果如下表。是该集合的大小。(1)对于P4，k最近邻邻域包含两个对象：可见簇C1的离群因子最大，其中包含的对象判第二阶段是计算每个簇的离群因子，并按离群因子对簇进行排序，最终确定离群簇，也即确定离群对象。簇内靠近核心点的对象的相对密度接近于1，而处于簇的边缘或是簇的外面的对象的相对较大。到k-最近邻的距离的计算应立即检查原因，予以纠正。对于测试集 中对象p，计算p与每个簇的距离 若 ，则说明p是已知类型的行为，将簇 的标识作为p的标识，否则说明p是一种新的行为，将p标识为可疑对象候选离群点。那么.选取三个指标:出生年月、学位和职称作为检测属性。离群因子(Outlier Factor)定义为簇 其它所有簇间距离的加权平均值：一张信用卡出现明显的高额消费也许是因为是盗用的卡。离群点检测的统计学方法具有坚实的基础，建立在标准的统计学技术(如分布参数的估计)之上。基于距离的离群点检测基于距离的离群点检测 例例6-2 在图在图6-5所示的二维数据集中，当所示的二维数据集中，当k=5时，哪个点具有时，哪个点具有最大的离群因子最大的离群因子,B的离群因子和的离群因子和D的离群因子哪个小？的离群因子哪个小？CDAB解答：图所示的二维数据集主体由解答：图所示的二维数据集主体由一个紧密的簇和一个松散的簇组成，一个紧密的簇和一个松散的簇组成，下图以灰度图显示了各点的离群因子下图以灰度图显示了各点的离群因子情况，情况，D的离群因子低于松散簇中部的离群因子低于松散簇中部分点的离群因子。点分点的离群因子。点C的离群因子最的离群因子最大，大，B点的离群因子大于点的离群因子大于D点的离群点的离群因子。这个例子说明，当数据集包含因子。这个例子说明，当数据集包含不同密度的区域时，基于距离的离群不同密度的区域时，基于距离的离群点检测方法不能很好地识别离群点。点检测方法不能很好地识别离群点。CDAB离群点得分递增离群因子(Outlier Factor)43基于距离的离群检测的优缺点基于距离的离群检测的优缺点n优点：优点：q基于距离的离群点检测方案简单 n缺点：缺点：q(1)检测结果对参数k的选择较敏感q(2)时间复杂度为 ，难以用于大规模数据集，这里n为数据集的规模；q(3)需要有关离群因子阈值或数据集中离群点个数的先验知识，在实际使用中有时由于先验知识的不足会造成一定的困难。q(4)因为它使用全局阈值，不能处理不同密度区域的数据集。基于距离的离群检测的优缺点优点：44基于相对密度的离群点检测基于相对密度的离群点检测基于相对密度的离群点检测452024/6/17基于密度的基于密度的离群点检测离群点检测 n当数据集含有多种分布或数据集由不同密度子集混合而成时，数据是否离群不仅仅取决于它与周围数据的距离大小，而且与邻域内的密度状况有关。n这里使用每个对象到第k个最近邻的距离大小来度量密度。2023/8/10基于密度的离群点检测 当数据集含有多种分布n定义6-4(1)对象的局部邻域密度 n(2)相对密度n其中，是不包含x的k-最近邻的集合，是该集合的大小，y是一个最近邻。基于相对密度的离群点检测方法通过比较对象的密度与它的邻域中的对象平均密度来检测离群点。簇内靠近核心点的对象的相对密度接近于1，而处于簇的边缘或是簇的外面的对象的相对较大。定义相对密度为离群因子：定义6-4(1)对象的局部邻域密度 基于相对密度47相对密度离群点检测算法相对密度离群点检测算法 n1：k是最近邻个数n2：for all 对象x don3：确定x的k-最近邻N(x,k)。n4：使用x的最近邻(即N(x,k)中的对象)，确定x的密度density(x,k)。n5：end forn6：for all 对象x don7：确定x的相对密度relative density(x,k)，并赋值给OF2(x,k)。n8：end for n9:对OF2(x,k)降序排列，确定离群点得分高的若干对象 相对密度离群点检测算法 1：k是最近邻个数48例例6-3：给定二维数据集，表：给定二维数据集，表6-2给出了点的坐标，可视化的给出了点的坐标，可视化的图形如图图形如图6-7所示所示(对象间的距离采用曼哈顿对象间的距离采用曼哈顿(Manhattan)距距离计算离计算)。n(1)取k=2，计算点P4，P15的局部邻域密度 及相对密度 ，哪个点更可能是离群点？n(2)取k=2，按照基于距离的离群点检测，P4，P15哪个点更可能是离群点？P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15P16X1 112222333344455Y2 341234123412301例6-3：给定二维数据集，表6-2给出了点的坐标，可视化的图49n(1)对于P4，k最近邻邻域包含两个对象：对于P15，k最近邻邻域包含2个对象：P12，P16的密度均为1，相对点相对点P4，点，点P15更可能是离群点。更可能是离群点。(1)对于P4，k最近邻邻域包含两个对象：对于P15，k50(2)对于k=2nP4的k最近邻邻域为 ，k最近邻距离均值为1。nP15的k最近邻邻域为 ，k最近邻距离均值为1.5。经过比较可以看出，点经过比较可以看出，点P15的离群程度要高。的离群程度要高。(2)对于k=251例例6-4 模拟图模拟图6-8中类似数据，中类似数据，K取取2，3，5时，以表格方式给出所有点时，以表格方式给出所有点的局部邻域密度及相对密度、基于距离的离群因子。的局部邻域密度及相对密度、基于距离的离群因子。(采用欧式距离采用欧式距离)n解答：K取2，3，5时，所有点的局部邻域密度、相对密度、基于距离的离群因子表所示。点的坐标k=2k=3k=5xy局部邻域密度相对密度距离离群因子局部邻域密度相对密度距离离群因子局部邻域密度相对密度距离离群因子45950.07 0.88 14.00 0.06 0.87 16.33 0.04 0.90 22.60 60960.05 1.34 20.50 0.04 1.15 22.33 0.04 1.11 27.00 51800.06 0.96 17.00 0.05 0.96 18.33 0.05 0.80 20.60 38900.08 0.91 13.00 0.06 0.94 16.33 0.04 0.96 23.80 39770.07 0.98 14.50 0.06 1.04 17.67 0.04 1.02 25.00 69790.04 1.21 22.50 0.04 1.33 25.67 0.03 1.35 31.80 1511690.13 1.39 8.00 0.13 1.16 8.00 0.10 1.07 9.80 1451630.13 1.56 8.00 0.11 1.40 9.33 0.09 1.27 11.40 1511560.14 1.36 7.00 0.12 1.20 8.67 0.10 1.09 10.40 1531630.17 1.04 6.00 0.15 0.87 6.67 0.14 0.76 7.40 1611540.12 1.11 8.50 0.09 1.49 11.33 0.07 1.49 13.60 1511610.22 0.70 4.50 0.18 0.70 5.67 0.14 0.76 7.40 1571670.13 1.17 8.00 0.11 1.40 9.33 0.09 1.24 11.20 1611590.12 1.44 8.50 0.10 1.20 9.67 0.09 1.14 10.80 1121860.02 7.00 56.00 0.02 7.99 58.67 0.02 6.68 60.80 502380.01 5.85 131.00 0.01 5.66 138.00 0.01 5.52 146.60 例6-4 模拟图6-8中类似数据，K取2，3，5时，以表格方52基于聚类的离群点检测基于聚类的离群点检测基于聚类的离群点检测532024/6/17基于聚类的离群点检测方法基于聚类的离群点检测方法 物以类聚物以类聚相似的对象聚合在一起。基于聚类的方法有两个共同特点：(1)先采用特殊的聚类算法处理输入数据而得到聚类，再在聚类的基础上来检测离群点。(2)只需要扫描数据集若干次，效率较高，适用于大规模数据集。2023/8/10基于聚类的离群点检测方法 物以类聚相似2024/6/17基于聚类的离群点检测方法基于聚类的离群点检测方法n静态数据的离群点检测q第一阶段对数据进行聚类q第二阶段计算对象或簇的离群因子，将离群因子大的对象或簇中对象判定为离群点。n动态数据的离群点检测q第一步，利用静态数据的离群检测方法建立离群检测模型q第二步，利用对象与已有模型间的相似程度来检测离群点关键问题：距离的定义、离群程度的度量2023/8/10基于聚类的离群点检测方法静态数据的离群点检基于对象离群因子的方法基于对象离群因子的方法n首先聚类所有对象，然后评估对象属于簇的程度q如果一个对象不强属于任何簇，则称该对象为基于聚类的离群点。q对于基于原型的聚类，可以用对象到它的簇中心的距离来度量对象属于簇的程度。基于对象离群因子的方法首先聚类所有对象，然后评估对象属于簇56基于对象离群因子的方法基于对象离群因子的方法n定义定义6-5 给定簇C，C的摘要信息CSI(Cluster Summary Information)定义为：其中n为簇C的大小，Summary由分类属性中不同取值的频度信息和数值属性的质心两部分构成，即：n定义定义6-6 假设据集D被聚类算法划分为k个簇 对象p的离群因子(Outlier Factor)OP3(p)定义为p与所有簇间距离的加权平均值：基于对象离群因子的方法定义6-5 给定簇C，C的摘要信息C57n引理引理 如果随机变量 服从正态分布 ，则有：引理 如果随机变量 服从正态分布 58两阶段离群点挖掘方法两阶段离群点挖掘方法TOD描述如下：描述如下：n第一步，对数据集D进行采用一趟聚类算法进行聚类，得到聚类结果n第二步，计算数据集D中所有对象p的离群因子OF3(p)，及其平均值Ave_OF和标准差Dev_OF，满足条件：的对象判定为离群点。通常取 两阶段离群点挖掘方法TOD描述如下：59例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)，试计算所有对象的离群因子。例6-5 基于聚类的离群点检测示例160例6-5 基于聚类的离群点检测示例1解答：根据定义6-6，公式对于P1点有：对于P2有：可见，点P1较P2更可能成为离群点。例6-5 基于聚类的离群点检测示例161例6-5 基于聚类的离群点检测示例1n同理可求得所有对象的离群因子，结果如表所示。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更有可能成为离群点。例6-5 基于聚类的离群点检测示例1xyOF3122.21362基于簇的离群因子的方法基于簇的离群因子的方法n(1)在某种度量下，相似对象或相同类型的对象会聚集在一起，或者说正常数据与离群数据会聚集在不同的簇中；n(2)正常数据占绝大部分，且离群数据与正常数据表现出明显不同，或者说离群数据会偏离正常数据(也就是大部分数据)。介绍簇的离群因子概念，利用簇的离群因子将簇区分为正常簇和离群簇。基于簇的离群因子的方法(1)在某种度量下，相似对象或相同类型63定义定义6-7n给定簇C，C的摘要信息CSI(Cluster Summary Information)定义为：其中kind为簇的类别(取值normal或outlier)，为簇C的大小,Cluster为簇C中对象标识的集合，Summary由分类属性中不同取值的频度信息和数值型属性的质心两部分构成，即：定义6-7给定簇C，C的摘要信息CSI(Cluster S64定义定义6-8n假设据集D被聚类算法划分为k个簇 ，簇 离群因子(Outlier Factor)定义为簇 其它所有簇间距离的加权平均值：如果一个簇离几个大簇的距离都比较远，则表明该簇偏离整体较远，其离群因子也较大。度量了簇 偏离整个数据集的程度，其值越大，说明 偏离整体越远。定义6-8假设据集D被聚类算法划分为k个簇 65基于聚类的离群挖掘方法基于聚类的离群挖掘方法(CBOD)nCBOD方法由两个阶段构成：q第一阶段是利用一趟聚类算法对数据集进行聚类；q第二阶段是计算每个簇的离群因子，并按离群因子对簇进行排序，最终确定离群簇，也即确定离群对象。基于聚类的离群挖掘方法(CBOD)CBOD方法由两个阶段构成66CBOD算法描述如下：算法描述如下：n第一阶段，聚类：对数据集D进行聚类，得到聚类结果 ；n第二阶段，确定离群簇：计算每个簇 的离群因子 ，按 递减的顺序重新排列 ，求满足：的最小 ，将簇 标识为outlier类(即其中每个对象均看成离群)，而将 标识为normal类(即其中每个对象均看成正常)。CBOD算法描述如下：第一阶段，聚类：对数据集D进行聚类，得67例例6-6 基于聚类的离群点检测示例基于聚类的离群点检测示例2对例6-5中的数据集，聚类后得到三个簇C=C1、C2、C3，簇心分别为：C1(5.5,7.5)、C2(5,2)、C3(1.75,2.25)。簇之间的距离分别为进一步计算三个簇的离群因子，具体如下：例6-6 基于聚类的离群点检测示例2对例6-5中的数据集，聚68例例6-6 基于聚类的离群点检测示例基于聚类的离群点检测示例2可见簇C1的离群因子最大，其中包含的对象判定为离群点，与例6-5得到的结论相同。例6-6 基于聚类的离群点检测示例269基于聚类的动态数据的离群点检测基于聚类的动态数据的离群点检测 基本思想如下：基本思想如下：在对训练集聚类的基础上，按照簇的离群因子排序簇，并按一定比例将簇标识为”normal”或”outlier”，以标识的簇作为分类模型，按照对象与分类模型中最接近簇的距离判断它是否离群点。基于聚类的动态数据的离群点检测 基本思想如下：在对训练集70基于聚类的动态数据的离群点检测基于聚类的动态数据的离群点检测n第一步，聚类：对训练集 进行聚类，得到聚类结果 ；n第二步，给簇作标记：计算每个簇 的离群因子 ，按 递减的顺序重新排列 ，求满足：的最小b，将簇 标识为离群簇，而将 标识为正常簇。n第三步，确定模型：以每个簇的摘要信息，聚类半径阈值r作为模型。(1)模型建立模型建立基于聚类的动态数据的离群点检测(1)模型建立71(2)模型评估模型评估n利用改进的最近邻分类方法INN(Improved Nearest Neighbor)评估测试集中的每个对象。INN方法具体描述如下：q对于测试集 中对象p，计算p与每个簇的距离 若 ，则说明p是已知类型的行为，将簇 的标识作为p的标识，否则说明p是一种新的行为，将p标识为可疑对象候选离群点。(2)模型评估利用改进的最近邻分类方法INN(Improv72(3)模型更新模型更新n对于测试集 中对象p，按照前面聚类的方式，对新增对象进行增量式聚类更新n用建立模型同样的方法对所有簇重新标记其类别。(3)模型更新对于测试集 中对象p，按照前面聚类的方736.6 离群点挖掘方法的评估离群点挖掘方法的评估可以通过下表所示混淆矩阵来描述离群点挖掘方法的检测性能。在离群点检测问题中，并不关注预测正确的normal类对象，重点关注的是正确预测的outlier类对象。预测类别outliernormal实际类别outlier预测正确的outlier预测错误的outliernormal预测错误的normal预测正确的normal6.6 离群点挖掘方法的评估可以通过下表所示混淆矩阵来描述74离群点检测方法准确性的两个指标两个指标n检测率(Detection rate)表示被正确检测的离群点记录数占整个离群点记录数的比例；n误报率(False positive rate)表示正常记录被检测为离群点记录数占整个正常记录数的比例。n期望离群点挖掘方法对离群数据有高的检测率，对正常数据有低的误报率，但两个指标之间会有一些冲突，高的检测率常常会导致高的误报率。也可以采用ROC曲线来显示检测率和误报率之间关系离群点检测方法准确性的两个指标检测率(Detection r75例例6-7 采用基于聚类的离群点挖掘方法处理采用基于聚类的离群点挖掘方法处理UCI中中KDDCUP99 数据集数据集n入侵检测问题可以看成一类特殊的离群点挖掘问题。nKDDCUP99数据集包含了约4900000条攻击记录。总共22种攻击，分为DOS，R2L，U2R，Probing等4类；总共有41个特征，其中9个分类特征，32个数值型特征。整个数据集太大，通常使用一个10%的子集来测试算法的性能；这个子集随机分割为P1，P2和P3三个子集，其中P1含40459条记录(normal占96%)，P2含19799条记录(normal占98.7%)。P3中包含有P1中没有出现过的ftpwrite，guess_passwd，imap，land，loadmodule，multihop，perl，phf，pod，rootkit，spy，warezmaster等攻击类型。例6-7 采用基于聚类的离群点挖掘方法处理UCI中KDDCU76(1)模型建立n以P1为训练集建立模型(取 =0.05)，求得EX=0.234，DX=0.134，r取EX+0.5DX=0.30。表6-6给出了按离群因子给P1聚类结果簇标识的结果，可见，聚类较好地将normal记录和attack记录划分到不同簇中，簇的离群因子能很好地将簇区分为”normal”和”outlier”(即对应于攻击记录)，使得建立的模型具有很好的分类能力。序号 簇大小正常记录数攻击记录数簇标识13600360outlier2505outlier394094outlier413392031136outlier5213421340normal6240824053normal7761normal816160normal91321302normal1015150normal1119181normal121711710normal13544254402normal14226182260711normal15389638960normal1661610normal17174217366normal从静态离群点检测的角度看，对于数据集P1，利用离群因子可以检测P1中98.4%的攻击记录。(1)模型建立以P1为训练集建立模型(取 =0.05)77(2)模型检验用建立的模型在P3上进行测试，检测率结果如下表。表在KDDCUP99数据集上的检测性能总的的检测率率误报率率对未未见攻攻击的的检测率率98.62%0.20%4.30%(2)模型检验用建立的模型在P3上进行测试，检测率结果如下78(3)模型更新效果在P1上建立模型，然后用P2更新模型，再在P3上检测。表6-8结果表明随着模型的更新(也就是有效信息的不断增加)，检测率和误报率没有明显变化，但对未见攻击的检测率明显提高。如果初始建模时训练集不够大，检测准确性将会随着模型的更新而逐步提高，直到稳定在某个水平总的检测率误报率对未见攻击的检测率98.47%0.12%34.30%(3)模型更新效果在P1上建立模型，然后用P2更新模型，79