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

第九章 异常检测 第九章 目录 9.1 概 述 9.2 基于距离的异常检测 9.3 基于密度的异常检测 9.4 基于图的异常检测 9.5 本 章 小 结 . 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标记为红色 //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是异常 图9.5 A类页、B类页和C类页 A、B、C三类页如图9.5所示。图中Cw、C?w是白色单元，Cv是非白色单元，Cr是红色单元，其中C?w、Cv?L2(Cw)。 . FindAllOutsD（FD）算法(3) 设第i页中的对象p映射到白色单元Cw中，为了判断对象p是否异常，需要计算对象p与下列三种对象间的距离： 1）被映射到Cw的L2邻域的白色单元中的白色对象 2）被映射到Cw的L2邻域的非白色单元中的非白色对象，位于第j页，且j?i 3）被映射到Cw的L2邻域的非白色单元中的非白色对象，位于第j页，但ji FD算法先读A类页，并将所有白色对象存储在主存，然后读B类页，若必要再读A类页。先读A类页，当所有A类页被读过之后，对象对（p，p’）的距离dist(p,p?)可以计算出来；读完B类页后， dist(p,p??)可以计算；再读A类页后， dist(p,p???)也可以计算。C类页不需要再读。 . FindAllOutsD（FD）算法(4) . FindAllOutsD（FD）算法(5) 算法：FindAllOutsD（FD）算法（D，dmin，M） 输入：数据对象集合D，邻域半径dmin，异常的dmin邻域内最多对象数目M 输出：D中的异常对象 步骤： （1）for q=1 to m countq=0 //m是单元数，单元的对象计数器清零 （2）for 每一个D中对象p （2.1）将p映射到合适的单元Cq中，但不存储p （2.2）countq+1 （2.3）记下Cq与p的页对应 （3）for q=1 to m （3.1）if countqM then 将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标记为黄色 //Cw中的所有对象都是异常 （5.3.3）else sumw=countw2 . FindAllOutsD（FD）算法(6) （6）for 每一个至少包含一个白色对象或黄色对象的页i （6.1）读第i页 （6.2）for 每一个有对象在页i中的白色单元或黄色单元Cq （6.2.1）for 页i中被映射到Cq中的每一个对象p 将p存在Cq中 kcountp=sumq （7）for 每一个非空白色单元Cw中的每一个对象p （7.1）for 每一个白色单元或黄色单元CL，CL?L2(Cw) （7.1.1）for CL中