thumb|Linear discriminant analysis on a two dimensional space with two classes. The Bayes boundary is calculated based on the true data generation parameters, the estimated boundary on the realised data points.
thumb|Linear discriminant analysis animation. Given a dataset with two labels, the dataset is projected to a line. The optimal projection is obtained when the ratio of (between-class variance)/(within-class variance) is maximized.
Linear discriminant analysis (LDA), normal discriminant analysis (NDA), canonical variates analysis (CVA), or discriminant function analysis is a generalization of Fisher's linear discriminant, a method used in statistics and other fields, to find a linear combination of features that characterizes or separates 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 analysis of variance (ANOVA) and regression analysis, which also attempt to express one dependent variable as a linear combination of other features or measurements. However, ANOVA uses categorical independent variables and a continuous dependent variable, whereas discriminant analysis has continuous independent variables and a categorical dependent variable (i.e. the class label). Logistic regression and probit regression are more similar to LDA than ANOVA is, as they also explain a categorical variable by the values of continuous independent variables. These other methods are preferable in applications where it is not reasonable to assume that the independent variables have a normal distribution, which is a fundamental assumption of the LDA method.
LDA is also closely related to principal component analysis (PCA) and factor analysis in that they 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, in contrast, does not take into account any difference in class, and factor analysis builds the feature combinations based on similarities rather than differences. 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.
Discriminant analysis is used when groups are known a priori (unlike in cluster analysis). Each case must have a score on one or more quantitative predictor measures, and a score on a group measure. In simple terms, discriminant function analysis is classification - the act of distributing things into groups, classes or categories of the same type.
History
The original dichotomous discriminant analysis was developed by Sir Ronald Fisher in 1936. It is different from an ANOVA or MANOVA, which is used to predict one (ANOVA) or multiple (MANOVA) continuous dependent variables by one or more independent categorical variables. Discriminant function analysis is useful in determining whether a set of variables is effective in predicting category membership.
LDA for two classes
Consider a set of observations <math> { \vec x } </math> (also called features, attributes, variables or measurements) for each sample of an object or event with known class <math>y</math>. This set of samples is called the training set in a supervised learning context. The classification problem is then to find a good predictor for the class <math>y</math> of any sample of the same distribution (not necessarily from the training set) given only an observation <math> \vec x </math>.
LDA approaches the problem by assuming that the conditional probability density functions <math>p(\vec x|y=0)</math> and <math>p(\vec x|y=1)</math> are both the normal distribution with mean and covariance parameters <math>\left(\vec \mu_0, \Sigma_0\right)</math> and <math>\left(\vec \mu_1, \Sigma_1\right)</math>, respectively. Under this assumption, the Bayes-optimal solution is to predict points as being from the second class if the log of the likelihood ratios is bigger than some threshold T, so that:
: <math> \frac{1}{2} (\vec x - \vec \mu_0)^\mathrm{T} \Sigma_0^{-1} ( \vec x - \vec \mu_0) + \frac{1}{2} \ln|\Sigma_0| - \frac{1}{2} (\vec x - \vec \mu_1)^\mathrm{T} \Sigma_1^{-1} ( \vec x - \vec \mu_1) - \frac{1}{2} \ln|\Sigma_1| \ > \ T </math>
Without any further assumptions, the resulting classifier is referred to as quadratic discriminant analysis (QDA).
LDA instead makes the additional simplifying homoscedasticity assumption (i.e. that the class covariances are identical, so <math>\Sigma_0 = \Sigma_1 = \Sigma</math>) and that the covariances have full rank.
In this case, several terms cancel:
:<math> {\vec x}^\mathrm{T} \Sigma_0^{-1} \vec x = {\vec x}^\mathrm{T} \Sigma_1^{-1} \vec x</math>
:<math>{\vec x}^\mathrm{T} {\Sigma_i}^{-1} \vec{\mu}_i = {\vec{\mu}_i}^\mathrm{T}{\Sigma_i}^{-1} \vec x</math> because both sides are scalar and transpose to each other (<math>\Sigma_i</math> is Hermitian)
and the above decision criterion
becomes a threshold on the dot product
:<math> {\vec w}^\mathrm{T} \vec x > c </math>
for some threshold constant c, where
:<math>\vec w = \Sigma^{-1} (\vec \mu_1 - \vec \mu_0)</math>
:<math> c = \frac12 \, {\vec w}^\mathrm{T} (\vec \mu_1 + \vec \mu_0)</math>
This means that the criterion of an input <math> \vec{ x }</math> being in a class <math>y</math> 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 <math> \vec{ x }</math> being in a class <math>y</math> is purely a function of projection of multidimensional-space point <math> \vec{ x }</math> onto vector <math> \vec{ w }</math> (thus, we only consider its direction). In other words, the observation belongs to <math>y</math> if corresponding <math> \vec{ x }</math> is located on a certain side of a hyperplane perpendicular to <math> \vec{ w }</math>. The location of the plane is defined by the threshold <math>c</math>.
Assumptions
The assumptions of discriminant analysis are the same as those for MANOVA. The analysis is quite sensitive to outliers and the size of the smallest group must be larger than the number of predictor variables. and it has also been shown that discriminant analysis may still be reliable when using dichotomous variables (where multivariate normality is often violated).
Discriminant functions
Discriminant analysis works by creating one or more linear combinations of predictors, creating a new latent variable for each function. These functions are called discriminant functions. The number of functions possible is either <math>N_g-1</math> where <math>N_g</math> = number of groups, or <math>p</math> (the number of predictors), whichever is smaller. The first function created maximizes the differences between groups on that function. The second function maximizes differences on that function, but also must not be correlated with the previous function. This continues with subsequent functions with the requirement that the new function not be correlated with any of the previous functions.
Given group <math>j</math>, with <math>\mathbb{R}_j</math> sets of sample space, there is a discriminant rule such that if <math>x \in\mathbb{R}_j</math>, then <math>x\in j</math>. Discriminant analysis then, finds “good” regions of <math>\mathbb{R}_j</math> to minimize classification error, therefore leading to a high percent correct classified in the classification table.
Each function is given a discriminant score to determine how well it predicts group placement.
- Structure Correlation Coefficients: The correlation between each predictor and the discriminant score of each function. This is a zero-order correlation (i.e., not corrected for the other predictors).
- Standardized Coefficients: Each predictor's weight in the linear combination that is the discriminant function. Like in a regression equation, these coefficients are partial (i.e., corrected for the other predictors). Indicates the unique contribution of each predictor in predicting group assignment.
- Functions at Group Centroids: Mean discriminant scores for each grouping variable are given for each function. The farther apart the means are, the less error there will be in classification.
Discrimination rules
- Maximum likelihood: Assigns <math>x</math> to the group that maximizes population (group) density.
- Bayes Discriminant Rule: Assigns <math>x</math> to the group that maximizes <math>\pi_i f_i(x)</math>, where π<sub>i</sub> represents the prior probability of that classification, and <math>f_i(x)</math> represents the population density.
Canonical discriminant analysis for k classes
Canonical discriminant analysis (CDA) finds axes (k − 1 canonical coordinates, k being the number of classes) 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.
Because LDA uses canonical variates, it was initially often referred as the "method of canonical variates" or canonical variates analysis (CVA).
Fisher's linear discriminant
The terms Fisher's linear discriminant and LDA are often used interchangeably, although Fisher's original article This generalization is due to C. R. Rao. Suppose that each of C classes has a mean <math> \mu_i </math> and the same covariance <math> \Sigma </math>. Then the scatter between class variability may be defined by the sample covariance of the class means
:<math> \Sigma_b = \frac{1}{C} \sum_{i=1}^C (\mu_i-\mu) (\mu_i-\mu)^\mathrm{T} </math>
where <math> \mu </math> is the mean of the class means. The class separation in a direction <math> \vec w </math> in this case will be given by
:<math> S = \frac