Decision Tree Construction Clause Samples

Decision Tree Construction. { } Decision tree constructing algorithms for data classification such as ID3 [86], C4.5 [87] and CART [14] are all loosely based on a common principle: divide- and-conquer [87]. The algorithms attempt to divide a training set T into multiple (disjoint) subsets so that each subset Ti belongs to a single target class. In the simplest form a training set consisting of N records is divided into N subsets T1,..., TN such that each subset is associated with a single record and target class. However, the predictive capabilities of such a classifier would be limited. Therefore decision tree construction algorithms like C4.5 try to build more general decision trees by limiting the number of partitions (and thereby limiting the size of the constructed decision tree). Since the problem of finding the smallest decision tree consistent with a specific training set is NP-complete [58], machine learning algorithms for constructing decision trees tend to be non-backtracking and greedy in nature. Although the non- backtracking and greedy nature of the algorithms has its advantages, such as resulting in relatively fast algorithms, they do depend heavily on the way the training set is divided into subsets. Algorithms like ID3 and C4.5 proceed in a recursive manner. First an attribute is selected for the root node and each of the branches to the child nodes corresponds with a possible value for this attribute. In this way the data set is split up into subsets according to the value of the attribute. This process is repeated recursively for each of the branches using only the records that occur in a certain branch. If all the records in a subset have the same target class the branch ends in a leaf node with the class prediction. If there are no attributes left to split a subset the branch ends in a leaf node predicting the class that occurs most frequent in the subset.