USING A NONLINEAR DISCRIMINANT FUNCTION

FOR SOLVING DISCRIMINANT ANALYSIS PROBLEMS

John Maloney and Yi–Hsin Liu

University of Nebraska, Omaha

Abstract. To solve a discriminant analysis problem, linear programming has been useful for finding a linear discriminant function. In this paper we present a mathematical programming approach to find a nonlinear discriminant function. It is believed that a nonlinear discriminant function can be more useful than a linear one.

1. Introduction. A discriminant analysis problem seeks a discriminant function f(x) which is used to separate the given groups of vector–valued data G_{1}, G_{2}, …, G_{m} and provides an allocation rule for placing future unclassified data into one of the groups.

In this paper we construct a nonlinear discriminant function using a linear program. In fact, we construct a general polynomial, of degree n, in the vector x to be used as a discriminant function. Clearly, a nonlinear discriminant function is more effective than a linear one, since a linear function can be treated as a special case (n = 1) in the mentioned polynomial.

In this paper, we assume that a subjective ranking (order relation) has been imposed on the groups G_{1}, G_{2}, …, G_{m}. That is, for any two distinct groups of data G_{i} and G_{j} either G_{i} is preferred to G_{j} or G_{j} is preferred to G_{i}. Without loss of generality, we may assume that G_{i} is preferred to G_{j} whenever i > j. This order relation is denoted by writing G_{j} ≺ G_{i} if i > j. Thus, we are given

G_{1} ≺ G_{2} ≺ ⋯ ≺ G_{m}.

This assumption arises in many problems and it is possible to use, in some cases, artificial intelligence techniques to determine the subjective rankings discussed above in [5]. This will not be discussed in this paper, rather we will assume that the rankings have been given.

The problem to be considered is stated as follows.

\underline{Problem 1}. Given m groups of vector–valued data (that is values in E^{n}) such that (1) G_{1} ≺ G_{2} ≺ ⋯ ≺ G_{m}

(2) G_{i} = {x_{j}^{i} ∈ E^{n} : j = 1, 2, …, l_{i}} where i = 1, 2, …, m, find a discriminant function f(x), and the appropriate intervals I_{i} = (L_{i}, U_{i}], such that

i. I_{i} ∩ I_{k} = ∅, ∀ 1 ≤ i, k ≤ n, i ≠ k. ii. f(x_{j}^{i}) ∈ I_{i}, ∀ j = 1, 2, …, l_{i} and ∀ i = 1, 2, …, m. iii. L_{1} < U_{1} < L_{2} < U_{2} < ⋯ < L_{m} < U_{m}

\underline{Definition 2}. The groups G_{1}, G_{2}, …, G_{m} are said to be separable if there exists a function f(x) such that f(x_{j}^{i}) ∈ I_{i}, ∀ j = 1, 2, …, l_{i} and ∀ i = 1, 2, …, m provided that (i), (ii), and (iii) above hold. Otherwise the groups are said to be nonseparable.

2. Model and Discussion. In the following f(x), x = (x_{1}, x_{2}, …, x_{n}) is restricted to the following form

f(x) = ∑_{j=0}^{n} a_{i_{1}i_{2}···i_{n}}x_{1}^{i_{1}}x_{2}^{i_{2}} ⋯ x_{n}^{i_{n}} where j = i_{1} + i_{2} + ⋯ i_{n}.

Determining the degree of the polynomial can be difficult, since there are no general rules for doing this. It depends on the number of groups considered in the problem and the number of data (observations) in each class. However, trial and error can provide good information in determining n, the order of the discriminant polynomial (function). The quantities \overline{x}_{i} in the objective function below are defined by

\overline{x}_{i} = \frac{∑_{j=1}^{l_{i}} x_{j}^{i}}{l_{i}} .

We may think of the \overline{x}_{i}’s as being the center of mass of l_{i} unit masses located at x_{j}^{i}. This then becomes the center of mass of the group G_{i}. For this reason we shall refer to the points \overline{x}_{i} as centroids.

The model used is

\underline{Q. P. 3}. Maximize

∑_{i=1}^{m} ∑_{j=i+1}^{m} |f(\overline{x}_{i}) − f(\overline{x}_{j})| + 2K − ∑_{i=1}^{m}(U_{i} − L_{i})

subject to the constraints

\begin{matrix}i. − K ≤ L_{i} ≤ f(x_{j}^{i}) ≤ U_{i} ≤ K i = 1, 2, …, m, j = 1, 2, …, l_{i} . \\ ii. 2K − ∑_{i=1}^{m}(U_{i} − L_{i}) ≥ 0 . \end{matrix}

We are finding the coefficient of the discriminant function, a_{i_{1}i_{2}···i_{n}}, that will give maximum separation to the values f(\overline{x}_{i}), and thus, lead to the most widely separated set of disjoint intervals I_{j}. We also obtain the intervals [L_{i}, U_{i}) to be of minimum length in the sense that f(x_{j}^{i}) = L_{i} for some j and f(x_{j}^{i}) = U_{i} for some (different) value of j.

The first term in the objective function is maximized by giving maximum separation to the centroids. The second term in the objective function is maximized by making the intervals [L_{i}, U_{i}] as small as possible subject to the constraint (i). One can, later, properly adjust the interval lengths to handle the future classification of new data.

Thus maximizing our objective function gives us the two properties that we sought above. K is a properly selected constant that guarantees a bounded solution for the intervals. In the example that follows a value of 100 was used, a larger or smaller value might well be suitable for a different problem.

The advantage of this form of the problem is that it determines what might be called a natural order for the intervals [L_{i}, U_{i}] and removes any dependence upon the order relation prescribed for the G_{i} in the original problem.

3. Example. In this example the discriminant function is a third order polynomial in the two coordinates x and y that has the form

f(x) = a_{30}x^{3} + a_{21}x^{2}y + a_{12}xy^{2} + a_{03}y^{3} + a_{20}x^{2} + a_{11}xy + a_{02}y^{2} + a_{10}x + a_{01}y + a_{00}.

The data set used in this example is given below. The model was solved on Gino [5].

\underline{Data Set 4}. The data is i. G_{1} = \{(1, 3), (2, 3), (2, 4), (3, 3), (4, 2)\} \overline{x}_{1} = (12/5, 3) . ii. G_{2} = \{(3, 4), (5, 4), (4, 5), (5, 5)\} \overline{x}_{2} = (17/4, 9/2) . iii. G_{3} = \{(2, 1), (3, 1), (2, 2), (3, 2)\} \overline{x}_{3} = (5/2, 3/2) .

The model results are presented in the table below.

\begin{matrix}interval & item \\ [−11.012358, −9.749569] & [L_{1}, U_{1}] \\ [−100.0, −69.838026] & [L_{2}, U_{2}] \\ [61.543902, 100.0] & [L_{3}, U_{3}] \end{matrix}

Table 4 Separable Data

The constants for the solution polynomial are

\begin{matrix}constant & value \\ a_{30} & −4.159692 \\ a_{21} & −26.017895 \\ a_{12} & 30.588933 \\ a_{03} & 17.776081 \\ a_{20} & −66.177253 \\ a_{11} & −29.645071 \\ a_{02} & −71.670812 \\ a_{10} & 274.182681 \\ a_{01} & 145.165613 \\ a_{00} & −252.679563 \end{matrix}

Table 5 Solution Function Constants

In the following figure we show the data.

Figure 1 87

\underline{References}

1. T. M. Cavalier, J. P. Ignizio, and A. L. Soyster, “Discriminant Analysis via Mathematical Programming: Certain Problems and Their Causes,” Computer and Operations Research, 16 (1989), 353–362.

2. N. Freed and F. Glover, “A Linear Programming Approach to the Discriminant Problem,” Decision Sciences, 12 (1981), 67–84.

3. N. Freed and F. Glover, “Simple But Powerful Goal Programming Models for Discriminant Problems,” European Journal of Operational Research, (1989), 353–362.

4. R. A. Johnson and D. W. Wichen, Applied Multivariate Statistical Analysis, Prentice Hall, Englewood Cliffs, N.J., 1988.

5. J. Liebman, L. Lasdon, L. Schrage, and A. Waren, GINO, The Scientific Press, San Francisco, California, 1986.

6. Y–H. Liu and Z. Chen, “Rule Base Assisted Consistence Checking for Decision Making,” Proceedings of the Twentieth Annual Model and Simulation Conference, May 1989.

7. Y–H. Liu and J. Maloney, “Discriminant Analysis Using a Bicriteria Linear Program,” Missouri Journal of Mathematical Sciences, 4 (1992), 61–69.

8. J. Maloney and Y–H. Liu, “A Quadratic Programming Approach for Solving Discriminant Analysis Problems,” Missouri Journal of Mathematical Sciences, 4 (1992), 139-144.

9. P. A. Rubin, “Evaluating the Maximum Distance Formulation of the Discriminant Problem,” European Journal of Operational Research, 41 (1989), 240–248.