监督NPE子空间降维算法源码

资 源 简 介

本项目致力于实现一种增强型的子空间学习算法——监督邻域保持嵌入（Supervised Neighborhood Preserving Embedding, S-NPE），用于解决高维数据的特征提取与降维问题。传统的NPE算法作为无监督流形学习方法，仅保留了数据的局部几何结构，但在分类任务中往往缺乏足够的判别力。本项目通过引入样本的类别标签信息，对标准NPE算法进行了如下改进与功能实现：1. 构建监督邻接图：在寻找最近邻时，限制搜索范围仅在同类样本中，或者利用标签信息对异类样本的距离进行惩罚，从而构建包含判别信息的近邻图；2. 局部权重优化：计算每个样本点由其同类近邻进行线性重构的权重系数，确保并在低维空间中保持这种同类间的线性重构关系；3. 判别子空间求解：通过转换优化目标，将其归结为约束条件下的广义特征值分解问题，求解出能够最大化类间距离同时保持类内局部结构的最优投影矩阵；4. 降维与验证：提供将新样本投影至低维空间的功能，并包含基于KNN分类器的算法性能评估模块，用于验证降维后数据的分类准确率。该项目主要应用于人脸识别、高光谱图像处理及手写体识别等模式识别领域。

详 情 说 明

基于监督NPE的子空间降维算法实现

项目简介

本项目实现了一种增强型的子空间学习算法——监督邻域保持嵌入（Supervised Neighborhood Preserving Embedding, S-NPE）。该算法旨在解决高维数据的特征提取与降维问题，特别适用于分类任务。

传统的NPE算法作为无监督流形学习方法，虽然能够保留数据的局部几何结构，但在缺乏类别信息引导的情况下，提取的特征往往缺乏足够的判别力。本项目通过引入样本的类别标签信息，改进了邻接图构建和权重计算过程，使其能够最大化类间距离同时保持同类样本的局部线性重构关系。

功能特性

• 高维数据模拟：内置高维合成数据集生成器，能够生成具有特定流形结构（如线性簇、非线性扭曲簇）的数据。
• 监督邻域构建：在构建近邻图时利用标签信息，强制仅在同类样本中寻找最近邻，增强了局部结构的纯度。
• 子空间特征学习：通过求解广义特征值问题，获得能够保持判别性局部结构的最优投影矩阵。
• 算法对比分析：集成了传统的PCA（主成分分析）算法作为基准，直观对比监督算法与无监督算法的差异。
• 可视化展示：提供降维后的2D散点图对比以及特征值谱图，直观展示聚类效果和能量分布。
• 量化评估：内置基于KNN分类器的评估模块，计算并对比原始空间、PCA空间及S-NPE空间的分类准确率。

系统要求

• MATLAB R2016a 或更高版本
• Statistics and Machine Learning Toolbox（用于 gscatter 绘图及统计功能）

使用方法

1. 确保MATLAB路径中包含本项目脚本。
2. 直接运行主函数即可启动流程。
3. 程序将依次执行：数据生成 -> S-NPE降维 -> PCA降维 -> 结果可视化 -> 精度评测。
4. 运行结束后，控制台将输出各阶段的分类准确率，并弹出包含对比图表的图形窗口。

代码实现逻辑详解

本项目的主逻辑分为四个主要步骤，严格遵循以下流程：

1. 环境初始化与数据生成

• 程序首先清理工作区并设置固定随机种子（42），以确保实验结果的可复现性。
• 生成D=100维的高维数据，包含3个类别，每类60个样本。

* 类别1：基于高斯分布生成的线性簇。 * 类别2：在随机基底上添加了正弦函数非线性扭曲和位移。 * 类别3：具有特定稀疏偏移特征的类簇。

• 所有数据在进入算法前均经过零均值化（Zero-mean）预处理。

2. S-NPE 算法执行与对比计算

• 调用核心算法函数 run_super_npe，传入归一化后的数据、标签、近邻数（K=8）和目标维度（d=2）。
• 作为对比，利用SVD分解计算标准PCA投影，提取前2个主成分作为基准降维结果。

3. 多维可视化

• 创建一个包含三个子图的窗口：

* 子图1：展示PCA降维后的数据分布，通常类间混叠较多。 * 子图2：展示S-NPE降维后的数据分布，验证同类样本的聚集程度和异类样本的分离度。 * 子图3：绘制S-NPE求解过程中的前20个广义特征值谱，用于分析子空间的结构特征。

4. 性能评估（KNN分类准确率）

• 使用1最近邻（1-NN）分类器对降维效果进行量化。
• 采用70%训练集、30%测试集的随机划分策略。
• 分别计算并输出以下三种情况的分类准确率：

1. 原始100维高维空间。 2. PCA降维后的2维子空间。 3. S-NPE降维后的2维子空间。

关键算法与实现细节

核心函数：run_super_npe

该函数实现了S-NPE算法的核心数学推导，具体步骤如下：

1. 构建监督邻接图：

与传统NPE不同，该实现在寻找每个样本 $x_i$ 的 $K$ 个近邻时，首先根据 labels 筛选出同类样本，仅在同类样本集合中计算欧氏距离并选取最近邻。这确保了局部重构关系完全基于同类信息。

1. 局部权重优化：

对于每个样本，计算其由同类近邻线性重构的权重系数。 * 构造局部Gram矩阵 $G = Z^T Z$，其中 $Z$ 为邻居节点与中心节点的差值。 * 为了防止 $G$ 矩阵奇异（即不可逆），代码中加入了一个微小的正则化项：$G + I times 10^{-3} times trace(G)$。 * 通过求解线性方程组 $G backslash mathbf{1}$ 并归一化，得到权重向量。

1. 矩阵构建：

* 计算稀疏权重矩阵 $W$。 * 计算中间矩阵 $M = (I - W)^T (I - W)$。

1. 求解广义特征值问题：

算法将优化目标转换为求解广义特征值问题 $A v = lambda B v$。 * 矩阵 A：$X M X^T$，为了数值稳定性，代码强制对其进行了对称化处理 $(A + A^T)/2$。 * 矩阵 B：$X X^T$，同样进行了对称化处理，并加入了 $10^{-6}$ 的微小扰动以保证正定性，防止求解时出现数值不稳定。 * 使用 eig 函数求解，并取实部特征值。

1. 投影与映射：

对特征值进行升序排序，丢弃可能的虚部，选取最小的 $d$ 个特征值对应的特征向量作为投影矩阵 $W_{proj}$。最后将数据投影到低维空间。

辅助函数：evaluate_knn

• 这是一个通用的评估模块，接受数据和标签。
• 它实现了简单的留出法（Hold-out）交叉验证。
• 对测试集中的每个样本，计算其与训练集中所有样本的距离，选取最近的 $k$ 个邻居进行多数投票（Mode），以此计算预测准确率。