Linear discriminant analysis (Ofer Abarbanel online library)

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, pattern recognition, and machine learning 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.[1][2] 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).[3] 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.[4] 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.[5][6]

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.[7] 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.[8] 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.[9]

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.[7]

  • Multivariate normality: Independent variables are normal for each level of the grouping variable.[9][7]
  • Homogeneity of variance/covariance (homoscedasticity): Variances among group variables are the same across levels of predictors. Can be tested with Box’s M statistic.[9]It has been suggested, however, that linear discriminant analysis be used when covariances are equal, and that quadratic discriminant analysis may be used when covariances are not equal.[7]
  • Multicollinearity: Predictive power can decrease with an increased correlation between predictor variables.[7]
  • Independence: Participants are assumed to be randomly sampled, and a participant’s score on one variable is assumed to be independent of scores on that variable for all other participants.[9][7]

It has been suggested that discriminant analysis is relatively robust to slight violations of these assumptions,[11] and it has also been shown that discriminant analysis may still be reliable when using dichotomous variables (where multivariate normality is often violated).[12]

Eigenvalues

An eigenvalue in discriminant analysis is the characteristic root of each function.[clarification needed] It is an indication of how well that function differentiates the groups, where the larger the eigenvalue, the better the function differentiates.[7] This however, should be interpreted with caution, as eigenvalues have no upper limit.[9][7] 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[clarification needed].[9] This means that the largest eigenvalue is associated with the first function, the second largest with the second, etc..

Effect size

Some suggest the use of eigenvalues as effect size measures, however, this is generally not supported.[9] 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.[9] Another popular measure of effect size is the percent of variance[clarification needed] 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.[9] Percent correctly classified can also be analyzed as an effect size. The kappa value can describe this while correcting for chance agreement.[9]Kappa normalizes across all categorizes rather than biased by a significantly good or poorly performing classes.[clarification needed][16]

Incremental LDA

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.[19] Chatterjee and Roychowdhury proposed an incremental self-organized LDA algorithm for updating the LDA features.[20] In other work, Demir and Ozmehmet proposed online local learning algorithms for updating LDA features incrementally using error-correcting and the Hebbian learning rules.[21] Later, Aliyari et al. derived fast incremental algorithms to update the LDA features by observing the new samples.[19]

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.

Biomedical studies

The main application of discriminant analysis in medicine is the assessment of severity state of a patient and prognosis of disease outcome. For example, during retrospective analysis, patients are divided into groups according to severity of disease – mild, moderate and severe form. Then results of clinical and laboratory analyses are studied in order to reveal variables which are statistically different in studied groups. Using these variables, discriminant functions are built which help to objectively classify disease in a future patient into mild, moderate or severe form.

In biology, similar principles are used in order to classify and define groups of different biological objects, for example, to define phage types of Salmonella enteritidis based on Fourier transform infrared spectra,[25] to detect animal source of Escherichia coli studying its virulence factors[26] etc.

Earth science

This method can be used to separate the alteration zones. For example, when different data from various zones are available, discriminant analysis can find the pattern within the data and classify it effectively.[27]

Comparison to logistic regression

Discriminant function analysis is very similar to logistic regression, and both can be used to answer the same research questions.[9] 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.[28] 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.[7] With all this being considered, logistic regression has become the common choice, since the assumptions of discriminant analysis are rarely met.[8][7]

Linear discriminant in high dimension

Geometric anomalities in high dimension lead to the well-known curse of dimensionality. Nevertheless, proper utilization of concentration of measure phenomena can make computation easier.[29] 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.[30] These linear inequalities can be selected in the standard (Fisher’s) form of the linear discriminant for a rich family of probability distribution.[31] In particular, such theorems are proven for log-concave distributions including multidimensional normal distribution (the proof is based on the concentration inequalities for long-concave measures[32]) 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.[33]

References

  1. ^ Jump up to:ab Fisher, R. A. (1936). “The Use of Multiple Measurements in Taxonomic Problems” (PDF). Annals of Eugenics. 7 (2): 179–188. doi:10.1111/j.1469-1809.1936.tb02137.x. hdl:2440/15227.
  2. ^McLachlan, G. J. (2004). Discriminant Analysis and Statistical Pattern Recognition. Wiley Interscience. ISBN 978-0-471-69115-0. MR 1190469.
  3. ^Analyzing Quantitative Data: An Introduction for Social Researchers, Debra Wetcher-Hendricks, p.288
  4. ^ Jump up to:ab Martinez, A. M.; Kak, A. C. (2001). “PCA versus LDA” (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 23 (=2): 228–233. doi:10.1109/34.908974.
  5. ^Abdi, H. (2007) “Discriminant correspondence analysis.”In: N.J. Salkind (Ed.): Encyclopedia of Measurement and Statistic. Thousand Oaks (CA): Sage. pp. 270–275.
  6. ^Perriere, G.; Thioulouse, J. (2003). “Use of Correspondence Discriminant Analysis to predict the subcellular location of bacterial proteins”. Computer Methods and Programs in Biomedicine. 70 (2): 99–105. doi:10.1016/s0169-2607(02)00011-1. PMID 12507786.
  7. ^ Jump up to:ab c d e f g h i j BÖKEOĞLU ÇOKLUK, Ö, & BÜYÜKÖZTÜRK, Ş. (2008). Discriminant function analysis: Concept and application. Eğitim araştırmaları dergisi, (33), 73-92.
  8. ^ Jump up to:ab Cohen et al. Applied Multiple Regression/Correlation Analysis for the Behavioural Sciences 3rd ed. (2003). Taylor & Francis Group.
  9. ^ Jump up to:ab c d e f g h i j k Green, S.B. Salkind, N. J. & Akey, T. M. (2008). Using SPSS for Windows and Macintosh: Analyzing and understanding data. New Jersey: Prentice Hall.
  10. ^Venables, W. N.; Ripley, B. D. (2002). Modern Applied Statistics with S (4th ed.). Springer Verlag. ISBN 978-0-387-95457-8.
  11. ^Lachenbruch, P. A. (1975). Discriminant analysis. NY: Hafner
  12. ^Klecka, William R. (1980). Discriminant analysis. Quantitative Applications in the Social Sciences Series, No. 19. Thousand Oaks, CA: Sage Publications.
  13. ^Hardle, W., Simar, L. (2007). Applied Multivariate Statistical Analysis. Springer Berlin Heidelberg. pp. 289–303.
  14. ^Garson, G. D. (2008). Discriminant function analysis. https://web.archive.org/web/20080312065328/http://www2.chass.ncsu.edu/garson/pA765/discrim.htm.
  15. ^ Jump up to:ab c Hardle, W., Simar, L. (2007). Applied Multivariate Statistical Analysis. Springer Berlin Heidelberg. pp. 289-303.
  16. ^Israel, Steven A. (June 2006). “Performance Metrics: How and When”. Geocarto International. 21 (2): 23–32. doi:10.1080/10106040608542380. ISSN 1010-6049.
  17. ^Garson, G. D. (2008). Discriminant function analysis. “Archived copy”. Archived from the original on 2008-03-12. Retrieved 2008-03-04. .
  18. ^Rao, R. C. (1948). “The utilization of multiple measurements in problems of biological classification”. Journal of the Royal Statistical Society, Series B. 10 (2): 159–203. JSTOR 2983775.
  19. ^ Jump up to:ab Aliyari Ghassabeh, Youness; Rudzicz, Frank; Moghaddam, Hamid Abrishami (2015-06-01). “Fast incremental LDA feature extraction”. Pattern Recognition. 48(6): 1999–2012. doi:10.1016/j.patcog.2014.12.012.
  20. ^Chatterjee, C.; Roychowdhury, V.P. (1997-05-01). “On self-organizing algorithms and networks for class-separability features”. IEEE Transactions on Neural Networks. 8 (3): 663–678. doi:10.1109/72.572105. ISSN 1045-9227. PMID 18255669.
  21. ^Demir, G. K.; Ozmehmet, K. (2005-03-01). “Online Local Learning Algorithms for Linear Discriminant Analysis”. Pattern Recogn. Lett. 26 (4): 421–431. doi:10.1016/j.patrec.2004.08.005. ISSN 0167-8655.
  22. ^Yu, H.; Yang, J. (2001). “A direct LDA algorithm for high-dimensional data — with application to face recognition”. Pattern Recognition. 34 (10): 2067–2069. CiteSeerX 10.1.1.70.3507. doi:10.1016/s0031-3203(00)00162-x.
  23. ^Friedman, J. H. (1989). “Regularized Discriminant Analysis” (PDF). Journal of the American Statistical Association. 84 (405): 165–175. CiteSeerX 10.1.1.382.2682. doi:10.2307/2289860. JSTOR 2289860. MR 0999675.
  24. ^Ahdesmäki, M.; Strimmer, K. (2010). “Feature selection in omics prediction problems using cat scores and false nondiscovery rate control”. Annals of Applied Statistics. 4 (1): 503–519. arXiv:0903.2003. doi:10.1214/09-aoas277.
  25. ^Preisner, O; Guiomar, R; Machado, J; Menezes, JC; Lopes, JA (2010). “Application of Fourier transform infrared spectroscopy and chemometrics for differentiation of Salmonella enterica serovar Enteritidis phage types”. Appl Environ Microbiol. 76 (11): 3538–3544. doi:10.1128/aem.01589-09. PMC 2876429. PMID 20363777.
  26. ^David, DE; Lynne, AM; Han, J; Foley, SL (2010). “Evaluation of virulence factor profiling in the characterization of veterinary Escherichia coli isolates”. Appl Environ Microbiol. 76 (22): 7509–7513. doi:10.1128/aem.00726-10. PMC 2976202. PMID 20889790.
  27. ^Tahmasebi, P.; Hezarkhani, A.; Mortazavi, M. (2010). “Application of discriminant analysis for alteration separation; sungun copper deposit, East Azerbaijan, Iran. Australian”(PDF). Journal of Basic and Applied Sciences. 6 (4): 564–576.
  28. ^Trevor Hastie; Robert Tibshirani; Jerome Friedman. The Elements of Statistical Learning. Data Mining, Inference, and Prediction (second ed.). Springer. p. 128.
  29. ^Kainen P.C. (1997) Utilizing geometric anomalies of high dimension: When complexity makes computation easier. In: Kárný M., Warwick K. (eds) Computer Intensive Methods in Control and Signal Processing: The Curse of Dimensionality, Springer, 1997, pp. 282–294.
  30. ^Donoho, D., Tanner, J. (2009) Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing, Phil. Trans. R. Soc. A 367, 4273–4293.
  31. ^Gorban, Alexander N.; Golubkov, Alexander; Grechuck, Bogdan; Mirkes, Evgeny M.; Tyukin, Ivan Y. (2018). “Correction of AI systems by linear discriminants: Probabilistic foundations”. Information Sciences. 466: 303–322. arXiv:1811.05321. doi:10.1016/j.ins.2018.07.040.
  32. ^Guédon, O., Milman, E. (2011) Interpolating thin-shell and sharp large-deviation estimates for isotropic log-concave measures, Geom. Funct. Anal. 21 (5), 1043–1068.
  33. ^Gorban, Alexander N.; Makarov, Valeri A.; Tyukin, Ivan Y. (July 2019). “The unreasonable effectiveness of small neural ensembles in high-dimensional brain”. Physics of Life Reviews. 29: 55–88. arXiv:1809.07656. doi:10.1016/j.plrev.2018.09.005. PMID 30366739.

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library