Improved Linear Programming Models for Discriminant Analysis*

Discriminant analysis is an important tool for practical problem solving. Classical statistical applications have been joined recently by applications in the fields of management science and artificial intelligence. In a departure from the methodology of statistics, a series of proposals have appeared for capturing the goals of discriminant analysis in a collection of linear programming formulations. The evolution of these formulations has brought advances that have removed a number of initial shortcomings and deepened our understanding of how these models differ in essential ways from other familiar classes of LP formulations. We will demonstrate, however, that the full power of the LP discriminant analysis models has not been achieved, due to a previously undetected distortion that inhibits the quality of solutions generated. The purpose of this paper is to show how to eliminate this distortion and thereby increase the scope and flexibility of these models. We additionally show how these outcomes open the door to special model manipulations and simplifications, including the use of a successive goal method for establishing a series of conditional objectives to achieve improved discrimination.     

SOME DIFFICULTIES AND IMPROVEMENTS IN APPLYING LINEAR PROGRAMMING FORMULATIONS TO THE DISCRIMINANT PROBLEM

In this paper, we discuss some disturbing features of two linear programming (LP) approaches to the discriminant problem. Specifically, we show that both approaches are sensitive to the choice of origin for the data although, intuitively, placement of origin should have no effect on the method of assigning cases to groups. In addition, we show that these LP approaches may lead to discriminant functions which assign all cases to the same group. We show that the usual statistical approach to this problem does not share these difficulties, and we make recommendations for implementing these LP approaches which help to alleviate the difficulties.     

A NEW CLASS OF MODELS FOR THE DISCRIMINANT PROBLEM

Discriminant analysis is relevant to business decision making in a variety of contexts, such as when one decides to make or buy a specified component, fund a venture project, or hire a particular person. Potential applications in artificial intelligence, particularly in the area of pattern recognition, have further underscored the importance of the field. A recent innovation in discriminant analysis is provided by special linear programming (LP) models, which offer attractive alternatives to classical statistical approaches. The scope of application in which discriminant analysis can be advantageously employed is broadened by the flexibility to tailor parameters in the LP approaches to reflect diverse goals and by the power to explore the sensitivity of these parameters. In spite of the promise of the LP formulations, however, limitations to their effectiveness have been uncovered in certain settings. A recent advance involving a normalization construct removes some of the limitations but entails solving the LP model twice (to allow for different signs of a normalization constant) and does not yield equivalent solutions for different rotations of the problem data. This paper introduces a new model and a new class of normalizations that remedy both remaining limitations, making it possible to take advantage of the modeling capabilities of the LP formulations without the attendant shortcomings encountered by earlier investigations. Our development shows by empirical testing and illustrative analysis that the quality of solutions from LP discriminant approaches is more favorable (relative to the classical model) than previously supposed.     

Characterization of Unacceptable Solutions in LP Discriminant Analysis*

Many linear programming models have been proposed for performing discriminant analysis. Partial characterizations for unacceptable solutions have been presented and new models proposed to circumvent these problems. In this paper those conditions leading to unacceptable solutions for all two-group models are characterized.     

Notes and Communications RESOLVING CERTAIN DIFFICULTIES AND IMPROVING THE CLASSIFICATION POWER OF LP DISCRIMINANT ANALYSIS FORMULATIONS

In certain settings, difficulties arise that limit the effectiveness of LP formulations for the discriminant problem. Explanations and possible remedies have been offered, but these have had only limited success. We provide a simple way to overcome these problems based on an appropriate use and interpretation of normalizations. In addition, we demonstrate a normalization that is invariant under all translations of the problem data, providing a stability property not shared by previous approaches. Finally, we discuss the possibility of using more general models to improve discrimination.     

Mathematical Programming Formulations for the Discriminant Problem: An Old Dog Does New Tricks*

In recent years, much research has been done on the application of mathematical programming (MP) techniques to the discriminant problem. While promising results have been obtained, many of these techniques are plagued by a number of problems associated with the model formulation including unbounded, improper, and unacceptable solutions as well as solution instability under linear transformation of the data. In attempting to solve these problems, numerous formulations have been proposec involving additional variables and/or normalization constraints. While effective, these models can also become quite complex. In this paper we demonstrate that a simple, well-known special case of Hand's [13] original formulation provides an implicit normalization which avoids the problems for which various complicated remedies have been devised. While other researchers have made use of this formulation, its properties have not previously been fully recognized.     

ESTIMATION OF MISCLASSIFICATION PROBABILITIES IN THE LINEAR PROGRAMMING APPROACHES TO THE TWO-GROUP DISCRIMINANT PROBLEM

Expressions for misclassification probabilities are derived under a contaminated multivariate normal model for the linear-programming approaches to the two-group discriminant problem.     

Solving the Classification Problem in Discriminant Analysis Via Linear and Nonlinear Programming Methods*

This paper demonstrates the feasibility of applying nonlinear programming methods to solve the classification problem in discriminant analysis. The application represents a useful extension of previously proposed linear programming-based solutions for discriminant analysis. The analysis of data obtained by conducting a Monte Carlo simulation experiment shows that these new procedures are promising. Future research that should promote application of the proposed methods for solving classification problems in a business decision-making environment is discussed.     

Unacceptable Solutions and the Hybrid Discriminant Model

A new family of linear programming (LP) discriminant models, the hybrid discriminant model, was recently presented with claims that it avoids all the problems of its predecessor LP models. However, this note shows that it does not avoid unacceptable solutions.     

Minimizing Misclassifications in Linear Discriminant Analysis*

A procedure is developed for determining two-group linear discriminant classifiers that misclassify the fewest number of observations in the training sample. An experimental study confirms the value of this approach.     

Necessary and Sufficient Conditions of Unacceptable Solutions in LP Discriminant Analysis*

Characterization of unacceptable solutions for linear programming (LP) discriminant models have been discussed in the literature and the results presented so far are not satisfactory. This paper establishes necessary and sufficient conditions of unacceptable solutions for a number of LP models, addresses the practical implications of these conditions, and discusses the relationship between unacceptable solutions and multiple solutions.     

A Note on Discriminant Analysis Using LAD

Using a regression approach to discriminant analysis is often incorrect because it forces the use of a binary dependent variable which violates virtually any distributional assumption for a linear model. However, assuming a Laplace distribution in an LP framework leads to a theoretical foundation for MSD discriminant analysis.     

Applications and Implementation

We propose an alternative solution to the discriminant problem, one that requires little more than a minimum familiarity with linear programming. The approach shows promise for eliminating the complexities of conventional statistical approaches without sacrificing the essential power of existing methods.     

A Variable Selection Criterion in the Linear Programming Approaches to Discriminant Analysis*

There are numerous variable selection rules in classical discriminant analysis. These rules enable a researcher to distinguish significant variables from nonsignificant ones and thus provide a parsimonious classification model based solely on significant variables. Prominent among such rules are the forward and backward stepwise variable selection criteria employed in statistical software packages such as Statistical Package for the Social Sciences and BMDP Statistical Software. No such criterion currently exists for linear programming (LP) approaches to discriminant analysis. In this paper, a criterion is developed to distinguish significant from nonsignificant variables for use in LP models. This criterion is based on the “jackknife” methodology. Examples are presented to illustrate implementation of the proposed criterion.     

FOUR APPROACHES TO THE CLASSIFICATION PROBLEM IN DISCRIMINANT ANALYSIS: AN EXPERIMENTAL STUDY*

Four discriminant models were compared in a simulation study: Fisher's linear discriminant function [14], Smith's quadratic discriminant function [34], the logistic discriminant model, and a model based on linear programming [17]. The study was conducted to estimate expected rates of misclassification for these four procedures when observations were sampled from a variety of normal and nonnormal distributions. In contrast to previous research, data were taken from four types of Kurtotic population distributions. The results indicate the four discriminant procedures are robust toward data from many types of distributions. The misclassification rates for both the logistic discriminant model and the formulation based on linear programming consistently decreased as the kurtosis in the data increased. The decreases, however, were of small magnitude. None of these procedures yielded statistically significant lower rates of misclassification under nonnormality. The quadratic discriminant function produced significantly lower error rates when the variances across groups were heterogeneous.     

Separation Failure in Linear Programming Discriminant Models

Linear programming discriminant analysis (LPDA) models are designed around a variety of objective functions, each representing a different measure of separation of the training samples by the resulting discriminant function. A separation failure is defined to be the selection of an “optimal” discriminant function which incompletely separates a pair of completely separable training samples. Occurrence of a separation failure suggests that the chosen discriminant function may have an unnecessarily low classification accuracy on the actual populations involved. In this paper, a number of the LPDA models proposed for the two-group case are examined to learn which are subject to separation failure. It appears that separation failure in any model can be avoided by applying the model twice, reversing group designations.     

Decision Power and Solutions of LP Discriminant Models: Rejoinder

A major problem of LP discriminant analysis is the validity of the solution. This note shows that to comprehend the effectiveness of the solution, conditions for unacceptable solutions need to be tightly characterized.     

ON USING LINEAR PROGRAMMING IN DISCRIMINANT PROBLEMS

This commentary evaluates the usefulness of the Freed and Glover [6] linear programming approach to the discriminant problem, relates linear programming to other parametric and nonparametric approaches, and evaluates the linear programming approach.     

A Comparison of Linear Programming and Parametric Approaches to the Two-Group Discriminant Problem*

Recent simulation-based studies of linear programming models for discriminant analysis have used the Fisher linear discriminant function as the benchmark for parametric methods. This article reports experimental evidence which suggests that, while some linear programming models may match or even exceed the Fisher approach in classification accuracy, none of the fifteen models tested is as accurate on normally distributed data as the Smith quadratic discriminant function. At the minimum, further testing is warranted with an emphasis on data sets that arise from significantly non-Gaussian populations.     

An Efficient Optimal Solution Algorithm for the Classification Problem

A new LP-based algorithm is developed to determine the optimal solution to the two-group classification problem. The procedure is efficient when compared to current research in a simulation study.