# Usage of LDA with more than two classes

I'm reading about the Linear Discriminant Analysis by Fisher and I have a couple of questions about its usage.

1. If you have k>2 classes in a two-dimensional space you find k−1 vectors that you need to use to project the sample data. Is it possible that one sample is closer to different means along different vectors?

2. Suppose you have, for example, 3 classes in a 3-dimensional space. You get two vectors, but now you need planes to be able to project your samples. Do you create those by combining the vectors obtained by LDA?

I will denote by $$K$$ the number of classes and by $$p$$ the dimension of the feature space.

I assume you use a procedure that can be rephrased as (it is the case of LDA, see conclusion):

1- For all $$k=1,\dots,K$$, estimate $$\hat{P}_k:\mathbb{R}^p\rightarrow \mathbb{R}$$ from a learning set.

2- For all $$k=1,\dots,K$$ set $$V_k=\{x\in \mathbb{R}^p:\; \forall j=1,\dots,K\;\; \widehat{\mathcal{L}}_{kj}(x)=\log(\hat{P}_k(x)/\hat{P}_{j}(x))\geq 0 \}$$

The almost non trivial point here is that $$(V_k)_{k=1,\dots,K}$$ forms a partition of $$\mathbb{R}^p$$, up to a set null measure (under suitable regularity condition satisfyed in the case of LDA). (i.e. $$\bigcup_{k=1,\dots,K} V_k=\mathbb{R}^p$$ and $$mes (V_i\cap V_j) =0$$ for any $$i\neq j$$). In other words: it is not possible (expept in pathologic cases such as $$\hat{P}_i=\hat{P}_j$$) that for two different classes $$i,j$$, $$x\in V_i$$, and $$x\in V_j$$, i.e. $$x$$ is classified in class $$i$$ and in class $$j$$.

Proof: The result is true because you can rewrite: $$V_k=\{x\in \mathbb{R}^p:\; \forall j=1,\dots,K\;\; \log(\hat{P}_k(x))\geq \log (\hat{P}_{j}(x)) \}$$ $$V_k=\{x\in \mathbb{R}^p:\; k=arg\max_{j=1,\dots,K}\;\; \log(\hat{P}_j(x))\}$$

Hence $$V_i\cap V_i \subset \{x:\;\hat{P}_j(x)=\hat{P}_i(x)\}$$ which should be of null measure

The intuition behind this result is that you certainly have two much separating functions ($$K(K-1)/2$$as you noticed in your question) but these are build from $$K$$ densities only...

Conclusion

Usual "LDA" belongs to that type of algorithm with $$\forall k=1,\dots,K$$, $$\hat{P}_k$$ gaussian with mean $$\hat{\mu}_k$$ and covariance $$\hat{C}$$ estimated in step 1-.

As a conclusion, the answer is no (there can't be problem such as the one you state) whatever the number of classes $$k$$ and the feature space dimension $$p$$.

A problem that can occur with dimensionality reduction: If you are in a high dimensional space it might be a good idea to reduce the dimension of your problem. If you choose "one subspace" to work with then there is no problem. However, if you choose to reduce the dimension per pairs of class (which is often natural, there is one good space to work with per pairs) this will result in a "separation function" $$\widehat{\mathcal{L}}_{kj}(x)$$ that cannot be decomposed into $$f_k-f_j$$...

I'm not sure I understand what you mean by projecting your sample data, but:

The result per set of 2 classes of LDA is always a linear form in the coordinates of your space (e.g. 3x_1-x_2+2). Hence it also defines a hyperplane (a line in 2D, a plane in 3D,...), where this linear form is zero, and the 'discriminating' between these two classes works by looking at the sign of the linear form.

The coefficients of this linear form always define a vector that is orthogonal to this hyperplane, and is defined up to a factor (in my example above, this vector is (3,-1), but could also be (-1, 1/3)). This should answer your second question.

Your first question is very confusing, but: for every pair of classes (given that they don't completely overlap), you should be able to decide which of two gets the better vote (i.e. which of these 2 classes your LDA would appoint this sample to). Due to the nature of the hyperplanes, it is impossible to have the choices for three classes so that A > B, B > C and C > A if that's what you are asking. Of course, it is possible that a sample is exactly on the discriminating hyperplane for two classes (or even on the intersection of two discriminating hyperplanes): for these points, the LDA has no way of deciding between the classes involved (the sample is 'just as close to either mean' then).

• one question: suppose you have 3 clusters and you find 2 vectors using LDA. What do you do to classify? Do you project over both vectors? I can only understand LDA with one vector, where you project the samples onto it and see which cluster center is closest. Thanks
– Bob
Jun 8 '11 at 9:49

To add to Robin's reply, you probably don't want to use LDAs. SVMs which serve a similar role as LDAs generally have the same problem. There exists a variant of the SVM called the multiclass SVM which provides a way to do this.