无监督的数据异常检测算法（3）- INFLO

1. INFLO原论文

Ranking Outliers Using Symmetric Neighborhood Relationship

1.1 综述（Abstract）

挖掘数据集中的异常值是为了找到偏离数据集其余部分的异常对象。除了经典的异常值分析算法之外，最近的研究还集中在挖掘局部异常值，即密度分布与其邻域显著不同的异常值。迄今为止，对于目标对象处密度分布的估计一直基于其$k$最近邻的密度分布，如LOF，然而，当离群点位于邻域内密度分布明显不同的位置时，例如，稀疏簇中的对象接近密集簇的情况，这可能会导致错误估计。为了避免这个问题，我们在这里提出了一种简单但有效的基于对称邻域关系的局部异常值度量。所提出的方法在估计其密度分布时同时考虑对象的邻居和反向邻居，正因如此，发现的异常值更有意义。

1.2 介绍（Introduce）

基本上，离群值被定义为在某种程度上偏离数据集其余部分的异常对象。如网络入侵可能会导致在低流量时段内的网络事件数量出现显著峰值，但是当比较中还包括高网络流量时段时，那么低流量时段的峰值就会显得微不足道。鉴于此，局部异常值的检测就有了很明显的意义。（LOF的叙述不再介绍），对于LOF局部异常值检测中，如果出现一些更为复杂的情况，其异常值的判断并不能成立，如下图所示：

示例: 考虑上图中的情况，其中$p$实际上是靠近密集簇$C_1$的稀疏簇$C_2$的一部分。与对象$q$和$r$相比，$p$明显表现出更小的离群值。但是如果使用LOF中提出的度量方式，在下述的两种情况中$p$可能会被错误地认为具有更强的离群值：

情况1: 对象$p$和$q$的最近邻对象密度相同，但$q$比$p$更接近簇$C_1$。在这种情况下，$p$将具有比$q$更强的异常值度量，这显然是错误的。

情况2: 虽然$r$的密度低于$p$，但其相邻的对象（由来自$C_2$的两个对象和一个异常值组成）的平均密度小于$p$。因此，当计算LOF离群值时，$p$可能会比$r$有更高的离群值，这也是错误的。

一般来说，位于两个集群之间边界附近的任何对象都可能被上述情况进行错误的异常值检测。

从上述的例子中可以看出，现有的离群值度量并不容易适用于数据集包含多个密度分布差异很大的簇类的复杂情况。造成上述问题的原因在于对物体邻域密度分布的估计不准确。在上图中，虽然$p$属于簇类$C_2$，但是它更接近簇类$C_1$，因此$p$的邻域密度分布估计来自$C_1$而不是$C_2$。

为了更好地估计邻域的密度分布，我们建议同时考虑最近邻(NN)和反向最近邻(RNN)。对象$p$的RNN本质上是将$p$做为其$k$最近邻之一的对象。通过考虑NN和RNN的对称邻域关系，可以很好地确定一个对象受其它对象影响的空间，合理地估计其邻域的密度从而使得异常值更有意义。在下图中可以说明NN与RNN的作用：

图中表明对象$p$有两个RNN：$s$和$t$，这将对象$p$与没有RNN的对象$q$和只有异常值作为其RNN的$r$区分开来。

INFLO的贡献：

1. 建议基于对称邻域关系挖掘异常值。所提出的方法在估计其邻域密度分布时考虑了对象的最近邻居和反向最近邻居的影响空间。
2. 为数据集中的每个对象分配被影响异常值（INFLO）的程度。INFLOw越高，这个对象越有可能是异常值。INFLO越低，这个对象越有可能是集群的成员。具体来说，$INFLO\approx 1$表示对象位于集群的核心部分。
3. 提出了几种有效的算法来挖掘基于INFLO的前$n$个异常值。为了减少大量KNN和RNN搜索产生的庞大计算，通过在搜索过程中动态修剪INFLO=1的对象，开发了一种双向搜索方法。此外，利用微集群技术压缩数据集以进行高效的对称查询，并使用两阶段修剪方法修剪掉那些永远不会出现在前$n$个异常值中的对象。
4. 对合成数据集和真实数据进行了全面的性能评估和分析，其表明本文所述方法不仅在性能上高效且可扩展，而且在对有意义的异常值进行排名方面也很有效。

通过对称关系影响离群值的度量

介绍新的度量与其相关属性。对于一些符号做出说明。令$D$表示大小为$N$的数据集，$p,q,o$表示数据集$D$中的一些对象，$k$为正整数，并使用$d(p,q)$表示对象$p$和$q$之间的欧式距离。

定义一：$k$距离和对象$p$的最近邻

$k-distance$ Of p（$p$的$k$距离）表示为$k_{dist}(p)$，是数据集$D$中对象$p$和点$o$之间的距离$d(p,o)$，其使得：

1. 至少对于$k$个对象$o'\in D$，有$d(p,o')\le d(p,o)$。
2. 至多对于$(k-1)$个对象$o'\in D$，有$d(p,o')<d(p,o)$。

对象$p$的$k$近邻$NN_k(p)$是数据集$D$的子集$X$，有$d(p,X)\le k_{dist}(p):NN_k(p)=\{X\in D ;\{p\}|d(p,X)\le k_{dist}(p)\}$

定义二：对象$p$的局部密度

对象$p$的局部密度表示为$den(p)$，是$p$的$k$距离的倒数：

尽管$p$的$k$最近邻（$NN_k(p)$）可能不唯一，但是$k_{dist}(p)$是唯一的。因此，$p$的密度也是唯一的。最近邻关系不是对称的。对于给定的$p$，其最近邻居可能没有$p$是最近邻的邻居之一。因此引入反向最近邻的概念如下。

定义三：对象$p$的反向最近邻

反向最近邻RNN是一个逆关系，可以将其定义为$RNN_k(p)=\{q|q\in D,p\in NN_k(p)\}$。

对于任何对象$p\in D$，$NN_k(p)$的搜索总是会返回$k$个结果，然而RNN可以为空或是有一或多个元素。通过一种方式将$NN_k(p)$和$RNN_k(p)$组合在一起，就形成了一个用于估计对象$p$周围的密度分布的局部邻域空间。将这个邻域空间称为$p$的$k$影响空间，记为：$IS_k(p)$。

定义四：$p$的$INFLO$

$p$的$INFLO$定义为：

其中：

INFLO是$k$影响空间$IS_k(p)$的平均密度与对象$p$的局部密度之比，如果对象$p$的密度远低于其影响空间中对象的平均密度，那么其INFLO值将会很高。从这个意义上来说，对象$p$是一个异常值当$INFLO_k(p)>t,and \quad t\gg 1$。另一方面，当密度非常接近时，他们的影响空间的$INFLO\approx 1$。