Datawhale组队学习【数据挖掘-异常检测-TASK4】
前言
异常检测TASK4主要内容：
1 理解基于距离的异常检测方法
2 掌握基于密度的LOF算法
内容来自datawhale组队学习讲义：
https://gitee.com/dreamzll/team-learning-data-mining/blob/master/AnomalyDetection/%E5%9B%9B%E3%80%81%E5%9F%BA%E4%BA%8E%E9%82%BB%E8%BF%91%E5%BA%A6%E7%9A%84%E6%96%B9%E6%B3%95.md
“异常”通常是一个主观的判断，什么样的数据被认为是“异常”的，需要结合业务背景和环境来具体分析确定。
实际上，数据通常嵌入在大量的噪声中，而我们所说的“异常值”通常指具有特定业务意义的那一类特殊的异常值。噪声可以视作特性较弱的异常值，没有被分析的价值。噪声和异常之间、正常数据和噪声之间的边界都是模糊的。异常值通常具有更高的离群程度分数值，同时也更具有可解释性。
在普通的数据处理中，我们常常需要保留正常数据，而对噪声和异常值的特性则基本忽略。但在异常检测中，我们弱化了“噪声”和“正常数据”之间的区别，专注于那些具有有价值特性的异常值。在基于相似度的方法中，主要思想是异常点的表示与正常点不同。
划重点：在异常检测中，我们弱化了“噪声”和“正常数据”之间的区别，专注于那些具有有价值特性的异常值。在基于相似度的方法中，主要思想是异常点的表示与正常点不同。
在异常检测算法中，有一类叫做基于近邻性的算法，它的思路是给定特征空间中的一组对象，用距离或密度测量来量化对象之间的相似度。与其他对象相距较远的对象可以被视为离群值。基于近邻性的方法假设离群值对象与其最近邻居的接近度与该对象与数据集中大多数其他对象的接近度有显著偏差。
基于近邻性的算法可以分为基于距离的方法（如果一个对象的邻居没有足够的点，则该对象为离群者）和基于密度的方法（如果一个对象的密度相对比邻居的密度低很多，则该对象为离群者）。
这里我们从距离和密度两个角度来表示数据，从而区分异常点和正常点。
一、基于距离的度量
基于距离的方法是一种常见的适用于各种数据域的异常检测算法，它基于最近邻距离来定义异常值。 此类方法不仅适用于多维数值数据，在其他许多领域，例如分类数据，文本数据，时间序列数据和序列数据等方面也有广泛的应用。
基于距离的异常检测有这样一个前提假设，即异常点的
k
k
k 近邻距离要远大于正常点。解决问题的最简单方法是使用嵌套循环。 第一层循环遍历每个数据，第二层循环进行异常判断，需要计算当前点与其他点的距离，一旦已识别出多于
k
k
k 个数据点与当前点的距离在
D
D
D 之内，则将该点自动标记为非异常值。 这样计算的时间复杂度为
O
(
N
2
)
O(N^{2})
O(N2)，当数据量比较大时，这样计算是及不划算的。 因此，需要修剪方法以加快距离计算。
该部分多偏于理论基础，主要是理解。
1.1 基于单元的方法
在基于单元格的技术中，数据空间被划分为单元格，单元格的宽度是阈值D和数据维数的函数。具体地说，每个维度被划分成宽度最多为
D
2
⋅
d
\frac{D}{{2 \cdot \sqrt d }}
2⋅d
D 单元格。在给定的单元以及相邻的单元中存在的数据点满足某些特性，这些特性可以让数据被更有效的处理。
以二维情况为例，此时网格间的距离为 D 2 ⋅ d \frac{D}{{2 \cdot \sqrt d }} 2⋅d D ，需要记住的一点是，网格单元的数量基于数据空间的分区，并且与数据点的数量无关。这是决定该方法在低维数据上的效率的重要因素，在这种情况下，网格单元的数量可能不多。 另一方面，此方法不适用于更高维度的数据。对于给定的单元格，其 L 1 L_{1} L1 邻居被定义为通过最多1个单元间的边界可从该单元到达的单元格的集合。请注意，在一个角上接触的两个单元格也是 L 1 L_{1} L1 邻居。 L 2 L_{2} L2 邻居是通过跨越2个或3个边界而获得的那些单元格。 上图中显示了标记为 X X X的特定单元格及其 L 1 L_{1} L1 和 L 2 L_{2} L2 邻居集。 显然，内部单元具有8个 L 1 L_{1} L1 邻居和40个 L 2 L_{2} L2 邻居。 然后，可以立即观察到以下性质：
- 单元格中两点之间的距离最多为 D / 2 D/2 D/2。
- 一个点与 L 1 L_{1} L1 邻接点之间的距离最大为 D D D。
- 一个点与它的 L r Lr Lr 邻居(其中 r r r > 2)中的一个点之间的距离至少为 D D D。
唯一无法直接得出结论的是 L 2 L_{2} L2 中的单元格。 这表示特定单元中数据点的不确定性区域。 对于这些情况，需要明确执行距离计算。 同时，可以定义许多规则，以便立即将部分数据点确定为异常值或非异常值。 规则如下：
- 如果一个单元格中包含超过 k k k 个数据点及其 L 1 L_{1} L1 邻居，那么这些数据点都不是异常值。
- 如果单元 A A A 及其相邻 L 1 L_{1} L1 和 L 2 L_{2} L2 中包含少于 k k k 个数据点，则单元A中的所有点都是异常值。
此过程的第一步是将部分数据点直接标记为非异常值（如果由于第一个规则而导致它们的单元格包含 k k k 个点以上）。 此外，此类单元格的所有相邻单元格仅包含非异常值。 为了充分利用第一条规则的修剪能力，确定每个单元格及其 L 1 L_{1} L1 邻居中点的总和。 如果总数大于 k k k ，则所有这些点也都标记为非离群值。
接下来，利用第二条规则的修剪能力。 对于包含至少一个数据点的每个单元格 A A A，计算其中的点数及其 L 1 L_{1} L1 和 L 2 L_{2} L2 邻居的总和。 如果该数字不超过 k k k，则将单元格 A A A 中的所有点标记为离群值。 此时，许多单元可能被标记为异常值或非异常值。
对于此时仍未标记为异常值或非异常值的单元格中的数据点需要明确计算其 k k k 最近邻距离。即使对于这样的数据点，通过使用单元格结构也可以更快地计算出 k k k 个最近邻的距离。考虑到目前为止尚未被标记为异常值或非异常值的单元格 A A A。这样的单元可能同时包含异常值和非异常值。单元格 A A A 中数据点的不确定性主要存在于该单元格的 L 2 L_{2} L2 邻居中的点集。无法通过规则知道 A A A 的 L 2 L_{2} L2 邻居中的点是否在阈值距离 D D D 内，为了确定单元 A A A 中数据点与其 L 2 L_{2} L2 邻居中的点集在阈值距离 D D D 内的点数，需要进行显式距离计算。对于那些在 L 1 L_{1} L1 和 L 2 L_{2} L2 中不超过 k k k 个且距离小于 D D D 的数据点，则声明为异常值。需要注意，仅需要对单元 A A A 中的点到单元 A A A的 L 2 L_{2} L2邻居中的点执行显式距离计算。这是因为已知 L 1 L_{1} L1 邻居中的所有点到 A A A 中任何点的距离都小于 D D D，并且已知 L r Lr Lr 中 ( r > 2 ) (r> 2) (r>2) 的所有点与 A A A上任何点的距离至少为 D D D。因此，可以在距离计算中实现额外的节省。
1.2 基于索引的方法
对于一个给定数据集，基于索引的方法利用多维索引结构(如 R \mathrm{R} R 树、 k − d k-d k−d 树)来搜索每个数据对象 A A A 在半径 D D D 范围 内的相邻点。设 M M M 是一个异常值在其 D D D -邻域内允许含有对象的最多个数，若发现某个数据对象 A A A 的 D D D -邻域内出现 M + 1 M+1 M+1 甚至更多个相邻点， 则判定对象 A A A 不是异常值。该算法时间复杂度在最坏情况下为 O ( k N 2 ) , O\left(k N^{2}\right), O(kN2), 其中 k k k 是数据集维数， N N N 是数据集包含对象的个数。该算法在数据集的维数增加时具有较好的扩展性，但是时间复杂度的估算仅考虑了搜索时间，而构造索引的任务本身就需要密集复杂的计算量。
二、基于密度的度量
基于密度的算法主要有局部离群因子(LocalOutlierFactor,LOF)，以及LOCI、CLOF等基于LOF的改进算法。下面我们以LOF为例来进行详细的介绍和实践。
先简单介绍一些概念：
2.1 k-距离（k-distance§）：
对于数据集 D D D中的给定对象 p p p，对象 p p p与数据集 D D D中任意点 o o o的距离为 d ( p , o ) d(p,o) d(p,o)。我们把数据集 D D D中与对象 p p p距离最近的 k k k个相邻点的最远距离表示为 k − d i s t a n c e ( p ) k-distance(p) k−distance(p)，把距离对象 p p p距离第 k k k近的点表示为 o k o_k ok，那么给定对象 p p p和点 o k o_k ok之间的距离 d ( p , o k ) = k − d i s t a n c e ( p ) d(p,o_k)=k − d i s t a n c e ( p ) d(p,ok)=k−distance(p)，满足：
- 在集合 D D D中至少有不包括 p p p在内的 k k k个点 o ′ o' o′，其中 o ′ ∈ D { p } o'∈D\{p\} o′∈D{p}，满足 d ( p , o ′ ) ≤ d ( p , o k ) d(p,o')≤d(p,o_k) d(p,o′)≤d(p,ok)
- 在集合 D D D中最多有不包括 p p p在内的 k − 1 k-1 k−1个点 o ′ o' o′，其中 o ′ ∈ D { p } o'∈D\{p\} o′∈D{p}，满足 d ( p , o ′ ) < d ( p , o k ) d(p,o')<d(p,o_k) d(p,o′)<d(p,ok)
直观一些理解，就是以对象 p p p为中心，对数据集 D D D中的所有点到 p p p的距离进行排序，距离对象 p p p第 k k k近的点 o k o_k ok与 p p p之间的距离就是k-距离。
2.2 k-邻域（k-distance neighborhood）：
由k-距离，我们扩展到一个点的集合——到对象
p
p
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 p p的第 k k k距离以内的所有点，包括第 k k k距离点。
-
对象 p p p的第 k k k邻域点的个数$ ∣ N_k§∣ ≥ k$。
在二维平面上展示出来的话，对象 p p p的k-邻域实际上就是以对象 p p p为圆心、k-距离为半径围成的圆形区域。就是说，k-邻域已经从“距离”这个概念延伸到“空间”了。
2.3 可达距离（reachability distance）：
有了邻域的概念，我们可以按照到对象 o o o的距离远近，将数据集 D D D内的点按照到 o o o的距离分为两类：
- 若 p i p_i pi在对象 o o o的k-邻域内，则可达距离就是给定点 p i p_i pi关于对象o的k-距离；
- 若
p
i
p_i
pi在对象
o
o
o的k-邻域外，则可达距离就是给定点
p
i
p_i
pi关于对象o的实际距离。
给定点 p i p_i pi关于对象 o o o的可达距离用数学公式可以表示为：
r
e
a
c
h
−
d
i
s
t
k
(
p
,
o
)
=
m
a
x
{
k
−
d
i
s
t
a
n
c
e
(
o
)
,
d
(
p
,
o
)
}
r e a c h−d i s t_ k ( p , o ) = m a x \{k−distance( o ) , d ( p , o )\}
reach−distk(p,o)=max{k−distance(o),d(p,o)} 。
这样的分类处理可以简化后续的计算，同时让得到的数值区分度更高。
如图：
-
p 1 p_1 p1在对象 o o o的k-邻域内， d ( p 1 , o ) < k − d i s t a n c e ( o ) d ( p_1 , o )<k−distance( o ) d(p1,o)<k−distance(o)，
可达距离 r e a c h − d i s t k ( p 1 , o ) = k − d i s t a n c e ( o ) r e a c h−d i s t_ k ( p_1 , o ) = k−distance( o ) reach−distk(p1,o)=k−distance(o) ;
-
p 2 p_2 p2在对象 o o o的k-邻域外， d ( p 2 , o ) > k − d i s t a n c e ( o ) d ( p_2 , o )>k−distance( o ) d(p2,o)>k−distance(o)，
可达距离 r e a c h − d i s t k ( p 2 , o ) = d ( p 2 , o ) r e a c h−d i s t_ k ( p_2 , o ) = d ( p_2 , o ) reach−distk(p2,o)=d(p2,o) ;
注意：这里用的是 p k p_k pk与 o o o的距离 d ( p k , o ) d(p_k,o) d(pk,o)与 o o o的k-距离 k − d i s t a n c e ( o ) k−distance( o ) k−distance(o)来进行比较，不是与 k − d i s t a n c e ( p ) k−distance( p ) k−distance(p)进行比较！
可达距离的设计是为了减少距离的计算开销， o o o的k-邻域内的所有对象 p p p的k-距离计算量可以被显著降低，相当于使用一个阈值把需要计算的部分“截断”了。这种“截断”对计算量的降低效果可以通过参数 k k k来控制， k k k的值越高，无需计算的邻近点越多，计算开销越小。但是另一方面， k k k的值变高，可能意味着可达距离变远，对集群点和离群点的区分度可能变低。因此，如何选择 k k k值，是LOF算法能否达到效率与效果平衡的重要因素。
2.4 局部可达密度（local reachability density）：
我们可以将“密度”直观地理解为点的聚集程度，就是说，点与点之间距离越短，则密度越大。在这里，我们使用数据集 D D D中对象 p p p与对象 o o o的k-邻域内所有点的可达距离平均值的倒数（注意，不是导数）来定义局部可达密度。
在进行局部可达密度的计算的时候，我们需要避免数据集内所有数据落在同一点上，即所有可达距离之和为0的情况：此时局部密度为∞，后续计算将无法进行。LOF算法中针对这一问题进行了如下的定义：对于数据集 D D D内的给定对象 p p p，存在至少 M i n P t s ( p ) ≥ 1 MinPts(p)\geq1 MinPts(p)≥1个不同于 p p p的点。因此，我们使用对象 p p p到 o ∈ N M i n P t s ( p ) o∈N_{MinPts}(p) o∈NMinPts(p)的可达距离 r e a c h − d i s t M i n P t s ( p , o ) reach-dist_{MinPts}(p, o) reach−distMinPts(p,o)作为度量对象 p p p邻域的密度的值。
给定点p的局部可达密度计算公式为： l r d M i n P t s ( p ) = 1 / ( ∑ o ∈ N M i n P t s ( p ) r e a c h − d i s t M i n P t s ( p , o ) ∣ N M i n P t s ( p ) ∣ ) lrd_{MinPts}(p)=1/(\frac {\sum\limits_{o∈N_{MinPts}(p)} reach-dist_{MinPts}(p,o)} {\left\vert N_{MinPts}(p) \right\vert}) lrdMinPts(p)=1/(∣NMinPts(p)∣o∈NMinPts(p)∑reach−distMinPts(p,o))
由公式可以看出，这里是对给定点p进行度量，计算其邻域内的所有对象o到给定点p的可达距离平均值。给定点p的局部可达密度越高，越可能与其邻域内的点 属于同一簇；密度越低，越可能是离群点。
2.5 局部异常因子：
得到lrd（局部可达密度）以后就可以将每个点的lrd将与它们的k个邻点的lrd进行比较，得到局部异常因子LOF。更具体地说，LOF在数学上是对象 p p p的邻居点 o o o（ o ∈ N M i n P t s ( p ) o∈N_{MinPts}(p) o∈NMinPts(p)）的lrd平均值与 p p p的lrd的比值。
不难看出， p p p的局部可达密度越低，且它的 M i n P t s MinPts MinPts近邻的平均局部可达密度越高，则 p p p的LOF值越高。
如果这个比值越接近1，说明o的邻域点密度差不多，o可能和邻域同属一簇；如果这个比值小于1，说明o的密度高于其邻域点密度，o为密集点；如果这个比值大于1，说明o的密度小于其邻域点密度，o可能是异常点。
由公式计算出的LOF数值，就是我们所需要的离群点分数。
三、实践
LOF算法可以用sklearn 或 pyod 两类库进行构建，下面将从代码角度介绍具体实现方法：
构造数据集，随机抽样组成训练集
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.neighbors import LocalOutlierFactor
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus']=False
pd.set_option('display.max_columns', None)
pd.set_option('display.max_rows', None)
np.random.seed(61)
# 构造两个数据点集群
X_inliers1 = 0.2 * np.random.randn(100, 2)
X_inliers2 = 0.5 * np.random.randn(100, 2)
# np.r_ 将 两个 array 拼接
X_inliers = np.r_[X_inliers1 + 2, X_inliers2 - 2]
# 构造一些离群的点
# numpy.random.uniform(low,high,size)
# 从一个均匀分布[low,high)中随机采样，注意定义域是左闭右开 size是 数量
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)
# 打标签，群内点构造离群值为1，离群点构造离群值为-1
ground_truth[-n_outliers:] = -1
训练集数据可视化
plt.title('构造数据集 (LOF)')
plt.scatter(X[:-n_outliers, 0], X[:-n_outliers, 1], color='b', s=5, label='集群点')
plt.scatter(X[-n_outliers:, 0], X[-n_outliers:, 1], color='orange', s=5, label='离群点')
plt.axis('tight')
plt.xlim((-5, 5))
plt.ylim((-5, 5))
legend = plt.legend(loc='upper left')
legend.legendHandles[0]._sizes = [10]
legend.legendHandles[1]._sizes = [20]
使用LocalOutlierFactor函数开始训练
# 训练模型（找出每个数据的实际离群值）
clf = LocalOutlierFactor(n_neighbors=20, contamination=0.1)
# 对单个数据集进行无监督检测时，以1和-1分别表示非离群点与离群点
y_pred = clf.fit_predict(X)
# 找出构造离群值与实际离群值不同的点
n_errors = y_pred != ground_truth
X_pred = np.c_[X,n_errors]
X_scores = clf.negative_outlier_factor_
# 实际离群值有正有负，转化为正数并保留其差异性（不是直接取绝对值）
X_scores_nor = (X_scores.max() - X_scores) / (X_scores.max() - X_scores.min())
X_pred = np.c_[X_pred,X_scores_nor]
X_pred = pd.DataFrame(X_pred,columns=['x','y','pred','scores'])
X_pred_same = X_pred[X_pred['pred'] == False]
X_pred_different = X_pred[X_pred['pred'] == True]
预测结果可视化
plt.title('局部离群因子检测 (LOF)')
plt.scatter(X[:-n_outliers, 0], X[:-n_outliers, 1], color='b', s=5, label='集群点')
plt.scatter(X[-n_outliers:, 0], X[-n_outliers:, 1], color='orange', s=5, label='离群点')
# 以标准化之后的局部离群值为半径画圆，以圆的大小直观表示出每个数据点的离群程度
plt.scatter(X_pred_same.values[:,0], X_pred_same.values[:, 1],
s=1000 * X_pred_same.values[:, 3], edgecolors='c',
facecolors='none', label='标签一致')
plt.scatter(X_pred_different.values[:, 0], X_pred_different.values[:, 1],
s=1000 * X_pred_different.values[:, 3], edgecolors='violet',
facecolors='none', label='标签不同')
plt.axis('tight')
plt.xlim((-5, 5))
plt.ylim((-5, 5))
legend = plt.legend(loc='upper left')
legend.legendHandles[0]._sizes = [10]
legend.legendHandles[1]._sizes = [20]
一些因为随机原因散落在集群内部的“离群点”也被识别为集群内部的点，但是一些与集群略为分散的“集群点”则被识别为离群点。
参考：https://zhuanlan.zhihu.com/p/345677102
四、总结
在基于相似度的方法中，主要思想是异常点的表示与正常点不同。通过对数据使用LOF算法，区分异常点，比一些统计规则更加准确，避免了更多的误判。