Meta-Instance Selection. Instance Selection as a Classification Problem with Meta-Features.
Marcin Blachnik, Piotr Ciepliński · 2025
Read Meta-Instance Selection. Instance Selection as a Classification Problem with Meta-Features. by Marcin Blachnik, Piotr Ciepliński (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-11526.txt.
Introduction
Marcin Blachnik and Piotr Ciepliński turn data pruning into a sorting task in a shared feature space in 2025. Pruning picks which training cases a nearest neighbor method should keep. It speeds later use, yet pruning itself can be slow. Their plan tags each case as keep or drop using a meta model. That model learns from past pruning runs on other data sets.
Features come from each case's neighbor graph. Seventeen data sets and five classic pruning methods supplied the tests. Results matched the classic methods while costing far less to run. Cost now scales with finding neighbors and running one sort. A balanced forest model is their pick for the sorter.
Catalog record
| CREATOR | Marcin Blachnik, Piotr Ciepliński |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-11526
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Meta-Instance Selection. Instance Selection as a Classification Problem with Meta-Features. Marcin Blachnik, Piotr Ciepliński Abstract 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. 1 Intrduction Currently, increasing attention is being paid to the issue of filtering data used in the learning process, with a focus on removing useless and noisy data samples. Hence, more and more dedicated solutions are being developed to filter out unimportant samples [ 1 ] and constitute the new paradigm called data-centric AI [ 2 ] . Additionally, the scaling law turns into the requirement of huge compute power both during training and prediction which is not always applicable in real live scenarios where the compute resources are limited. In that case, both the training data and the prediction model should require small computing resources. Therefore the training set should ensure a possible small size but keep the prediction accuracy of the original training set. This issue is not new, along with its development has been started primarily for the nearest neighbor classifier under the name of instance selection. Thus, already in the late 1960s and early 1970s, algorithms such as Condensed Nearest Neighbor (CNN), Edited Nearest Neighbor (ENN), and many others were developed. The benchmarks of instance selection indicate the Drop3 [ 3 ] and ICF [ 4 ] algorithms as the most wildly used, which, despite not being new, are characterized by excellent properties in terms of the balance between the prediction accuracy of the kNN algorithm and the reduction of the size of the stored set of prototypes ( reduction\_rate ) [ 5 ] . These algorithms are also applicable not only as elements of the learning process for the kNN algorithm (prototype selection as part of the learning process) and hence could also be used as universal algorithms for reducing the size of the training set for any classifier, thereby accelerating the learning process of complex predictive models, the process of finding optimal parameters, etc. Examples of such applications can be found in [ 6 , 7 ] or in [ 5 ] . All algorithms belonging to the Instance Selection group share one common element, namely, they explore the structure of the nearest neighbors graph by determining connections between the k nearest samples and their interdependencies to identify vectors that are significant for the decision boundary. This article is also concerned with the challenge of building an instance selection system, however with a different approach by converting the instance selection process into the binary classification problem. Instance selection algorithms typically rely on the analysis of a nearest-neighbor graph. In the nearest neighbor graph, the vertices correspond to individual instances of the training set, and the edges contain information about the nearest neighbors of a given vector. Instance selection algorithms iteratively, often repeatedly, traverse the graph’s vertices, allowing to identify whether a particular vector can be important in the learning process or not. But it is important to note, that the characteristics of the nearest neighbors graph (NNG) are common and do not depend on the domain or problem described by the dataset. Therefore, by extracting features that describe the vertices in the NNG the problem of instance selection can be converted into a new meta-dataset in a fixed-sized feature space (meta-features), that is common to all possible datasets. Now, when taking all previously conducted results of any instance selection algorithm on any given dataset the binary information of keeping or rejecting an instance can be used as instance labels, leading to a meta-tanning set. This training set can then be used to train a classifier, which will be called a meta-classifier. In prediction mode, a given input dataset for which the instance selection would be performed is represented as an NGG. Then meta-features are extracted and used as input to the meta-classifier which returns a probability indicating the importance of a given instance. This allows us to select instances without running the original instance selection algorithm. To maintain satisfactory generalization of the meta-classier, it is significant to create a meta-data set that combines meta-data describing the NNG extracted not from one but multiple datasets, and concatenating all these datasets together. The conducted analyses show that contrasted to traditional methods of instance selection, for some of them, meta-selection methods allow for better results than the original methods. Moreover, these results are achieved much faster, as the selection process is carried out in a single pass, unlike in instance selection methods, where selection requires iteratively traversing the NNG. An additional advantage of the developed solution is the description of the training samples’ importance as a probability density distribution, indicating how likely a given training vector should be included in the training set without affecting the performance of the classifier or in other words how significant a given vector is in the learning process. The use of a thresholding function allows for determining the number of important samples as a postprocessing step adjusting the desired value to the needs of a given compute resources. The contribution of this article: 1. A new perspective on the data selection process as a classification problem is presented. In the proposed solution a meta-classifier makes decisions about the importance or non-importance of a given training sample. 2. The development of meta-attributes describing the nearest neighbor graph, which also serve as input to the meta-classifier. 3. A new metric for instance selection method performance is proposed Article structure: Section 2 describes the current state of knowledge in the area of data pruning and meta-learning. Section 3 provides a detailed description of the concept, operation, and construction of the meta-classifier, as well as the feature space used to build the meta-classifier. Section 4 presents the experimental design, including the process of building the meta-classifier, performance evauation methods and metrics used to asses its quality. The next section 5 presents the obtained results in comparison to the original instance selection methods. The final chapter 6 contains a summary of the results and future directions for further research. 2 Related Work In this article,