《数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第9章》由会员分享，可在线阅读，更多相关《数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第9章（48页珍藏版）》请在金锄头文库上搜索。
1、1,第九章 异常检测,2,第九章 目录,9.1 概 述 9.2 基于距离的异常检测 9.3 基于密度的异常检测 9.4 基于图的异常检测 9.5 本 章 小 结,3,9.1 概述,9.1.1 异常概念 9.1.2 异常的成因 9.1.3 异常检测方法,4,9.1.1 异常概念,异常是数据集中的小比例对象。通常，异常对象被称为离群点、例外（Outlier）、野点等。异常检测是一个有趣的数据挖掘任务，其目标是发现与大部分其他对象不同的对象。异常检测也称偏差检测（deviation detection）或例外挖掘（exception mining），它是发现新知识、新类别的一条有效途径。 异常检测可
2、以分为两个子问题：1）定义在给定的数据集合中什么样的数据认为是不一致的； 2）找到一个有效的方法挖掘这样的异常。,5,9.1.2 异常的成因,常见的异常成因有： 1）数据来源于不同的类。一个数据对象可能不同于其他数据对象（即异常），因为它属于一个不同的类型或类。 2）自然变异。属于同类的数据对象由于自然变异出现了异常。 3）数据测量或收集误差。数据测量和收集过程中出现的误差是另一个异常源。例如，由于人的错误、测量设备的问题或存在噪声，测量值可能被错误记录。,6,9.1.3 异常检测方法（1）,对于不考虑数据空间或时间的基本异常检测方法大致可以分成四类： 基于统计分布的异常检测（Distribu
3、tion-based outlier detection） 基于偏差的异常检测（Deviation-based outlier detection） 基于距离的异常检测（Distance-based outlier detection） 基于密度的异常检测（Density-based outlier detection）。,7,基于统计分布的异常检测方法对给定的数据集假设了一个分布或概率模型（例如，正态分布或泊松分布），然后根据模型采用不和谐检验识别异常。异常是那些同模型不能完美拟合的对象。 基于偏差的异常检测不使用统计检验或基于距离的度量来识别异常对象。相反，它通过检查一组对象的主要特征来识
4、别异常。“背离”这种描述的对象认为是异常。 基于距离的异常检测指定参数pct和dmin，如果数据集合D中的对象至少有pct部分与对象o的距离大于dmin，则称对象o是以pct和dmin为参数的基于距离的异常，记为DB(pct,dmin)。 基于密度的异常检测不将异常看作一种二元性质，而是使用局部异常因子（LOF）来评估一个对象是异常的程度。该程度依赖于对象相对于其邻域的孤立情况。,9.1.3 异常检测方法（2）,8,9.1.3 异常检测方法（3）,当考虑对象间的空间关系时，常用的异常检测方法有两种： 基于图的异常检测（Graph-based outlier detection） 基于多维空间的
5、异常检测（Multi-dimensional space-based outlier detection）,9,9.1.3 异常检测方法（4）,基于图的异常检测以图的连通性为基础。异常定义为属性值明显不同于其空间连通近邻的数据对象，这样的异常常常称为空间异常。 基于多维空间的异常检测也是检测空间异常，只是其空间邻域的定义与基于图的异常检测方法中的定义不同。在基于多维空间的异常检测中，空间邻域的定义基于欧几里德距离，而在基于图的异常检测中，空间邻域的定义基于图的连通性。,10,9.2 基于距离的异常检测,9.2.1 嵌套-循环(Nested-Loop，NL)算法 9.2.2 基于单元（Cell-
6、Based）的算法,11,9.2.1 嵌套-循环(Nested-Loop，NL)算法(1),主要思想：假设N是数据集中对象数，缓冲区的大小为数据集大小的B%，算法将整个缓冲区分成两个阵列，分别称为第一阵列和第二阵列。将数据集中的数据划分成块，每块大小为0.5B%。对象以块为单位读入阵列中，然后直接计算数据对象间的距离。第一阵列中的每个对象都有一个计数器，用于记录对象dmin邻域内的对象数目。某个计数器的值一旦大于一个异常的dmin邻域内最多对象数目M=N(1-pct) ，该计数器就停止计数。,12,算法：嵌套-循环（NL）算法（D，dmin，M） 输入：数据对象集合D，邻域半径dmin，一个异
7、常的dmin邻域内最多对象数目M 输出：D中的异常对象 步骤： （1）用数据集D中的一个数据块填充第一阵列 （2）for 第一阵列中每个数据对象ti，do （2.1）counti=0 （2.2）for第一阵列中的每个对象tj （2.2.1）if dist(ti,tj)dmin，then counti+1 /dist（）是距离函数 （2.2.2）if countiM，then 标记ti不是一个异常，处理下一个ti （3）当第一阵列中的对象都比较完后，do （3.1）用另一个数据块填充第二阵列，将那些从未填充过第一阵列的数据块记录下来,9.2.1 嵌套-循环(Nested-Loop，NL)算法(2
8、),13,（3.2）for第一阵列中未标记的每个数据对象ti （3.2.1）for第二阵列中的每个对象tj if dist(ti,tj)dmin，then counti+1 if countiM，则标记ti不是一个异常，处理下一个ti （4）输出第一阵列中每一个未被标记的对象ti，表示它是一个异常 （5）if第二阵列曾经充当过第一阵列，then stop else交换第一阵列和第二阵列的角色，转（2） 算法（2）考察了第一阵列中对象间的距离，（3）考察第一和第二阵列中对象间的距离，（5）保证数据集中的每个对象都能被作为中心进行考虑。,9.2.1 嵌套-循环(Nested-Loop，NL)算法(
9、3),14,例9.1 设NL算法用50%的缓冲区。数据集被分成A、B、C、D 四个逻辑块。每个阵列和块能容纳1/4数据集的对象数。数据块和阵列如图9.1所示。 图9.1 数据块和阵列,9.2.1 嵌套-循环(Nested-Loop，NL)算法(4),15,数据块填充阵列的顺序为： 序号 第一阵列 第二阵列 1 A B、C、D 读4块（A、B、C、D） 2 D A、B、C 读2块（B、C） 3 C D、A、B 读2个块（A、B） 4 B C、A、D 读2个块（A、D） 循环4次，总共读了10个块，遍历数据库的次数总计为10/4=2.5次。 NL算法的复杂性为O(kN2)。NL算法不受数据集大小和
10、维数的限制，但是当数据集较大时，NL算法需要多次遍历数据库。如果数据集被划分为n=200/B个块（B是缓冲区的百分比），那么（i）算法NL需读的块的总数为n+(n-2)(n-1)，（ii）遍历数据库的次数 n-2。,9.2.1 嵌套-循环(Nested-Loop，NL)算法(5),16,9.2.2 基于单元（Cell-Based）的算法（1）,基于单元的算法将空间区域划分为矩形单元，通过使用单元-单元的处理来代替NL算法中对象-对象的处理，避免了复杂性中的N2项，从而提高效率。 基于单元的算法分为两个：FindAlloutsM和FindAlloutsD。FindAlloutsM适用于检测存储于
11、主存的数据集中的异常，FindAlloutsD适用于处理大型、磁盘数据集。,17,9.2.2 基于单元（Cell-Based）的算法（2）,9.2.2.1 相关概念 9.2.2.2 FindAlloutsM 9.2.2.3 FindAlloutsD,18,9.2.2.1 相关概念 (1),1）1层邻域L1 单元Cx,y的1层邻域L1是按通常意义定义的Cx,y的直接邻域，即 L=1(Cx,y)= Cu,v|u=x1, v=y1, Cu,vCx,y 图9.2所示的是非边界单元的8个L1邻域。,图9.2 单元Cxy的1层邻域L1,19,性质1：同一单元中两个对象间的最远距离为dmin/2，即 性质2
12、：若Cu,v是Cx,y的L1邻域，那么Cu,v中的对象ti与Cx,y中对象tj间的最大距离为dmin，即 这是因为相邻单元中对象间的最远距离不会超过单元对角线长度的2倍。,9.2.2.1 相关概念 (2),20,2）2层邻域L2 单元Cx,y的2层邻域L2的定义为： L2(Cx,y)= Cu,v|u=x3, v=y3, Cu,v L1(Cx,y), Cu,vCx,y 每个非边界单元有72-32=40个L2邻域。,9.2.2.1 相关概念 (3),图9.3 单元的2层邻域L2,21,性质3：假如Cu,v Cx,y，Cu,v既不是Cx,y的L1邻域，也不是Cx,y的L2邻域，那么Cu,v中的对象t
13、i与Cx,y中对象tj间的距离一定大于dmin，即 这是因为L1和L2的厚度加起来是3个单元，ti与tj间的距离一定大于,9.2.2.1 相关概念 (4),22,性质4： 若Cx,y中的对象数M，那么Cx,y中的对象都不异常； 若Cx,y中的对象数+L1(Cx,y)中的对象数M，那么Cx,y中的对象都不异常； 若Cx,y中的对象数+ L1(Cx,y)中的对象数+ L2(Cx,y)中的对象数M，那么Cx,y中的每一个对象都是异常。,9.2.2.1 相关概念 (5),23,9.2.2.2. FindAllOutsM（FM）算法(1),FM算法使用了性质1性质4来检测异常和非异常，这种检测是以单元-
14、单元为基础，而不是以对象-对象为基础，从而可以将大量不可能是异常的对象排除。只有不满足性质4的单元内的对象才进行对象-对象的处理。,24,9.2.2.2. FindAllOutsM（FM）算法(2),算法：FindAllOutsM算法（D，dmin，M） 输入：数据对象集合D，邻域半径dmin，一个异常的dmin邻域内最多对象数目M 输出：D中的异常对象 步骤： （1）for q=1 to m countq=0 /m是单元数，单元的对象计数器清零 （2）将 D中每个对象p映射到合适的单元Cq中，存储p，countq+1 （3）检测各个单元，if countq M，then 将Cq标记为红色 /
15、Cq中的所有对象都不是异常 （4）对每一个红色单元Cr，将它的每一个L1邻域标记为粉红色，提供未曾被标记为红色的邻域 （5）for 每一个非空的白色单元Cw（未被标记颜色） （5.1） （5.2）if countw2 M，then 标记Cw为粉红色 （5.3）else （5.3.1）（5.3.2）if countw3 M，then 输出Cw中的所有对象 /都是异常 （5.3.3）else for Cw中的每一个对象p countp= countw2 for L2(Cw)中的每一个对象 if then countp+1 if countp M then 输出p /p是异常,25,在算法（5.3.
16、3）步，白色单元Cw中的每个对象p必须与Cw的L2邻域中的每个对象p比较，然后决定有多少个p在p的dmin邻域内。一旦p的dmin邻域内的对象数目超过M，则p不是异常。只有p的dmin邻域内的对象数目M，p才是异常。,9.2.2.2. FindAllOutsM（FM）算法(3),26,9.2.2.3. FindAllOutsD（FD）算法(1),FM算法适用于检测存储于主存的数据集中的异常。对于大型磁盘数据集，无法将整个数据集存储于主存中，因此，将数据集分页，各页依次读入主存处理。在处理大型磁盘数据的过程中，提高效率的关键在于使读页的次数或遍历数据库的次数最小化。在基于单元的算法中，有两个阶段需要读页： 1）初始映射阶段：在算法FM的（2），每个对象被映射到合适的单元中。这一步需要遍历数据库一次。 2）对象成对比较阶段：在算法FM的5.3.c步，为了完成对象
