Quinlan's ID3 machine learning algorithm induces classification trees (rules) from a set of training examples. The algorithm is extremely effective when training examples are composed of attributes whose values are taken from small discrete domains. The classification accuracy of ID3-produced trees on domains whose attributes are many-valued tends to be marginal due to the large number of possible values which may be associated with each attribute. Attempts to solve this problem by a priori grouping of attribute values into distinct subsets has met with limited success. The dynamic ID3 algorithm improves the performance of ID3 on this type of problem by grouping many-valued attributes dynamically as the tree is built. Experimental results are provided which compare the performance of dynamic ID3 with standard ID3 and ID3 in which a priori grouping has been used.
Available at: http://works.bepress.com/chaman-sabharwal/25/