基于核的线性判别分析（Kernel Linear Discriminant Analysis, K-LDA）的数学推导与非线性分类过程
字数 6145 2025-12-19 22:37:56

基于核的线性判别分析（Kernel Linear Discriminant Analysis, K-LDA）的数学推导与非线性分类过程

题目描述

线性判别分析（LDA）是一种经典的监督降维与分类方法，其核心思想是寻找一个投影方向，使得类间散度最大、类内散度最小。然而，LDA本质上是线性的，无法处理非线性可分的复杂数据。核线性判别分析（K-LDA） 通过“核技巧”（Kernel Trick）将原始数据隐式映射到一个高维（甚至无限维）的再生核希尔伯特空间（RKHS），然后在该特征空间中执行标准的LDA。本题目将深入讲解K-LDA的数学推导、求解过程及其非线性分类的实现步骤。

解题过程

1. 背景回顾：线性判别分析（LDA）的核心目标

对于一个C类分类问题，给定样本集 { (x_i, y_i) }，其中 \(x_i \in \mathbb{R}^d\)， \(y_i \in \{1, 2, ..., C\}\)。
LDA的目标是找到一个投影方向 \(w \in \mathbb{R}^d\)，使得投影后的数据：

  • 类间散度（Between-class scatter） 尽可能大
  • 类内散度（Within-class scatter） 尽可能小

这可以形式化为最大化广义瑞利商（Generalized Rayleigh Quotient）：

\[J(w) = \frac{w^T S_b w}{w^T S_w w} \]

其中：

  • \(S_b = \sum_{c=1}^{C} n_c (\mu_c - \mu)(\mu_c - \mu)^T\) 是类间散度矩阵，\(n_c\) 是第c类的样本数，\(\mu_c\) 是第c类的均值向量，\(\mu\) 是所有样本的全局均值向量。
  • \(S_w = \sum_{c=1}^{C} \sum_{x_i \in \text{Class } c} (x_i - \mu_c)(x_i - \mu_c)^T\) 是类内散度矩阵。

最优投影方向 \(w\) 是广义特征值问题 \(S_b w = \lambda S_w w\) 的最大特征值对应的特征向量。对于多类问题，可取前 \(C-1\) 个最大特征值对应的特征向量构成投影矩阵 \(W \in \mathbb{R}^{d \times (C-1)}\)。

2. 从线性到非线性：核技巧的思想

当数据非线性可分时，LDA的线性投影面可能无法有效分离不同类别。核技巧的核心思想是：

  • 引入一个非线性映射 \(\phi: \mathbb{R}^d \to \mathcal{H}\)，将原始数据 \(x_i\) 映射到高维特征空间 \(\mathcal{H}\) 中的 \(\phi(x_i)\)。
  • 在特征空间 \(\mathcal{H}\) 中，数据的线性分离性可能大大增强。
  • 但 \(\phi\) 的显式形式通常未知或维度极高，因此我们避免直接计算 \(\phi(x)\)，而是通过一个核函数 \(k(x, y) = \langle \phi(x), \phi(y) \rangle_{\mathcal{H}}\) 来隐式地计算特征空间中的内积。常用的核函数包括高斯核（RBF核）、多项式核等。

因此，K-LDA的目标是：在特征空间 \(\mathcal{H}\) 中寻找一个投影方向 \(w_{\phi} \in \mathcal{H}\)，使得广义瑞利商最大化。

3. K-LDA的数学推导

步骤1：特征空间中的LDA目标
在特征空间中，样本变为 \(\phi(x_i)\)。特征空间中的类间散度矩阵 \(S_b^{\phi}\) 和类内散度矩阵 \(S_w^{\phi}\) 定义为：

\[S_b^{\phi} = \sum_{c=1}^{C} n_c (\mu_c^{\phi} - \mu^{\phi})(\mu_c^{\phi} - \mu^{\phi})^T, \quad S_w^{\phi} = \sum_{c=1}^{C} \sum_{x_i \in \text{Class } c} (\phi(x_i) - \mu_c^{\phi})(\phi(x_i) - \mu_c^{\phi})^T \]

其中 \(\mu_c^{\phi} = \frac{1}{n_c} \sum_{x_i \in \text{Class } c} \phi(x_i)\) 是第c类在特征空间中的均值向量，\(\mu^{\phi} = \frac{1}{n} \sum_{i=1}^{n} \phi(x_i)\) 是全局均值向量。

广义瑞利商为：

\[J(w_{\phi}) = \frac{w_{\phi}^T S_b^{\phi} w_{\phi}}{w_{\phi}^T S_w^{\phi} w_{\phi}} \]

步骤2：表示定理与对偶表示
由于 \(w_{\phi}\) 位于由 \(\{ \phi(x_i) \}_{i=1}^{n}\) 张成的空间中（因为优化目标只涉及样本的映射），根据表示定理，最优投影方向 \(w_{\phi}\) 可表示为所有训练样本映射的线性组合：

\[w_{\phi} = \sum_{i=1}^{n} \alpha_i \phi(x_i) = \Phi \alpha \]

其中 \(\Phi = [\phi(x_1), \phi(x_2), ..., \phi(x_n)]\) 是特征矩阵（在实际计算中不显式存储），\(\alpha = [\alpha_1, \alpha_2, ..., \alpha_n]^T \in \mathbb{R}^n\) 是对偶系数向量。

步骤3：将目标函数重写为关于 \(\alpha\) 的形式
我们需要将 \(J(w_{\phi})\) 中的分子和分母用 \(\alpha\) 和核矩阵表示。定义核矩阵 \(K \in \mathbb{R}^{n \times n}\)，其中 \(K_{ij} = k(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle\)。

首先，对于任意样本 \(\phi(x)\) 在方向 \(w_{\phi}\) 上的投影为：

\[w_{\phi}^T \phi(x) = \left( \sum_{i=1}^{n} \alpha_i \phi(x_i) \right)^T \phi(x) = \sum_{i=1}^{n} \alpha_i k(x_i, x) = \alpha^T k_x \]

其中 \(k_x = [k(x_1, x), k(x_2, x), ..., k(x_n, x)]^T \in \mathbb{R}^n\)。

考虑全局均值向量 \(\mu^{\phi}\) 的投影：

\[w_{\phi}^T \mu^{\phi} = w_{\phi}^T \left( \frac{1}{n} \sum_{j=1}^{n} \phi(x_j) \right) = \frac{1}{n} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i k(x_i, x_j) = \frac{1}{n} \alpha^T K 1_n \]

其中 \(1_n \in \mathbb{R}^n\) 是全1向量。

类似地，第c类的均值向量 \(\mu_c^{\phi}\) 的投影为：

\[w_{\phi}^T \mu_c^{\phi} = \frac{1}{n_c} \sum_{i=1}^{n} \sum_{x_j \in \text{Class } c} \alpha_i k(x_i, x_j) = \frac{1}{n_c} \alpha^T K 1_c \]

其中 \(1_c \in \mathbb{R}^n\) 是一个指示向量，如果样本 \(x_j\) 属于第c类，则第j个分量为1，否则为0。

步骤4：构建核类间散度矩阵 \(S_b^{\phi}\) 和类内散度矩阵 \(S_w^{\phi}\) 的核形式
在特征空间中，投影方向 \(w_{\phi}\) 下的类间散度可写为：

\[w_{\phi}^T S_b^{\phi} w_{\phi} = \sum_{c=1}^{C} n_c (w_{\phi}^T \mu_c^{\phi} - w_{\phi}^T \mu^{\phi})^2 \]

代入上述投影表达式，定义矩阵 \(M = [m_1, m_2, ..., m_C] \in \mathbb{R}^{n \times C}\)，其中第c列 \(m_c = \frac{1}{n_c} K 1_c - \frac{1}{n} K 1_n\)。则：

\[w_{\phi}^T S_b^{\phi} w_{\phi} = \alpha^T \left( \sum_{c=1}^{C} n_c m_c m_c^T \right) \alpha = \alpha^T M N M^T \alpha \]

其中 \(N = \text{diag}(n_1, n_2, ..., n_C)\)。

类似地，类内散度可写为：

\[w_{\phi}^T S_w^{\phi} w_{\phi} = \sum_{c=1}^{C} \sum_{x_i \in \text{Class } c} (w_{\phi}^T \phi(x_i) - w_{\phi}^T \mu_c^{\phi})^2 \]

定义第c类的核矩阵块 \(K^{(c)} \in \mathbb{R}^{n_c \times n_c}\)，以及对应的系数向量块 \(\alpha^{(c)}\)。经过推导（详细过程略，核心是利用中心化核矩阵），可得：

\[w_{\phi}^T S_w^{\phi} w_{\phi} = \alpha^T K W K \alpha \]

其中 \(W = \text{diag}(W_1, W_2, ..., W_C)\)，每个 \(W_c = I_{n_c} - \frac{1}{n_c} 1_{n_c} 1_{n_c}^T\) 是第c类的中心化矩阵，\(I_{n_c}\) 是单位矩阵，\(1_{n_c}\) 是全1向量。

步骤5：广义特征值问题的对偶形式
因此，广义瑞利商变为：

\[J(\alpha) = \frac{\alpha^T M N M^T \alpha}{\alpha^T K W K \alpha} \]

最大化 \(J(\alpha)\) 等价于求解广义特征值问题：

\[(M N M^T) \alpha = \lambda (K W K) \alpha \]

由于 \(K W K\) 可能奇异（特别是当 \(n > d_{\phi}\) 时，特征空间维度 \(d_{\phi}\) 可能很高），实践中通常引入一个正则化项，即求解：

\[(M N M^T) \alpha = \lambda (K W K + \eta I) \alpha \]

其中 \(\eta\) 是一个小的正数（如 \(10^{-6}\)），\(I\) 是单位矩阵，以确保矩阵可逆。

解此广义特征值问题，得到前 \(C-1\) 个最大特征值对应的特征向量 \(\alpha_1, \alpha_2, ..., \alpha_{C-1} \in \mathbb{R}^n\)，构成系数矩阵 \(A = [\alpha_1, \alpha_2, ..., \alpha_{C-1}] \in \mathbb{R}^{n \times (C-1)}\)。

4. 非线性分类过程

训练阶段：

  1. 给定训练集 \(\{ (x_i, y_i) \}_{i=1}^{n}\)。
  2. 选择核函数 \(k(\cdot, \cdot)\)（如高斯核 \(k(x, y) = \exp(-\gamma \|x - y\|^2)\)），计算核矩阵 \(K\)。
  3. 构造矩阵 \(M\)、\(N\)、\(W\) 并求解正则化后的广义特征值问题，得到系数矩阵 \(A\)。
  4. 将训练数据投影到K-LDA子空间：对每个训练样本 \(x_i\)，其投影坐标为 \(z_i = A^T k_{x_i} \in \mathbb{R}^{C-1}\)，其中 \(k_{x_i} = [k(x_1, x_i), ..., k(x_n, x_i)]^T\)。
  5. 在投影空间（\(C-1\) 维）中，对每一类计算投影后的类均值向量 \(\bar{\mu}_c = \frac{1}{n_c} \sum_{x_i \in \text{Class } c} z_i\)。

测试阶段（对新样本 \(x_{\text{test}}\) 分类）：

  1. 计算测试样本与所有训练样本的核向量：\(k_{\text{test}} = [k(x_1, x_{\text{test}}), ..., k(x_n, x_{\text{test}})]^T\)。
  2. 投影到K-LDA子空间：\(z_{\text{test}} = A^T k_{\text{test}}\)。
  3. 在投影空间中，计算 \(z_{\text{test}}\) 到每一类的均值 \(\bar{\mu}_c\) 的距离（通常使用欧氏距离或马氏距离）。
  4. 将 \(x_{\text{test}}\) 分配给距离最近的类。

总结

K-LDA通过核技巧将LDA扩展到非线性领域，其核心步骤包括：利用核函数隐式映射到高维特征空间，将对偶系数向量 \(\alpha\) 作为优化变量，将广义瑞利商重写为关于核矩阵的表达式，并求解一个广义特征值问题以获得投影方向。最终，在投影后的低维空间中进行距离度量的分类。该方法在保持LDA类别判别能力的同时，能够处理复杂的非线性可分数据。

基于核的线性判别分析（Kernel Linear Discriminant Analysis, K-LDA）的数学推导与非线性分类过程 题目描述 线性判别分析（LDA）是一种经典的监督降维与分类方法，其核心思想是寻找一个投影方向，使得类间散度最大、类内散度最小。然而，LDA本质上是线性的，无法处理非线性可分的复杂数据。 核线性判别分析（K-LDA） 通过“核技巧”（Kernel Trick）将原始数据隐式映射到一个高维（甚至无限维）的再生核希尔伯特空间（RKHS），然后在该特征空间中执行标准的LDA。本题目将深入讲解K-LDA的数学推导、求解过程及其非线性分类的实现步骤。 解题过程 1. 背景回顾：线性判别分析（LDA）的核心目标 对于一个C类分类问题，给定样本集 { (x_ i, y_ i) }，其中 \( x_ i \in \mathbb{R}^d \)， \( y_ i \in \{1, 2, ..., C\} \)。 LDA的目标是找到一个投影方向 \( w \in \mathbb{R}^d \)，使得投影后的数据： 类间散度（Between-class scatter） 尽可能大 类内散度（Within-class scatter） 尽可能小 这可以形式化为最大化 广义瑞利商（Generalized Rayleigh Quotient） ： \[ J(w) = \frac{w^T S_ b w}{w^T S_ w w} \] 其中： \( S_ b = \sum_ {c=1}^{C} n_ c (\mu_ c - \mu)(\mu_ c - \mu)^T \) 是 类间散度矩阵 ，\( n_ c \) 是第c类的样本数，\( \mu_ c \) 是第c类的均值向量，\( \mu \) 是所有样本的全局均值向量。 \( S_ w = \sum_ {c=1}^{C} \sum_ {x_ i \in \text{Class } c} (x_ i - \mu_ c)(x_ i - \mu_ c)^T \) 是 类内散度矩阵 。 最优投影方向 \( w \) 是广义特征值问题 \( S_ b w = \lambda S_ w w \) 的最大特征值对应的特征向量。对于多类问题，可取前 \( C-1 \) 个最大特征值对应的特征向量构成投影矩阵 \( W \in \mathbb{R}^{d \times (C-1)} \)。 2. 从线性到非线性：核技巧的思想 当数据非线性可分时，LDA的线性投影面可能无法有效分离不同类别。核技巧的核心思想是： 引入一个非线性映射 \( \phi: \mathbb{R}^d \to \mathcal{H} \)，将原始数据 \( x_ i \) 映射到高维特征空间 \( \mathcal{H} \) 中的 \( \phi(x_ i) \)。 在特征空间 \( \mathcal{H} \) 中，数据的线性分离性可能大大增强。 但 \( \phi \) 的显式形式通常未知或维度极高，因此我们避免直接计算 \( \phi(x) \)，而是通过一个 核函数 \( k(x, y) = \langle \phi(x), \phi(y) \rangle_ {\mathcal{H}} \) 来隐式地计算特征空间中的内积。常用的核函数包括高斯核（RBF核）、多项式核等。 因此，K-LDA的目标是：在特征空间 \( \mathcal{H} \) 中寻找一个投影方向 \( w_ {\phi} \in \mathcal{H} \)，使得广义瑞利商最大化。 3. K-LDA的数学推导 步骤1：特征空间中的LDA目标 在特征空间中，样本变为 \( \phi(x_ i) \)。特征空间中的类间散度矩阵 \( S_ b^{\phi} \) 和类内散度矩阵 \( S_ w^{\phi} \) 定义为： \[ S_ b^{\phi} = \sum_ {c=1}^{C} n_ c (\mu_ c^{\phi} - \mu^{\phi})(\mu_ c^{\phi} - \mu^{\phi})^T, \quad S_ w^{\phi} = \sum_ {c=1}^{C} \sum_ {x_ i \in \text{Class } c} (\phi(x_ i) - \mu_ c^{\phi})(\phi(x_ i) - \mu_ c^{\phi})^T \] 其中 \( \mu_ c^{\phi} = \frac{1}{n_ c} \sum_ {x_ i \in \text{Class } c} \phi(x_ i) \) 是第c类在特征空间中的均值向量，\( \mu^{\phi} = \frac{1}{n} \sum_ {i=1}^{n} \phi(x_ i) \) 是全局均值向量。 广义瑞利商为： \[ J(w_ {\phi}) = \frac{w_ {\phi}^T S_ b^{\phi} w_ {\phi}}{w_ {\phi}^T S_ w^{\phi} w_ {\phi}} \] 步骤2：表示定理与对偶表示 由于 \( w_ {\phi} \) 位于由 \( \{ \phi(x_ i) \} {i=1}^{n} \) 张成的空间中（因为优化目标只涉及样本的映射），根据表示定理，最优投影方向 \( w {\phi} \) 可表示为所有训练样本映射的线性组合： \[ w_ {\phi} = \sum_ {i=1}^{n} \alpha_ i \phi(x_ i) = \Phi \alpha \] 其中 \( \Phi = [ \phi(x_ 1), \phi(x_ 2), ..., \phi(x_ n)] \) 是特征矩阵（在实际计算中不显式存储），\( \alpha = [ \alpha_ 1, \alpha_ 2, ..., \alpha_ n ]^T \in \mathbb{R}^n \) 是对偶系数向量。 步骤3：将目标函数重写为关于 \( \alpha \) 的形式 我们需要将 \( J(w_ {\phi}) \) 中的分子和分母用 \( \alpha \) 和核矩阵表示。定义核矩阵 \( K \in \mathbb{R}^{n \times n} \)，其中 \( K_ {ij} = k(x_ i, x_ j) = \langle \phi(x_ i), \phi(x_ j) \rangle \)。 首先，对于任意样本 \( \phi(x) \) 在方向 \( w_ {\phi} \) 上的投影为： \[ w_ {\phi}^T \phi(x) = \left( \sum_ {i=1}^{n} \alpha_ i \phi(x_ i) \right)^T \phi(x) = \sum_ {i=1}^{n} \alpha_ i k(x_ i, x) = \alpha^T k_ x \] 其中 \( k_ x = [ k(x_ 1, x), k(x_ 2, x), ..., k(x_ n, x) ]^T \in \mathbb{R}^n \)。 考虑全局均值向量 \( \mu^{\phi} \) 的投影： \[ w_ {\phi}^T \mu^{\phi} = w_ {\phi}^T \left( \frac{1}{n} \sum_ {j=1}^{n} \phi(x_ j) \right) = \frac{1}{n} \sum_ {i=1}^{n} \sum_ {j=1}^{n} \alpha_ i k(x_ i, x_ j) = \frac{1}{n} \alpha^T K 1_ n \] 其中 \( 1_ n \in \mathbb{R}^n \) 是全1向量。 类似地，第c类的均值向量 \( \mu_ c^{\phi} \) 的投影为： \[ w_ {\phi}^T \mu_ c^{\phi} = \frac{1}{n_ c} \sum_ {i=1}^{n} \sum_ {x_ j \in \text{Class } c} \alpha_ i k(x_ i, x_ j) = \frac{1}{n_ c} \alpha^T K 1_ c \] 其中 \( 1_ c \in \mathbb{R}^n \) 是一个指示向量，如果样本 \( x_ j \) 属于第c类，则第j个分量为1，否则为0。 步骤4：构建核类间散度矩阵 \( S_ b^{\phi} \) 和类内散度矩阵 \( S_ w^{\phi} \) 的核形式 在特征空间中，投影方向 \( w_ {\phi} \) 下的类间散度可写为： \[ w_ {\phi}^T S_ b^{\phi} w_ {\phi} = \sum_ {c=1}^{C} n_ c (w_ {\phi}^T \mu_ c^{\phi} - w_ {\phi}^T \mu^{\phi})^2 \] 代入上述投影表达式，定义矩阵 \( M = [ m_ 1, m_ 2, ..., m_ C] \in \mathbb{R}^{n \times C} \)，其中第c列 \( m_ c = \frac{1}{n_ c} K 1_ c - \frac{1}{n} K 1_ n \)。则： \[ w_ {\phi}^T S_ b^{\phi} w_ {\phi} = \alpha^T \left( \sum_ {c=1}^{C} n_ c m_ c m_ c^T \right) \alpha = \alpha^T M N M^T \alpha \] 其中 \( N = \text{diag}(n_ 1, n_ 2, ..., n_ C) \)。 类似地，类内散度可写为： \[ w_ {\phi}^T S_ w^{\phi} w_ {\phi} = \sum_ {c=1}^{C} \sum_ {x_ i \in \text{Class } c} (w_ {\phi}^T \phi(x_ i) - w_ {\phi}^T \mu_ c^{\phi})^2 \] 定义第c类的核矩阵块 \( K^{(c)} \in \mathbb{R}^{n_ c \times n_ c} \)，以及对应的系数向量块 \( \alpha^{(c)} \)。经过推导（详细过程略，核心是利用中心化核矩阵），可得： \[ w_ {\phi}^T S_ w^{\phi} w_ {\phi} = \alpha^T K W K \alpha \] 其中 \( W = \text{diag}(W_ 1, W_ 2, ..., W_ C) \)，每个 \( W_ c = I_ {n_ c} - \frac{1}{n_ c} 1_ {n_ c} 1_ {n_ c}^T \) 是第c类的中心化矩阵，\( I_ {n_ c} \) 是单位矩阵，\( 1_ {n_ c} \) 是全1向量。 步骤5：广义特征值问题的对偶形式 因此，广义瑞利商变为： \[ J(\alpha) = \frac{\alpha^T M N M^T \alpha}{\alpha^T K W K \alpha} \] 最大化 \( J(\alpha) \) 等价于求解广义特征值问题： \[ (M N M^T) \alpha = \lambda (K W K) \alpha \] 由于 \( K W K \) 可能奇异（特别是当 \( n > d_ {\phi} \) 时，特征空间维度 \( d_ {\phi} \) 可能很高），实践中通常引入一个正则化项，即求解： \[ (M N M^T) \alpha = \lambda (K W K + \eta I) \alpha \] 其中 \( \eta \) 是一个小的正数（如 \( 10^{-6} \)），\( I \) 是单位矩阵，以确保矩阵可逆。 解此广义特征值问题，得到前 \( C-1 \) 个最大特征值对应的特征向量 \( \alpha_ 1, \alpha_ 2, ..., \alpha_ {C-1} \in \mathbb{R}^n \)，构成系数矩阵 \( A = [ \alpha_ 1, \alpha_ 2, ..., \alpha_ {C-1} ] \in \mathbb{R}^{n \times (C-1)} \)。 4. 非线性分类过程 训练阶段： 给定训练集 \( \{ (x_ i, y_ i) \}_ {i=1}^{n} \)。 选择核函数 \( k(\cdot, \cdot) \)（如高斯核 \( k(x, y) = \exp(-\gamma \|x - y\|^2) \)），计算核矩阵 \( K \)。 构造矩阵 \( M \)、\( N \)、\( W \) 并求解正则化后的广义特征值问题，得到系数矩阵 \( A \)。 将训练数据投影到K-LDA子空间：对每个训练样本 \( x_ i \)，其投影坐标为 \( z_ i = A^T k_ {x_ i} \in \mathbb{R}^{C-1} \)，其中 \( k_ {x_ i} = [ k(x_ 1, x_ i), ..., k(x_ n, x_ i) ]^T \)。 在投影空间（\( C-1 \) 维）中，对每一类计算投影后的类均值向量 \( \bar{\mu} c = \frac{1}{n_ c} \sum {x_ i \in \text{Class } c} z_ i \)。 测试阶段（对新样本 \( x_ {\text{test}} \) 分类）： 计算测试样本与所有训练样本的核向量：\( k_ {\text{test}} = [ k(x_ 1, x_ {\text{test}}), ..., k(x_ n, x_ {\text{test}}) ]^T \)。 投影到K-LDA子空间：\( z_ {\text{test}} = A^T k_ {\text{test}} \)。 在投影空间中，计算 \( z_ {\text{test}} \) 到每一类的均值 \( \bar{\mu}_ c \) 的距离（通常使用欧氏距离或马氏距离）。 将 \( x_ {\text{test}} \) 分配给距离最近的类。 总结 K-LDA通过核技巧将LDA扩展到非线性领域，其核心步骤包括：利用核函数隐式映射到高维特征空间，将对偶系数向量 \( \alpha \) 作为优化变量，将广义瑞利商重写为关于核矩阵的表达式，并求解一个广义特征值问题以获得投影方向。最终，在投影后的低维空间中进行距离度量的分类。该方法在保持LDA类别判别能力的同时，能够处理复杂的非线性可分数据。