异常检测算法之LOF

向右看齐 2022-09-10 10:15 368阅读 0赞

# 前言： #

LOF：Local outlier factor，即局部异常因子。LOF主要是通过比较每个点p和其邻域点的密度来判断该点是否为异常点，如果点p的密度越低，越可能被认定是异常点。至于密度，是通过点之间的距离来计算的，点之间距离越远，密度越低，距离越近，密度越高，完全符合我们的理解。而且，因为lof对密度的计算是通过点的k邻域来计算，而不是全局计算，因此得名为“局部”异常因子。**即LOF是基于密度分析，通过局部的数据密度来检测异常。**

# 原理 #

LOF算法，**是基于密度的离群点检测方法中一个比较有代表性的算法**。**该算法会给数据集中的每个点计算一个离群因子LOF，通过判断LOF是否接近于1来判定是否是离群因子。若LOF远大于1，则认为是离群因子，接近于1，则是正常点**。

为了叙述LOF算法，首先引入以下概念：  
**（1）对象p的k距离（距离对象p最近的第k个对象的距离）**  
对于正整数k，对象p的k距离可记作k-distance§。在样本空间中，存在对象o，它与对象p之间的距离记做d(p,o)。如果满足以下两个条件，我们则认为k-distance§=d(p,o)：  
1)在样本空间中，至少存在k个对象q，使得d(p,q)<=d(d,o)；  
2)在样本空间中，至多存在k-1个对象q，使得d(p,q)<d(p,o)。  
k−distance§=max||p−o||（样本o和p的最大距离即p的k邻域的最大距离）  
显然易见，如果使用k−distance§来量化对象p的局部空间区域范围，**那么对于对象密度较大的区域，k−distance§值较小，而对象密度较小的区域，k−distance§值较大。**

**（2）对象p的第k距离领域**  
已经对象p的第k距离，那么，与对象p之间距离小于等于k−distance§的对象集合称为对象p的第k距离领域，记作：Nk§  
该领域其实是以p为中心， k−distance§为半径的区域内所有对象的集合（不包括p本身）。由于可能同时存在多个第k距离的数据，因此该集合至少包括k个对象。可以想象，离群度越大的对象的范围往往比较大，而离群度比较小的对象范围小。  
**（3）对象p相对于对象o的可达距离**  
公式：reachdist(p,o)=max\{k−distance(o),||p−o||\}  
公式的理解可以参考下图，对于两个不同的点p1和p2，它们的可达距离计算是不一样的，对p1来说，因为p1 在 o 的 k 邻域内(可以看出这里的k=3)，所以它们的距离就是 k-distance(o) 的距离，也就是等于圆的半径；而对于p2，很明显它不在o的k邻域内，所以它的可达距离就是实际距离，也就是这两点之间的距离。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbm9ib2R5fg_size_18_color_FFFFFF_t_70_g_se_x_16]  
**（4）局部可达密度**  
对象p的局部可达密度定义为p的k最近邻点的平均可达距离的倒数（实质也就是p的第k距离邻域内所有可达距离的平均值的导数。越大越好，代表数据聚的越紧凑）  
![在这里插入图片描述][4a93b5246862466290910e343e87b5e8.png]  
**（5）局部离群点因子**  
![在这里插入图片描述][1f3aced7c1a24282a373f0d973f82749.png]  
如果这个比值越接近1，说明p和其K距离邻域内的点密度差不多，p可能和其K距离邻域内的点同属一簇；如果这个比值越小于1，说明p的密度高于其邻域内其他点的密度，p为密集点；如果这个比值越大于1，说明p的密度小于其邻域内其他点的密度，p越可能是异常点。通过这种方式就能在样本空间数据分布不均匀的情况下也可以准确发现离群点。  
**可以想象下，一个离群点p，它的lrdk(o)是远大于lrdk§的，通过特例很容易看出，这样该算法就可以很好的理解了**

## 优缺点 ##

**优点：**  
LOF算法是一种非监督算法  
LOF算法是一种基于密度的算法  
LOF算法适合于对不同密度的数据的异常检测

**缺点：**  
检测的数据必须有明显的密度差异  
计算比较复杂  
应用场景有限

## 调参 ##

LOF(self, n_neighbors=20, algorithm='auto', leaf_size=30,
        metric='minkowski', p=2, metric_params=None,
        contamination=0.1, n_jobs=1)
    
    n_neighbors：（int，optional （default = 20 ）） - 默认情况下用于kneighbors查询的邻居数。如果n_neighbors大于提供的样本数，则将使用所有样本。
    
    Algorithm：（{ ‘auto’ ，‘ball_tree’ ，‘kd_tree’ ，‘brute’} ，可选） -
    用于计算最近邻居的算法：
    'ball_tree’将使用BallTree
    'kd_tree’将使用KDTree
    'brute’将使用蛮力搜索。
    'auto’将尝试根据传递给fit()方法的值来确定最合适的算法。
    注意：在稀疏输入上拟合将使用强力来覆盖此参数的设置。
    
    leaf_size：（int，optional （default = 30 ）） - 传递给BallTree或KDTree的叶子大小。
    这可能会影响构造和查询的速度，以及存储树所需的内存。最佳值取决于问题的性质。
    
    Metric：（字符串或可调用，默认’minkowski’） -用于距离计算的度量。
    from scikit-learn: [‘cityblock’, ‘cosine’, ‘euclidean’, ‘l1’, ‘l2’, ‘manhattan’]
    from scipy.spatial.distance: [‘braycurtis’, ‘canberra’, ‘chebyshev’, ‘correlation’, ‘dice’, ‘hamming’, ‘jaccard’, ‘kulsinski’, ‘mahalanobis’, ‘matching’, ‘minkowski’, ‘rogerstanimoto’, ‘russellrao’, ‘seuclidean’, ‘sokalmichener’, ‘sokalsneath’, ‘sqeuclidean’, ‘yule’]
    
    p：（整数，可选（默认值= 2 ）） - 来自sklearn.metrics.pairwise.pairwise_distances的Minkowski度量的参数。
    当p = 1时，这相当于使用manhattan_distance（l1）。
    对于p = 2使用euclidean_distance（l2）。
    对于任意p，使用minkowski_distance（l_p)

# 总结 #

经实践，发现该算法在面对数据量较大的场景时，执行效率较低。作为基于密度的算法，效果比KNN要好，面对适当的场景，可以尝试法使用。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbm9ib2R5fg_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/225114e817f842cca1cda427bf641c0d.png
[4a93b5246862466290910e343e87b5e8.png]: /images/20220829/1315ebffeb274d7c8e3dad1a942c7fba.png
[1f3aced7c1a24282a373f0d973f82749.png]: /images/20220829/352eabcc21e44ed19d08c2d421caced5.png