Linear discriminant analysis: A detailed tutorial

Abstract

Linear Discriminant Analysis (LDA) is a very common technique for dimensionality reduction problems as a pre-processing step for machine learning and pattern classification applications. At the same time, it is usually used as a black box, but (sometimes) not well understood. The aim of this paper is to build a solid intuition for what is LDA, and how LDA works, thus enabling readers of all levels be able to get a better understanding of the LDA and to know how to apply this technique in different applications. The paper first gave the basic definitions and steps of how LDA technique works supported with visual explanations of these steps. Moreover, the two methods of computing the LDA space, i.e. class-dependent and class-independent methods, were explained in details. Then, in a step-by-step approach, two numerical examples are demonstrated to show how the LDA space can be calculated in case of the class-dependent and class-independent methods. Furthermore, two of the most common LDA problems (i.e. Small Sample Size (SSS) and non-linearity problems) were highlighted and illustrated, and state-of-the-art solutions to these problems were investigated and explained. Finally, a number of experiments was conducted with different datasets to (1) investigate the effect of the eigenvectors that used in the LDA space on the robustness of the extracted feature for the classification accuracy, and (2) to show when the SSS problem occurs and how it can be addressed.

Keywords

Dimensionality reduction PCA LDA Kernel Functions Class-Dependent LDA Class-Independent LDA SSS (Small Sample Size) problem eigenvectors artificial intelligence

1. Introduction

Dimensionality reduction techniques are important in many applications related to machine learning [15], data mining [6,33], Bioinformatics [47], biometric [61] and information retrieval [73]. The main goal of the dimensionality reduction techniques is to reduce the dimensions by removing the redundant and dependent features by transforming the features from a higher dimensional space that may lead to a curse of dimensionality problem, to a space with lower dimensions. There are two major approaches of the dimensionality reduction techniques, namely, unsupervised and supervised approaches. In the unsupervised approach, there is no need for labeling classes of the data. While in the supervised approach, the dimensionality reduction techniques take the class labels into consideration [15,32].

There are many unsupervised dimensionality reduction techniques such as Independent Component Analysis (ICA) [28,31] and Non-negative Matrix Factorization (NMF) [14], but the most famous technique of the unsupervised approach is the Principal Component Analysis (PCA) [4,62,67,71]. This type of data reduction is suitable for many applications such as visualization [2,40], and noise removal [70]. On the other hand, the supervised approach has many techniques such as Mixture Discriminant Analysis (MDA) [25] and Neural Networks (NN) [27], but the most famous technique of this approach is the Linear Discriminant Analysis (LDA) [50]. This category of dimensionality reduction techniques are used in biometrics [12,36], Bioinformatics [77], and chemistry [11].

The LDA technique is developed to transform the features into a lower dimensional space, which maximizes the ratio of the between-class variance to the within-class variance, thereby guaranteeing maximum class separability [43,76]. There are two types of LDA technique to deal with classes: class-dependent and class-independent. In the class-dependent LDA, one separate lower dimensional space is calculated for each class to project its data on it whereas, in the class-independent LDA, each class will be considered as a separate class against the other classes [1,74]. In this type, there is just one lower dimensional space for all classes to project their data on it.

Fig. 1.

Visualized steps to calculate a lower dimensional subspace of the LDA technique.

Although the LDA technique is considered the most well-used data reduction techniques, it suffers from a number of problems. In the first problem, LDA fails to find the lower dimensional space if the dimensions are much higher than the number of samples in the data matrix. Thus, the within-class matrix becomes singular, which is known as the small sample problem (SSS). There are different approaches that proposed to solve this problem. The first approach is to remove the null space of within-class matrix as reported in [56,79]. The second approach used an intermediate subspace (e.g. PCA) to convert a within-class matrix to a full-rank matrix; thus, it can be inverted [4,35]. The third approach, a well-known solution, is to use the regularization method to solve a singular linear systems [38,57]. In the second problem, the linearity problem, if different classes are non-linearly separable, the LDA cannot discriminate between these classes. One solution to this problem is to use the kernel functions as reported in [50].

The brief tutorials on the two LDA types are reported in [1]. However, the authors did not show the LDA algorithm in details using numerical tutorials, visualized examples, nor giving insight investigation of experimental results. Moreover, in [57], an overview of the SSS for the LDA technique was presented including the theoretical background of the SSS problem. Moreover, different variants of LDA technique were used to solve the SSS problem such as Direct LDA (DLDA) [22,83], regularized LDA (RLDA) [18,37,38,80], PCA+LDA [42], Null LDA (NLDA) [10,82], and kernel DLDA (KDLDA) [36]. In addition, the authors presented different applications that used the LDA-SSS techniques such as face recognition and cancer classification. Furthermore, they conducted different experiments using three well-known face recognition datasets to compare between different variants of the LDA technique. Nonetheless, in [57], there is no detailed explanation of how (with numerical examples) to calculate the within and between class variances to construct the LDA space. In addition, the steps of constructing the LDA space are not supported with well-explained graphs helping for well understanding of the LDA underlying mechanism. In addition, the non-linearity problem was not highlighted.

This paper gives a detailed tutorial about the LDA technique, and it is divided into five sections. Section 2 gives an overview about the definition of the main idea of the LDA and its background. This section begins by explaining how to calculate, with visual explanations, the between-class variance, within-class variance, and how to construct the LDA space. The algorithms of calculating the LDA space and projecting the data onto this space to reduce its dimension are then introduced. Section 3 illustrates numerical examples to show how to calculate the LDA space and how to select the most robust eigenvectors to build the LDA space. While Section 4 explains the most two common problems of the LDA technique and a number of state-of-the-art methods to solve (or approximately solve) these problems. Different applications that used LDA technique are introduced in Section 5. In Section 6, different packages for the LDA and its variants were presented. In Section 7, two experiments are conducted to show (1) the influence of the number of the selected eigenvectors on the robustness and dimension of the LDA space, (2) how the SSS problem occurs and highlights the well-known methods to solve this problem. Finally, concluding remarks will be given in Section 8.

2. LDA technique

2.1. Definition of LDA

The goal of the LDA technique is to project the original data matrix onto a lower dimensional space. To achieve this goal, three steps needed to be performed. The first step is to calculate the separability between different classes (i.e. the distance between the means of different classes), which is called the between-class variance or between-class matrix. The second step is to calculate the distance between the mean and the samples of each class, which is called the within-class variance or within-class matrix. The third step is to construct the lower dimensional space which maximizes the between-class variance and minimizes the within-class variance. This section will explain these three steps in detail, and then the full description of the LDA algorithm will be given. Figures 1 and 2 are used to visualize the steps of the LDA technique.

Fig. 2.

Projection of the original samples (i.e. data matrix) on the lower dimensional space of LDA ( $V_{k}$ ).

2.2. Calculating the between-class variance (

S_{B}

)

The between-class variance of the ith class ( $S_{B_{i}}$ ) represents the distance between the mean of the ith class ( $μ_{i}$ ) and the total mean (μ). LDA technique searches for a lower-dimensional space, which is used to maximize the between-class variance, or simply maximize the separation distance between classes. To explain how the between-class variance or the between-class matrix ( $S_{B}$ ) can be calculated, the following assumptions are made. Given the original data matrix $X = {x_{1}, x_{2}, \dots, x_{N}}$ , where $x_{i}$ represents the ith sample, pattern, or observation and N is the total number of samples. Each sample is represented by M features ( $x_{i} \in R^{M}$ ). In other words, each sample is represented as a point in M-dimensional space. Assume the data matrix is partitioned into $c = 3$ classes as follows, $X = [ω_{1}, ω_{2}, ω_{3}]$ as shown in Fig. 1 (step (A)). Each class has five samples (i.e. $n_{1} = n_{2} = n_{3} = 5$ ), where $n_{i}$ represents the number of samples of the ith class. The total number of samples (N) is calculated as follows, $N = \sum_{i = 1}^{3} n_{i}$ .

To calculate the between-class variance ( $S_{B}$ ), the separation distance between different classes which is denoted by $(m_{i} - m)$ will be calculated as follows: $\begin{array}{rcl} {(m_{i} - m)}^{2} & = & {(W^{T} μ_{i} - W^{T} μ)}^{2} \\ (1) & = & W^{T} (μ_{i} - μ) {(μ_{i} - μ)}^{T} W \end{array}$ where $m_{i}$ represents the projection of the mean of the ith class and it is calculated as follows, $m_{i} = W^{T} μ_{i}$ , where m is the projection of the total mean of all classes and it is calculated as follows, $m = W^{T} μ$ , W represents the transformation matrix of LDA,1

¹
The transformation matrix (W) will be explained in Section 2.4.

μ_{i} (1 \times M)

represents the mean of the ith class and it is computed as in Equation (2), and

μ (1 \times M)

is the total mean of all classes and it can be computed as in Equation (3) [36,83]. Figure 1 shows the mean of each class and the total mean in step (B) and (C), respectively.

\begin{array}{l} (2) & μ_{j} = \frac{1}{n_{j}} \sum_{x_{i} \in ω_{j}} x_{i} \\ (3) & μ = \frac{1}{N} \sum_{i = 1}^{N} x_{i} = \sum_{i = 1}^{c} \frac{n_{i}}{N} μ_{i} \end{array}

where c represents the total number of classes (in our example

c = 3

The term $(μ_{i} - μ) {(μ_{i} - μ)}^{T}$ in Equation (1) represents the separation distance between the mean of the ith class ( $μ_{i}$ ) and the total mean (μ), or simply it represents the between-class variance of the ith class ( $S_{B_{i}}$ ). Substitute $S_{B_{i}}$ into Equation (1) as follows: $\begin{matrix} (4) & {(m_{i} - m)}^{2} = W^{T} S_{B i} W \end{matrix}$

The total between-class variance is calculated as follows, ( $S_{B} = \sum_{i = 1}^{c} n_{i} S_{B_{i}}$ ). Figure 1 (step (D)) shows first how the between-class matrix of the first class ( $S_{B_{1}}$ ) is calculated and then how the total between-class matrix ( $S_{B}$ ) is then calculated by adding all the between-class matrices of all classes.

2.3. Calculating the within-class variance (

S_{W}

)

The within-class variance of the ith class ( $S_{W_{i}}$ ) represents the difference between the mean and the samples of that class. LDA technique searches for a lower-dimensional space, which is used to minimize the difference between the projected mean ( $m_{i}$ ) and the projected samples of each class ( $W^{T} x_{i}$ ), or simply minimizes the within-class variance [36,83]. The within-class variance of each class ( $S_{W_{j}}$ ) is calculated as in Equation (5). $\begin{array}{l} \sum_{x_{i} \in ω_{j}, j = 1, \dots, c} {(W^{T} x_{i} - m_{j})}^{2} \\ = \sum_{x_{i} \in ω_{j}, j = 1, \dots, c} {(W^{T} x_{i j} - W^{T} μ_{j})}^{2} \\ = \sum_{x_{i} \in ω_{j}, j = 1, \dots, c} W^{T} {(x_{i j} - μ_{j})}^{2} W \\ = \sum_{x_{i} \in ω_{j}, j = 1, \dots, c} W^{T} (x_{i j} - μ_{j}) {(x_{i j} - μ_{j})}^{T} W \\ (5) & = \sum_{x_{i} \in ω_{j}, j = 1, \dots, c} W^{T} S_{W_{j}} W \end{array}$

From Equation (5), the within-class variance for each class can be calculated as follows, $S_{W_{j}} = d_{j}^{T} * d_{j} = \sum_{i = 1}^{n_{j}} (x_{i j} - μ_{j}) {(x_{i j} - μ_{j})}^{T}$ , where $x_{i j}$ represents the ith sample in the jth class as shown in Fig. 1 (step (E), (F)), and $d_{j}$ is the centering data of the jth class, i.e. $d_{j} = ω_{j} - μ_{j} = {x_{i}}_{i = 1}^{n_{j}} - μ_{j}$ . Moreover, step (F) in the figure illustrates how the within-class variance of the first class ( $S_{W_{1}}$ ) in our example is calculated. The total within-class variance represents the sum of all within-class matrices of all classes (see Fig. 1 (step (F))), and it can be calculated as in Equation (6). $\begin{array}{rcl} S_{W} & = & \sum_{i = 1}^{3} S_{W_{i}} \\ = & \sum_{x_{i} \in ω_{1}} (x_{i} - μ_{1}) {(x_{i} - μ_{1})}^{T} \\ + \sum_{x_{i} \in ω_{2}} (x_{i} - μ_{2}) {(x_{i} - μ_{2})}^{T} \\ (6) & + \sum_{x_{i} \in ω_{3}} (x_{i} - μ_{3}) {(x_{i} - μ_{3})}^{T} \end{array}$

2.4. Constructing the lower dimensional space

After calculating the between-class variance ( $S_{B}$ ) and within-class variance ( $S_{W}$ ), the transformation matrix (W) of the LDA technique can be calculated as in Equation (7), which is called Fisher’s criterion. This formula can be reformulated as in Equation (8). $\begin{array}{l} (7) & arg max_{W} \frac{W^{T} S_{B} W}{W^{T} S_{W} W} \\ (8) & S_{W} W = λ S_{B} W \end{array}$ where λ represents the eigenvalues of the transformation matrix (W). The solution of this problem can be obtained by calculating the eigenvalues ( $λ = {λ_{1}, λ_{2}, \dots, λ_{M}}$ ) and eigenvectors ( $V = {v_{1}, v_{2}, \dots, v_{M}}$ ) of $W = S_{W}^{- 1} S_{B}$ , if $S_{W}$ is non-singular [36,81,83].

The eigenvalues are scalar values, while the eigenvectors are non-zero vectors, which satisfies the Equation (8) and provides us with the information about the LDA space. The eigenvectors represent the directions of the new space, and the corresponding eigenvalues represent the scaling factor, length, or the magnitude of the eigenvectors [34,59]. Thus, each eigenvector represents one axis of the LDA space, and the associated eigenvalue represents the robustness of this eigenvector. The robustness of the eigenvector reflects its ability to discriminate between different classes, i.e. increase the between-class variance, and decreases the within-class variance of each class; hence meets the LDA goal. Thus, the eigenvectors with the k highest eigenvalues are used to construct a lower dimensional space ( $V_{k}$ ), while the other eigenvectors ( ${v_{k + 1}, v_{k + 2}, v_{M}}$ ) are neglected as shown in Fig. 1 (step (G)).

Figure 2 shows the lower dimensional space of the LDA technique, which is calculated as in Fig. 1 (step (G)). As shown, the dimension of the original data matrix ( $X \in R^{N \times M}$ ) is reduced by projecting it onto the lower dimensional space of LDA ( $V_{k} \in R^{M \times k}$ ) as denoted in Equation (9) [81]. The dimension of the data after projection is k; hence, $M - k$ features are ignored or deleted from each sample. Thus, each sample ( $x_{i}$ ) which was represented as a point a M-dimensional space will be represented in a k-dimensional space by projecting it onto the lower dimensional space ( $V_{k}$ ) as follows, $y_{i} = x_{i} V_{k}$ . $\begin{matrix} (9) & Y = X V_{k} \end{matrix}$

Figure 3 shows a comparison between two lower-dimensional sub-spaces. In this figure, the original data which consists of three classes as in our example are plotted. Each class has five samples, and all samples are represented by two features only ( $x_{i} \in R^{2}$ ) to be visualized. Thus, each sample is represented as a point in two-dimensional space. The transformation matrix ( $W (2 \times 2)$ ) is calculated using the steps in Section 2.2, 2.3, and 2.4. The eigenvalues ( $λ_{1} and λ_{2}$ ) and eigenvectors (i.e. sub-spaces) ( $V = {v_{1}, v_{2}}$ ) of W are then calculated. Thus, there are two eigenvectors or sub-spaces. A comparison between the two lower-dimensional sub-spaces shows the following notices:

First, the separation distance between different classes when the data are projected on the first eigenvector ( $v_{1}$ ) is much greater than when the data are projected on the second eigenvector ( $v_{2}$ ). As shown in the figure, the three classes are efficiently discriminated when the data are projected on $v_{1}$ . Moreover, the distance between the means of the first and second classes ( $m_{1} - m_{2}$ ) when the original data are projected on $v_{1}$ is much greater than when the data are projected on $v_{2}$ , which reflects that the first eigenvector discriminates the three classes better than the second one.

Second, the within-class variance when the data are projected on $v_{1}$ is much smaller than when it projected on $v_{2}$ . For example, $S_{W_{1}}$ when the data are projected on $v_{1}$ is much smaller than when the data are projected on $v_{2}$ . Thus, projecting the data on $v_{1}$ minimizes the within-class variance much better than $v_{2}$ .

From these two notes, we conclude that the first eigenvector meets the goal of the lower-dimensional space of the LDA technique than the second eigenvector; hence, it is selected to construct a lower-dimensional space.

Fig. 3.

A visualized comparison between the two lower-dimensional sub-spaces which are calculated using three different classes.

2.5. Class-dependent vs. class-independent methods

The aim of the two methods of the LDA is to calculate the LDA space. In the class-dependent LDA, one separate lower dimensional space is calculated for each class as follows, $W_{i} = S_{W_{i}}^{- 1} S_{B}$ , where $W_{i}$ represents the transformation matrix for the ith class. Thus, eigenvalues and eigenvectors are calculated for each transformation matrix separately. Hence, the samples of each class are projected on their corresponding eigenvectors. On the other hand, in the class-independent method, one lower dimensional space is calculated for all classes. Thus, the transformation matrix is calculated for all classes, and the samples of all classes are projected on the selected eigenvectors [1].

Algorithm 1

Linear Discriminant Analysis (LDA): Class-Independent

Algorithm 2

Linear Discriminant Analysis (LDA): Class-Dependent

2.6. LDA algorithm

In this section the detailed steps of the algorithms of the two LDA methods are presented. As shown in Algorithms 1 and 2, the first four steps in both algorithms are the same. Table 1 shows the notations which are used in the two algorithms.

2.7. Computational complexity of LDA

In this section, the computational complexity for LDA is analyzed. The computational complexity for the first four steps, common in both class-dependent and class-independent methods, are computed as follows. As illustrated in Algorithm 1, in step (2), to calculate the mean of the ith class, there are $n_{i} M$ additions and M divisions, i.e., in total, there are $(N M + c M)$ operations. In step (3), there are $N M$ additions and M divisions, i.e., there are $(N M + M)$ operations. The computational complexity of the fourth step is $c (M + M^{2} + M^{2})$ , where M is for $μ_{i} - μ$ , $M^{2}$ for $(μ_{i} - μ) {(μ_{i} - μ)}^{T}$ , and the last $M^{2}$ is for the multiplication between $n_{i}$ and the matrix $(μ_{i} - μ) {(μ_{i} - μ)}^{T}$ . In the fifth step, there are $N (M + M^{2})$ operations, where M is for $(x_{i j} - μ_{j})$ and $M^{2}$ is for $(x_{i j} - μ_{j}) {(x_{i j} - μ_{j})}^{T}$ . In the sixth step, there are $M^{3}$ operations to calculate $S_{W}^{- 1}$ , $M^{3}$ is for the multiplication between $S_{W}^{- 1}$ and $S_{B}$ , and $M^{3}$ to calculate the eigenvalues and eigenvectors. Thus, in class-independent method, the computational complexity is $O (N M^{2})$ if $N > M$ ; otherwise, the complexity is $O (M^{3})$ .

In Algorithm 2, the number of operations to calculate the within-class variance for each class $S_{W_{j}}$ in the sixth step is $n_{j} (M + M^{2})$ , and to calculate $S_{W}$ , $N (M + M^{2})$ operations are needed. Hence, calculating the within-class variance for both LDA methods are the same. In the seventh step and eighth, there are $M^{3}$ operations for the inverse, $M^{3}$ for the multiplication of $S_{W_{i}}^{- 1} S_{B}$ , and $M^{3}$ for calculating eigenvalues and eigenvectors. These two steps are repeated for each class which increases the complexity of the class-dependent algorithm. Totally, the computational complexity of the class-dependent algorithm is $O (N M^{2})$ if $N > M$ ; otherwise, the complexity is $O (c M^{3})$ . Hence, the class-dependent method needs computations more than class-independent method.

Table 1
Notation

Notation Description

X Data matrix

N Total number of samples in X

W Transformation matrix

$n_{i}$ Number of samples in $ω_{i}$

$μ_{i}$ The mean of the ith class

μ Total or global mean of all samples

$S_{W i}$ Within-class variance or scatter matrix of the ith class ( $ω_{i}$ )

$S_{B i}$ Between-class variance of the ith class ( $ω_{i}$ )

V Eigenvectors of W

$V_{i}$ ith eigenvector

$x_{i j}$ The ith sample in the jth class

k The dimension of the lower dimensional space ( $V_{k}$ )

$x_{i}$ ith sample

M Dimension of X or the number of features of X

$V_{k}$ The lower dimensional space

c Total number of classes

$m_{i}$ The mean of the ith class after projection

m The total mean of all classes after projection

$S_{W}$ Within-class variance

$S_{B}$ Between-class variance

λ Eigenvalue matrix

$λ_{i}$ ith eigenvalue

Y Projection of the original data

$ω_{i}$ ith Class

Notation	Description
X	Data matrix
N	Total number of samples in X
W	Transformation matrix
$n_{i}$	Number of samples in $ω_{i}$
$μ_{i}$	The mean of the ith class
μ	Total or global mean of all samples
$S_{W i}$	Within-class variance or scatter matrix of the ith class ( $ω_{i}$ )
$S_{B i}$	Between-class variance of the ith class ( $ω_{i}$ )
V	Eigenvectors of W
$V_{i}$	ith eigenvector
$x_{i j}$	The ith sample in the jth class
k	The dimension of the lower dimensional space ( $V_{k}$ )
$x_{i}$	ith sample
M	Dimension of X or the number of features of X
$V_{k}$	The lower dimensional space
c	Total number of classes
$m_{i}$	The mean of the ith class after projection
m	The total mean of all classes after projection
$S_{W}$	Within-class variance
$S_{B}$	Between-class variance
λ	Eigenvalue matrix
$λ_{i}$	ith eigenvalue
Y	Projection of the original data
$ω_{i}$	ith Class

In our case, we assumed that there are 40 classes and each class has ten samples. Each sample is represented by 4096 features ( $M > N$ ). Thus, the computational complexity of the class-independent method is $O (M^{3}) = 4096^{3}$ , while the class-dependent method needs $O (c M^{3}) = 40 \times 4096^{3}$ .

3. Numerical examples

In this section, two numerical examples will be presented. The two numerical examples explain the steps to calculate the LDA space and how the LDA technique is used to discriminate between only two different classes. In the first example, the lower-dimensional space is calculated using the class-independent method, while in the second example, the class-dependent method is used. Moreover, a comparison between the lower dimensional spaces of each method is presented. In all numerical examples, the numbers are rounded up to the nearest hundredths (i.e. only two digits after the decimal point are displayed).

The first four steps of both class-independent and class-dependent methods are common as illustrated in Algorithms 1 and 2. Thus, in this section, we show how these steps are calculated.

Given two different classes, $ω_{1} (5 \times 2)$ and $ω_{2} (6 \times 2)$ have ( $n_{1} = 5$ ) and ( $n_{2} = 6$ ) samples, respectively. Each sample in both classes is represented by two features (i.e. $M = 2$ ) as follows: $\begin{array}{l} (17) & \begin{aligned} ω_{1} = [\begin{matrix} 1.00 & 2.00 \\ 2.00 & 3.00 \\ 3.00 & 3.00 \\ 4.00 & 5.00 \\ 5.00 & 5.00 \end{matrix}] and \\ ω_{2} = [\begin{matrix} 4.00 & 2.00 \\ 5.00 & 0.00 \\ 5.00 & 2.00 \\ 3.00 & 2.00 \\ 5.00 & 3.00 \\ 6.00 & 3.00 \end{matrix}] \end{aligned} \end{array}$

To calculate the lower dimensional space using LDA, first the mean of each class $μ_{j}$ is calculated. The total mean $μ (1 \times 2)$ is then calculated, which represents the mean of all means of all classes. The values of the mean of each class and the total mean are shown below, $\begin{array}{l} (18) & \begin{aligned} μ_{1} = [\begin{matrix} 3.00 & 3.60 \end{matrix}], \\ μ_{2} = [\begin{matrix} 4.67 & 2.00 \end{matrix}], and \\ μ = [\begin{matrix} \frac{5}{11} μ_{1} & \frac{6}{11} μ_{2} \end{matrix}] = [\begin{matrix} 3.91 & 2.727 \end{matrix}] \end{aligned} \end{array}$

The between-class variance of each class ( $S_{B_{i}} (2 \times 2)$ ) and the total between-class variance ( $S_{B} (2 \times 2)$ ) are calculated. The values of the between-class variance of the first class ( $S_{B_{1}}$ ) is equal to, $\begin{array}{rcl} S_{B_{1}} & = & n_{1} {(μ_{1} - μ)}^{T} (μ_{1} - μ) \\ = & 5 {[\begin{matrix} - 0.91 & 0.87 \end{matrix}]}^{T} [\begin{matrix} - 0.91 & 0.87 \end{matrix}] \\ (19) & = & [\begin{matrix} 4.13 & - 3.97 \\ - 3.97 & 3.81 \end{matrix}] \end{array}$

Similarly, $S_{B_{2}}$ is calculated as follows: $\begin{matrix} (20) & \begin{matrix} S_{B_{2}} = [\begin{matrix} 3.44 & - 3.31 \\ - 3.31 & 3.17 \end{matrix}] \end{matrix} \end{matrix}$

The total between-class variance is calculated a follows: $\begin{array}{rcl} S_{B} & = & S_{B_{1}} + S_{B_{2}} \\ = & [\begin{matrix} 4.13 & - 3.97 \\ - 3.97 & 3.81 \end{matrix}] \\ + [\begin{matrix} 3.44 & - 3.31 \\ - 3.31 & 3.17 \end{matrix}] \\ (21) & = & [\begin{matrix} 7.58 & - 7.27 \\ - 7.27 & 6.98 \end{matrix}] \end{array}$

To calculate the within-class matrix, first subtract the mean of each class from each sample in that class and this step is called mean-centering data and it is calculated as follows, $d_{i} = ω_{i} - μ_{i}$ , where $d_{i}$ represents centering data of the class $ω_{i}$ . The values of $d_{1} and d_{2}$ are as follows: $\begin{array}{l} (22) & \begin{aligned} d_{1} = [\begin{matrix} - 2.00 & - 1.60 \\ - 1.00 & - 0.60 \\ 0.00 & - 0.60 \\ 1.00 & 1.40 \\ 2.00 & 1.40 \end{matrix}] and \\ d_{2} = [\begin{matrix} - 0.67 & 0.00 \\ 0.33 & - 2.00 \\ 0.33 & 0.00 \\ - 1.67 & 0.00 \\ 0.33 & 1.00 \\ 1.33 & 1.00 \end{matrix}] \end{aligned} \end{array}$

In the next two subsections, two different methods are used to calculate the LDA space.

3.1. Class-independent method

In this section, the LDA space is calculated using the class-independent method. This method represents the standard method of LDA as in Algorithm 1.

After centring the data, the within-class variance for each class ( $S_{W_{i}} (2 \times 2)$ ) is calculated as follows, $S_{W_{j}} = d_{j}^{T} * d_{j} = \sum_{i = 1}^{n_{j}} {(x_{i j} - μ_{j})}^{T} (x_{i j} - μ_{j})$ , where $x_{i j}$ represents the ith sample in the jth class. The total within-class matrix ( $S_{W} (2 \times 2)$ ) is then calculated as follows, $S_{W} = \sum_{i = 1}^{c} S_{W_{i}}$ . The values of the within-class matrix for each class and the total within-class matrix are as follows: $\begin{array}{l} (23) & \begin{aligned} S_{W_{1}} = [\begin{matrix} 10.00 & 8.00 \\ 8.00 & 7.20 \end{matrix}], \\ S_{W_{2}} = [\begin{matrix} 5.33 & 1.00 \\ 1.00 & 6.00 \end{matrix}], \\ S_{W} = [\begin{matrix} 15.33 & 9.00 \\ 9.00 & 13.20 \end{matrix}] \end{aligned} \end{array}$ The transformation matrix (W) in the class-independent method can be obtained as follows, $W = S_{W}^{- 1} S_{B}$ , and the values of ( $S_{W}^{- 1}$ ) and (W) are as follows: $\begin{array}{l} (24) & \begin{aligned} S_{W}^{- 1} = [\begin{matrix} 0.11 & - 0.07 \\ - 0.07 & 0.13 \end{matrix}] and \\ W = [\begin{matrix} 1.36 & - 1.31 \\ - 1.48 & 1.42 \end{matrix}] \end{aligned} \end{array}$

The eigenvalues ( $λ (2 \times 2)$ ) and eigenvectors ( $V (2 \times 2)$ ) of W are then calculated as follows: $\begin{array}{l} (25) & \begin{aligned} λ = [\begin{matrix} 0.00 & 0.00 \\ 0.00 & 2.78 \end{matrix}] and \\ V = [\begin{matrix} - 0.69 & 0.68 \\ - 0.72 & - 0.74 \end{matrix}] \end{aligned} \end{array}$

From the above results it can be noticed that, the second eigenvector ( $V_{2}$ ) has corresponding eigenvalue more than the first one ( $V_{1}$ ), which reflects that, the second eigenvector is more robust than the first one; hence, it is selected to construct the lower dimensional space. The original data is projected on the lower dimensional space, as follows, $y_{i} = ω_{i} V_{2}$ , where $y_{i} (n_{i} \times 1)$ represents the data after projection of the ith class, and its values will be as follows: $\begin{array}{rcl} y_{1} & = & ω_{1} V_{2} \\ = & [\begin{matrix} 1.00 & 2.00 \\ 2.00 & 3.00 \\ 3.00 & 3.00 \\ 4.00 & 5.00 \\ 5.00 & 5.00 \end{matrix}] [\begin{matrix} 0.68 \\ - 0.74 \end{matrix}] \\ (26) & = & [\begin{matrix} - 0.79 \\ - 0.85 \\ - 0.18 \\ - 0.97 \\ - 0.29 \end{matrix}] \end{array}$

Similarly, $y_{2}$ is as follows: $\begin{matrix} (27) & y_{2} = ω_{2} V_{2} = [\begin{matrix} 1.24 \\ 3.39 \\ 1.92 \\ 0.56 \\ 1.18 \\ 1.86 \end{matrix}] \end{matrix}$

Fig. 4.

Probability density function of the projected data of the first example, (a) the projected data on $V_{1}$ , (b) the projected data on $V_{2}$ .

Figure 4 illustrates a probability density function (pdf) graph of the projected data ( $y_{i}$ ) on the two eigenvectors ( $V_{1} and V_{2}$ ). A comparison of the two eigenvectors reveals the following:

The data of each class is completely discriminated when it is projected on the second eigenvector (see Fig. 4(b)) than the first one (see Fig. 4(a). In other words, the second eigenvector maximizes the between-class variance more than the first one.

The within-class variance (i.e. the variance between the same class samples) of the two classes are minimized when the data are projected on the second eigenvector. As shown in Fig. 4(b), the within-class variance of the first class is small compared with Fig. 4(a).

3.2. Class-dependent method

In this section, the LDA space is calculated using the class-dependent method. As mentioned in Section 2.5, the class-dependent method aims to calculate a separate transformation matrix ( $W_{i}$ ) for each class.

The within-class variance for each class ( $S_{W_{i}} (2 \times 2)$ ) is calculated as in class-independent method. The transformation matrix ( $W_{i}$ ) for each class is then calculated as follows, $W_{i} = S_{W_{i}}^{- 1} S_{B}$ . The values of the two transformation matrices ( $W_{1}$ and $W_{2}$ ) will be as follows: $\begin{array}{rcl} W_{1} & = & S_{W_{1}}^{- 1} S_{B} \\ = & {[\begin{matrix} 10.00 & 8.00 \\ 8.00 & 7.20 \end{matrix}]}^{- 1} [\begin{matrix} 7.58 & - 7.27 \\ - 7.27 & 6.98 \end{matrix}] \\ = & [\begin{matrix} 0.90 & - 1.00 \\ - 1.00 & 1.25 \end{matrix}] [\begin{matrix} 7.58 & - 7.27 \\ - 7.27 & 6.98 \end{matrix}] \\ (28) & = & [\begin{matrix} 14.09 & - 13.53 \\ - 16.67 & 16.00 \end{matrix}] \end{array}$

Similarly, $W_{2}$ is calculated as follows: $\begin{matrix} (29) & W_{2} = [\begin{matrix} 1.70 & - 1.63 \\ - 1.50 & 1.44 \end{matrix}] \end{matrix}$

The eigenvalues ( $λ_{i}$ ) and eigenvectors ( $V_{i}$ ) for each transformation matrix ( $W_{i}$ ) are calculated, and the values of the eigenvalues and eigenvectors are shown below. $\begin{array}{l} (30) & \begin{aligned} λ_{ω_{1}} = [\begin{matrix} 0.00 & 0.00 \\ 0.00 & 30.01 \end{matrix}] and \\ V_{ω_{1}} = [\begin{matrix} - 0.69 & 0.65 \\ - 0.72 & - 0.76 \end{matrix}] \end{aligned} \\ (31) & \begin{aligned} λ_{ω_{2}} = [\begin{matrix} 3.14 & 0.00 \\ 0.00 & 0.00 \end{matrix}] and \\ V_{ω_{2}} = [\begin{matrix} 0.75 & 0.69 \\ - 0.66 & 0.72 \end{matrix}] \end{aligned} \end{array}$ where $λ_{ω_{i}}$ and $V_{ω_{i}}$ represent the eigenvalues and eigenvectors of the ith class, respectively.

From the results shown (above) it can be seen that, the second eigenvector of the first class ( $V_{ω_{1}}^{{2}}$ ) has corresponding eigenvalue more than the first one; thus, the second eigenvector is used as a lower dimensional space for the first class as follows, $y_{1} = ω_{1} * V_{ω_{1}}^{{2}}$ , where $y_{1}$ represents the projection of the samples of the first class. While, the first eigenvector in the second class ( $V_{ω_{2}}^{{1}}$ ) has corresponding eigenvalue more than the second one. Thus, $V_{ω_{2}}^{{1}}$ is used to project the data of the second class as follows, $y_{2} = ω_{2} * V_{ω_{2}}^{{1}}$ , where $y_{2}$ represents the projection of the samples of the second class. The values of $y_{1}$ and $y_{2}$ will be as follows: $\begin{matrix} (32) & y_{1} = [\begin{matrix} - 0.88 \\ - 1.00 \\ - 0.35 \\ - 1.24 \\ - 0.59 \end{matrix}] and y_{2} = [\begin{matrix} 1.68 \\ 3.76 \\ 2.43 \\ 0.93 \\ 1.77 \\ 2.53 \end{matrix}] \end{matrix}$

Figure 5 shows a pdf graph of the projected data (i.e. $y_{1}$ and $y_{2}$ ) on the two eigenvectors ( $V_{ω_{1}}^{{2}} and V_{ω_{2}}^{{1}}$ ) and a number of findings are revealed the following:

First, the projection data of the two classes are efficiently discriminated.

Second, the within-class variance of the projected samples is lower than the within-class variance of the original samples.

Fig. 5.

Probability density function (pdf) of the projected data using class-dependent method, the first class is projected on $V_{ω_{1}}^{{2}}$ , while the second class is projected on $V_{ω_{2}}^{{1}}$ .

3.3. Discussion

In these two numerical examples, the LDA space is calculated using class-dependent and class-independent methods.

Figure 6 shows a further explanation of the two methods as following:

Class-Independent: As shown from the figure, there are two eigenvectors, $V_{1}$ (dotted black line) and $V_{2}$ (solid black line). The differences between the two eigenvectors are as follows:

The projected data on the second eigenvector ( $V_{2}$ ) which has the highest corresponding eigenvalue will discriminate the data of the two classes better than the first eigenvector. As shown in the figure, the distance between the projected means $m_{1} - m_{2}$ which represents $S_{B}$ , increased when the data are projected on $V_{2}$ than $V_{1}$ .

The second eigenvector decreases the within-class variance much better than the first eigenvector. Figure 6 illustrates that the within-class variance of the first class ( $S_{W_{1}}$ ) was much smaller when it was projected on $V_{2}$ than $V_{1}$ .

As a result of the above two findings, $V_{2}$ is used to construct the LDA space.

Class-Dependent: As shown from the figure, there are two eigenvectors, $V_{ω_{1}}^{{2}}$ (red line) and $V_{ω_{2}}^{{1}}$ (blue line), which represent the first and second classes, respectively. The differences between the two eigenvectors are as following:

Projecting the original data on the two eigenvectors discriminates between the two classes. As shown in the figure, the distance between the projected means $m_{1} - m_{2}$ is larger than the distance between the original means $μ_{1} - μ_{2}$ .

The within-class variance of each class is decreased. For example, the within-class variance of the first class ( $S_{W_{1}}$ ) is decreased when it is projected on its corresponding eigenvector.

As a result of the above two findings, $V_{ω_{1}}^{{2}}$ and $V_{ω_{2}}^{{1}}$ are used to construct the LDA space.

Class-Dependent vs. Class-Independent: The two LDA methods are used to calculate the LDA space, but a class-dependent method calculates separate lower dimensional spaces for each class which has two main limitations: (1) it needs more CPU time and calculations more than class-independent method; (2) it may lead to SSS problem because the number of samples in each class affects the singularity of $S_{W_{i}}$ .2

²
SSS problem will be explained in Section 4.2.

These findings reveal that the standard LDA technique used the class-independent method rather than using the class-dependent method.

Fig. 6.

Illustration of the example of the two different methods of LDA methods. The blue and red lines represent the first and second eigenvectors of the class-dependent approach, respectively, while the solid and dotted black lines represent the second and first eigenvectors of class-independent approach, respectively.

4. Main problems of LDA

Although LDA is one of the most common data reduction techniques, it suffers from two main problems: the Small Sample Size (SSS) and linearity problems. In the next two subsections, these two problems will be explained, and some of the state-of-the-art solutions are highlighted.

4.1. Linearity problem

LDA technique is used to find a linear transformation that discriminates between different classes. However, if the classes are non-linearly separable, LDA can not find a lower dimensional space. In other words, LDA fails to find the LDA space when the discriminatory information are not in the means of classes. Figure 7 shows how the discriminatory information does not exist in the mean, but in the variance of the data. This is because the means of the two classes are equal. The mathematical interpretation for this problem is as follows: if the means of the classes are approximately equal, so the $S_{B}$ and W will be zero. Hence, the LDA space cannot be calculated.

One of the solutions of this problem is based on the transformation concept, which is known as a kernel methods or functions [3,50]. Figure 7 illustrates how the transformation is used to map the original data into a higher dimensional space; hence, the data will be linearly separable, and the LDA technique can find the lower dimensional space in the new space. Figure 8 graphically and mathematically shows how two non-separable classes in one-dimensional space are transformed into a two-dimensional space (i.e. higher dimensional space); thus, allowing linear separation.

The kernel idea is applied in Support Vector Machine (SVM) [49,66,69] Support Vector Regression (SVR) [58], PCA [51], and LDA [50]. Let ϕ represents a nonlinear mapping to the new feature space $Z$ . The transformation matrix (W) in the new feature space ( $Z$ ) is calculated as in Equation (33).

$\begin{matrix} (33) & F (W) = max | \frac{W^{T} S_{B}^{ϕ} W}{W^{T} S_{W}^{ϕ} W} | \end{matrix}$ where W is a transformation matrix and $Z$ is the new feature space. The between-class matrix ( $S_{B}^{ϕ}$ ) and the within-class matrix ( $S_{W}^{ϕ}$ ) are defined as follows: $\begin{array}{l} (34) & S_{B}^{ϕ} = \sum_{i = 1}^{c} n_{i} (μ_{i}^{ϕ} - μ^{ϕ}) {(μ_{i}^{ϕ} - μ^{ϕ})}^{T} \\ (35) & \begin{matrix} S_{W}^{ϕ} = & \sum_{j = 1}^{c} \sum_{i = 1}^{n_{j}} (ϕ {x_{i j}} - μ_{j}^{ϕ}) \\ \times {(ϕ {x_{i j}} - μ_{j}^{ϕ})}^{T} \end{matrix} \end{array}$ where $μ_{i}^{ϕ} = \frac{1}{n_{i}} \sum_{i = 1}^{n_{i}} ϕ {x_{i}}$ and $μ^{ϕ} = \frac{1}{N} \sum_{i = 1}^{N} ϕ {x_{i}} = \sum_{i = 1}^{c} \frac{n_{i}}{N} μ_{i}^{ϕ}$ .

Fig. 7.

Two examples of two non-linearly separable classes, top panel shows how the two classes are non-separable, while the bottom shows how the transformation solves this problem and the two classes are linearly separable.

Thus, in kernel LDA, all samples are transformed non-linearly into a new space $Z$ using the function ϕ. In other words, the ϕ function is used to map the original features into $Z$ space by creating a nonlinear combination of the original samples using a dot-products of it [3]. There are many types of kernel functions to achieve this aim. Examples of these function include Gaussian or Radial Basis Function (RBF), $K (x_{i}, x_{j}) = exp (- ‖ x_{i} - x_{j} ‖^{2} / 2 σ^{2})$ , where σ is a positive parameter, and the polynomial kernel of degree d, $K (x_{i}, x_{j}) = {(⟨ x_{i}, x_{j} ⟩ + c)}^{d}$ , [3,29,51,72].

Fig. 8.

Example of kernel functions, the samples lie on the top panel (X) which are represented by a line (i.e. one-dimensional space) are non-linearly separable, where the samples lie on the bottom panel (Z) which are generated from mapping the samples of the top space are linearly separable.

4.2. Small sample size problem

4.2.1. Problem definition

Singularity, Small Sample Size (SSS), or under-sampled problem is one of the big problems of LDA technique. This problem results from high-dimensional pattern classification tasks or a low number of training samples available for each class compared with the dimensionality of the sample space [30,38,82,85].

The SSS problem occurs when the $S_{W}$ is singular.3

³
A matrix is singular if it is square, does not have a matrix inverse, the determinant is zeros; hence, not all columns and rows are independent.

The upper bound of the rank4

⁴

The rank of the matrix represents the number of linearly independent rows or columns.

S_{W}

N - c

, while the dimension of

S_{W}

M \times M

[17,38]. Thus, in most cases

M ≫ N - c

which leads to SSS problem. For example, in face recognition applications, the size of the face image my reach to

100 \times 100 = 10, 000

pixels, which represent high-dimensional features and it leads to a singularity problem.

4.2.2. Common solutions to SSS problem:

There are many studies that proposed many solutions for this problem; each has its advantages and drawbacks.

Regularization (RLDA): In regularization method, the identity matrix is scaled by multiplying it by a regularization parameter ( $η > 0$ ) and adding it to the within-class matrix to make it non-singular [18,38,45,82]. Thus, the diagonal components of the within-class matrix are biased as follows, $S_{W} = S_{W} + η I$ . However, choosing the value of the regularization parameter requires more tuning and a poor choice for this parameter can degrade the performance of the method [38,45]. Another problem of this method is that the parameter η is just added to perform the inverse of $S_{W}$ and has no clear mathematical interpretation [38,57].

Sub-space: In this method, a non-singular intermediate space is obtained to reduce the dimension of the original data to be equal to the rank of $S_{W}$ ; hence, $S_{W}$ becomes full-rank,5

⁵
A is a full-rank matrix if all columns and rows of the matrix are independent, (i.e. $rank (A) = # rows = # cols$ ) [23].

and then

S_{W}

can be inverted. For example, Belhumeur et al. [4] used PCA, to reduce the dimensions of the original space to be equal to

N - c

(i.e. the upper bound of the rank of

S_{W}

). However, as reported in [22], losing some discriminant information is a common drawback associated with the use of this method.

Null Space: There are many studies proposed to remove the null space of $S_{W}$ to make $S_{W}$ full-rank; hence, invertible. The drawback of this method is that more discriminant information is lost when the null space of $S_{W}$ is removed, which has a negative impact on how the lower dimensional space satisfies the LDA goal [83].

Four different variants of the LDA technique that are used to solve the SSS problem are introduced as follows:

PCA+LDA technique. In this technique, the original d-dimensional features are first reduced to h-dimensional feature space using PCA, and then the LDA is used to further reduce the features to k-dimensions. The PCA is used in this technique to reduce the dimensions to make the rank of $S_{W}$ is $N - c$ as reported in [4]; hence, the SSS problem is addressed. However, the PCA neglects some discriminant information, which may reduce the classification performance [57,60].

Direct LDA technique. Direct LDA (DLDA) is one of the well-known techniques that are used to solve the SSS problem. This technique has two main steps [83]. In the first step, the transformation matrix, W, is computed to transform the training data to the range space of $S_{B}$ . In the second step, the dimensionality of the transformed data is further transformed using some regulating matrices as in Algorithm 4. The benefit of the DLDA is that there is no discriminative features are neglected as in PCA+LDA technique [83].

Regularized LDA technique. In the Regularized LDA (RLDA), a small perturbation is add to the $S_{W}$ matrix to make it non-singular as mentioned in [18]. This regularization can be applied as follows: $\begin{matrix} (36) & {(S_{W} + η I)}^{- 1} S_{B} w_{i} = λ_{i} w_{i} \end{matrix}$ where η represents a regularization parameter. The diagonal components of the $S_{W}$ are biased by adding this small perturbation [13,18]. However, the regularization parameter need to be tuned and poor choice of it can degrade the generalization performance [57].

Null LDA technique. The aim of the NLDA technique is to find the orientation matrix W, and this can be achieved using two steps. In the first step, the range space of the $S_{W}$ is neglected, and the data are projected only on the null space of $S_{W}$ as follows, $S_{W} W = 0$ . In the second step, the aim is to search for W that satisfies $S_{B} W = 0$ and maximizes $| W^{T} S_{B} W |$ . The higher dimensionality of the feature space may lead to computational problems. This problem can be solved by (1) using the PCA technique as a pre-processing step, i.e. before applying the NLDA technique, to reduce the dimension of feature space to be $N - 1$ ; by removing the null space of $S_{T} = S_{B} + S_{W}$ [57], (2) using the PCA technique before the second step of the NLDA technique [54]. Mathematically, in the Null LDA (NLDA) technique, the h column vectors of the transformation matrix $W = [w_{1}, w_{2}, \dots, w_{h}]$ are taken to be the null space of the $S_{W}$ as follows, $w_{i}^{T} S_{W} w_{i} = 0, \forall i = 1, \dots, h$ , where $w_{i}^{T} S_{B} w_{i} \neq 0$ . Hence, $M - (N - c)$ linearly independent vectors are used to form a new orientation matrix, which is used to maximize $| W^{T} S_{B} W |$ subject to the constraint $| W^{T} S_{W} W | = 0$ as in Equation (37). $\begin{matrix} (37) & W = arg max_{| W^{T} S_{W} W | = 0} | W^{T} S_{B} W | \end{matrix}$

5. Applications of the LDA technique

In many applications, due to the high number of features or dimensionality, the LDA technique have been used. Some of the applications of the LDA technique and its variants are described as follows:

5.1. Biometrics applications

Biometrics systems have two main steps, namely, feature extraction (including pre-processing steps) and recognition. In the first step, the features are extracted from the collected data, e.g. face images, and in the second step, the unknown samples, e.g. unknown face image, is identified/verified. The LDA technique and its variants have been applied in this application. For example, in [10,20,41,68,75,83], the LDA technique have been applied on face recognition. Moreover, the LDA technique was used in Ear [84], fingerprint [44], gait [5], and speech [24] applications. In addition, the LDA technique was used with animal biometrics as in [19,65].

5.2. Agriculture applications

In agriculture applications, an unknown sample can be classified into a pre-defined species using computational models [64]. In this application, different variants of the LDA technique was used to reduce the dimension of the collected features as in [9,21,26,46,63,64].

5.3. Medical applications

In medical applications, the data such as the DNA microarray data consists of a large number of features or dimensions. Due to this high dimensionality, the computational models need more time to train their models, which may be infeasible and expensive. Moreover, this high dimensionality reduces the classification performance of the computational model and increases its complexity. This problem can be solved using LDA technique to construct a new set of features from a large number of original features. There are many papers have been used LDA in medical applications [8,16,39,52–55].

6. Packages

In this section, some of the available packages that are used to compute the space of LDA variants. For example, WEKA6

⁶
http:/www.cs.waikato.ac.nz/ml/weka/

is a well-known Java-based data mining tool with open source machine learning software such as classification, association rules, regression, pre-processing, clustering, and visualization. In WEKA, the machine learning algorithms can be applied directly on the dataset or called from person’s Java code. XLSTAT7

⁷

http://www.xlstat.com/en/

is another data analysis and statistical package for Microsoft Excel that has a wide variety of dimensionality reduction algorithms including LDA. dChip8

⁸

https://sites.google.com/site/dchipsoft/home

package is also used for visualization of gene expression and SNP microarray including some data analysis algorithms such as LDA, clustering, and PCA. LDA-SSS9

⁹

http://www.staff.usp.ac.fj/sharma_al/index.htm

is a Matlab package, and it contains several algorithms related to the LDA techniques and its variants such as DLDA, PCA+LDA, and NLDA. MASS10

¹⁰

http://www.statmethods.net/advstats/discriminant.html

package is based on R, and it has functions that are used to perform linear and quadratic discriminant function analysis. Dimensionality reduction11

¹¹

http://www.public.asu.edu/*jye02/Software/index.html

package is mainly written in Matlab, and it has a number of dimensionality reduction techniques such as ULDA, QLDA, and KDA. DTREG12

¹²

http://www.dtreg.com/index.htm

is a software package that is used for medical data and modeling business, and it has several predictive modeling methods such as LDA, PCA, linear regression, and decision trees.

7. Experimental results and discussion

In this section, two experiments were conducted to illustrate: (1) how the LDA is used for different applications, (2) what is the relation between its parameter (Eigenvectors) and the accuracy of a classification problem, (3) when the SSS problem could appear and a method for solving it.

7.1. Experimental setup

This section gives an overview of the databases, the platform, and the machine specification used to conduct our experiments. Different biometric datasets were used in the experiments to show how the LDA using its parameter behaves with different data. These datasets are described as follows:

ORL dataset13

¹³
http://www.cam-orl.co.uk

face images dataset (Olivetti Research Laboratory, Cambridge) [48], which consists of 40 distinct individuals, was used. In this dataset, each individual has ten images taken at different times and varying light conditions. The size of each image is

92 \times 112

Yale dataset14

¹⁴

http://vision.ucsd.edu/content/yale-face-database

is another face images dataset which contains 165 grey scale images in GIF format of 15 individuals [78]. Each individual has 11 images in different expressions and configuration: center-light, happy, left-light, with glasses, normal, right-light, sad, sleepy, surprised, and a wink.

2D ear dataset (Carreira-Perpinan,1995)15

¹⁵

http://faculty.ucmerced.edu/mcarreira-perpinan/software.html

images dataset [7] was used. The ear data set consists of 17 distinct individuals. Six views of the left profile from each subject were taken under a uniform, diffuse lighting.

In all experiments, k-fold cross-validation tests have used. In k-fold cross-validation, the original samples of the dataset were randomly partitioned into k subsets of (approximately) equal size and the experiment is run k times. For each time, one subset was used as the testing set and the other $k - 1$ subsets were used as the training set. The average of the k results from the folds can then be calculated to produce a single estimation. In this study, the value of k was set to 10.

The images in all datasets resized to be $64 \times 64$ and $32 \times 32$ as shown in Table 2. Figure 9 shows samples of the used datasets and Table 2 shows a description of the datasets used in our experiments.

Fig. 9.

Samples of the first individual in: ORL face dataset (top row); Ear dataset (middle row), and Yale face dataset (bottom row).

Table 2

Dataset description

Dataset	Dimension (M)	No. of Samples (N)	No. of classes (c)
${ORL}_{64 \times 64}$	4096	400	40
${ORl}_{32 \times 32}$	1024	400	40
${Ear}_{64 \times 64}$	4096	102	17
${Ear}_{32 \times 32}$	1024	102	17
${Yale}_{64 \times 64}$	4096	165	15
${Yale}_{32 \times 32}$	1024	165	15

In all experiments, to show the effect of the LDA with its eigenvector parameter and its SSS problem on the classification accuracy, the Nearest Neighbour classifier was used. This classifier aims to classify the testing image by comparing its position in the LDA space with the positions of training images. Furthermore, class-independent LDA was used in all experiments. Moreover, Matlab Platform (R2013b) and using a PC with the following specifications: Intel(R) Core(TM) i5-2400 CPU @ 3.10 GHz and 4.00 GB RAM, under Windows 32-bit operating system were used in our experiments.

7.2. Experiment on LDA parameter (eigenvectors)

The aim of this experiment is to investigate the relation between the number of eigenvectors used in the LDA space, and the classification accuracy based on these eigenvectors and the required CPU time for this classification.

Fig. 10.

Accuracy and CPU time of the LDA techniques using different percentages of eigenvectors, (a) Accuracy (b) CPU time.

As explained earlier that the LDA space consists of k eigenvectors, which are sorted according to their robustness (i.e. their eigenvalues). The robustness of each eigenvector reflects its ability to discriminate between different classes. Thus, in this experiment, it will be checked whether increasing the number of eigenvectors would increase the total robustness of the constructed LDA space; hence, different classes could be well discriminated. Also, it will be tested whether increasing the number of eigenvectors would increase the dimension of the LDA space and the projected data; hence, CPU time increases. To investigate these issue, three datasets listed in Table 2 (i.e. ${ORL}_{32 \times 32}$ , ${Ear}_{32 \times 32}$ , ${Yale}_{32 \times 32}$ ), were used. Moreover, seven, four, and eight images from each subject in the ORL, ear, Yale datasets, respectively, are used in this experiment. The results of this experiment are presented in Fig. 10.

From Fig. 10 it can be noticed that the accuracy and CPU time are proportional with the number of eigenvectors which are used to construct the LDA space. Thus, the choice of using LDA in a specific application should consider a trade-off between these factors. Moreover, from Fig. 10(a), it can be remarked that when the number of eigenvectors used in computing the LDA space was increased, the classification accuracy was also increased to a specific extent after which the accuracy remains constant. As seen in Fig. 10(a), this extent differs from application to another. For example, the accuracy of the ear dataset remains constant when the percentage of the used eigenvectors is more than 10%. This was expected as the eigenvectors of the LDA space are sorted according to their robustness (see Section 2.6). Similarly, in ORL and Yale datasets the accuracy became approximately constant when the percentage of the used eigenvectors is more than 40%. In terms of CPU time, Fig. 10(b) shows the CPU time using different percentages of the eigenvectors. As shown, the CPU time increased dramatically when the number of eigenvectors increases.

Figure 11 shows the weights16

¹⁶

The weight of the eigenvector represents the ratio of its corresponding eigenvalue ( $λ_{i}$ ) to the total of all eigenvalues ( $λ_{i}, i = 1, 2, \dots, k$ ) as follows, $\frac{λ_{i}}{\sum_{j = 1}^{k} λ_{j}}$ .

of the first 40 eigenvectors which confirms our findings. From these results, we can conclude that the high order eigenvectors of the data of each application (the first 10% of ear database and the first 40% of ORL and Yale datasets) are robust enough to extract and save the most discriminative features which are used to achieve a good accuracy.

These experiments confirmed that increasing the number of eigenvectors will increase the dimension of the LDA space; hence, CPU time increases. Consequently, the amount of discriminative information and the accuracy increases.

Fig. 11.

The robustness of the first 40 eigenvectors of the LDA technique using ${ORL}_{32 \times 32}$ , ${Ear}_{32 \times 32}$ , and ${Yale}_{32 \times 32}$ datasets.

7.3. Experiments on the small sample size problem

The aim of this experiment is to show when the LDA is subject to the SSS problem and what are the methods that could be used to solve this problem. In this experiment, PCA-LDA [4] and Direct-LDA [22,83] methods are used to address the SSS problem. A set of experiments was conducted to show how the two methods interact with the SSS problem, including the number of samples in each class, the total number of classes used, and the dimension of each sample.

As explained in Section 4, using LDA directly may lead to the SSS problem when the dimension of the samples are much higher than the total number of samples. As shown in Table 2, the size of each image or sample of the ORL dataset is $_{64 \times 64}$ is 4096 and the total number of samples is 400. The mathematical interpretation of this point shows that the dimension of $S_{W}$ is $M \times M$ , while the upper bound of the rank of $S_{W}$ is $N - c$ [79,82]. Thus, all the datasets which are reported in Table 2 lead to singular $S_{W}$ .

To address this problem, PCA-LDA and direct-LDA methods were implemented. In the PCA-LDA method, PCA is first used to reduce the dimension of the original data to make $S_{W}$ full-rank, and then standard LDA can be performed safely in the subspace of $S_{W}$ as in Algorithm 3. For more details of the PCA-LDA method are reported in [4]. In the direct-LDA method, the null-space of $S_{W}$ matrix is removed to make $S_{W}$ full-rank, then standard LDA space can be calculated as in Algorithm 4. More details of direct-LDA methods are found in [83].

Table 2 illustrates various scenarios designed to test the effect of different dimensions on the rank of $S_{W}$ and the accuracy. The results of these scenarios using both PCA-LDA and direct-LDA methods are summarized in Table 3.

Algorithm 3

PCA-LDA

Algorithm 4

Direct-LDA

Table 3

Accuracy of the PCA-LDA and direct-LDA methods using the datasets listed in Table 2

Dataset	$Dim (S_{W})$	# Training images	# Testing images	$Rank (S_{W})$	Accuracy (%)

					PCA-LDA	Direct-LDA
${ORL}_{32 \times 32}$	1024 × 1024	5	5	160	75.5	88.5
		7	3	240	75.5	97.5
		9	1	340	80.39	97.5
${Ear}_{32 \times 32}$	1024 × 1024	3	3	34	80.39	96.08
		4	2	51	88.24	94.12
		5	1	68	100	100
${Yale}_{32 \times 32}$	1024 × 1024	6	5	75	78.67	90.67
		8	3	105	84.44	97.79
		10	1	135	100	100
${ORL}_{64 \times 64}$	4096 × 4096	5	5	160	72	87.5
		7	3	240	81.67	96.67
		9	1	340	82.5	97.5
${Ear}_{64 \times 64}$	4096 × 4096	3	3	34	74.5	96.08
		4	2	51	91.18	96.08
		5	1	68	100	100
${Yale}_{64 \times 64}$	4096 × 4096	6	5	75	74.67	92
		8	3	105	95.56	97.78
		10	1	135	93.33	100

The bold values indicate that the corresponding methods obtain best performances.

As summarized in Table 3, the rank of $S_{W}$ is very small compared to the whole dimension of $S_{W}$ ; hence, the SSS problem occurs in all cases. As shown in Table 3, using the PCA-LDA and the Direct-LDA, the SSS problem can be solved and the Direct-LDA method achieved results better than PCA-LDA because as reported in [22,83], Direct-LDA method saves approximately all important information for classification while the PCA in PCA-LDA method saves the information with high variance.

¹⁷

The range of a matrix A represents the column-space of A ( $C (A)$ ), where the dimension of $C (A)$ is equal to the rank of A.

8. Conclusions

In this paper, the definition, mathematics, and implementation of LDA were presented and explained. The paper aimed to give low-level details on how the LDA technique can address the reduction problem by extracting discriminative features based on maximizing the ratio between the between-class variance, $S_{B}$ , and within-class variance, $S_{W}$ , thus discriminating between different classes. To achieve this aim, the paper followed the approach of not only explaining the steps of calculating the $S_{B}$ , and $S_{W}$ (i.e. the LDA space) but also visualizing these steps with figures and diagrams to make it easy to understand. Moreover, two LDA methods, i.e. class-dependent and class-independent, are explained and two numerical examples were given and graphically illustrated to explain how the LDA space using the two methods can be constructed. In all examples, the mathematical interpretation of the robustness and the selection of the eigenvectors as well the data projection were detailed and discussed. Also, LDA common problems (e.g. the SSS and linearity) were mathematically explained using graphical examples, then their state-of-the-art solutions are highlighted. Moreover, a detailed implementation of LDA applications was presented. Using three standard datasets, a number of experiments were conducted to (1) investigate and explain the relation between the number of eigenvectors and the robustness of the LDA space, (2) to practically show when the SSS problem occurs and how it can be addressed.

References

Balakrishnama and

Ganapathiraju, Linear discriminant analysis-a brief tutorial, Institute for Signal and Information Processing (1998).

Barshan,

Ghodsi,

Azimifar and

M.Z.

Jahromi, Supervised principal component analysis: Visualization, classification and regression on subspaces and submanifolds, Pattern Recognition 44(7) (2011), 1357–1371. doi:10.1016/j.patcog.2010.12.015.

Baudat and

Anouar, Generalized discriminant analysis using a kernel approach, Neural Computation 12(10) (2000), 2385–2404. doi:10.1162/089976600300014980.

P.N.

Belhumeur,

J.P.

Hespanha and

Kriegman, Eigenfaces vs. fisherfaces: Recognition using class specific linear projection, IEEE Transactions on Pattern Analysis and Machine Intelligence 19(7) (1997), 711–720. doi:10.1109/34.598228.

N.V.

Boulgouris and

Z.X.

Chi, Gait recognition using Radon transform and linear discriminant analysis, IEEE Transactions on Image Processing 16(3) (2007), 731–740. doi:10.1109/TIP.2007.891157.

Bramer, Principles of Data Mining, 2nd edn, Springer, 2013.

Carreira-Perpinan, Compression neural networks for feature extraction: Application to human recognition from ear images, MS thesis, Faculty of Informatics, Technical University of Madrid, Spain, 1995.

H.-P.

Chan,

Wei,

M.A.

Helvie,

Sahiner,

D.D.

Adler,

M.M.

Goodsitt and

Petrick, Computer-aided classification of mammographic masses and normal tissue: Linear discriminant analysis in texture feature space, Physics in Medicine and Biology 40(5) (1995), 857–876. doi:10.1088/0031-9155/40/5/010.

Chen,

N.C.

Carpita,

W.-D.

Reiter,

R.H.

Wilson,

Jeffries and

M.C.

McCann, A rapid method to screen for cell-wall mutants using discriminant analysis of Fourier transform infrared spectra, The Plant Journal 16(3) (1998), 385–392. doi:10.1046/j.1365-313x.1998.00301.x.

10.

L.-F.

Chen,

H.-Y.M.

Liao,

M.-T.

Ko,

J.-C.

Lin and

G.-J.

Yu, A new lda-based face recognition system which can solve the small sample size problem, Pattern Recognition 33(10) (2000), 1713–1726. doi:10.1016/S0031-3203(99)00139-9.

11.

Coomans,

Massart and

Kaufman, Optimization by statistical linear discriminant analysis in analytical chemistry, Analytica Chimica Acta 112(2) (1979), 97–122. doi:10.1016/S0003-2670(01)83513-3.

12.

Cui and

Xu, Three dimensional palmprint recognition using linear discriminant analysis method, in: Proceedings of the Second International Conference on Innovations in Bio-Inspired Computing and Applications (IBICA), 2011, IEEE, 2011, pp. 107–111. doi:10.1109/IBICA.2011.31.

13.

D.-Q.

Dai and

P.C.

Yuen, Face recognition by regularized discriminant analysis, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 37(4) (2007), 1080–1085. doi:10.1109/TSMCB.2007.895363.

14.

Donoho and

Stodden, When does non-negative matrix factorization give a correct decomposition into parts? in: Advances in Neural Information Processing Systems 16, MIT Press, 2004, pp. 1141–1148.

15.

R.O.

Duda,

P.E.

Hart and

D.G.

Stork, Pattern Classification, 2nd edn, Wiley, 2012.

16.

Dudoit,

Fridlyand and

T.P.

Speed, Comparison of discrimination methods for the classification of tumors using gene expression data, Journal of the American Statistical Association 97(457) (2002), 77–87. doi:10.1198/016214502753479248.

17.

T.-t.

Feng and

Wu, A theoretical contribution to the fast implementation of null linear discriminant analysis method using random matrix multiplication with scatter matrices, 2014, arXiv preprint arXiv:1409.2579.

18.

J.H.

Friedman, Regularized discriminant analysis, Journal of the American Statistical Association 84(405) (1989), 165–175. doi:10.1080/01621459.1989.10478752.

19.

Gaber,

Tharwat,

A.E.

Hassanien and

Snasel, Biometric cattle identification approach based on Weber’s local descriptor and adaboost classifier, Computers and Electronics in Agriculture 122 (2016), 55–66. doi:10.1016/j.compag.2015.12.022.

20.

Gaber,

Tharwat,

Ibrahim,

Snáel and

A.E.

Hassanien, Human thermal face recognition based on random linear oracle (rlo) ensembles, in: International Conference on Intelligent Networking and Collaborative Systems, IEEE, 2015, pp. 91–98. doi:10.1109/INCoS.2015.67.

21.

Gaber,

Tharwat,

Snasel and

A.E.

Hassanien, Plant identification: Two dimensional-based vs. one dimensional-based feature extraction methods, in: 10th International Conference on Soft Computing Models in Industrial and Environmental Applications, Springer, 2015, pp. 375–385.

22.

Gao and

J.W.

Davis, Why direct lda is not equivalent to lda, Pattern Recognition 39(5) (2006), 1002–1006. doi:10.1016/j.patcog.2005.11.016.

23.

G.H.

Golub and

C.F.

Van Loan, Matrix Computations, 4th edn, Vol. 3, Johns Hopkins University Press, 2012.

24.

Haeb-Umbach and

Ney, Linear discriminant analysis for improved large vocabulary continuous speech recognition, in: IEEE International Conference on Acoustics, Speech, and Signal Processing (1992), Vol. 1, IEEE, 1992, pp. 13–16.

25.

Hastie and

Tibshirani, Discriminant analysis by Gaussian mixtures, Journal of the Royal Statistical Society. Series B (Methodological) (1996), 155–176.

26.

Héberger,

Csomós and

Simon-Sarkadi, Principal component and linear discriminant analyses of free amino acids and biogenic amines in Hungarian wines, Journal of Agricultural and Food Chemistry 51(27) (2003), 8055–8060. doi:10.1021/jf034851c.

27.

G.E.

Hinton and

R.R.

Salakhutdinov, Reducing the dimensionality of data with neural networks, Science 313(5786) (2006), 504–507. doi:10.1126/science.1127647.

28.

Honda and

Ichihashi, Fuzzy local independent component analysis with external criteria and its application to knowledge discovery in databases, International Journal of Approximate Reasoning 42(3) (2006), 159–173. doi:10.1016/j.ijar.2005.10.011.

29.

Hu,

Zhang,

Chen,

Pedrycz and

Yu, Gaussian kernel based fuzzy rough sets: Model, uncertainty measures and applications, International Journal of Approximate Reasoning 51(4) (2010), 453–471. doi:10.1016/j.ijar.2010.01.004.

30.

Huang,

Liu,

Lu and

Ma, Solving the small sample size problem of lda, in: Proceedings of 16th International Conference on Pattern Recognition, 2002, Vol. 3, IEEE, 2002, pp. 29–32.

31.

Hyvärinen,

Karhunen and

Oja, Independent Component Analysis, Vol. 46, Wiley, 2004.

32.

Kirby, Geometric Data Analysis: An Empirical Approach to Dimensionality Reduction and the Study of Patterns, Wiley, 2000.

33.

D.T.

Larose, Discovering Knowledge in Data: An Introduction to Data Mining, 1st edn, Wiley, 2014.

34.

Li,

Zhu and

Ogihara, Using discriminant analysis for multi-class classification: An experimental investigation, Knowledge and Information Systems 10(4) (2006), 453–472. doi:10.1007/s10115-006-0013-y.

35.

Liu,

Y.-Q.

Cheng,

J.-Y.

Yang and

Liu, An efficient algorithm for foley–sammon optimal set of discriminant vectors by algebraic method, International Journal of Pattern Recognition and Artificial Intelligence 6(5) (1992), 817–829. doi:10.1142/S0218001492000412.

36.

Lu,

K.N.

Plataniotis and

A.N.

Venetsanopoulos, Face recognition using lda-based algorithms, IEEE Transactions on Neural Networks 14(1) (2003), 195–200. doi:10.1109/TNN.2002.806647.

37.

Lu,

K.N.

Plataniotis and

A.N.

Venetsanopoulos, Regularized discriminant analysis for the small sample size problem in face recognition, Pattern Recognition Letters 24(16) (2003), 3079–3087. doi:10.1016/S0167-8655(03)00167-3.

38.

Lu,

K.N.

Plataniotis and

A.N.

Venetsanopoulos, Regularization studies of linear discriminant analysis in small sample size scenarios with application to face recognition, Pattern Recognition Letters 26(2) (2005), 181–191. doi:10.1016/j.patrec.2004.09.014.

39.

Moghaddam,

Weiss and

Avidan, Generalized spectral bounds for sparse lda, in: Proceedings of the 23rd International Conference on Machine Learning, ACM, 2006, pp. 641–648.

40.

Müller,

Nocke and

Schumann, Enhancing the visualization process with principal component analysis to support the exploration of trends, in: Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation, Vol. 60, Australian Computer Society, Inc., 2006, pp. 121–130.

41.

Noushath,

G.H.

Kumar and

Shivakumara, (2d) 2 lda: An efficient approach for face recognition, Pattern Recognition 39(7) (2006), 1396–1400. doi:10.1016/j.patcog.2006.01.018.

42.

K.K.

Paliwal and

Sharma, Improved pseudoinverse linear discriminant analysis method for dimensionality reduction, International Journal of Pattern Recognition and Artificial Intelligence 26(1) (2012), 1250002. doi:10.1142/S0218001412500024.

43.

Pan,

Song,

Gan and

Gu, Consistent feature selection and its application to face recognition, Journal of Intelligent Information Systems 43(2) (2014), 307–321. doi:10.1007/s10844-014-0324-5.

44.

C.H.

Park and

Park, Fingerprint classification using fast Fourier transform and nonlinear discriminant analysis, Pattern Recognition 38(4) (2005), 495–503. doi:10.1016/j.patcog.2004.08.013.

45.

C.H.

Park and

Park, A comparison of generalized linear discriminant analysis algorithms, Pattern Recognition 41(3) (2008), 1083–1097. doi:10.1016/j.patcog.2007.07.022.

46.

Rezzi,

D.E.

Axelson,

Héberger,

Reniero,

Mariani and

Guillou, Classification of olive oils using high throughput flow 1 h nmr fingerprinting with principal component analysis, linear discriminant analysis and probabilistic neural networks, Analytica Chimica Acta 552(1) (2005), 13–24. doi:10.1016/j.aca.2005.07.057.

47.

Saeys,

Inza and

Larrañaga, A review of feature selection techniques in bioinformatics, Bioinformatics 23(19) (2007), 2507–2517. doi:10.1093/bioinformatics/btm344.

48.

F.S.

Samaria and

A.C.

Harter, Parameterisation of a stochastic model for human face identification, in: Proceedings of the Second IEEE Workshop on Applications of Computer Vision, 1994, IEEE, 1994, pp. 138–142.

49.

Schölkopf,

C.J.

Burges and

A.J.

Smola, Advances in Kernel Methods: Support Vector Learning, MIT Press, 1999.

50.

Schölkopf and

K.-R.

Mullert, Fisher discriminant analysis with kernels, in: Proceedings of the 1999 IEEE Signal Processing Society Workshop Neural Networks for Signal Processing IX, Madison, WI, USA, 1999, pp. 41–48.

51.

Schölkopf,

Smola and

K.-R.

Müller, Nonlinear component analysis as a kernel eigenvalue problem, Neural Computation 10(5) (1998), 1299–1319. doi:10.1162/089976698300017467.

52.

Sharma,

Imoto and

Miyano, A between-class overlapping filter-based method for transcriptome data analysis, Journal of Bioinformatics and Computational Biology 10(5) (2012), 1250010. doi:10.1142/S0219720012500102.

53.

Sharma,

Imoto and

Miyano, A filter based feature selection algorithm using null space of covariance matrix for dna microarray gene expression data, Current Bioinformatics 7(3) (2012), 289–294. doi:10.2174/157489312802460802.

54.

Sharma,

Imoto,

Miyano and

Sharma, Null space based feature selection method for gene expression data, International Journal of Machine Learning and Cybernetics 3(4) (2012), 269–276. doi:10.1007/s13042-011-0061-9.

55.

Sharma and

K.K.

Paliwal, Cancer classification by gradient lda technique using microarray gene expression data, Data & Knowledge Engineering 66(2) (2008), 338–347. doi:10.1016/j.datak.2008.04.004.

56.

Sharma and

K.K.

Paliwal, A new perspective to null linear discriminant analysis method and its fast implementation using random matrix multiplication with scatter matrices, Pattern Recognition 45(6) (2012), 2205–2213. doi:10.1016/j.patcog.2011.11.018.

57.

Sharma and

K.K.

Paliwal, Linear discriminant analysis for the small sample size problem: An overview, International Journal of Machine Learning and Cybernetics (2014), 1–12.

58.

A.J.

Smola and

Schölkopf, A tutorial on support vector regression, Statistics and Computing 14(3) (2004), 199–222. doi:10.1023/B:STCO.0000035301.49549.88.

59.

Strang, Introduction to Linear Algebra, 4th edn, Wellesley-Cambridge Press, Massachusetts, 2003.

60.

D.L.

Swets and

J.J.

Weng, Using discriminant eigenfeatures for image retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence 18(8) (1996), 831–836. doi:10.1109/34.531802.

61.

M.M.

Tantawi,

Revett,

Salem and

M.F.

Tolba, Fiducial feature reduction analysis for electrocardiogram (ecg) based biometric recognition, Journal of Intelligent Information Systems 40(1) (2013), 17–39. doi:10.1007/s10844-012-0214-7.

62.

Tharwat, Principal component analysis-a tutorial, International Journal of Applied Pattern Recognition 3(3) (2016), 197–240. doi:10.1504/IJAPR.2016.079733.

63.

Tharwat,

Gaber,

Y.M.

Awad,

Dey and

A.E.

Hassanien, Plants identification using feature fusion technique and bagging classifier, in: The 1st International Conference on Advanced Intelligent System and Informatics (AISI2015), Beni Suef, Egypt, November 28–30, 2015, Springer, 2016, pp. 461–471.

64.

Tharwat,

Gaber and

A.E.

Hassanien, One-dimensional vs. two-dimensional based features: Plant identification approach, Journal of Applied Logic (2016).

65.

Tharwat,

Gaber,

A.E.

Hassanien,

H.A.

Hassanien and

M.F.

Tolba, Cattle identification using muzzle print images based on texture features approach, in: Proceedings of the Fifth International Conference on Innovations in Bio-Inspired Computing and Applications IBICA 2014, Springer, 2014, pp. 217–227.

66.

Tharwat,

A.E.

Hassanien and

B.E.

Elnaghi, A ba-based algorithm for parameter optimization of support vector machine, Pattern Recognition Letters (2016).

67.

Tharwat,

Ibrahim,

A.E.

Hassanien and

Schaefer, Ear recognition using block-based principal component analysis and decision fusion, in: International Conference on Pattern Recognition and Machine Intelligence, Springer, 2015, pp. 246–254. doi:10.1007/978-3-319-19941-2_24.

68.

Tharwat,

Mahdi,

El Hennawy and

A.E.

Hassanien, Face sketch synthesis and recognition based on linear regression transformation and multi-classifier technique, in: The 1st International Conference on Advanced Intelligent System and Informatics (AISI2015), Beni Suef, Egypt, November 28–30, 2015, Springer, 2016, pp. 183–193.

69.

Tharwat,

Y.S.

Moemen and

A.E.

Hassanien, Classification of toxicity effects of biotransformed hepatic drugs using whale optimized support vector machines, Journal of Biomedical Informatics (2017).

70.

C.G.

Thomas,

R.A.

Harshman and

R.S.

Menon, Noise reduction in bold-based fmri using component analysis, Neuroimage 17(3) (2002), 1521–1537. doi:10.1006/nimg.2002.1200.

71.

Turk and

Pentland, Eigenfaces for recognition, Journal of Cognitive Neuroscience 3(1) (1991), 71–86. doi:10.1162/jocn.1991.3.1.71.

72.

Vapnik, The Nature of Statistical Learning Theory, 2nd edn, Springer, New York, 2013.

73.

Venna,

Peltonen,

Nybo,

Aidos and

Kaski, Information retrieval perspective to nonlinear dimensionality reduction for data visualization, The Journal of Machine Learning Research 11 (2010), 451–490.

74.

Viszlay,

Lojka and

Juhár, Class-dependent two-dimensional linear discriminant analysis using two-pass recognition strategy, in: Proceedings of the 22nd European Signal Processing Conference (EUSIPCO), IEEE, 2014, pp. 1796–1800.

75.

Wang and

Tang, Random sampling lda for face recognition, in: Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), Vol. 2, IEEE, 2004, pp. II–II.

76.

Welling, Fisher Linear Discriminant Analysis, Vol. 3, Department of Computer Science, University of Toronto, 2005.

77.

M.C.

Wu,

Zhang,

Wang,

D.C.

Christiani and

Lin, Sparse linear discriminant analysis for simultaneous testing for the significance of a gene set/pathway and gene selection, Bioinformatics 25(9) (2009), 1145–1151. doi:10.1093/bioinformatics/btp019.

78.

Yang,

Zhang,

A.F.

Frangi and

J.-y.

Yang, Two-dimensional pca: A new approach to appearance-based face representation and recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence 26(1) (2004), 131–137. doi:10.1109/TPAMI.2004.1261097.

79.

Yang,

Gong,

Gu,

Li and

Liang, Null space discriminant locality preserving projections for face recognition, Neurocomputing 71(16) (2008), 3644–3649. doi:10.1016/j.neucom.2008.03.009.

80.

Yang and

Wu, Regularized complete linear discriminant analysis, Neurocomputing 137 (2014), 185–191. doi:10.1016/j.neucom.2013.08.048.

81.

Ye,

Janardan and

Li, Two-dimensional linear discriminant analysis, in: Proceedings of 17th Advances in Neural Information Processing Systems (NIPS), 2004, pp. 1569–1576.

82.

Ye and

Xiong, Computational and theoretical analysis of null space and orthogonal linear discriminant analysis, The Journal of Machine Learning Research 7 (2006), 1183–1204.

83.

Yu and

Yang, A direct lda algorithm for high-dimensional data with application to face recognition, Pattern Recognition 34(10) (2001), 2067–2070. doi:10.1016/S0031-3203(00)00162-X.

84.

Yuan and

Z.-c.

Mu, Ear recognition based on 2d images, in: Proceedings of the First IEEE International Conference on Biometrics: Theory, Applications, and Systems, 2007, BTAS 2007, IEEE, 2007, pp. 1–5.

85.

X.-S.

Zhuang and

D.-Q.

Dai, Inverse Fisher discriminate criteria for small sample size problem and its application to face recognition, Pattern Recognition 38(11) (2005), 2192–2194. doi:10.1016/j.patcog.2005.02.011.

Linear discriminant analysis: A detailed tutorial

Abstract

Keywords

1. Introduction

2.1. Definition of LDA

1 The transformation matrix (W) will be explained in Section 2.4.

2.4. Constructing the lower dimensional space

2.7. Computational complexity of LDA

3.1. Class-independent method

2 SSS problem will be explained in Section 4.2.

4.1. Linearity problem

4.2.1. Problem definition

3 A matrix is singular if it is square, does not have a matrix inverse, the determinant is zeros; hence, not all columns and rows are independent.

5 A is a full-rank matrix if all columns and rows of the matrix are independent, (i.e. rank ( A ) = # rows = # cols ) [23].

5.1. Biometrics applications

5.2. Agriculture applications

5.3. Medical applications

6. Packages

6 http:/www.cs.waikato.ac.nz/ml/weka/

7.1. Experimental setup

13 http://www.cam-orl.co.uk

References

¹
The transformation matrix (W) will be explained in Section 2.4.

²
SSS problem will be explained in Section 4.2.

³
A matrix is singular if it is square, does not have a matrix inverse, the determinant is zeros; hence, not all columns and rows are independent.

⁵
A is a full-rank matrix if all columns and rows of the matrix are independent, (i.e. $rank (A) = # rows = # cols$ ) [23].

⁶
http:/www.cs.waikato.ac.nz/ml/weka/

¹³
http://www.cam-orl.co.uk