DataWhale组队学习活动

基于相似度的异常检测方法中，主要考虑异常点和正常点的相似度。相似度的度量有两种方式：基于距离的和基于密度的。

基于距离的度量

基于距离的度量通过最近邻距离来定义异常值，当某个点的k邻近距离远大于正常点时，它被定义为异常点。k邻近距离指的是在空间中离该点最近的k个邻居的平均距离。那么通常查找某个点的k邻近距离可以使用循环嵌套的方法。首先循环遍历每个数据，然后进行异常判断，计算当前点与其他点的距离，如果当前节点中有k个数据点与它的距离小于D，那么这个点就是非异常的。这种方法的时间复杂度为$O(N^{2})$，数据量较大时，可以使用修剪方法加快计算。
以下是两种修剪的方法：

1.基于单元的方法

数据空间被划分为单元格，单元格的宽度是阈值D和数据维数的函数。

2.基于索引的方法

利用多维索引结构(如 $\mathrm{R}$ 树、$k-d$ 树)来搜索每个数据对象 $A$ 在半径 $D$ 范围 内的相邻点。

基于密度的度量

基于密度的算法主要有局部离群因子(LocalOutlierFactor,LOF)，以及LOCI、CLOF等基于LOF的改进算法。

1.k-距离（k-distance(p)）

p点的k-距离就是p距离数据集的每一个点的距离中第k近的距离，就是k-距离。

2.k-邻域（k-distance neighborhood）

k-距离引申出k-邻域，k-邻域是一个集合，这个集合包含所有到点p的距离小于等于k-距离的所有点。

3.可达距离（reachability distance）

给定点p关于o的可达距离的计算取决于p是否在o的k-邻域内。如果p在o的k-邻域内，那么可达距离就是o的k-距离，如果不在k-邻域内，那么科大距离就是p和o的实际距离。

可达距离可以减少距离的计算开销，用一个阈值把需要计算的部分截断了，$k$的值越高，无需计算的邻近点越多，计算开销越小。但是另一方面，$k$的值变高，可能意味着可达距离变远，对集群点和离群点的区分度可能变低。因此，如何选择$k$值，是LOF算法能否达到效率与效果平衡的重要因素。

4.局部可达密度（local reachability density）

给定点p关于o的局部可达密度是p到o的k-邻域内所有点的可达距离平均值的导数。
计算时需要避免数据集内所有数据落在同一点上，此时可达距离之和为0，局部密度就是∞。

5.局部异常因子(LOF)

局部异常银子是通过每个点的局部可达密度和它们的k个邻点的局部可达密度进行比较，得到LOF。
LOF是对象p的邻居点o的局部可达密度的平均值与p的局部可达密度的比值。
LOF数值就是离群点分数。

数据的LOF值越高，通常会有更稀疏的邻居，更可能是异常点。