Improvement And Application Of Rough Set Attribute Reduction Algorithm Based On Boolean Matrix Representation

Rough set theory, as one of the important methods of data mining, is a mathematical tool that can be used to deal with imprecise and incomplete information system, which was given by Poland mathematician Palawk in 1990 s. Attribute reduction is the most important content of rough set theory. At present, many attribute reduction algorithm's time and space cost is too high to deal with large scale decision tables. Because the Boolean matrix is convenient for storage and operation, this is the basis for the study of attribute reduction algorithm based on Boolean matrix representation. However, there are still many problems about attribute reduction algorithm of Boolean matrix representation, such as heuristic information selection is incomplete, the result is not accurate, not suitable for large-scale decision table and other issues. To solve these problems, this paper puts forward the improved algorithm.First of all, because selecting the heuristic information of the existing algorithm is not complete. Aiming at this problem that the existing algorithms do not take into account the importance of the core attributes when condensed Boolean matrix. In this paper, by combination the attribute importance with the improved condition discrimination ability the attribute reduction algorithm based on core and improved condition distinguishing ability is proposed, using the reverse delete reduction set to ensure completeness finally. Examples show that the improved algorithm is more accurate in distinguishing capability, and the result of the reduction is more complete.Secondly, aiming at this problem that the time and space complexity of the existing algorithms is too high, even some algorithms can not deal with large scale decision table. In this paper, we continue to improve the algorithm based on the improved algorithm, the elementary row transformation of the matrix and the bitmap operations are carried out on the Boolean matrix., and use the importance of the core attribute to sort quickly for each row of Boolean matrices before the preliminary compression, and get a new attribute reduction algorithm based on line change and condition distinguishing ability. Then use Matlab programming to achieve the algorithm, and apply it to the specific examples. The examples show that the algorithm can ensure the reduction results more accurate, in dealing with a large scale decision table complex degree is greatly reduced.Finally, the improved reduction algorithm based on line transformation and condition distinguishing ability is applied to the study of the evaluation index of College Students' Employment, and get the influence of employment related factors, and with other methods were compared. The examples show that the improved algorithm has very strong practicability.