A Quick Attribute Reduction Algorithm with Complexity of max(O(｜C｜｜U｜),O(｜C｜~2｜U/C｜))

Computing U/C is one of the most important and time-consuming computation in attribute reduction based on positive region.At present,the idea of the best algorithm for computing U/C is based on quick sorting,and it's time complexity is O(｜C｜｜U｜log｜U｜).In this paper,a new algorithm based on radix sorting for computing U/C is provided,and its complexity is cut down to O(｜C｜｜U｜).On the other hand,it is not fully reasonable to regard approximate quality as heuristic information in attribution reduction algorithm based on positive region.So a new and relatively reasonable formula measuring attribution importance is designed for reducing searching space as quickly as possible,and the recursive calculating method of the formula is provided.The algorithm complexity of calculating the formula is descended to O(｜C-P｜｜U′-U′_(P)｜).Then the formula measuring attribute importance is used as heuristic information to design an efficient attribute reduction algorithm,whose worst time complexity is cut down to(max)(O(｜C｜｜U｜,O(｜C｜~(2)｜U/C｜)).An example is used to illustrate the efficiency of the new algorithm. At last,experimental result shows that the new algorithm is not only efficient but also scalable.