Tree-based algorithms for action rules discovery

One of the main goals in Knowledge Discovery is to find interesting associations between values of attributes, those that are meaningful in a domain of interest. The most effective way to reduce the amount of discovered patterns is to apply two interestingness measures, subjective and objective. Subjective measures are based on the subjectivity and understandability of users examining the patterns. They are divided into actionable, unexpected, and novel. Because classical knowledge discovery algorithms are unable to determine if a rule is truly actionable for a given user [1], we focus on a new class of rules [15], called E-action rules, that can be used not only for automatic analysis of discovered classification rules but also for hints of how to reclassify some objects in a data set from one state into another more desired one. Actionability is closely linked with the availability of flexible attributes [18] used to describe data and with the feasibility and cost [23] of desired re-classifications. Some of them are easy to achieve. Some, initially seen as impossible within constraints set up by a user, still can be successfully achieved if additional attributes are available. For instance, if a system is distributed and collaborating sites agree on the ontology [5], [6] of their common attributes, the availability of additional data from remote sites can help to achieve certain re-classifications of objects at a server site [23]. Action tree algorithm, presented in this paper, requires prior extraction of classification rules similarly as the algorithms proposed in [15] and [17] but it guarantees a faster and more effective process of E-action rules discovery. It was implemented as system DEAR 2.2 and tested on several public domain databases. Support and confidence of E-action rules is introduced and used to prune a large number of generated candidates which are irrelevant, spurious, and insignificant.