A new sample reduction method for decreasing the running time of the k-nearest neighbors algorithm to diagnose patients with congestive heart failure: backward iterative elimination

Abstract

The model complexity is strictly connected to both the sample size and the number of features in a conventional pattern recognition study. Although there are some sample reduction methods in the literature, they cannot give the highest classifier performance or are not able to achieve the minimum number of samples in general. In this study, we offered a new sample reduction method, named Backward Iterative Elimination. To show its efficiency, we classified congestive heart failure (CHF) patients and healthy subjects from heart rate variability (HRV) features using the k-nearest neighbors (kNN) classifier. We extracted 59 HRV features (time and frequency domain measurements through power spectral density estimates of different transformation methods in addition to nonlinear measures calculated from Poincare plot, sample entropy, symbolic dynamics, and detrended fluctuation analysis) from databases provided by the Massachusetts Institute of Technology and Boston's Beth Israel Hospital. The extracted features were classified using kNN with various odd k values from 1 to 19. The proposed method was compared to three well-known reduction methods: Backward elimination, Gaussian elimination, and Genetic algorithm. The proposed system yielded the highest accuracy values for each k value. While the genetic algorithm achieved the maximum sample size reduction in general, the proposed method showed better sample size reduction performance than other backward elimination methods. The method resulted in a classifier accuracy of 87.95% with 33 samples only. In this case, the algorithm run time reduces to 9.1411 ms, which is 12.1578 ms using all samples. In conclusion, the Backward Iterative Elimination gives the highest classifier performances with an appropriate ratio in sample size reduction so that it can be utilized in pattern recognition studies as a good alternative.