共享最近邻算法：一种更稳健的距离度量方法

这篇文章里，我介绍了一种称为共享最近邻（SNN）的距离测量方法，并描述了它在异常值检测中的应用。我还将简短介绍其在预测和聚类中的使用，但会重点关注异常值检测，特别是SNN在k近邻算法中的异常值检测应用。不过也会简要讨论SNN在更广泛的异常值检测中的应用。

本文继续了关于异常检测的一个系列，包括关于频繁模式异常因子、基于计数的异常值检测器、测试异常检测器的方法和距离度量学习的文章。本文还包括我书中的另一段节选《Python中的异常检测》。

在数据科学中，处理表格数据时，计算行之间的距离是一个非常常见的任务。例如，在某些预测模型（例如 kNN）中，当我们使用 kNN 预测某个实例的目标值时，我们首先从训练数据中识别出最相似的记录（这需要一个衡量行之间相似度的方法）。然后，我们查看这些最相似记录的目标值，其想法是测试记录很可能具有与大多数最相似记录相同的目标值（对于分类），或者最相似记录目标值的平均（对于回归）。

还有一些其他的预测模型也使用距离度量，例如基于半径的方法，如RadiusNeighborsClassifier。然而，在聚类中，距离度量的应用最为广泛。事实上，距离计算在聚类中几乎是普遍存在的：据我所知，所有的聚类算法在某种程度上都依赖于计算记录对之间的距离。

许多离群点检测算法使用距离计算，包括许多非常流行的算法（如k近邻、局部离群点因子（LOF）、范围搜索、局部离群点概率（LoOP）等）。但这并非所有离群点检测算法的特征：许多算法以完全不同的方式识别离群点（例如孤立森林、频繁模式离群点因子、计数离群点检测器、ECOD、HBOS)，但许多检测器在某种程度上仍然利用行之间的距离计算。

聚类和离群点检测算法（使用距离的算法）通常从计算任意两行之间的距离开始，即计算数据中每对行之间的距离。至少从原则上来说是这样：为了执行得更高效，某些行对的距离计算可能会被省略或近似，但从理论上讲，我们通常从计算一个 n x n 的距离矩阵开始，其中 n 是数据中的行数。

这也就是说，需要有一种方法来测量任意两条记录之间的距离。但是，就像在一篇有关距离度量学习（DML，距离度量学习的英文缩写）的文章中提到的，找到合适的方法来判断两条记录的相似度可能很困难。

更常见的一种方法，特别是在处理数值数据时，是使用欧几里得距离。这种方法通常效果很好，并且具有很强的直观吸引力，尤其是在从几何角度来看时：即把数据视为空间中的点，如下面的散点图中所示。在二维图中，每个记录都表示为一个点，通过它们之间的欧几里得距离来衡量记录的相似性是很自然的。

然而，现实世界中的表格数据通常包含大量特征，处理这种数据时的一个主要挑战是所谓的“维度诅咒”。这种现象会从多个方面表现出来，但最严重的问题是，当维度足够多到一定程度时，记录之间的距离变得不再具有实际意义。

如下图所示，有一个点（用红色表示）在X轴（左侧窗格）上是不寻常的，但在其他维度（维度1、2和3）中是正常的。假设这个数据集只有这四个维度，计算每对记录之间的欧氏距离，我们会发现红色点与其他所有点的距离异常远。因此，它很可能会被标记为离群点。

然而，如果有几百个维度，如果红色点在除了维度0以外的所有维度中都相当常见，它就不太可能被可靠地标记为离群点：维度0中的较大距离在与其他所有维度的距离进行比较时会被平均，最终变得不那么重要。

这在预测、聚类和异常值检测来说是一个大问题，这些方法依赖于距离度量。

SNN 有时用来减轻这种效应。然而，我在下面的实验中将展示，SNN 效果最佳的场景（至少在我下面使用的 k-近邻离群点检测器中）不一定是在维度较高的地方（虽然这种情况也很重要），而是在数据密度在不同区域变化的地方。我将在下面解释这代表什么以及这对某些离群点检测器的影响。

SNN 用于定义任意两条记录之间的距离，就像欧几里得距离、曼哈顿距离、Canberra 距离、余弦相似度以及其他许多距离度量一样。正如其名所示，所计算的具体距离与任意两条记录之间共享邻居的数量有关。

这样，SNN 与其他距离度量相比，SNN 更独特，虽然它仍然更接近于欧几里得和其他标准度量，而不是距离度量学习（DML）。DML 目标是找到记录之间的逻辑距离，这与数值的具体大小无关。

另一方面，SNN 实际上是通过使用标准距离度量首先计算行之间的原始距离。如果第一步使用了欧几里得距离，则 SNN 距离类似于欧几里得距离；如果第一步使用了余弦距离，则 SNN 距离类似于余弦距离；等等。

然而，在我们深入细节或展示其如何应用于离群点检测之前，我们将快速回顾一下用于聚类的SNN，因为SNN最初是在聚类研究中发展起来的。这里描述的一般过程也被用于计算其他上下文中的SNN距离，包括离群点检测。

术语可能有点让人困惑，但也有一个通常称为SNN的聚类方法，这种方法使用SNN距离，并且与DBSCAN聚类方法非常相似。实际上，它可以说是对DBSCAN的一种改进。

可以在这里查看描述这一内容的主要论文：https://www-users.cse.umn.edu/~kumar001/papers/siam_hd_snn_cluster.pdf。不过，更早的使用SNN增强DBSCAN的想法可以追溯到1973年Jarvis-Patrick撰写的一篇论文。这里链接的论文采取了一种类似但更进一步的方法。

DBSCAN 是一种强大的聚类算法，至今仍被广泛使用。它可以很好地处理各种大小和形状的聚类（甚至是非常任意的形状）。在这种情况下，当聚类具有不同的密度时（它假定所有聚类具有相似的密度），它可能会遇到困难。大多数聚类算法也有类似的问题。比如，K-均值聚类假定所有聚类的密度相似，而高斯混合模型聚类则假设所有聚类形状大致符合高斯分布。

这里我不详细描述完整的DBSCAN算法，但做一个非常简要的概述：它通过识别所谓的_核心点_来工作，这些核心点位于密集区域中，可以安全地被视为内点。然后，它识别靠近核心点的其他点，围绕每个核心点形成聚簇。它通过一系列步骤运行，每次扩展和合并到目前为止发现的聚簇（合并重叠的聚簇）。靠近现有聚簇的点（即使这些点不直接接近原始核心点，而是接近已被添加到聚簇中的点）会被归入该聚簇。最终，每个点要么属于一个聚簇，要么未分配给任何聚簇（这些则是相对孤立的点）。

与异常值检测类似，聚类在处理高维数据集时也会遇到困难，同样是因为维度灾难，尤其是标准距离度量失效。在每一步，DBSCAN 基于尚未归类的点与已归类点之间的距离进行工作，当这些距离计算不可靠时，聚类也就变得不可靠。在高维度下，核心点可能无法与其他点（包括噪声点）区分开来，甚至包括那些不属于任何聚类的噪声点。

正如所指出的，DBSCAN 在处理数据的不同区域具有不同密度时也会遇到困难。问题在于，DBSCAN 使用的是一个全局的“点彼此接近”的标准，但不同的区域确实可能有不同的密度。

比如，当我们谈论的数据涉及到金融交易时。这可能包括销售、费用、工资单等各类交易，每种交易的特征各不相同。这些交易生成的速度可能不同，可能有不同的金额、数量以及数值范围。例如，销售交易可能比费用交易多得多。而且金额范围可能相差很大：也许最大的销售交易只是最小销售交易的约10倍大小，但最大的费用交易可能是最小费用交易的1000倍。因此，销售交易与费用交易的特性可能存在很大差异。

假设不同类型的交易分布在空间的不同区域（如果我们把数据看作高维空间中的点，每个维度代表数据表中的一个特征，每个记录则是一个点），我们可能会得到如下的图，其中左下角是销售交易，右上角是支出项目。

许多聚类算法（以及许多预测和异常检测算法）可能因为这些密度上的差异而无法很好地处理这些数据。如果DBSCAN仅仅依据整个数据集中的平均距离来进行聚类（在这种情况下，平均距离可能会被销售交易之间的距离所主导，尤其是在数据中销售交易的数量远多于其他类型的数据点时），它可能会将上右区域的所有点都排除在聚类之外。

SNN的目标是创建一个更可靠的度量标准，以应对高维度和变化的密度。

SNN的核心思想在于：若依照标准距离度量，点p1接近p2，可以说它们实际上也接近，但这可能不可靠。然而，如果p1和p2也有许多相同的最近邻点，我们可以更有把握地说它们接近。它们共有的邻居可以确认这种相似性。

通过共享近邻，在上图中，位于右上方的点会被正确地归入同一簇，因为它们通常与其他点共享许多相同的最近邻点，彼此间存在密切联系。

贾维斯-帕特里克用图来解释这一点，这是一种有用的看待数据的方式。我们可以将每个记录视为空间中的一个点（就像上面提到的散点图一样），并在每对数据点之间添加一条线来表示它们的相似性。为此，我们计算每对数据点之间的欧几里得距离（或使用其他类似的度量标准）。

由于图通常表示为邻接矩阵（n x n 矩阵，其中 n 表示图中的节点数，表示每对节点之间的连接关系），我们也可以把这一过程看作是邻接矩阵的表现。

从上面的散点图来看，我们可能有一个 n x n 的矩阵，比如：

          第1点    第2点    第3点    等等   第n点  
    第1点    0.0    3.3    2.9    等等   1.9  
    第2点    3.3    0.0    1.8    等等   4.0  
    第3点    2.9    1.8    0.0    等等   2.7  
    等等    等等    等等    等等    等等  
    第n点    1.9    4.0    2.7    等等   0.0

矩阵关于主对角线对称（即，从点1到点2的距离等于从点2到点1的距离），各点到自身的距离是0.0，因此主对角线上的值全为零。

SNN算法是一个两步过程，首先先计算这些原始成对距离（通常是欧几里得距离）。接着，它会生成第二个矩阵，包含共享最近邻的这些距离。

为了进行这种计算，它首先使用一个称为_ sparceification_的过程。为此，每对记录p和q，只有p和q都在对方的k个最近邻列表中时，它们之间才会有一个链接。这简单地确定：对于p，我们有到所有其他点的距离。对于某个k（作为参数指定，但让我们假设值为10），我们找出距离p最接近的10个点。这可能包括也可能不包括q。同样对于q：我们找到它的k个最近邻，看看p是否在其中。

我们现在有一个像上面那样的矩阵，很多单元格现在都是零。

然后我们考虑共同的最近邻。对于指定的k来说，p有一组k个最近邻（我们将这组称为S1），q也有一组k个最近邻（我们将这组称为S2）。我们可以通过S1和S2重叠的数量来衡量p和q的SNN相似程度。

在一个更复杂的形式中，我们也可以考虑S1和S2中邻居的顺序。如果p和q不仅有着大致相同的最近邻点，我们就可以确信p和q是接近的。进一步地，如果它们首先都最接近于p243，然后是p873，接着是p3321，最后是p773（或者至少顺序相仿），我们就可以更加确定p和q是相似的。不过，这篇文章中，我们将仅计算p和q共有多少最近邻点（在各自的k个最近邻点集合中）。

所以我们确实需要一个标准的距离测量标准来开始，但一旦这个标准建立起来，我们就使用点间距离的排序，而非实际的数值，这种方法通常更稳定。

对于SNN聚类，我们先这样计算SNN距离，然后按照标准的DBSCAN算法继续，找出核心点，找到足够接近的核心点，并逐步合并聚类。

例如，至少有两个SNN聚类算法的实现可以在GitHub上找到： https://github.com/albert-espin/snn-clustering 和 https://github.com/felipeangelimvieira/SharedNearestNeighbors 等。

尽管SNN起源于聚类（并且在聚类中仍然非常重要），正如前面提到的，作为一种距离度量，SNN在其他机器学习领域（包括异常值检测）也有相关性。我们现在回头来看看这一点。

在描述Python中SNN距离度量方法的实现之前，我将快速介绍一下简单的K近邻离群点检测算法。

    import pandas as pd  
    from sklearn.neighbors import BallTree  
    import statistics  

    class KNN:  
        def __init__(self, metric='euclidian'):  
            self.metric = metric  

        def fit_predict(self, data, k):  
            data = pd.DataFrame(data)  
            balltree = BallTree(data, metric=self.metric)  

            # 获取每个记录的k个最近邻
            knn = balltree.query(data, k=k)[0]  

            # 计算每个记录的k个最近邻的平均值
            scores = [statistics.mean(x[:k]) for x in knn]  
            return scores

对于一个二维数据表和一个指定的 k，fit_predict() 方法会为每个记录计算一个异常分数。该分数是到 k 个最近邻的平均距离。与此相反，使用到 k 个最近邻的最大距离（而不是平均距离）的变体有时被称为 Kth 最邻近，即使用最大距离的版本；而这种变体通常被称为 K 最邻近，即使用平均距离的版本，不过叫法上会有些变化。

这里的大部分工作实际上是scikit-learn的BallTree类在做，该类会计算并存储传入数据框中各点之间的成对距离。其query()方法返回对于传入data参数中的每个元素两个结果：

• 到最近的 k 个点的距离
• 最近 k 个点的索引

对于这个探测器，我们只需要距离信息，所以只需要取返回结果的第一个元素[0]。

fit_predict() 会返回数据框中每个记录与其最近的 k 个邻居的平均距离，这是它们异常性的估计：记录与其最近的邻居距离越远，它就越可能是异常值（不过，如之前提到的，这种方法在不同区域密度不一致时效果较差）。

这并不是一个可以直接投入生产的实现，但展示了基本的概念。KNN异常检测的完整实现可以在PyOD中找到。

使用SNN距离度量，可以实现一个简单的异常点检测器，如下所示。

    class SNN:  
        def __init__(self, metric='欧几里得'):  
            self.metric = metric  

        def get_pairwise_distances(self, data, k):  
            data = pd.DataFrame(data)  
            balltree = BallTree(data, metric=self.metric)    
            knn = balltree.query(data, k=k+1)[1]  
            pairwise_distances = np.zeros((len(data), len(data)))  
            for i in range(len(data)):  
                for j in range(i+1, len(data)):  
                    if (j in knn[i]) and (i in knn[j]):  
                        weight = len(set(knn[i]).intersection(set(knn[j])))  
                        pairwise_distances[i][j] = weight  
                        pairwise_distances[j][i] = weight  
            return pairwise_distances  

        def fit_predict(self, data, k):  
            data = pd.DataFrame(data)  
            pairwise_distances = self.get_pairwise_distances(data, k)  
            scores = [statistics.mean(sorted(x, reverse=True)[:k]) for x in pairwise_distances]  
            min_score = min(scores)  
            max_score = max(scores)  
            scores = [min_score + (max_score - x) for x in scores]  
            return scores

这里的SNN检测器实际上也可以被当作一种使用SNN距离的KNN检测器。为了简化起见，我们将这两种检测器分别称为KNN和SNN，前者使用标准距离度量（如曼哈顿或欧几里得距离），后者使用SNN距离。

就像KNN检测器一样，SNN检测器也为每个传递给fit_predict()的记录返回一个分数，这里指的是到k个最近邻的平均SNN距离，而不是标准距离度量计算的平均距离。

此类还提供了get_pairwise_distances()方法，该方法用于fit_predict()中，但也可以直接调用，特别是在计算成对SNN距离时有用。我们将在后面看到一个具体例子，用DBSCAN进行异常值检测。

在 get_pairwise_distances() 中，我们取 BallTree 的 query() 方法返回结果中的元素 [1]，因为我们关心的是这些点的最近邻点，而不是它们的具体距离。

根据指示，我们把所有距离设为零，除非这两条记录都在彼此最近的k个记录之中。然后我们计算特定的SNN距离值，即每对点在各自最近的k个邻居中共享的邻居数量。

可以使用如 Jaccard 或 Dice 这样的度量来量化每对点的最近邻之间的重叠量，但因为这两者的大小都是 k，我们只需计算每对点之间重叠的数量即可。

在另一种提供的方法 fit_predict() 中，我们首先获取成对的样本距离。这些实际上是正常度的度量，而不是离群点的程度，所以在返回分数之前会将这些度量转换为其相反数。

最终分数是每个记录与最近k个点之间的平均相似度。

所以，k实际上在这里被用来完成两个不同的任务：首先用于识别最近的k个邻居（当我们计算KNN距离时，使用欧几里得或其他度量），再在第二步中使用（当我们计算SNN距离时，使用重叠的平均值）。可以为这两个步骤使用两个不同的参数，一些实现确实如此，有时会将这个参数称为_eps_。这源于DBSCAN的历史，其中eps用于定义两点间允许的最大距离，以使它们被视为处于相同的邻域。

再次，这不一定适合生产环境，还远未达到优化。有可以提高速度的技术，尤其是在计算原始成对距离的步骤，这是研究中的一个活跃方向。当你有非常大量的数据时，可能需要考虑使用BallTree的替代方案，例如faiss，或者采用其他加速处理的方法。但对于中等规模的数据集来说，这样的代码通常已经足够了。

我已经用不同的数据集和条件对上述的KNN和SNN离群点检测器进行了测试，包括使用合成数据和真实数据。多年来，我在多个离群点检测项目中也使用了SNN距离。

总体来说，我发现实际上SNN并不一定在高维数据上表现得比KNN更好，不过SNN有时候会更好。

不过，我看到SNN在数据密度存在差异时，比标准KNN表现得更好。

更精确地说，SNN 在高维度和密度变化的结合情况下，比单独存在高维度或密度变化时，更能显著优于配合 KNN 类型检测器使用的其他距离度量。

这可以通过以下测试代码来看到。这段代码使用相对简单的合成数据集，更清楚地说明这一点。

    def test_variable_blobs(nrows=1000, ncols=500, nclusters=60, outlier_multiplier=2.0, k=30, metric='manhattan'):  
        np.random.seed(1)  

        # ########################################################  
        # 定义测试数据  

        # 定义每个聚类的大小  
        n_samples_arr = []  
        remaining_count = nrows  
        for i in range(nclusters-1):  
            cluster_size = np.random.randint(1, remaining_count // (nclusters - i))  
            n_samples_arr.append(cluster_size)  
            remaining_count -= cluster_size  
        n_samples_arr.append(remaining_count)  

        # 定义每个聚类的密度  
        cluster_std_arr = []  
        for i in range(nclusters):  
            cluster_std_arr.append(np.random.uniform(low=0.1, high=2.0))  

        # 定义每个聚类的中心位置  
        cluster_centers_arr = []  
        for i in range(nclusters):  
            cluster_centers_arr.append(np.random.uniform(low=0.0, high=10.0, size=ncols))  

        # 创建样本数据  
        x, y = make_blobs(n_samples=n_samples_arr,  
                          cluster_std=cluster_std_arr,  
                          centers=cluster_centers_arr,  
                          n_features=ncols,  
                          random_state=0)  
        df = pd.DataFrame(x)  

        # 加入一个已知的离群样本  
        avg_row = [x[:, i].mean() for i in range(ncols)]  
        outlier_row = avg_row.copy()  
        outlier_row[0] = x[:, 0].max() * outlier_multiplier  
        df = pd.concat([df, pd.DataFrame([outlier_row])])  
        df = df.reset_index(drop=True)  

        # ########################################################  
        # 比较标准距离度量与SNN  

        # 使用标准KNN计算离群分数  
        scored_df = df.copy()  
        knn = KNN(metric=metric)  
        scored_df['knn_scores'] = knn.fit_predict(df, k=k)  

        # 使用SNN计算离群分数  
        snn = SNN(metric=metric)  
        scored_df['snn_scores'] = snn.fit_predict(df, k=k)  

        # 绘制两种检测器的分数分布图，并展示  
        # 已知离群样本的分数（相对于整个数据集的分数区间）  
        fig, ax = plt.subplots(nrows=1, ncols=2, figsize=(12, 4))  
        sns.histplot(scored_df['knn_scores'], ax=ax[0])  
        ax[0].axvline(scored_df.loc[nrows, 'knn_scores'], color='red')  
        sns.histplot(scored_df['snn_scores'], ax=ax[1])  
        ax[1].axvline(scored_df.loc[nrows, 'snn_scores'], color='red')  
        plt.suptitle(f"列数：{ncols}")  
        plt.tight_layout()  
        plt.show()

在这个方法里，我们在数据集中加入一个已知的异常点，分别获取KNN和SNN的异常分数，并画出结果图。

测试数据是通过scikit-learn的make_blobs()函数生成的，该函数会生成一组高维聚类。生成的一个离群点将位于这些聚类之外，并且，默认情况下，该离群点在列0中的值会非常极端。

代码复杂性的一大来源在于生成测试数据。在这里，我们没有只是使用默认参数调用 make_blobs()，而是指定了每个聚类的大小和密度，以确保它们各不相同。密度是通过设置每个聚类的标准差数组来描述的，这描述了每个聚类的分布情况。

这会产生如下所示的数据：

这仅展示了四个维度，但通常我们会称这种方法为创建多维度的数据。已知的异常点以红色标出。在维度0中，它有一个极端值，并且在大多数其他维度中，它往往会落在聚类之外，因此它是一个明显的异常点。

可以进行测试，比如：

test_variable_blobs(nrows=1000, ncols=20, nclusters=1, k=30, metric='euclidean')  
test_variable_blobs(nrows=1000, ncols=100, nclusters=5, k=30, metric='euclidean')  
test_variable_blobs(nrows=1000, ncols=250, nclusters=10, k=30, metric='euclidean')  
test_variable_blobs(nrows=1000, ncols=400, nclusters=15, k=30, metric='euclidean')  
test_variable_blobs(nrows=1000, ncols=450, nclusters=20, k=30, metric='euclidean')  
test_variable_blobs(nrows=1000, ncols=500, nclusters=20, k=30, metric='euclidean')  
test_variable_blobs(nrows=1000, ncols=750, nclusters=20, k=30, metric='euclidean')  
test_variable_blobs(nrows=1000, ncols=1000, nclusters=20, k=30, metric='euclidean')  
test_variable_blobs(nrows=1000, ncols=2000, nclusters=20, k=30, metric='euclidean')  
test_variable_blobs(nrows=1000, ncols=3000, nclusters=20, k=30, metric='euclidean')  

test_variable_blobs(nrows=1000, ncols=20, nclusters=1, k=30)  
test_variable_blobs(nrows=1000, ncols=100, nclusters=5, k=30)  
test_variable_blobs(nrows=1000, ncols=250, nclusters=10, k=30)  
test_variable_blobs(nrows=1000, ncols=400, nclusters=15, k=30)  
test_variable_blobs(nrows=1000, ncols=450, nclusters=20, k=30)  
test_variable_blobs(nrows=1000, ncols=500, nclusters=20, k=30)  
test_variable_blobs(nrows=1000, ncols=750, nclusters=20, k=30)  
test_variable_blobs(nrows=1000, ncols=1000, nclusters=20, k=30)  
test_variable_blobs(nrows=1000, ncols=2000, nclusters=20, k=30)  
test_variable_blobs(nrows=1000, ncols=3000, nclusters=20, k=30)

首先执行一系列基于欧几里得距离的测试（既用于KNN检测器，也用于SNN检测器的第一步测试），接着执行一系列基于曼哈顿距离的测试（这是test_variable_blobs()方法默认使用的）——对于KNN检测器和SNN检测器的第一步测试，都使用曼哈顿距离。

我们对每一个测试使用从20到3000不等的列数。

从计算欧几里得距离开始，KNN和SNN在这20个特征下表现良好，都能给已知异常值分配较高的异常分数。这里可以看到每个检测器的异常分数分布（KNN检测器显示在左侧窗格，SNN检测器显示在右侧窗格），以及一条红色的垂直线，表示每个检测器对已知异常值的异常分数。在两种情况下，已知异常值的分数都显著高于其他记录：这两种检测器表现都不错。

但使用欧几里得距离往往会迅速恶化，特别是在添加特征时，即使只有100个特征也表现得很差。这在KNN和SNN检测器中都适用，具体情况如下。已知异常值获得了相对正常的评分，没有显示出任何异常迹象，如以下所示：

使用曼哈顿距离时，我们发现，当特征数量较小时，KNN表现良好，但随着特征数量的增加，其性能会下降。然而，一旦特征数量超过大约50个（在少量特征的情况下，几乎任何距离度量都表现良好），KNN使用曼哈顿距离比使用欧几里得距离表现更好。

在以下所有情况下（使用曼哈顿及SNN距离），我们在左侧窗格中显示KNN异常得分的分布（以及KNN检测器为已知异常分配的得分），并在右侧窗格中显示SNN得分的分布（以及SNN检测器为已知异常分配的得分）。

具有20个功能，两者表现都不错。

当有100个特征时，KNN依然给已知的异常值打了一个较高的分数，但并不是非常高。SNN依然在以下所有情况中表现优秀：

当有250个特征时，KNN给已知的异常值的得分比较低，且得分的分布也很奇怪。

具有500个特性。

具有1000个功能，

有2000个功能哦。

具有3000个功能。

即使使用曼哈顿距离的KNN检测器，我们可以看到100个特征时得分的分布看起来很奇怪，并且更重要的是，同样在100个特征时，已知异常值的得分很低：得分太低，未能反映其异常性。

另一方面，SNN分数的分布情况即使在3000个特征时仍然合理，已知的异常样本得到的SNN分数直到接近2000个特征时仍然非常高（对于2000和3000个特征，它的分数依然很高，但并非最高分记录）。

SNN检测器（本质上是一种基于SNN距离的K近邻离群点检测算法）比用曼哈顿距离的K近邻要可靠得多。

一个关键点是，不考虑SNN距离的话，曼哈顿距离在我们处理具有大量特征的数据时比欧几里得距离更适合用来检测异常值。维度灾难仍然存在（所有距离度量最终都会出现问题），但在有数十或数百个特征的情况下，这种情况比使用欧几里得距离要轻微得多。

事实上，虽然在较低维度上非常合适，但是当特征数量适中时（有时甚至只有30或40个特征），欧几里得距离可能会出现问题。因此，这里的做法是使用曼哈顿距离进行比较，这样会更公平，这就是这里采用的方法。

通常，我们应该注意那些声称与欧几里得距离相比的距离测量评估，因为这些评估可能会误导。在处理距离计算时，我们通常默认使用欧几里得距离，但这正是我们应该质疑的假设。

在我们这里分析的情况中（其中聚类的大小和密度各不相同），SNN 比 KNN 表现得更好（并且令人印象深刻的是，即使在接近 2000 个特征时依然保持稳定）。这个发现更具有实际意义，因为我们是用基于曼哈顿距离的 KNN 来比较的，而不是用欧几里得距离的 KNN。

然而，在许多其他情况下，特别是在数据集中在单一聚类中，或者聚类密度相似的情况下，KNN的表现甚至可能比SNN更好。

并不是说SNN应该总是优于其他距离度量，而是在某些情况下，它可能会好得多。

在其他情况下，其他距离度量也可能更合适，包括余弦相似度、Canberra距离、马氏距离、切比雪夫距离等。在进行离群点检测时，使用这些度量通常是值得的。

在这里，KNN的不足之处在于，类似使用DBSCAN进行聚类时的情况，不同的区域（也就是不同的聚类）密度不同。

KNN 是一种被称为 全局异常值检测器 的检测器示例。如果你熟悉局部和全局异常值的概念，这两个概念有相似之处，但也有不同。这里的“全局”指的是整个数据集中有一种普遍的正常标准。这与之前讨论的 DBSCAN 聚类中提到的全局正常距离概念相似。数据中的每个记录都会被与这个普遍的正常标准进行对比。对于 KNN 异常值检测，有一个全局的正常平均距离到 k 个最近邻的标准。

但是，在数据在不同区域密度不同的情况下，这样的全球标准在这里就没有太大意义了。如图所示，如上图所示，有两个群集，左下角的群集比右上角的群集密集得多。

重要的是，该点距离其邻居之间的距离相对于该区域的正常情况，而不是相对于其他集群或整个数据集的正常情况。

这是另一个重要的异常值检测器，局部异常因子（LOF）正是为了解决这个问题（原始的LOF论文实际上描述了类似的情况）。与全局异常值检测器相反，LOF是一个局部异常值检测器：将点与附近点进行比较的检测器，而不是与整个数据集进行比较，因此是将每个点与该区域的“正常”标准进行比较。在LOF的情况下，它将每个点与附近点的平均距离进行比较。

本地异常值检测方法也提供了一种有价值的识别异常值的方法，特别是在数据密度变化较大的区域，我在《Python中的异常值检测》一书中介绍过相关内容，并将在我未来的文章中继续介绍。

SNN 还为密度变化的问题提供了重要的解决方案。使用 SNN 距离时，密度的变化无关紧要。每个记录都会与一个全局标准比较，该标准是记录与其最近邻平均共享邻居的数量。这是一个相当稳健的计算，在数据聚类或某些区域比其他区域更密集的情况下也能很好地工作。

在这篇文章中，我们主要探讨了用于离群点检测的KNN算法，但SNN也可以与任何基于行间距离的离群点检测器一起使用。例如Radius、局部离群点因子（LOF）以及其他多种算法。也包括所有基于聚类的离群点检测算法。

识别异常值可以通过聚类的几种方式，例如识别非常小的聚类中的点，远离聚类中心的点等。在这里，我们将看看一种异常简单的方法来检测异常值：先对数据进行聚类，再识别那些没有被分配到任何聚类中的点。

DBSCAN 是用于这种类型的异常检测常用的聚类算法之一，因为它有一个方便的特点（并不是所有的聚类算法都有这个特点），即允许一些点不被分配到任何聚类。

DBSCAN（至少使用scikit-learn的版本）还让我们能够轻松处理SNN距离。

所以，DBSCAN不仅是一种有用的聚类算法，还被广泛用于离群点检测。我们还将通过SNN距离来检测离群点作为另一个例子。

在使用SNN距离之前，我们将展示一个使用DBSCAN的例子，因为DBSCAN更常被用来识别数据中的异常值（这里使用的是默认的欧几里得距离）。这里使用的是上述创建的相同数据集，其中最后一行是已知的那个单一异常值。

    聚类模型 = DBSCAN(eps=20, min_samples=2).fit(df.values)  
    print(聚类模型.labels_)  
    print(pd.Series(聚类结果).value_counts())

设置 DBSCAN 的参数可能需要一些试验和调整。在这种情况下，我调整参数，直到算法识别出一个离群点，我通过打印 labels_ 属性确认这个离群点是最后一行的数据。标签如下：

[0 1 1 ... 1 0 -1]

-1 表示未被分配到任何聚类的记录。并且，通过 value_counts() 可以看出只有一个记录被分配到 -1 聚类。因此，在这个示例中，DBSCAN 工作得很好。这意味着我们无法通过使用 SNN 来改进它，这提供了一个使用 DBSCAN 进行异常值检测的清晰示例，并且保证数据集可以通过基于聚类的异常值检测方法来分析。

为了使用SNN距离，首先需要计算成对的SNN距离（DBSCAN不能自己计算这些距离）。计算出这些距离后，可以将它们以n x n矩阵的形式传给DBSCAN。

这里我们计算SNN的成对距离。

# 初始化SNN模型
snn = SNN(metric='manhattan')  
# 计算曼哈顿距离
pairwise_dists = snn.get_pairwise_distances(df, k=100)  
# 打印成对距离
print(pairwise_dists)

两两之间的距离看起来是这样的：

矩阵([[0., 0., 0., ……, 0., 57., 0.],  
     [0., 0., 0., ……, 0., 0., 0.],  
     [0., 0., 0., ……, 0., 0., 0.],  
     ……,  
     [0., 0., 0., ……, 0., 0., 0.],  
     [57., 0., 0., ……, 0., 0., 0.],  
     [0., 0., 0., ……, 0., 0., 0.]])

为了快速简便地反转这些距离，使之更适合DBSCAN，我们称之为。

    d = pd.DataFrame(pairwise_dists).apply(lambda x: 1000-x)

该代码把成对距离转换成数据框，然后用lambda函数把每个数变成1000减去这个数的结果。

在这里，1000 只是一个大于实际数据中任何值的数字。然后，我们调用 DBSCAN，使用 ‘precomputed’ 作为距离度量，并将成对距离传递给 fit() 函数。

clustering = DBSCAN(eps=975, min_samples=2, metric='precomputed').fit(d.values)  # 聚类分析使用DBSCAN算法，设置eps为975，min_samples为2，metric为预计算的距离矩阵。
print(clustering.labels_)  
# 显示聚类标签的频数分布
display(pd.Series(clustering.labels_).value_counts())

再次，这仅识别了单一的异常值（只有单一记录被赋予了群集ID -1，而这正是数据集的最后一行记录）。通常，DBSCAN以及其他接受“预计算的距离”作为度量的工具可以处理SNN距离度量，并从而可能产生更稳健的结果。

在使用DBSCAN时，使用SNN距离可以很好地工作，因为异常点（DBSCAN中称为“噪声点”）和正常点往往几乎所有链接都会断开，因此异常点最终不会被归入任何聚类。一些异常点（尽管是不太极端的异常点）会与其他记录有一些链接，但通常会与这些记录几乎没有共享邻居，因此将获得较高的异常分数（相比之下，完全无链接的异常点得分会更高，这是合适的）。

这可能需要一些试验和调整，在某些情况下，可能需要调整k的值以及DBSCAN参数，但这种调整程度在异常值检测中很常见，进行一些微调是常见的。

SNN 在离群点检测中的应用并不像理想中那么广泛，但有一个著名的检测工具在使用它：SOD，这个工具在 PyOD 库中可以找到。

SOD 是一种离群点检测工具，专注于找到用于离群点检测的有效子空间，但会在过程中用到 SNN。在 SOD 的论文中提到，这有助于提供更可靠的距离计算。

SOD（类似于KNN和LOF）的工作方式，通过为每个点识别一个包含k个邻居的邻域，SOD中将此邻域称为参考集。参考集是通过SNN发现的。因此，这些邻域是通过找到共享邻居最多的点来确定的，而不是以欧几里得距离最近的点。

作者发现这种情况不仅在高维度下稳健，而且在存在许多不相关特征时同样稳健：邻居的排名顺序通常保持有效，因此即使具体距离不可靠，最近邻集也能被可靠地确定。

一旦我们为一个点确定了参照集，SOD 就利用这一点来确定子空间，即能解释参照集最大方差的特征集。并且，一旦 SOD 确定了这些子空间，它会检查每个点到数据中心的距离，并据此提供一个异常值评分。

SNN的一个明显用途是嵌入（例如，图像、视频、音频、文本、网络或其他模态的数据的向量表示），这些嵌入通常具有非常高的维度数。我们将在《Python中的离群点检测》（https://www.manning.com/books/outlier-detection-in-python）中更深入地探讨这个问题，但是在这里简单说明一下：专为数值表格数据设计的标准离群点检测方法（孤立森林、局部离群点因子、第k个最近邻等），实际上在处理嵌入时表现不佳。主要原因似乎是维度数量过高以及许多与离群点检测无关的维度。

还有其他一些成熟的离群点检测技术，例如基于自编码器、变分自编码器、生成对抗网络等方法，此外还有其他一些技术。此外，书中也有涉及这些内容，我也希望未来能在平台上写一篇类似的文章来讨论。此外，我现在正在研究除了欧几里得距离、余弦距离等标准度量外的其他度量，比如SNN。这些度量是否有效还在进一步研究中。

类似于距离度量学习，共享最近邻法的计算起来比标准的距离度量（如曼哈顿距离和欧几里得距离）更耗时，但在处理特征数量庞大、不同密度以及（特别是）如SOD作者发现的无关特征时可能更加稳健可靠。

因此，在某些情况下，SNN（局部异常因子）可能更适合作为距离度量，并且可能更适合用于离群点检测。我们已经看到它可以用于 kth 最近邻离群点检测，以及单纯用于 DBSCAN 离群点检测（以及当仅使用 DBSCAN 进行聚类时）。

实际上，SNN 可以与任何基于样本间距离的离群点检测方法配合使用。换句话说，它可以与任何基于距离、密度或聚类的异常值检测方法一起使用。

我们还指出SNN并不总比其他距离度量更优。当考虑到分类、日期和文本列（以及其他可能出现在表格数据中的特征类型）时，问题会更加复杂。但即使只考虑数值数据，在拥有大量特征的数据集上，简单的曼哈顿距离比SNN更适用，在其他情况下则SNN更适用。数据行的数量、特征的数量、特征的重要性、特征的分布、特征间的关联、数据的聚类等情况都相关，通常无法提前预测哪种方法会更好。

SNN 是解决高维度、密度变化和不相关特征等问题的一个有用工具，容易实现，并且常常值得尝试一下。

本文只是对SNN的介绍，未来的文章可能会更深入地探讨SNN，但总的来说，在确定用于异常检测的距离度量（以及其他相关建模决策）时，最佳的方法是使用一种称为掺假（在此文章中有描述）的技术，其中我们创建的数据经过修改以包含强烈但现实的异常。通过这种方式，我们可以尝试评估哪种方法最有效于检测你可能遇到的异常。

在这里，我们使用了合成数据的一个例子，这可以帮助描述异常值检测方法在何处比另一种方法表现更好，并且非常有价值（例如，我们发现当改变密度并增加特征数量时，SNN（S-近邻算法）优于使用曼哈顿距离的方法，但在密度保持一致且特征数量较少时，两者都表现良好）。但是，尽管使用合成数据非常重要，这只是了解不同方法在类似数据上表现的一个步骤。数据增强将更倾向于在这种情况下会更有帮助，或者至少是整个过程中的一部分。

同样，在异常值检测中，通常认为没有单一的检测器能可靠地识别所有你感兴趣的异常值。每个检测器主要识别特定类型的异常值，而且我们通常对识别多种类型的异常值感兴趣（事实上，很多时候，我们只是想找出任何与正常情况显著不同的数据——尤其是在刚开始分析数据集时）。

鉴于这一点，我们通常会使用多个检测器进行离群值检测并将它们的结果组合成一个集成。一个增加集成内部多样性的有用技术是使用不同的距离度量。例如，如果曼哈顿距离、欧几里得距离、SNN距离，甚至可能是其他度量（如坎塔纳距离、余弦距离等）都表现良好（都产生不同的但合理的结果），那么使用所有这些度量可能是值得的。然而，通常只会有一两种度量能产生有意义的结果。虽然SNN并不是唯一的度量，但它是一个非常有用的尝试，特别是在其他距离度量难以发挥作用时。

所有图片均为作者拍摄。