On inducing topologically minimal decision trees
Tapio Elomaa, J. Kivinen · [1990] Proceedings of the 2nd International IEEE Conference on Tools for Artificial Intelligence · 2002
Both theoretical and empirical results are presented concerning W. Van de Velde's (1989, 1990) decision tree induction algorithm IDL. Contrary to a conjecture by Van de Velde, the algorithm does not always produce a topologically minimal tree. This is true both of IDL used as an incremental decision tree induction algorithm and of IDL used as a post-processor for trees generated by TDIDT. Experiments have been made on using IDL in post-processing trees produced by ID3. The test domains are exclusive-OR functions with irrelevant attributes. The results show that in this domain IDL removes efficiently the tests of irrelevant attributes from the trees. The computational complexity analysis of IDL is reviewed.>