Self-weighted learning framework for adaptive locality discriminantanalysis
自加权学习框架用于自适应局部判别分析
https://www.sciencedirect.com/science/article/pii/S003132032200259X
摘要
线性判别分析（LDA）是最重要的降维技术之一，被广泛应用于许多领域。然而，传统的LDA算法旨在从数据中捕获全局结构，而忽略了局部信息。这可能导致LDA在一些具有复杂几何分布的真实世界数据集中失败。尽管有许多先前的研究专注于保留局部信息，但它们都面临同样的问题：从原始空间获得的成对数据点的邻域关系可能不可靠，特别是在噪声较大的情况下。因此，我们提出了一种新颖的自加权学习框架，称为自加权自适应局部判别分析（SALDA），用于基于局部感知的降维。所提出的框架可以自适应地学习一个内在的低维子空间，以便我们可以在理想的子空间下探索样本之间更好的邻域关系。此外，我们的模型可以自动学习为同一类中的成对数据点分配权重，并且与其他经典的局部感知方法相比不需要额外的参数。最后，实验结果表明，该算法在合成数据集和真实世界基准数据集上均具有有效性和优越性。
关键词：监督降维、线性判别分析、重加权方法
- 引言
在许多现实世界的应用中，例如生物信息学[1,2]、医学图像分析[3,4]和人脸识别[5,6]，确实存在大量高维数据。这些具有众多冗余特征的高维数据通常会降低实际技术的性能，例如高光谱图像中的分类问题[7,8]。幸运的是，基于一个合理的假设——即高维数据很可能位于一个低维流形上，降维成为提取少量判别性特征的常用方法。作为一种分析高维数据的关键技术，降维在机器学习及其他领域中发挥着重要作用。
降维的目标是减少冗余特征，同时保留数据的内在信息。在过去二十年中，降维问题吸引了全球学者越来越多的关注。因此，近年来提出了许多扩展算法，尤其是两类经典算法：主成分分析（PCA）[9]和线性判别分析（LDA）[10]。对于无监督算法PCA而言，它通过全局保留原始数据中的最大协方差信息，有效解决降维问题。与PCA不同，LDA是一种有监督方法，能够学习一个最优投影矩阵，使得同类数据点之间的距离最小化，而不同类之间的距离最大化。本文聚焦于LDA算法的研究。
LDA算法在降维领域中扮演着重要角色，并在有监督学习中表现优异。为解决相关问题，研究者已提出多种LDA的扩展算法，例如半监督LDA（SLDA）[11]和正则化最大-最小LDA（MMLDA）[12]。然而，这类LDA算法仍存在一些缺陷。第一个瓶颈是小样本问题（Small Sample Size, SSS）[13]，当数据维度大于样本数量时经常出现。第二个瓶颈是过度降维问题（over-reducing problem）[14]，这是因为LDA算法受其模型约束，最多只能将数据维度降至c−1（其中c表示数据中的类别数量），因此可能不适用于类别较多的数据集。最后，LDA算法基于高斯分布假设；尽管它们擅长处理高斯分布数据，但对于更复杂的数据却难以有效处理。这主要是因为传统LDA算法仅关注捕获数据的全局结构，而忽略了局部信息，导致其在现实应用中稳定性不足。
针对上述三个问题，已有许多方法被提出以提升LDA算法的性能。近年来，过度降维和小样本（SSS）问题已通过传统LDA的变体[15,16]等方法得到有效解决。此外，不同于Fisher准则，Li等人[17]基于最大间隔准则（Maximum Margin Criterion, MMC）提出了一些新的特征提取器来应对SSS问题。为进一步克服上述LDA的第三个问题，图学习方法[18,19]被引入LDA框架。文献[20]提出了一种LDA的扩展算法——局部Fisher判别分析（Local Fisher Discriminant Analysis, LFDA），该方法在最大化类间可分性的同时，能够捕捉类内的局部结构。此外，Cai等人[21]利用k近邻算法（KNN）[22]构建类内图和类间图，并提出了局部敏感判别分析（Locality Sensitive Discriminant Analysis, LSDA）模型，将原始数据集投影到一个新的低维子空间。与此同时，Nie等人[23]提出了一种成对形式的LDA，称为邻域MinMax投影（Neighborhood MinMax Projection, NMMP），旨在最小化同类成对点之间的距离，并尽可能分离不同类的数据点。此外，Fan等人[24]提出了一种名为局部线性判别分析（Local Linear Discriminant Analysis, LLDA）的新模型，可学习一个变换矩阵以处理复杂数据集。然而，该算法需要使用整个输入数据集的一部分来获取变换矩阵，因此难以有效处理大规模数据集。
最后但同样重要的是，对于大量基于局部感知（locality-aware）的方法，通常采用KNN技术作为预处理步骤来构建相似性图。因此，图的质量在很大程度上依赖于近邻数量k的选择。此外，这些方法通常基于原始空间中的距离度量来学习数据样本间的邻接关系。然而，直接在原始空间中使用距离度量并不可靠，因为本质上相似的点在原始空间的距离度量下可能相距甚远。关于这一观点，我们将在“相关工作”一节中给出更详细的说明。
因此，本文提出了一种新颖的自加权自适应局部判别分析（Self-Weighted Adaptive Locality Discriminant Analysis, SALDA）框架，以解决上述问题。该框架通过拉近本质相似的点、推远不相似的点来学习变换矩阵。与大多数局部感知算法类似，SALDA专注于探索数据点的局部邻域关系。本文的主要贡献如下：
- 与传统LDA方法需要额外步骤先构建相似性图不同，我们将图学习的思想嵌入LDA方法中，进一步提出了一种通用的降维框架SALDA。通过挖掘数据的局部结构，SALDA能够处理更复杂的分布数据，例如非高斯数据和多模态数据。
- 与当前局部感知技术通常需在原始数据空间中使用KNN构建邻接图不同，我们的SALDA方法能够自动探索数据点之间的邻接关系，无需引入额外的流程和参数。此外，我们的方法基于目标子空间中的距离（而非原始空间）来发现邻接关系，从而使SALDA对噪声更具鲁棒性和可靠性。
- 为求解所提出的SALDA框架，我们设计了一种基于重加权（re-weighted）方法的通用高效算法，并在理论上证明了该算法的收敛性。在合成数据集和八个真实世界数据集上的实验结果表明，我们的SALDA方法优于其他经典降维算法。
本文是对会议版本[25]的实质性扩展。与先前版本相比，我们在本文中进一步阐释了SALDA旨在解决的问题，并通过图1和图2提供了可视化解释。此外，我们扩展了所提出的模型，设计了一个更适合处理降维问题的框架，并提出了一种统一的优化算法来求解该框架。我们对所提框架进行了理论分析，并证明了其收敛性。在实验部分，我们在合成数据和八个真实世界数据集上验证了算法性能，并进一步将SALDA与其他前沿方法进行了比较。实验结果充分展示了SALDA算法的优越性。此外，本文还开展了算法收敛性分析以及SALDA中超参数p的敏感性分析，在八个基准数据集上的实验结果验证了SALDA算法的鲁棒性。
本文其余部分组织如下：第2节简要回顾LDA；第3节提出用于降维的自加权自适应局部判别分析（SALDA）框架，并相应设计了一种高效的优化算法；第4节对SALDA进行理论分析并介绍若干扩展；第5节展示所提方法的实验结果；最后，第6节对全文进行总结。
- 相关工作
在本节中，我们将回顾传统的线性判别分析方法（LDA），并证明根据所提出模型的推导，LDA 会赋予同一类中的样本相等的权重。因此，这使得 LDA 仅关注数据中的全局结构。对于如图1所示的复杂分布数据，传统LDA模型可能会陷入平凡解。因此，在我们的工作中，我们提出了一种新模型来解决这一问题。
通过LDA获得的最优投影矩阵 W 在最小化类内距离和最大化类间距离的约束下。为了得到LDA的数学公式，我们首先定义三个变量如下：
从问题(6)可以看出，基于迹的LDA对同一类样本具有相等的权重，这使得LDA只能捕捉全局结构。因此，LDA在高斯分布数据集上表现良好，但在复杂分布数据集上无法获得理想结果。由于这种LDA算法忽略了数据的局部结构，并迫使同一类中的成对点尽可能接近，即使这些成对点距离较远。
为了解决上述问题，提出了许多局部感知算法来研究局部数据结构。对于局部Fisher判别分析（LFDA），它利用了亲和矩阵的概念来定义局部类内散布矩阵 和局部类间散布矩阵，因此LFDA可以有效地从原始数据空间捕获局部信息。LDA和局部方法LFDA的降维实验结果如图2所示（所提出的模型SALDA将在第3节定义）。对于图1(a)中所示的单峰分布数据，LDA和LFDA都能将不同类别的数据点分开并找到正确的投影方向。然而，对于图1(b)中所示的多峰分布数据（即同一类中的点形成几个独立的组），LDA由于不同类别的点重叠而表现不佳，而LFDA仍然表现良好。类似于LFDA，所提出的LSDA方法引入了KNN技术来构建类内和类间图，以便在降维过程中利用构建的图来保留局部信息。近年来，这种图学习的思想在局部LDA方法中得到了广泛应用，如局部线性判别分析（LLDA）、非参数判别分析（NDA）和自适应局部线性判别分析（ALLDA）。
这些局部感知方法研究了局部数据结构，并在某些情况下取得了良好的结果。然而，这些方法学习到的邻域关系可能不可靠。这有两个主要原因。首先，KNN技术通常作为这些局部感知方法的预处理步骤来构建相似性图。因此，最近邻数 k 可能严重影响相似性图的质量，进而影响降维性能。其次，直接利用原始空间的距离度量并不可靠。这里，我们给出了一个例子来说明它们的弱点。在图2中，玩具数据集由两个类别组成，以不同的形状和颜色显示。对于图2(a)中描述的传统局部感知方法，它基于原始空间的距离在相同类别内找到邻近点，这在有噪声的数据集上无法实现高性能。此外，它依赖于KNN处理和参数 k 的选择，这可能进一步影响算法的最终性能（图2(a)中 ）。
因此，基于上述分析，我们打算提出一种新方法来研究期望子空间中的局部数据结构。此外，我们的方法可以自适应地学习数据点之间的相似性权重，而无需引入额外参数，即学习子空间中的邻近点将具有较大的权重，而距离较远的点将具有较小甚至为零的权重。在图2(b)中，这些实线表示从内在子空间中学习到的点之间的大权重。通过利用这种方法，我们可以捕获可靠的邻域关系，性能将优于其他局部感知方法。
自加权自适应局部判别分析
在本节中，我们提出了一种名为自加权自适应局部判别分析（SALDA）的新型框架，用于降维问题。首先，我们提出了SALDA框架的目标函数，并对我们的模型进行了理论分析。然后，通过在通用框架中引入一个设计好的函数，我们提出了一种特定的算法来优化这个模型，并进一步在实验中评估我们的算法性能。提出了许多基于局部感知的方法来捕获数据的局部结构。但是从原始特征空间来看，所提出的方法可能无法学习到邻域之间的可靠关系，特别是在严重噪声的情况下。此外，KNN技术通常作为这些方法的预处理步骤，这需要额外的努力来调整KNN中的参数。
与之前的局部感知方法不同，我们提出了一种新的局部感知降维方法，自适应地从内在子空间中学习数据点之间的权重。所提出的模型旨在通过最小化内在相似点之间的距离，同时尽可能远地分离不相似的点，来学习一个最优投影 W。为了捕获数据中隐藏的局部结构信息，我们需要获得理想子空间中点之间的邻域关系。因此，SALDA的新型通用框架可以描述为以下形式：
为了获得直观的形式，我们通过在所提出的框架SALDA中最小化一个函数来展示特定的算法，该算法用于解决以下问题：
在这里，我们将推导出一个高效的算法来解决当时的这个问题。
与问题(6)相比，我们知道每个类内数据对之间的权重可能不会在目标函数(10)中明确定义。因此，基于之前的分析，我们将展示SALDA如何为每对数据生成有意义的权重。
在每次迭代中，我们需要解决问题(8)。通过图嵌入框架的公式推导，问题(8)可以进一步重新表述为：
3.1 算法的复杂度
理论分析
在本节中，提出了一种有效的算法来解决一个一般问题，该问题将方程(7)和(10)视为特殊情况。此外，稍后将展示所提出算法在问题(10)与LDA之间的紧密联系。
4.1 解决一般问题的算法
在本部分中，我们考虑解决以下一般问题：
4.2 算法2的收敛性分析
在本节中，我们将证明所提出的算法2的收敛性，可以分为两个步骤。首先，我们给出定理1来证明问题(13) 的目标值将通过算法2收敛到一个固定值。其次，基于引理1和定理2，可以证明收敛解是问题(13) 的局部最优值。然后，具体的证明过程如下：
4.3. 与LDA的联系
根据方程(8)，所提出方法在方程(10)中的类内散布矩阵可以推导为：
这与LDA具有相似的形式。
从方程(5)和(28)可以看出，LDA和我们的方法都是监督降维方法。它们的形式和目标相似：它们都旨在最大化类间散布矩阵并最小化类内散布矩阵。
根据定理3，可以进一步得出结论：问题(28)可转化为问题(5)的形式。因此，传统的LDA算法是我们所提出的SALDA框架的一个特例。
- 实验
本节在合成数据集和八个真实世界数据集上开展实验，以验证所提出方法的有效性。我们选取了一些当前最先进的基于局部感知（locality-aware）的方法，与所提出的SALDA算法进行比较。此外，本部分还对SALDA进行了参数分析和收敛性分析。
5.1 合成数据集
本小节在两个名为Synthetic-1和Synthetic-2的合成数据集上执行SALDA算法，以验证我们算法的有效性。这两个合成数据集均包含三个类别，其前两个维度的数据点位于三个同心圆上，如图3(a)和(e)所示。为验证SALDA算法的有效性，我们在这些数据集中添加了八个维度的高斯噪声，从而构成10维的合成数据集。噪声维度由高斯分布生成，取值范围从0到N。在本实验中，我们将噪声水平N分别设为5（Synthetic-1）和100（Synthetic-2）。对于SALDA，本实验中参数p设为1。图3中同时展示了LDA [10] 和局部感知模型LFDA [20] 的结果，以与我们的算法进行对比。
如图3所示，所提出的SALDA算法在从原始数据集中捕获局部结构信息方面表现更优。特别是从图3(d)和(h)可见，我们的模型能够分别为这两个不同噪声水平的合成数据集学习出理想的二维子空间。而对于LDA，从图3(b)和(f)可以看出，由于LDA仅关注全局结构，无法学习到具有判别性的子空间。从图3(c)可见，LFDA具备挖掘局部信息的能力，在噪声水平为5时取得了良好性能。然而，图3(g)表明，当数据维度受到严重噪声污染时，LFDA可能无法获得稳定的结果。这是因为LFDA是在原始空间而非最优子空间中学习邻域信息。
为进一步验证我们的SALDA模型具备捕捉数据间局部结构的能力，我们在Synthetic-1和Synthetic-2数据集上对SALDA所获得的相似性图S进行了可视化。图4展示了在两个合成数据集上的可视化结果。此处，对于所得到的图S，我们将其中大于255的元素统一设为255，以便更好地可视化。从图4(a)和(b)均可看出，图S中的每个块都非常稀疏，仅少数元素具有较大的数值。这表明我们的模型在所期望的子空间中充分考虑了类内样本之间的局部信息。因此，只有那些在投影后彼此相邻且属于同一类的样本才具有较高的相似度。
综上所述，基于图3和图4的分析结果，我们可以得出结论：所提出的SALDA模型能够自适应地从所学习的子空间中为每个样本捕获邻域信息。此外，我们的模型在处理含噪声维度的数据集时更加稳健，并能从原始空间中获得更具判别性的最优子空间。
5.2 真实世界数据集
5.2.1 数据集
本实验选取了八个真实世界数据集来测试我们SALDA模型的性能，包括USPS [37]、YALE [38]、PIE [39]、MSRA [40] 以及四个UCI数据集 [41]：Australian、Heart、Diabetes和Pima。这些数据集的详细介绍如下：
USPS数据集是一个手写数字图像数据库，包含超过9000张图像。在本实验中，我们从中选取六个数字以验证算法性能，每张数字图像的尺寸为16×16。
YALE数据集由耶鲁大学计算视觉与控制中心提供，包含15个不同个体的165张正面人脸图像，拍摄条件涵盖不同的面部表情、光照条件和面部细节。在本实验中，每张图像被下采样至32×32大小。
CMU PIE数据集共包含68个受试者，总计41,368张人脸图像。这些图像由13台同步相机和21个闪光灯在不同姿态、光照和表情条件下拍摄而成。我们选取PIE数据集中名为POSE07的子集用于实验，每张图像被下采样至32×32大小。
MSRA数据库由微软亚洲研究院收集，包含12个个体在不同背景和光照条件下的图像。每位个体至少采集64张人脸图像，每张图像被调整为16×16大小。
四个UCI数据集包括Australian、Heart、Diabetes和Pima，均来自UCI机器学习库，它们的类别分布并不复杂。
表1列出了这些基准数据集的详细信息。在本实验中，主成分分析（PCA）[9] 被用作预处理步骤，以加快处理速度并节省计算时间。所有对比算法均在相同的预处理数据集上执行。对于这八个基准数据集，我们首先随机选取每类样本的30%作为训练集，其余样本作为测试集。在获得最优投影矩阵W∗后，我们将投影后的训练集作为已知标签信息，并在投影后的测试集上采用K近邻（KNN）技术作为分类器。通过投影后测试样本与投影后训练样本之间的最近邻关系，即可获得最终的分类结果。在本实验中，分类器KNN的参数k（即近邻数量）设为1。
5.2.2 对比方法
为验证所提出方法的优越性，我们选取LDA以及若干当前最先进的局部感知（locality-aware）方法作为对比算法，包括：局部Fisher判别分析（LFDA）[20]、局部敏感判别分析（LSDA）[21]、局部线性判别分析（LLDA）[24]、非参数判别分析（NDA）[29]、最大间隔准则（MMC）[17]、面向可分性的子类判别分析（SSDA）[42]、自适应判别分析（ADA）[43]、自适应局部线性判别分析（ALLDA）[30]，以及一种名为多类Fukunaga-Koontz判别分析（FKDA）[44] 的Fukunaga-Koontz方法。在投影后的测试数据集上采用KNN算法以获得最终的分类结果。此外，直接在预处理后的原始数据集上使用KNN所得的分类结果被用作基线（baseline）。
SALDA中的参数p在区间(0, 2]范围内进行调整，具体的参数分析细节将在第5.3节中介绍。在本实验中，我们将参数p设为1，并将我们的SALDA算法与其他先进方法进行比较。此外，为确保实验的公平性，其他对比算法中的参数均按照其各自原始论文中的设定进行配置。特别地，我们将LDA的降维维度设为c−1（其中c为类别数）。对于其他降维方法，我们在维度范围m∈[1, d−1]（d为原始特征维度）内采用贪心策略（greedy strategy）选择最优维度。最终的分类结果通过KNN算法在经各对比算法降维后的测试集上获得。我们在八个真实世界基准数据集上分别独立运行所有对比方法十次。表2报告了不同方法在最优降维维度下所取得的最大平均分类准确率及其标准差。
5.2.3 性能
表2记录了实验结果。其中最优结果以粗体标出，次优结果以下划线标出。从表2可得出以下结论：
- 可以观察到，SALDA在几乎所有相关方法中均取得了更优且更稳定的性能。特别是与其他局部感知（locality-aware）方法相比，我们的SALDA算法在大多数基准数据集上获得了更好的效果。这种优越性能的原因在于：大多数传统的局部感知方法基于原始空间中的距离来学习邻域关系，而这种距离可能无法可靠地揭示数据的内在局部结构，从而进一步影响分类性能。与以往方法不同，SALDA在所期望的子空间中自动寻找邻近点，并将本质上相似的点拉近，因此自然取得了良好的结果。
- 从结果可以看出，大多数局部感知方法的表现优于LDA。这一现象的主要原因是：LDA仅关注全局数据结构，忽略了局部结构，导致其在处理复杂分布数据时性能较差。相比之下，其他局部感知方法通过挖掘局部邻域关系，在这些基准数据集上取得了更好的结果。
- 对于这些竞争性方法而言，它们依赖KNN过程来寻找每个数据点的邻居，因此需要额外调节参数k。而众所周知，SALDA能够自动学习点对之间的权重，无需手动设置此类参数。因此，与以往方法相比，我们的方法使用更为便捷，在实际应用中具有更强的实用性。
5.3 参数与收敛性分析
根据公式(10)，我们的方法中仅存在一个参数 p（其中 0 < p ≤ 2）。为评估该参数对性能的影响，我们采用网格搜索法，将 p 设置在 [0.1, 0.4, 0.7, 1.0, 1.3, 1.6, 1.9] 范围内。
仿真实验（参见图5）在八个数据集上运行，以展示所提出的SALDA算法在不同参数 p 下的分类准确率变化。从图5可见，当 p 取不同值时，分类准确率存在波动。总体而言，当 p 调整为1时，我们的方法在这些数据集上获得了最佳结果。此外，从图5(a)、(d)、(g)和(h)所示的USPS、MSRA、Diabetes和Pima数据集来看，甚至存在比 p=1 时更优的性能表现。因此，在第5.2节的实验中，使用 p=1 的本方法与其他竞争算法进行比较是合理的。当然，若在实际应用中对所提出的方法实施网格搜索，则可获得更好的性能。
此外，为进一步验证我们的算法在真实场景中的性能，我们分析了该算法在所呈现的八个基准数据集（包括USPS、YALE、PIE、MSRA、Australian、Heart、Diabetes和Pima）上的收敛性。
SALDA在这些数据集上获得的收敛曲线分别如图6的各个子图所示。可以看出，我们的算法在所有这些基准数据集上均能在10至15次迭代内收敛，这表明我们的算法易于优化，并且在处理高维数据集时效率非常高。此外，图6所示结果表明，SALDA在真实世界基准数据集上表现非常稳定。
- 结论
在本研究中，我们提出了一种新的基于局部感知的降维框架（SALDA）。与传统的LDA算法相比，所提出的方法能够从原始数据空间中自适应地学习一个最优子空间，从而更有效地从期望子空间中获取邻域关系，即使在存在严重噪声维度的情况下亦然。此外，SALDA能够自动为同一类内的数据点对分配权重，这对我们的模型捕捉局部信息非常有用。因此，我们的SALDA模型能够更有效、更稳健地处理具有复杂分布的真实世界数据集。在合成数据集和真实世界数据集上的实验结果进一步表明，我们的模型优于其他经典的基于局部感知的方法。
在本文中，我们将ℓp-范数引入到我们的框架中以解决降维问题，这有助于我们的模型保留局部信息并增强对噪声的鲁棒性。然而，ℓp-范数无法使我们的框架具备处理含异常值数据的能力。因此，在未来的工作中，我们计划将ℓ2,1-范数[45]引入我们的框架，以应对异常值问题。
原文链接：https://www.sciencedirect.com/science/article/pii/S003132032200259X
热门跟贴