无监督的数据异常检测算法（2）- COF

1.COF-基于连通性的局部异常因子检测方法

在LOF中，$k$距离邻域默认是根据欧式距离来进行计算的，这样也间接性地假定了数据是以球形的方式分布在样本周围。但如果特征有一个直接线性相关，那这个密度的估算就会出现问题。在《Enhancing effectiveness of outlier detections for low density patterns》作者提出了COF-基于连通性的局部异常因子检测方法。

其使用一种称为链接距离的最短路径方法来估计邻域的局部密度。从数学上来讲，这个链接距离是连接所有$k$个近邻样本点的所有距离之和的最小值。对于特征明显线性相关的简单样本，这种密度估计方法的精度要高得多。

虽然COF克服了LOF算法对于序列数据和低密度数据对象不能有效度量的缺陷。但是由于COF增加了连接路径的建立，因此计算会比LOF更为复杂。

1.1 Enhancing effectiveness of outlier detections for low density patterns - 提高低密度模式离群点检测的有效性

介绍

基于密度的异常检测方案LOF，并未明确的将所检测的数据分为离群值与非离群值。如果需要划分的话，就需要人为给出阈值对其进行分隔。由于数据的LOF值是通过比较其与邻域的密度获得的，因此它比基于距离的方案具有更强的建模能力，基于距离的异常检测方案进对于数据本身的密度？？

”Algorithms for Mining Distance based Outliers in Large Datasets”-大数据中基于距离的异常值挖掘方法

基于密度的方案的弱点在于它只考虑了一个对象与其邻居的密度之间的差异。因此，如果异常值的密度接近其邻居数据点的密度，则其有效性就会降低。因此，本文提出一种基于连通性的离群因子（COF）方案，并说明COF相较于LOF在效率和性能上的改进。

提出问题

However,one weakness of the density based scheme is that it may rule out outliers close to some non-outliers pattern that has low density.

虽然基于密度的异常值检测方案很强大，然而，基于密度的方案的一个弱点是它可能会排出接近某些具有低密度的非异常值模式的异常值。

虽然高密度可以反映数据的逻辑形式，顺序或排列。但是它并不是必要条件，至少在当前文献定义的形式中是这样。因此，离群值并不总是比它所偏离的模式的密度低。如下图示例：

在上图中，$C_1$是一条直线型数据，在二维空间中密度较低。点$o_1$和$C_2$中的数据点是异常值。由于$o_1$偏离低密度模式，基于密度的异常值度量函数LOF将无法有效识别它，除非使用较小的$k$值。另一方面，使用太小的$k$将排除$C_2$中的异常值，也就是将$C_2$作为正常值，所以必须使用大于其基数的$k$值来识别异常值。所以，当LOF遇到这样分布的数据时，将无法很好饿进行离群点检测。

基于上述问题，通过COF进行解决。

COF概述

上述问题的解决方案基于区分“低密度”与“孤立性”的想法。低密度通常是指一个物体“近”邻域中的物体数量较少，而孤立性指的是一个物体与其它物体“连接”的程度。因此，隔离可能意味着低密度，但另一个方向并不总是正确的。如上放示例图中，点$o_1$是孤立的，而$C_1$中的任何点$p$都不是。但是它们有着相等的低密度。

在一般情况下，低密度离群值是偏离高密度模式的结果，而孤立的离群值是偏离连接模式的结果。离群值指标应该考虑到这种情况。

我们观察到具有低密度的团通常表现出低维结构，例如上图中$C_1$所示的图案是二维空间中的一条线。另一方面，一个数据点的孤立性可以用它到最近邻居点的距离进行描述。在一般情况下，我们还可以谈论一组对象的孤立性，即这一组数据与其最近邻居点的距离。

首先引入一些符号，然后再设定基于连通性的异常检测方法。

定义1：

$P,Q\subseteq \mathcal{D},P\cap Q=\varnothing\quad \text{and}\quad P,Q\ne \varnothing$，定义$dist(P,Q) = min\{dist(x,y):x\in P \& y\in Q\}$，将$dist(P,Q)$称为$P$和$Q$之间的距离。对于任何给定的$q\in Q$，如果存在$p\in P$使得$dist(p,q)=dist(P,Q)$，则称$q$是$Q$中$P$的最近邻。

在以下定义中，令$G=\{p_1,p_2,\cdots,p_r\}$是$\mathcal{D}$的子集。

定义2:

A set based nearest path, or SBN-path, from $p_1$ on $G$ is a sequence $<p_1,p_2,\cdots,p_r>$ such that for all $1\le i\le r-1$, $p_{i+1}$ is the nearest neighbor of set $\{p_1,\cdots,p_i\}$ in $\{p_{i+1},\cdots,p_r\}$

翻译不明白了=。=

假设一个集合最初只包含一个数据$p_1$，然后进入迭代扩展的过程。在每一次的迭代中，它都会在剩余对象中选择最近的邻居。如果它的最近邻居不是唯一的，我们可以在它的邻居之间加入一个预定义的顺序来打破距离相等的问题，因此SBN路径是唯一确定的。这里SBN路径表示最近的对象出现的顺序。

定义3:

令$s = <p_1,p_2,\cdots,p_r>$是SBN路径。关于$s$的基于集合的最近路径或SBN踪迹是一个序列$<e_1,\cdots e_{r-1}>$。对于所有满足$1\le i \le r-1$的$i$，$e_i = (o_i,p_{i+1})$，
其中$o_i \in \{p_1,p_2,\cdots,p_i\}$，并且$dist(e_i) = dist(o_i,p_{i+1})=dist(\{p_1,\cdots,p_i\},\{p_{i+1},\cdots,p_r\})$
我们称每一个$e_i$为一个边缘，称序列$<dist(e_1),\cdots,dist(e_{r-1})>$为序列$<e_1,\cdots,e_{r-1}>$的成本说明。

当SBN路径中某一次路径寻找中出现多个相同的邻居点，通过预先设定好的规则打破平局，SBN路径就是唯一的！

定义4:

令$s = <p_1,p_2,\cdots,p_r>$为从$p_1$开始的一个SBN路径，$e = <e_1,\cdots,e_{r-1}>$是$s$的SBN踪迹。用$ac-dist_G(p_1)$表示从$p_1$到$G-\{p_1\}$的平均链接距离，其定义为：

因为从$p_1$到$G-\{p_1\}$的平均链接距离是对来自$p_1$的一些SBN路径的SBN轨迹描述成本的加权和。因为本文中所述SBN路径为唯一路径，因此，将上述的平均链接距离进行定义明确：

在上式中，将求和符号后面的分式视为权重，那么平均链接距离可以被视为SBN轨迹的成本描述中的加权距离平均值。将较大的权重分配给较早的“terms”。因此，如果靠近$p_1$的边界实际上大于远离$p_1$的边，则它们在$ac-dist_G(p_1)$中的贡献更高。这与我们的动机是相同的。在边界的距离对于所有边界$e_i$都相同时，有$ac-dist_G(p_1)=dist(e_i)$

定义5:

令$p\in\mathcal{D}$和$k$都是一个正整数。$p$的相对于其$k$邻域的基于连通性的离群因子（COF）定义为：

$p$的连通性异常因子是$p$到$N_k(p)$的平均链接距离与$p$的$k$距离邻域到他们自己的$k$距离邻域的平均链接距离的平均值之比。

它表示一个点偏离一个模式有多远。

举例

以上图为例。数据点的分布模式是一条线，并且有两个离群点。

假设：$dist(1,2)=5,dist(2,7)=3$，直线上任意两个相邻的点之间的距离为1。令$k=10$。

我们现在计算三个样本点的平均链接距离，以此来显示这些样本点的COF值是如何以适当的方式反映“偏离模式”的。

对于点1：

第$k$距离邻域$N_k(1) = \{2,9,10,8,11,7,12,6,13,5\}$。

从点1到$N_k(1)\cup\{1\}$的SBN路径为：$s_1 = <1,2,7,6,5,8,9,10,11,12,13>$

这个SBN路径是怎么来的呢？这里就是通过SBN- Trail，也就是SBN路径的寻找轨迹而获得的。

从1开始，距离1最近的是2，第一步轨迹就是<1,2>，现在走到了2，下一步就是从2开始寻找下一步走到哪。

这里也就明白了，因为会存在在选择下一步走到哪时，从当前位置到多个点的距离相同，这里就需要通过提前制定的规则进行选择，以保证唯一路径。

当前点1的路径轨迹为：$tr_1 = <(1,2),(2,7),(7,6),(6,5),(7,8),(8,9),(9,10),(10,11),(11,12),(12,13)>$

文中的cost description的意思就是，路径中每一步的步长，文中使用的是$e_i$表示第$i$个轨迹，$dist(e_i)$就是轨迹的步长。

每一个轨迹的步长为：$c_1= <5,3,1,1,1,1,1,1,1,1>$

根据点$p$的平均链接距离定义：

此时对于点1，有：

$G$即$N_{k}(1)\cup\{1\}:\{1,2,9,10,8,11,7,12,6,13,5\}$

根据$G$中的元素数量可知$r = 11$

$dist(e_i)$即为$c_1$中的第$i$个元素。

计算可知：$ac-dist_{N_k(1)\cup\{1\}}(1) = 2.05$

同理计算点2的平均链接距离：$ac-dist_{N_k(2)\cup\{2\}}(2) = 1.46$

点7的平均链接距离：$ac-dist_{N_k(7)\cup\{7\}}(7) = 0.98$

可以同样地计算其它点的平均链接距离，对于偏离“模式”较多的点，例如点1，点2，其成本描述列表中的前几项往往比偏离较少的点的值更大。成本描述列表中的项目被赋予更大的权重，它们对相应的平均链接距离贡献更大，平均链接距离是成本描述中的值的加权和。

因此，强烈移动的点将比弱移动的点具有更大的平均链接距离。在一般情况下，强烈移动点的$k$距离邻域中的大多数点应该具有较小的平均链接距离。对于这种强烈移动的点，这会导致更大的基于连通性的异常因子。另一方面，对于弱偏移的点，其$k$距离邻域中的大多数点应该具有可比较的平均链接距离值，从而导致此类点的基于连通性的离群值较小。最薄弱的移动点是那些属于模式本身的点。它们基于连通性的离群影响因子应该接近。

COF计算步骤

1. 距离度量尺度

距离度量方式同1.2.1.2中介绍的距离度量方式

在下述内容中统一使用$d(A,B)$表示点$A$和点$B$之间的距离。根据定义，可以根据交换律得$d(A,B)=d(B,A)$

2. 第$k$距离

$d_k(O)$为点$O$的第$k$距离，$d_k(O) = d(O,P)$满足如下条件

• 在集合中至少存在$k$个点$P'\in D\{O\}$使得$d(O,P')\le d(O,P)$
• 在集合中至多存在$k-1$个点$P'\in D\{O\}$使得$d(O,P')<d(O,P)$

简而言之：点$P$是距离$O$最近的第$k$个点

3. $k$距离邻域

设$N_k(O)$为点$O$的第$k$距离邻域，满足：

此处的邻域表示的是具体的点，这个邻域集合中包含所有到点$O$的距离小于点$O$第$k$邻域距离的点。

4. 局部最短路径

从第$k$距离到$k$距离邻域，这两个步骤LOF与COF是相同的。当获取到$k$距离邻域之后COF则与LOF出现了不同。LOF是计算可达距离与局部可达密度。而基于连通性的局部异常因子COF则是计算局部最短路径。

A set based nearest path, or SBN-path, from $p_1$ on $G$ is a sequence $<p_1,p_2,\cdots,p_r>$ such that for all $1\le i\le r-1$, $p_{i+1}$ is the nearest neighbor of set $\{p_1,\cdots,p_i\}$ in $\{p_{i+1},\cdots,p_r\}$

对于所要计算基于连通性的局部离群因子的点$p_1$，所计算的范围为$k$邻域，即$N_k(p_1)$。局部最短路径的计算方式为：

1. 从点$p_1$开始在$N_k(p_1)$中寻找距离$p_1$最近的点$o$，即$\min{d(p_1,o)}$。
2. 再从点$o$开始不断通过最短的轨迹花费寻找下一个点，直到走遍$N_k(p_1)$。

行走的路径就是局部最短路径。

这里会出现两个问题

Q ：当出现有多个点可以选择的时候，该选择哪一个点？

A：原论文中所述为，定义一个规则来打破平局，是的最短路径具有唯一性。

Q：当出现不同方向，路径应该是什么样的？

A：像二叉树一样来确定最小的路径轨迹花费。

将从$p_1$开始获取到的路径记为$s = <p_1,p_2,\cdots,p_r>$

5. 局部最短路径轨迹花费

在寻找最短路径时，每走一步的步长$d(p_1,o)$即为轨迹花费。根据最短路径$s$的长度可知一共会有$r-1$步

将第$i$个轨迹花费记为$c_1:\{dist(e_1),\cdots,dist(e_i),\cdots,dist(e_{r-1})\}$

 

6. 局部平均链接距离

根据最短路径轨迹花费定义局部平均链接距离$ac-dist_G(p_1)$为：

此处的$G$即为$N_k(p_1)\cup \{p_1\}$，$r$即为$G$中的元素数量。

7. 基于连通性的局部离群因子

将点$p_1$的基于连通性的$N_k(p_1)$局部离群因子定义为：

其表达的意思即为：