DISCRIMINANT ANALYSIS USING A BICRITERIA

LINEAR PROGRAM

Yi–Hsin Liu and John Maloney

University of Nebraska at Omaha

Abstract. In the past decade, there has been some interest shown in the use of linear programs to solve discriminant analysis problems. In this paper we present and clarify an alternative to the statistical approach for discriminating between two (or more) groups of vector–valued data in which an order relation is given.

By the nature of this problem, a bicriteria linear program can be used instead of a statistical approach and hence no statistical assumptions need to be imposed on the problem.

1. Introduction. Classical discriminant analysis is a multivariate statistical technique concerned with

(1) separating distinct sets of objectives and

(2) allocating new objectives to previously defined groups [4]. In the past decade, this problem has been studied using linear programs [1, 2, 3]. However, in many cases, a “complete separation” using a linear discriminant function is impossible. Therefore, by the nature of the problem a bicriteria linear programming approach is preferred.

The bicriteria linear program contains the following two objective criteria:

(1) maximize the total separation and

(2) minimize the total misclassification Of course, (2) above can be omitted if it is known that the groups are separable. This

will be discussed further in the later sections.

A linear discriminant analysis problem seeks a vector c which is used to construct a linear discriminant function f(x) = cx. This linear discriminant function is then 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 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 [5] and it is possible to use, in some cases, artificial intelligence techniques to determine the subjective rankings discussed above. This will not be discussed in this paper, rather we will assume that the rankings have been given.

We now formally state the problem.

\underline{Problem 1.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 vector c (and hence a linear discriminant function f(x) = cx), 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} i = 1, 2, …, m. iii. L_{1} < U_{1} ≤ L_{2} < U_{2} ≤ ⋯ ≤ L_{m} < U_{m}

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

2. Models and Discussion. First, we solve a simple basic mode, L. P. 2.1, to follow, which assumes that the groups are separable. We will then generalize the basic model to attack the case where the groups are not separable.

\underline{L. P. 2.1}. Maximize

(1)  ∑_{c=1}^{m} α_{ii} + ∑_{i=1}^{m−1} α_{i+1,i}

subject to the constraints

(2)  L_{i} ≤ cx_{j}^{i} ≤ U_{i} i = 1, 2, …, m, j = 1, 2, …, l_{i}
(3)  U_{i} − L_{i} = α_{ii} i = 1, 2, …, m
(4)  L_{i+1} − U_{i} =α_{i+1,i} i = 1, 2, …, m − 1
(5)  0 ≤ α_{ii}, α_{i+1,i} ≤ K

L. P. 2.1 finds the vector c and the boundaries of the intervals U_{i}, L_{i} while the x_{j}^{i}’s are given data and K is chosen so as to bound the unknown quantites to be found.

The assumption of separability guarantees that f(x_{j}^{i}) ∈ (L_{i}, U_{i}] and the remaining constraints guarantee that

L_{1} < U_{1} ≤ L_{2} < U_{2} ≤ ⋯ ≤ L_{m} < U_{m} .

The last constraint in problem 2.1 guarantees that the solution will be bounded. Without it the model is unbounded as can be seen from (2) or from the dual linear program of L. P. 2.1. In fact, the upper bound K can be chosen to be any real number, since by (2) one can see that in the discriminant function f(x) = cx, that c is a vector of relative weights. Or, if one considers the geometry, it will be the normal of the hyperplane defined by f(x) = cx = z^{∗}, for some real number z^{∗}.

Let c^{∗} and (L_{i}^{∗}, U_{i}^{∗}] be an optimal solution found from L. P. 2.1. Then the allocation rule for a new vector \overline{x} states that if f(\overline{x}) = c^{∗}\overline{x} ∈ J_{i} then \overline{x} ∈ G_{i}, where

J_{i} = (\frac{L_{i}^{∗} + U_{i−1}^{∗}}{2} , \frac{U_{i}^{∗} + L_{i+1}^{∗}}{2} ] .

Then J_{i} ∩ J_{j} = ∅ if i ≠ j ∀ 1 ≤ i, j ≤ m.

Next, we consider the nonseparable case. This case is a generalization of the separable case. In the nonseparable case, we assume that

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

and

L_{1} < U_{1} ≤ L_{2} < U_{2} ≤ ⋯ ≤ L_{m} < U_{m} .

To find f(x) = cx and L_{i},U_{i} for all i, however, we note that the condition

f(x_{j}^{i}) = cx_{j}^{i} ∈ I_{i}

may very well be false for some of the x_{j}^{i} ∈ G_{i}. Thus for each x_{j}^{i} ∈ G_{i}, one of the following three cases must hold

a. L_{i} ≤ cx_{j}^{i} ≤ U_{i} b. cx_{j}^{i} ≤ L_{i} c. cx_{j}^{i} ≥ U_{i}

The above three cases can be combined into

(6)  L_{i} − β_{j}^{i} ≤ cx_{j}^{i} ≤ U_{i} + γ_{j}^{i}

where β_{j}^{i} and γ_{j}^{i} both are nonnegative quantities and can be considered as the “distance” away from the interval, or the “error” due to misclassification. When the groups are separable we have that β_{j}^{i} = γ_{j}^{i} = 0 ∀ i, j. Based on this, we develop the following bicriteria linear program

\underline{B. C. L. P. 2.2}. Maximize

(7)  ∑_{i=1}^{m} α_{ii} + ∑_{i=1}^{m−1} α_{i+1,i}

and minimize

(8)  ∑_{i=1}^{m} ∑_{j=1}^{l_{i}} β_{j}^{i} + ∑_{i=1}^{m} ∑_{j=1}^{l_{i}} γ_{j}^{i}

subject to the constraints (2), (3), (4), (5), of L. P. 2.1 and

(9)  0 ≤ β_{j}^{i} ≤ K, 0 ≤ γ_{j}^{i} ≤ K

In the above (7) maximizes the total interval length as in (1), while (8) minimizes the total misclassification. This last problem simultaneously optimizes both goals of the discriminant analysis problem.

To solve the bicriteria linear program one can use the weighted linear program to obtain an optimal solution for B. C. L. P. 2.2. By the scalarization theorem of the multicritieria linear program [6] and the nature of the problem, one can then obtain the following weighted linear program with equal weights for both objectives as in the problem.

\underline{L. P. 2.3}. Maximize

(10)  ∑_{i=1}^{m} α_{ii} + ∑_{i=1}^{m−1} α_{i+1,i} − (∑_{i=1}^{m} ∑_{j=1}^{l_{i}} β_{j}^{i} + ∑_{i=1}^{m} ∑_{j=1}^{l_{i}} γ_{j}^{i})

subject to the constraints (2), (3), (4), (5), (9).

An optimal solution of L. P. 2.3 c^{∗}, β_{j}^{i^{∗}}, γ_{j}^{i^{∗}}, U_{i}^{∗}, L_{i}^{∗} then can be used to define a linear discriminant function f(x) = c^{∗}x and the allocation rule then would be the same as the separable case. When the optimal solution has β_{j}^{i} = γ_{j}^{i} = 0 for all i, j, such that 1 ≤ j ≤ l_{i} and 1 ≤ i ≤ m, then we have the separable case.

3. Conclusions and Examples. L. P. 2.3, in fact, is a general formulation of L. P. 2.1. In general, among groups G_{i}, i = 1, 2, …, m with G_{1} ≺ G_{2} ≺ ⋯ ≺ G_{m}, it is very difficult to detect whether the groups are separable or nonseparable. So for any given problem one should always apply problem 2.3 to solve the discriminant analysis problem.

An optimal solution of L. P. 2.3 then shows whether the groups are separable or nonseparable and determines a linear discriminant function. Also one can then obtain an allocation rule for the future data allocation.

\underline{Example 3.1}. Given the data shown in table 1, find a discriminant function.

G_{1}  G_{2}  G_{3}
x_{1}^{1} = (2, 1)  x_{1}^{2} = (2, 3)  x_{1}^{3} = (4, 8)
x_{2}^{1} = (3, 1)  x_{2}^{2} = (3, 4)  x_{2}^{3} = (4, 9)
x_{3}^{1} = (3, 2)  x_{3}^{2} = (3, 5)  x_{3}^{3} = (5, 9)
x_{4}^{1} = (5, 3)  x_{4}^{2} = (6, 6)  x_{4}^{3} = (5, 10)
x_{5}^{1} = (6, 2)  x_{5}^{2} = (7, 8)  x_{5}^{3} = (7, 10)

x_{6}^{2} = (8, 7) x_{7}^{2} = (1, 4) Table 1

Let the order relation be given by G_{1} ≺ G_{2} ≺ G_{3}. Applying L. P. 2.3 and (6) we obtain the discriminant function f(x) = −33.3x_{1} + 53.3x_{2} and the intervals J_{1} = (−∞, 50], J_{2} = (50, 243.33] and J_{3} = (243.33, ∞]. The allocation rule for new data x = (x_{1}, x_{2}) will be

i. x ∈ G_{1} if −33.3x_{1} + 53.3x_{2} ∈ J_{1}. ii. x ∈ G_{2} if −33.3x_{1} + 53.3x_{2} ∈ J_{2}. iii. x ∈ G_{3} if −33.3x_{1} + 53.3x_{2} ∈ J_{3}.

Figure 1 67

\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. 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.

6. J. Philip, “Algorithm for the Vector Maximization Problem,” Mathematical Programming, 2 (1972), 207–229.

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