Boosting interclass boundary preservation (BIBP): a KD-tree enhanced data reduction algorithm

Interclass boundary preservation (IBP) is a data reduction technique that maintains only the instances (referred to as “prototypes”) at the decision boundary between consecutive classes of data to reduce the dataset’s size. It augments the original distance-based instance selection (DIS) to support a minimum class size using Naïve random over-sampling, preventing a particular class from being underrepresented in kNN classification. Both techniques suffer from prolonged instance selection execution due to using the Euclidean distance function in a one-versus-rest approach. This paper proposes Boosting Interclass Boundary Preservation (BIBP) and Boosting Distance-Based Instance Selection (BDIS) algorithms that replace the Euclidean distance function with a K-dimensional tree (KD-Tree) in their original algorithms to significantly reduce their runtimes, enhancing applicability to real-world datasets. Through hyperplane partitioning in the KD-Tree, searching for prototypes becomes much faster than a brute-force approach using Euclidean distance. The evaluation was conducted on real-world datasets from the UCI machine learning repository. The results demonstrate that the proposed BIBP and BDIS algorithms achieve significant runtime reductions while maintaining data reduction and classification performance comparable to their original counterparts.