基于集合枚举树的最小属性约简算法

"以互补条件熵为启发信息的正域属性约简.pdf" 本文研究的核心是粗糙集理论在处理不完整和不确定信息时的应用，特别是针对属性约简问题。粗糙集理论由Pawlak在1982年提出，它提供了一种处理不确定性和不完整性信息的新方法。该理论的核心是知识约简，旨在在保持决策或分类能力不变的情况下，去除决策表中的冗余和不相关信息。 知识约简的目标是找到最小属性约简，即在保持分类能力不变的前提下，属性集的最小子集。最小属性约简的寻找是一个关键问题，因为决策表的属性约简通常不是唯一的。然而，S.K.M. Wong和W. Ziarko证明了找到一个决策表的最小约简是一个NP-hard问题，这主要是由于属性组合的复杂性。 为了应对这一挑战，文章提出了一种新的最小属性约简算法，该算法基于集合枚举树。首先，重新定义了属性的重要性，并在条件属性集上建立了序关系。接着，利用至上而下、层次优先的搜索策略遍历集合枚举树，以找到最小属性约简。为了提高算法效率，文章引入了两种剪枝策略：父集剪枝和属性核剪枝。前者通过判断集合的父集是否为属性约简来避免不必要的计算，后者则通过确认所有属性约简都包含核属性来简化搜索空间。 优化计算的运用确保了相同集合的正域只需计算一次，进一步提升了算法的效率。文章通过在UCI数据集上的实验验证了该算法的有效性。这种新算法不仅能够找到决策表的最小属性约简，而且通过采用剪枝策略，显著减少了计算量，提高了算法的运行速度。 该论文研究提供了一种创新的、高效的最小属性约简算法，为粗糙集理论在实际应用中的复杂性问题提供了解决方案。通过重新定义属性重要性并构建集合枚举树，算法有效地解决了属性组合爆炸的问题，对决策表的分析和知识提取具有重要的理论与实践价值。