AQ, rough sets, and matroid theory. (English) Zbl 0819.68048

Tsumoto, Shusaku; Tanaka, Hiroshi

Ziarko, Wojciech P. (ed.), Rough sets, fuzzy sets and knowledge discovery. Proceedings of the international workshop, RSKD ’93, Banff, Alberta, Canada, 12-15 October 1993. London: Springer-Verlag (in collab. with the British Computer Society). Workshops in Computing. 290-297 (1994).

Summary: In order to acquire knowledge from database, 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 database, 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 knowledge from databases whose patterns are described as the combination of attribute-value pairs. Combination of the concepts of rough sets and matroid theory gives us an excellent framework and enables us to understand the differences and the similarities of these methods clearly. Using this framework, we compare three methods, AQ, Pawlak’s Consistent Rules. The results shows that they generate bases of Matroid from attribute-value space and that their solutions are optimal to the classification of the training samples.
For the entire collection see [Zbl 0812.00038].

MSC:

68P15	Database theory
68T30	Knowledge representation
03E99	Set theory

Keywords:

inductive learning; rough sets; Matroid