Machine learning-aided medical decision making presents three major challenges: achieving model parsimony, ensuring credible predictions, and providing real-time recommendations with high computational efficiency. In this paper, we formulate medical decision making as a classification problem and develop a moment kernel machine (MKM) to tackle these challenges. The main idea of our approach is to treat the clinical data of each patient as a probability distribution and leverage moment representations of these distributions to build the MKM, which transforms the high-dimensional clinical data to low-dimensional representations while retaining essential information. We then apply this machine to various pre-surgical clinical datasets to predict surgical outcomes and inform medical decision making, which requires significantly less computational power and time for classification while yielding favorable performance compared to existing methods. Moreover, we utilize synthetic datasets to demonstrate that the developed moment-based data mining framework is robust to noise and missing data, and achieves model parsimony giving an efficient way to generate satisfactory predictions to aid personalized medical decision making.