不一致决策表快速知识约简算法研究

Quick Knowledge Reduction Algorithm in Inconsistent Information System

知识约简是粗糙集理论重要研究内容之一.目前,通常采用差别矩阵来计算不一致决策表的分布约简、最大分布约简和分配约简,可以获得所有约简,但算法复杂度较高,在较大数据集下非常耗时.针对不一致决策表,提出不一致决策表的一致化决策表转化算法,将计算原不一致决策表的约简转化为计算一致化决策表的约简.给出了5种一致化决策表约简的定义,探讨了各种约简结果之间的关系,利用相对不可辨识的对象对构建了高效的差别矩阵知识约简算法.理论分析和实验结果表明,本文所提出的算法能够有效地减少计算时间,适合处理大数据集.

Knowledge reduction is one of the important research issues in rough set theory. Existing approaches to knowledge reduction of distribution reduct, maximum distribution reduct and assignment reduct are based on discernibility matrix for an inconsistent decision table, which are very time-consuming when the decision table is large. To address this issue, the computation for the reducts of the original inconsistent decision table is converted into the computation for the reducts of the derived consistent decision tables. The relationships of five proposed reductions are discussed. An efficient discernibility matrix algorithm for large datasets is proposed using the relatively indiscemibility object pairs. Theoretical analysis and experimental results show that our knowledge reduction algorithms can be used to reduce computational costs for large inconsistent datasets.