Abstract: In recent years, many scholars like to use the method of the discernibility matrix to design attribute reduction algorithm, but due to the calculation of the discernibility matrix not only time-consuming but also a waste of space, resulting that these attribute reduction algorithms are not good enough. In order to reduce the complexity of attribute reduction algorithm, this paper defines a heuristic function on the basis of Boolean conflict matrix, which can measure the number of conflicts of the condition attribute in the decision table and gives a fast algorithm of the heuristic function at the same time. Then, it designs an effective attribute reduction algorithm of the incomplete table based on the improved Boolean conflict matrix with the heuristic function, and the algorithm can effectively reduce the time complexity. Finally, the experimental results show that the new algorithm is effective.

Key words: rough set, Boolean conflict matrix, heuristic function, attribute reduction

摘要： 近年来，诸多学者喜欢用差别矩阵的方法来设计属性约简的算法，但由于计算差别矩阵不仅费时且还浪费空间，导致这些属性约简算法都不够理想。为了降低属性约简算法的复杂度，在布尔冲突矩阵的基础上，定义了一个启发函数，该函数能求出决策表中条件属性导致的冲突个数，同时给出了计算该启发函数的快速算法。然后用该启发函数设计了一个有效的基于改进的布尔冲突矩阵的不完备决策表的高效属性约简算法，该算法能够有效降低时间复杂度。最后实验结果说明了新算法的有效性。

关键词: 粗糙集, 布尔冲突矩阵, 启发函数, 属性约简