CID3: an extension of ID3 for attributes with ordered domains

Abstract

Quinlan's ID3 is a popular and efficient algorithm for inducing decision trees from concept examples, where the examples are presented as vectors of attribute-value pairs. If some attributes have integer or real domains ID3 tends to generate very complex decision trees. This is due to: (1) an attribute selection heuristic biased towards attributes with domains of large cardinality (2) strong constraints (bias) imposed on decision trees generated and (3) the fact that ID3 does not distinguish between attributes with unordered domains and attributes with linearly ordered (integer or real) domains. ID3- IV and GID3 address the first and second problem respectively. We propose CID3, a generalization of GID3, which addresses the third problem. These algorithms are compared with respect to five criteria for decision tree quality and computational efficiency. The test domain consists of normal and abnormal electrocardiograms (ECGs) described mainly by integer and real attributes. CID3, which implements the weakest bias and uses the most domain knowledge, generates a superior quality decision tree for the ECGs.