摘要：针对决策树分类方法的计算效率进行深入研究,根据信息增益计算的特点,引入了上凸函数的概念,用于提高决策树分类过程中信息增益的计算效率.利用我们所提出的"一致性定理"和"特殊一致性定理",从理论上证明了利用上凸函数对信息增益计算进行改进后,构造的决策树与原决策树具有相同的分类准确率.同时我们通过对大数据集的实验,发现在相同规模的数据集下,改进后的决策树算法比原算法有更高的计算效率,并且这种计算效率的提高有随着数据集规模的增加而增加的趋势.

关键词：决策树 id3算法 上凸函数 信息熵 

单位：北京科技大学管理学院; 北京; 100083