介绍#

局部离群因子算法（Local Outlier Factor, LOF） 是一种基于密度比的方法，用于检测数据中的离群点。与以往的离群点检测算法不同，该算法从局部角度考虑，通过密度比来判断数据点是否为离群点。核心思路为： 在规定了局部区域后，离群点区域的密度与周围区域的密度有着较大的差别，因此，通过计算待检测点区域密度与周围区域密度的比值，即可判断该点是否为离群点，如下图：

可以明显看出，点B周围的密度较点A周围的密度显著较低，且距离点群较远，因此可以判断点B为离群点（异常点）。在实际应用中离群点的局部密度也显著低于邻居的局部密度，根据这个特性，我们可以判断一个点是否为离群点。

前置知识#

KNN——K邻近算法#

KNN（K Nearest Neighbors） 是一个监督学习分类算法，可以用于分类，也可以用于回归。具体思路为：

确地k值——找距离待检测点最近k个邻居点，k值不同，最终得到的结果也不同
确定距离计算方法，常用的有：

前置背景
设点 $A(x_1,x_2,x_3,……,x_n)$ ，点 $B(y_1,y_2,y_3,……,y_n)$
1. 欧氏距离(Euclidean Distance)： $d_{ab} = \sqrt{(x_1-y_1)^2 + (x_2 - y_2)^2 + \cdots +(x_n-y_n)^2}$
  
  最常用的距离度量，表示两点之间的直线距离。适用于连续数值型特征，但对特征尺度敏感。
2. 曼哈顿距离(Manhattan Distance)： $d_{ab} = |x_1-y_1| + |x_2-y_2| + \cdots + |x_n-y_n|$
  
  也称为城市街区距离，计算各维度绝对差值的和。在高维空间中比欧氏距离更稳定。
3. 切比雪夫距离(Chebyshev Distance)： $d_{ab} = \max\limits_i |x_i - y_i|$
  
  定义为各维度坐标差的最大值。常用于棋盘问题，相当于国际象棋中王的移动距离。
4. 闵可夫斯基距离(Minkowski Distance)： $d_{ab} = (\sum\limits_{i=1}^n |x_i - y_i|^p)^{\frac{1}{p}}$
  
  这是一个距离度量的一般形式：
  - 当 $p=1$ 时，退化为曼哈顿距离
  - 当 $p=2$ 时，退化为欧氏距离
  - 当 $p \to \infty$ 时，趋近于切比雪夫距离
5. 余弦相似度(Cosine Similarity)： $\cos(\theta) = \frac{\sum\limits_{i=1}^n x_i y_i}{\sqrt{\sum\limits_{i=1}^n x_i^2} \sqrt{\sum\limits_{i=1}^n y_i^2}}$
  
  衡量两个向量方向的相似度，而非距离大小。常用于文本分析和推荐系统。
选择建议
- 特征连续且尺度一致：优先考虑欧氏距离
- 特征稀疏或高维：余弦相似度或曼哈顿距离效果更好
- 对异常值敏感：曼哈顿距离比欧氏距离更鲁棒
- 数据需要标准化：使用距离度量前，建议对特征进行归一化或标准化处理
这里由于数据集是简单的二维点集，故使用欧式距离作为距离计算的方法。
计算找到待检测点的K邻近点，然后根据这些邻近点完成想要的操作如预测类别。这里只使用这些邻近点来计算密度

第K距离（K-Distance）#

对于数据集中的任意点P，将其到所有其他数据点的距离按升序排列：

d_{(1)} \leq d_{(2)} \leq \cdots \leq d_{(k)} \leq \cdots \leq d_{(n)}

则第k个距离值 $d_{(k)}$ 称为点P的第k距离，记作 $k\_distance(P)$ 。也就是以P为圆心， $k\_distance(P)$ 为半径画圆，圆内恰好包含k个点（含边界上的点）。

例子：#

假设有点P，其他点按到P的距离排序为：[1.2, 1.5, 1.8, 2.3, 2.7, 3.1, …]

当k=3时：

第1近邻：距离1.2 <- 第1距离
第2近邻：距离1.5 <- 第2距离
第3近邻：距离1.8 <- 第3距离
第5近邻：距离2.7 <- 第5距离

相应的，第k距离也就是第k近邻点距离点P的距离。

第K邻域（K-Distance Neighborhood）#

任取一点P，距离点P的距离小于等于第k距离的所有点的集合，即为第K邻域，记作 $N_k(P)$ 。使用数学表示如下：

N_k(P)=\{Q \in D \setminus \{P\} \mid d(P,Q) \leq k\_distance(P)\}

其中：

D代表整个数据集
$D \setminus \{P\}$ 表示集合D去除子集{P}后的集合，也就是 $D - (D \cap \{P\})$
$k\_diatance(P)$ 表示点P的第k距离
$d(P,Q)$ 表示P和Q的距离

用图表示：

可达距离（Reachability Distance）#

设点O为待检测点，点P为O的第K邻域内的点，则点O与点P的可达距离为：

reach-dist_k(P,O) = \max(k-distance(P),d(P,O))

也就是点 O 到 P 的距离与点 P 的第 k 距离中的较大值。

算法原理#

局部可达密度（Local Reachability Density)#

和平常的密度计算方式相似，局部可达密度（LRD）的计算公式为：

LRD_k(P) = \frac {\left | N_k(P) \right | }{\sum_{O\in N_k(P)}{reach-dist_k(P,O)}}

其中：

$N_k(P)$ 为点P的第k邻域， $\left | N_k(P) \right |$ 表示邻域内的邻居数量
$reach-dist_k(P,Q)$ 为点P与Q的可达距离

局部利群因子（Local Outlier Factor）#

这是LOF算法最重要的部分，整个算法根据此值来判离群点。思想为：

Info

利群点的局部可达密度一定与正常点的局部可达密度有差异，因此可以通过计算待检测点的第k邻域内的点的局部可达密度与待检测点局部可达密度密度的比值来判断待检测点是否是离群点。

为了确保没有偶然性，计算待检测点第k邻域内的全部点的局部可达密度与待检测点局部可达密度的比值，然后取其平均值做为最终的检测标准，可以在较大程度上鉴别离群点。

注意

注意，此图仅供教学使用，虚线圆圈出的范围不代表第k邻域，这里只是为了表示方便以让读者真切感受到基于密度的局部利群因子判断离群点的效果。真实的第k邻域如下：

如上图所示，通过局部可达密度可以很好的找出离群点，局部异常因子的计算方式如下：

LOF_k(P) = \frac {\sum_{O \in N_k(P)}{\frac {LRD_k(O)}{LRD_k(P)}}}{\left | N_k(P) \right |}

其中：

P为待检测点，O为点P的第k邻域的点
$N_k(P)$ 为点P的第k邻域， $\left | N_k(P) \right |$ 表示邻域内的邻居数量

通常认为， $LOF_k(P)$ 这个比值越大于1，表明p点的密度越小于其周围点的密度，p点越可能是离群点；这个比值越小于1，表明p点的密度越大于其周围点的密度，p点越可能是正常点。

算法流程#

1. 确定超参k值#

k值对于LOF非常重要，当 k 较小时，LOF 的局部密度估计不稳定，对噪声敏感，容易导致正常点被误判为离群点；当 k 较大时，局部信息被削弱，异常点可能被周围正常点淹没，从而难以被检测出来。

通常对于中小数据来说，k值在10~20左右较为合理，在此之后，随着数据量地增多以及维度的增大，k值需要适度增大，与此同时可以使用多个k值或者k值区间进行测试，选取效果最好，最稳定的即可。

2. 计算可达密度#

首先使用KNN找到待检测点的第k邻域，然后计算待检测点的可达密度。

对于待检测点第k邻域内的所有点也做和待检测点相同的处理，先找到第k邻域，然后计算可达密度。

3. 计算局部离群因子#

通过LOF的计算公式：

LOF_k(P) = \left ( \frac {\left | N_k(P) \right |}{\sum_{O \in N_k(P)}{\frac {LRD_k(O)}{LRD_k(P)}}} \right ) ^ {-1}

计算待检测点的局部离群因子，然后根据经验，一般来说LOF显著大于1时，认为其为离群点。

Python实现代码#

手动实现#

借助numpy可以使用向量化高效地编写

1
import numpy as np
2

3

4
class LOF:
5
    """
6
    Local Outlier Factor (LOF)
7
    """
8

9
    def __init__(self, k=10):
10
        self.k = k
11
        self.lof_scores_ = None
12
        self.labels_ = None
13

14
    def _compute_distance_matrix(self, X):
15
        """
16
        计算欧式距离矩阵
17
        """
18
        sum_X = np.sum(X ** 2, axis=1)
19
        # 使用完全平方公式开
20
        sq_dists = sum_X[:, np.newaxis] + sum_X - 2 * np.dot(X, X.T)
21
        dist_matrix = np.sqrt(np.maximum(sq_dists, 0)) # 避免浮点数的精度误差导致负数出现
22
        return dist_matrix
23

24
    def _get_k_neighbors(self, dist_matrix):
25
        """
26
        获取k邻域
27
        """
28
        # 填充对角线，避免自己成为自己的邻居
29
        np.fill_diagonal(dist_matrix, np.inf)
30
        # 对每行进行排序，获取前k个邻居的索引
31
        sorted_indices = np.argsort(dist_matrix, axis=1)
32
        knn_indices = sorted_indices[:, :self.k]
33
        # 获取第 k 个邻居的距离 (k-distance)
34
        k_distances = dist_matrix[np.arange(dist_matrix.shape[0]), knn_indices[:, -1]]
35

36
        return knn_indices, k_distances
37

38
    def _compute_reachability_distance(self, dist_matrix, knn_indices, k_distance):
39
        """
40
        计算可达距离
41
        """
42
        # 获取每个点到其k个邻居的真实欧式距离
43
        # dist_matrix shape: (n, n), knn_indices shape: (n, k)
44
        # result shape: (n, k)
45
        dist_to_neighbors = np.take_along_axis(dist_matrix, knn_indices, axis=1)
46

47
        # 获取每个邻居点的 k-distance
48
        # k_distance shape: (n,), knn_indices shape: (n, k)
49
        # 我们需要查找 knn_indices 中每个索引对应的 k_distance
50
        # result shape: (n, k)
51
        k_dist_of_neighbors = k_distance[knn_indices]
52

53
        # 计算可达距离: max(k_distance(neighbor), distance(i, neighbor))
54
        reach_dist = np.maximum(k_dist_of_neighbors, dist_to_neighbors)
55

56
        return reach_dist
57

58
    def _compute_lrd(self, reach_dist):
59
        """
60
        计算局部可达密度 (Vectorized)
61
        """
62
        # 加上小常数防止除以0
63
        lrd = 1.0 / (np.mean(reach_dist, axis=1) + 1e-10)
64
        return lrd
65

66
    def _compute_lof(self, lrd, knn_indices):
67
        """
68
        计算LOF值
69
        LOF(A) = avg(LRD(neighbors) / LRD(A))
70
        """
71
        # 获取每个点邻域内所有点的 LRD
72
        # lrd shape: (n,), knn_indices shape: (n, k)
73
        # result shape: (n, k)
74
        lrd_neighbors = lrd[knn_indices]
75

76
        # 将邻居的 LRD 除以 自身的 LRD
77
        # 利用广播机制: (n, k) / (n, 1)
78
        lrd_ratios = lrd_neighbors / lrd[:, np.newaxis]
79

80
        # 求平均值得到 LOF
81
        lof = np.mean(lrd_ratios, axis=1)
82
        return lof
83

84
    def fit(self, X):
85
        """
86
        训练模型
87
        """
88
        X = np.array(X)
89
        n_samples = X.shape[0]
90
        if self.k >= n_samples:
91
            raise ValueError(f"k ({self.k}) must be smaller than the number of samples ({n_samples}).")
92

93
        # 距离矩阵
94
        dist_matrix = self._compute_distance_matrix(X)
95
        # k邻域及第k距离
96
        knn_indices, k_distance = self._get_k_neighbors(dist_matrix)
97
        # 可达距离
98
        reach_dist = self._compute_reachability_distance(
99
            dist_matrix,
100
            knn_indices,
101
            k_distance
102
        )
103

104
        # LRD
105
        self.lrd_ = self._compute_lrd(reach_dist)
106
        # LOF
107
        self.lof_scores_ = self._compute_lof(self.lrd_, knn_indices)
108

109
        return self
110

111
    def fit_predict(self, X, threshold=1.5):
112
        """
113
        训练并预测，默认LOF分数大于1.5的点被认为是离群点
114
        """
115
        self.fit(X)
116

117
        # 初始化标签，1为正常，-1为异常
118
        labels = np.ones(len(self.lof_scores_))
119
        labels[self.lof_scores_ > threshold] = -1
120

121
        self.labels_ = labels
122
        return labels

sklearn API#

1
from sklearn.neighbors import LocalOutlierFactor
2

3
lof = LocalOutlierFactor(n_neighbors=10)
4
sklearn_labels = lof.fit_predict(X)

两者对比#

测试代码:

1
if __name__ == '__main__':
2
    import matplotlib.pyplot as plt
3

4
    np.random.seed(0)
5
    # 正常数据
6
    normal = np.random.normal(0, 1, (200, 2))
7
    # 异常数据
8
    outliers = np.random.uniform(-6, 6, (20, 2))
9
    X = np.vstack([normal, outliers])
10

11
    model = LOF(k=10)
12
    labels = model.fit_predict(X)
13
    print(f"手动实现的LOF预测LOF分数前10：{model.lof_scores_[:10]}")
14

15
    plt.scatter(X[:, 0], X[:, 1], c=labels)
16
    plt.title("Manually LOF Outlier Detection")
17
    plt.show()
18

19
    from sklearn.neighbors import LocalOutlierFactor
20
    lof = LocalOutlierFactor(n_neighbors=10)
21
    sklearn_labels = lof.fit_predict(X)
22
    print(f"Sklearn LOF预测前10：{lof.negative_outlier_factor_[:10]}")
23
    plt.scatter(X[:, 0], X[:, 1], c=sklearn_labels)
24
    plt.title("Sklearn LOF Outlier Detection")
25
    plt.show()

运行结果：

运行结果：

1
手动实现的LOF预测LOF分数前10：[1.21976091 1.52021709 1.45510191 0.99129674 0.96082814 1.07181726
2
 0.95758032 1.03500003 1.34157547 1.04033416]
3

4
Sklearn LOF预测前10：[-1.21976091 -1.52021709 -1.45510191 -0.99129674 -0.96082814 -1.07181726
5
 -0.95758032 -1.03500003 -1.34157547 -1.04033416]

Note

Sklearn使用的是 $-LOF$ 值，为了和直觉一直（分数越低异常程度越高）而取 $LOF$ 的相反数

常见疑问及解答（Q&A）#

问：为什么要引入可达距离，直接使用距离不行吗？

答：不行。假设检测异常点P且有极少数点非常非常靠近点P，这时如果采用直接距离，局部可达密度（LRD）的计算公式会变为
$LRD_k(P) = \frac {\left | N_k(P) \right | }{\sum_{O\in N_k(P)}d(P,O)}$
易知 $LRD_k(P)$ 会异常变大，进而导致 $LOF_k(P)$ 会变的非常非常接近0，而根据我们规定的判别条件，此时认为点P是正常点，但实际上P为异常点，这就产生了错误。这种情况称为密度爆炸，如下图（点P为异常点，为方便起见已只绘制点P及其k邻域）所示：

密度爆炸

从图中可以看除有两三个点及其接近点P，而其余点距离点P较远，因此 $\sum_{O \in N_k(P)}{d(O,P)}$ 会被少数及其接近点P的点拉小，从而影响最终的检测结果。

而使用可达距离正是为了解决这个问题，我们规定最小的距离为 $distance_k(P)$ ，从而保证了 $\sum_{O\in N_k(P)}{reach-dist_k(P,O)}$ 不会异常偏小，进而保证了最终检验结果的准确性及正确性。

缺点#

对k值（邻居数）非常敏感
计算复杂度太高，时间复杂度为 $O(n^2)$ ，这在较大规模数据集中无法接受
高维数据效果差：距离趋于相似且局部密度难以区分

我与我周旋久，宁作我

离群点检测——局部离群因子算法

介绍#

前置知识#

KNN——K邻近算法#

第K距离（K-Distance）#

例子：#

第K邻域（K-Distance Neighborhood）#

可达距离（Reachability Distance）#

算法原理#

局部可达密度（Local Reachability Density)#

局部利群因子（Local Outlier Factor）#

算法流程#

1. 确定超参k值#

2. 计算可达密度#

3. 计算局部离群因子#

Python实现代码#

手动实现#

sklearn API#

两者对比#

常见疑问及解答（Q&A）#

缺点#

参考资料#

文章分享

目录