Linear discriminant analysis


Linear discriminant analysis

Linear discriminant analysis (LDA) and the related Fisher's linear discriminant are methods used in statistics, pattern recognition and machine learning to find a linear combination of features which characterize or separate two or more classes of objects or events. The resulting combination may be used as a linear classifier, or, more commonly, for 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.[1][2] 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). Logistic regression and probit regression are more similar to LDA, as they also explain a categorical variable. These other methods are preferable in applications where it is not reasonable to assume that the independent variables are normally distributed, which is a fundamental assumption of the LDA method.

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.[3] 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 independent variables for each observation are continuous quantities. When dealing with categorical independent variables, the equivalent technique is discriminant correspondence analysis.[4][5]

Contents

LDA for two classes

Consider a set of observations  \vec 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  \vec x [6]:338.

LDA approaches the problem by assuming that the conditional probability density functions p(\vec x|y=0) and p(\vec x|y=1) are both normally distributed with mean and covariance parameters \left(\vec \mu_0, \Sigma_{y=0}\right) and \left(\vec \mu_1, \Sigma_{y=1}\right), respectively. Under this assumption, the Bayes optimal solution is to predict points as being from the second class if the ratio of the log-likelihoods is below some threshold T, so that;

 (\vec x- \vec \mu_0)^T \Sigma_{y=0}^{-1} ( \vec x- \vec \mu_0)\ +\ \mathrm{ln}|\Sigma_{y=0}|\ -\ (\vec x- \vec \mu_1)^T \Sigma_{y=1}^{-1} ( \vec x- \vec \mu_1)\ -\ \mathrm{ln}|\Sigma_{y=1}| \ < \ T

Without any further assumptions, the resulting classifier is referred to as QDA (quadratic discriminant analysis). LDA also makes the simplifying homoscedastic assumption (i.e. that the class covariances are identical, so Σy = 0 = Σy = 1 = Σ) and that the covariances have full rank. In this case, several terms cancel and the above decision criterion becomes a threshold on the dot product

 \vec w \cdot \vec x < c

for some threshold constant c, where

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

This means that the criterion of an input  \vec x being in a class y is purely a function of this linear combination of the known observations.

It is often useful to see this conclusion in geometrical terms: the criterion of an input  \vec x being in a class y is purely a function of projection of multidimensional-space point  \vec x onto direction  \vec w . In other words, the observation belongs to y if corresponding  \vec x is located on a certain side of a hyperplane perpendicular to  \vec w . The location of the plane is defined by the threshold c.

Canonical discriminant analysis for k classes

Canonical discriminant analysis finds axes (the number of categories -1 = k-1 canonical coordinates) that best separate the categories. These linear functions are uncorrelated and define, in effect, an optimal k-1 space through the n-dimensional cloud of data that best separates (the projections in that space of) the k groups. See "Multiclass LDA" for details below.

Fisher's linear discriminant

The terms Fisher's linear discriminant and LDA are often used interchangeably, although Fisher's original article[1] 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 = 0y = 1. Then the linear combination of features  \vec w \cdot \vec x will have means  \vec w \cdot \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.

Be sure to note that the vector \vec w is the normal to the discriminant hyperplane. As an example, in a two dimensional problem, the line that best divides the two groups is perpendicular to \vec w.

Generally, the data points to be discriminated are projected onto \vec w; then the threshold that best separates the data is chosen from analysis of the one-dimensional distribution. There is no general rule for the threshold. However, if projections of points from both classes exhibit approximately the same distributions, the good choice would be hyperplane in the middle between projections of the two means, \vec w \cdot \vec \mu_{y=0} and \vec w \cdot \vec \mu_{y=1} . In this case the parameter c in threshold condition  \vec w \cdot \vec x < c can be found explicitly:

 c = \vec w \cdot (\vec \mu_{y=0} + \vec \mu_{y=1})/2 .

Multiclass LDA

In the case where there are more than two classes, the analysis used in the derivation of the Fisher discriminant can be extended to find a subspace which appears to contain all of the class variability. Suppose that each of C classes has a mean μi and the same covariance Σ. Then the between class variability may be defined by the sample covariance of the class means

 \Sigma_b = \frac{1}{C} \sum_{i=1}^C (\mu_i-\mu) (\mu_i-\mu)^T

where μ is the mean of the class means. The class separation in a direction  \vec w in this case will be given by

 S = \frac{\vec w^T \Sigma_b \vec w}{\vec w^T \Sigma \vec w}

This means that when  \vec w is an eigenvector of Σ − 1Σb the separation will be equal to the corresponding eigenvalue. Since Σb is of most rank C-1, then these non-zero eigenvectors identify a vector subspace containing the variability between features. These vectors are primarily used in feature reduction, as in PCA. The smaller eigenvalues will tend to be very sensitive to the exact choice of training data, and it is often necessary to use regularisation as described in the next section.

Other generalizations of LDA for multiple classes have been defined to address the more general problem of heteroscedastic distributions (i.e., where the data distributions are not homoscedastic). One such method is Heteroscedastic LDA (see e.g. HLDA among others).

If classification is required, instead of dimension reduction, there are a number of alternative techniques available. For instance, the classes may be partitioned, and a standard Fisher discriminant or LDA used to classify each partition. A common example of this is "one against the rest" where the points from one class are put in one group, and everything else in the other, and then LDA applied. This will result in C classifiers, whose results are combined. Another common method is pairwise classification, where a new classifier is created for each pair of classes (giving C(C-1)/2 classifiers in total), with the individual classifiers combined to produce a final classification.

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 does not exceed the number of samples.[3] 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. However, better numeric stability may be achieved by first projecting the problem onto the subspace spanned by Σb.[7] Another strategy to deal with small sample size is to use a Shrinkage estimator of the covariance matrix, which can be expressed mathematically as

 C_{new} = (1-\lambda) C+\lambda I\,

where I is the identity matrix, and λ is the shrinkage intensity or regularisation parameter. This leads to the framework of regularized discriminant analysis[8] or shrinkage discriminant analysis.[9]

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.

Applications

In addition to the examples given below, LDA is applied in positioning and product management.

Bankruptcy prediction

In bankruptcy prediction based on accounting ratios and other financial variables, linear discriminant analysis was the first statistical method applied to systematically explain which firms entered bankruptcy vs. survived. Despite limitations including known nonconformance of accounting ratios to the normal distribution assumptions of LDA, Edward Altman's 1968 model is still a leading model in practical applications.

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.

Marketing

In marketing, discriminant analysis was once 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. Logistic regression or other methods are now more commonly used. The use of discriminant analysis in marketing can be 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 R, 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.

See also

References

  1. ^ a b Ronald Fisher (1936)The Use of Multiple Measurements in Taxonomic Problems In: Annals of Eugenics, 7, p. 179--188
  2. ^ McLachlan (2004)Discriminant Analysis and Statistical Pattern Recognition In: Wiley Interscience
  3. ^ a b Martinez & Kak (2004)PCA versus LDA In: IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(2): 228–233
  4. ^ H. Abdi (2007)" Discriminant correspondence analysis." In: "N.J. Salkind (Ed.): Encyclopedia of Measurement and Statistics". Thousand Oaks (CA): Sage. pp. 270--275.
  5. ^ G. Perriere & J. Thioulouse (2003). ["Use of Correspondence Discriminant Analysis to predict the subcellular location of bacterial proteins]. In: "Computer Methods and Programs in Biomedicine", 70, 99--105.
  6. ^ Venables, W. N.; Ripley, B. D. (2002). Modern Applied Statistics with S (4th ed.). Springer Verlag. ISBN 0-387-95457-0. 
  7. ^ H. Yu and J. Yang (2001) A direct LDA algorithm for high-dimensional data--with application to face recognition, Pattern Recognition: Vol 34, No. 10, pp. 2067-2069.
  8. ^ Friedman (1989)Regularized Discriminant Analysis In: Journal of the American Statistical Association 84(405): 165–175
  9. ^ M. Ahdesmäki and K. Strimmer (2010) Feature selection in omics prediction problems using cat scores and false nondiscovery rate control, Annals of Applied Statistics: Vol. 4: No. 1, pp. 503-519.

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Linear discriminant analysis — Die Diskriminanzanalyse ist eine Methode der multivariaten Verfahren in der Statistik. Sie wurde von R. A. Fisher 1936 zum ersten Mal in The use of multiple measurements in taxonomic problems[1] beschrieben. Sie wird in der Statistik und im… …   Deutsch Wikipedia

  • Optimal discriminant analysis — (ODA) and the related classification tree analysis (CTA) are statistical methods that maximize predictive accuracy. For any specific sample and exploratory or confirmatory hypothesis, optimal discriminant analysis (ODA) identifies the statistical …   Wikipedia

  • Discriminant function analysis — is a statistical analysis to predict a categorical dependent variable by one or more continuous or binary independent variables. It is different from an ANOVA or MANOVA, which is used to predict one (ANOVA) or multiple (MANOVA) continuous… …   Wikipedia

  • Linear classifier — In the field of machine learning, the goal of classification is to group items that have similar feature values, into groups. A linear classifier achieves this by making a classification decision based on the value of the linear combination of… …   Wikipedia

  • discriminant function — Statistics. a linear function of measurements of different properties of an object or event that is used to assign the object or event to one population or another (discriminant analysis). [1935 40] * * * …   Universalium

  • Principal component analysis — PCA of a multivariate Gaussian distribution centered at (1,3) with a standard deviation of 3 in roughly the (0.878, 0.478) direction and of 1 in the orthogonal direction. The vectors shown are the eigenvectors of the covariance matrix scaled by… …   Wikipedia

  • Principal components analysis — Principal component analysis (PCA) is a vector space transform often used to reduce multidimensional data sets to lower dimensions for analysis. Depending on the field of application, it is also named the discrete Karhunen Loève transform (KLT),… …   Wikipedia

  • multivariate analysis — Univariate analysis consists in describing and explaining the variation in a single variable. Bivariate analysis does the same for two variables taken together (covariation). Multivariate analysis (MVA) considers the simultaneous effects of many… …   Dictionary of sociology

  • Multivariate analysis of variance — (MANOVA) is a generalized form of univariate analysis of variance (ANOVA). It is used when there are two or more dependent variables. It helps to answer : 1. do changes in the independent variable(s) have significant effects on the dependent …   Wikipedia

  • Multilinear subspace learning — (MSL) aims to learn a specific small part of a large space of multidimensional objects having a particular desired property. It is a dimensionality reduction approach for finding a low dimensional representation with certain preferred… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.