Spectral Graph Optimization for Instance Reduction

The operation of instance-based learning algorithms is based on storing a large set of prototypes in the system´s database. However, such systems often experience issues with storage requirements, sensitivity to noise, and computational complexity, which result in high search and response times. In this brief, we introduce a novel framework that employs spectral graph theory to efficiently partition the dataset to border and internal instances. This is achieved by using a diverse set of border-discriminating features that capture the local friend and enemy profiles of the samples. The fused information from these features is then used via graph-cut modeling approach to generate the final dataset partitions of border and nonborder samples. The proposed method is referred to as the spectral instance reduction (SIR) algorithm. Experiments with a large number of datasets show that SIR performs competitively compared to many other reduction algorithms, in terms of both objectives of classification accuracy and data condensation.