数据挖掘——第九章离群点挖掘ppt课件.ppt
2022/11/12,离群点挖掘,主要内容,离群点挖掘的概述离群点数据挖掘方法简介基于统计的方法基于距离的方法基于密度的方法基于聚类的方法,什么是离群点(Outlier)？,Hawkins的定义：离群点是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。Weisberg的定义：离群点是与数据集中其余部分不服从相同统计模型的数据。Samuels的定义：离群点是足够地不同于数据集中其余部分的数据。Porkess的定义：离群点是远离数据集中其余部分的数据,离群点的特殊意义和实用价值,现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中，离群点通常作为噪音而忽略，许多数据挖掘算法试图降低或消除离群点的影响。而在有些应用领域识别离群点是许多工作的基础和前提，离群点会带给我们新的视角。 如在欺诈检测中，离群点可能意味欺诈行为的发生，在入侵检测中离群点可能意味入侵行为的发生。,实例：例如我们设儿童上学的具体年龄总体服从正态分布，所给的数据集是某地区随机选取的开始上学的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的孩子可能是个例外。而且由均值可知，此地的孩子普遍上学较晚.教育部门以后可据此作一些政策上的改进。,案例：孤立点挖掘在高等学校科技统计数据分析中的应用 孤立点实验数据源：（选自全国普通高等学校科技统计数据上报基表中的数据） 甘肃省2010年科技统计上报数据中的一所高校数据 对基表中的数据，如选取科技人员职称和学历作为最终测试对象，因职称只有院士、正高、副高、讲师、助教和其它职称共六种职称，而学历只有高中以下、中专、大专、本科、硕士和博士共六种职称，职称和学历跨度小，检测出来的孤立点孤立程度相对较低，故选取跨度较大的出生年月作为测试对象。选取三个指标:出生年月、学位和职称作为检测属性。,实验及结果分析 用DS算法时，取M=20，算法返回距离的值最大的20个教师信息如表1所示。 通过分析，可以发现孤立点数据中存在两种典型的孤立点类别： (1)孤立点数据远远偏离于正常值的范围 序号1-4 （噪声） (2)孤立点数据偏离于正常值的范围 可能是录入错误，可能是真实数据,离群点检测的应用领域,电信、保险、银行中的欺诈检测与风险分析 发现电子商务中的犯罪行为灾害气象预报税务局分析不同团体交所得税的记录，发现异常模型和趋势 海关、民航等安检部门推断哪些人可能有嫌疑 海关报关中的价格隐瞒营销定制：分析花费较小和较高顾客的消费行为医学研究中发现医疗方案或药品所产生的异常反应计算机中的入侵检测应用异常检测到文本编辑器，可有效减少文字输入的错误 ,离群点挖掘(Outlier mining),离群点挖掘问题由两个子问题构成：。 (1)定义在一个数据集中什么数据是不一致或离群的数据；(2)找出所定义的离群点的有效挖掘方法。离群点挖掘问题可以概括为如何度量数据偏离的程度和有效发现离群点的问题。,为什么会出现离群点？,测量、输入错误或系统运行错误所致数据内在特性所决定客体的异常行为所致 由于离群点产生的机制是不确定的，离群点挖掘算法检测出的“离群点”是否真正对应实际的异常行为，不是由离群点挖掘算法来说明、解释的，只能由领域专家来解释，离群点挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。,离群点挖掘中需要处理的几个问题,(1) 全局观点和局部观点离群点与众不同，但具有相对性。(2) 点的离群程度可以通过定义对象的偏离程度来给对象打分离群因子(Outlier Factor)或离群值得分(Outlier Score)，即都为离群点的情况下，也还有分高和分低的区别。(3) 离群点的数量及时效性正常点的数量远远超过离群点的数量，离群点的数量在大规模数据集中所占的比例较低，小于5%甚至1%,离群点实例,一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的 ；一个公司的高层管理人员的工资明显高于普通员工的工资可能成为离群点但却是合理的数据(如平安保险公司2007年 5位高管税后收入超过了1000万元)； 一部住宅电话的话费由每月200元以内增加到数千元可能就因为被盗打或其它特殊原因所致； 一张信用卡出现明显的高额消费也许是因为是盗用的卡。,离群点与众不同但具有相对性： 高与矮，疯子与常人。类似术语： Outlier mining，Exception mining:异常挖掘、离群挖掘、例外挖掘和稀有事件挖掘 。,离群点检测方法分类,从使用的主要技术路线角度分类,基于统计的方法基于距离的方法基于密度的方法基于聚类的方法基于偏差的方法基于深度的方法基于小波变换的方法基于神经网络的方法,从类标号(正常或异常)利用的程度分类,无监督的离群点检测方法在实际情况下，没有提供类标号有监督的离群点检测方法要求存在离群点类和正常类的训练集半监督的离群点检测方法训练数据包含被标记的正常数据，但是没有关于离群点对象的信息,离群点检测中需要处理的问题,(1)用于定义离群点的属性个数,一个对象只有单个属性一个对象具有多个属性：可能某个属性异常，某个属性正常如：对于男生而言， 身高1.6m，体重55kg，这个很正常； 身高1.6m，体重75kg，这个有点离群； 身高1.8m，体重75kg，基本正常。若对于女生，则三组值可能都不太正常。 所以，定义离群点需要指明如何使用多个属性的值确定一个对象是否离群？,(2)全局观点和局部观点,一个对象可能相对于所有对象看上去离群，但它相对于它的局部近邻不是离群的例如：身高1.85m对于一般人群是不常见的，但对于职业篮球运动员不算什么,(3)点的离群程度,某些技术方法是以二元方式来报告对象是否离群点，即：离群点或正常点但，这不能反映某些对象比其他对象更加极端偏离的基本事实通过定义对象的离群程度来给对象打分 ，如都为离群点的情况下，也还有分高和分低的区别。离群点得分(outlier score)或离群因子(Outlier Factor),离群点检测的挑战和前提,挑战：数据中有多少离群点?方法应该是无监督的，就像在干草堆中寻找一根针前提假设假定数据集中被认为正常的点数远远超过被认为离群的点数,基于统计的离群点检测,基于统计的离群点检测,这类方法大部分是从针对不同分布的离群点检验方法发展起来的，通常用户使用分布来拟合数据集。假定所给定的数据集存在一个分布或概率模型(例如，正态分布或泊松分布)，然后将与模型不一致(即分布不符合)的数据标识为离群数据。,基于统计的离群点检测,假定用一个参数模型来描述数据的分布 (如正态分布)应用基于统计分布的离群点检测方法依赖于数据分布参数分布 (如均值或方差)期望离群点的数目 (置信度区间),离群点的概率定义,离群点的概率定义：离群点是一个对象，关于数据的概率分布模型，它具有低概率概率分布模型通过估计用户指定的分布的参数，由数据创建。例：如果假定数据具有高斯分布，则基本分布的均值和标准差可以通过计算数据的均值和标准差来估计，然后可以估计每个对象在该分布下的概率。,实例：检测一元正态分布中的离群点,下面利用统计学中最常用的分布-高斯(正态)分布，来介绍一种简单的统计学离群点检测方法。正态分布用记号：N (，)表示，表示均值，表示方差。,来自N(0,1)分布的对象(值)出现在分布尾部的机会很小。例如，对象落在 3标准差的中心区域以外的概率仅有0.0027。更一般地，如果x是属性值，则|x|=c的概率随c增加而迅速减小。设= p (|x| c)。表6-1显示当分布为N(0,1)时c的某些样本值和对应的值。注意：离群值超过4个标准差的值出现的可能性是万分之一。,实例：检测一元正态分布中的离群点,定义,定义 设属性x 取自具有均值0 和标准差1 的高斯分布。如果属性值x 满足： P(|x|c)=，其中c 是一个选定的常量，则x以概率1-为离群点。 为了使用该定义，需要指定值。从不寻常的值(对象)预示来自不同的值的观点来说，表示我们错误地将来自给定分布的值分类为离群点的概率。从离群点是N(0,1)分布的稀有值的观点来说，表示稀有程度。,如果(正常对象的)一个感兴趣的属性的分布是具有均值和标准差的正态分布，即 分布，则可以通过变换z=(x-)/转换为标准正态分布N(0,1)，通常和是未知的，可以通过样本均值和样本标准差来估计。实践中，当观测值很多时，这种估计的效果很好；另一方面，由概率统计中的大数定律可知，在大样本的情况下可以用正态分布近似其它分布。,在该图中， 中心线是观测值的预测值， 3 对应上下控制线， 2对应上、下警告线。根据3原则，99.73%的观测值将落在上下控制线的区间内，仅有0.27%的观测值落在此区间之外。,质量控制示意图,对于观测样本X：(1)如此点在上、下警告线之间区域内,则测定过程处于控制状态，生产过程或样本分析结果有效；(2)如果此点超出上、下警告线，但仍在上、下控制线之间的区域内，提示质量开始变劣，可能存在“失控”倾向,应进行初步检查，并采取相应的校正措施；(3)若此点落在上、下控制线之外，表示生产或测定过程“失控，生产的是废品或观测样本无效。应立即检查原因，予以纠正。,质量控制示意图,基于统计的离群点检测方法的优缺点,优点：离群点检测的统计学方法具有坚实的基础，建立在标准的统计学技术(如分布参数的估计)之上。当存在充分的数据和所用的检验类型的知识时，这些检验可能非常有效。缺点：大部分统计方法是针对单个属性的，对于多元数据技术方法较少。在许多情况下, 数据分布是未知的。对于高维数据, 很难估计真实的分布。这类方法不适合混合类型数据,基于距离的离群点检测,基于距离的离群点检测,基于距离的离群点检测方法，其基本思想如下：一个对象是离群的，如果它远离大部分其它对象。优点：确定数据集的有意义的邻近性度量比确定它的统计分布更容易，综合了基于分布的思想，克服了基于分布方法的主要缺陷 。,基于距离方法的两种不同策略,第一种策略是采用给定邻域半径，依据点的邻域中包含的对象多少来判定离群点如果一个点的邻域内包含的对象少于整个数据集的一定比例则标识它为离群点，也就是将没有足够邻居的对象看成是基于距离的离群点。利用k最近邻距离的大小来判定离群使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的离群程度由到它的k-最近邻的距离给定 。这种方法对k的取值比较敏感。k太小(例如1)，则少量的邻近离群点可能导致较低的离群程度。k太大，则点数少于k的簇中所有的对象可能都成了离群点。,到k-最近邻的距离的计算,k-最近邻的距离：一个对象的离群点得分由到它的k-最近邻的距离给定。离群点得分的最低值为0，最高值是距离函数的可能最大值-如无穷大,定义6-2 对于正整数k，对象p的k最近邻距离k-distance(p)定义为:(1)除p外，至少有k个对象o满足 (2)除p外，至多k-1个对象o满足,2022/11/12,定义6-3 点x的离群因子定义为：,这里 是不包含x的k-最近邻的集合， 是该集合的大小。,基于距离的离群点检测算法,输入：数据集D；最近邻个数k输出：离群点对象列表1：for all 对象x do2： 确定x的k-最近邻集合N(x,k)3： 确定x的离群因子 OF1(x,k)4：end for5：对OF1(x,k)降序排列，确定离群因子大的若干对象6：return应注意：x的k-最近邻的集 包含的对象数可能超过k。,选择合适的离群因子阈值,一种形式上简单的方法是指定离群点个数；这里介绍另一种确定OF1(x,k)分割阈值的方法：对OF1(x,k)降序排列，选择OF1(x,k)急剧下降的点作为离群值、正常值的分隔点，如图6-3所示，在该图中，有两个点判定为离群点。,例6-1,例6-1 在图6-4所示的二维数据集中，当k=2时，P1、P2哪个点具有更高的离群点得分？(使用欧式距离),例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-2 在图6-5所示的二维数据集中，当k=5时，哪个点具有最大的离群因子,B的离群因子和D的离群因子哪个小？,解答：图所示的二维数据集主体由一个紧密的簇和一个松散的簇组成，下图以灰度图显示了各点的离群因子情况，D的离群因子低于松散簇中部分点的离群因子。点C的离群因子最大，B点的离群因子大于D点的离群因子。这个例子说明，当数据集包含不同密度的区域时，基于距离的离群点检测方法不能很好地识别离群点。,基于距离的离群检测的优缺点,优点：基于距离的离群点检测方案简单 缺点：(1) 检测结果对参数k的选择较敏感(2)时间复杂度为 ，难以用于大规模数据集，这里n为数据集的规模；(3)需要有关离群因子阈值或数据集中离群点个数的先验知识，在实际使用中有时由于先验知识的不足会造成一定的困难。(4) 因为它使用全局阈值，不能处理不同密度区域的数据集。,基于相对密度的离群点检测,2022/11/12,基于密度的离群点检测,当数据集含有多种分布或数据集由不同密度子集混合而成时，数据是否离群不仅仅取决于它与周围数据的距离大小，而且与邻域内的密度状况有关。这里使用每个对象到第k个最近邻的距离大小来度量密度。,定义6-4 (1) 对象的局部邻域密度 (2) 相对密度其中， 是不包含x的k-最近邻的集合， 是该集合的大小，y是一个最近邻。,基于相对密度的离群点检测方法通过比较对象的密度与它的邻域中的对象平均密度来检测离群点。 簇内靠近核心点的对象的相对密度接近于1，而处于簇的边缘或是簇的外面的对象的相对较大。定义相对密度为离群因子：,相对密度离群点检测算法,1：k是最近邻个数2：for all 对象x do3： 确定x的k-最近邻N(x,k)。4： 使用x的最近邻(即N(x,k)中的对象)， 确定x的密度density(x,k)。5：end for6：for all 对象x do7： 确定x的相对密度relative density(x,k)， 并赋值给OF2(x,k)。8：end for 9:对OF2(x,k)降序排列，确定离群点得分高的若干对象,例6-3：给定二维数据集，表6-2给出了点的坐标，可视化的图形如图6-7所示(对象间的距离采用曼哈顿(Manhattan)距离计算)。,(1)取k=2，计算点P4， P15的局部邻域密度 及相对密度 ，哪个点更可能是离群点？ (2)取k=2，按照基于距离的离群点检测，P4， P15哪个点更可能是离群点？,(1) 对于P4，k最近邻邻域包含两个对象：,对于P15，k最近邻邻域包含2个对象：,P12，P16的密度均为1，,相对点P4，点P15更可能是离群点。,(2)对于k=2P4的k最近邻邻域为 ，k最近邻距离均值为1。P15的k最近邻邻域为 ，k最近邻距离均值为1.5。经过比较可以看出，点P15的离群程度要高。,例6-4 模拟图6-8中类似数据，K取2，3，5时，以表格方式给出所有点的局部邻域密度及相对密度、基于距离的离群因子。(采用欧式距离),解答：K取2，3，5时，所有点的局部邻域密度、相对密度、基于距离的离群因子表所示。,基于聚类的离群点检测,2022/11/12,基于聚类的离群点检测方法,物以类聚相似的对象聚合在一起。 基于聚类的方法有两个共同特点： (1)先采用特殊的聚类算法处理输入数据而得到聚类，再在聚类的基础上来检测离群点。 (2)只需要扫描数据集若干次，效率较高，适用于大规模数据集。,2022/11/12,基于聚类的离群点检测方法,静态数据的离群点检测第一阶段对数据进行聚类第二阶段计算对象或簇的离群因子，将离群因子大的对象或簇中对象判定为离群点。动态数据的离群点检测第一步，利用静态数据的离群检测方法建立离群检测模型第二步，利用对象与已有模型间的相似程度来检测离群点关键问题：距离的定义、离群程度的度量,基于对象离群因子的方法,首先聚类所有对象 ，然后评估对象属于簇的程度如果一个对象不强属于任何簇，则称该对象为基于聚类的离群点。对于基于原型的聚类，可以用对象到它的簇中心的距离来度量对象属于簇的程度。,基于对象离群因子的方法,定义6-5 给定簇C，C的摘要信息CSI(Cluster Summary Information)定义为： 其中n为簇C的大小，Summary由分类属性中不同取值的频度信息和数值属性的质心两部分构成，即：定义6-6 假设据集D被聚类算法划分为k个簇 对象p的离群因子(Outlier Factor)OP3(p)定义为p与所有簇间距离的加权平均值：,引理 如果随机变量 服从正态分布 ，则有：,两阶段离群点挖掘方法TOD描述如下：第一步，对数据集D进行采用一趟聚类算法进行聚类，得到聚类结果第二步，计算数据集D中所有对象p的离群因子OF3(p)，及其平均值Ave_OF和标准差Dev_OF，满足条件： 的对象判定为离群点。 通常取,例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 基于聚类的离群点检测示例1解答：根据定义6-6，公式对于P1点有： 对于P2有：可见，点P1较P2更可能成为离群点。,例6-5 基于聚类的离群点检测示例1同理可求得所有对象的离群因子，结果如表所示。,进一步求得所有点的离群因子平均值Ave_OF=2.95，标准差Dev_OF=1.3，假设 ；则阈值E=Ave_OF + *Dev_OF=2.95+1.3=4.25离群因子大于4.25的对象可视为离群点，P1 与P2都是离群点，但相对而言，P1更有可能成为离群点。,基于簇的离群因子的方法,(1)在某种度量下，相似对象或相同类型的对象会聚集在一起，或者说正常数据与离群数据会聚集在不同的簇中；(2)正常数据占绝大部分，且离群数据与正常数据表现出明显不同，或者说离群数据会偏离正常数据(也就是大部分数据)。 介绍簇的离群因子概念，利用簇的离群因子将簇区分为正常簇和离群簇。,定义6-7,给定簇C，C的摘要信息CSI (Cluster Summary Information)定义为： 其中kind为簇的类别(取值normal或outlier)， 为簇C的大小, Cluster为簇C中对象标识的集合，Summary由分类属性中不同取值的频度信息和数值型属性的质心两部分构成，即：,定义6-8,假设据集D被聚类算法划分为k个簇 ，簇 离群因子(Outlier Factor) 定义为簇 其它所有簇间距离的加权平均值：,如果一个簇离几个大簇的距离都比较远，则表明该簇偏离整体较远，其离群因子也较大。 度量了簇 偏离整个数据集的程度，其值越大，说明 偏离整体越远。,基于聚类的离群挖掘方法(CBOD),CBOD方法由两个阶段构成：第一阶段是利用一趟聚类算法对数据集进行聚类；第二阶段是计算每个簇的离群因子，并按离群因子对簇进行排序，最终确定离群簇，也即确定离群对象。,CBOD算法描述如下：,第一阶段，聚类：对数据集D进行聚类，得到聚类结果 ；第二阶段，确定离群簇：计算每个簇 的离群因子 ，按 递减的顺序重新排列 ，求满足： 的最小 ，将簇 标识为outlier类(即其中每个对象均看成离群)，而将 标识为normal类(即其中每个对象均看成正常)。,例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,可见簇C1的离群因子最大，其中包含的对象判定为离群点，与例6-5得到的结论相同。,基于聚类的动态数据的离群点检测 基本思想如下：,在对训练集聚类的基础上，按照簇的离群因子排序簇，并按一定比例将簇标识为”normal”或”outlier”，以标识的簇作为分类模型，按照对象与分类模型中最接近簇的距离判断它是否离群点。,基于聚类的动态数据的离群点检测,第一步，聚类：对训练集 进行聚类，得到聚类结果 ；第二步，给簇作标记：计算每个簇 的离群因子 ，按 递减的顺序重新排列 ，求满足： 的最小b，将簇 标识为离群簇，而将 标识为正常簇。第三步，确定模型：以每个簇的摘要信息，聚类半径阈值r作为模型。,(1) 模型建立,(2) 模型评估,利用改进的最近邻分类方法INN(Improved Nearest Neighbor) 评估测试集中的每个对象。INN方法具体描述如下：对于测试集 中对象p，计算p与每个簇的距离 若 ，则说明p是已知类型的行为，将簇 的标识作为p的标识，否则说明p是一种新的行为，将p标识为可疑对象候选离群点 。,(3) 模型更新,对于测试集 中对象p，按照前面聚类的方式，对新增对象进行增量式聚类更新用建立模型同样的方法对所有簇重新标记其类别。,6.6 离群点挖掘方法的评估,可以通过下表所示混淆矩阵来描述离群点挖掘方法的检测性能。在离群点检测问题中，并不关注预测正确的normal类对象，重点关注的是正确预测的outlier类对象。,离群点检测方法准确性的两个指标,检测率(Detection rate)表示被正确检测的离群点记录数占整个离群点记录数的比例；误报率(False positive rate)表示正常记录被检测为离群点记录数占整个正常记录数的比例。期望离群点挖掘方法对离群数据有高的检测率，对正常数据有低的误报率，但两个指标之间会有一些冲突，高的检测率常常会导致高的误报率。也可以采用ROC曲线来显示检测率和误报率之间关系,例6-7 采用基于聚类的离群点挖掘方法处理UCI中KDDCUP99 数据集,入侵检测问题可以看成一类特殊的离群点挖掘问题。KDDCUP99数据集包含了约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等攻击类型。,(1)模型建立,以P1为训练集建立模型(取 =0.05)，求得EX=0.234，DX=0.134， r取EX+0.5DX=0.30。表6-6给出了按离群因子给P1聚类结果簇标识的结果，可见，聚类较好地将normal记录和attack记录划分到不同簇中，簇的离群因子能很好地将簇区分为”normal”和” outlier”(即对应于攻击记录)，使得建立的模型具有很好的分类能力。,从静态离群点检测的角度看，对于数据集P1，利用离群因子可以检测P1中98.4%的攻击记录。,(2) 模型检验,用建立的模型在P3上进行测试，检测率结果如下表。表在KDDCUP99数据集上的检测性能,(3) 模型更新效果,在P1上建立模型，然后用P2更新模型，再在P3上检测。表6-8结果表明随着模型的更新(也就是有效信息的不断增加)，检测率和误报率没有明显变化，但对未见攻击的检测率明显提高。如果初始建模时训练集不够大，检测准确性将会随着模型的更新而逐步提高，直到稳定在某个水平,本章小结,(1) 介绍了离群点概念及离群点挖掘的意义 (2) 从技术的角度介绍了离群点挖掘的几种常用方法：基于统计的方法、基于距离的方法、基于相对密度和基于聚类的方法，对这几种方法的优劣进行了分析。并通过实例说明了这些离群点检测方法的应用。,作业:,
