关键词: 粗糙集, 属性约简, 计算复杂度, 划分子集, 信息系统

Abstract:

Based on the degree of significance of the attribute, the attribute reduction algorithm proposed by Pawlak is one of the commonly used algorithms, which measure the degree of significance of the attribute by calculating the granularity of the equivalence relation. However, the computational complexity of this algorithm which calculates the degree of significance of every attribute is very high due to computing the partition of different equivalence relation on whole university. Motivated by the idea of set partition in decision tree methods, an attribute reduction algorithm based on set partition was proposed which could improve the attribute reduction algorithm based on the significance of attributes. The basic idea of the proposed algorithm was to calculate the new partition iteratively by adding a nocore attribute to the core attribute set using the partition induced by the core attribute set. In the framework of keeping the positive region of decision attribute invariant, the attribute set with the most refined partition was an attribute reduct. Theoretical analyses showed that the algorithm could reduce the computational time complexity for calculating the attribute reduction,thereby the efficiency can be improved.

Key words:  rough sets, attribute reduction, computational complexity, partition subset, information system