Approximate Reducts and Association Rules - Correspondence and Complexity Results
Hung Son Nguyen, Dominik Ślȩzak · 1999
. We consider approximate versions of fundamental notions of theories of rough sets and association rules. We analyze the complexity of searching for ff-reducts, understood as subsets discerning "ff-almost" objects from different decision classes, in decision tables. We present how optimal approximate association rules can be derived from data by using heuristics for searching for minimal ff-reducts. NP-hardness of the problem of finding optimal approximate association rules is shown as well. It makes the results enabling the usage of rough sets algorithms to the search of association rules extremely important in view of applications. 1 Introduction Theory of rough sets ([5]) provides efficient tools for dealing with fundamental data mining challenges, like data representation and classification, or knowledge description (see e.g. [2], [3], [4], [8]). Basing on the notions of information system and decision table, the language of reducts and rules was proposed for expressing ...