基于相似性和接近方向的替换性分析方法，用于k近邻分类器

《Engineering Applications of Artificial Intelligence》：Similarity and approaching direction based substitutability analysis method for k-nearest neighbor classifier

　　**摘要**
k近邻分类器（KNN）是一种经典的数据驱动模型，用于处理分类问题。然而，现有的各种KNN在判断靠近分类边界的测试样本时容易出错。为了解决KNN的这一缺陷，本文提出了一种基于相似性和接近方向的替代性分析方法，该方法可以被视为一种泛化的度量学习KNN。通过整合接近方向的信息，KNN能够更自由地调整分类边界。此外，为了高效地获得正确的接近方向，本文提出了一种快速学习方法，该方法只需要解决几个低维的子优化问题。在加利福尼亚大学欧文分校机器学习仓库（UCI）的相关实验以及一些工业和数值分类问题上，已经证明了所提出的基于相似性和接近方向的替代性分析方法的有效性和先进性。研究表明，配备这种替代性分析方法的KNN能够更好地处理靠近分类边界的测试样本。

**引言**
分类问题在各种实际工程应用中非常常见（Li等人，2024；Li等人，2021；Li等人，2016；Liu等人，2023；Li等人，2023）。k近邻分类器（KNN）是最著名的数据驱动分类器之一（Zhang等人，2022；Thammasorn等人，2023；Zhao等人，2021）。一般来说，KNN具有两个重要优势（Wang等人，2020；Kassani等人，2017；Banerjee等人，2019；Wang和Mao，2020）：一方面，它具有有效的简洁性，结构简单却实用，不需要太多的训练样本作为驱动因素；另一方面，它具有高度的可解释性，可以被视为基于实例的知识表示和推理方式，容易被行业专家理解。迄今为止，KNN已被改进并应用于许多实际分类问题中，包括高速铣削中的碎屑识别（Shi等人，2020）、电解槽中的异常预测（Shi等人，2023）、入侵植物识别（Guo等人，2021）以及人脸识别（Liu和Liu，2017）。尽管KNN在许多实际分类问题上取得了改进，但它仍存在一个严重限制其分类性能的缺陷：现有的高性能KNN在判断靠近分类边界的测试样本时容易出错。为了清楚地说明这一缺陷，图1提供了一个示例。在图1中，两个红色训练样本和一个绿色训练样本足够接近左侧的测试样本。在现有的高性能KNN中，这三个训练样本都会被简单地视为测试样本的邻居，从而导致错误的分类结果。

本文提出了一种泛化的k近邻分类器框架，以清晰地分析现有高性能KNN容易误判靠近分类边界测试样本的根本原因。该框架包括三个部分：训练样本集、替代性分析和加权多数投票。训练样本集是一组数据，是KNN运行的基础；替代性分析负责分析每个训练样本与测试样本之间的替代程度，通常替代程度越高，就越认为两个样本的输出标签相同；加权多数投票则根据训练样本的输出标签和它们之间的替代程度来估计测试样本的输出标签。基于这种泛化的k近邻分类器框架，本文对几种现有的高性能KNN进行了分析，发现了两个重要现象：首先，这些KNN在替代性分析方面存在差异，替代性分析的质量决定了它们的分类性能；其次，现有的高性能KNN的替代性分析主要基于相似性标准（????≈????），这使得任何靠近测试样本的训练样本都可能被视为核心替代者。然而，如图1所示，仅基于相似性的替代性分析不足以作为测试样本靠近分类边界时的高质量替代性判断标准。更多相关细节见第2节。

**注释1**
替代性分析可以视为一个功能模块，其输入为两个样本的特征向量，输出表示两个样本属于同一类别的概率。因此，为了解决现有高性能KNN容易误判靠近分类边界测试样本的问题，需要结合其他标准来提出更完善的替代性分析方法。直观来说，每个训练样本的接近方向是一个可行的选择。以图1为例，如果将靠近左侧测试样本的两个红色训练样本的接近方向限制为向上或向左，那么替代性分析的结果就可以更准确地调整。基于这一思路，本文提出了一种基于相似性和接近方向的替代性分析方法，该方法使用相似性和接近方向指数来衡量样本之间的替代性。当能够获得正确的接近方向时，对靠近分类边界的测试样本的替代性分析在理论上会更加准确。此外，正确的接近方向可以通过一些低维优化问题来确定，这些问题的求解成本在大多数工业应用中是可以接受的。更多相关细节见第3节。

**注释2**
所提出的SD-KNN可以视为度量学习KNN的泛化形式，其核心思想是以数据驱动的方式学习替代性分析。然而，SD-KNN在两个方面更为复杂：首先是接近方向，传统的度量学习KNN没有对接近方向的限制（可以视为SD-KNN的一个特例，其中接近方向被设定为????+?(??)=??????(??)）；其次是数量，传统KNN仅学习一个用于测试样本与??个训练样本之间替代性分析的函数，而SD-KNN则学习??个函数。因此，SD-KNN可能比传统KNN具有更高的性能上限。

本文的其余部分组织如下：第2节阐述所提出的k近邻分类器泛化框架；第3节介绍基于相似性和接近方向的替代性分析方法；第4节展示相关实验的结果和讨论；第5节对本文进行总结。

**k近邻分类器的泛化框架**
本节提出了k近邻分类器的泛化框架，如图2所示，包括三个部分：训练样本集、替代性分析和加权多数投票。

**现有替代性分析的缺陷**
在KNN的泛化框架中，替代性分析是决定分类性能的关键因素。目前，所有KNN中的替代性分析都仅基于测量训练样本与测试样本之间的相似性（公式（5）这一思路，这实际上将替代性分析问题简化为了相似性分析问题。当然，满足相似性条件（????≈????）的样本……

**数据集**
实验中使用了三种数据集：第一种来自UCI公共库（http://archive.ics.uci.edu/ml）的基准数据集，其特点在表1中有描述；第二种是某知名铝电解企业中用于几种铝还原槽（ARC）的合成平衡材料与能量（AR-SBME）异常识别数据；第三种是……

**结论**
本文研究了如何解决现有高性能KNN容易误判靠近分类边界测试样本的问题。主要贡献如下：
- 提出了一种k近邻分类器的泛化框架；
- 基于该框架，阐明了现有高性能KNN容易误判靠近分类边界测试样本的根本原因。

**利益冲突声明**
作者声明没有已知的财务利益冲突或个人关系可能影响本文的研究工作。

**作者信息**
Jue Shi
中国长沙科技大学电气与信息工程学院