Research On Attribute Reduction Algorithm In Rough Set Based On Tabu Search

The theory of Rough Set (RS) proposed by Pawlak in 1982 emerges as a powerful tool for managing uncertainty that arises from inexact, noisy, or incomplete information. It is shown to be methodologically significant in the domains of artificial intelligence and cognitive science, especially in respect of the representation of and the reasoning with imprecise knowledge, machine learning, and knowledge discovery.Reduction of an information system is a key problem in RS theory. We need to get reducts of an information system in order to extract rule-like knowledge from an information system. Reduct is a minimal attribute subset of the original data which has the same discernible power as all of the attributes in the rough set framework. Obviously, reduction is a process of extracting attribute subset, which maintains the representational power and has minimal redundancy. Many researchers are making their efforts to develop efficient algorithms for the reduction of information systems, these techniques have been successfully applied to data reduction, text classification and texture analysis. One of the promising CI tools is memory-based heuristics, such as Tabu Search (TS), which shows excellent performance in solving many combinatorial search problems. However, the contributions of memory-based heuristics to information systems and data mining applications are still limited compared with other CI tools like evolutionary computing and neural networks. This paper proposes a TS-based approach, called Tabu Search for Attribute Reduction (TSAR), to solve the problem of attribute reduction of an information system.TSAR uses a 0-1 variable as the representation of solutions in searching for reducts. A dependency degree function of rough set is invoked to measure the solution quality. The search process in TSAR is a high-level TS with long term memory. Therefore, TSAR invokes diversification and intensification search besides the TS neighborhood search.The TSAR method proposed in this paper uses the TS neighborhood search for the reduction of an information system. TS neighborhood search is mainly based on two concepts, which are avoiding returning to a recently visited solution and accepting downhill move to escape from local maximum information. Some search history information is reserved to help the search process to behave more intelligently. Specifically, the best reducts found so far and the frequency of choosing each attribute are saved to provide the diversification and intensification schemes with more promising solutions. TSAR invokes three diversification and intensification schemes, which are diverse solution generation, best reduct shaking which attempts to reduce its cardinality, and elite reducts inspiration. The performance of TSAR is tested through 10 well-known datasets and compared with another attribute reduction method of rough set as shown in the literature. The obtained numerical results indicate that the proposed TSAR method is competitive for the AR problem in terms of reduct quality. Moreover, TSAR shows a superior performance in saving the computational costs of the dependency degree function.