Ensemble learning has been widely used for improving classification accuracy. Recent studies show that building ensemble classifiers through a multi-modal perturbation strategy can further improve classification performance. In this study, we propose an ensemble pruning algorithm based on approximate reducts and optimal sampling (EPA_AO). In EPA_AO, we design the multi-modal perturbation strategy to build different individual classifiers. The proposed perturbation strategy can simultaneously perturb the attribute space and training set, which can improve the diversity of individual classifiers. We use the evidential K-nearest neighbor (KNN) algorithm to train individual classifiers and compare EPA_AO with existing algorithms of the same type on multiple UCI data sets. Experimental results show that EPA_AO is an effective ensemble learning approach.