基于邻域关系的一种高效属性约简算法

An Efficient Attribute Reduction Algorithm under Neighborhood Relations

摘要: 属性约简是粗糙集理论中的重要研究内容之一。近年来得到了快速发展，诸多学者已经做出了大量的优秀成果。基于粗糙集的属性约简通过约简目标的约束构建属性重要度函数，迭代剔除冗余属性，从而获得求解结果，这种方法往往具有较高的时间开销。针对上述问题，本文在邻域关系下提出一种求解约简的高效算法。通过设计逐层收缩的正域迭代机制，去除已确定的正域对象，从而减少每次迭代过程中论域的基数，降低局部的时间复杂度。在UCI数据集下对算法的运行结果以及运行时间进行比较。实验结果表明，该算法在保证约简结果一致性的前提下，显著降低了求解属性约简的时间开销。

Abstract: Attribute reduction, as a pivotal research focus in rough set theory, has undergone significant advancement in recent years with substantial contributions from scholars. The rough set-based attribute reduction methodology constructs attribute significance functions constrained by reduction criteria and iteratively removes redundant attributes to derive reducts, which typically entails considerable computational complexity. Addressing this challenge, this paper proposes an efficient reduct computation algorithm under neighborhood relations. The core innovation involves a progressively contracted positive-region iteration mechanism that reduces universe cardinality during iterations by eliminating confirmed positive-region objects, thereby decreasing localized time complexity. Comparative evaluations of algorithm performance and execution time on UCI datasets demonstrate that the proposed approach significantly reduces computational overhead while preserving reduct consistency.