An iterative mixed integer programming method for classification accuracy maximizing discriminant analysis
Linear discriminant functions which maximize the number of correctly classified observations in a training sample can be generated by a mixed integer programming (MIP) discriminant analysis model in which a binary variable is associated with each observation, but because of the computational requirements this model can only be applied to relatively small problems. In this paper, an iterative MIP method is developed to allow classification accuracy maximizing discriminant functions to be generated for problems with many more observations than can be considered by the standard MIP formulation. Using minimization of the sum of deviations as the objective, a mathematical programming discriminant analysis model is first used to generate a discriminant function for the complete set of observations. A neighborhood of observations about this function is then defined and a MIP model is used to generate a discriminant function that maximizes classification accuracy within this neighborhood. The process of defining a neighborhood about the most recently generated discriminant function and solving a neighborhood MIP model is repeated until there is no improvement in the total number of observations classified correctly. This new iterative MIP method is applied to a two-group problem involving 690 observations. In many classification problems, e.g. credit risk assessment and medical diagnosis, classification decisions must be based on limited information. In problems of this type, classification models may be used to assign observations of unknown class to specified groups based on the values of a set of variables associated with each observation. These models can be developed by discriminant analysis techniques in which a training sample of observations of known class is used to generate a function that separates these observations into the specified classes optimally in terms of a technique dependent separation criterion. Classification accuracy in the training sample can be used as the separation criterion by using a mixed integer programming (MIP) model in which a binary variable is associated with each observation. Although this MIP approach can provide a benchmark for assessing the training sample performance of other linear classification models, the computational requirements are prohibitive unless the number of observations is relatively small. An iterative MIP method is developed to generate classification accuracy maximizing discriminant functions for problems with more observations than can be considered by the standard MIP approach. This iterative MIP method is applied to a two-group classification problem involving 690 observations. The performance of this new method is shown to compare favorably with other methods for generating classification models.
discriminant analysis mathematical programming variable selection