Instance selection, also known as dataset reduction or dataset condensation, is a data pre-processing step applied in many Machine learning and data mining tasks. Its primary purpose is to reduce the original dataset to a manageable volume, thereby lowering the computational resources required for the learning process. Additionally, instance selection algorithms can remove noisy instances before learning, which can improve accuracy in classification problems. The optimal outcome is the minimum data subset that achieves the same task with no performance loss compared to using the entire dataset, requiring a trade-off between reduction rate and classification quality.
Algorithm Categories
Instance selection algorithms are grouped by the type of instances they preserve. One class focuses on boundary instances, which lie near class decision frontiers. Algorithms in this group include DROP3, ICF, and LSBo. Another class preserves internal instances, which are central to each class; examples include ENN and LSSm. These internal-selection algorithms are often used to filter harmful or noisy instances, and they may serve as preprocessing steps for boundary-selection methods. For instance, ENN is the first step in DROP3, and LSSm is used by LSBo.
A third category selects the densest instances within arbitrary neighborhoods, potentially including both boundary and internal points. Algorithms such as LDIS, CDIS, and XLDIS fall here. LDIS and CDIS are simple and produce subsets highly representative of the original data. Because they search for representative instances separately within each class, they are faster in time complexity and effective running time than algorithms like DROP3 and ICF.
Prototype-Based Approaches
Some algorithms do not select actual instances but instead generate synthetic prototypes. PSSA, PSDSP, and PSSP use the notion of spatial partition, specifically hyperrectangles, to identify similar instances and extract a prototype for each group. These approaches can be adapted to select actual instances as well; the algorithm ISDSP follows a similar strategy but chooses real instances rather than prototypes.
Applications and Trade-offs
Instance selection is valuable in scenarios with large datasets where training time and memory usage are significant concerns. By reducing the dataset, it enables faster model training and can improve generalization by eliminating noise. However, aggressive reduction risks losing informative instances, potentially degrading classification performance. The balance between reduction rate and accuracy is central to evaluating any instance selection strategy.
Relation to Other Techniques
Instance selection is distinct from Data Augmentation, which generates new synthetic samples to expand the dataset, and from Model Pruning, which reduces model complexity after training. It is also different from feature selection, which reduces the number of attributes rather than instances. In practice, instance selection is often combined with other preprocessing steps to optimize the overall machine learning pipeline.
Evaluation and Practical Considerations
Common evaluation metrics include reduction rate, which measures the proportion of instances removed, and classification accuracy on a held-out test set. The choice of algorithm depends on the data distribution and the specific goals, such as noise removal versus maximum reduction. Algorithms like ENN are effective for cleaning noisy datasets, while boundary-based methods like DROP3 aim to retain critical decision boundaries. The computational cost of the selection process itself is also a factor, with simpler methods like LDIS being preferred for very large datasets.
Future Directions
Research continues to explore more efficient and scalable instance selection methods, particularly for high-dimensional data and Deep learning applications. There is interest in integrating instance selection with Neural network training pipelines, where reducing the dataset can accelerate training without significant accuracy loss. As datasets grow in size and complexity, instance selection remains a relevant tool for managing computational resources in Artificial intelligence systems.