As a decision tree generated algorithm, C4.5 algorithm is very influential. But the decision tree classification by C4.5 algorithm is of less accuracy, more branches, and larger scale. To solve these problems, we propose a C4.5 improved algorithm based on rough set theory and CAIM criterion. The algorithm uses the discretization method based on CAIM criterion to process the continuous attributes, which decreases the information loss degree and improve the classification accuracy in discretization. The discretized sample is reduced by attribute reduction method based on rough set theory, which eliminates the redundant attribute and trims the size of decision tree. Experiments show that the algorithm can effectively improve the classification accuracy of decision tree generated by C4.5 algorithm and reduce the scale of decision tree.