维度规约（特征的提取和组合）

2020-03-07 本文已影响0人有机会一起种地OT

介绍
第一部分参数方法——类密度模型参数估计
第二部分监督学习——分类（基于似然的方法）
第三部分监督学习——分类（基于判别式的方法）（参数方法——判别式参数估计）
第四部分监督学习——回归
第五部分监督学习——关联规则
第六部分维度规约（特征的提取和组合）
第七部分半参数方法
第八部分非监督学习——聚类
第九部分非参数方法——密度估计
第十部分非参数方法——决策树实现的判别式
第十一部分多层感知器——非参数估计器
第十二部分局部模型
第十三部分支持向量机与核机器
第十四部分隐马尔科夫模型
第十五部分参数的贝叶斯估计
第十六部分集成学习——组合多学习器
第十七部分增强学习
第十八部分机器学习实验
第十九部分特征工程与数据预处理

任何分类和回归方法的复杂度都依赖于输入的数量。我们需要输入数据含有可供决策的信息。理想情况下，不需要将特征选择或特征提取作为一个单独的过程。并且有效的方法，应该能够利用任何必要的特征，并丢弃不相关的特征。

但将降维作为一个单独的预处理步骤，有如下一些原因：

1、在大多数机器学习算法中，复杂度依赖于输入的维度d及样本规模N。为了减少存储及计算时间，需要考虑降低维度。同时降低d也降低了检验算法的复杂度。

2、去除不必要的采集数据，

3、更简单的模型可以在小数据集上更鲁棒。（《监督学习——分类（基于判别式的方法）（参数方法——判别式参数估计）》多元情况部分中，提到过高维输入x可能存在奇异的协方差矩阵估计）

4、当数据可以用较少的特征解释时，有利于理解数据背后的过程，并提取知识，利于解释。

降低维度主要有两类方法：特征选择、特征提取。

特征选择——从d个维中找到提供最多信息的k个维度，丢弃其他（d-k）个维度的数据。

特征提取——找到k个维度的新集合，这k个维度是原来d个维度的组合。这些方法可以是监督的或者非监督的。如同为线性投影方法的主成分分析（PCA）和线性判别分析（LDA）分别是非监督的和监督的。线性维度归约以外，还有非线性维度归约方法，如等距特征映射（Isomap）、局部线性嵌入（LLE）、拉普拉斯特征映射。

线性空间中的降维

主成分分析

1、主成分计算

在投影方法中，我们要找到的是从原d维输入空间到新的 $k(k<d)$ 维空间的、具有最小信息损失的映射。

x在方向\omega 上的投影为 $z=\omega^T \mathbf{x}$ 。

PCA是一种非监督方法，其最大化的准则是方差，主成分是这样的 $\omega _1$ ，样本投影在 $\omega _1$ 上后最分散。同时为了保证解唯一，要求 $\|\omega_1\|=1$ 。

如果 $z_1=\omega_1^T \mathbf{x}$ 且 $Cov(\mathbf{x})=\Sigma$ ，则 $Var(z_1)=\omega_1^T\Sigma\omega_1$ 。寻找 $\omega_1$ 使得 $Var(z_1)$ 在约束 $\omega_1^T\omega_1=1$ 下最大化。写成拉格朗日问题，有：

$\max_{\omega_1}\omega_1^T\Sigma\omega_1-\alpha(\omega_1^T\omega_1-1)$

关于 $\omega_1$ 求导并令它等于0，有 $2\Sigma\omega_1-2\alpha\omega_1=0$ ，也就是 $\Sigma\omega_1=\alpha\omega_1$ 。 $\omega_1$ 是 $\Sigma$ 的特征向量， $\alpha$ 是对应的特征值。因为我们想最大化方差 $\omega_1^T\Sigma\omega_1=\alpha\omega_1^T\omega_1=\alpha$ ，特征值就等于方差，所以选择最大化特征值的特征向量。

因此，主成分是输入样本协方差矩阵的具有最大特征值的特征向量。

第二个主成分 $\omega_2$ 也应该最大化方差 $Var(z_2)$ ，具有单位长度，并且与 $\omega _1$ 正交（也就是与 $\omega_1$ 不相关）。则对第二个主成分有：

$\max_{\omega_2}\omega_2^T\Sigma\omega_2-\alpha(\omega_2^T\omega_2-1)-\beta(\omega_2^T\omega_1-0)$

关于 $\omega_2$ 求导并令它等于0，有 $2\Sigma\omega_2-2\alpha\omega_2-\beta\omega_1=0$ 。左乘 $\omega_1^T$ ，得 $2\omega_1^T\Sigma\omega_2-2\alpha\omega_1^T\omega_2-\beta\omega_1^T\omega_1=0$ 。

其中 $\omega_1^T\Sigma\omega_2=\omega_2^T\Sigma\omega_1=\lambda_1\omega_2^T\omega_1=0$ 。

于是得 $\beta=0$ ， $\Sigma\omega_2=\alpha\omega_2$ 。表明 $\omega _2$ 是 $\Sigma$ 得具有第二大特征值的特征向量。类似地，其他维可由递减特征值的特征向量给出。并且，因为 $\Sigma$ 是对称的，所以对于任意两个不同的特征值，对应的特征向量是正交的。

最后有降维后的数据 $\mathbf{z}=\mathbf{W}^T(\mathbf{x}-\mathbf{m})$ ，其中W的k列是\Sigma 的估计S的k个主特征向量。投影前从 x 中减去样本均值 m ，将数据原点中心化。

等同地，我们想找到一个矩阵W，使得 $\mathbf{z}=\mathbf{W}^T\mathbf{x}$ (不失一般性，x已经中心化)， $Cov(\mathbf{z})=\mathbf{D}=\mathbf{W}^TS\mathbf{W}$ ，其中D是对角矩阵，既我们希望得到不相关的z_i。令S是D的估计， $d\times d$ 矩阵C的第 i 列是S的规范化特征向量 $c_i$ ，则 $C^TC=I$ 。且有

$\begin{align}S&=SCC^T\\&=S(\mathbf{c_1},\mathbf{c_2},\cdots,\mathbf{c_d})C^T\\&=(\lambda_1\mathbf{c_1},\lambda_2\mathbf{c_2},\cdots,\lambda_d\mathbf{c_d})C^T\\&=\lambda_1\mathbf{c_1}\mathbf{c_1^T}+\cdots+\lambda_d\mathbf{c_d}\mathbf{c_d^T}\\&=CDC^T\end{align}$

其中D是对角矩阵，对角元素是特征值\lambda_i。这称为S的谱分解。C是正交的，有 $C^TSC=D$ 。所以可以令 $\mathbf{W}=C$ ， $Cov(\mathbf{z})$ 是对角矩阵。

2、选取主成分

得到了各主成分 $\omega _i$ ，根据特征值大小，可统计方差比例 $\frac{\lambda_1,+\cdots+\lambda_k}{\lambda_1,+\cdots+\lambda_k+\cdots+\lambda_d}$ ，取贡献了一定比例以上的前k个主成分。或可通过忽略小于平均输入方差的特征值对应的特征向量，来得到k个主成分。

PCA解释方差，但对离群点很敏感。少量离群点会明显影响方差，从而对特征向量产生很大影响。一般会通过计算数据点的马氏距离，丢弃孤立的离群点，保证估计的鲁棒性。

因子分析

因子分析（FA）同PCA一样时非监督的。假设存在不可观测的潜在因子集合 $z_j,j=1,\cdots,k$ ，它们组合成样本实例 $\mathbf{x}$ 。与PCA方法相反，FA的目的时通过较少的因子 z 刻画观测变量 x 之间的依赖性。也就是相较于PCA的 $\mathbf{z}=\mathbf{W}^T\mathbf{x}$ ，FA试图找到 z 使得其构成 x ： $\mathbf{x}=V^T\mathbf{z}$ 。

在PCA中，挑选大特征值的特征向量构成W，损失了没有被选中的特征值对应的方差。但FA虽也在一个更小的维空间重构数据，但没有丢失信息。

特征嵌入

X是 $N\times d$ 的样本数据矩阵，协方差矩阵是 $d\times d$ 的。如果X已中心化，具有零均值，则协方差矩阵等于 $X^TX$ 。PCA使用 $X^TX$ 的特征向量，谱分解是 $X^TX=CDC^T$ ，C的各列是 $X^TX$ 的特征向量，D是对应特征值构成的 $d \times d$ 对角矩阵。

如果我们想将维度归约到 $k<d$ ，在PCA中，假定W中的特征向量按特征值大小排序，取W的前k列（ $X^TX$ 具有最大特征值的k个特征向量），我们记这些特征向量为 $\omega _i$ ，对应特征值为 $\lambda_i$ 。从原始输入空间映射到新的k维空间：

$z_i^t=\mathbf{\omega}_i^T\mathbf{x}^t,i=1,\cdots ,k;t=1,\cdots,N$

对任意 $i\leq k$ ，有

$\begin{align}(X^TX)\omega_i&=\lambda_i\omega_i\\(XX^T)X\omega_i&=\lambda_iX\omega_i\end{align}$

因此， $X\omega_i$ 是 $XX^T$ 的具有特征值 $\lambda_i$ 的特征向量。注意， $X^TX$ 是 $d \times d$ 的，而 $XX^T$ 是 $N \times N$ 的。

其谱分解为 $XX^T=VEV^T$ ，其中 $V$ 是 $N \times N$ 的， $V$ 的列是 $XX^T$ 的特征向量 $v_i=X\omega_i / \sqrt{\lambda_i}$ （单位化后的）， $E$ 是对应特征值构成的对角矩阵。 $XX^T$ 的N维特征向量是新的特征嵌入（FE）空间的坐标。

求得了 $v_i$ ，可直接得到 $X\omega_i$ （PCA所做的）： $z_i^t=V_{ti}\sqrt{E_{tt}}$

通常 $d<N$ ，这是使用PCA来计算 $X^TX$ 更简单。而有时 $d>N$ ，则计算 $XX^T$ 容易一些。

对于PCA，得到的是投影向量，可通过取x与特征向量的点积，将任意一个x投影到新的k维空间。但线性嵌入没有学习得到投影映射的模型，每当有一个新的数据加入，都需要重新进行计算。

多维定位

假设N个点，知道每对点间距离 $d_{ij}$ （不需知道这些点的坐标，维度，也不必知道如何计算这些距离）。多维定位（MDS）是把这些点映射到低维空间的方法，使它们在低维空间重得欧式距离尽可能接近原始空间中的给定距离 $d_{ij}$ 。

可以使用MDS进行维度归约，通过d维 x 空间的逐对欧氏距离，将距离作为MDS的输入。如有样本 $X=\{\mathbf{x}^t \}_{t=1}^N$ ，其中 $\mathbf{x}^t\in \mathbf{R}^d$ ，在运用MDS方法时，不需知道 x 的具体坐标。对每两个点 r 和 s。它们之间的平方欧氏距离为

$d_{rs}^2=\|\mathbf{x}^r-\mathbf{x}^s\|^2=\sum_{j=1}^d(x_j^r)^2+\sum_{j=1}^dx_j^rx_j^s+\sum_{j=1}^d(x_j^s)^2=b_{rr}+b_{ss}-2b_{rs}$ ，其中 $b_{rs}=\sum_{j=1}^dx_j^rx_j^s$ 。

将数据中心化并假定 $\sum_{r=1}^Nx_j^r=0,\forall j=1,\cdots,d$ 。由此有 $\sum_{r=1}^Nb_{rs}=\sum_{j=1}^d\sum_{r=1}^Nx_j^rx_j^s=0$ 。

并记 $T=\sum_{t=1}^Nb_{tt}$ ，得到

$\begin{align}\sum_rd_{rs}^2&=\sum_r(b_{rr}+b_{ss}-2b_{rs})\\&=T+Nb_{ss}\\\end{align}$

由上述各等式可得：

$\begin{align} b_{rs}&=\frac{1}{2} (d_{rs}^2-b_{rr}-b_{ss}) \\ &=\frac{1}{2} (d_{rs}^2-\frac{1}{N} (\sum_id_{is}^2-T)- \frac{1}{N} (\sum_id_{ri}^2-T)) \\ \end{align}$

故通过已知的 $d_{rs}$ ，计算得到了 $b_{rs}=\sum_{j=1}^dx_j^rx_j^s$ ，也就是得到了 $B=XX^T$ 。也就是线性嵌入的结果。通过B的特征向量得到各实例在新空间中的坐标。

PCA、FA与MDS做了同样的事情，当d<N时，PCA代价更低。在相关性矩阵上而不是协方差矩阵上做PCA等价于用标准欧氏距离来做MDS，其中每个变量都有单位方差。而MDS

上面介绍的MDS用线性映射的方法，将原空间上的数据，线性地映射到新空间： $\mathbf{z}=g(\mathbf{x}|W)=W^T\mathbf{x}$

MDS中也可以使用非线性的映射，这被称为Sammon映射。映射中的标准化误差称为Sammon应力：

$\begin{align} E(\theta |X)&=\sum_{r,s}\frac{(\|\mathbf{z}^r-\mathbf{z}^s\|-\|\mathbf{x}^r-\mathbf{x}^s\|)^2}{\|\mathbf{x}^r-\mathbf{x}^s\|^2}\\ &=\sum_{r,s}\frac{(\|g(\mathbf{x}^r|\theta)-g(\mathbf{x}^s|\theta)\|-\|\mathbf{x}^r-\mathbf{x}^s\|)^2}{\|\mathbf{x}^r-\mathbf{x}^s\|^2} \end{align}$

可对g使用任何回归方法，训练 $\theta$ 最小化训练数据 X 上的Sammon应力。

对于分类的情况，可在距离的定义中包含类信息，如 $d^{\prime}_{rs}=(1-\alpha)d_{rs}+\alpha c_{rs}$ ，其中 $c_{rs}$ 是r和s所属类之间的距离。应该主观地提供这个类间距离， $\alpha$ 用交叉验证优化。

线性判别分析

线性判别分析（LDA）是一种用于分类问题的维度归约的监督方法。

两类问题，考虑两个类 $C_1$ ， $C_2$ 的样本，希望找到由向量 $\omega$ 定义的方向，使得当数据投影到 $\omega$ 上时，来自两个类的样本尽可能分开。

$z=\omega^Tx$ 是 $x$ 到 $\omega$ 上的投影。 $\mathbf{m}_1$ 和 $m_1$ 是 $C_1$ 类样本在投影前和投影后的均值。注意这里 $\mathbf{m}_1\in R^d$ ，而 $m_1\in R$ 。设样本 $X=\{\mathbf{x}^t,r^t \}$ ，对 $\mathbf{x}^t\in C_1$ 有 $r^t=1$ ， $\mathbf{x}^t\in C_2$ 有 $r^t=0$ 。

$m_1=\frac{\sum_t\omega^T\mathbf{x}^tr^t}{\sum_tr^t} =\omega^T\mathbf{m}_1$ ， $m_2=\frac{\sum_t\omega^T\mathbf{x}^t(1-r^t)}{\sum_t(1-r^t)} =\omega^T\mathbf{m}_2$ 。

来自两个类的样本投影后在均值周围的散布是

$s_1=\sum_t(\omega^T\mathbf{x}^t-m_1)^2r^t$ ， $s_2=\sum_t(\omega^T\mathbf{x}^t-m_2)^2(1-r^t)$ 。

投影后，为了使各类尽可能地分开，则希望均值金尽可能远离，并且类实例散布在尽可能小的范围里。既， $|m_1-m_2|$ 大， $s_1^2+s_2^2$ 小。费希尔线性判别式是这样的 $\omega$ ，最大化 $J(\omega)=\frac{(m_1-m_2)^2}{s_1^2+s_2^2}$ 。其中

$\begin{align} (m_1-m_2)^2&=(\omega^T\mathbf{m}_1-\omega^T\mathbf{m}_2)^2\\&=\omega^T(\mathbf{m}_1-\mathbf{m}_2)(\mathbf{m}_1-\mathbf{m}_2)\omega\\&=\omega^TS_B\omega \end{align}$

$\begin{align} s_1^2+s_2^2&=\sum_t[(\omega^T\mathbf{x}^t-m_1)r^t+(\omega^T\mathbf{x}^t-m_2)(1-r^t)] \\ &=\sum_t[\omega^T(\mathbf{x}^t-\mathbf{m}_1)(\mathbf{x}^t-\mathbf{m}_1)^T\omega r^t+\omega^T(\mathbf{x}^t-\mathbf{m}_2)(\mathbf{x}^t-\mathbf{m}_2)^T\omega (1-r^t)] \\ &=\omega^TS_W\omega \end{align}$

其中 $S_B=(\mathbf{m}_1-\mathbf{m}_2)(\mathbf{m}_1-\mathbf{m}_2)^T$ 是类间散度矩阵， $S_W$ 是类内散布的和。从而

$J(\omega)=\frac{\omega^TS_B\omega}{\omega^TS_W\omega}=\frac{|\omega^T(\mathbf{m}_1-\mathbf{m}_2)^2|}{\omega^TS_W\omega}$ ，关于 $\omega$ 求 $J$ 的导数，并令其为0，得

$\frac{\omega^T(\mathbf{m}_1-\mathbf{m}_2)}{\omega^TS_W\omega} \left(2(\mathbf{m}_1-\mathbf{m_2}-\frac{\omega^T(\mathbf{m}_1-\mathbf{m}_2)}{\omega^TS_W\omega}S_W\omega) \right)=0$

其中 $\frac{(\mathbf{m}_1-\mathbf{m}_2)}{\omega^TS_W\omega}$ 是常数，有 $\omega=cS_W^{-1}(\mathbf{m}_1-\mathbf{m}_2)$ ，c是常数。这里关注的是 $\omega$ 的方向，故c取1。

对于K>2个类，我们希望找到矩阵W，使得 $z=W^T\mathbf{x}$ ，其中z是k维的，矩阵W是 $d \times k$ 矩阵。 $C_i$ 的类内散布矩阵是

$S_i=\sum_ir_i^t(\mathbf{x}^t-\mathbf{m}_i)(\mathbf{x}^t-\mathbf{m}_i)^T$ ，其中对 $\mathbf{x}^t\in C_i$ 有 $r_i^t=1$ ，否则为0。

总的类内散布矩阵是 $S_W=\sum_{i=1}^KS_i$ 。

类间散布矩阵是 $S_B=\sum_{i=1}^KN_i(\mathbf{m}_i-\mathbf{m})(\mathbf{m}_i-\mathbf{m})^T$ ，其中 $N_i=\sum_tr_i^t，\mathbf{m}=\frac1K\sum_{i=1}^K\mathbf{m}_i$ 。

投影后类间散布矩阵为 $W^TS_BW$ ，类内散布矩阵是 $W^TS_WW$ ，都是 $k\times k$ 矩阵。

同样地，我们希望类间散布更大，类内散布更小，故最大化 $J(W)=\frac{|W^TS_BW|}{|W^TS_WW|}$ ，其解为 $\omega=S_W^{-1}S_B$ 的最大的特征向量。注意， $S_B$ 是K个秩为1的矩阵 $(\mathbf{m}_1-\mathbf{m})(\mathbf{m}_1-\mathbf{m}^T)$ 的和，并且可知它们之中最多只有K-1个是独立，因此S_B的秩最大只有K-1。同2类一样，数据在 $\omega$ 上的投影自然是降维的。

为了使用LDA，需要类内散布矩阵 $S_W$ 可逆。如果不可逆，可先用PCA消除奇异性，在运用LDA。同时，应该确保PCA 没有把维度降得太低，使得LDA没有多少事可做。

相比于PCA只注重总体的方差，LDA的监督性注重类间散布。

流形学习

前面所介绍的方法，都需要数据落在一个线性子空间中。但这一前提并不总是成立。等距特征映射（Isomap）与下面的局部线性嵌入和拉普拉斯特征映射，不同于上面的方法，考虑的是流形（mainfold）上的输入数据，且为非监督方法。关注的局部数据的逐对距离，而不是全局相似性。

等距特征映射

Isomap使用所有数据点对之间的测地距离（沿流形的距离）。对输入空间中靠近的邻近点，可以使用欧氏距离。对距离远的点，用沿流形的各点之间的距离和来近似。

视两个点 r 和 s 是连接的，如果 $\|\mathbf{x}^r-\mathbf{x}^s\|<\varepsilon$ 或 s 是 r 的n个最近邻之一，则其rs边长是 $\|\mathbf{x}^r-\mathbf{x}^s\|$ 。对任意两个节点 r 和s， $d_{rs}$ 是它们之间最短路径的长度。然后在 $d_{rs}$ 可上应用MDS。

与使用MDS一样，由于使用了线性嵌入来将N个数据放到一个低维空间，所以没有学习一个从原空间到低维空间的映射函数。

局部线性嵌入

局部线性嵌入（LLE）从局部线性拟合来发现全局非线性结构。其基本思想是，流形的每个局部可以线性地近似。每个点可通过其邻近点的线性加权和给出。

原数据 $\mathbf{x}^r$ 和它的近邻 $\mathbf{x}_r^s$ 可使用最小二乘法找到重构权重 $W_{rs}$ 。其最小化误差 $E(W|X)=\sum_r\|\mathbf{x}^r-\sum_sW_{rs}x_r^s\|^2$ ，

且满足 $\forall r,W_{rr}=0,\sum_sW_{rs}=1$ 。

LLE试图用重构权重 $W_{rs}$ 反应数据的固有几何性质，期望这种性质在映射后的新空间中也能保持。因此，LLE方法下一步保持 $W_{rs}$ 固定，来取新坐标 z 的值。

$E(Z|W)=\sum_r\|\mathbf{z}^r-\sum_sW_{rs}\mathbf{z}^s\|^2$

与Isomap一样，LLE的解是N个点的新坐标，不学习映射。对此有两种解决方案：

1、使用相同的思想，对新元素 $x^{\prime}$ ，在原始 d 维空间中找出 $x^{\prime}$ 的n个近邻（原数据集中的实例，已映射到新空间），并且首先学习最小化 $E^{\omega}(\omega|X)=\|\mathbf{x}^{\prime}-\sum_s\omega_s\mathbf{x}^s \|^2$ 的重构权重 $\omega_j$ 。然后使用它们在新的k维空间中重构 $\mathbf{z}^{\prime}=\sum_s\omega_s\mathbf{z}^{s}$ 。

2、使用映射后的结果 $X=\left\{ \mathbf{x}^t,\mathbf{z}^t \right\}_{t=1}^N$ 作为训练集，可训练任意回归器 $g(\mathbf{x}^t|\theta)$ 。例如多层感知器，作为从 $\mathbf{x}^t$ 到 $\mathbf{z}^t$ 映射的近似。

Isomap和LLE中，全局非线性组织通过整合部分重叠的局部线性约束而得到。

拉普拉斯特征映射

考虑数据实例 $\mathbf{x}^r \in R^d(r=1,\cdots,N)$ 和它们的投影 $\mathbf{z}^r \in R^k$ 。假定实例点对之间相似度为 $B_{rs}$ ， $B_{rs}$ 可在原始空间中计算。r和s相等时取最大值，并且它是对称的 $B_{rs}=B_{sr}$ 。

这里的目标函数是 $\min \sum_{r,s}\|\mathbf{z}^r-\mathbf{z}^s\|^2B_{rs}$ ，意义在于相似的实例应该放在新空间中的邻近位置，而不相似的实例在新空间中的位置相对不关心。

计算 $B_{rs}$ ，MDS方法中使用点积 $B_{rs}=(\mathbf{x}^r)^T\mathbf{x}^s$ 。但在拉普拉斯特征映射中，同Isomap和LLE一样，只关注局部相似性。通过r 和s 之间的某个最大 $\varepsilon$ 距离，或者通过k最近邻来定义邻域，邻域之外，设置 $B_{rs}=0$ 。邻域之内，对于用户指定的某个 $\sigma$ 值，使用高斯核把欧氏距离转换为相似度：

$B_{rs}=\exp \left[ \frac{\|\mathbf{x}^r-\mathbf{x}^s\|^2}{2\sigma^2}\right]$

定义了 $B_{rs}$ 后，最小化目标函数

$\begin{align} &\min \sum_{r,s}\|\mathbf{z}^r-\mathbf{z}^s \|^2B_{rs}\\ &\min \sum_{r,s}\sum_{k}(z_k^r-z_k^s)^2B_{rs}\\ &\min \sum_k(\sum_{r,s}B_{rs}(z_k^r)^2-2\sum_{r,s}B_{rs}z_k^rz_k^s+\sum_sB_{rs}(z_k^s)^2)\\ &\min \sum_k2(\sum_{r,s}B_{rs}(z_k^r)^2-\sum_{r,s}B_{rs}z_k^rz_k^s) \end{align}$

简写为 $\min \mathbf{z}^TD\mathbf{z}-\mathbf{z}^TB\mathbf{z}$ ，其中D是 $\sum_sB_{rs}$ 的 $N\times N$ 对角矩阵，B是 $B_{rs}$ 构成的 $N \times N$ 矩阵。

定义图拉普拉斯（graph Laplacian） $L=D-B$ 。目标最小化 $\mathbf{z}^TL\mathbf{z}$ 。约束 $\|\mathbf{z}\|=1$ 。与特征嵌入一样，得到新空间中的坐标 z。其解是L的特征向量，又因为我们要最小化 $\mathbf{z}^TL\mathbf{z}$ ，所以选则最小特征值的特征向量作为解（注意忽略0特征值）。

拉普拉斯特征映射是一种特征嵌入方法。也就是直接在新空间中得到坐标，而没有可用于新实例的映射模型。

拉普拉斯特征映射使用特征嵌入的思想，并保持逐对相似性。相同的思想也用于核机器，核机器中逐对相似性由核函数给出。

对特征提取和决策之间，如果特征提取过程做的很好，则分类或回归算法任务就会容易很多。

核维度规约

核机器的运用，将非线性空间的问题变为新的线性空间上的问题。具体对核方法的介绍见《支持向量机与核机器》一节。

对于维度规约方法，也可以运用核方法。对于处理线性子空间的方法，不能直接运用在流形问题上。核版本的方法可以解决这个问题，核机器内在地将原问题映射到新的线性子空间中，再在线空间上采用线性方法。核PCA使用核矩阵的特征向量核特征值，这对应于在基函数映射后的 $\Phi(\mathbf{x})$ 的空间上做线性维度规约。而在MDS中，核值则作为相似度值。`