关于人工智能:异常检测探索数据深层次背后的奥秘中篇

异样检测：摸索数据深层次背地的神秘《中篇》

1. 异样检测——线性相关办法

  实在数据集中不同维度的数据通常具备高度的相关性，这是因为不同的属性往往是由雷同的根底过程以密切相关的形式产生的。在古典统计学中，这被称为——回归建模 ，一种参数化的相关性剖析。
  一类相关性剖析试图通过其余变量预测独自的属性值，另一类办法用一些潜在变量来代表整个数据。前者的代表是 线性回归 ，后者一个典型的例子是 主成分剖析。本文将会用这两种典型的线性相关分析方法进行异样检测。

  须要明确的是，这里有两个重要的假如：

  假如一：近似线性相关假如。线性相关假如是应用两种模型进行异样检测的重要实践根底。

  假如二：子空间假如。子空间假如认为数据是镶嵌在低维子空间中的，线性办法的目标是找到适合的低维子空间使得异样点 (o) 在其中区别于失常点(n)。

  基于这两点假如，在异样检测的第一阶段，为了确定特定的模型是否适宜特定的数据集，对数据进行探索性和可视化剖析是十分要害的。

• 线性回归

  在线性回归中，咱们假如不同维度的变量具备肯定的相关性，并能够通过一个相关系数矩阵进行掂量。因而对于特定的观测值，能够通过线性方程组来建模。在理论利用中，观测值的数量往往远大于数据的维度，导致线性方程组是一个超定方程，不能间接求解。因而须要通过优化的办法，最小化模型预测值与实在数据点的误差。

  线性回归是统计学中一个重要的利用，这个重要的利用往往是指通过一系列自变量去预测一个非凡因变量的值。在这种状况下，异样值是依据其余自变量对因变量的影响来定义的，而自变量之间互相关系中的异样则不那么重要。这里的异样点检测次要用于数据降噪，防止异样点的呈现对模型性能的影响，因此这里关注的趣味点次要是正常值(n)。

  而咱们通常所说的异样检测中并不会对任何变量给与非凡看待，异样值的定义是基于根底数据点的整体散布，这里咱们关注的趣味点次要是异样值(o)。

狭义的回归建模只是一种工具，这种工具既能够用来进行数据降噪也能够进行异样点检测。

1.1 基于自变量与因变量的线性回归

1.1.1 最小二乘法

  为了简略起见，这里咱们一元线性回归为例:

$$Y=\sum_{i=1}^{d} a_{i} \cdot X_{i}+a_{d+1}$$

  变量 Y 为因变量，也就是咱们要预测的值；$X_{1}…X_{d}$ 为一系列因变量，也就是输出值。系数 $a_{1}…a_{d+1}$ 为要学习的参数。假如数据共蕴含 $N$ 个样本，第 $j$ 个样本蕴含的数据为 $x_{j1}…x_{jd}$ 和 $y_{j}$，带入式 (1) 如下式所示：

$$y_{j}=\sum_{i=1}^{d} a_{i} \cdot x_{j i}+a_{d+1}+\epsilon_{j}$$

  这里 $\epsilon_{j}$ 为第 $j$ 个样本的误差。以 $Y$ 代表 $N \times 1$ 的因变量矩阵 ${(y_{1}…y_{N})}^{T}$，即样本中的实在值；以 $U$ 代表 $N \times (d+1)$ 的自变量矩阵，其中第 $j$ 行为 $(x_{j1}…x_{jd}, 1)$；以 $A$ 代表 $(d+1) \times 1$ 的系数矩阵 $(a_{1}…a_{d+1})^{T}$。则模型可示意为：
$$f(U, A) = U \cdot A$$

  定义指标函数为：

$$L(A) = \frac{1}{2}{\left\| {Y – U \cdot A} \right\|^2} $$

  指标函数是对于 $A$ 的凸函数，其对 $A$ 求偏导为：

$$\frac{{\partial L(A)}}{{\partial A}} = \frac{1}{2}\frac{{\partial {{\left\| {Y – U \cdot A} \right\|}^2}}}{{\partial A}} = – {U^T}(Y – U \cdot A)$$

  令 $\frac{{\partial L(A)}}{{\partial A}}=0$，失去最优参数为：

$$A=\left(U^{T} \cdot U\right)^{-1} \cdot\left(U^{T} \cdot Y\right)$$

  这种求解线性回归参数的办法也叫 最小二乘法。

  最小二乘法要求矩阵 $U^{T} \cdot U$ 可逆，即 $U^{T} \cdot U$ 是满秩的。当 $U^{T} \cdot U$ 不可逆时能够通过两种办法进行参数估计，一种先应用主成分剖析等办法来预处理数据，打消不同特色之间的相关性，而后再应用最小二乘法。第二种办法是应用 梯度降落法。

1.1.2 梯度降落法

数据集

  监督学习个别靠数据驱动。咱们通常收集一系列的实在数据，例如多栋屋宇的实在售出价格和它们对应的面积和房龄。咱们心愿在这个数据下面寻找模型参数来使模型的预测价格与实在价格的误差最小。在机器学习术语里，该数据集被称为训练数据集（training data set）或训练集（training set），通常还应该有一个用于避免过拟合的穿插验证集和一个用于评估模型性能的测试集(test set)。一栋屋宇被称为一个样本（sample），其实在售出价格叫作标签（label），用来预测标签的两个因素叫作特色（feature）。

损失函数

  如果把线性回归看作是一个优化问题，那么咱们要优化的指标就是损失函数。损失函数是用来掂量样本误差的函数，咱们的优化指标是要求得在误差最小的状况下模型参数的值。这里强调一下损失函数和代价函数的区别：

留神：
Loss Function(损失函数)：the error for single training example;
Cost Function(代价函数)：the average of the loss functions of the entire training set;

  线性回归罕用的损失函数是均方误差，表达式为：

$$l^{(i)}(\mathbf{w}, b)=\frac{1}{2}\left(\hat{y}^{(i)}-y^{(i)}\right)^{2}$$

$$
L(\mathbf{w}, b)=\frac{1}{n} \sum_{i=1}^{n} l^{(i)}(\mathbf{w}, b)=\frac{1}{n} \sum_{i=1}^{n} \frac{1}{2}\left(\mathbf{w}^{\top} \mathbf{x}^{(i)}+b-y^{(i)}\right)^{2}
$$

  其中 $\hat{y}$ 为预测值，$y$ 为实在值。
优化算法 – 随机梯度降落

  当模型和损失函数模式较为简单时，下面的误差最小化问题的解能够间接用公式表达出来。这类解叫作解析解（analytical solution）。本节应用的线性回归和平方误差刚好属于这个领域。然而，大多数深度学习模型并没有解析解，只能通过优化算法无限次迭代模型参数来尽可能升高损失函数的值。这类解叫作数值解（numerical solution）。

  在求数值解的优化算法中，小批量随机梯度降落（mini-batch stochastic gradient descent）被宽泛应用。它的算法很简略：先选取一组模型参数的初始值，如随机选取；接下来对参数进行屡次迭代，使每次迭代都可能升高损失函数的值。在每次迭代中，先随机平均采样一个由固定数目训练数据样本所组成的小批量（mini-batch），而后求小批量中数据样本的均匀损失和无关模型参数的导数（梯度），最初用此后果与事后设定的学习率的乘积作为模型参数在本次迭代的减小量。如下式所示：

$$
(\mathbf{w}, b) \leftarrow(\mathbf{w}, b)-\frac{\eta}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \partial_{(\mathbf{w}, b)} l^{(i)}(\mathbf{w}, b)
$$

学习率 ($\eta$): 代表在每次优化中，可能学习的步长的大小
批量大小($B$): 是小批量计算中的批量大小 batch size

1.2 基于异样检测的线性回归

  前一节探讨了这样一种状况：即一个特定的变量被认为是非凡的，最优立体是通过最小化该非凡变量的均方误差而确定的。而咱们通常所说的异样检测中并不会对任何变量给与非凡看待，异样值的定义是基于根底数据点的整体散布，因而须要采纳一种更个别的回归建模：即以类似的形式看待所有变量，通过最小化数据对该立体的 投影误差 确定最佳回归立体。在这种状况下，假如咱们有一组变量 $X_{1}… X_{d}$，对应的回归立体如下：

$$a_{1} \cdot X_{1}+\ldots+a_{d} \cdot X_{d}+a_{d+1}=0$$

  为了后续计算的不便，对参数进行如下束缚：
$$\sum\limits_{i = 1}^d {a_i^2 = 1} $$
  以 $L_{2}$ 范数作为指标函数：
$$L = {\left\| {U \cdot A} \right\|_2}$$

  这样的一个问题能够通过主成分分析方法失去无效解决，咱们会独自用一个局部进行探讨。

2. 主成分剖析

  上一节的最小二乘法试图找到一个与数据具备最佳匹配 $(d−1)$ 维超平面。主成分分析方法可用于解决这一问题的狭义版本。具体来说，它能够找到任意 $k(k<d)$ 维的最优示意超平面，从而使平方投影误差最小化。

2.1 原理推导

  对于 $d$ 维，蕴含 $N$ 个样本的数据，用 $R_{i}$ 示意其中第 $i$ 行为：$[x_{i1}… x_{id}]$。由此能够失去 $d \times d$ 的协方差矩阵（规范的 PCA 该当计算相关系数矩阵，即对数据进行均值为 0 方差为 1 的标准化解决，而协方差矩阵只须要减去均值即可）:

$$Σ = (R – \bar{R})^{T} \cdot (R – \bar{R}) $$

  易知协方差矩阵 $Σ$ 是对称并且半正定的，因而能够进行类似对角化：

$$Σ = P \cdot D \cdot P^{T}$$

  这里的 $D$ 为对角矩阵，对角元素为特征值；$P$ 为规范正交矩阵，每一行为对应的特征向量；这些规范正交向量提供了数据应该投影的轴线方向。与异样检测相干的主成分剖析的次要性质如下：

• 如果前 $k$ 的特征向量选定之后（依据最大的 $k$ 个特征值），由这些特征向量定义的 $k$ 维超平面是在所有维度为 $k$ 的超平面中，所有数据点到它的均方间隔尽可能小的立体。
• 如果将数据转换为与正交特征向量对应的轴系，则转换后的数据沿每个特征向量维的方差等于相应的特征值。在这种新示意中，转换后的数据的协方差为 0。
• 因为沿特征值小的特征向量的转换数据的方差很低，因而沿这些方向的变换数据与平均值的显着偏差可能示意离群值。

  须要留神的是，相比 2.2 节的内容，这里提供了一个更加广泛的解决办法。2.2 中的内容能够归为主成分剖析中只保留最大特征值对应的特征向量的状况。

  在失去这些特征值和特征向量之后，能够将数据转换到新的坐标系中。以 $Y_{1}…Y_{N}$ 示意新坐标系中的数据，这些数据能够通过原始向量 $R_{i}$ 与蕴含新轴系的规范正交特征向量矩阵 $P$ 的乘积来实现。
$${Y_i} = {R_i} \cdot P$$

  在许多波及高维数据集的实在场景中，很大一部分特征值往往十分接近于零。这意味着大多数数据都沿着一个低维的子空间排列。从异样检测的角度来看，这是十分不便的，因为离这些投影方向十分远的观测值能够被假设为离群值。例如，对于特征值较小（方差较小）的特征向量 $j$，第 $i$ 条记录的 $y_{ij}$ 与 $y_{kj}$ 的其余值的偏差较大，阐明有离群行为。这是因为当 $j$ 固定而 $k$ 变动时，$y_{kj}$ 的值该当变动不大。因而，$y_{ij}$ 值是不常见的。

  在不选取任何特定的 $k$ 维汇合的状况下，一种更准确的异样检测建模办法是应用特征值来计算数据点沿每个主重量方向到质心的归一化间隔。设 $e_{j}$ 为第 $j$ 个特征向量，$λ_{j}$ 为沿该方向的方差(特征值)。数据点 $\bar{X}$ 绝对于对数据质心 $\bar{\mu} $ 的总体归一化异样得分能够由下式给出:

$$S \operatorname{core}(\bar{X})=\sum_{j=1}^{d} \frac{\left|(\bar{X}-\bar{\mu}) \cdot \bar{e}_{j}\right|^{2}}{\lambda_{j}}$$

  值得注意的是，对异样得分的大部分奉献是由 $λ_{j}$ 值较小的主成分的偏差提供的，这一点上文中有提及过。主成分剖析比因变量回归能更稳固地解决多数异样值的存在。这是因为主成分剖析是依据最优超平面来计算误差的，而不是一个特定的变量。当数据中退出更多的离群点时，最优超平面的变动通常不会大到影响离群点的抉择。因而，这种办法更有可能抉择正确的异样值，因为回归模型一开始就更精确。

2.2 归一化问题

  当不同维度的尺度差异较大时，应用 $PCA$ 有时并不能失去直观无效的后果。例如，思考一个蕴含年龄和工资等属性的人口统计数据集。工资属性的范畴可能是几万，而年龄属性简直总是小于 100，应用主成分剖析会导致主成分被高方差属性所管制。对于一个只蕴含年龄和工资的二维数据集，最大的特征向量简直与工资轴平行，这会升高异样点检测过程的有效性。因而，一个天然的解决方案是对数据进行均值为 0 方差为 1 的标准化解决。这隐含地导致在主成分剖析中应用相关矩阵而不是协方差矩阵。当然，这个问题并不是线性建模所独有的，对于大多数异样检测算法，都须要应用这样的预处理。

2.3、回归剖析的局限性

  回归剖析作为检测离群值的工具有一些局限性。这些毛病中最重要的是在本章的一开始就探讨了，其中探讨了回归剖析的数据特定性质。特地是，为了使回归剖析技术无效，数据须要高度相干，并沿着低维子空间对齐。当数据不相干，但在某些区域高度汇集时，这种办法可能不会无效。

  另一个相干的问题是，数据中的相关性在实质上可能不是全局性的。子空间相关性可能是特定于数据的特定地位的。在这种状况下，由主成分剖析发现的全局子空间对于异样检测是次优的。因而，为了创立更个别的部分子空间模型，有时将线性模型与邻近模型联合起来是有用的。

• 小结 总结

  实在数据中，数据不同属性之间往往具备显著的相关性。在这种状况下，线性建模能够提供一种无效的工具来从底层数据中移除异样值或者进行异样检测。对于其余基于因变量回归的利用，线性建模是一种工具，去除异样值对于进步此类利用的性能是十分重要的。在大多数状况下，主成分剖析提供了去除异样值和进行异样检测最无效的办法，因为它对存在多数异样值的数据更有鲁棒性。

• 参考资料

[1]《Outlier Analysis》——Charu C. Aggarwal

[2] Anomaly Detection: A Survey VARUN CHANDOLA, ARINDAM BANERJEE, and VIPIN KUMAR University of Minnesota

[3] Anomaly Detection: A Tutorial

[4] Data Mining Concepts and Techniques Third Edition

3. 异样检测——基于类似度的办法

“异样”通常是一个主观的判断，什么样的数据被认为是“异样”的，须要联合业务背景和环境来具体分析确定。
  实际上，数据通常嵌入在大量的噪声中，而咱们所说的“异样值”通常指具备特定业务意义的那一类非凡的异样值。噪声能够视作个性较弱的异样值，没有被剖析的价值。噪声和异样之间、失常数据和噪声之间的边界都是含糊的。异样值通常具备更高的离群水平分数值，同时也更具备可解释性。
  在一般的数据处理中，咱们经常须要保留失常数据，而对噪声和异样值的个性则根本疏忽。但在异样检测中，咱们弱化了“噪声”和“失常数据”之间的区别，专一于那些具备有价值个性的异样值。在基于类似度的办法中，次要思维是异样点的示意与失常点不同

3.1、基于间隔的度量

  基于间隔的办法是一种常见的实用于各种数据域的异样检测算法，它基于最近邻间隔来定义异样值。此类办法不仅实用于多维数值数据，在其余许多畛域，例如分类数据，文本数据，工夫序列数据和序列数据等方面也有宽泛的利用。
  基于间隔的异样检测有这样一个前提假如，即异样点的 $k$ 近邻间隔要远大于失常点。解决问题的最简略办法是应用嵌套循环。第一层循环遍历每个数据，第二层循环进行异样判断，须要计算以后点与其余点的间隔，一旦已辨认出多于 $k$ 个数据点与以后点的间隔在 $D$ 之内，则将该点主动标记为非异样值。这样计算的工夫复杂度为 $O(N^{2})$，当数据量比拟大时，这样计算是及不划算的。因而，须要修剪办法以放慢间隔计算。

3.1.1 基于单元的办法

  在基于单元格的技术中，数据空间被划分为单元格，单元格的宽度是阈值 D 和数据维数的函数。具体地说，每个维度被划分成宽度最多为 $\frac{D}{{2 \cdot \sqrt d}}$ 单元格。在给定的单元以及相邻的单元中存在的数据点满足某些个性，这些个性能够让数据被更无效的解决。

  以二维状况为例，此时网格间的间隔为 $\frac{D}{{2 \cdot \sqrt d}}$，须要记住的一点是，网格单元的数量基于数据空间的分区，并且与数据点的数量无关。这是决定该办法在低维数据上的效率的重要因素，在这种状况下，网格单元的数量可能不多。另一方面，此办法不适用于更高维度的数据。对于给定的单元格，其 $L_{1}$ 街坊被定义为通过最多 1 个单元间的边界可从该单元达到的单元格的汇合。请留神，在一个角上接触的两个单元格也是 $L_{1}$ 街坊。$L_{2}$ 街坊是通过逾越 2 个或 3 个边界而取得的那些单元格。上图中显示了标记为 $X$ 的特定单元格及其 $L_{1}$ 和 $L_{2}$ 街坊集。显然，外部单元具备 8 个 $L_{1}$ 街坊和 40 个 $L_{2}$ 街坊。而后，能够立刻察看到以下性质：

• 单元格中两点之间的间隔最多为 $D/2$。
• 一个点与 $L_{1}$ 邻接点之间的间隔最大为 $D$。
• 一个点与它的 $Lr$ 街坊 (其中 $r$ > 2) 中的一个点之间的间隔至多为 $D$。

  惟一无奈间接得出结论的是 $L_{2}$ 中的单元格。这示意特定单元中数据点的不确定性区域。对于这些状况，须要明确执行间隔计算。同时，能够定义许多规定，以便立刻将局部数据点确定为异样值或非异样值。规定如下：

• 如果一个单元格中蕴含超过 $k$ 个数据点及其 $L_{1}$ 街坊，那么这些数据点都不是异样值。
• 如果单元 $A$ 及其相邻 $L_{1}$ 和 $L_{2}$ 中蕴含少于 $k$ 个数据点，则单元 A 中的所有点都是异样值。

  此过程的第一步是将局部数据点间接标记为非异样值（如果因为第一个规定而导致它们的单元格蕴含 $k$ 个点以上）。此外，此类单元格的所有相邻单元格仅蕴含非异样值。为了充分利用第一条规定的修剪能力，确定每个单元格及其 $L_{1}$ 街坊中点的总和。如果总数大于 $k$，则所有这些点也都标记为非离群值。

  接下来，利用第二条规定的修剪能力。对于蕴含至多一个数据点的每个单元格 $A$，计算其中的点数及其 $L_{1}$ 和 $L_{2}$ 街坊的总和。如果该数字不超过 $k$，则将单元格 $A$ 中的所有点标记为离群值。此时，许多单元可能被标记为异样值或非异样值。

  对于此时仍未标记为异样值或非异样值的单元格中的数据点须要明确计算其 $k$ 最近邻间隔。即便对于这样的数据点，通过应用单元格构造也能够更快地计算出 $k$ 个最近邻的间隔。思考到目前为止尚未被标记为异样值或非异样值的单元格 $A$。这样的单元可能同时蕴含异样值和非异样值。单元格 $A$ 中数据点的不确定性次要存在于该单元格的 $L_{2}$ 街坊中的点集。无奈通过规定晓得 $A$ 的 $L_{2}$ 街坊中的点是否在阈值间隔 $D$ 内，为了确定单元 $A$ 中数据点与其 $L_{2}$ 街坊中的点集在阈值间隔 $D$ 内的点数，须要进行显式间隔计算。对于那些在 $L_{1}$ 和 $L_{2}$ 中不超过 $k$ 个且间隔小于 $D$ 的数据点，则声明为异样值。须要留神，仅须要对单元 $A$ 中的点到单元 $A$ 的 $L_{2}$ 街坊中的点执行显式间隔计算。这是因为已知 $L_{1}$ 街坊中的所有点到 $A$ 中任何点的间隔都小于 $D$，并且已知 $Lr$ 中 $(r> 2)$ 的所有点与 $A$ 上任何点的间隔至多为 $D$。因而，能够在间隔计算中实现额定的节俭。

3.1.2 基于索引的办法

  对于一个给定数据集，基于索引的办法利用多维索引构造 (如 $\mathrm{R}$ 树、$k-d$ 树) 来搜寻每个数据对象 $A$ 在半径 $D$ 范畴 内的相邻点。设 $M$ 是一个异样值在其 $D$ - 邻域内容许含有对象的最多个数，若发现某个数据对象 $A$ 的 $D$ - 邻域内呈现 $M+1$ 甚至更多个相邻点，则断定对象 $A$ 不是异样值。该算法工夫复杂度在最坏状况下为 $O\left(k N^{2}\right),$ 其中 $k$ 是数据集维数，$N$ 是数据集蕴含对象的个数。该算法在数据集的维数减少时具备较好的扩展性，然而工夫复杂度的估算仅思考了搜寻工夫，而结构索引的工作自身就须要密集简单的计算量。

3.2、基于密度的度量

  基于密度的算法次要有部分离群因子(LocalOutlierFactor,LOF)，以及 LOCI、CLOF 等基于 LOF 的改良算法。上面咱们以 LOF 为例来进行具体的介绍和实际。

  基于间隔的检测实用于各个集群的密度较为平均的状况。在下图中，离群点 B 容易被检出，而若要检测出较为靠近集群的离群点 A，则可能会将一些集群边缘的点当作离群点抛弃。而 LOF 等基于密度的算法则能够较好地适应密度不同的集群状况。

   那么，这个基于密度的度量值是怎么得来的呢？还是要从间隔的计算开始。相似 k 近邻的思路，首先咱们也须要来定义一个“k- 间隔”。

3.2.1 k- 间隔（k-distance(p)）：

  对于数据集 $D$ 中的给定对象 $p$，对象 $p$ 与数据集 $D$ 中任意点 $o$ 的间隔为 $d(p,o)$。咱们把数据集 $D$ 中与对象 $p$ 间隔最近的 $k$ 个相邻点的最远距离示意为 $k-distance(p)$，把间隔对象 $p$ 间隔第 $k$ 近的点示意为 $o_k$，那么给定对象 $p$ 和点 $o_k$ 之间的间隔 $d(p,o_k)=k − d i s t a n c e (p)$，满足：

• 在汇合 $D$ 中至多有不包含 $p$ 在内的 $k$ 个点 $o’$，其中 $o’∈D\{p\}$，满足 $d(p,o’)≤d(p,o_k)$
• 在汇合 $D$ 中最多有不包含 $p$ 在内的 $k-1$ 个点 $o’$，其中 $o’∈D\{p\}$，满足 $d(p,o’)<d(p,o_k)$

  直观一些了解，就是以对象 $p$ 为核心，对数据集 $D$ 中的所有点到 $p$ 的间隔进行排序，间隔对象 $p$ 第 $k$ 近的点 $o_k$ 与 $p$ 之间的间隔就是 k - 间隔。

3.2.2 k- 邻域（k-distance neighborhood）：

  由 k - 间隔，咱们扩大到一个点的汇合——到对象 $p$ 的间隔小于等于 k - 间隔的所有点的汇合，咱们称之为 k - 邻域：$N_{k − d i s t a n c e ( p)}(p) = {q ∈ D \backslash{ p} ∣ d (p , q) ≤ k − d i s t a n c e (p)}
$。

• k- 邻域蕴含对象 $p$ 的第 $k$ 间隔以内的所有点，包含第 $k$ 间隔点。
• 对象 $p$ 的第 $k$ 邻域点的个数 $ ∣ N_k(p)∣ ≥ k$。

  在二维立体上展现进去的话，对象 $p$ 的 k - 邻域实际上就是以对象 $p$ 为圆心、k- 间隔为半径围成的圆形区域。就是说，k- 邻域曾经从“间隔”这个概念延长到“空间”了。

3.2.3 可达间隔（reachability distance）：

  有了邻域的概念，咱们能够依照到对象 $o$ 的间隔远近，将数据集 $D$ 内的点依照到 $o$ 的间隔分为两类：

• 若 $p_i$ 在对象 $o$ 的 k - 邻域内，则可达间隔就是给定点 $p_i$ 对于对象 o 的 k - 间隔；
• 若 $p_i$ 在对象 $o$ 的 k - 邻域外，则可达间隔就是给定点 $p_i$ 对于对象 o 的理论间隔。

  给定点 $p_i$ 对于对象 $o$ 的可达间隔用数学公式能够示意为：

  $$r e a c h−d i s t_ k (p , o) = m a x \{k−distance( o) , d (p , o)\}$$。
  这样的分类解决能够简化后续的计算，同时让失去的数值区分度更高。

• $p_1$ 在对象 $o$ 的 k - 邻域内，$d (p_1 , o)<k−distance(o)$，

  可达间隔 $r e a c h−d i s t_ k (p_1 , o) = k−distance(o)$ ;

• $p_2$ 在对象 $o$ 的 k - 邻域外，$d (p_2 , o)>k−distance(o)$，

  可达间隔 $r e a c h−d i s t_ k (p_2 , o) = d (p_2 , o)$ ;

  留神：这里用的是 $p_k$ 与 $o$ 的间隔 $d(p_k,o)$ 与 $o$ 的 k - 间隔 $k−distance(o)$ 来进行比拟，不是与 $k−distance(p)$ 进行比拟！

  可达间隔的设计是为了缩小间隔的计算开销，$o$ 的 k - 邻域内的所有对象 $p$ 的 k - 间隔计算量能够被显著升高，相当于应用一个阈值把须要计算的局部“截断”了。这种“截断”对计算量的升高成果能够通过参数 $k$ 来管制，$k$ 的值越高，无需计算的邻近点越多，计算开销越小。然而另一方面，$k$ 的值变高，可能意味着可达间隔变远，对集群点和离群点的区分度可能变低。因而，如何抉择 $k$ 值，是 LOF 算法是否达到效率与成果均衡的重要因素。

3.2.4 部分可达密度（local reachability density）：

  咱们能够将“密度”直观地了解为点的汇集水平，就是说，点与点之间间隔越短，则密度越大。在这里，咱们应用数据集 $D$ 中对象 $p$ 与对象 $o$ 的 k - 邻域内所有点的可达间隔平均值的倒数（留神，不是导数）来定义部分可达密度。

  在进行部分可达密度的计算的时候，咱们须要防止数据集内所有数据落在同一点上，即所有可达间隔之和为 0 的状况：此时部分密度为∞，后续计算将无奈进行。LOF 算法中针对这一问题进行了如下的定义：对于数据集 $D$ 内的给定对象 $p$，存在至多 $MinPts(p)\geq1$ 个不同于 $p$ 的点。因而，咱们应用对象 $p$ 到 $o∈N_{MinPts}(p)$ 的可达间隔 $reach-dist_{MinPts}(p, o)$ 作为度量对象 $p$ 邻域的密度的值。

  给定点 p 的部分可达密度计算公式为：$$lrd_{MinPts}(p)=1/(\frac {\sum\limits_{o∈N_{MinPts}(p)} reach-dist_{MinPts}(p,o)} {\left\vert N_{MinPts}(p) \right\vert})$$

  由公式能够看出，这里是对给定点 p 进行度量，计算其邻域内的所有对象 o 到给定点 p 的可达间隔平均值。给定点 p 的部分可达密度越高，越可能与其邻域内的点 属于同一簇；密度越低，越可能是离群点。

3.2.5 部分异样因子：

  失去 lrd（部分可达密度）当前就能够将每个点的 lrd 将与它们的 k 个邻点的 lrd 进行比拟，失去部分异样因子 LOF。更具体地说，LOF 在数学上是对象 $p$ 的街坊点 $o$（$o∈N_{MinPts}(p)$）的 lrd 平均值与 $p$ 的 lrd 的比值。

  不难看出，$p$ 的部分可达密度越低，且它的 $MinPts$ 近邻的均匀部分可达密度越高，则 $p$ 的 LOF 值越高。

  如果这个比值越靠近 1，阐明 o 的邻域点密度差不多，o 可能和邻域同属一簇；如果这个比值小于 1，阐明 o 的密度高于其邻域点密度，o 为密集点；如果这个比值大于 1，阐明 o 的密度小于其邻域点密度，o 可能是异样点。

  由公式计算出的 LOF 数值，就是咱们所须要的离群点分数。

• 参考资料

[1]《Outlier Analysis》——Charu C. Aggarwal

[2] LOF: Identifying Density-Based Local Outliers

更多优质内容请关注公号：汀丶人工智能；会提供一些相干的资源和优质文章，收费获取浏览。