核化主成分分析（Kernelized Principal Component Analysis, Kernel PCA）的数学推导与特征空间降维过程

字数 5856 2025-12-18 02:43:48

核化主成分分析（Kernelized Principal Component Analysis, Kernel PCA）的数学推导与特征空间降维过程

1. 问题描述

主成分分析（PCA）是一种经典的线性降维方法，它通过寻找数据协方差矩阵的特征向量来获取数据的主方向。然而，当数据结构非线性时，线性PCA可能无法有效捕捉数据的低维流形。核化主成分分析（Kernel PCA）通过引入核技巧，将数据隐式映射到高维特征空间，并在该空间中执行线性PCA，从而实现对非线性结构的降维。本题目要求详细讲解Kernel PCA的数学推导步骤，包括：

从线性PCA到核技巧的过渡
特征空间协方差矩阵的特征值问题推导
核矩阵中心化的处理
新样本的投影计算

2. 从线性PCA到核技巧的过渡

2.1 线性PCA回顾

设原始数据矩阵为 \(\mathbf{X} = [\mathbf{x}_1, \dots, \mathbf{x}_n] \in \mathbb{R}^{d \times n}\)，其中 \(\mathbf{x}_i\) 是 \(d\) 维向量，\(n\) 是样本数。假设数据已中心化（即均值为零）。线性PCA的目标是找到一组正交基 \(\mathbf{w} \in \mathbb{R}^d\)，使得投影后的方差最大：

\[\max_{\mathbf{w}} \mathbf{w}^T \mathbf{C} \mathbf{w}, \quad \text{s.t.} \ \mathbf{w}^T \mathbf{w} = 1, \]

其中 \(\mathbf{C} = \frac{1}{n} \mathbf{X} \mathbf{X}^T\) 是协方差矩阵。通过求解特征值问题 \(\mathbf{C} \mathbf{w} = \lambda \mathbf{w}\) 得到主成分。

2.2 引入核技巧

若数据非线性可分，我们通过一个非线性映射 \(\phi: \mathbb{R}^d \to \mathcal{H}\) 将数据映射到高维特征空间 \(\mathcal{H}\)。在 \(\mathcal{H}\) 中，数据变为 \(\phi(\mathbf{x}_1), \dots, \phi(\mathbf{x}_n)\)。假设映射后的数据已中心化（即 \(\sum_i \phi(\mathbf{x}_i) = 0\)），则特征空间中的协方差矩阵为：

\[\mathbf{C}_\phi = \frac{1}{n} \sum_{i=1}^n \phi(\mathbf{x}_i) \phi(\mathbf{x}_i)^T. \]

PCA在特征空间中的特征值问题为：

\[\mathbf{C}_\phi \mathbf{v} = \lambda \mathbf{v}, \]

其中 \(\mathbf{v}\) 是特征向量。由于 \(\phi\) 可能映射到无穷维空间，直接计算 \(\mathbf{v}\) 不可行。核技巧的核心思想是：特征向量 \(\mathbf{v}\) 一定位于 \(\phi(\mathbf{x}_1), \dots, \phi(\mathbf{x}_n)\) 张成的子空间中，即存在系数 \(\alpha_1, \dots, \alpha_n\) 使得：

\[\mathbf{v} = \sum_{i=1}^n \alpha_i \phi(\mathbf{x}_i). \]

3. 特征空间中的特征值问题推导

3.1 代入特征方程

将 \(\mathbf{v} = \sum_{j=1}^n \alpha_j \phi(\mathbf{x}_j)\) 代入特征方程 \(\mathbf{C}_\phi \mathbf{v} = \lambda \mathbf{v}\)：

\[\frac{1}{n} \sum_{i=1}^n \phi(\mathbf{x}_i) \phi(\mathbf{x}_i)^T \left( \sum_{j=1}^n \alpha_j \phi(\mathbf{x}_j) \right) = \lambda \sum_{j=1}^n \alpha_j \phi(\mathbf{x}_j). \]

简化左侧：

\[\frac{1}{n} \sum_{i=1}^n \phi(\mathbf{x}_i) \left( \sum_{j=1}^n \alpha_j \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j) \right) = \lambda \sum_{j=1}^n \alpha_j \phi(\mathbf{x}_j). \]

定义核函数 \(k(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)\)，则上式化为：

\[\frac{1}{n} \sum_{i=1}^n \phi(\mathbf{x}_i) \left( \sum_{j=1}^n \alpha_j k(\mathbf{x}_i, \mathbf{x}_j) \right) = \lambda \sum_{j=1}^n \alpha_j \phi(\mathbf{x}_j). \]

3.2 转化为核矩阵方程

将等式两边同时左乘 \(\phi(\mathbf{x}_l)^T\)（\(l = 1, \dots, n\)）：

\[\frac{1}{n} \sum_{i=1}^n k(\mathbf{x}_l, \mathbf{x}_i) \left( \sum_{j=1}^n \alpha_j k(\mathbf{x}_i, \mathbf{x}_j) \right) = \lambda \sum_{j=1}^n \alpha_j k(\mathbf{x}_l, \mathbf{x}_j). \]

定义核矩阵 \(\mathbf{K} \in \mathbb{R}^{n \times n}\)，其中 \(K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)\)，并令 \(\boldsymbol{\alpha} = [\alpha_1, \dots, \alpha_n]^T\)，则上式可写为矩阵形式：

\[\frac{1}{n} \mathbf{K} \mathbf{K} \boldsymbol{\alpha} = \lambda \mathbf{K} \boldsymbol{\alpha}. \]

假设 \(\mathbf{K}\) 可逆，两边左乘 \(\mathbf{K}^{-1}\) 可得：

\[\frac{1}{n} \mathbf{K} \boldsymbol{\alpha} = \lambda \boldsymbol{\alpha}. \]

更常见的情况是直接求解广义特征值问题：

\[\mathbf{K} \boldsymbol{\alpha} = n \lambda \boldsymbol{\alpha}. \]

令 \(\lambda' = n \lambda\)，则问题简化为标准特征值问题：

\[\mathbf{K} \boldsymbol{\alpha} = \lambda' \boldsymbol{\alpha}. \]

4. 核矩阵中心化处理

在实际应用中，映射后的数据 \(\phi(\mathbf{x}_i)\) 未必中心化。因此，我们需要对核矩阵进行中心化，使其对应于中心化后的特征向量内积。中心化后的核矩阵 \(\tilde{\mathbf{K}}\) 定义为：

\[\tilde{K}_{ij} = \left( \phi(\mathbf{x}_i) - \frac{1}{n} \sum_{m=1}^n \phi(\mathbf{x}_m) \right)^T \left( \phi(\mathbf{x}_j) - \frac{1}{n} \sum_{l=1}^n \phi(\mathbf{x}_l) \right). \]

展开并利用核函数表示：

\[\tilde{K}_{ij} = K_{ij} - \frac{1}{n} \sum_{m=1}^n K_{im} - \frac{1}{n} \sum_{l=1}^n K_{lj} + \frac{1}{n^2} \sum_{m,l=1}^n K_{ml}. \]

这等价于矩阵运算：

\[\tilde{\mathbf{K}} = \mathbf{K} - \mathbf{1}_n \mathbf{K} - \mathbf{K} \mathbf{1}_n + \mathbf{1}_n \mathbf{K} \mathbf{1}_n, \]

其中 \(\mathbf{1}_n\) 是 \(n \times n\) 矩阵，所有元素为 \(1/n\)。

5. 特征向量归一化与投影计算

5.1 特征向量归一化

求解 \(\tilde{\mathbf{K}} \boldsymbol{\alpha} = \lambda' \boldsymbol{\alpha}\) 得到特征值 \(\lambda'_k\) 和特征向量 \(\boldsymbol{\alpha}_k\)。注意，特征空间中的特征向量 \(\mathbf{v}_k\) 需满足单位长度约束 \(\mathbf{v}_k^T \mathbf{v}_k = 1\)。代入 \(\mathbf{v}_k = \sum_{i=1}^n \alpha_{k,i} \phi(\mathbf{x}_i)\)：

\[\mathbf{v}_k^T \mathbf{v}_k = \sum_{i,j=1}^n \alpha_{k,i} \alpha_{k,j} \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j) = \boldsymbol{\alpha}_k^T \tilde{\mathbf{K}} \boldsymbol{\alpha}_k = \lambda'_k \boldsymbol{\alpha}_k^T \boldsymbol{\alpha}_k. \]

因此，归一化条件为 \(\lambda'_k \boldsymbol{\alpha}_k^T \boldsymbol{\alpha}_k = 1\)，即：

\[\boldsymbol{\alpha}_k \leftarrow \frac{\boldsymbol{\alpha}_k}{\sqrt{\lambda'_k}}. \]

5.2 新样本的投影

对于新样本 \(\mathbf{x}_{\text{new}}\)，其在第 \(k\) 个核主成分上的投影为：

\[t_k = \mathbf{v}_k^T \phi(\mathbf{x}_{\text{new}}) = \sum_{i=1}^n \alpha_{k,i} \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_{\text{new}}) = \sum_{i=1}^n \alpha_{k,i} k(\mathbf{x}_i, \mathbf{x}_{\text{new}}). \]

注意：核函数中的 \(\phi\) 需使用与训练数据相同的中心化处理。实际计算时，需使用中心化后的核向量 \(\tilde{\mathbf{k}}_{\text{new}}\)，其中：

\[\tilde{k}_{\text{new},i} = k(\mathbf{x}_{\text{new}}, \mathbf{x}_i) - \frac{1}{n} \sum_{m=1}^n k(\mathbf{x}_m, \mathbf{x}_i) - \frac{1}{n} \sum_{l=1}^n k(\mathbf{x}_{\text{new}}, \mathbf{x}_l) + \frac{1}{n^2} \sum_{m,l=1}^n k(\mathbf{x}_m, \mathbf{x}_l). \]

则投影为 \(t_k = \tilde{\mathbf{k}}_{\text{new}}^T \boldsymbol{\alpha}_k\)。

6. 总结与关键点

核心思想：通过核函数隐式映射数据到高维空间，并在该空间执行线性PCA。
数学关键：特征向量可表示为训练样本的线性组合，从而将特征值问题转化为核矩阵的特征值问题。
中心化：必须对核矩阵进行中心化以对应特征空间数据中心化。
计算步骤：
1. 选择核函数（如高斯核 \(k(\mathbf{x}, \mathbf{y}) = \exp(-\|\mathbf{x}-\mathbf{y}\|^2/(2\sigma^2))\)）。
2. 计算核矩阵 \(\mathbf{K}\) 并中心化得到 \(\tilde{\mathbf{K}}\)。
3. 求解 \(\tilde{\mathbf{K}} \boldsymbol{\alpha} = \lambda' \boldsymbol{\alpha}\)，保留前 \(p\) 个最大特征值对应的特征向量 \(\boldsymbol{\alpha}_k\)。
4. 归一化 \(\boldsymbol{\alpha}_k\) 使得特征向量单位长度。
5. 将新样本投影到核主成分上得到降维表示。

通过以上步骤，Kernel PCA能够捕捉非线性数据结构，广泛应用于图像处理、模式识别等领域。

核化主成分分析（Kernelized Principal Component Analysis, Kernel PCA）的数学推导与特征空间降维过程 1. 问题描述主成分分析（PCA）是一种经典的线性降维方法，它通过寻找数据协方差矩阵的特征向量来获取数据的主方向。然而，当数据结构非线性时，线性PCA可能无法有效捕捉数据的低维流形。核化主成分分析（Kernel PCA）通过引入核技巧，将数据隐式映射到高维特征空间，并在该空间中执行线性PCA，从而实现对非线性结构的降维。本题目要求详细讲解Kernel PCA的数学推导步骤，包括：从线性PCA到核技巧的过渡特征空间协方差矩阵的特征值问题推导核矩阵中心化的处理新样本的投影计算 2. 从线性PCA到核技巧的过渡 2.1 线性PCA回顾设原始数据矩阵为 \( \mathbf{X} = [ \mathbf{x}_ 1, \dots, \mathbf{x}_ n] \in \mathbb{R}^{d \times n} \)，其中 \( \mathbf{x} i \) 是 \( d \) 维向量，\( n \) 是样本数。假设数据已中心化（即均值为零）。线性PCA的目标是找到一组正交基 \( \mathbf{w} \in \mathbb{R}^d \)，使得投影后的方差最大： \[ \max {\mathbf{w}} \mathbf{w}^T \mathbf{C} \mathbf{w}, \quad \text{s.t.} \ \mathbf{w}^T \mathbf{w} = 1, \] 其中 \( \mathbf{C} = \frac{1}{n} \mathbf{X} \mathbf{X}^T \) 是协方差矩阵。通过求解特征值问题 \( \mathbf{C} \mathbf{w} = \lambda \mathbf{w} \) 得到主成分。 2.2 引入核技巧若数据非线性可分，我们通过一个非线性映射 \( \phi: \mathbb{R}^d \to \mathcal{H} \) 将数据映射到高维特征空间 \( \mathcal{H} \)。在 \( \mathcal{H} \) 中，数据变为 \( \phi(\mathbf{x}_ 1), \dots, \phi(\mathbf{x} n) \)。假设映射后的数据已中心化（即 \( \sum_ i \phi(\mathbf{x} i) = 0 \)），则特征空间中的协方差矩阵为： \[ \mathbf{C} \phi = \frac{1}{n} \sum {i=1}^n \phi(\mathbf{x} i) \phi(\mathbf{x} i)^T. \] PCA在特征空间中的特征值问题为： \[ \mathbf{C} \phi \mathbf{v} = \lambda \mathbf{v}, \] 其中 \( \mathbf{v} \) 是特征向量。由于 \( \phi \) 可能映射到无穷维空间，直接计算 \( \mathbf{v} \) 不可行。核技巧的核心思想是：特征向量 \( \mathbf{v} \) 一定位于 \( \phi(\mathbf{x}_ 1), \dots, \phi(\mathbf{x}_ n) \) 张成的子空间中，即存在系数 \( \alpha_ 1, \dots, \alpha_ n \) 使得： \[ \mathbf{v} = \sum {i=1}^n \alpha_ i \phi(\mathbf{x}_ i). \] 3. 特征空间中的特征值问题推导 3.1 代入特征方程将 \( \mathbf{v} = \sum_ {j=1}^n \alpha_ j \phi(\mathbf{x} j) \) 代入特征方程 \( \mathbf{C} \phi \mathbf{v} = \lambda \mathbf{v} \)： \[ \frac{1}{n} \sum_ {i=1}^n \phi(\mathbf{x}_ i) \phi(\mathbf{x} i)^T \left( \sum {j=1}^n \alpha_ j \phi(\mathbf{x} j) \right) = \lambda \sum {j=1}^n \alpha_ j \phi(\mathbf{x} j). \] 简化左侧： \[ \frac{1}{n} \sum {i=1}^n \phi(\mathbf{x} i) \left( \sum {j=1}^n \alpha_ j \phi(\mathbf{x}_ i)^T \phi(\mathbf{x} j) \right) = \lambda \sum {j=1}^n \alpha_ j \phi(\mathbf{x}_ j). \] 定义核函数 \( k(\mathbf{x}_ i, \mathbf{x}_ j) = \phi(\mathbf{x}_ i)^T \phi(\mathbf{x} j) \)，则上式化为： \[ \frac{1}{n} \sum {i=1}^n \phi(\mathbf{x} i) \left( \sum {j=1}^n \alpha_ j k(\mathbf{x}_ i, \mathbf{x} j) \right) = \lambda \sum {j=1}^n \alpha_ j \phi(\mathbf{x}_ j). \] 3.2 转化为核矩阵方程将等式两边同时左乘 \( \phi(\mathbf{x} l)^T \)（\( l = 1, \dots, n \)）： \[ \frac{1}{n} \sum {i=1}^n k(\mathbf{x}_ l, \mathbf{x} i) \left( \sum {j=1}^n \alpha_ j k(\mathbf{x}_ i, \mathbf{x} j) \right) = \lambda \sum {j=1}^n \alpha_ j k(\mathbf{x}_ l, \mathbf{x} j). \] 定义核矩阵 \( \mathbf{K} \in \mathbb{R}^{n \times n} \)，其中 \( K {ij} = k(\mathbf{x}_ i, \mathbf{x}_ j) \)，并令 \( \boldsymbol{\alpha} = [ \alpha_ 1, \dots, \alpha_ n ]^T \)，则上式可写为矩阵形式： \[ \frac{1}{n} \mathbf{K} \mathbf{K} \boldsymbol{\alpha} = \lambda \mathbf{K} \boldsymbol{\alpha}. \] 假设 \( \mathbf{K} \) 可逆，两边左乘 \( \mathbf{K}^{-1} \) 可得： \[ \frac{1}{n} \mathbf{K} \boldsymbol{\alpha} = \lambda \boldsymbol{\alpha}. \] 更常见的情况是直接求解广义特征值问题： \[ \mathbf{K} \boldsymbol{\alpha} = n \lambda \boldsymbol{\alpha}. \] 令 \( \lambda' = n \lambda \)，则问题简化为标准特征值问题： \[ \mathbf{K} \boldsymbol{\alpha} = \lambda' \boldsymbol{\alpha}. \] 4. 核矩阵中心化处理在实际应用中，映射后的数据 \( \phi(\mathbf{x} i) \) 未必中心化。因此，我们需要对核矩阵进行中心化，使其对应于中心化后的特征向量内积。中心化后的核矩阵 \( \tilde{\mathbf{K}} \) 定义为： \[ \tilde{K} {ij} = \left( \phi(\mathbf{x} i) - \frac{1}{n} \sum {m=1}^n \phi(\mathbf{x} m) \right)^T \left( \phi(\mathbf{x} j) - \frac{1}{n} \sum {l=1}^n \phi(\mathbf{x} l) \right). \] 展开并利用核函数表示： \[ \tilde{K} {ij} = K {ij} - \frac{1}{n} \sum_ {m=1}^n K_ {im} - \frac{1}{n} \sum_ {l=1}^n K_ {lj} + \frac{1}{n^2} \sum_ {m,l=1}^n K_ {ml}. \] 这等价于矩阵运算： \[ \tilde{\mathbf{K}} = \mathbf{K} - \mathbf{1}_ n \mathbf{K} - \mathbf{K} \mathbf{1}_ n + \mathbf{1}_ n \mathbf{K} \mathbf{1}_ n, \] 其中 \( \mathbf{1}_ n \) 是 \( n \times n \) 矩阵，所有元素为 \( 1/n \)。 5. 特征向量归一化与投影计算 5.1 特征向量归一化求解 \( \tilde{\mathbf{K}} \boldsymbol{\alpha} = \lambda' \boldsymbol{\alpha} \) 得到特征值 \( \lambda'_ k \) 和特征向量 \( \boldsymbol{\alpha}_ k \)。注意，特征空间中的特征向量 \( \mathbf{v}_ k \) 需满足单位长度约束 \( \mathbf{v}_ k^T \mathbf{v} k = 1 \)。代入 \( \mathbf{v} k = \sum {i=1}^n \alpha {k,i} \phi(\mathbf{x} i) \)： \[ \mathbf{v} k^T \mathbf{v} k = \sum {i,j=1}^n \alpha {k,i} \alpha {k,j} \phi(\mathbf{x}_ i)^T \phi(\mathbf{x}_ j) = \boldsymbol{\alpha}_ k^T \tilde{\mathbf{K}} \boldsymbol{\alpha}_ k = \lambda'_ k \boldsymbol{\alpha}_ k^T \boldsymbol{\alpha}_ k. \] 因此，归一化条件为 \( \lambda'_ k \boldsymbol{\alpha}_ k^T \boldsymbol{\alpha}_ k = 1 \)，即： \[ \boldsymbol{\alpha}_ k \leftarrow \frac{\boldsymbol{\alpha}_ k}{\sqrt{\lambda'_ k}}. \] 5.2 新样本的投影对于新样本 \( \mathbf{x} {\text{new}} \)，其在第 \( k \) 个核主成分上的投影为： \[ t_ k = \mathbf{v} k^T \phi(\mathbf{x} {\text{new}}) = \sum {i=1}^n \alpha_ {k,i} \phi(\mathbf{x} i)^T \phi(\mathbf{x} {\text{new}}) = \sum_ {i=1}^n \alpha_ {k,i} k(\mathbf{x} i, \mathbf{x} {\text{new}}). \] 注意：核函数中的 \( \phi \) 需使用与训练数据相同的中心化处理。实际计算时，需使用中心化后的核向量 \( \tilde{\mathbf{k}} {\text{new}} \)，其中： \[ \tilde{k} {\text{new},i} = k(\mathbf{x}_ {\text{new}}, \mathbf{x} i) - \frac{1}{n} \sum {m=1}^n k(\mathbf{x} m, \mathbf{x} i) - \frac{1}{n} \sum {l=1}^n k(\mathbf{x} {\text{new}}, \mathbf{x} l) + \frac{1}{n^2} \sum {m,l=1}^n k(\mathbf{x}_ m, \mathbf{x} l). \] 则投影为 \( t_ k = \tilde{\mathbf{k}} {\text{new}}^T \boldsymbol{\alpha}_ k \)。 6. 总结与关键点核心思想：通过核函数隐式映射数据到高维空间，并在该空间执行线性PCA。数学关键：特征向量可表示为训练样本的线性组合，从而将特征值问题转化为核矩阵的特征值问题。中心化：必须对核矩阵进行中心化以对应特征空间数据中心化。计算步骤：选择核函数（如高斯核 \( k(\mathbf{x}, \mathbf{y}) = \exp(-\|\mathbf{x}-\mathbf{y}\|^2/(2\sigma^2)) \)）。计算核矩阵 \( \mathbf{K} \) 并中心化得到 \( \tilde{\mathbf{K}} \)。求解 \( \tilde{\mathbf{K}} \boldsymbol{\alpha} = \lambda' \boldsymbol{\alpha} \)，保留前 \( p \) 个最大特征值对应的特征向量 \( \boldsymbol{\alpha}_ k \)。归一化 \( \boldsymbol{\alpha}_ k \) 使得特征向量单位长度。将新样本投影到核主成分上得到降维表示。通过以上步骤，Kernel PCA能够捕捉非线性数据结构，广泛应用于图像处理、模式识别等领域。