异常检测—task 04 基于相似度的方法

 数据通常被嵌入在大量的噪声中，而我们所说的“异常值”通常指那些具有特定也无意义的哪一类特殊的异常值，噪声可以被视为较弱的异常值，没有被分析的价值。噪声与异常之间、正常数据和噪声之间的边界都是模糊的。异常值通常具有更高的利群程度分数值，同时也更具有可解释性。
 在普通数据的处理中，我们常常需要保留正常数据，而对噪声和异常值的特性基本忽略，但在异常检测中，我们弱化了“噪声”和“正常数据”之间的区别，专注于那些具有价值特性的异常值，但在基于相似度的方法中，主要思想是异常点的表示与正常点不同。

基于距离的度量

  基于距离的方法是一种常见的适用于各种数据域的异常检测算法，它基于最近邻距离来定义异常值。此类方法不仅适用于多维数值数据，在其他许多淋雨，例如分类数据、文本数据、时间序列数据等方面也有广泛的应用。
 基于距离的异常话内测有这样一个前提假设，即异常点的 k k k近邻距离要远大于正常点。解决问题的最简单方法是采用嵌套循环。第一层循环遍历每个数据，第二层循环进行异常判断，需要计算当前点与其他点的距离，一旦已识别出多于 k k k个数据点与当前点的距离在 D D D以内，则将该点自动标记为非异常值。这样计算的时间复杂度为 O ( N 2 ) O(N^2) O(N2)，当数据量较大时，这样计算是及不划算的，因此，需要采用剪枝方法以加快距离计算。

基于单元的方法

 在基于单元格的技术中，数据空间被划分为单元格，单元格的宽度是阈值 D D D和数据维数的函数，具体而言，每个维度被划分为宽度最多为 D 2 d \frac{D}{2\sqrt{d}} 2d ​D​单元格。在给定的单元以及相邻单元中存在的数据点满足某些特性，这些特性可以让数据被更有效地处理。
 以二维情况为例，此时网格间的距离为 D 2 d \frac{D}{2\sqrt{d}} 2d ​D​，需要记住的一点是，网格单元的数量基于数据空间的分区，并且与数据点的数量无关。这是决定该方法在低维数据上的效率的重要因素，在这种情况下，网格单元的数量可能不多。另一方面，此方法不适用于更高维度的数据。对于给定的单元格，其 L 1 L_{1} L1​邻居被定义为通过最多 L 1 L_{1} L1​个单元间的边界可从该单元到达的单元格的集合。请注意，在一个角上接触的两个单元格也是 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 L_{r} Lr​邻居(其中 r > 2 r>2 r>2)中的一个点之间的距离至少为 D D D(严格来讲是 3 D 2 2 \frac{3D}{2\sqrt{2}} 22 ​3D​)
  

 唯一无法直接得出结论的是 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 A A中的所有数据点都是异常值
   此过程的第一步就是将部分数据点直接标记为非异常值，此外，此类单元格的所有相邻单元格仅包含非异常值。为了充分利用第一条规则的修建能力，确定每个单元格及其 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 ( r > 2 ) L_{r}(r>2) Lr​(r>2)中的所有点与 A A A上任意点的距离都至少为 D D D。因此，可以在距离计算中实现额外的节省。

基于索引的方法

 对于一个给定的数据集，基于索引的方法利用多维索引结构(如 R 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(kN^2) O(kN2)，其中 k k k是数据维， N N N是数据集中包含对象的个数。该算法在数据集增加时具有较好的扩展性，但是时间复杂度的估算仅考虑了搜索时间，而构造索引的任务本身就需要密集复杂的计算量。

基于密度的度量

 基于密度的算法主要有局部离群因子(LocalOutlierFactor,LOF)以及LOCI、CLOF等基于LOF的改进算法。
 基于距离的检测适用于各个集群的密度较为均匀的情况。而LOF等基于密度的检测则可以较好地适应密度不同的集群情况。在下图中，离群点B容易被检出，而若要检测出较为接近集群的离群点A，则可能会将一些集群边缘的点当作离群点丢弃。而LOF等基于密度的算法则可以较好地适应密度不同的集群情况。

k − 距 离 k-距离 k−距离

 对于数据集 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-distance(p) d(p,ok​)=k−distance(p)，满足：

• 在集合 D D D中至少有不包括 p p p在内的 k k k个点 o ′ o' o′，其中 o ′ ∈ D { p } o'\in 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'\in 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为中心，对数据集D中的所有点到p的距离进行排序，距离对象p第k近的点KaTeX parse error: Expected '}', got 'EOF' at end of input: o_{k]与 p p p之间的距离就是 k − 距 离 k-距离 k−距离

k-邻域

 由k-距离，我们扩展到一个点的集合——到对象p的距离小于等于k-距离的所有点的集合，我们称之为k-邻域： N k − d i s t a n c e ( p ) ) = { q ∈ D { p } ∣ d ( p , q ) < = k = d i s t a n c e ( p ) } N_{k-distance(p))}=\{q \in D\{p\}|d(p,q)<=k=distance(p) \} Nk−distance(p))​={q∈D{p}∣d(p,q)<=k=distance(p)}：

• k − k- k−邻域包含对象p的第k距离以内的所有点，包括第k距离点
• 对象p的第k邻域点的个数 ∣ N k ( p ) ∣ > = k |N_{k}(p)|>=k ∣Nk​(p)∣>=k
   在二维平面上，对象p的k-邻域实际上就是以对象p为圆心、k-距离为半径围成的圆形区域，就是说，k-邻域已经从"距离"这个概念延伸到空间了。
  

可 达 距 离 可达距离 可达距离

 有了邻域的概念，我们就可以按照到对象 o o o的距离远近，将数据集 D D D内的点按照到 o o o的距离分为两类：

• 若 p i p_{i} pi​在对象o的k-邻域内，则可达距离就是给定点 p i p_{i} pi​关于距离o的k-距离
• 若 p i p_{i} pi​在对象 o o o的 k − k- k−距离外，则可达距离就是关于给定点 p i p_{i} pi​关于对象o的实际距离
   综上所述，给定点 p i p_{i} pi​关于对象o的可达距离的计算公式为：
  r e a c h − d i s t k ( p , o ) = m a x { l − d i s t a n c e ( o ) , d ( p , o ) } reach-dist_{k}(p,o)=max\{l-distance(o),d(p,o)\} reach−distk​(p,o)=max{l−distance(o),d(p,o)}
   这样的分类处理可以简化后续的计算，同时让得到的数值区分度更高：
  
   可达距离的涉及是为了减少距离的计算开销， o o o的 k − k- k−邻域内的所有对象 p p p的 k − k- k−距离计算量可以被显著降低，相当于使用一个阈值将需要计算的部分进行了阶段。这种阶段对计算量的减少可以通过参数 k k k来进行调节， k k k的数值越大，无需计算的邻近点越多，计算开销越小。但是另一方面， k k k的值变大，可能意味着可达距离变远，对集群点和离群点的区分可能性变低。因此，对于如何选择k值，是 L O F LOF LOF算法能否达到效率与效果平衡的重要因素。

局部可达密度

 我们可以将密度直观的理解为点的聚集程度，就是说，点与点之间的距离越短，则密度越大。在这里，我们使用数据集 D D D中的对象 p p p与对象 o o o的 k − k- k−邻域内所有点的可达距离平均值的倒数来定义局部可达密度。
 在进行局部可达密度的计算的时候，我们需要避免数据集内的数据落在同一个点上，即所有可达距离之和为0的情况：此时局部密度为 ∞ \infty ∞，后续计算将无法进行。 L O F LOF LOF算法针对这一问题进行了如下的定义：对于数据集 D D D中的给定对象 p p p，存在至少 M i n P t s ( p ) > = 1 MinPts(p)>=1 MinPts(p)>=1个不同于p的点。因此，我们使用对象p到 o ∈ N M i n P t s ( p ) o \in 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邻域的密度的值：
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_{o \in N_{MinPts(p)}}reach-dist_{MinPts}(p,o)}{|N_MinPts(p)|}) lrdM​inPts(p)=1/(∣NM​inPts(p)∣∑o∈NMinPts(p)​​reach−distMinPts​(p,o)​)
 由公式可以看出，这是对于给定点 p p p进行度量，计算其邻域内的所有对象 o o o到给定点 p p p的可达距离平均值。给定点 p p p的局部科大密度越高，越可能与其邻域内的点属于同一簇；密度越低，越可能是离群点。

局部异常因子

 得到 l r d lrd lrd（局部可达密度）以后就可以将每个点的 l r d lrd lrd与其 k k k个邻近点进行比较，得到局部异常因子 L O F LOF LOF， L O F LOF LOF在数学上是对象 p p p的邻居点 o ( o ∈ N M i n P t s ( p ) ) o(o \in N_{MinPts}(p)) o(o∈NMinPts​(p))的 l r d lrd lrd平均值与 p p p的 l r d lrd lrd的比值：

 不难看出， p p p的局部可达密度越低，且其 M i n P t s MinPts MinPts近邻的平均局部可达密度越高，则 p p p的 L O F LOF LOF值越高。如果这个比值越接近于1，说明 o o o的邻近点密度差不多， o o o可能和邻域同属一簇；如果这个比值小于1，说明 o o o的密度高于其邻域点密度， o o o为密集点；如果这个比值大于1，说明 o o o的密度小于其邻域点密度， o o o可能是异常点。根据公式计算出来的 L O F LOF LOF数值就是我们所需要的离群点分数。

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
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(1000)

x_inliers1 = 0.2*np.random.randn(100,2)
x_inliers2 = 0.5*np.random.randn(100,2)
x_inliers = np.r_[x_inliers1+2,x_inliers2-2]
# 构造离群点
x_outliers = np.random.uniform(low = -4,high = 4,size = (20,2))
n_outliers = len(x_outliers)
# 拼成训练集
X = np.r_[x_inliers,x_outliers]
# 打标签
ground_truth = np.ones(len(X),dtype = int)
ground_truth[-n_outliers:] = -1

plt.figure(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]
plt.show()

# 进一步采用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_scoresX_scores.min())/(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],
            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]
plt.show()