A COMMON ALGEBRAIC FRAMEWORK OF EMPIRICAL LEARNING METHODS BASED ON ROUGH SETS AND MATROID THEORY

Article type: Research Article

Authors: Tsumoto, Shusaku | Tanaka, Hiroshi

Affiliations: Department of Information Medicine, Medical Research Institute, Tokyo Medical and Dental, University, 1-5-45 Yushima, Bunkyo-ku, Tokyo 113, Japan, Tel: +81-3-5684-5395, Fax: +81-3-5684-3618, E-mail: tsumoto@cmn.tmd.ac.jp, tanaka@cim.tmd.ac.jp

Abstract: In order to acquire knowledge from databases, there have been proposed several methods of inductive learning, such as ID3 family and AQ family. These methods are applied to discover meaningful knowledge from large databases, and their usefulness is ensured. 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 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 matroid theory gives us an excellent set-theoretical framework and enables us to understand the differences and the similarities between these methods clearly. In this paper, we compare three classical methods, AQ, Pawlak's Consistent Rules and ID3. The results show that there exist the differences in algebraic structure between the former two and the latter and that this causes the differences between AQ and ID3.

DOI: 10.3233/FI-1996-272313

Journal: Fundamenta Informaticae, vol. 27, no. 2-3, pp. 273-288, 1996