Classification and Regression Trees

For all 642592 possible features a Classification and Regression Tree (CART) is created. CART analysis is a form of binary recursive partitioning. Each node is split into two child nodes, in which case the original node is called a parent node. The term recursive refers to the fact that the binary partitioning process is applied over and over to reach a given number of splits (4 in this case). In order to find the best possible split features, all possible splits are calculated, as well as all possible return values to be used in a split node. The program seeks to maximize the average ``purity'' of the two child nodes using the misclassification error measure. Fig. 5 (left) shows a CART classifier.

Figure 5: Left: A Classification and Regression Tree with 4 splits. According to the specific filter applied to the image input section x, the output of the tree, $h_t(x)$ is calculated, depending on the threshold values. Right: A cascade of CARTs [16]. $h_t(x)$ is determined depending on the path through the tree.