Linear discriminant analysis

From Wikipedia, the free encyclopedia

You have new messages (last change).

Linear discriminant analysis (LDA) and the related Fisher's linear discriminant are used in statistics to find the linear combination of features which best separate two or more classes of object or event. The resulting combinations may be used as a linear classifier, or more commonly in dimensionality reduction before later classification.

LDA is closely related to ANOVA (analysis of variance) and regression analysis, which also attempt to express one dependent variable as a linear combination of other features or measurements. In the other two methods however, the dependent variable is a numerical quantity, while for LDA it is a categorical variable (i.e. the class label).

LDA is also closely related to principal component analysis (PCA) and factor analysis in that both look for linear combinations of variables which best explain the data. LDA explicitly attempts to model the difference between the classes of data. PCA on the other hand does not take into account any difference in class, and factor analysis builds the feature combinations based on differences rather than similarities. Discriminant analysis is also different from factor analysis in that it is not an interdependence technique : a distinction between independent variables and dependent variables (also called criterion variables) must be made.

LDA works when the measurements made on each observation are continuous quantities. When dealing with categorical variables, the equivalent technique is Discriminant Correspondence Analysis (see References).

Contents

[edit] LDA for two classes

Consider a set of observations x (also called features, attributes, variables or measurements) for each sample of an object or event with known class y. This set of samples is called the training set. The classification problem is then to find a good predictor for the class y of any sample of the same distribution (not necessarily from the training set) given only an observation x.

LDA approaches the problem by assuming that the probability density functions p(\vec x|y=1) and p(\vec x|y=0) are both normally distributed, with identical full-rank covariances Σy = 0 = Σy = 1 = Σ

It can be shown that the required probability p(y| \vec x) depends only on the dot product \vec w \cdot \vec x where

\vec w = \Sigma^{-1} (\vec \mu_1 - \vec \mu_0)

That is, the probability of an input x being in a class y is purely a function of this linear combination of the known observations.

A similar analysis that allows the covariances to be different is called quadratic discriminant analysis (QDA).

[edit] Fisher's linear discriminant

The terms Fisher's linear discriminant and LDA are often used interchangeably, although Fisher's original article The Use of Multiple Measures in Taxonomic Problems (1936) actually describes a slightly different discriminant, which does not make some of the assumptions of LDA such as normally distributed classes or equal class covariances.

Suppose two classes of observations have means \vec \mu_{y=0}, \vec \mu_{y=1} and covariances Σy = 0,Σy = 1. Then the linear combination of features \vec w \cdot \vec x will have means \vec w . \vec \mu_{y=i} and variances \vec w^T \Sigma_{y=i} \vec w for i = 0,1. Fisher defined the separation between these two distributions to be the ratio of the variance between the classes to the variance within the classes:

S=\frac{\sigma_{between}^2}{\sigma_{within}^2}= \frac{(\vec w \cdot \vec \mu_{y=1} - \vec w \cdot \vec \mu_{y=0})^2}{\vec w^T \Sigma_{y=1} \vec w + \vec w^T \Sigma_{y=0} \vec w} = \frac{(\vec w \cdot (\vec \mu_{y=1} - \vec \mu_{y=0}))^2}{\vec w^T (\Sigma_{y=0}+\Sigma_{y=1}) \vec w}

This measure is, in some sense, a measure of the signal-to-noise ratio for the class labelling. It can be shown that the maximum separation occurs when

\vec w = (\Sigma_{y=0}+\Sigma_{y=1})^{-1}(\vec \mu_{y=1} - \vec \mu_{y=0})

When the assumptions of LDA are satisfied, the above equation is equivalent to LDA.

[edit] Multiclass LDA

Suppose C classes have means \vec \mu_{i} and covariance matrices Σi, with i = 1, \dots , C. The decision boundaries of these C classes if given by the quadratic terms (\vec x- \vec \mu_i)^T \Sigma_i^{-1} ( \vec x- \vec \mu_i) + ln |\Sigma_i| = (\vec x- \vec \mu_j)^T \Sigma_j^{-1} ( \vec x- \vec \mu_j) + ln |\Sigma_j|.

When the class distributions share the same covariance matrix, \Sigma_i = \Sigma_j, \forall i \neq j, these equations result in linear boundaries. This led this extension of the work pioneered by Fisher (which was originally only defined for the 2 class problem) to be known as Linear Discriminant Analysis (LDA).

Under the assumption of equal covariance matrices (also known as homoscedastic), LDA provides those C-1 features where the Bayes error is minimized. This operation can be shown to reduce to the following eigenvalue decomposition problem:

S_B V = \bar\Sigma V \Lambda ,

where SB is the between-class scatter matrix and \bar\Sigma is the average over all Σi.

LDA is not guarantee however to find the Bayes optimal solution for a set of less than C-1 features (even if the data is homoscedastic), and is very sensitive to the number of samples used.

A common way to improve the accuracy and robustness of this approach is to add a regularization term to the estimate of \bar\Sigma. In general this can be written as \bar\Sigma + \epsilon \mathbf{I}, where \mathbf{I} is the identity matrix and ε is small. This value can be found, for example, using cross-validation.

Other generalizations of LDA have been defined to address the more general problem of heteroscedastic distributions (i.e., where the data distributions are not homoscedastic). These are usually called Hetroscedastic LDA (see e.g. HLDA amnog others). Alternatively, one can use QDA.

[edit] Practical use

In practice, the class means and covariances are not known. They can, however, be estimated from the training set. Either the maximum likelihood estimate or the maximum a posteriori estimate may be used in place of the exact value in the above equations. Although the estimates of the covariance may be considered optimal in some sense, this does not mean that the resulting discriminant obtained by substituting these values is optimal in any sense, even if the assumption of normally distributed classes is correct.

Another complication in applying LDA and Fisher's discriminant to real data occurs when the number of observations of each sample exceeds the number of samples. In this case, the covariance estimates do not have full rank, and so cannot be inverted. There are a number of ways to deal with this. One is to use a pseudo inverse instead of the usual matrix inverse in the above formulae. Another, called regularised discriminant analysis, is to artificially increase the number of available samples by adding white noise to the existing samples. These new samples do not actually have to be calculated, since their effect on the class covariances can be expressed mathematically as

Cnew = C + σ2I

where I is the identity matrix, and σ is the amount of noise added, called in this context the regularisation parameter. The value of σ is usually chosen to give the best results on a cross-validation set. The new value of the covariance matrix is always invertible, and can be used in place of the original sample covariance in the above formulae.

Also, in many practical cases linear discriminants are not suitable. LDA and Fisher's discriminant can be extended for use in non-linear classification via the kernel trick. Here, the original observations are effectively mapped into a higher dimensional non-linear space. Linear classification in this non-linear space is then equivalent to non-linear classification in the original space. The most commonly used example of this is the kernel Fisher discriminant.

LDA can be generalized to multiple discriminant analysis, where c becomes a categorical variable with N possible states, instead of only two. Analogously, if the class-conditional densities p(\vec x|c=i) are normal with shared covariances, the sufficient statistic for P(c|\vec x) are the values of N projections, which are the subspace spanned by the N means, affine projected by the inverse covariance matrix. These projections can be found by solving a generalized eigenvalue problem, where the numerator is the covariance matrix formed by treating the means as the samples, and the denominator is the shared covariance matrix.

[edit] Applications

[edit] Face recognition

In computerised face recognition, each face is represented by a large number of pixel values. Linear discriminant analysis is primarily used here to reduce the number of features to a more manageable number before classification. Each of the new dimensions is a linear combination of pixel values, which form a template. The linear combinations obtained using Fisher's linear discriminant are called Fisher faces, while those obtained using the related principal component analysis are called eigenfaces.

[edit] Marketing

In marketing, discriminant analysis is often used to determine the factors which distinguish different types of customers and/or products on the basis of surveys or other forms of collected data. The use of discriminant analysis in marketing is usually described by the following steps:

  1. Formulate the problem and gather data - Identify the salient attributes consumers use to evaluate products in this category - Use quantitative marketing research techniques (such as surveys) to collect data from a sample of potential customers concerning their ratings of all the product attributes. The data collection stage is usually done by marketing research professionals. Survey questions ask the respondent to rate a product from one to five (or 1 to 7, or 1 to 10) on a range of attributes chosen by the researcher. Anywhere from five to twenty attributes are chosen. They could include things like: ease of use, weight, accuracy, durability, colourfulness, price, or size. The attributes chosen will vary depending on the product being studied. The same question is asked about all the products in the study. The data for multiple products is codified and input into a statistical program such as SPSS or SAS. (This step is the same as in Factor analysis).
  2. Estimate the Discriminant Function Coefficients and determine the statistical significance and validity - Choose the appropriate discriminant analysis method. The direct method involves estimating the discriminant function so that all the predictors are assessed simultaneously. The stepwise method enters the predictors sequentially. The two-group method should be used when the dependent variable has two categories or states. The multiple discriminant method is used when the dependent variable has three or more categorical states. Use Wilks’s Lambda to test for significance in SPSS or F stat in SAS. The most common method used to test validity is to split the sample into an estimation or analysis sample, and a validation or holdout sample. The estimation sample is used in constructing the discriminant function. The validation sample is used to construct a classification matrix which contains the number of correctly classified and incorrectly classified cases. The percentage of correctly classified cases is called the hit ratio.
  3. Plot the results on a two dimensional map, define the dimensions, and interpret the results. The statistical program (or a related module) will map the results. The map will plot each product (usually in two dimensional space). The distance of products to each other indicate either how different they are. The dimensions must be labelled by the researcher. This requires subjective judgement and is often very challenging. See perceptual mapping.

[edit] See also

positioning, marketing, product management, marketing research

[edit] See also

[edit] References

  • Fisher, R.A. The Use of Multiple Measurements in Taxonomic Problems. Annals of Eugenics, 7: 179-188 (1936) pdf file
  • Discriminant Analysis and Statistical Pattern Recognition. G.J. McLachlan. Wiley-Interscience; New Ed edition (August 4, 2004).
  • Pattern Classification (2nd ed.), R.O. Duda, P.E. Hart, D.H. Stork, Wiley Interscience, (2000). ISBN 0-471-05669-3
  • Friedman, J.H. Regularized Discriminant Analysis. Journal of the American Statistical Association, (1989)pdf file
  • Abdi, H. Discriminant Correspondence Analysis. In N.J. Salkind (Ed.): Encyclopedia of Measurement and Statistics. Thousand Oaks (CA): Sage, (2007)pdf file
  • Martinez, A.M., Kak, A.C. PCA versus LDA. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23, No. 2, pp. 228-233, 2001.
  • Mika, S. et al. Fisher Discriminant Analysis with Kernels. IEEE Conference on Neural Networks for Signal Processing IX, (1999) gzipped ps file
  • Nagendra Kumar Goel, Investigation of Silicon Auditory Models and Generalization of Linear Discriminant Analysis for improved Speech Recognition. Chapter 5 PhD Thesis, Johns Hopkins University, (1997) ps file

[edit] External links

Retrieved from "http://en.wikipedia.org../../../l/i/n/Linear_discriminant_analysis.html"