《第九章--异常检测-数据挖掘：概念与技术-教学1课件.ppt》由会员分享，可在线阅读，更多相关《第九章--异常检测-数据挖掘：概念与技术-教学1课件.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章第九章 异常检测异常检测19.1 概述概述9.1.1 异常概念异常概念异常是数据集中的小比例对象。通常，异常对象被称为离异常是数据集中的小比例对象。通常，异常对象被称为离群点、例外（群点、例外（Outlier）、野点等。异常检测是一个有趣的数）、野点等。异常检测是一个有趣的数据挖掘任务，其目标是发现与大部分其他对象不同的对象。据挖掘任务，其目标是发现与大部分其他对象不同的对象。异常检测也称偏差检测（异常检测也称偏差检测（deviation detection）或例外挖掘）或例外挖掘（exception mining），它是发现新知识、新类别的一条有），它是发现新知识、新类别的一条有效途径
2、。效途径。异常检测可以分为两个子问题：异常检测可以分为两个子问题：1）定义在给定的数据集合）定义在给定的数据集合中什么样的数据认为是不一致的；中什么样的数据认为是不一致的；2）找到一个有效的方）找到一个有效的方法挖掘这样的异常。法挖掘这样的异常。29.1.2 异常的成因异常的成因 常见的异常成因有：常见的异常成因有：数据来源于不同的类。一个数据对象可能不同于其他数据来源于不同的类。一个数据对象可能不同于其他数据对象（即异常），因为它属于一个不同的类型或数据对象（即异常），因为它属于一个不同的类型或类。类。自然变异。属于同类的数据对象由于自然变异出现了自然变异。属于同类的数据对象由于自然变异出现
3、了异常。异常。数据测量或收集误差。数据测量和收集过程中出现的数据测量或收集误差。数据测量和收集过程中出现的误差是另一个异常源。例如，由于人的错误、测量设误差是另一个异常源。例如，由于人的错误、测量设备的问题或存在噪声，测量值可能被错误记录。备的问题或存在噪声，测量值可能被错误记录。39.1.3 异常检测方法异常检测方法 对于不考虑数据空间或时间的基本异常检测对于不考虑数据空间或时间的基本异常检测方法大致可以分成四类：方法大致可以分成四类：l基于统计分布的异常检测（基于统计分布的异常检测（Distribution-based outlier detection）l 基于偏差的异常检测（基于偏差的
4、异常检测（Deviation-based outlier detection）l 基于距离的异常检测（基于距离的异常检测（Distance-based outlier detection）l 基于密度的异常检测（基于密度的异常检测（Density-based outlier detection）49.2 基于距离的异常检测基于距离的异常检测9.2.1 嵌套嵌套-循环循环(Nested-Loop，NL)算法算法主要思想：假设主要思想：假设N是数据集中对象数，缓冲区的大小是数据集中对象数，缓冲区的大小为数据集大小的为数据集大小的B%，算法将整个缓冲区分成两个阵列，算法将整个缓冲区分成两个阵列，分别
5、称为第一阵列和第二阵列。分别称为第一阵列和第二阵列。将数据集中的数据划分成块，每块大小为将数据集中的数据划分成块，每块大小为0.5B%。对。对象以块为单位读入阵列中，然后直接计算数据对象间的距象以块为单位读入阵列中，然后直接计算数据对象间的距离。第一阵列中的每个对象都有一个计数器，用于记录对离。第一阵列中的每个对象都有一个计数器，用于记录对象象dmin邻域内的对象数目。某个计数器的值一旦大于一邻域内的对象数目。某个计数器的值一旦大于一个异常的个异常的dmin邻域内最多对象数目邻域内最多对象数目M=N(1-pct)，该计数，该计数器就停止计数。器就停止计数。基于距离的异常：没有基于距离的异常：没
6、有“足够多足够多”近邻的对象。近邻的对象。6算法：嵌套算法：嵌套-循环（循环（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
7、counti+1 /dist（）是距离函数（）是距离函数 （2.2.2）if countiM，then 标记标记ti不是一个异常，处理下一个不是一个异常，处理下一个ti（3）当第一阵列中的对象都比较完后，）当第一阵列中的对象都比较完后，do （3.1）用另一个数据块填充第二阵列，将那些从未填充过第一阵列的数据）用另一个数据块填充第二阵列，将那些从未填充过第一阵列的数据块记录下来块记录下来 7（3.2）for第一阵列中未标记的每个数据对象第一阵列中未标记的每个数据对象ti （3.2.1）for第二阵列中的每个对象第二阵列中的每个对象tj if dist(ti,tj)dmin，then count
8、i+1 if countiM，则标记，则标记ti不是一个异常，处理下一个不是一个异常，处理下一个ti（4）输出第一阵列中每一个未被标记的对象）输出第一阵列中每一个未被标记的对象ti，表示它是一个异常表示它是一个异常（5）if第二阵列曾经充当过第一阵列，第二阵列曾经充当过第一阵列，then stop else交换第一阵列和第二阵列的角色，转（交换第一阵列和第二阵列的角色，转（2）算法（算法（2）考察了第一阵列中对象间的距离，（）考察了第一阵列中对象间的距离，（3）考察第一和第二阵）考察第一和第二阵列中对象间的距离，（列中对象间的距离，（5）保证数据集中的每个对象都能被作为中心进行考）保证数据集中
9、的每个对象都能被作为中心进行考虑。虑。8数据块填充阵列的顺序为：数据块填充阵列的顺序为：序号序号 第一阵列第一阵列 第二阵列第二阵列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算法需要
10、多次遍历数据库。算法需要多次遍历数据库。如果数据集被划分为如果数据集被划分为n=200/B 个块（个块（B是缓冲区的百分比）是缓冲区的百分比），那么（，那么（i）算法）算法NL需读的块的总数为需读的块的总数为n+(n-2)(n-1)，（，（ii）遍历数据库的次数遍历数据库的次数n-2。109.2.2 基于单元（基于单元（Cell-Based）的算法）的算法 基于单元的算法将空间区域划分为矩形单元，通过使基于单元的算法将空间区域划分为矩形单元，通过使用单元用单元-单元的处理来代替单元的处理来代替NL算法中对象算法中对象-对象的处理，对象的处理，避免了复杂性中的避免了复杂性中的N2项，从而提高效率
11、。项，从而提高效率。基于单元的算法分为两个：基于单元的算法分为两个：FindAlloutsM和和FindAlloutsD。FindAlloutsM适用于检测存储于主存的适用于检测存储于主存的数据集中的异常，数据集中的异常，FindAlloutsD适用于处理大型、磁盘适用于处理大型、磁盘数据集。数据集。11性质性质1：同一单元中两个对象间的最远距离为同一单元中两个对象间的最远距离为dmin/2，即，即 性质性质2：若若Cu,v是是Cx,y的的L1邻域，那么邻域，那么Cu,v中的对象中的对象ti与与Cx,y中中对象对象tj间的最大距离为间的最大距离为dmin，即，即 这是因为相邻单元中对象间的最远
12、距离不会超过单元对角这是因为相邻单元中对象间的最远距离不会超过单元对角线长度的线长度的2倍。倍。13性质性质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间的距离一间的距离一定大于定大于 15性质性质4：若若Cx,y中的对象数中的对象数M，那么，那么Cx,y中的对象都不异中的对象都不异常；常；若若Cx,y中的对象数中的对象数+
13、L1(Cx,y)中的对象数中的对象数M，那么，那么Cx,y中的对象都不异常；中的对象都不异常；若若Cx,y中的对象数中的对象数+L1(Cx,y)中的对象数中的对象数+L2(Cx,y)中的对象数中的对象数 M，那么，那么Cx,y中的每一个对象都是异常。中的每一个对象都是异常。16算法：算法：FindAllOutsM算法（算法（D，dmin，M）输入：数据对象集合输入：数据对象集合D，邻域半径，邻域半径dmin，一个异常的一个异常的dmin邻域内最多对象数目邻域内最多对象数目M输出：输出：D中的异常对象中的异常对象步骤：步骤：（1）for q=1 to m countq=0 /m是单元数，单元的对
14、象计数器清零是单元数，单元的对象计数器清零（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
15、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是异常是异常 18在在算算法法（5.3.3）步步，白白色色单单元元Cw中中的的每每个个对对象象p必必须须与与Cw的的L2邻邻域域中中的的每每个个对对象象p 比比较较，然然后后决决
16、定定有有多多少少个个p 在在p的的dmin邻邻域域内内。一一旦旦p的的dmin邻邻域域内内的的对对象象数数目目超超过过M，则则p不不是是异异常常。只有只有p的的dmin邻域内的对象数目邻域内的对象数目 M，p才是异常。才是异常。193.FindAllOutsD（FD）算法）算法FM算法适用于检测存储于主存的数据集中的异常。对于大算法适用于检测存储于主存的数据集中的异常。对于大型磁盘数据集，无法将整个数据集存储于主存中，因此，将型磁盘数据集，无法将整个数据集存储于主存中，因此，将数据集分页，各页依次读入主存处理。在处理大型磁盘数据数据集分页，各页依次读入主存处理。在处理大型磁盘数据的过程中，提高
17、效率的关键在于使读页的次数或遍历数据库的过程中，提高效率的关键在于使读页的次数或遍历数据库的次数最小化。在基于单元的算法中，有两个阶段需要读页：的次数最小化。在基于单元的算法中，有两个阶段需要读页：1）初始映射阶段：在算法）初始映射阶段：在算法FM的（的（2），每个对象被映），每个对象被映射到合适的单元中。这一步需要遍历数据库一次。射到合适的单元中。这一步需要遍历数据库一次。2）对象成对比较阶段：在算法）对象成对比较阶段：在算法FM的的5.3.c步，为了完成步，为了完成对象对象-对象的距离计算，白色单元对象的距离计算，白色单元Cw中的每个对象中的每个对象p与与Cw的的L2邻域中的每个对象邻域中
18、的每个对象p 都需要读。因为映射到同一单元或相都需要读。因为映射到同一单元或相邻单元中的对象，它们在磁盘上的物理地址不一定邻近。每邻单元中的对象，它们在磁盘上的物理地址不一定邻近。每一对对象（一对对象（p，p）的比较可能要求读一页，因此引起了大）的比较可能要求读一页，因此引起了大量的输入输出。量的输入输出。20FD算法的方法是挑选对象子集保存在主存中，将磁盘上的算法的方法是挑选对象子集保存在主存中，将磁盘上的数据页分类。各类数据页按一定顺序读入，从而使读页次数数据页分类。各类数据页按一定顺序读入，从而使读页次数最小化。被挑选的子集由映射到白色单元中的对象构成。这最小化。被挑选的子集由映射到白色
19、单元中的对象构成。这些对象称为白色对象，它们需要进行对象些对象称为白色对象，它们需要进行对象-对象的计算。白色对象的计算。白色单元中的对象数目被限定在单元中的对象数目被限定在M以内。以内。在在FD算法中，根据所包含的对象，所有页分成算法中，根据所包含的对象，所有页分成A、B、C三种类型。三种类型。1）A类页：包含白色对象的页。类页：包含白色对象的页。2）B类页：不包含白色对象，但是包含映射到白色单元的类页：不包含白色对象，但是包含映射到白色单元的L2邻域的非白色单元中的对象的页。邻域的非白色单元中的对象的页。3）C类页：所有其它页。类页：所有其它页。21A类页、类页、B类页和类页和C类页类页A
20、、B、C三类页如下图所示。图中三类页如下图所示。图中Cw、C w是白色单元，是白色单元，Cv是是非白色单元，非白色单元，Cr是红色单元，其中是红色单元，其中C w、Cv L2(Cw)。22算法：算法：FindAllOutsD（FD）算法（）算法（D，dmin，M）输入：数据对象集合输入：数据对象集合D，邻域半径，邻域半径dmin，异常的异常的dmin邻域内最多对象数目邻域内最多对象数目M输出：输出：D中的异常对象中的异常对象步骤：步骤：（1）for q=1 to m countq=0 /m是单元数，单元的对象计数器清零是单元数，单元的对象计数器清零（2）for 每一个每一个D中对象中对象p （
21、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）
22、（5.3.2）if countw3 M，then 将将Cw标记为黄色标记为黄色 /Cw中的所有对象都是异常中的所有对象都是异常 （5.3.3）else sumw=countw224（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中的每
23、一个对象中的每一个对象p （7.1）for 每一个白色单元或黄色单元每一个白色单元或黄色单元CL，CL L2(Cw)（7.1.1）for CL中的每一个对象中的每一个对象if，then kcountp+1 if kcountpM，then 标记标记p不是异常，处理下一个不是异常，处理下一个p（8）标记黄色单元中的所有对象是异常，输出这些异常）标记黄色单元中的所有对象是异常，输出这些异常 （9）for 至少包含一个（至少包含一个（i）既不是白色对象，也不是黄色对象，（）既不是白色对象，也不是黄色对象，（ii）映射到某白）映射到某白色单元色单元Cw的的L2邻域内的对象的页邻域内的对象的页i （9.
24、1）读页）读页i （9.2）for 每一个既不是白色单元，也不是黄色单元，并且有对象在页每一个既不是白色单元，也不是黄色单元，并且有对象在页i中的单元中的单元Cq，Cq L2(Cw)（9.2.1）for 页页i中映射到中映射到Cq中的每一个对象中的每一个对象for 每一个非空白色单元每一个非空白色单元Cw，Cw L2(Cq)for Cw中的每个对象中的每个对象p if ，then kcountp+1 if kcountpM，then 标记标记p不是异常不是异常（10）for 每一个非空白色单元中的每个对象每一个非空白色单元中的每个对象p （10.1）If p未被标记为非异常，未被标记为非异常，
25、then 标记标记p是异常，输出是异常，输出p25在在FD算法中，前算法中，前5步的处理与步的处理与FM算法相似，只是在算法相似，只是在FD的第（的第（2）步，不再存储对象，但是记录有对象被映射）步，不再存储对象，但是记录有对象被映射到到Cq中的页。中的页。建立这样的联系非常重要。因为在后面的步骤中，可建立这样的联系非常重要。因为在后面的步骤中，可能需要获取一个给定单元的对象，或者需要知道一个特定能需要获取一个给定单元的对象，或者需要知道一个特定页中的对象被映射到了哪些单元中。在（页中的对象被映射到了哪些单元中。在（5.3.2）步，如果）步，如果检测出一个白色单元中的所有对象都是异常，则将此白
26、色检测出一个白色单元中的所有对象都是异常，则将此白色单元标记为黄色。它的对象在（单元标记为黄色。它的对象在（6）从相应的页读入内存，）从相应的页读入内存，然后在（然后在（8）步标记并输出。（）步标记并输出。（6）只读那些至少包含一个）只读那些至少包含一个白色对象或黄色对象的页，即白色对象或黄色对象的页，即A类页。这些页的白色对象类页。这些页的白色对象或黄色对象与白色单元或黄色对象与白色单元Cw一同存储。一同存储。Cw中存储了中存储了countw个对象，并且个对象，并且countw M。为了处理。为了处理L2邻域，（邻域，（6.2.1)的第的第二步将二步将dmin-邻域计数器初始化为邻域计数器初
27、始化为Cw L1(Cw)中的对象数。中的对象数。269.3 基于密度的异常检测基于密度的异常检测9.3.1 相关概念相关概念1）k距离距离 对象对象p的的k距离距离kdistance(p)是是p到它的到它的k最近邻的最大距最近邻的最大距离。它定义为离。它定义为p与对象与对象o D之间的距离之间的距离d(p，o)，满足：，满足：（1）D中至少存在中至少存在k个对象到个对象到p的距离小于或等于的距离小于或等于p到到o的距的距离。（离。（2）D中最多有中最多有k-1个对象到个对象到p的距离比的距离比p到到o的距离小。的距离小。k与聚类算法与聚类算法DBSCAN中的中的MinPts相同，用于定义对象相
28、同，用于定义对象p的的局部邻域。局部邻域。2）k距离邻域距离邻域 对象对象p的的k距离邻域距离邻域Nk_distance(p)(p)包含所有与包含所有与p的距离不超的距离不超过过k_distance(p)的对象，即：的对象，即：Nkdistance(p)(p)=q Dp|d(p,q)kdistance(p)基于密度的异常：如果一个对象相对于它的局部邻域基于密度的异常：如果一个对象相对于它的局部邻域是远离的。是远离的。283）可达距离）可达距离 给定自然数给定自然数k，对象，对象p关于对象关于对象o的可达距离的可达距离reach_distk(p，o)为：为：reach_distk(p，o)=ma
29、xk_distance(o)，d(p，o)。reach_distk(p，o)的含义是，如果对象的含义是，如果对象p远离远离o，则两者间的，则两者间的可达距离就是它们间的实际距离。但是，如果可达距离就是它们间的实际距离。但是，如果p在在o的的k距离距离邻域内，则实际距离用邻域内，则实际距离用o的的k距离取代。距离取代。k距离越大，在相同距离越大，在相同邻域中对象的可达距离越相似。下图所示的是邻域中对象的可达距离越相似。下图所示的是=4时对象时对象p1和和p2关于对象关于对象o的可达距离。的可达距离。294）局部可达密度）局部可达密度用用MinPts表示表示p的邻域中最小的对象个数，那么对象的邻域
30、中最小的对象个数，那么对象p的局的局部可达密度为对象部可达密度为对象p与它的与它的MinPts邻域的平均可达距离的倒数：邻域的平均可达距离的倒数：5）局部异常因子）局部异常因子LOF 对象对象p的局部异常因子定义为：的局部异常因子定义为：LOF是对象是对象p和它的最近邻的局部可达密度的比率的平均和它的最近邻的局部可达密度的比率的平均值。值。p的局部可达密度越小，的局部可达密度越小，p的的MinPts最近邻的局部可达密度最近邻的局部可达密度越大，越大，LOFMinPts(p)越高。越高。LOF表征了表征了p的异常程度：如果的异常程度：如果p不不是局部异常，则是局部异常，则LOFMinPts(p)
31、接近于接近于1；p是局部异常的程度越大，是局部异常的程度越大，LOFMinPts(p)越高。越高。319.3.2 基于密度的异常检测算法基于密度的异常检测算法 LOF表征了对象表征了对象p的异常程度，因此，可以通过计算的异常程度，因此，可以通过计算LOF(p)来判断对象来判断对象p是否是局部异常。基于密度的异常检是否是局部异常。基于密度的异常检测算法的核心是对于指定的近邻个数测算法的核心是对于指定的近邻个数k，基于对象的最近基于对象的最近邻计算对象的邻计算对象的LOF。算法：基于密度的异常检测算法（算法：基于密度的异常检测算法（D，MinPts，k）输入：数据对象集合输入：数据对象集合D，近邻
32、个数，近邻个数MinPts，异常对象数目异常对象数目k输出：输出：k个异常个异常步骤：步骤：（1）for D中每个数据对象中每个数据对象p （1.1）确定）确定p的的MinPts距离邻域距离邻域NMinpts_distance(p)(p)32（1.2）使用）使用p的最近邻（即的最近邻（即NMinPts_distance(p)(p)中的对象），中的对象），计算计算p的局部可达密度的局部可达密度lrdMinPts(p)（1.3）计算）计算NMinPts_distance(p)(p)中每个对象中每个对象o的局部可达密的局部可达密度度lrdMinPts(o)（1.4）计算）计算p的局部异常因子的局部异
33、常因子LOFMinPts(p)（2）输出）输出D中中LOF值最大的值最大的k个对象个对象基于密度的异常检测算法的时间复杂度为基于密度的异常检测算法的时间复杂度为O(n2)（其（其中中n是是D中对象个数）。算法给出了对象异常程度的定中对象个数）。算法给出了对象异常程度的定量度量，并且在数据具有不同密度的区域也能够很好地量度量，并且在数据具有不同密度的区域也能够很好地识别局部异常。识别局部异常。339.4 基于图的异常检测基于图的异常检测9.4.1 相关概念相关概念1空间图空间图G 空间图空间图G=S,E，其中，其中S是空间对象是空间对象s1，s2，sn的集合，的集合，是是S中对象间连接的边的集合
34、。中对象间连接的边的集合。2空间邻域空间邻域 空间邻域基于图的连通性定义。如果在空间邻域基于图的连通性定义。如果在中，结中，结点点s1、s2与与s3相连，那么相连，那么s1、s2是是s3的空间邻域。的空间邻域。异常定义为属性值明显不同于其空间连通近邻异常定义为属性值明显不同于其空间连通近邻的数据对象。的数据对象。343空间统计量空间统计量S(x)数据对象数据对象x的统计量的统计量S(x)定义为定义为x的属性值与其邻域属的属性值与其邻域属性平均的差，即性平均的差，即S(x)=f(x)Ey N(x)(f(y)，其中，其中f(x)是是x的的属性值，属性值，N(x)是是x的邻域集合，的邻域集合，Ey
35、N(x)(f(y)是是x邻域属邻域属性的平均。性的平均。如果如果f(x)是正态分布，则空间统计量是正态分布，则空间统计量S(x)也是正态分布。也是正态分布。4空间异常空间异常 如果数据对象如果数据对象x满足：满足：,则则x是空间异常。其中是空间异常。其中 s是所有是所有S(x)的均值，的均值，s是所有是所有S(x)的标准偏差，的标准偏差，的选的选择依赖于指定的置信区间，比如对于择依赖于指定的置信区间，比如对于95%的置信区间，的置信区间，2。359.4.2 测试参数的计算测试参数的计算在检测空间异常之前，需要计算测试参数，如在检测空间异常之前，需要计算测试参数，如统计量的均值、标准偏差。计算测
36、试参数的算法统计量的均值、标准偏差。计算测试参数的算法（Test Parameters Computation，TPC）描述如下：）描述如下：算法：算法：TPC算法（算法（，D，F，ND，G）输入：属性空间输入：属性空间，数据对象集合，数据对象集合D，上的距离函数上的距离函数F，邻，邻域深度域深度ND，空间图，空间图G=(D，E)输出：输出：s，s 步骤：步骤：（1）for i=1 to|D|（1.1）oi=Get_one_Object(i，D)/从从D 中选择对象中选择对象 （1.2）NNS=Find_Neighbour_Nodes_Set(oi，ND，G)/从从G中搜索对象中搜索对象oi的
37、邻域的邻域 36（1.3）Accum_Dist=0 （1.4）for j=1 to|NNS|（1.4.1）ok=Get_one_Object(j，NNS)（1.4.2）Accum_Dist=F(oi，ok，)（1.5）Avg_Dist=Accum_Dist/|NNS|/计算对象计算对象oi的统的统计量计量 （1.6）Add_Element(Avg_Dist_Set，i)/存储对象存储对象oi的统计的统计量量（2）sGet_Mean(Avg_Dist_Set)/计算统计量的均计算统计量的均值值（3）sGet_Standard_Dev(Avg_Dist_Set)/计算统计量的计算统计量的标准偏差标
38、准偏差（4）return(s，s)Avg_Dist_Set用于存储所有对象的统计量用于存储所有对象的统计量S(x)。379.4.3 指定路径上的空间异常检测指定路径上的空间异常检测(Route Outlier Detection，ROD)算法算法基于基于TCP计算得到的参数计算得到的参数 s和和 s，具有空间图，具有空间图的数据集的数据集D中指定路径上的异常可以被检测出来。中指定路径上的异常可以被检测出来。ROD算法使用算法使用TPC算法计算的算法计算的 s和和 s检测用户指定路检测用户指定路径上的空间异常。在具有空间图径上的空间异常。在具有空间图的数据集的数据集D中指定中指定路径路径RN，R
39、OD算法首先在算法首先在G中为路径中为路径RN上的每个节上的每个节点点x查找其空间邻域；然后计算查找其空间邻域；然后计算x的属性值与其邻域的的属性值与其邻域的属性平均值之差属性平均值之差S(x)；使用空间异常测试公式；使用空间异常测试公式 ，每个，每个S(x)都能被检测，从而判定都能被检测，从而判定x是否是异常。是否是异常。是是预先指定的置信度区间。预先指定的置信度区间。38算法：指定路径上的空间异常检测（算法：指定路径上的空间异常检测（ROD）算法（，）算法（，D，F，ND，G，CI，s，s，RN）输入：属性空间，数据对象集合输入：属性空间，数据对象集合D，上的距离函数，上的距离函数F，邻域
40、深度邻域深度ND，空间图，空间图G=(D，E)，置信区间，置信区间CI，TPC算法算法计算的计算的 s和和 s，路径上的节点集，路径上的节点集RN输出：路径上的异常集输出：路径上的异常集 步骤：步骤：（1）for i=1 to|RN|（1.1）oi=Get_one_Object(i，D)（1.2）NNS=Find_Neighbour_Nodes_Set(oi，ND，G)/从从G中搜索对象中搜索对象oi的邻域的邻域 （1.3）Accum_Dist=039 （1.4）for j=1 to|NNS|（1.4.1）ok=Get_one_Object(j，NNS)（1.4.2）Accum_Dist=F(oi，ok，)（1.5）Avg_Dist=Accum_Dist/|NNS|/计算对象计算对象oi的统计量的统计量 （1.6）Tvalue=(Avg_Dists)/s （1.7）if Check_Normal_Table(Tvalue，CI)=True then Add_Element(Outlier_Set，i)/查正态分布表查正态分布表（2）输出）输出Outlier_Set40