Introduction to Linear Discriminant Analysis

参考自 Multi-label Linear Discriminant Analysis

Linear discriminant analysis (LDA) is a well-known method for dimensionality reduction.

Given a data set with $n$ samples $\{x^{(i)},y^{(i)}{\}}_{i=1}^n$ and $K$ classes, where $x^{(i)}\in {\mathbb{R}}^p$ and $y^{(i)}\in \{0,1{\}}^K$ ($K$ 维的 0-1 vector). $y_k^{(i)}=1$ if $x^{(i)}$ belongs to the $k$^th class, and 0 otherwise.

Let input data be partitioned into $K$ groups as $\{{\pi }_k{\}}_{k=1}^K$, where ${\pi }_k$ denotes the group of the $k$^th class with $n_k$ data points. Classical LDA deals with single-label problems, where data partitions are mutually exclusive, i.e., ${\pi }_i\cap {\pi }_j=\varnothing$ if $i\ne j$, and $\sum _{k=1}^K{n}_k=n$.

We write $X=[x^{(1)},\cdots ,x^{(n)}{]}^T$ and

where $y_{(k)}\in {0,1}^n$ is the class-wise label indication vector for the $k^{th}$ class.

简单理一下：

• # of features = $p$
• # of samples = $n$
• $x^{(i)}$ is a $p\times 1$ vector
• $X$ is a $n\times p$ matrix
• $y^{(i)}$ is a $K\times 1$ vector
• $y_{(i)}$ is a $n\times 1$ vector
• $Y$ is a $n\times K$ matrix

Classical LDA seeks a linear transformation $G\in {\mathbb{R}}^{p\times r}$ that maps $x^{(i)}$ in the high $p$-dimensional space to $q^{(i)}\in {\mathbb{R}}^r$ in a lower $r$-dimensional ($r<p$) space by $q^{(i)}=G^T{x}^{(i)}$. In classical LDA, the between-class, within-class, and total-class scatter matrices are defined as follows:

where $m_k=\frac{1}{n_k}\sum _{x^{(i)}\in {\pi }_k}{x}^{(i)}$ is the class mean (class centroid) of the $k$^th class, $m=\frac{1}{n}\sum _{i=1}^n{x}^{(i)}$ is the global mean (global centroid), and $S_t=S_b+S_w$.

The optimal $G$ is chosen such that the between-class distance is maximize whilst the within-class distance is minimized in the low-dimensional projected space, which leads to the standard LDA optimization objective as follows:

In linear algebra, the trace (迹) of an $n\times n$ square matrix $A$ is defined to be the sum of the elements on the main diagonal (the diagonal from the upper left to the lower right) of $A$, i.e.,