论文标题
最佳的1-NN原型病理几何原型
Optimal 1-NN Prototypes for Pathological Geometries
论文作者
论文摘要
使用原型方法来减少训练数据集的大小可以大大降低基于实例的学习算法（如K-Nearebt邻居分类器）的分类计算成本。分类器与其原始性能匹配所需的原型的数量和分布与训练数据的几何形状密切相关。结果，通常很难找到给定数据集的最佳原型，而是使用启发式算法。但是，我们认为一个特别具有挑战性的环境，通常使用的启发式算法未能找到合适的原型，并表明可以通过分析找到最佳原型。我们还提出了一种在这种情况下查找几乎最佳原型的算法，并使用它来验证理论结果。
Using prototype methods to reduce the size of training datasets can drastically reduce the computational cost of classification with instance-based learning algorithms like the k-Nearest Neighbour classifier. The number and distribution of prototypes required for the classifier to match its original performance is intimately related to the geometry of the training data. As a result, it is often difficult to find the optimal prototypes for a given dataset, and heuristic algorithms are used instead. However, we consider a particularly challenging setting where commonly used heuristic algorithms fail to find suitable prototypes and show that the optimal prototypes can instead be found analytically. We also propose an algorithm for finding nearly-optimal prototypes in this setting, and use it to empirically validate the theoretical results.
