基于知识粒度的不完备决策表的属性约简算法

摘要

The use of knowledge granularity is an effective attribute reduction approach. But for a large decision ta⁃ble, computing knowledge granularity is so time⁃consuming that the algorithm is not efficient for practical use.After the introduction of the discernibility matrix of granularity, a function was designed for calculating the occurrence frequency of condition attributes in the matrix. In this paper, we design an efficient attribute reduction algorithm based on the granularity discernibility matrix. The new algorithm reduces the time and space complexities to O( K|C||U|) (K=max{|Tc(xi)|, xi∈U}) and O(|U|), respectively. The results from our simulation example verify that the proposed algorithm is feasible and highly efficient.%知识粒度是属性约简的有效方法，但对于大型的决策表，计算知识粒度过于费时，算法效率不高。在引入粒度差别矩阵后，设计了一个计算粒度差别矩阵中条件属性出现频率的函数，有效地降低粒度差别矩阵的存储空间，根据此函数设计了一个高效属性约简算法。新算法使得时间复杂度与空间复杂度都降为 O（K｜C｜｜U｜）（其中K＝max｛｜Tc（ xi ）｜， xi∈U｝和O（｜U｜）。最后通过实例仿真说明了此算法的高效性和可行性。