The Set Covering Machine Based On Rough Set Theory

The classifier design is a key step for pattern recognition systems, which can effect performance of system. Among the many classifier design methods existed, the majority of them adopts single - layer structure, that is to say, directly mapping the input pattern into the comprehensible results. Although the single- layer structure looks simple and intuitionist, it often becomes an obstacle to thoroughly bring into play the maximized performance of the classifier. This paper takes the structure of Classifier itself into consideration, and puts forward a two - layer classifier design method based on the Rough Set theory and the set covering machine algorithm.The theory of set covering machine has been proposed by Mario Marchand and John Shawe-Taylor in 2002 as an alternative to the support vector machine when the objective is to obtain a sparse classifier with good generalization. It uses a set covering greedy algorithm. The function which SCM outputs is very simple, our theoretical and experimental results indicate that the set covering machine is definitely a good candidate for machine tasks. But the real-world data in database always have large number of superabundant and jumbled attributes. The time efficiency and algorithm quality of SCM are seriously reduced. The rough set theory is a useful tool for resolving attribute reduction. So we take advantage of the rough set theory in processing of incomplete and uncertain knowledge, get rid of the superabundant and jumbled attributes, and then improve classifying performance.At first, we briefly introduce the Rough Set theory and attributes reduction based on Rough Set theory. Then present the background and fundamental of SCM, furthermore design, write, and test programs of SCM. And use an example to demonstrate algorithmic arithmetic process of SCM.Then discusses the attributes reduction based on Rough Set theory and set covering problem to combine them. Finally, the set covering machine based on Rough Set theory is given.Presently, study about SCM is very few; there is not much literature to be consulted. So, realization and application of SCM is one kind of newer trial. In the end we make the conclusion that two - layer structure design observably improve the performance of the classifier without increasing the constructing complexity of the classifier at the same time.