开发者学堂课程【高校精品课北京理工大学数据仓库与数据挖掘(下)：Proximity-Base Approaches】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1041/detail/15656
Proximity-Base Approaches
内容介绍：
一、基于距离的异常检测算法
二、基于密度的异常检测算法变量
本课程开始数据仓库与数据挖掘的学习。在这一部分，将介绍基于邻近性的异常检测方法。基于邻近性的异常检测方法，主要包含基于距离的异常检测方法和基于密度的异常检测方法。
一、基于距离的异常检测算法
1.概念
首先来看一下基于距离的异常检测算法。基于距离的异常检测算法主要是根据一个数据对象，它某个特定领域范围内数据对象的个数来判断这个数据对象是否是异常，如果它这个领域内的数据对象个数比较多，那么这个数据对象就是正常的，否则就是异常的。
2.参数
在基于距离的异常检测算法中，需要使用到两个参数，一个是r，也就是用户指定的距离阈值，距离阈值就确定了数据对象的领域范围。第二个参数指的是∏把它称之为叫做比比率阈值，它主要是用来衡量某个数据对象，它特定领域范围内的数据对象的个数占全体数据对象个数的比率。
对于一个数据对象 o。如果在它以 r 为半径的领域范围内的邻居数目。和所有数据集的数目的比率。将一个对象判断成为异常的，指的是在给定参数 r 和∏的条件下，如果这个对象为圆心，以 r 为半径的领域范围内的邻居的数目，在全体数据对象数目的比率小于等于∏，认为这个数据对象是异常的。
和这种方法计算相似的，还可以去计算数据对象到它的第 k 个最近邻邻居的距离，如果这个数据对象到它的第 k 个最近邻邻居的距离大于 r，就认为这个数据对象是异常的。其中，它的k的值是用∏全于数据集中数据对象的数目。
3.缺点
基于距离的异常检测算法有一个缺点，就是它很难去识别局部异常。所谓的局部异常，就指的是这个数据对象和它的邻居相比是异常的，但是和全局数据对象来比，那么它的异常性就不那么显着。
4.例子
通过一个例子介绍局部异常以及解释为什么基于距离的异常检测算法不能够有效识别局部异常，在下图展示的是两个蔟，c1 蔟和 c2 蔟。可以看到明显的 C1 这个蔟的密度是比较稠密的，而 c2 蔟的密度是比较稀疏的。对于对象 o3 它离蔟 c1 和 c2 都很远，认为 o3 是一个异常对象，对于对象 o4 大家可以看到它基本上是在位于 c2 的这个分布范围，那么它应该是一个正常对象，但是对于对象 o1 和 o2。它和蔟 c1 相比，它的密度分布是非常非常稀疏的，所以 o 1，o 2 应该是相对于蔟 c1 来说是一场对象。
但是如果使用基于距离的异常检测算法，那么可以发现。O1 和 o2 对象的最邻近距离都会包含 c1 中的数据对象，那么也就是它的距离是比较小的，因为 c1 的分布是比较稠密的，那么它的距离往往会比 c2 这个蔟中某些数据对象的距离要想，比如对于 o4 这样的一个对象来说。所以如果想把 o1 和 o2 对象在基于距离的异常检测算法中把它判别为异常对象，就需要调整阈值，那么调整阈值的结果是所有 c2 中数据对象有可能会被全部判定为异常对象。那么，基于这样的一个考虑，一个最直接的想法就是，可以将数据对象和它邻居的密度进行对比。那如果这个数据对象它邻居的密度比这个数据对象的密度要高很多，就认为这个数据对象是异常的。
二、基于密度的异常检测算法变量
那么，基于这样的一个想法，就设计了基于密度的异常检测算法。在基于密度的异常检测算法，会去对每一个数据点进行局部异常评分，这个局部异常评分主要是根据比较这个数据对象的密度和它邻居的密度来进行得到的。基于密度的异常检测算法中，需要计算的变量比较多。
1. 数据对象 o 的 k 距离
那么首先第一个就是数据对象 o 的k距离，把它称之为叫做 distk（o），就指的是数据对象 o 到它第 k 个最近邻邻居的距离。
2. 数据对象 o 的 k 距离邻域
那么第二个变量就是数据对象 o 的 k 距离邻域。对象 o 的 k 距离邻域就指的是离这个数据对象的距离小于等于 distk（o）的所有数据对象的集合。那么注意，对象o 的 k 距离邻域的数目可能会大于k，因为在对象 o 的 distk（o）邻域范围内可能会有一些数据对象到 o 的距离是相等的。
3.局部可达密度
那么第三个，需要计算的变量称之为从对象 o’到 o 的可达距离。从对象 o’到 o的可达距离，就指的是 distk（o）和 distk（o’）之间的最大值。用下图的这张事例介绍，比如对于对象 o1 来说。它和另外一个对象 p 之间的距离是要大于 o 的distk（o），所以说它的可达距离，就是对象 o1 和对象，p 之间的距离，那对于这个对象 o2 来说，那么这个对象 o2 和 p 之间的距离，是要远远的小于这个对象o2 的 k 距离，所以就认为，从 p 到对象 o2 的可达距离，就是这个对象 o2 的 k 距离。那么在计算对象的 k 距离之后可以计算一个数据对象的局部可达密度，那么下图是局部可达密度的计算公式，那么可以把它颠倒，发过来看一下，这样的一个局部可达密度其实就是某一个数据对象，它所有邻居到这个对象的可达距离的平均值，对象 o 的局部可达密度，就是这个对象所有邻居到这个项可达距离平均值的导数。
4.局部异常因子
在计算了每个数据对象的局部可达密度之后，就可以计算每一个数据对象的局部异常因子，局部异常因子简称 lof 就是对每一个数据对象的异常评分，那么它的计算公式可以看一下下图公式部分，它的含义就是指的是这个数据对象，所有邻居的局部可达密度和这个对象局部可达密度比值的均值。
对于 lof 直来说，如果这个值越高的话，就意味着它的周围邻居的密度要比这个对象要高很多，那么这个数据对象的异常评分就越高，它为异常的可能性就越高，那么如果这个评分越低的话，那么就意味着这个数据对象它的密度比较高，那么它的这样的一个 lof 值就会比较低，就意味着这个数据对象为异常的可能性比较低。
基于邻近性的异常检测算法，就介绍到这里。
