This paper proposes a novel ensemble algorithm aimed at improving the performance of k-Nearest Neighbors (KNN) classification by incorporating feature bagging techniques, which help overcome the inherent limitations of KNN in Big Data scenarios. The proposed algorithm, termed FBE (Feature Bagging-based Ensemble), employs an efficient ensemble strategy with sorted feature subset techniques to reduce the time complexity from linear to logarithmic. By focusing on essential features during iterative training and utilizing a binary search in the testing phase, FBE boosts computational efficiency and accuracy in high-dimensional and imbalanced datasets. Our study rigorously evaluates the proposed FBE algorithm against traditional KNN, Random Forest (RF), and AdaBoost algorithms across ten benchmark datasets from the UCI Machine Learning Repository. The experimental results demonstrate that FBE not only outperforms the conventional KNN and AdaBoost across all evaluated metrics (accuracy, precision, recall, and F1 score) but also shows competitive performance compared to RF. Specifically, FBE exhibits remarkable improvements in datasets characterized by high dimensionality and class imbalances. The main contributions of this research include the development of an adaptive KNN framework that addresses the typical computational demands and vulnerability to noise in the data, making it well-suited for large-scale datasets. The ensemble methodology within FBE also helps reduce overfitting, a common challenge in standard KNN models, by diversifying the decision-making process across multiple data subsets. This strategy ensures robustness and reliability, positioning FBE as a suitable tool for classification tasks in diverse domains such as healthcare and image processing.