增量决策树算法研究

文中主要解决传统的ID3算法不能处理增量数据集构造决策树的问题。在传统ID3决策树算法和原有增量算法的基础上,利用信息论中熵变原理的特点,对与增量决策树算法相关的三个定理进行相应的改进,在理论上证明了改进的增量决策树算法的有效性和可靠性。同时对增量决策树算法和ID3算法的复杂度进行了对比分析,得出增量决策树算法的实例费用和信息熵费用都高于ID3算法的结论。最后通过一个实验证明,改进的增量决策树算法能够构造出与ID3算法形态基本相同的决策树。

Researches on Incremental Alogrithm of Decision Trees

The problem that the traditional ID3 algorithm can't deal with the decision trees from incremental datasets is solved.According to the character of entropy diversification in the fields of information theory,improves three theorem of incremental decision trees and proves the validity and reliability of the new algorithm in the base of the original ID3 and incremental algorithm. Moreover, the incremental algorithm and ID3 algorithm are compared in terms of calculative complexity and draw the conclusion that incremental algorithm has higher calculative complexity than ID3 algorithm's in terms of instance count additions and entropy score. Finally through the training instance, the incremental algorithm can induce the shape of decision trees equivalent to those formed by the ID3 algorithm.