Rule and matroid theory

In order to acquire knowledge from databases, several methods of inductive learning, such as decision tree and rule induction, have been proposed. These methods are applied to discover meaningful knowledge from large databases, which shows they are useful. However, since there has been no formal approach proposed to treat these methods, efficiency of each method is only compared empirically. In this paper, we introduce the matroid theory and rough sets to construct a common framework for empirical machine learning methods which induce the combination of attribute-value pairs from databases. Combination of the concepts of rough sets and the matroid theory gives us an excellent set-theoretical framework and enables us to understand the differences and similarities between these methods from the viewpoint of partitions of the universe.