Linear discriminant analysis
Linear discriminant analysis (LDA), normal discriminant analysis (NDA), 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.
Not to be confused with latent Dirichlet allocation.
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.[2][3] 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).[4] 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 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 they both look for linear combinations of variables which best explain the data.[5] 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 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.[6][7]
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.[8] In simple terms, discriminant function analysis is classification - the act of distributing things into groups, classes or categories of the same type.
History[edit]
The original dichotomous discriminant analysis was developed by Sir Ronald Fisher in 1936.[9] 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.[10]
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.[8]
It has been suggested that discriminant analysis is relatively robust to slight violations of these assumptions,[12] and it has also been shown that discriminant analysis may still be reliable when using dichotomous variables (where multivariate normality is often violated).[13]
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 where = number of groups, or (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 , with sets of sample space, there is a discriminant rule such that if , then . Discriminant analysis then, finds “good” regions of to minimize classification error, therefore leading to a high percent correct classified in the classification table.[14]
Each function is given a discriminant score to determine how well it predicts group placement.
Eigenvalues[edit]
An eigenvalue in discriminant analysis is the characteristic root of each function. It is an indication of how well that function differentiates the groups, where the larger the eigenvalue, the better the function differentiates.[8] This however, should be interpreted with caution, as eigenvalues have no upper limit.[10][8] The eigenvalue can be viewed as a ratio of SSbetween and SSwithin as in ANOVA when the dependent variable is the discriminant function, and the groups are the levels of the IV.[10] This means that the largest eigenvalue is associated with the first function, the second largest with the second, etc..
Effect size[edit]
Some suggest the use of eigenvalues as effect size measures, however, this is generally not supported.[10] Instead, the canonical correlation is the preferred measure of effect size. It is similar to the eigenvalue, but is the square root of the ratio of SSbetween and SStotal. It is the correlation between groups and the function.[10] Another popular measure of effect size is the percent of variance for each function. This is calculated by: (λx/Σλi) X 100 where λx is the eigenvalue for the function and Σλi is the sum of all eigenvalues. This tells us how strong the prediction is for that particular function compared to the others.[10] Percent correctly classified can also be analyzed as an effect size. The kappa value can describe this while correcting for chance agreement.[10]Kappa normalizes across all categorizes rather than biased by a significantly good or poorly performing classes.[17]
Canonical discriminant analysis for k classes[edit]
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.
Incremental LDA[edit]
The typical implementation of the LDA technique requires that all the samples are available in advance. However, there are situations where the entire data set is not available and the input data are observed as a stream. In this case, it is desirable for the LDA feature extraction to have the ability to update the computed LDA features by observing the new samples without running the algorithm on the whole data set. For example, in many real-time applications such as mobile robotics or on-line face recognition, it is important to update the extracted LDA features as soon as new observations are available. An LDA feature extraction technique that can update the LDA features by simply observing new samples is an incremental LDA algorithm, and this idea has been extensively studied over the last two decades.[20] Chatterjee and Roychowdhury proposed an incremental self-organized LDA algorithm for updating the LDA features.[21] In other work, Demir and Ozmehmet proposed online local learning algorithms for updating LDA features incrementally using error-correcting and the Hebbian learning rules.[22] Later, Aliyari et al. derived fast incremental algorithms to update the LDA features by observing the new samples.[20]
Comparison to logistic regression[edit]
Discriminant function analysis is very similar to logistic regression, and both can be used to answer the same research questions.[10] Logistic regression does not have as many assumptions and restrictions as discriminant analysis. However, when discriminant analysis’ assumptions are met, it is more powerful than logistic regression.[33] Unlike logistic regression, discriminant analysis can be used with small sample sizes. It has been shown that when sample sizes are equal, and homogeneity of variance/covariance holds, discriminant analysis is more accurate.[8] Despite all these advantages, logistic regression has none-the-less become the common choice, since the assumptions of discriminant analysis are rarely met.[9][8]
Linear discriminant in high dimensions[edit]
Geometric anomalies in higher dimensions lead to the well-known curse of dimensionality. Nevertheless, proper utilization of concentration of measure phenomena can make computation easier.[34] An important case of these blessing of dimensionality phenomena was highlighted by Donoho and Tanner: if a sample is essentially high-dimensional then each point can be separated from the rest of the sample by linear inequality, with high probability, even for exponentially large samples.[35] These linear inequalities can be selected in the standard (Fisher's) form of the linear discriminant for a rich family of probability distribution.[36] In particular, such theorems are proven for log-concave distributions including multidimensional normal distribution (the proof is based on the concentration inequalities for log-concave measures[37]) and for product measures on a multidimensional cube (this is proven using Talagrand's concentration inequality for product probability spaces). Data separability by classical linear discriminants simplifies the problem of error correction for artificial intelligence systems in high dimension.[38]