高效的不完备决策系统属性约简算法

摘要 差别矩阵方法因其易懂，易设计被广大学者接受并使用．然而，对于大型的决策表而言，计算差别矩阵时不仅费时，而且会占用大量的存储空间，使得算法的效率不高．为了尽可能减少差别矩阵的存储空间，又能用到差别矩阵的思想，提出了区分对象对集的思想，研究发现，这样设计的方法也无法适用大型数据集．为此，在区分对象对集基础上，设计一个能计算区分对象对集的个数的函数，并用该函数设计了一个启发函数，同时给出该启发函数的快速算法，利用启发函数设计了一个高效的不完备决策系统属性约简算法，新算法时间复杂度及空间复杂度分别降为O（K|C||U|）（其中K=max｛|TC（xi）|，xi∈U｝和O（|U|）．通过实例仿真说明该算法是一高效可行的属性约简算法