关键词: 决策树, ID3算法, 上凸函数, 信息熵

Abstract: In this paper,we research deeply the theory of decision trees induction.According to the character of expected information and the quality of convex function,we propose a new algorithm to raise the efficiency of calculating expected information in the process of inducing the decision trees.By using the theory of consistency and special consistency,we also prove that the accuracy of decision trees constructed by the improved algorithm is equal to the one of ID3 algorithm.At the same time,through the experiment of testing the large datasets,we find that the new algorithm has higher calculative efficiency than the old one in the same datasets.Moreover with the larger scale of datasets,the calculation of expected information has more rapid efficiency.

Key words: decision tress, ID3 Algorithm, convex function, expected information