On Dimensionality, Sample Size, Classification Error, and Complexity of Classification Algorithm in Pattern Recognition

Abstract

This paper compares four classification algorithms-discriminant functions when classifying individuals into two multivariate populations. The discriminant functions (DF's) compared are derived according to the Bayes rule for normal populations and differ in assumptions on the covariance matrices' structure. Analytical formulas for the expected probability of misclassification EP_N are derived and show that the classification error EP_N depends on the structure of a classification algorithm, asymptotic probability of misclassification P∞, and the ratio of learning sample size N to dimensionality p:N/p for all linear DF's discussed and N²/p for quadratic DF's. The tables for learning quantity H = EPN</sub./P∞ depending on parameters P∞, N, and p for four classifilcation algorithms analyzed are presented and may be used for estimating the necessary learning sample size, detennining the optimal number of features, and choosing the type of the classification algorithm in the case of a limited learning sample size.