线性判别分析(Linear Discriminant Analysis,LDA)是一种常用的模式识别算法,它在降维和分类问题中被广泛应用。LDA 的主要思想是,将数据投影到一个低维空间中,并使得不同类别的数据点之间的距离最大化,同一类别内的数据点之间的距离最小化。
下面我们来详细讲解一下 LDA 的算法原理。
假设我们有一个数据集 D=(x1,y1),(x2,y2),⋯ ,(xn,yn)D={(x_1,y_1),(x_2,y_2),cdots,(x_n,y_n)},其中 xi∈Rdx_i in mathbb{R}^d 表示样本的特征向量,yiy_i 表示样本的标签(假设样本属于 kk 个类别之一)。我们的目标是将这些数据投影到一个 mm 维的子空间中,使得不同类别的样本点之间的距离最大化,同一类别内的样本点之间的距离最小化。
假设我们已经将数据投影到了一个 mm 维的子空间中,其中 m<dm < d,我们可以将样本的特征向量表示为 z=(z1,z2,⋯ ,zm)Tz=(z_1,z_2,cdots,z_m)^T,其中 ziz_i 表示样本在第 ii 个维度上的投影。我们用 μiboldsymbol{mu}_i 表示第 ii 类样本在子空间中的均值向量,用 Σiboldsymbol{Sigma}_i 表示第 ii 类样本在子空间中的协方差矩阵。
我们的目标是找到一个投影矩阵 W∈Rd×mboldsymbol{W} in mathbb{R}^{d times m},使得样本在投影后的子空间中的类别可分性最大化。具体来说,我们可以通过最大化两个指标来实现这个目标:
- 类间距离最大化(Between-Class Scatter Matrix):表示不同类别样本的投影之间的距离。它的计算公式为:
SB=∑i=1kNi(μi−μ)(μi−μ)TS_B = textstylesum_{i=1}^{k} N_i(mu_i-mu)(mu_i-mu)^T
其中 NiN_i 表示第 ii 类样本的数量,μboldsymbol{mu} 表示所有样本的均值向量,μiboldsymbol{mu}_i 表示第 ii 类样本在子空间中的均值向量。
类内距离最小化(Within-Class Scatter Matrix):表示同一类别样本之间的投影距离。它的计算公式为:
SW=∑i=1kΣiS_W = textstylesum_{i=1}^{k} Sigma_i
将两个指标综合起来,我们可以定义一个目标函数:
J(W)=tr(WrSBW)tr(WrSWW)boldsymbol{J}(boldsymbol{W}) = frac{mathrm{tr}(W^rS_BW)}{mathrm{tr}(W^rS_WW)}
其中 tr(⋅)mathrm{tr}(cdot) 表示矩阵的迹(即矩阵对角线上的元素之和)。我们的目标是最大化目标函数 J(W)boldsymbol{J}(boldsymbol{W}),找到一个最优的投影矩阵 Wboldsymbol{W}。
我们可以通过求解广义特征值问题来得到最优的投影矩阵 Wboldsymbol{W}。具体来说,我们需要计算 SW−1SBboldsymbol{S}_W^{-1}boldsymbol{S}_B 的最大 mm 个特征值对应的特征向量,将这些特征向量组成一个矩阵 Wboldsymbol{W},即为最优的投影矩阵。
LDA 算法的代码实现如下:
import numpy as np
def lda(X, y, m):
"""
X: shape (n, d), input data
y: shape (n,), labels
m: int, number of dimensions to project to
"""
classes = np.unique(y)
n_classes = len(classes)
n_samples, n_features = X.shape
# Compute mean of each class
means = np.zeros((n_classes, n_features))
for i, c in enumerate(classes):
Xc = X[y == c]
means[i] = np.mean(Xc, axis=0)
# Compute within-class scatter matrix
Sw = np.zeros((n_features, n_features))
for i, c in enumerate(classes):
Xc = X[y == c]
Xc_centered = Xc - means[i]
Sw += Xc_centered.T @ Xc_centered
# Compute between-class scatter matrix
mu = np.mean(X, axis=0)
Sb = np.zeros((n_features, n_features))
for i, c in enumerate(classes):
Ni = len(X[y == c])
mu_i = means[i]
Sb += Ni * (mu_i - mu)[:, None] @ (mu_i - mu)[None, :]
# Solve generalized eigenvalue problem
eigvals, eigvecs = np.linalg.eig(np.linalg.inv(Sw) @ Sb)
eigvecs = eigvecs[:, np.argsort(eigvals)[::-1][:m]]
# Project data onto subspace
X_lda = X @ eigvecs
return X_lda
其中,X 是输入数据,y 是标签,m 是要投影到的维度。函数首先计算每个类别的均值向量 means,然后计算类内协方差矩阵 Sw 和类间协方差矩阵 Sb,最后通过求解广义特征值问题得到最优的投影矩阵 eigvecs,将数据投影到子空间并返回投影后的数据 X_lda。
下面我们使用 scikit-learn 库中的 LDA 实现对鸢尾花数据集进行降维并可视化。首先加载数据集并进行数据预处理:
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler
# Load dataset
iris = load_iris()
X, y = iris.data, iris.target
# Standardize data
scaler = StandardScaler()
X_std = scaler.fit_transform(X)
然后使用 LDA 进行降维:
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis as LDA
# Perform LDA
lda = LDA(n_components=2)
X_lda = lda.fit_transform(X_std, y)
最后,我们可以将投影后的数据进行可视化:
import matplotlib.pyplot as plt
# Plot results
plt.scatter(X_lda[:, 0], X_lda[:, 1], c=y)
plt.xlabel('LD1')
plt.ylabel('LD2')
plt.show()
这将显示一个二维散点图,其中每个点代表一个样本,其颜色对应于其类别。可以看到,LDA 成功地将数据投影到了一个新的低维子空间,并且不同类别的数据点在这个子空间中分离得更好。