
## 4.3 Learning Algorithms

We chose three well known algorithms from the machine learning and statistical pattern recognition communities to form the filters decision trees nearest neighbor classifiers and linear machines We restrict the presentation of our empirical results to these three algo rithms to enhance the clarity of our presentation of the method and to reduce the number of tables presented However in addition to the experiments reported  we also ran experiments with five base level algorithms the three in this paper plus NN and LMDT Brodley Our results for the increased set of learning algorithms showed the same Utgoff trends as those reported in this article A univariate decision tree (D-Tree) is either a leaf node containing a classification or an attribute test with for each value of the attribute a branch to a decision tree To classify an instance using a decision tree one starts at the root node and finds the branch corresponding to the value of the test attribute observed in the instance This process repeats at the subtree rooted at that branch until a leaf node is reached The instance is then assigned the class label of the leaf One well known approach to constructing a decision tree is to grow a tree until each of the terminal nodes leaves contain instances from a single class and then prune back the tree with the objective of finding the subtree with the lowest misclassification rate  Our implemented algorithm uses C
s pruning method with a confidence level of Quinlan To select a test for a node in the tree  we choose the test that maximizes the information gain ratio metric  Quinlan Our implementation sets the minimum number of in stances to form a test node to be equal to two Univariate decision tree algorithms require that each test have a discrete number of outcomes  To meet this requirement  each ordered feature Ai is mapped to a set of unordered features by finding a set of Boolean tests of the form Ai b where b is in the observed range and is a cut point of Ai Our algorithm finds the value of b that maximizes the information gain ratio  To this end  the observed values for A; are sorted and the midpoints between class boundaries are evaluated Quinlan Fayyad Irani A k-nearest neighbor (k-NN) classifier  Duda   Hart is a set of n instances each from one of m classes that are used to classify an unlabeled instance according to the majority classification of the instance s k nearest neighbors  In this version of the algorithm each instance in the training data presented to the algorithm is retained To determine the distance between a pair of instances we apply the Euclidean distance metric In our experiments k was set to one A linear machine (LM) is a set of R linear discriminant functions that are used collec tively to assign an instance to one of the R classes Nilsson Let Y be an instance description a pattern vector consisting of a constant and the n features that describe the instance Then each discriminant function gi Y has the form W? Y  where Wi is a vector cc of n