language: en

Goal-Directed Classification using Linear Machine Decision Trees *

Bruce A. Draper Carla E. Brodley Paul E. Utgoff
Department of Computer Science University of Massachusetts
Amherst, MA., USA. 01003
bdraper@cs.umass.edu September 17, 1993

Abstract Recent work in feature-based classification has focused on non-parametric techniques that can classify instances even when the underlying feature distributions are unknown. The inference algorithms for training these techniques, however, are designed to maximize the accuracy of the classifier, with all errors weighted equally. In many applications, certain errors are far more costly than others, and the need arises for non-parametric classification techniques that can be trained to optimize task-specific cost functions. This paper reviews the Linear Machine Decision Tree (LMDT) algorithm for inducing multivariate decision trees, and shows how LMDT can be altered to induce decision trees that minimize arbitrary misclassification cost functions (MCFs). Demonstrations of pixel classification in outdoor scenes show how MCFs can optimize the performance of embedded classifiers within the context of larger image understand ing systems.

Keywords: Decision Trees, Non-Parametric Classification, Pattern Recognition, Object Recognition, Computer Vision, Machine Learning.

1 Introduction