This paper analyzes the existing decision tree algorithms for dealing with multi-valued and multi-labeled data. These algorithms have the following shortcomings: The choice of which attributes is difficult and the calculation for similarity is not precise enough. Based on these deficiencies, this paper proposes a new decision tree algorithm for multi-valued and multi-labeled data (AMDT). In the algorithm, firstly a new formula sim5 is proposed for calculating the similarity between two label-sets in the child nodes. It comprehensively considers the condition which the elements appear and not appear in both of the two label-sets at the same time and adjusts the proportion of them by the coefficient α, so that the similarity calculations of the label-sets are more comprehensive and accurate. Secondly, we propose the new conditions of the corresponding node to stop splitting. Lastly, we give the prediction method. Results of comparison experiments with the existing algorithms (MMC, SSC and SCC_SP_1) show that AMDT has the higher predictive accuracy.