Reduct Generation in Information Systems
Janusz A. Starzyk, Dale E. Nelson · 2002
Abstract – When data sets are analyzed, statistical pattern recognition is often used to find the information hidden in the data. Another approach to information discovery is data mining. Data mining is concerned with finding previously undiscovered relationships in data sets. Rough set theory provides a theoretical basis from which to find these undiscovered relationships. Automatic Target Recognition (ATR) is one area which can benefit from this approach. We present a new theoretical concept, strong equivalence, and an efficient algorithm, the Expansion Algorithm, for generation of all reducts of an information system. The process of finding reducts has been proven to be NP-hard. Using the elimination method, problems of size 13 could be solved in reasonable times. Using our Expansion Algorithm, the size of problems that can be solved has grown to 40. Further, by using the strong equivalence property in the Expansion Algorithm, additional savings of up to 50 % can be achieved. This paper describes the fundamentals of this algorithm and the simulation results obtained from randomly generated information systems. The full paper provides the mathematical foundations of the algorithm. In the world today, we are inundated with volumes of data. Businesses have been accumulating vast amounts of data in accounting, inventory and sales