一种广义决策保持的快速启发式属性约简算法

A Fast Heuristic Attribute Reduction Algorithm for Generalized Decision Preservation

摘要: 属性约简是粗糙集理论的重要概念之一，旨在获得一个可以保持原始信息系统分类能力的最小属性子集。广义决策保持约简是粗糙集中的属性约简方法之一，其目标为维护决策系统中的决策结果，确保在约简过程中不丢失原始决策。这意味着约简后的系统仍可正确地进行决策，而决策规则的有效性和决策能力得以保持。传统的广义决策保持启发式属性约简算法注重算法的有效性，而算法的效率有待优化。传统算法在计算广义决策保持相似度时需多次遍历每个对象的等价类与决策类，存在大量的重复计算。为了克服这个问题，我们通过引入哈希表来存储每个对象的等价类与其广义决策，使得计算广义决策保持相似度时可针对计算对象直接得出结果而不是依次遍历，由此提出了广义决策保持的快速启发式属性约简算法。最后，通过6组UCI数据集验证了本文提出算法的有效性与高效性。

Abstract: Attribute reduction is one of the key concepts in rough set theory, aimed at obtaining the minimal subset of attributes that retains the classification capability of the original information system. Generalized Decision-Preserving Reduction is a method of attribute reduction within rough set theory, which focuses on maintaining the outcomes of decision-making systems, ensuring that the original decisions are not lost during the reduction process. This implies that the reduced system can still make correct decisions, with the effectiveness and capability of decision rules maintained. Traditional algorithms prioritize effectiveness, but their efficiency needs improvement. These conventional algorithms require multiple traversals through each object’s equivalence class and decision class to compute the similarity degree for generalized decision preservation, leading to extensive redundant computations. To overcome this issue, we introduce the use of hash tables to store each object’s equivalence class and its generalized decision, allowing direct computation of similarity degree for generalized decision preservation for a computational object, rather than sequential traversals, thereby accelerating the algorithm. Finally, the efficacy and efficiency of the proposed algorithm are validated through six sets of UCI datasets.