kNNPC（k-最近邻算法，按类别划分）：一种能够以较高概率预测外推区域的分类方法

《Journal of Chemometrics》：kNNPC (k-Nearest Neighbor Algorithm Per-Class): Classification Method Predicting Extrapolation Regions With Reasonable Probability

　　摘要

在分类任务中，对于训练分布之外的样本，预测的类别概率往往过于自信，这可能导致不安全的决策。提出了一种称为kNNPC（每个类别的k最近邻算法）的方法，以减轻这种过度自信的问题，特别是在外推或分布偏移的情况下。对于给定的测试样本，kNNPC会调整预测的类别概率向量，使其在样本与训练数据在特征空间不相似时更接近最大不确定性分布。重要的是，kNNPC并不旨在明确识别外推区域；相反，它提供了一个保守的概率输出，作为防止过度自信预测的实际保障。kNNPC在基准测试和真实世界数据集上进行了评估，包括Iris数据集、毒性分类数据集和超导临界温度数据集，并与标准概率分类器进行了比较。结果表明，kNNPC可以有效抑制域外样本的过度自信概率，同时保持相当的预测性能。所提出方法的Python代码可在https://github.com/hkaneko1985/dcekit获取。

1 引言

在判别问题中，除了预测的类别标签外，通常还会使用类别成员概率。然而，对于位于特征空间远离训练数据的样本，许多标准分类器会产生过于自信的概率，即使这些样本超出了可以期望可靠泛化的区域。这个问题在化学计量学及相关领域尤为重要，因为模型通常应用于可能无法被训练分布良好表示的候选样本。基于模型的适用性域[1, 2]的概念，当输入到模型的x值位于远离训练数据的区域（即外推区域）时，正确预测类别y的可能性很低。然而，在传统的分类方法中，当输入到模型的x值属于外推区域时，分配给一个类别的概率会变为100%。例如，在分子设计的虚拟筛选中，可能在训练数据中表现不佳的支架或描述符模式的新生成分子上应用已训练的模型。同样，在材料信息学中，可能在观察到的组成空间密集区域之外的假设组成或掺杂材料上使用训练有素的分类器进行筛选。设xi表示样本i的p维特征向量，X表示训练样本的n×p数据矩阵。在本手稿中，“特征空间”指的是特征向量xi所表示的域。根据适用性域的概念[1, 2]，当查询样本xi在特征空间远离训练样本时，预测的可靠性较低。在这些外推区域，标准分类器仍可能将接近1.0的概率分配给一个类别，这可能导致误导性的自信决策。图1显示了为二元Iris数据集获得的示例概率图。原始数据集[3, 4]包含三个类别和四个变量；在这个示例中，setosa样本被分配到类别1，而versicolor和virginica样本被合并到类别0。应用了主成分分析，并使用前两个主成分（PC1和PC2），它们共同解释了95.8%的方差，用于可视化，并且PC1和PC2被用作此示例分析中的二维特征向量。图1a显示了这两个特征的散点图。十字表示类别1的样本，点表示类别0的样本。使用所有样本作为训练数据，构建了基于k最近邻算法（kNN）[5]、逻辑回归（LR）[6]、带高斯核的支持向量机（SVM）[7]、随机森林（RF）[8]和极端梯度提升（XGB）[9]的分类模型，并在图1a显示的特征空间上计算了类别1的输出概率。如图1b–f所示，对于所有方法，都存在概率为100%的区域（红色区域），即使这些区域远离训练数据，例如特征空间的最左侧外推区域。概率为0%的区域（蓝色区域）意味着类别0的概率为100%，并且存在即使远离训练数据也将100%的概率分配给类别0的区域，例如特征空间的最右侧外推区域。在特征空间的外推区域，两个类别的概率应该相等，即在图1所示的示例中，最左侧和最右侧的外推区域应该有50%的概率属于类别1。

2 方法

给定一个查询样本，kNNPC计算查询样本到每个类别的训练样本的类别平均kNN距离，并将这些距离转换为类别成员概率。为类别距离设置一个阈值，超过阈值的距离将被替换为该阈值。因此，远离所有类别训练数据的查询样本在每个类别都有相同的 capped 距离，从而得到1/(类别数量)的概率。设y有m个类别，分别表示为C1、C2、…、Cm，并设k1、k2、…、km为kNN中每个类别的k值。kNNPC中的模型构建算法如下：

1. 对于类别i中的每个样本，计算其与最近ki个样本的平均距离（不包括自身），这适用于所有类别。
2. 计算每个类别的平均距离值中的最大值。
3. 将所有类别的最大值中的最小值设置为阈值。预测样本j属于类别p的概率的算法如下：

然后，分配概率最高的类别。距离限制步骤是kNNPC与普通基于软距离的kNN概率的主要区别。对于远离所有类别的查询样本，所有类别的距离都会超过阈值。经过限制后，所有类别的距离都变为阈值。因此，转换后的索引对所有类别都是相同的，归一化后得到概率1/m。相比之下，如果没有这个限制操作，较大的类别距离之间的差异仍可能转换为看似自信的概率。方程（1）和（2）可以解释为类别kNN距离的高斯核归一化，因此与这些先前的方法[10, 11]密切相关。本研究的贡献不在于使用这种距离到概率的转换本身，而在于引入了一个明确的距离限制步骤。当样本远离训练数据时，kNNPC能够将每个类别的概率调整为1/(类别数量)。此外，如图1a所示，样本的变异性预计会在不同类别和同一类别内的不同簇之间变化，因此改变ki值允许kNNPC处理这种变异性差异。已经提出了几种基于邻域的方法，从样本之间的距离或相似性中获得软概率或类似概率的类别分配，包括软kNN类型的投票方案和保持邻域的公式[10, 11]。本研究并不声称在将邻域信息转换为类似概率的输出这一通用想法上的原创性。相反，本研究的重点是一种简单的逐类别kNN公式，具有明确的阈值机制，当样本远离训练数据时，预测的类别概率向量接近最大不确定性分布。这种设计旨在作为对外推区域中过度自信预测的实际保障。应该注意的是，已经提出了几种kNN的变体来处理外推或异常检测，例如半径最近邻方法和选择性拒绝分类[12-17]。同样，也探索了自适应k最近邻规则来处理不同的局部数据密度。我们的kNNPC基于这些概念，但特别关注在材料设计中的多类别问题中调整类别概率。单类别分类器、基于隔离的方法和其他新颖性检测方法对于检测或拒绝训练域之外的样本非常相关。然而，它们的输出通常是异常分数或接受/拒绝决策，而不是所有类别的校准类别成员概率。因此，它们解决的是与本研究相关但不同的任务。kNNPC适用于仍然需要为每个样本提供类别概率的情况，同时应避免外推区域中的过度自信概率。将kNNPC与单类别或基于隔离的方法结合，并对这些混合工作流程进行基准测试将是未来工作的重要课题。虽然许多基于适用性域的方法侧重于定义模型的边界并拒绝该域之外的样本，但本研究的方法旨在以概率方式处理这些外推区域。kNNPC与单类别或基于隔离的方法结合，并对这些混合工作流程进行基准测试将是未来工作的重要课题。尽管许多基于适用性域的方法侧重于定义模型的边界并拒绝该域之外的样本，但本研究的方法旨在以概率方式处理这些外推区域。与拒绝预测不同，kNNPC在这些区域为所有类别分配相等的概率，从而避免了传统分类器对未知样本分配高概率的问题。尽管这种方法没有区分决策边界（高随机不确定性）和外推区域（高认知不确定性），但它提供了对外推区域中误导性高置信预测的合理保障。使用Iris数据集以及有机化合物数据集和无机化合物数据集证明了kNNPC相对于传统分类方法的有效性。为了从基础和实际的角度检验kNNPC的行为，使用了简单的基准数据集和真实世界的化学/材料数据集。选择Iris数据集是因为它允许在低维空间中直观地可视化概率行为，而毒性和超导体数据集用于评估所提出的方法是否也适用于更现实的化学计量学和材料信息学场景。这种数据集的组合不仅用于评估概率图的可解释性，还用于评估在应用导向问题中的实际预测性能。

给定一个查询样本，kNNPC计算查询样本到每个类别的训练样本的类别平均kNN距离，并将这些距离转换为类别成员概率。为类别距离设置一个阈值，超过阈值的距离将被替换为该阈值。因此，远离所有类别训练数据的查询样本在每个类别都有相同的 capped 距离，从而得到1/(类别数量)的概率。设y有m个类别，分别表示为C1、C2、…、Cm，并设k1、k2、…、km为kNN中每个类别的k值。kNNPC中的模型构建算法如下：

1. 对于类别i中的每个样本，计算其与最近ki个样本（不包括自身）的平均距离，这适用于所有类别。
2. 计算每个类别的平均距离值中的最大值。
3. 将所有类别的最大值中的最小值设置为阈值。预测样本j属于类别p的概率的算法如下：

然后，分配概率最高的类别。距离限制步骤是kNNPC与普通基于软距离的kNN概率的主要区别。对于远离所有类别的查询样本，所有类别的距离都超过阈值。经过限制后，所有类别的距离都变为阈值。因此，转换后的索引对所有类别都是相同的，归一化后得到概率1/m。相比之下，如果没有这个限制操作，较大的类别距离之间的差异仍可能转换为看似自信的概率。方程（1）和（2）可以解释为类别kNN距离的高斯核归一化，因此与这些先前的方法[10, 11]密切相关。本研究的贡献不在于使用这种距离到概率的转换本身，而在于在归一化之前引入了一个明确的距离限制步骤。当查询样本远离所有类别的训练样本时，所有类别的距离都超过阈值并被替换为相同的值。因此，得到的概率向量接近（1/m, …, 1/m），这防止了不受支持的外推区域样本获得看似自信的类别概率。当前实验评估了这种完整的限制公式。与个别软kNN变体的系统实证比较以及限制步骤的消融将是未来有价值的工作。将kNNPC从二元分类扩展到多类别分类是直接的。对于查询样本，分别计算到最近ki个训练样本的平均距离。这些类别距离被限制，转换为相对指数，并归一化，使得所有类别的概率之和为一。因此，当查询样本接近特定类别的训练样本时，该类别的预测概率相对较高。相比之下，当查询样本与所有类别的训练数据相差较远时，各类别之间的距离上限变得相似，预测概率向量趋近于最大不确定性分布，即每个类别的概率为1/m。超参数包括距离类型和ki。在本研究中采用了欧几里得距离。对于每个类别的ki超参数，如果有n个候选值，则需要对所有组合进行全网格搜索，并进行交叉验证。因此，通过结合贝叶斯优化和交叉验证来优化ki。在贝叶斯优化中，目标函数被设置为最大化训练数据上的交叉验证准确率。ki的搜索范围从1到所有类别中最小的训练样本数量，优化过程旨在找到在训练集内最大化泛化性能的最佳ki值。所有模型选择仅使用训练数据完成。测试数据未用于超参数选择，仅用于最终评估。对于每种方法，都在训练数据上使用了分层五折交叉验证，并以平均交叉验证准确率作为优化标准。

2.1 kNN、LR、SVM、RF和XGB

对于LR和XGB，没有进行超参数选择，使用默认值。对于kNN，邻居数量在{1, 2, …, 29, 30}之间搜索，使用欧几里得距离。对于SVM，使用高斯核，C和gamma分别在{2?10, 2?9, …, 29, 210}和{2?20, 2?19, …, 29, 210}之间搜索。对于RF，在{0.1, 0.2, …, 0.9, 1.0}之间搜索特征选择率。通过网格搜索来最大化分层五折交叉验证准确率。

3 结果与讨论

提出的方法kNNPC的有效性通过图1中的二类Iris数据集、[3, 4]中的三类Iris数据集、有机化合物的毒性数据集[18]以及无机超导体的转变温度（Tc）数据集[19, 20]进行了验证。对于所有数据集，数据被随机分为训练数据（75%）和测试数据（25%），并在完成训练数据上的模型选择后使用测试数据评估预测性能。对于二类Iris数据集，setosa被分配到类别1，versicolor和virginica合并到类别0。总样本数为150个，其中类别1有50个样本，类别0有100个样本。训练/测试分割后，训练集共有112个样本（类别1：37个，类别0：75个），测试集共有38个样本（类别1：13个，类别0：25个）。对于三类Iris数据集，响应变量是原始的Iris类别：setosa、virginica或versicolor，共有四个特征。应用了主成分分析，并使用前两个主成分（PC1和PC2），它们共同解释了95.8%的方差，用于可视化和此说明性分析中的二维特征向量。总样本数为150个，包括50个setosa样本、50个versicolor样本和50个virginica样本。训练/测试分割后，训练集共有112个样本（setosa：37个，versicolor：38个，virginica：37个），测试集共有38个样本（setosa：13个，versicolor：12个，virginica：13个）。对训练数据进行了主成分分析，并使用相同的加载向量将测试数据投影到主成分空间，以避免信息泄露。毒性数据集包含1213种有机化合物，来自一个在线挑战赛，该挑战赛邀请研究人员估计这些化合物对Tetrahymena pyriformis的毒性。它包含了50%生长抑制浓度（pIGC50）的对数值。对于这种分类，pIGC50≥0.25的化合物被分配到类别1，pIGC50<0.25的化合物被分配到类别0。完整的毒性数据集共有1213个样本，包括609个类别1样本和604个类别0样本。训练/测试分割后，训练集共有910个样本（类别1：457个，类别0：453个），测试集共有303个样本（类别1：152个，类别0：151个）。使用RDKit [21]计算化合物的分子描述符。对于无机超导体的Tc数据集，仅在极少数化合物中出现的元素可能导致训练/测试分割后的模型评估不稳定。因此，分析限制在由20个最常见元素组成的化合物上，从而得到一个包含4146个样本的数据集。Tc≥77 K的样本被分类为类别1，而Tc<77 K的样本被分类为类别0。数据集共有4146个样本，包括1158个类别1样本和2988个类别0样本。训练/测试分割后，训练集共有3110个样本（类别1：869个，类别0：2241个），测试集共有303个样本（类别1：289个，类别0：747个）。特征向量表示每种金属元素的比例。图2显示了使用与图1相同的二类Iris数据集，在显示的特征空间上使用kNNPC计算类别1概率的结果。与图1相比，概率仅在类别1样本附近较高，在类别0样本附近较低，在远离两个类别的区域为50%。而传统方法在特征空间的外推区域分配100%或0%的概率，所提出的kNNPC在训练数据附近没有支持的类别区域分配了大约50%的保守概率。

图2显示了二类Iris数据集的kNNPC分类结果。绘制的符号代表用于构建每个模型的训练样本。十字表示类别1（setosa），点表示类别0（virginica和versicolor）。图3显示了使用三类Iris数据集构建每个模型的结果，并计算了在显示的特征空间上每个类别的概率。图1-3中的概率图旨在可视化模型在特征空间上的行为，而测试样本的预测性能在表1-3中进行了定量总结。如图3所示，传统方法在某些靠近训练样本的区域分配了非常高的类别概率，即使在远离训练样本的区域也是如此，而这些区域本来就难以进行可靠的类别预测。相比之下，使用所提出的kNNPC，如图3p-r所示，概率仅在目标类别的样本附近较高，在其他类别的样本附近较低，在特征空间的外推区域大约为33%。这证实了所提出的方法通过产生更保守（最大不确定性导向）的概率来减轻了训练分布之外样本的过度自信概率输出。在多类设置中，图3中的每个面板应解释为一个目标类别的概率图。因此，对应于给定方法的三个面板共同代表了三个类别的完整概率向量。结果表明，kNNPC仅在相应类别的训练样本附近提供特定类别的高概率，而在训练数据不支持的区域分配了几乎均匀的概率。这种行为与多类情况下对外推区域的保守概率处理是一致的。

表1. 使用Iris数据集进行测试数据分类方法的预测结果。两类

三类

准确率

召回率

精确度

F1分数

AUC

准确率

kNN

0.97

1.00

0.96

0.98

0.96

0.89

LR

1.00

1.00

1.00

1.00

1.00

0.92

SVM

0.97

1.00

0.96

0.98

1.00

0.84

RF

1.00

1.00

1.00

1.00

1.00

0.92

XGB

1.00

1.00

1.00

1.00

1.00

0.89

kNNPC

0.97

1.00

0.96

0.98

1.00

0.92

表2. 使用毒性数据集进行测试数据分类方法的预测结果。准确率

召回率

精确度

F1分数

AUC

kNN

0.83

0.79

0.86

0.82

0.93

LR

0.86

0.88

0.85

0.86

0.94

SVM

0.89

0.88

0.90

0.89

0.96

RF

0.88

0.88

0.88

0.88

0.95

XGB

0.88

0.88

0.88

0.88

0.95

kNNPC

0.86

0.80

0.90

0.85

0.93

表3. 使用Tc数据集进行测试数据分类方法的预测结果。准确率

召回率

精确度

F1分数

AUC

kNN

0.88

0.80

0.78

0.79

0.86

LR

0.79

0.58

0.65

0.61

0.88

SVM

0.89

0.81

0.81

0.81

0.93

RF

0.89

0.83

0.80

0.81

0.95

XGB

0.88

0.84

0.76

0.80

0.95

kNNPC

0.89

0.80

0.79

0.80

0.94

表1显示了二类Iris数据集的测试数据预测结果，表2显示了有机化合物毒性数据集的测试数据预测结果，表3显示了无机超导体Tc数据集的测试数据预测结果。表1-3中的性能比较目的不是为了证明kNNPC在标准分类指标上普遍优于所有现有分类器。相反，目的是展示kNNPC可以在外推区域抑制过度自信的概率输出，同时保持与广泛使用的分类方法相当的预测性能。从这个角度来看，准确率、召回率、精确度、F1分数和AUC的可比值是有意义的，因为它们表明所提出的概率调整不会显著损害常规分类性能。包括软kNN变体、新颖性检测方法、单类分类器和其他不确定性感知方法在内的更广泛比较将是有价值的，但这样的基准超出了本研究的范围，将在未来的工作中进行探讨。对于三类Iris数据集，kNNPC实现了与最佳性能方法相当的准确率。这一结果表明，所提出的基于类别的距离公式可以扩展到多类判别问题，而不会损失整体预测性能。尽管这里仅报告了三类情况的整体准确率，但图3中的概率图提供了补充信息，表明特定类别的概率与kNNPC的预期设计一致。更详细的类别分析将是有信息量的，并将在未来的工作中考虑。在二类Iris数据集中，kNNPC的准确率不是最高的，但其准确率与其他方法相当，召回率、精确度和ROC曲线下面积的值也与其他方法相当。虽然其他方法在特征空间的外推区域产生了过度自信的概率，如图1所示，但kNNPC对测试样本进行了类似的预测性能分类，并对外推区域分配了更保守的概率，表明所提出的kNNPC方法可以为域外样本提供更保守的概率输出。对于毒性数据集，kNNPC在所有传统指标上没有取得最高值，但其性能与广泛使用的分类器相当。这一结果表明，所提出的概率调整在提供与训练数据不相似的样本的更保守行为的同时，不会显著损害常规判别性能。对于Tc数据集也观察到了类似的趋势。kNNPC的传统指标与其他分类器相当，而其概率输出旨在避免在训练数据支持不足的区域产生过度自信的预测。这一属性在材料探索中特别有意义，因为候选化合物通常位于观察数据集的密集区域之外。总体而言，这些结果表明，kNNPC的主要优势在于它能够为那些位于训练数据代表性不足区域的样本提供保守且易于解释的类别概率，同时保持与标准分类器相当的预测性能。在实际分类性能与抑制过度自信的概率输出之间的这种平衡在化学计量学、分子设计、材料探索以及工艺相关应用中尤为重要，因为这些应用中的模型通常需要应用于观测数据密集区域之外的候选对象。

4 结论

为了解决传统分类器（如kNN、LR、SVM、RF和XGB）在特征空间外推区域中经常出现的过度自信预测问题，本研究提出了kNNPC方法。该方法计算每个类别到最近邻样本的平均距离，并引入一个阈值，以便在特征空间的外推区域为每个类别分配相同的概率。这一框架使得即使在远离训练数据的区域也能输出保守的概率值。通过对Iris数据集（包含两类和三类样本）、有机化合物的毒性数据集以及无机化合物的超导转变温度数据集的验证表明，kNNPC能够在外推区域减少过度自信的概率估计，同时在准确性、召回率、精确度、F1分数和AUC等方面保持与标准分类器相当的性能。在包含三类的Iris数据集中，kNNPC的准确性与表现最佳的方法相当，并且在训练数据未覆盖的区域提供了保守的概率分布图。这些结果表明，kNNPC是一种在不可避免需要外推的领域（如分子设计、材料与工艺设计、材料探索和工艺管理）中进行可靠分类的有效方法。未来的工作将致力于将该方法扩展到大规模和高维数据集，并将其与集成学习和深度学习相结合，以进一步扩展其应用范围并提高其鲁棒性。未来的研究还将包括与软kNN变体的系统实证比较、对阈值调整操作的消融研究，以及将kNNPC与新奇性检测或适用性领域方法相结合的混合工作流程。所提出方法的Python代码可在https://github.com/hkaneko1985/dcekit获取。

致谢

本研究得到了日本学术振兴会（KAKENHI）的科研资助（项目编号24K08152和24K01234）的支持。

资金支持

本研究得到了日本学术振兴会（项目编号24K08152和24K01234）的资助。

数据可用性声明

支持本研究结果的数据可应相应作者的要求提供。