离群点挖掘分析课件

商务数据挖掘与应用案例分析商务数据挖掘与应用案例分析第6章离群点挖掘

6.1概述>>

6.2基于相对密度的离群点检测方法>>

6.3基于聚类的离群点检测方法>>6.4离群点检测方法的评估>>

第6章离群点挖掘6.1概述>>开篇案例——保险欺诈检验随着保险业的蓬勃发展，保险欺诈现象也越来越严重。有关统计数据显示，国际上某些险种因被欺诈而导致的赔款支出最高可达保险费收入的50％。从所发生的保险欺诈案例看，手段无所不用且花样翻新，有的虚构或者伪造索赔，人寿保险中常见的是移花接木、冒名顶替，或者自演自导一幕幕自残的苦肉计，更恶劣的还有杀亲骗保者，财产保险中，诸如故意沉船、故意纵火等骗赔伎俩，五花八门。愈演愈烈的保险欺诈违法犯罪活动，不仅极大地损害了保险合同当事人的合法权益，而且还严重扰乱了保险市场的正常秩序。一方面他对保险公司的财产构成了直接的侵犯；另一方面，保险公司面对保险欺诈不得不提高保费，这样，诚实的投保人成为最大的损失者，这将会严重阻碍保险业的发展。在人寿保险业务中，一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作地址、工资水平、索赔次数等等。我们主要想通过数据挖掘找出行为异常的客户记录。我们主要关注购买人的年龄、工作单位、健康状况、工资水平的信息和购买后的索赔情况，可以认为保单号、单位代号、单位名称是一些无关信息。这种人寿保险公司通过分析客户信息识别保险中的欺诈特征就是离群点检测方法研究的问题。数据挖掘中的多数方法都会将异常数据视为噪音或异常而丢弃。而离群点检验在激增的客户信息和业务数据中寻找异常数据，并进行更深层次的分析。这些异常数据与数据的一般行为或模型不一致，发生的概率非常小。但在保险欺诈检验中，小概率事件可能比正常发生的事件更有意义。因此，通过离群点检验将客户信息进行细致的分类挖掘，寻找欺诈的一般特征，并建立客户分析预测模型，对具有欺诈特征的客户群体实施相应的措施，以提高公司的反欺诈能力。开篇案例——保险欺诈检验随着保险业的蓬勃发展，保险欺诈现象也6.1概述(1)什么是离群点(Outlier)？Hawkins的定义：离群点是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。Weisberg的定义：离群点是与数据集中其余部分不服从相同统计模型的数据。Samuels的定义：离群点是足够地不同于数据集中其余部分的数据。Porkess的定义：离群点是远离数据集中其余部分的数据6.1概述(1)什么是离群点(Outlier)？离群点的特殊意义和实用价值现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中，离群点通常作为噪音而忽略，许多数据挖掘算法试图降低或消除离群点的影响。而在有些应用领域识别离群点是许多工作的基础和前提，离群点会带给我们新的视角。如在欺诈检测中，离群点可能意味欺诈行为的发生，在入侵检测中离群点可能意味入侵行为的发生。6.1概述(2)离群点的特殊意义和实用价值6.1概述(2)离群点检测的应用领域电信、保险、银行中的欺诈检测与风险分析发现电子商务中的犯罪行为灾害气象预报税务局分析不同团体交所得税的记录，发现异常模型和趋势海关、民航等安检部门推断哪些人可能有嫌疑海关报关中的价格隐瞒营销定制：分析花费较小和较高顾客的消费行为医学研究中发现医疗方案或药品所产生的异常反应计算机中的入侵检测应用异常检测到文本编辑器，可有效减少文字输入的错误……6.1概述(3)离群点检测的应用领域6.1概述(3)离群点挖掘问题由两个子问题构成：(1)定义在一个数据集中什么数据是不一致或离群的数据；(2)找出所定义的离群点的有效挖掘方法。离群点挖掘问题可以概括为如何度量数据偏离的程度和有效发现离群点的问题。为什么会出现离群点？测量、输入错误或系统运行错误所致数据内在特性所决定客体的异常行为所致由于离群点产生的机制是不确定的，离群点挖掘算法检测出的“离群点”是否真正对应实际的异常行为，不是由离群点挖掘算法来说明、解释的，只能由领域专家来解释，离群点挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。6.1概述(4)离群点挖掘问题由两个子问题构成：6.1概述(4)离群点挖掘中需要处理的几个问题(1)全局观点和局部观点离群点与众不同，但具有相对性。(2)点的离群程度可以通过定义对象的偏离程度来给对象打分——离群因子(OutlierFactor)或离群值得分(OutlierScore)，即都为离群点的情况下，也还有分高和分低的区别。(3)离群点的数量及时效性正常点的数量远远超过离群点的数量，离群点的数量在大规模数据集中所占的比例较低，小于5%甚至1%.6.1概述(5)离群点挖掘中需要处理的几个问题6.1概述(5)离群点实例一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的；一个公司的高层管理人员的工资明显高于普通员工的工资可能成为离群点但却是合理的数据(如平安保险公司2007年5位高管税后收入超过了1000万元)；一部住宅电话的话费由每月200元以内增加到数千元可能就因为被盗打或其它特殊原因所致；一张信用卡出现明显的高额消费也许是因为是盗用的卡。6.1概述(6)离群点实例6.1概述(6)离群点与众不同但具有相对性：高与矮，疯子与常人。类似术语：Outliermining，Exceptionmining:异常挖掘、离群挖掘、例外挖掘和稀有事件挖掘。6.1概述(7)离群点与众不同但具有相对性：6.1概述(7)(1)用于定义离群点的属性个数一个对象只有单个属性一个对象具有多个属性：可能某个属性异常，某个属性正常如：对于男生而言，身高1.6m，体重55kg，这个很正常；身高1.6m，体重75kg，这个有点离群；身高1.8m，体重75kg，基本正常。若对于女生，则三组值可能都不太正常。所以，定义离群点需要指明如何使用多个属性的值确定一个对象是否离群？6.2基于相对密度的离群点检测(1)(1)用于定义离群点的属性个数6.2基于相对密度的离群点检(2)全局观点和局部观点一个对象可能相对于所有对象看上去离群，但它相对于它的局部近邻不是离群的例如：身高1.85m对于一般人群是不常见的，但对于职业篮球运动员不算什么6.2基于相对密度的离群点检测(2)(2)全局观点和局部观点6.2基于相对密度的离群点检测(到k-最近邻的距离的计算定义6-1对于正整数k，对象p的k最近邻距离k_distance(p)定义为:

(1)除p外，至少有k个对象o满足(2)除p外，至多k-1个对象o满足利用k最近邻距离的大小来判定离群使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的离群程度由到它的k-最近邻的距离给定。这种方法对k的取值比较敏感。k太小(例如1)，则少量的邻近离群点可能导致较低的离群程度。k太大，则点数少于k的簇中所有的对象可能都成了离群点。6.2基于相对密度的离群点检测(1)到k-最近邻的距离的计算6.2基于相对密度的离群点检测(定义6-2(1)对象的局部邻域密度(2)相对密度其中，是不包含x的k-最近邻的集合，是该集合的大小，y是一个最近邻。基于相对密度的离群点检测方法通过比较对象的密度与它的邻域中的对象平均密度来检测离群点。簇内靠近核心点的对象的相对密度接近于1，而处于簇的边缘或是簇的外面的对象的相对较大。定义相对密度为离群因子：6.2基于相对密度的离群点检测(2)定义6-2(1)对象的局部邻域密度6.2基于相对密度基于相对密度离群点检测算法,该算法由三步组成：第一步：对于每一对象x，确定x的k-最近邻集合N(x,k)和密度density(x,k)第二步：对于每一对象x，确定x的相对密度relativedensity(x,k)，并赋值给OF1(x,k)第三步：对OF1(x,k)降序排列，确定离群因子大的若干对象6.2基于相对密度的离群点检测(3)基于相对密度离群点检测算法,该算法由三步组成：6.2基于相选择合适的离群因子阈值一种形式上简单的方法是指定离群点个数；这里介绍另一种确定OF1(x,k)分割阈值的方法：对OF1(x,k)降序排列，选择OF1(x,k)急剧下降的点作为离群值、正常值的分隔点，如图6-3所示，在该图中，有两个点判定为离群点。6.2基于相对密度的离群点检测(4)选择合适的离群因子阈值6.2基于相对密度的离群点检测(4

例6-1给定二维数据集，表6-1给出了点的坐标，可视化的图形如图6-2所示(对象间的距离采用曼哈顿(Manhattan)距离计算)。K取2，3，5时，以表格方式给出所有点的局部邻域密度及相对密度的离群因子。

表6-1例6-1二维数据集P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15P16P17P18P19P20P21P22X1222345.55.566666.56.57772.53345Y7876776.5787.57676.587621.5254例6-1给定二维数据集，表6-1给出了点的坐标，可视化的K取2，3，5时，所有点的局部邻域密度、相对密度如表6-3所示

表6-3不同k值的计算结果.点的坐标k=2k=3k=5标号xy局部邻域密度相对密度局部邻域密度相对密度局部邻域密度相对密度P1170.571.380.571.210.501.20P2280.571.380.571.210.501.20P3271.000.681.000.580.830.64P4260.571.380.571.210.461.23P5371.000.900.631.050.630.92P6470.801.880.571.890.571.41P75.56.51.141.331.141.190.921.14P85.572.000.791.331.210.861.16P9681.201.391.201.150.91

1.10P1067.52.000.801.331.220.861.17P11672.001.002.000.781.230.81P12661.001.311.001.310.821.22P136.572.000.702.000.701.430.72P146.56.51.091.261.091.261.090.94P15781.001.160.81.760.641.64P16771.111.281.111.241.110.91P17761.001.071.001.070.671.55P182.521.331.250.331.290.331.03P1931.51.331.250.38

1.000.281.43P20322.000.670.440.820.321.25P21450.501.180.381.900.381.64P22540.382.350.382.240.292.67K取2，3，5时，所有点的局部邻域密度、相对密度如表6-3所6.3基于聚类的离群点检测方法（1）6.3.1基于对象的离群因子的方法6.3.2基于簇的离群因子的方法6.3.3基于聚类的动态数据的离群点检测方法6.3基于聚类的离群点检测方法（1）6.3.1基于对象6.3基于聚类的离群点检测方法(2)基于聚类的方法有两个共同特点：(1)先采用特殊的聚类算法处理输入数据而得到聚类，再在聚类的基础上来检测离群点。(2)只需要扫描数据集若干次，效率较高，适用于大规模数据集。6.3基于聚类的离群点检测方法(2)基于聚类的方法有两个6.3基于聚类的离群点检测方法(3)静态数据的离群点检测第一阶段对数据进行聚类第二阶段计算对象或簇的离群因子，将离群因子大的对象或簇中对象判定为离群点。动态数据的离群点检测第一步，利用静态数据的离群检测方法建立离群检测模型第二步，利用对象与已有模型间的相似程度来检测离群点关键问题：距离的定义、离群程度的度量6.3基于聚类的离群点检测方法(3)静态数据的离群点检测6.3.1基于对象离群因子的方法(1)首先聚类所有对象，然后评估对象属于簇的程度如果一个对象不强属于任何簇，则称该对象为基于聚类的离群点。可以用对象到它的簇中心的距离来度量对象属于簇的程度。6.3.1基于对象离群因子的方法(1)首先聚类所有对象6.3.1基于对象离群因子的方法(2)定义6-3给定簇C，C

的摘要信息CSI(ClusterSummaryInformation)定义为：其中n为簇C

的大小，Summary由分类属性中不同取值的频度信息和数值属性的质心两部分构成，即：定义6-4假设据集D被聚类算法划分为k个簇对象p的离群因子(OutlierFactor)OF2(p)定义为p与所有簇间距离的加权平均值：

OF2(p)度量了对象p偏离整个数据集的程度，其值越大，说明p偏离整体越远。6.3.1基于对象离群因子的方法(2)定义6-3给定基于对象的离群因子检测方法描述如下：第一步，对数据集D进行采用一趟聚类算法进行聚类，得到聚类结果第二步，计算数据集D中所有对象p的离群因子OF2(p)，对OF2(p)降序排列，确定离群因子大的若干对象。

6.3.1基于对象离群因子的方法(3)基于对象的离群因子检测方法描述如下：6.3.1基于对象离群例6-2基于聚类的离群点检测示例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-2基于聚类的离群点检测示例1解答：根据定义6-4，公式对于P1点有：

对于P2有：可见，点P1较P2更可能成为离群点。第6章离群点挖掘分析课件同理可求得所有对象的离群因子，结果如表所示。xyOF2122.2132.3112.9212.6221.7231.9685.9242.5322.2574.8523.4同理可求得所有对象的离群因子，结果如表所示。xyOF21226.3.2基于簇的离群因子的方法（1）(1)在某种度量下，相似对象或相同类型的对象会聚集在一起，或者说正常数据与离群数据会聚集在不同的簇中；(2)正常数据占绝大部分，且离群数据与正常数据表现出明显不同，或者说离群数据会偏离正常数据(也就是大部分数据)。6.3.2基于簇的离群因子的方法（1）(1)在某种度量下定义6-5给定簇C，C的摘要信息CSI(ClusterSummaryInformation)定义为：

其中kind为簇的类别(取值‘normal’或‘outlier’)，为簇C的大小,Cluster为簇C中对象标识的集合，Summary

由分类属性中不同取值的频度信息和数值型属性的质心两部分构成，即：6.3.2基于簇的离群因子的方法（2）定义6-5给定簇C，C的摘要信息CSI(Cluster定义6-6假设据集D被聚类算法划分为k个簇，簇离群因子(OutlierFactor)

定义为簇与其它所有簇间距离的加权平均值：如果一个簇离几个大簇的距离都比较远，则表明该簇偏离整体较远，其离群因子也较大。度量了簇偏离整个数据集的程度，其值越大，说明偏离整体越远。6.3.2基于簇的离群因子的方法（3）定义6-6假设据集D被聚类算法划分为k个簇该方法由两个阶段构成：第一阶段是利用一趟聚类算法对数据集进行聚类；第二阶段是计算每个簇的离群因子，并按离群因子对簇进行排序，最终确定离群簇，也即确定离群对象。6.3.2基于簇的离群因子的方法（4）该方法由两个阶段构成：6.3.2基于簇的离群因子的方法（具体算法描述如下：第一阶段，聚类：对数据集D进行聚类，得到聚类结果；第二阶段，确定离群簇：计算每个簇的离群因子，按递减的顺序重新排列，求满足：

的最小，将簇标识为‘outlier’类(即其中每个对象均看成离群)，而将标识为‘normal’类(即其中每个对象均看成正常)。6.3.2基于簇的离群因子的方法（5）具体算法描述如下：6.3.2基于簇的离群因子的方法（5）例6-3基于聚类的离群点检测示例2对例6-3中的数据集，聚类后得到三个簇C={C1、C2、C3}，簇心分别为：C1(5.5,7.5)、C2(5,2)、C3(1.75,2.25)。簇之间的距离分别为：进一步计算三个簇的离群因子，具体如下：例6-3基于聚类的离群点检测示例2对例6-3中的数据集，聚第6章离群点挖掘分析课件基本思想如下：在对训练集聚类的基础上，按照簇的离群因子排序簇，并按一定比例将簇标识为”normal”或”outlier”，以标识的簇作为分类模型，按照对象与分类模型中最接近簇的距离判断它是否离群点。6.3.3基于聚类的动态数据的离群点检测方法（1）基本思想如下：6.3.3基于聚类的动态数据的离群点检测方法6.3.3基于聚类的动态数据的离群点检测方法（2）(1)模型建立第一步，聚类：对训练集进行聚类，得到聚类结果；第二步，给簇作标记：计算每个簇的离群因子，按递减的顺序重新排列，求满足：

的最小b，将簇识为离群簇，而将标识为正常簇。第三步，确定模型：以每个簇的摘要信息，聚类半径阈值r作为模型6.3.3基于聚类的动态数据的离群点检测方法（2）(1)(2)模型评估利用改进的最近邻分类方法INN(ImprovedNearestNeighbor)评估测试集中的每个对象。INN方法具体描述如下：对于测试集中对象p，计算p与每个簇的距离若，则说明p是已知类型的行为，将簇的标识作为p的标识，否则说明p是一种新的行为，将p标识为可疑对象——候选离群点。6.3.3基于聚类的动态数据的离群点检测方法（3）(2)模型评估利用改进的最近邻分类方法INN(Improv(3)模型更新对于测试集中对象p，按照前面聚类的方式，对新增对象进行增量式聚类更新用建立模型同样的方法对所有簇重新标记其类别。6.3.3基于聚类的动态数据的离群点检测（3）(3)模型更新对于测试集中对象p，按照前面聚类的方6.4离群点挖掘方法的评估（1）可以通过下表所示混淆矩阵来描述离群点挖掘方法的检测性能。在离群点检测问题中，并不关注预测正确的normal类对象，重点关注的是正确预测的outlier类对象。预测类别outliernormal实际类别outlier预测正确的outlier预测错误的outliernormal预测错误的normal预测正确的normal6.4离群点挖掘方法的评估（1）可以通过下表所示混淆矩阵离群点检测方法准确性的两个指标检测率(Detectionrate)表示被正确检测的离群点记录数占整个离群点记录数的比例；误报率(Falsepositiverate)表示正常记录被检测为离群点记录数占整个正常记录数的比例。期望离群点挖掘方法对离群数据有高的检测率，对正常数据有低的误报率，但两个指标之间会有一些冲突，高的检测率常常会导致高的误报率。也可以采用ROC曲线来显示检测率和误报率之间关系6.4离群点挖掘方法的评估（2）离群点检测方法准确性的两个指标6.4离群点挖掘方法的评估本章小结(1)介绍了离群点概念及离群点挖掘的意义。(2)从技术的角度介绍了基于相对密度和基于聚类的离群点挖掘方法，对这几种方法的优劣进行了分析。并通过实例说明了这些离群点检测方法的应用。本章小结(1)介绍了离群点概念及离群点挖掘的意义。作业：P125：6.1，6.2,6.3作业：P125：6.1，6.2,6.3商务数据挖掘与应用案例分析商务数据挖掘与应用案例分析第6章离群点挖掘

6.1概述>>

6.2基于相对密度的离群点检测方法>>

6.3基于聚类的离群点检测方法>>6.4离群点检测方法的评估>>

第6章离群点挖掘6.1概述>>开篇案例——保险欺诈检验随着保险业的蓬勃发展，保险欺诈现象也越来越严重。有关统计数据显示，国际上某些险种因被欺诈而导致的赔款支出最高可达保险费收入的50％。从所发生的保险欺诈案例看，手段无所不用且花样翻新，有的虚构或者伪造索赔，人寿保险中常见的是移花接木、冒名顶替，或者自演自导一幕幕自残的苦肉计，更恶劣的还有杀亲骗保者，财产保险中，诸如故意沉船、故意纵火等骗赔伎俩，五花八门。愈演愈烈的保险欺诈违法犯罪活动，不仅极大地损害了保险合同当事人的合法权益，而且还严重扰乱了保险市场的正常秩序。一方面他对保险公司的财产构成了直接的侵犯；另一方面，保险公司面对保险欺诈不得不提高保费，这样，诚实的投保人成为最大的损失者，这将会严重阻碍保险业的发展。在人寿保险业务中，一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作地址、工资水平、索赔次数等等。我们主要想通过数据挖掘找出行为异常的客户记录。我们主要关注购买人的年龄、工作单位、健康状况、工资水平的信息和购买后的索赔情况，可以认为保单号、单位代号、单位名称是一些无关信息。这种人寿保险公司通过分析客户信息识别保险中的欺诈特征就是离群点检测方法研究的问题。数据挖掘中的多数方法都会将异常数据视为噪音或异常而丢弃。而离群点检验在激增的客户信息和业务数据中寻找异常数据，并进行更深层次的分析。这些异常数据与数据的一般行为或模型不一致，发生的概率非常小。但在保险欺诈检验中，小概率事件可能比正常发生的事件更有意义。因此，通过离群点检验将客户信息进行细致的分类挖掘，寻找欺诈的一般特征，并建立客户分析预测模型，对具有欺诈特征的客户群体实施相应的措施，以提高公司的反欺诈能力。开篇案例——保险欺诈检验随着保险业的蓬勃发展，保险欺诈现象也6.1概述(1)什么是离群点(Outlier)？Hawkins的定义：离群点是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。Weisberg的定义：离群点是与数据集中其余部分不服从相同统计模型的数据。Samuels的定义：离群点是足够地不同于数据集中其余部分的数据。Porkess的定义：离群点是远离数据集中其余部分的数据6.1概述(1)什么是离群点(Outlier)？离群点的特殊意义和实用价值现有数据挖掘研究大多集中于发现适用于大部分数据的常规模式,在许多应用领域中，离群点通常作为噪音而忽略，许多数据挖掘算法试图降低或消除离群点的影响。而在有些应用领域识别离群点是许多工作的基础和前提，离群点会带给我们新的视角。如在欺诈检测中，离群点可能意味欺诈行为的发生，在入侵检测中离群点可能意味入侵行为的发生。6.1概述(2)离群点的特殊意义和实用价值6.1概述(2)离群点检测的应用领域电信、保险、银行中的欺诈检测与风险分析发现电子商务中的犯罪行为灾害气象预报税务局分析不同团体交所得税的记录，发现异常模型和趋势海关、民航等安检部门推断哪些人可能有嫌疑海关报关中的价格隐瞒营销定制：分析花费较小和较高顾客的消费行为医学研究中发现医疗方案或药品所产生的异常反应计算机中的入侵检测应用异常检测到文本编辑器，可有效减少文字输入的错误……6.1概述(3)离群点检测的应用领域6.1概述(3)离群点挖掘问题由两个子问题构成：(1)定义在一个数据集中什么数据是不一致或离群的数据；(2)找出所定义的离群点的有效挖掘方法。离群点挖掘问题可以概括为如何度量数据偏离的程度和有效发现离群点的问题。为什么会出现离群点？测量、输入错误或系统运行错误所致数据内在特性所决定客体的异常行为所致由于离群点产生的机制是不确定的，离群点挖掘算法检测出的“离群点”是否真正对应实际的异常行为，不是由离群点挖掘算法来说明、解释的，只能由领域专家来解释，离群点挖掘算法只能为用户提供可疑的数据，以便用户引起特别的注意并最后确定是否真正的异常。对于异常数据的处理方式也取决于应用，并由领域专家决策。6.1概述(4)离群点挖掘问题由两个子问题构成：6.1概述(4)离群点挖掘中需要处理的几个问题(1)全局观点和局部观点离群点与众不同，但具有相对性。(2)点的离群程度可以通过定义对象的偏离程度来给对象打分——离群因子(OutlierFactor)或离群值得分(OutlierScore)，即都为离群点的情况下，也还有分高和分低的区别。(3)离群点的数量及时效性正常点的数量远远超过离群点的数量，离群点的数量在大规模数据集中所占的比例较低，小于5%甚至1%.6.1概述(5)离群点挖掘中需要处理的几个问题6.1概述(5)离群点实例一个人的年龄为-999就可能是由于程序处理缺省数据设置默认值所造成的；一个公司的高层管理人员的工资明显高于普通员工的工资可能成为离群点但却是合理的数据(如平安保险公司2007年5位高管税后收入超过了1000万元)；一部住宅电话的话费由每月200元以内增加到数千元可能就因为被盗打或其它特殊原因所致；一张信用卡出现明显的高额消费也许是因为是盗用的卡。6.1概述(6)离群点实例6.1概述(6)离群点与众不同但具有相对性：高与矮，疯子与常人。类似术语：Outliermining，Exceptionmining:异常挖掘、离群挖掘、例外挖掘和稀有事件挖掘。6.1概述(7)离群点与众不同但具有相对性：6.1概述(7)(1)用于定义离群点的属性个数一个对象只有单个属性一个对象具有多个属性：可能某个属性异常，某个属性正常如：对于男生而言，身高1.6m，体重55kg，这个很正常；身高1.6m，体重75kg，这个有点离群；身高1.8m，体重75kg，基本正常。若对于女生，则三组值可能都不太正常。所以，定义离群点需要指明如何使用多个属性的值确定一个对象是否离群？6.2基于相对密度的离群点检测(1)(1)用于定义离群点的属性个数6.2基于相对密度的离群点检(2)全局观点和局部观点一个对象可能相对于所有对象看上去离群，但它相对于它的局部近邻不是离群的例如：身高1.85m对于一般人群是不常见的，但对于职业篮球运动员不算什么6.2基于相对密度的离群点检测(2)(2)全局观点和局部观点6.2基于相对密度的离群点检测(到k-最近邻的距离的计算定义6-1对于正整数k，对象p的k最近邻距离k_distance(p)定义为:

(1)除p外，至少有k个对象o满足(2)除p外，至多k-1个对象o满足利用k最近邻距离的大小来判定离群使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的离群程度由到它的k-最近邻的距离给定。这种方法对k的取值比较敏感。k太小(例如1)，则少量的邻近离群点可能导致较低的离群程度。k太大，则点数少于k的簇中所有的对象可能都成了离群点。6.2基于相对密度的离群点检测(1)到k-最近邻的距离的计算6.2基于相对密度的离群点检测(定义6-2(1)对象的局部邻域密度(2)相对密度其中，是不包含x的k-最近邻的集合，是该集合的大小，y是一个最近邻。基于相对密度的离群点检测方法通过比较对象的密度与它的邻域中的对象平均密度来检测离群点。簇内靠近核心点的对象的相对密度接近于1，而处于簇的边缘或是簇的外面的对象的相对较大。定义相对密度为离群因子：6.2基于相对密度的离群点检测(2)定义6-2(1)对象的局部邻域密度6.2基于相对密度基于相对密度离群点检测算法,该算法由三步组成：第一步：对于每一对象x，确定x的k-最近邻集合N(x,k)和密度density(x,k)第二步：对于每一对象x，确定x的相对密度relativedensity(x,k)，并赋值给OF1(x,k)第三步：对OF1(x,k)降序排列，确定离群因子大的若干对象6.2基于相对密度的离群点检测(3)基于相对密度离群点检测算法,该算法由三步组成：6.2基于相选择合适的离群因子阈值一种形式上简单的方法是指定离群点个数；这里介绍另一种确定OF1(x,k)分割阈值的方法：对OF1(x,k)降序排列，选择OF1(x,k)急剧下降的点作为离群值、正常值的分隔点，如图6-3所示，在该图中，有两个点判定为离群点。6.2基于相对密度的离群点检测(4)选择合适的离群因子阈值6.2基于相对密度的离群点检测(4

例6-1给定二维数据集，表6-1给出了点的坐标，可视化的图形如图6-2所示(对象间的距离采用曼哈顿(Manhattan)距离计算)。K取2，3，5时，以表格方式给出所有点的局部邻域密度及相对密度的离群因子。

表6-1例6-1二维数据集P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15P16P17P18P19P20P21P22X1222345.55.566666.56.57772.53345Y7876776.5787.57676.587621.5254例6-1给定二维数据集，表6-1给出了点的坐标，可视化的K取2，3，5时，所有点的局部邻域密度、相对密度如表6-3所示

表6-3不同k值的计算结果.点的坐标k=2k=3k=5标号xy局部邻域密度相对密度局部邻域密度相对密度局部邻域密度相对密度P1170.571.380.571.210.501.20P2280.571.380.571.210.501.20P3271.000.681.000.580.830.64P4260.571.380.571.210.461.23P5371.000.900.631.050.630.92P6470.801.880.571.890.571.41P75.56.51.141.331.141.190.921.14P85.572.000.791.331.210.861.16P9681.201.391.201.150.91

1.10P1067.52.000.801.331.220.861.17P11672.001.002.000.781.230.81P12661.001.311.001.310.821.22P136.572.000.702.000.701.430.72P146.56.51.091.261.091.261.090.94P15781.001.160.81.760.641.64P16771.111.281.111.241.110.91P17761.001.071.001.070.671.55P182.521.331.250.331.290.331.03P1931.51.331.250.38

1.000.281.43P20322.000.670.440.820.321.25P21450.501.180.381.900.381.64P22540.382.350.382.240.292.67K取2，3，5时，所有点的局部邻域密度、相对密度如表6-3所6.3基于聚类的离群点检测方法（1）6.3.1基于对象的离群因子的方法6.3.2基于簇的离群因子的方法6.3.3基于聚类的动态数据的离群点检测方法6.3基于聚类的离群点检测方法（1）6.3.1基于对象6.3基于聚类的离群点检测方法(2)基于聚类的方法有两个共同特点：(1)先采用特殊的聚类算法处理输入数据而得到聚类，再在聚类的基础上来检测离群点。(2)只需要扫描数据集若干次，效率较高，适用于大规模数据集。6.3基于聚类的离群点检测方法(2)基于聚类的方法有两个6.3基于聚类的离群点检测方法(3)静态数据的离群点检测第一阶段对数据进行聚类第二阶段计算对象或簇的离群因子，将离群因子大的对象或簇中对象判定为离群点。动态数据的离群点检测第一步，利用静态数据的离群检测方法建立离群检测模型第二步，利用对象与已有模型间的相似程度来检测离群点关键问题：距离的定义、离群程度的度量6.3基于聚类的离群点检测方法(3)静态数据的离群点检测6.3.1基于对象离群因子的方法(1)首先聚类所有对象，然后评估对象属于簇的程度如果一个对象不强属于任何簇，则称该对象为基于聚类的离群点。可以用对象到它的簇中心的距离来度量对象属于簇的程度。6.3.1基于对象离群因子的方法(1)首先聚类所有对象6.3.1基于对象离群因子的方法(2)定义6-3给定簇C，C

的摘要信息CSI(ClusterSummaryInformation)定义为：其中n为簇C

的大小，Summary由分类属性中不同取值的频度信息和数值属性的质心两部分构成，即：定义6-4假设据集D被聚类算法划分为k个簇对象p的离群因子(OutlierFactor)OF2(p)定义为p与所有簇间距离的加权平均值：

OF2(p)度量了对象p偏离整个数据集的程度，其值越大，说明p偏离整体越远。6.3.1基于对象离群因子的方法(2)定义6-3给定基于对象的离群因子检测方法描述如下：第一步，对数据集D进行采用一趟聚类算法进行聚类，得到聚类结果第二步，计算数据集D中所有对象p的离群因子OF2(p)，对OF2(p)降序排列，确定离群因子大的若干对象。

6.3.1基于对象离群因子的方法(3)基于对象的离群因子检测方法描述如下：6.3.1基于对象离群例6-2基于聚类的离群点检测示例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-2基于聚类的离群点检测示例1解答：根据定义6-4，公式对于P1点有：

对于P2有：可见，点P1较P2更可能成为离群点。第6章离群点挖掘分析课件同理可求得所有对象的离群因子，结果如表所示。xyOF2122.2132.3112.9212.6221.7231.9685.9242.5322.2574.8523.4同理可求得所有对象的离群因子，结果如表所示。xyOF21226.3.2基于簇的离群因子的方法（1）(1)在某种度量下，相似对象或相同类型的对象会聚集在一起，或者说正常数据与离群数据会聚集在不同的簇中；(2)正常数据占绝大部分，且离群数据与正常数据表现出明显不同，或者说离群数据会偏离正常数据(也就是大部分数据)。6.3.2基于簇的离群因子的方法（1）(1)在某种度量下定义6-5给定簇C，C的摘要信息CSI(ClusterSummaryInformation)定义为：

其中kind为簇的类别(取值‘normal’或‘outlier’)，为簇C的大小,Cluster为簇C中对象标识的集合，Summary

由分类属性中不同取值的频度信息和数值型属性的质心两部分构成，即：6.3.2基于簇的离群因子的方法（2）定义6-5给定簇C，C的摘要信息CSI(Cluster定义6-6假设据集D被聚类算法划分为k个簇，簇离群因子(OutlierFactor)

定义为簇与其它所有簇间距离的加权平均值：如果一个簇离几个大簇的距离都比较远，则表明该簇偏离整体较远，其离群因子也较大。度量了簇偏离整个数据集的程度，其值越大，说明偏离整体越远。6.3.2基于簇的离群因子的方法（3）定义6-6假设据集D被聚类算法划分为k个簇该方法由两个阶段构成：第一阶段是利用一趟聚类算法对数据集进行聚类；第二阶段是计算每个簇的离群因子，并按离群因子对簇进行排序，最终确定离群簇，也即确定离群对象。6.3.2基于簇的离群因子的方法（4）该方法由两个阶段构成：6.3.2基于簇的离群因子的方法（具体算法描述如下：第一阶段，聚类：对数据集D进行聚类，得到聚类结果；第二阶段，确定离群簇：计算每个簇的离群因子，按递减的顺序重新排列，求满足：