特征脸算法

2020-10-09 本文已影响0人卡德尔先生

前言

特征脸算法使经典的人脸识别算法，特征脸算法使用了PCA方法。本文介绍了PCA算法和其应用特征脸算法

算法流程

特征脸算法：

设数据集D为 $M$ 张 $N\times N$ 的图片 $\{\Phi_1, \Phi_2....\Phi_M\}$ ，则将图片展开，组成 $M\times N^2$ 大小的矩阵。
计算此矩阵的对均值向量 $\bar{\Phi}$ ，此为 $N\times N$ ，对每个图片，计算 $\tilde{\Phi}_i = \Phi_i-\bar\Phi_i$ 。
计算 $\tilde{\Phi}$ 的协方差矩阵 $C=\tilde{\Phi}^T\tilde{\Phi}$ ，注意 $C$ 的大小为 $(N\times N) \times (N \times N)$ 。 $C$ 寻找的是像素之间的关系而不是图片之间的关系
计算算 $C$ 的特征值 $\{\lambda_1,\lambda_2,...,\lambda_{N\times N}\}$ 与其对应的特征向量 $\{\mathbf{v_1},\mathbf{v_2},...,\mathbf{v_{N\times N}}\}$ ，找到前 $n$ 个特征值所对应的特征向量，组成新的矩阵 $V$ 。
改变基。以特征向量作为新的基做新的图片 $I' = \tilde{\Phi} V$
使用KNN进行分类

算法原理

如果我们要学习一组图片 $\Omega$ 的基 $V_{\Omega}$ ，让 $\Omega=\{\alpha^{(1)},\alpha^{(2)},...,\alpha^{(N)}\}$ ，其中 $\alpha^{(i)}=\{\alpha^{(i)}_1,\alpha^{(i)}_2,...,\alpha^{(i)}_{mn}\}$

那么对于所有的图片，找到一个图片近似 $\alpha^{(0)}$ ，对以下的 $J_0(\alpha^{(0)})$ 求最小值

$J_0(\alpha^{(0)})=\Sigma^N_{i=0}||\alpha^{(0)}-\alpha^{(i)}||^2_2$

其中 $||\alpha^{(0)}-\alpha^{(i)}||^2_2$ 是欧几里得平方距离

$\alpha^{(0)}$ 是一个在 $\Omega$ 的基中的一张图片

如果要使 $J_0(\alpha^{(0)})$ 最小，则易得 $\alpha^{(0)}$ 是样本图片的均值 $\alpha^{(0)}=m=\frac{1}{N}\sum\limits_{k=1}^n\alpha^{(i)}$ （偏导）

$J_0(\alpha^{(0)})=\Sigma^N_{i=0}||(\alpha^{(0)}-m)-(\alpha^{(i)}-m)||^2_2$

其中 $\alpha^{(0)}-m=0$ 。所以 $J_0(\alpha^{(0)})=\Sigma^N_{i=0}||m-\alpha^{(i)}||^2_2$ ，此式独立于 $\alpha^{(0)}$

$\Omega$ 的零维呈现是一个点 $\Omega$ 的一维呈现是一条线

让 $\mathbf{e}$ 是通过 $\alpha^{(0)}$ 的一条线的方向。 $e$ 回使 $\Omega$ 的方差达到最高

$\alpha=\alpha^{(0)}+a\mathbf{e}\ a\in\mathbb{R} \ \ e\in\mathbb{R^{mn}} \ \ ||e||=1$

其中 $\alpha$ 是任意图像

$\alpha^{(0)}$ 是平均图像

$J_1(\{\alpha^{(1)},\alpha^{(2)},...,\alpha^{(N)}\}, \mathbf{e})=\Sigma^N_{i=0}||(\alpha^{(0)}+a^{(i)}\mathbf{e})-\alpha^{(i)}||^2=\sum\limits_i(a^{(i)})^2-2\sum\limits_i a^{(i)}\mathbf{e}^T(\alpha^{(i)}-\alpha^{(0)})+\sum\limits^N_{i=0}||\alpha^{(0)}-\alpha^{(i)}||^2_2$ $\frac{\partial J_1}{\partial a^{(i)}}=2a^{(i)}-2\mathbf{e}^T(\alpha^{(i)}-\alpha^{(0})$

当求出来的偏导为0的时候 $a^{(i)}=\mathbf{e}^T(\alpha^{(i)}-\alpha^{(0)})$ ，可以将 $a$ 用 $\mathbf{e}$ 代替

那么如何决定 $\mathbf{e}$ 的方向呢？

$J_1(\{\alpha^{(1)},\alpha^{(2)},...,\alpha^{(N)}\}, \mathbf{e})=\sum\limits_i(a^{(i)})^2-2\sum\limits_i a^{(i)}\mathbf{e}^T(\alpha^{(i)}-\alpha^{(0)})+\sum\limits^N_{i=0}||\alpha^{(0)}-\alpha^{(i)}||^2_2\\=-\sum\limits_i [\mathbf{e}^T(\alpha^{(i)}-\alpha^{(0)})]^2+\sum\limits^N_{i=0}||\alpha^{(0)}-\alpha^{(i)}||^2_2\\=-\sum\limits_i\mathbf{e}^T(\alpha^{(i)}-\alpha^{(0)})(\alpha^{(i)}-\alpha^{(0)})^T\mathbf{e}+\sum\limits^N_{i=0}||\alpha^{(0)}-\alpha^{(i)}||^2_2$

其中 $(\alpha^{(i)}-\alpha^{(0)})(\alpha^{(i)}-\alpha^{(0)})^T$ 为 $\Omega$ 的协方差矩阵

让 $S=(\alpha^{(i)}-\alpha^{(0)})(\alpha^{(i)}-\alpha^{(0)})^T$

由于 $\sum\limits^N_{i=0}||\alpha^{(0)}-\alpha^{(i)}||^2_2$ 是常数

$\arg \min\limits_{e} \hat{J_1}(\mathbf{e})=-\mathbf{e}^T\mathbf{S}\mathbf{e}$ 其中 $||\mathbf{e}||=1$

使用拉格朗日乘子法

$\mathbf{u}=\mathbf{e}^T\mathbf{S}\mathbf{e}-\lambda(\mathbf{e}^T\mathbf{e}-1)$

$\frac{\partial \mathbf{u}}{\partial \mathbf{e}}=2\mathbf{S}\mathbf{e}-2\lambda\mathbf{e}$

当 $\frac{\partial \mathbf{u}}{\partial \mathbf{e}}=0$ 的时候

$\mathbf{S}\mathbf{e}=\lambda\mathbf{e}$

所以选取前 $d$ 个 $\lambda$ 所对应的 $\mathbf{e}$

为什么选择最大的 $\lambda$ :

$\hat{J_1}(\mathbf{e})=-\mathbf{e}^T\mathbf{S}\mathbf{e}=-\lambda\mathbf{e}^T\mathbf{e}=-\lambda$

最大的 $\lambda$ 使 $\hat{J_1}(\mathbf{e})$ 最小

最后新的基为

$\alpha=\alpha^{(0)}+\sum\limits^d_{i=1}a_i\mathbf{e}_i\\\mathbf{e_i}^T\mathbf{e}_j=0\quad \forall i \neq j$

这种算法也被称作PCA，可以看作是一个由原来维度的向量到 $d$ 大小的向量的投影

代码

from sklearn.datasets import fetch_openml
import numpy as np

mnist = fetch_openml('mnist_784', cache=False)

x_train = mnist.data.astype('float32')[:2000] / 255
y_train = mnist.target.astype('int64')[:2000]

x_test = mnist.data.astype('float32')[2000:2500] /255
y_test = mnist.target.astype('int64')[2000:2500]


def zero_mean(x_train, x_test):
    x_train_mean = np.mean(x_train, axis=0)
    x_train_norm = x_train - x_train_mean
    x_test_norm = x_test - x_train_mean
    return x_train_norm, x_test_norm


def compute_basis(data, n=300):
    C = data.T @ data
    w, v = np.linalg.eig(C)
    basis_indices = np.argsort(w)[::-1][:n]
    eigenvectors = v[basis_indices]
    return eigenvectors.T


def change_basis(data_matrix, eigenvectors):
    I_eig = data_matrix @ eigenvectors
    return I_eig


def knn_predict(eig_train_x, eig_test_x, y_train, y_test, k=1):
    predictions = np.zeros_like(y_test)
    for i in range(eig_test_x.shape[0]):
        x = eig_test_x[i]
        distance_vector = np.sum((eig_train_x - x) ** 2, axis=1)
        nearest_indices = np.argsort(distance_vector)[:k]
        a = y_train[nearest_indices]
        uni, count = np.unique(a, return_counts=True)
        predictions[i] = uni[np.argmax(count)]
    return predictions


if __name__ == '__main__':
    x_train_norm, x_test_norm = zero_mean(x_train, x_test)
    eigenvectors = compute_basis(x_train_norm)
    eig_train_x = change_basis(x_train_norm, eigenvectors)
    eig_test_x = change_basis(x_test_norm, eigenvectors)

特征脸算法

前言

算法流程

算法原理

代码

猜你喜欢

热点阅读