Available clinical methods for heart failure (HF) diagnosis are expensive and require a high-level of experts intervention. Recently, various machine learning models have been developed for the prediction of HF where most of them have an issue of over-fitting. Over-fitting occurs when machine learning based predictive models show better performance on the training data yet demonstrate a poor performance on the testing data and the other way around. Developing a machine learning model which is able to produce generalization capabilities (such that the model exhibits better performance on both the training and the testing data sets) could overall minimize the prediction errors. Hence, such prediction models could potentially be helpful to cardiologists for the effective diagnose of HF. This paper proposes a two-stage decision support system to overcome the over-fitting issue and to optimize the generalization factor. The first stage uses a mutual information based statistical model while the second stage uses a neural network. We applied our approach to the HF subset of publicly available Cleveland heart disease database. Our experimental results show that the proposed decision support system has optimized the generalization capabilities and has reduced the mean percent error (MPE) to 8.8% which is significantly less than the recently published studies. In addition, our model exhibits a 93.33% accuracy rate which is higher than twenty eight recently developed HF risk prediction models that achieved accuracy in the range of 57.85% to 92.31%. We can hope that our decision support system will be helpful to cardiologists if deployed in clinical setup.