Rough Set Attribute Reduction Based On Tree Structure

Rough set theory is a mathematical tool for dealing with uncertain problems.It is distinguished from the previous fuzzy sets and probability theory,which is not required to provide any prior information.Therefore,many scholars have attracted much attention and attention.After more than thirty years of development and improvement,the theory has been widely used in data analysis,artificial intelligence and other fields,and has become one of the popular data processing theories.As one of the core contents of rough set theory,attribute reduction is always the focus of scholars.Based on different inspiring ideas,many attribute reduction algorithms have been proposed by scholars.The reduction algorithm based on discernibility matrix is more and more concerned by researchers because of its advantages such as ease of computation and storage.However,there are still some problems in the method,such as the existence of a large number of redundant elements,and the high cost of time and space.In order to solve these problems,this paper proposes a tree type storage structure,which can eliminate some redundant elements in the difference matrix and can realize the compression storage of the non empty elements of the differential matrix.Based on the data structure,a rough set attribute reduction algorithm is proposed in this paper.The main contents of this paper are as follows:1.The attribute reduction algorithm based on attribute importance,difference matrix and improved differential matrix is studied,and the advantages and disadvantages of these algorithms are analyzed and compared.2.Aiming at the large number of redundant elements in the process of attribute reduction in discernibility matrix,a storage structure based on digital lookup tree is proposed.The structure eliminates the repetitive elements in the difference matrix,and makes the part of the parent-child relationship sharing the path of the parent set in the tree,thus realizing the compressed storage of the data.The effectiveness of the algorithm is verified by experimental comparison.3.The pruning strategy is introduced to the traditional digital search tree to achieve further compression and storage of the differential information.Based on the improved digital lookup tree,the corresponding reduction algorithm is proposed.Experiments on UCI dataset prove that the algorithm is effective.