主成分分析和判别函数

模式分类

@author lancelot-vim

主成分分析

考虑n个d维的样本$x_1, x_2...x_n$，如何使用一个d维的向量$x_0$，来代表这n个样本，确切说，我们希望这n个样本和它的代表$x_0$之间的距离的和越小越好，特别的，使用欧几里得距离来定义误差函数$J_0(x_0)$:$J_0(x_0)=\sum_{k = 1}^n||x_0-x_k||^2$

我们的目标是寻找$x_0$，使得$J_0$最小，很容易可以得到:$x_0 = \frac{1}{n}\sum_{k = 1}^nx_k$

实际上，样本均值是样本数据集的零维表达，它表达了样本之间的相似，但不能表达样本的差异性。过样本均值做一条直线，并将所有的样本向这条直线上做投影，那么我们能得到代表所有样本的一维向量，若$\vec{e}$表示这条直线的单位向量，那么直线方程为$\vec{x} = \vec{m} + a\vec{e}$,其中$\vec{m}$代表样本均值
其中$a$是一个实数，表示某点离开$m$的距离，我们用$m = a_ke$来表示$x_k$，可得:
$\qquad \qquad \qquad J_1(a_1,a_2...a_n,e) = \sum_{k=1}^n||(m+a_ke)-x_k||^2 \\ \qquad \qquad \qquad \quad \qquad \qquad \qquad \ \ = \sum_{k=1}^na_k^2||e||^2-2\sum_{k = 1}^na_ke^T(x_k-m) + \sum_{k=1}^n||x_k-m||^2$
由于$||e|| = 1$，通过对$a_k$求偏导，令结果为0有:$a_k=e^T(x_k - m)$，直观上表示为点到直线的距离

这就引出一个问题，什么方向的直线才是最好的直线，对此定义"散布矩阵"(scatter matrix)
$\qquad \qquad \qquad \qquad \qquad S = \sum_{k=1}^n(x_k-m)(x_k-m)^T$

将上式代入$J_1$,有:
$J_1(e)=\sum_{k=1}^na_k^2-2\sum_{k=1}^na_k^2 + \sum_{k=1}^n||x_k-m||^2 \\ \qquad \ = -\sum_{k=1}^ne^T(x_k-m)(x_k-m)^Te + \sum_{k=1}^n||x_k-m||^2 \\ \qquad \ =-e^TSe + \sum_{k=1}^n||x_k-m||^2$

因此，我们需要找单位向量$e$，让$-e^TSe$最大，根据拉格朗日乘数法可得:$Se = \lambda e$，最终我们可以得到新的平方判决函数:
$\qquad \qquad \qquad \qquad \qquad \qquad J_{d'} = \sum_{k=1}^n||(m+\sum_{i=1}^{d'}a_{ki}e_i)-x_k||^2$
其中：$e_1,e_2...e_{d'}$为散布矩阵的d'个的最大特征值所对应的特征向量

判别方法

PCA（主成分分析）对于代表或者说表达数据样本特别有效，但是可能对分类并没有什么作用，比如对于字母Q和O，很可能PCA会Q的尾巴丢掉，总的来说PCA方法是用来寻找有效主轴方向的方法，而判别分类方法(discriminant analysis)使用来寻找有效分类方向的方法。

Fisher 线性判别分析

考虑把d维空间的数据投影到一条直线上去，希望不同类别之间的距离尽量远，相同类别尽量紧凑，我们希望找到这样一条直线。假设我们有一组d维的样本$x_1, x_2...x_n$，它们分别属于两个不同的类别，其中大小为$n_1$的样本子集$D_1$属于类别$w_1$，大小为$n_2$的样本子集$D_2$属于类别$w_2$，如果对$x$中的各个成分做线性组合，就能的到一个內积，结果为标量 $y = w^Tx$,这样，n个样本就能的到n个结果$y_1,y_2...y_n$，相应属于$Y_1,Y_2$。

从几何上来说，假设$||w|| = 1$，那么每个$y_i$就是把$x_i$向方向为$w$的直线作投影，$w$本身的范数仅仅只是乘以了一个倍数，并不重要，但方向很重要。假如$w_1,w_2$在d维空间上形成两个显著分开的聚类，那么我们希望数据在直线的投影是分来的。

一个很好的用来确定最佳分类方向的方法是度量两个类别样本均值的差，加入$m_i$为d为样本的均值，那么投影后的点为：
$\tilde{m}_i = \frac{1}{n_i}\sum_{y \in Y_i}y = \frac{1}{n_i}\sum_{x\in D_i}w^Tx = w^Tm$
因此投影之后的样本差为:$|\tilde{m}_i - \tilde{m}_j| = |w^T(m_1 - m_2)|$
由于可以增加$w$的幅值，使得距离超级大，但是投影样本均值的差却是相对的，所以我们需要定义类别$w_i$的类内散布：$\tilde{s}^2 = \sum_{y \in Y_i}(y - \tilde{m}_i)^2$,于是$\frac{1}{n}(\tilde{s}_1^2 + \tilde{s}_2^2)$就是全部数据总体方差的估计，而$\tilde{s}_1^2 + \tilde{s}_2^2$称作投影样本的总类内散布
由此Fisher线性可分性准则要求在投影$y = w^Tx$下，准测函数$J(w)=\frac{|\tilde{m}_1 - \tilde{m}_2|^2}{\tilde{s}_1^2 + \tilde{s}_2^2}$尽可能大

要使$J(\bullet)$最大化的$w$能够使投影后的两类最大程度的分开，我们还需要一个阈值准则来确定最终的分类器。
为了把$J(\cdot)$写成$w$的表达式，定义类内散布矩阵$S_i = \sum_{x\in D_i}(x-m_i)(x-m_i)^T$，和总散布矩阵$S_w=S_1 + S_2$
可得：

• $\tilde{s}_i^2=\sum_{x\in D_i}(w^Tx - w^Tm_i)^2 = \sum_{x\in D_i}w^T(x-m_i)(x-m_i)^Tw = w^TS_iw$
• 各散度的和: $\tilde{s}_1^2 + \tilde{s}_2^2 = w^TS_ww$
• 各散度的差: $(\tilde{m}_1 - \tilde{m}_2)^2 = (w^Tm_1 - w^Tm_2)^2 = w^T(m_1 - m_2)(m_1 - m_2)^Tw = w^TS_Bw$

我们把$S_w$称为总类内散度矩阵。它与全部样本的样本写方差矩阵成正比，并且是对称且半正定的。当$d \le n$时，$S_w$通常非奇异。类似的，$S_B$被称为总类间散步矩阵，也是对称半正定的，但由于$S_B$是两个向量的外积，所以秩至多等于1.特别的，对于任意的$w$,$S_Bw$的方向沿着$m_1 - m_2$。
若使用$S_B,S_w$来表达，准则函数$J(\cdot)$可以写为：$J(w) =\frac{w^TS_Bw}{w^TS_wW}$

这个表达式在数学物理中经常被使用，同城被称为广义瑞利商，容易证明，使得准则函数$J$最大化的$w$满足$S_Bw = \lambda S_ww$
这是一个广义特征值问题，可以理解成在$J$的极值处，$w$发生微小扰动，并不会使得$J$的分子分母比例发生太大变化。假如$S_w$是非奇异的，我们就能把该问题化为通常的特征值问题: $S_w^{-1}S_Bw = \lambda w$

多重判别分析

对于c-类问题，把Fisher线性判别准则作推广，就需要c-1个判别函数，也就是说投影问题实际上是从d维空间向c-1维空间作投影， 并且假设$d\geq c$，类内散布矩阵推广是明显的：$S_w = \sum_{k=1}^cS_i$,其中$S_i=\sum_{x\in D_i}(x-m_i)(x-m_i)^T$
对$S_B$的推广不是那么容易，假设我们定义总体均值为$m=\frac{1}{n}\sum x = \frac{1}{n}\sum_{i=1}^n n_im_i$,总体散布矩阵$S_T = \sum(x-m)(x-m)^T$,有：
$S_T=\sum_{i=1}^c\sum_{x\in D_i}(x-m_i + m_i-m)(x-m_i + m_i -m)^T \\ \quad \ =\sum_{i=1}^c\sum_{x\in D_i}(x-m_i)(x-m_i)^T+\sum_{i=1}^c\sum_{x \in D_i)(m_i-m)(m_i-m)^T} \\ \quad \ =S_w + \sum_{i=1}^cn_i(m_i-m)(m_i - m)^T$
由于，总散布矩阵就是类内散布矩阵和内间散布矩阵的和，即$S_T = S_w + S_B$，所以自然而然定义类间散布矩阵为：$S_B =\sum_{i=1}^cn_i(m_i-m)(m_i - m)^T$

从d维空间向c-1维空间的投影是通过c-1个分类方程进行的：$y_i = w^T_ix \ \ (i = 1, 2\ ...\ c)$,如果我们吧$y_i$看作一个c-1维的方程组，可以表达为简单的矩阵方程$y = W^Tx$
对原始样本$x_1, x_2\ ... \ x_n$进行投影后，的到新的样本$y_1, y_2, ... y_n$，这些新得到的样本本身又具有它们自己的均值向量和散步矩阵，由此：

• $\tilde{m}_i = \frac{1}{n_i}\sum_{y \in Y_i}y$
• $\tilde{m} = \frac{1}{n}\sum_{i = 1}^cn_i\tilde{m}_i$
• $\tilde{S}_w=\sum_{i=1}^c\sum_{y\in Y_i}(y-\tilde{m}_i)(y-\tilde{m}_i)^T$
• $\tilde{S}_B = \sum_{i=1}^cn_i(\tilde{m}_i-\tilde{m})(\tilde{m}_i-\tilde{m})^T$

易证:

• $\tilde{S}_w = W^TS_wW$
• $\tilde{S}_B = W^TS_BW$

最终，我们的到了判别函数:$J(W) = \frac{|\tilde{S}_B|}{|\tilde{S}_w|} = \frac{|W^TS_BW|}{|W^TS_wW|}$

要使得$J(\cdot)$最大化，需使矩阵$W$的列向量为$S_Bw_i = \lambda_iS_ww_i$特征值所对应的特征向量

下一篇： 隐马尔可夫模型