基于消除零空间的高维小样本数据判别特征选择算法

《Neurocomputing》：Discriminant feature selection algorithm for high-dimensional small sample data via removing null space

　　夏斌志|王雪|郭瑞妮 中国西安710121，西安邮电大学理学院 摘要 辨别特征选择（DFS）是一种有效的特征选择方法，它利用线性判别分析（LDA）变换矩阵的行稀疏性。然而，当处理高维小样本数据时，DFS方法会遇到与经典LDA类似的问题：散点矩阵的奇异性以及较高的计算复杂度。尽管现有的DFS算法已经采用了一些策略来解决这两个问题，但这些策略仍然存在各种问题和缺陷。为同时解决上述两个问题，本文提出了一种新的DFS准则。这种新准则的优势在于，通过利用它，DFS问题可以等价地转化为反复求解正则化LDA问题的迭代过程。而且，通过结合基于零空间降维与正则化的方法，可以高效地求解正则化LDA问题。针对这一求解过程，本文提出了名为“通过去除零空间进行DFS”（RNS-DFS）的算法。RNS-DFS不仅有效解决了高维小样本数据下DFS的散点矩阵奇异性和高计算复杂度问题，还具有以下几项优势：（1）降维操作使得算法对稀疏正则化参数的敏感性较低；（2）算法的高效率使得交叉验证成为参数选择的实用方法；（3）通过特征加权为理解DFS的工作机制提供了新的视角。最后，本文还提出了RNS-DFS的扩展模型。在多种数据集上进行的广泛对比实验验证了所提出的RNS-DFS算法及其扩展算法的有效性和高效性。引言 在当今大数据时代，随着传感器技术的进步和信息获取方法的改进，数据维度呈指数级增长。在高维数据情况下，传统分类方法在许多场景中的应用受到限制。直接处理高维数据不仅会导致较高的计算复杂度，还会使分类性能大幅下降。为了解决这个问题，常见的策略是在分类之前先降低数据的维度。降维的两种主要方法是特征提取（FE）和特征选择（FS），它们的核心目标都是降低数据维度以提高模型的效率和性能[1]。特征提取涉及一种数学变换，将原始的高维特征映射到低维空间，生成全新的复合特征。这些新特征通常是原始特征的线性或非线性组合，旨在捕捉数据中的底层结构或关键信息。而特征选择则是直接从原始特征集中选择一组重要的特征。它并不改变特征本身，而是去除冗余或无关的特征[2]。与特征提取相比，特征选择的优势在于其可解释性。根据是否使用样本标签，特征选择方法可分为无监督和有监督两类[3]。本文重点研究有监督的特征选择方法。在过去的二十多年里，基于稀疏表示理论的特征选择算法得到了发展并取得了巨大成功，成为了特征选择算法的重要组成部分。由于基于行稀疏正则化的特征选择方法本质上是一种多任务学习方法，能够提升小样本数据上的泛化能力，因此它们也成为了基于稀疏正则化的特征选择方法中的重要组成部分。迄今为止，已经提出了大量基于行稀疏正则化的特征选择算法。回归[4]、主成分分析[5]以及线性判别分析（LDA）[6]等方法的行稀疏版本早已出现。此外，最近的研究还提出将基于-l范数的行稀疏性与其他范数相结合形成正则化项，以此提升基于行稀疏正则化的特征选择算法的性能。例如，在参考文献[7]、[8]中，作者将-l范数与-p范数作为模型的正则化项，这样既能在变换矩阵中实现行稀疏性，又能选择对数据重建重要的特征。同样，在参考文献[9]中，作者将-l范数与平方-p范数结合形成正则化项，从而在保持行稀疏性的同时选择对每个类别都重要的特征。在参考文献[10]、[11]中，作者将量子机器学习引入这类算法，利用量子机器学习固有的并行处理能力和强大的非线性关系建模能力，进一步提升了基于行稀疏正则化的特征选择算法的性能。总之，基于行稀疏正则化的特征选择算法仍在不断发展中。LDA[12]是一种经典的有监督特征提取方法，其核心思想是找到一种最优的变换方式，在尽可能保留类别区分信息的同时降低数据的维度。然而，传统LDA在处理高维数据时面临两个主要挑战：散点矩阵的奇异性以及较高的计算复杂度。为了解决这些问题，许多学者提出了LDA的各种变体算法。LDA得到的特征是原始特征的线性组合，但这些特征所代表的含义很难解释。为了提高LDA降维结果的可解释性，近期有学者提出在LDA的目标函数中加入行稀疏正则化项，从而有助于选择对数据中所有类别都有益的特征。在这种背景下，我们将基于行稀疏LDA的这种特征选择方法称为辨别特征选择（DFS）方法。Masaeli等人首次提出了DFS算法[6]，该算法在LDA模型基础上引入了-l范数作为稀疏正则化项。通过最小化变换矩阵的-l范数，实现了逐行稀疏，进而完成了特征筛选，将LDA转化为一种新的特征选择算法。然而，该算法存在全零解的缺陷。当计算结果接近此类解时，特征选择功能就会完全失效。此外，该算法还采用拟牛顿法进行计算，这大大增加了时间成本[13]。为了解决该算法的这些局限性，Tao等人[13]提出了改进的DFS算法，采用了比值迹准则（RTC）。该算法用-p范数替代了原来的-l范数，并对变换矩阵施加了正交约束。它的突出特点是，在迭代重加权（IRW）框架下，将DFS的优化问题转化为与散点矩阵相关的、易于计算的广义特征值问题。不过，该算法在迭代过程中需要不断对散点矩阵进行特征值分解，其时间复杂度为O(d^3)，其中d表示数据维度，因此在处理高维数据时耗时极高。此外，我们的实验结果表明，该算法对正则化参数的选择相对敏感，而且该论文的作者并未提供有效的参数选择方法。Zhao等人首次提出了基于迹比值准则的DFS算法（TRC-DFS），这也是首个利用零空间去除降维技术来探讨DFS效率的研究[14]。然而，他们提出的高效算法是一种两阶段算法，缺乏统一的目标函数，因此无法从理论上保证所得变换矩阵的行稀疏性。为了解决现有基于范数的特征选择算法存在的稀疏性限制和参数调整问题，Nie等人提出了DFS算法，该算法采用-p范数而非传统的-l范数，在迹比值框架内实现精确的稀疏特征选择。虽然它有效地解决了因近似稀疏性导致的参数敏感性问题，但其求解过程的时间复杂度为O(d^3)，这严重限制了其实际应用[15]。为了解决在LDA中计算正交稀疏投影的难题，Mo等人提出了联合稀疏正交线性判别分析（JSOLDA）方法[16]。该算法从散点矩阵分解的角度重新诠释了LDA，通过约束散点矩阵分解并施加-p范数惩罚项，实现了联合稀疏与正交的特征提取。不过，该算法的计算复杂度仍然很高。2024年，Zhu等人[17]提出了一种抗噪声的DFS算法。该方法不仅在LDA的损失函数和正则化项中应用了-p范数，还通过引入图结构来重构散点矩阵。然而，该算法有两个缺点：其机制较为复杂，且其主要计算复杂度与数据维度d的立方成正比，因此不适合处理高维数据。2026年，Wang等人提出了NTRFS[18]，这是一种强大的DFS算法，通过最小化-p范数以及带有-p范数约束的块稀疏投影学习来提高抗噪声能力，无需手动调整参数。它的自适应异常估计机制能够利用有益的噪声信息，减少噪声样本对类别原型的影响，从而提升在真实世界噪声环境中的泛化能力。不过，该算法的主要计算复杂度与所选特征数量的立方成正比。当特征数量较多时，计算成本会非常高，这也使得该算法不适合处理高维数据。在[19]中，Sun等人将Softmax分类模型与-p范数正则化相结合，提出了一种改进的DFS算法。-范数能够产生更精确的行稀疏解，从而实现直接的特征选择。同时，Softmax模型提高了模型输出的可解释性，提升了分类性能。然而，该算法涉及大小为d^2的矩阵求逆，其计算复杂度为O(d^3)，因此也不适合处理高维数据。Sheikhpour等人[20]开发了一种半监督DFS算法，该算法整合了超图学习机制，进一步拓展了DFS的应用范围。在[21]中，有人提出了DFS的无监督版本，该版本可以同时学习类别标签矩阵和变换矩阵。尽管已经提出了大量的DFS算法，但在处理高维小样本数据时，仍然存在两个与LDA类似的根本性挑战：散点矩阵的奇异性问题以及较高的计算复杂度。现有的算法虽然已经采取了一些策略来解决这些问题，但仍然存在各种缺陷。为同时应对上述两个挑战，本文提出了一种新的DFS方法，称为“通过去除零空间进行辨别特征选择”（RNS-DFS）。本文的主要贡献可总结如下：•我们提出了一种新的DFS准则，该准则能够将问题转化为一个迭代过程，在该过程中，可以通过在每次迭代中反复结合基于零空间降维与正则化，高效地求解正则化LDA子问题。•我们提出了RNS-DFS，这是一种与所提DFS准则相对应的高效算法，能够解决高维小样本数据下的散点矩阵奇异性和高计算成本问题。它具有三个主要优势：（1）由于进行了降维，对该稀疏正则化参数的敏感性较低；（2）计算效率高，便于进行实际的交叉验证以选择参数；（3）通过特征加权为理解DFS的工作机制提供了新的视角。•我们为所提出的RNS-DFS算法提供了详细的推导过程以及相应的算法步骤。此外，我们还给出了RNS-DFS算法的收敛性证明和计算复杂度分析。•我们还提出了RNS-DFS的扩展算法。•我们在十个不同的数据集上进行了广泛的对比实验，以评估所提算法的有效性和高效性。本文的其余部分结构如下。第2节回顾了相关的主要研究工作。第3节介绍了我们提出的方法。第4节进一步讨论了所提出的RNS-DFS算法与RLDA[12]、[22]之间的关系，并将其与两种主要的DFS算法——RTC-DFS[13]和TRC-DFS[14]进行了比较。第5节我们在多种数据集上对该算法进行了评估。第6节总结了本文内容，并探讨了未来可能的研究方向。

符号、定义与相关工作
本节主要介绍本文中使用的部分符号和定义，同时简要回顾了LDA算法[12]、零空间消除技术[22][23][24]、LDFS算法[6]以及DFS算法[13]。

提出的方法
鉴于现有的DFS算法在解决散布矩阵奇异性问题以及降低计算复杂度方面仍存在不足，本节提出了一种新的DFS准则——RNS-DFS，并给出了针对该准则的高效求解算法。

讨论
通过将所提出的RNS-DFS算法与正则化LDA[12][22]、RTC-DFS[13]以及TRC-DFS[14]进行比较，本节进一步阐述了该算法的机制及其优势。

实验结果与分析
为评估所提出的RNS-DFS和RNS-EDFS算法的性能，我们在10个数据集上进行了对比实验，涉及的11种FS算法包括LS[28]、mRMR[30]、RF[31]、TR[32]和DFG-SFS[33]、TRC-DFS[14]、RTC-DFS[13]、S2DFS[15]、STR-LDA[34]、JSOLDA[16]以及NTRFS[18]。在这11种算法中，LS、mRMR、RF和TR是四种常用的经典特征选择算法，常作为特征选择领域对比实验的基准。DFG-SFS则是近期出现的算法。

结论
本文通过提出一种新的DFS准则及相应的算法RNS-DFS，解决了高维小样本数据场景下DFS面临的两个难题。RNS-DFS算法能够有效解决高维小样本数据中的散布矩阵奇异性问题以及高计算成本问题。它具有三大优势：（1）通过特征加权为理解DFS的工作机制提供了新视角；（2）由于……其对稀疏正则化参数的敏感性较低。

作者贡献声明
支晓斌：撰写——审稿与编辑，撰写——初稿，方法论设计。王雪：撰写——审稿与编辑，撰写——初稿，软件实现。郭瑞妮：数据整理，软件实现，撰写——初稿。

利益冲突声明
作者声明不存在任何可能影响本文研究成果的已知财务利益或个人关系。

致谢
本研究得到了中国国家自然科学基金（项目编号62071378、62071379、62071380）、中国山西省自然科学基础研究计划（编号2020JM-580）以及陕西省高校青年创新团队的支持。支晓斌于2000年在中国陕西师范大学获得数学学士学位，2003年在中国汕头大学获得应用数学硕士学位，2013年在中国西安电子科技大学获得模式识别与智能系统博士学位。目前他是西安邮电大学理学院的副教授，研究兴趣集中在机器学习和高维数据分析领域。