arXiv:2501.11526cs.LGcs.AI2025-01

把选样本变成分类任务,用元特征加速近邻分类。

Meta-Instance Selection. Instance Selection as a Classification Problem with Meta-Features

  • 将样本选择转为元特征空间中的分类问题。
  • 在17个数据集上效果接近传统方法,计算量大幅降低。
  • 适合需要快速推理的近邻学习场景,推荐用平衡随机森林。

数据剪枝(实例选择)是机器学习中重要问题,尤其对近邻分类器而言。但现有方法在加速预测阶段的同时,自身计算效率较低。本文提出将实例选择转化为统一元特征空间中的分类任务,每个实例被分类为“保留”或“删除”。通过历史数据集上的实例选择结果构建标签,训练元分类器。元特征基于最近邻图属性提取。在17个不同规模的数据集和5种参考方法(ENN、Drop3、ICF、HMN-EI、CCIS)上实验表明,该方法性能接近基准,且计算复杂度显著降低:仅需计算每个样本的k近邻并运行元分类器。研究还建议使用平衡随机森林作为元分类器。

原文摘要 · Abstract (English)

Data pruning, or instance selection, is an important problem in machine learning especially in terms of nearest neighbour classifier. However, in data pruning which speeds up the prediction phase, there is an issue related to the speed and efficiency of the process itself. In response, the study proposes an approach involving transforming the instance selection process into a classification task conducted in a unified meta-feature space where each instance can be classified and assigned to either the "to keep" or "to remove" class. This approach requires training an appropriate meta-classifier, which can be developed based on historical instance selection results from other datasets using reference instance selection methods as a labeling tool. This work proposes constructing the meta-feature space based on properties extracted from the nearest neighbor graph. Experiments conducted on 17 datasets of varying sizes and five reference instance selection methods (ENN, Drop3, ICF, HMN-EI, and CCIS) demonstrate that the proposed solution achieves results comparable to reference instance selection methods while significantly reducing computational complexity. In the proposed approach, the computational complexity of the system depends only on identifying the k-nearest neighbors for each data sample and running the meta-classifier. Additionally, the study discusses the choice of meta-classifier, recommending the use of Balanced Random Forest.

实例选择近邻分类元特征加速推理

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。