Instance Selection for the Construction of Large-Margin Classifiers: A Kernel Density Estimation-Based Approach

This paper proposes an instance selection methodology to reduce the computational cost of constructing the Gabriel Graph in classification problems. The approach uses kernel density estimation to identify samples located in regions of greater uncertainty between classes, where structural support vertices tend to concentrate. The graph is then built only on this reduced subset, preserving the information that is most relevant for defining the decision boundary. The methodology was evaluated on synthetic and real datasets through support-edge recovery and functional agreement between the full and reduced separators. The results show that classifier behavior is preserved in several scenarios, while substantially reducing the graph construction cost.