LMNN大间隔最近邻监督距离度量学习系统

资 源 简 介

本项目实现了一种高效的监督式距离度量学习算法，即大间隔最近邻（Large Margin Nearest Neighbor, LMNN）算法。该算法是目前监督距离度量学习领域中效果最好的方法之一，旨在通过优化手段学习一个针对特定数据集的马氏度量（Mahalanobis distance）。 其核心功能是在给定的训练数据上，学习一个线性变换矩阵，使得在变换后的特征空间中，每个样本点的k个目标邻居（属于同一类别的近邻点）被尽可能拉近，而不同类别的样本（称为侵入者）则被推离，且保持一个较大的安全间隔。 实现方法采

详 情 说 明

大间隔最近邻（LMNN）监督距离度量学习系统

本系统实现了一种基于凸优化的监督式距离度量学习算法——大间隔最近邻（LMNN）。其核心目标是通过学习一个线性变换矩阵，将原始特征空间转换到一个新的度量空间中。在这个新空间中，同类样本被相互拉近，而异类样本被推离，从而优化k-最近邻（kNN）分类器的性能。

项目介绍

距离度量学习是机器学习中的重要任务，旨在根据数据的标签信息自动学习出最适合该任务的距离计算方式。本项目实现的LMNN算法通过在马氏度量框架下建立大间隔约束，解决了传统欧氏距离在处理复杂分布、高维特征及存在噪声数据时表现不佳的问题。该系统不仅包含了核心的优化算法，还集成了数据生成、性能评估及结果可视化等完整流程。

功能特性

1. 模拟高维数据集生成：能够自动生成具有重合性的多类高维正态分布数据，用于模拟真实世界中具有挑战性的分类场景。
2. 目标邻居预处理：针对每个训练样本，在同类中自动筛选出k个最接近的样本作为“目标邻居”，建立初始的吸引力结构。
3. 大间隔凸优化：采用子梯度下降法极小化由“吸引项”和“排斥项”组成的代价函数。
4. 侵入者检测机制：在迭代过程中动态识别违反大间隔约束的异类点（即侵入者），并触发排斥能量函数。
5. 性能对比分析：自动对比欧氏距离与学习后的马氏距离在kNN分类下的准确率，直观展现度量学习的提升效果。
6. 多维状态可视化：利用主成分分析（PCA）技术将优化前后的特征空间降维并可视化，动态展示类别分离度的变化。

实现逻辑与算法细节

系统按照以下逻辑步骤运行：

1. 数据初始化与划分

系统首先生成150个4维特征的样本，分为3个类别。数据分布被设计为具有一定的重叠性以测试算法的纠错能力。数据集按70%和30%的比例划分为训练集与测试集。

1. 确定目标邻居（Target Neighbors）

在训练阶段，算法为每个样本寻找k个同类近邻点。这些点在优化过程中产生的梯度会将原本距离较远的同类样本拉近。

1. 梯度下降与矩阵更新

优化算法基于代价函数计算总梯度。 * 吸引项（Pull Loss）：计算训练样本与其目标邻居之间的总距离平方和。这部分在迭代前预先计算为固定的矩阵。 * 排斥项（Push Loss）：在每次迭代中，寻找那些进入了“目标邻居+安全间隔”半径内的异类样本。这部分属于活跃约束，随变换矩阵L的更新而动态变化。 * 矩阵L更新：通过计算代价函数相对于线性变换L的偏导数，利用预设的学习率和迭代步数，不断调整空间映射关系。

1. 马氏度量评估

优化完成后，学习到的线性变换L被用来构建马氏度量矩阵M（M = L'L）。系统使用3-NN算法在测试集上分别运行欧氏距离和马氏距离度量，通过对比正确率来验证学习效果。

关键函数与实现细节

1. 子梯度下降：

算法没有直接求解闭式解（因为排斥项的非光滑性），而是通过在每一轮迭代中查找活跃的“三元组”约束（样本i，目标邻居j，侵入者l）来计算子梯度。

1. 代价函数平衡：

通过mu参数（默认0.5）平衡吸引和排斥的作用。mu越大，系统对异类侵入的惩罚越重，旨在获得更大的分类间隔。

1. 停止准则：

系统通过监测相邻两次迭代之间的Loss差值来判断是否收敛。当初代代价函数的变化量小于设定的阈值（tol）时，算法自动停止。

1. 可视化映射：

通过提取学习到的线性变换对全量数据实施特征转换，并使用PCA抽取主成分，在二维平面上描绘出类间的分布变化。

使用方法

1. 配置环境：确保您的计算机上安装了MATLAB环境。
2. 运行脚本：直接执行脚本，程序将自动开始模拟数据生成。
3. 观察输出：控制台将实时打印每一轮迭代的Loss值和当前的优化进度。
4. 查看结果：优化结束后，程序将自动弹出一个对比图窗口，分别显示原始空间和学习后空间的PCA视图，并输出最终的线性变换矩阵L和准确率统计。

系统要求

• 软件环境：MATLAB R2016a 或更高版本。
• 工具箱要求：

* Statistics and Machine Learning Toolbox（用于正态分布生成及PCA降维）。

• 硬件建议：标准PC环境即可，算法针对本规模数据集具备秒级运行效率。