In the Clinical Decision Support System (CDSS), over-fitting phenomenon may appear when decision tree algorithm was used. For this problem, this paper will make use of the Rough Set theory to the training set for attribute reduction, the decision tree built by using the decision tree algorithm was used to predict the test data. In this paper, 46 copies of coronary heart disease clinical data were used to test the improved algorithm. Comparing the accuracy of the algorithm and the improved algorithm, we can know that, the improved algorithm has a better recognition rate for the diagnosis of coronary heart disease, and effectively solves the over-fitting phenomenon in the Decision Tree Algorithm.