机器学习丨离群点检测算法 LOF 及其 Python 实践

背景

离群点检测算法具有非常强的实际意义和广泛的应用前景，包括欺诈检测、网络性能和活动监控等等。

📢 离群点和噪声有区别：噪声是观测值的随机误差和方差；离群点属于观测值，可能是真实数据产生或者噪声产生，整体而言是和大部分观测值明显不同的观测值。

本文主要学习下基于密度的离群点检测方法中最具有代表性的算法：局部离群因子检测算法 (Local Outlier Factor, LOF) ^[1]。

LOF 算法

基于密度的离群点检测方法基本假设：非离群点对象周围的密度与其邻域周围的密度类似，而离群点对象周围的密度显著不同于其邻域周围的密度。 如下图所示：

局部离群因子检测算法 LOF 是一种典型的基于密度的高精度离群点检测方法，通过给每个数据点都分配一个依赖于邻域密度的离群因子 $LOF$ ，进而判断该数据点是否为离群点。若 $LOF\gg 1$ ，则该数据点为离群点；若 $LOF \approx 1$ ，则该数据点为正常数据点。

假设当前的样本集合 $D$ 包含 $n$ 个数据点，其数据维度为 $m$ ，数据点表示为

$\forall X_{i}=\left(x_{i 1}, x_{i 2}, \cdots, x_{i m}\right) \in R \quad i=1,2, \cdots, n$

LOF 算法需要度量不同数据点间的距离 $d(X_i, X_j)= d(X_j, X_i)$ ，至于距离度量可以采用欧式距离、汉明距离、马氏距离等等。为了简明仅给出欧式距离计算公式如下：

$d_{\text{Euclid}}\left(X_{i}, X_{j}\right)=\sqrt{\sum_{k=1}^{m}\left(X_{i k}-X_{j k}\right)^{2}}$

在介绍 LOF 算法前先引用几个重要的概念 ^[2]。

第 $k$ 距离

定义：设 $d_k(O)$ 为数 $O$ 的第 $k$ 距离

$d_k(O)= d(O, P)$

即：点 $P$ 是距离点 $O$ 最近的第 $k$ 个点。

$k$ 距离邻域

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

$N_{k}(O)=\left\{P^{\prime} \in D \backslash\{O\} \mid d\left(O, P^{\prime}\right) \leq d_{k}(O)\right\}$

即： $D \backslash\{O\}$ 中所有到点 $O$ 距离不大于 $d_k(O)$ 的点集合。

可达距离

定义：以点 $O$ 为中心，点 $P$ 到点 $O$ 的第 $k$ 可达距离定义为

$d_{k}(P, O)=\max \left\{d_{k}(O), d(P, O)\right\}$

即：点 $P$ 到点 $O$ 的第 $k$ 可达距离至少为 $d_k(O)$ ，距离 $O$ 最近的 $k$ 个点到 $O$ 的可达距离被认为是相等的为等于 $d_k(O)$ 。

局部密度可达

定义：局部密度可达为

$\rho_{k}(P)=\frac{1}{\sum_{O \in N_{k}(P)} d_{k}(P, O) /\left|N_{k}(P)\right|}=\frac{\left|N_{k}(P)\right|}{\sum_{O \in N_{k}(P)} d_{k}(P, O)}$

即：点 $P$ 的第 $k$ 邻域内所有点到 $P$ 的平均可达距离。如果 $P$ 和周围邻域点是同一簇，那么可达距离越可能为较小的 $d_k(O)$ ，导致可达距离之和越小，局部可达密度越大。如果 $O$ 和周围邻域点较远，那么可达距离可能会取较大值 $d(P, O)$ ，导致可达距离之和越大，局部可达密度越小。

📢 注意：关于局部可达密度的定义其实暗含假设，即：不存在大于等于 $k$ 个重复的点，这些重复点的平均可达距离为零，局部可达密度就变为无穷大。解决方法是可以将可达距离加上非常小的值。

根据以上定义，LOF 计算公式如下

$L O F_{k}(P)=\frac{\sum_{O \in N_{k}(P)} \frac{\rho_{k}(O)}{\rho_{k}(P)}}{\left|N_{k}(P)\right|}$

即：点 $P$ 的邻域 $N_k(P)$ 内其他点的局部可达密度与点 $P$ 的局部可达密度之比的平均数。如果这个比值越接近 1，说明 $O$ 的邻域点密度差不多， $O$ 可能和邻域同属一簇；如果这个比值小于1，说明 $O$ 的密度高于其邻域点密度为密集点；如果这个比值大于 1，说明 $O$ 的密度小于其邻域点密度可能是异常点。

LOF 算法需要计算数据点对间的距离，整个算法时间复杂度为 $O(n^2)$ 。为了提高算法效率，FastLOF^[3] 算法对其进行改进。主要思路先将数据集划分为多个子集，再分别计算 LOF 分数，剔除异常分数小于 1 的再进行计算，详情可以参考原文。

Python 实践

为了方便此处直接采用 Scikit-learn 中提供的包测试算法效果。

采用人工生成的离群点数据测试，代码如下所示：

# Generate train data
X_inliers = 0.3 * np.random.randn(100, 2)
X_inliers = np.r_[X_inliers + 2, X_inliers - 2]

# Generate some outliers
X_outliers = np.random.uniform(low=-4, high=4, size=(20, 2))
X = np.r_[X_inliers, X_outliers]

n_outliers = len(X_outliers)
ground_truth = np.ones(len(X), dtype=int)
ground_truth[-n_outliers:] = -1

clf = LocalOutlierFactor(n_neighbors=20, contamination=0.1)

y_pred = clf.fit_predict(X)
n_errors = (y_pred != ground_truth).sum()
X_scores = clf.negative_outlier_factor_

plt.title("Local Outlier Factor (LOF)")
plt.scatter(X[:, 0], X[:, 1], color="k", s=3.0, label="Data points")
# plot circles with radius proportional to the outlier scores
radius = (X_scores.max() - X_scores) / (X_scores.max() - X_scores.min())
plt.scatter(
    X[:, 0], X[:, 1], s=1000 * radius, edgecolors="r", facecolors="none", label="Outlier scores"
)
plt.axis("tight")
plt.xlim((-5, 5))
plt.ylim((-5, 5))
plt.xlabel("prediction errors: %d" % (n_errors))
legend = plt.legend(loc="upper left")
legend.legendHandles[0]._sizes = [10]
legend.legendHandles[1]._sizes = [20]
plt.show()

对应的实验结果如下：

M. M. Breunig, H. P. Kriegel, R. T. Ng, J. Sander. LOF: Identifying Density-based Local Outliers SIGMOD, 2000. ↩︎
https://zhuanlan.zhihu.com/p/37753692 ↩︎
M. Goldstein. FastLOF: An Expectation-Maximization based Local Outlier detection algorithm. ICPR, 2012 ↩︎