电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第9章

48页
  • 卖家[上传人]:E****
  • 文档编号:89184296
  • 上传时间:2019-05-20
  • 文档格式:PPT
  • 文档大小:420KB
  • / 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),它是发现新知识、新类别的一条有效途径。 异常检测可以分为两个子问题:1)定义在给定的数据集合中什么样的数据认为是不一致的; 2)找到一个有效的方法挖掘这样的异常。,5,9.1.2 异常的成因,常见的异常成因有: 1)数据来源于不同的类。一个数据对象可能不同于其他数据对象(即异常),因为它属于一个不同的类型或类。 2)自然变异。属于同类的数据对象由于自然变异出现了异常。 3)数据测量或收集误差。数据测量和收集过程中出现的误差是另一个异常源。例如,由

      2、于人的错误、测量设备的问题或存在噪声,测量值可能被错误记录。,6,9.1.3 异常检测方法(1),对于不考虑数据空间或时间的基本异常检测方法大致可以分成四类: 基于统计分布的异常检测(Distribution-based outlier detection) 基于偏差的异常检测(Deviation-based outlier detection) 基于距离的异常检测(Distance-based outlier detection) 基于密度的异常检测(Density-based outlier detection)。,7,基于统计分布的异常检测方法对给定的数据集假设了一个分布或概率模型(例如,正态分布或泊松分布),然后根据模型采用不和谐检验识别异常。异常是那些同模型不能完美拟合的对象。 基于偏差的异常检测不使用统计检验或基于距离的度量来识别异常对象。相反,它通过检查一组对象的主要特征来识别异常。“背离”这种描述的对象认为是异常。 基于距离的异常检测指定参数pct和dmin,如果数据集合D中的对象至少有pct部分与对象o的距离大于dmin,则称对象o是以pct和dmin为参数的基于距离

      3、的异常,记为DB(pct,dmin)。 基于密度的异常检测不将异常看作一种二元性质,而是使用局部异常因子(LOF)来评估一个对象是异常的程度。该程度依赖于对象相对于其邻域的孤立情况。,9.1.3 异常检测方法(2),8,9.1.3 异常检测方法(3),当考虑对象间的空间关系时,常用的异常检测方法有两种: 基于图的异常检测(Graph-based outlier detection) 基于多维空间的异常检测(Multi-dimensional space-based outlier detection),9,9.1.3 异常检测方法(4),基于图的异常检测以图的连通性为基础。异常定义为属性值明显不同于其空间连通近邻的数据对象,这样的异常常常称为空间异常。 基于多维空间的异常检测也是检测空间异常,只是其空间邻域的定义与基于图的异常检测方法中的定义不同。在基于多维空间的异常检测中,空间邻域的定义基于欧几里德距离,而在基于图的异常检测中,空间邻域的定义基于图的连通性。,10,9.2 基于距离的异常检测,9.2.1 嵌套-循环(Nested-Loop,NL)算法 9.2.2 基于单元(Cell-

      4、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,一个异常的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不是一个异常,

      5、处理下一个ti (3)当第一阵列中的对象都比较完后,do (3.1)用另一个数据块填充第二阵列,将那些从未填充过第一阵列的数据块记录下来,9.2.1 嵌套-循环(Nested-Loop,NL)算法(2),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)算法(3),14,例9.1 设NL算法用50%的缓冲区。数据集被分成A、B、C、D 四个逻辑块。每个阵列和块能容纳1/4数据集的对象数。数据块和阵列如图9.1所示。 图9.1 数据块和阵列,9.2.1 嵌套

      6、-循环(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算法不受数据集大小和维数的限制,但是当数据集较大时,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适用于检测存储于

      7、主存的数据集中的异常,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:若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=4

      8、0个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中的对象ti与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来检测异常和非异常,这种检测是以单元-单元为基础,而不是以对象-对象为基础,从而可以将大量不可能是异常的对象排除。只有不满足性质4的单元内的对象才进行对象-对象的处理。,24,9.2.2.2. FindAllOutsM(FM)算法(2),

      9、算法: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标记为红色 /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.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步,为了完成对象

      《数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第9章》由会员E****分享,可在线阅读,更多相关《数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第9章》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.