无监督的数据异常检测算法（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，并未明确的将所检测的数据分为离群值与非离群值。如果需要划分的话，就需要人为给出阈值对其进行分隔。
”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)。局部最短路径的计算方式为：
- 从点p_1开始在N_k(p_1)中寻找距离p_1最近的点o，即\min{d(p_1,o)}。
- 再从点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)局部离群因子定义为：
其表达的意思即为：