Attribute reduction algorithm based on discernibility matrices in classification

Large numbers of duplicate elements contained in discernibility matrix may employ a lot of memory.When the dataset is dense,the time complexity of constructing discernibility matrix is very high.In this paper,an attribute reduction algorithm SDMAR based on simplified discernibility matrix is proposed.Firstly,the attributes are merged by calculating the attributes similarity and the same individuals in universe are deleted before reducing attribute,then a simplified decision table is got.Secondly, simplified discernibility matrix is constructed according to reduction decision table.To achieve the purpose of attribute reduction, the attributes occurred most frequent in discernibility matrix are found and the elements included these attributes are deleted,until discernibility matrix is empty.The analysis of the algorithm and a case shows the time complexity of attribute reduction is low.