基于自适应k最近邻粗糙集的鲁棒特征选择

《Pattern Recognition》：Robust feature selection with adaptive k -nearest-neighbor rough sets

　　周明马|李家平|黄英音|陈金坤|林国平|郑美玲
福建闽南师范大学数学与统计学院，漳州，363000，中国

摘要
尽管k最近邻粗糙集（KNNRS）对连续数据非常有效，但由于参数k的主观选择以及贪婪特征选择策略带来的高计算成本，它容易受到噪声的影响。为了解决这些限制，本文提出了一种基于粒度一致性的自适应k最近邻粗糙集（AKNRS）模型。这种方法显著提高了对噪声和具有模糊类别标签样本的鲁棒性。为了在特征评估过程中减少冗余计算，我们引入了一种快速评估单个特征可分性的机制。这种评估有助于有效地对特征进行预排序，从而以更高效和原则性的方式指导选择过程。基于这一框架，我们开发了一种新的特征选择算法，称为基于可分性的自适应k最近邻粗糙集（S-AKNRS）。在实验中，S-AKNRS在平均分类性能和对噪声的鲁棒性方面均优于邻域粗糙集、传统的KNNRS以及其他六种最先进的特征选择方法。

引言
在现实世界的应用中，许多数据集都包含冗余和噪声特征。从这些数据中提取相关和有用的信息仍然是数据处理的重大挑战。因此，数据降维和信息提取已成为数据挖掘中的核心研究方向，而特征选择则是有效知识发现的基本组成部分。
粗糙集理论[1]为从不精确和不一致的数据中提取规则和特征提供了一个强大的框架。尽管k最近邻方法简单直接，但在机器学习和数据挖掘中非常有效，尤其是在分类和聚类方面。KNNRS模型[2]结合了这两种方法的优点，利用它们的互补优势来提高数据处理性能。在现实世界的应用中，数据集通常表现出异构特性——这是推动开发针对不同数据类型的各种粗糙集模型的关键因素。这些模型包括Pawlak的经典粗糙集[3]、优势粗糙集[4]、[5]、[6]、邻域粗糙集[7]、[8]、[9]、[10]、[11]、模糊粗糙集[12]、[13]、[14]、[15]、[16]、[17]、覆盖粗糙集[5]、[18]、[19]、[20]以及KNNRS[21]、[22]、[23]、[24]、[25]、[26]。总体而言，经典和扩展的粗糙集方法已被广泛用于特征选择[27]、[28]、[29]、规则提取[30]和决策分析[31]、[32]等任务。
KNNRS通过利用样本受其邻近样本影响的原则，在特征选择方面表现出色。传统的KNNRS基于通过k最近邻定义的关系。邻域的概念是指目标元素周围特定范围内的所有元素集合，针对数值数据和混合数据已经进行了大量的邻域度量研究。邻域通常由基于半径的标准或k最近邻标准定义。例如，吴等人提出了一种基于邻域等价关系的新型邻域粗糙集模型[10]。胡等人使用δ-邻域和k最近邻的概念定义了反映特征子集分类性能的正区域[8]、[22]。朱和胡在粒度邻域粗糙集框架内开发了一种自适应特征选择算法[33]。赵等人引入了一种基于回归的方法，将特征敏感性整合到自适应特征选择过程中[34]。王等人提出了一种基于矩阵的特征选择方法，消除了降秩的需要，并进一步探索了邻域度量以增强邻域粗糙集中的信息区分能力[35]、[36]。
基于邻域和k最近邻信息粒度的粗糙集模型存在固有的局限性：在局部特征密度分布不同的信息系统中——即使经过重新缩放后——控制信息粒度大小的参数也应适应局部数据密度，这在稀疏和密集分布的区域之间是不同的。为了改进基于邻域的特征选择，研究人员提出了各种增强措施和替代策略。胡等人将最近邻关系应用于具有混合类型特征的信息系统，并开发了一种使用变精度k最近邻策略（FarVPKNN）的前向属性选择算法[22]。他们表明，在许多情况下，通过k最近邻关系获得的特征子集比基于传统邻域定义的特征子集具有更好的分类性能。王等人通过结合邻域和k最近邻粒度定义了一个复合最近邻信息粒度，并基于这种精细的粒度定义提出了一种基于邻域的特征选择算法（NNRS）[2]。夏等人将粒子球计算纳入邻域粗糙集框架，建立了粒子球邻域粗糙集（GBNRS），该模型能够自适应地确定最佳邻域半径，并设计了相应的特征选择算法[37]。胡等人利用属性之间的数据重叠程度对特征进行排序，并通过结合重叠程度和KNNRS开发了一种特征消除算法（OD&KNN）[21]。此外，基于信息论中的香农熵的互信息在特征选择框架中被广泛采用[38]、[39]、[40]。曲等人将粗糙互信息与自适应邻域粗糙集结合，开发了一种最大相关性和最小冗余（MRMR）引导的特征选择方法[41]。徐等人基于条件互信息制定了一个客观的特征评估函数，并引入了相应的交互式特征选择算法（KNCMI）[25]。
许多基于邻域和k最近邻的粗糙集方法依赖于固定的邻域参数（半径或k）。这些参数对性能有很大影响，并且因数据集和局部区域的不同而变化，使得手动调整变得困难，并且在局部密度异构和噪声特征存在的情况下降低了鲁棒性。同时，一些提高适应性的方法仍然会产生高计算成本，因为它们需要在特征子集变化时重新划分或重复计算正区域，这在高维度或大样本量时变得不可行。
受这些限制的启发，我们的目标有三个：（1）通过适应局部数据结构来消除对单一手动选择的邻域参数的需求；（2）通过粒度一致的局部邻域来提高对异构密度和噪声的鲁棒性；（3）通过避免冗余的正区域重新计算来降低迭代特征选择的运行时间成本。为了实现这些目标，我们（i）使用粒度一致性调整每个信息粒度的k值；（ii）引入一种快速的、决策感知的可分性度量来预排序并暴露特征之间的冗余；（iii）执行增量选择，重用之前计算的正区域以大幅降低复杂性。最后，我们提出了一种基于特征可分性和自适应k最近邻粗糙集的新特征选择算法——S-AKNRS。实验结果表明，S-AKNRS在所有数据集上的平均分类性能更好，并且在平均运行时间方面显著优于几种最先进的方法。

为了明确我们的目标和理由：本工作（1）开发了一种基于粒度一致性的自适应k最近邻粗糙集（AKNRS）框架，以消除对固定手动选择的k值的需求，并提高对噪声和异构局部密度的鲁棒性；（2）提出了一种快速的、决策感知的可分性度量来预排序特征并暴露冗余；（3）将这些想法整合到S-AKNRS中，这是一种高效的特征选择算法，可以避免重复的正区域重新计算，从而大幅降低计算成本，同时保持或提高分类性能。该方法通过结合粗糙集近似和局部k最近邻粒度并强制使用一致的信息粒度来理论证明其合理性，从而使k值适应局部数据结构。本文的其余部分组织如下：第2节回顾了基础知识；第3节介绍了AKNRS；第4节介绍了可分性度量和S-AKNRS算法；第5节报告了实验结果；第6节总结了工作并展望了未来工作。

**章节片段**
**基础知识**
本节回顾了传统的邻域粗糙集理论和KNNRS框架。
设DIS=(U,B,D)是一个决策信息系统，其中U={x1,x2,…,xn}是一个非空的有限宇宙（一组样本），B是属性（特征）的集合，D是决策属性（标签）。N是由决策属性D诱导的等价类的数量，即U/IND(D)={D1,D2,…,DN}。

**基于数据可分性和自适应k最近邻粗糙集的特征选择**
在典型的粗糙集特征选择中，大多数方法使用贪婪搜索来寻找特征子集，这通常会导致计算效率低下。为了解决这个问题，我们定义了特征的数据可分性，并将其作为预测指标，即特征重要性的度量来对特征进行排序。

**实验分析**
在本节中，我们验证了我们的算法（S-AKNRS）在多个分类数据集上的有效性。我们还将它与其他特征选择算法进行比较，以评估其性能。评估标准主要包括算法的运行时间和使用所选特征实现的分类准确性。

**结论**
AKNRS模型自动调整邻域大小k以适应局部数据特性，从而提高了对不同数据分布和噪声及异常值的鲁棒性。这种自调能力使得算法在各种数据集上的性能稳定，并减轻了由经验选择的参数引起的性能波动。我们进一步将数据可分性整合到AKNRS框架中，从而提高了计算效率和分类性能。

**CRediT作者贡献声明**
周明马：撰写——原始草稿、验证、监督、调查、形式分析、概念化。
李家平：撰写——审阅与编辑、软件、方法论。
黄英音：撰写——审阅与编辑。
陈金坤：撰写——审阅与编辑。
林国平：撰写——审阅与编辑。
郑美玲：撰写——审阅与编辑。

**利益冲突声明**
我们声明与可能不当影响我们工作的其他人或组织没有财务和个人关系，对任何产品、服务和/或公司没有专业或其他形式的个人利益，这些利益可能会影响本文中提出的观点或手稿的评审。

**致谢**
本研究得到了中国国家自然科学基金（项目编号62476078）和福建省自然科学基金（项目编号2024J01799和2025J01362）的支持。