Research On Attribute Reduction Algorithm Of Test-cost-sensitive Rough Set

Rough set is a mathematical tool to describe the problem of incomplete and uncertain, it does not need any prior knowledge to analyze and process the data. In the face of formation of massive data in the high speed of the information age, Rough set plays an important role in the analysis and processing of data. Attribute reduction is one of the important contents of rough set theory, the core idea of it is to ensure that the classification ability of the knowledge base is invariable, to remove redundancy, error, or knowledge that is not required. And cost sensitive learning is one of the hot topics in the field of machine learning and data mining, it is to build a classifier with the minimum cost; the cost includes the testing cost, the classification cost, the computation cost, the cost of obtaining the sample and so on. Introducing cost sensitive learning into the problem of attribute reduction in rough set theory deserved in-depth study, the error classification cost is introduced into rough set theory and the related research has achieved good results, and the related research of test cost sensitive rough set theory began to develop in recent years.In this paper, we mainly study the problem of attribute reduction in the test cost sensitive rough set, Complete decision table and incomplete decision table are used as the research objects. The main research work has the following aspects:(1)In order to solve the problem of high efficiency and accuracy of the test cost sensitive attribute reduction, an algorithm for minimizing test cost reduction based on immune quantum particle swarm optimization is proposed. According to the conditional information entropy and the test cost factor, the proper fitness function is defined. The problem of attribute reduction of the minimum test cost is converted to the optimization problem of 0-1,and the problem of the minimum attribute reduction is a kind of minimizing test cost reduction problem with special test cost. Finally, the reduction algorithm is presented by combining quantum particle swarm optimization and artificial immune algorithm. Experiments are compared with the existing minimum attribute reduction algorithm and test cost sensitive attribute reduction algorithm, results show that the presented algorithm is effective.(2)In incomplete decision table, an efficient algorithm for calculating the tolerance relation is given. The concept of inconsistent object is proposed, and its natures are researched. According to its nature, the definition of the core attributes and attribute reduction based on inconsistent object is presented, and the algorithm of the core attributes is designed. A new definition of attribute importance is put forward. Finally, according to the importance of attribute design a heuristic attribute reduction algorithm. In the worst case, the time complexity is O(k|C|2|U|),and space complexity is O(|U|).Theoretical, example analysis and experimental results show that the accuracy and feasibility of the reduction algorithm.(3)The problem of test-cost-sensitive attribute reduction in incomplete decision table are introduced. The definition of inconsistent object set is proposed and an algorithm for computing the inconsistent object set is designed. According to the nature of inconsistent object set improved definition of attribute significance. Considering the test cost factors and the change of the number of inconsistent object set to define a new attribute significance, and the weight setting method of it. And then give the calculation algorithm of attribute significance. Based on these conditions, using attribute significance given an attribute reduction algorithm, the time complexity and space complexity of the algorithm are O(k|C|2|U|) and O(|U|).Theoretical and experimental results show that the accuracy and feasibility of the reduction algorithm.