Linear discriminant analysis
From Wikipedia, the free encyclopedia
Categories: Multivariate statistics | Statistics | Classification algorithms | Psychometrics | Market research | Marketing | Consumer behaviour
|
Linear discriminant analysis (LDA) and the related Fisher's linear discriminant are methods used in statistics and machine learning to find the linear combination of features which best 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. 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).
LDA for two classesConsider 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 conditional probability density functions Failed to parse (Missing texvc executable; please see math/README to configure.): p(\vec x|y=1) and Failed to parse (Missing texvc executable; please see math/README to configure.): p(\vec x|y=0) are both normally distributed. Under this assumption, the Bayes optimal solution is to predict points as being from the second class if the likelihood ratio is below some threshold T, so that Failed to parse (Missing texvc executable; please see math/README to configure.): (\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
Fisher's linear discriminantThe 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 Failed to parse (Missing texvc executable; please see math/README to configure.): \vec \mu_{y=0}, \vec \mu_{y=1}
and covariances Failed to parse (Missing texvc executable; please see math/README to configure.): \Sigma_{y=0},\Sigma_{y=1}
. Then the linear combination of features Failed to parse (Missing texvc executable; please see math/README to configure.): \vec w \cdot \vec x
will have means Failed to parse (Missing texvc executable; please see math/README to configure.): \vec w \cdot \vec \mu_{y=i}
and variances Failed to parse (Missing texvc executable; please see math/README to configure.): \vec w^T \Sigma_{y=i} \vec w
for Failed to parse (Missing texvc executable; please see math/README to configure.): 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:
Multiclass LDAIn 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 Failed to parse (Missing texvc executable; please see math/README to configure.): \mu_i and the same covariance Failed to parse (Missing texvc executable; please see math/README to configure.): \Sigma . Then the between class variability may be defined by the sample covariance of the class means
is the mean of the class means. The class separation in a direction Failed to parse (Missing texvc executable; please see math/README to configure.): \vec w in this case will be given by
is an eigenvector of Failed to parse (Missing texvc executable; please see math/README to configure.): \Sigma_b \Sigma^{-1}
the separation will be equal to the corresponding eigenvalue. Since Failed to parse (Missing texvc executable; please see math/README to configure.): \Sigma_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 eigenvectors 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) classifiers in total), with the individual classifiers combined to produce a final classification. Practical useIn 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
is the identity matrix, and Failed to parse (Missing texvc executable; please see math/README to configure.): \sigma is the amount of noise added, called in this context the regularisation parameter. The value of Failed to parse (Missing texvc executable; please see math/README to configure.): \sigma 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 Failed to parse (Missing texvc executable; please see math/README to configure.): p(\vec x|c=i) are normal with shared covariances, the sufficient statistic for Failed to parse (Missing texvc executable; please see math/README to configure.): 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. ApplicationsIn addition to the examples given below, LDA is applied in positioning, product management, and marketing research. Face recognitionIn 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. MarketingIn 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:
See alsoReferences
External linkseo:Vikipedio:Projekto matematiko/Lineara diskriminanta analitiko fa:تحلیل تفکیک خطی fr:Analyse discriminante linéaire hr:Linearna analiza različitih it:Analisi discriminante nl:Discriminantanalyse ja:判別分析 pl:Analiza dyskryminacyjna ru:Дискриминантный анализ sl:Diskriminantna analiza |
