Fast rule extraction with binary-coded relations

Article type: Research Article

Authors: Pindur, Roman | Susmaga, Robert

Affiliations: Institute of Computing Science, Poznań University of Technology, Piotrowo 3a, 60-965 Poznań, Poland. E-mail: [email protected], [email protected]

Abstract: The induction of rules is one of the key issues of the Rough Sets Theory (RST). Generally, this problem is equivalent to finding prime implicants of a Boolean function, which is an NP-hard combinatorial problem. In practice, the NP-hardness makes solving medium-sized and large real-life problems difficult. To counteract this we propose a new algorithm, in which representation of relations between objects are represented in the form of binary vectors. The relations considered are: indiscernibility and dominance. It is an important enhancement of the classic RST approach, in which only indiscernibility was taken into account. Evaluation of the proposed algorithm in experiments with numerous real-life data sets produced satisfactory results.

Keywords: knowledge discovery, rough sets theory, preference modelling, decision rules, indiscernibly relation, dominance relation

DOI: 10.3233/IDA-2003-7104

Journal: Intelligent Data Analysis, vol. 7, no. 1, pp. 27-42, 2003