Beyond Support-Confidence Framework

The standard support-confidence framework suffers from a few weaknesses. Indeed, some of the rules generated with these measures may have poor predictive ability, which means the measures do not perfectly account for the semantics of directed associations. Besides, mining large dense databases with the standard algorithms generally leads to combinatorial explosion, making the approach impracticable. This chapter describes new measures aimed at improving the rule predictive ability and algorithms aimed at limiting combinatorial explosion. In Section 9.1 we present a criticism of the support-confidence framework and we propose a new measure to substitute for confidence. The new measure, so-called conviction, is shown to produce association rules with much better predictive ability. Algorithms for conviction-based rule generation and pruning are proposed. Limiting the complexity of the cas-enumeration procedure is the topic of the next section (Section 9.2). First, the complexity of the search space is drastically reduced. This is achieved by limiting the rule-mining problem to one in which the consequent of the rules is fixed (input of the mining algorithm). Next, in order to reduce the complexity of the search procedure, testing for confidence/conviction is shifted to the cas-enumeration process itself. New one-step sequential and parallel rule-mining algorithms are proposed as an alternative to the classical two-step algorithms. A new measure of rule improvement is also proposed, which yields an efficient improvement-based pruning algorithm. Finally, a new paradigm is presented in Section 9.3 as an alternative to association rule mining: correlated attribute sets are mined instead of association rules. The paradigm relies on a new measure called collective strength. The measure is presented and analyzed, and new efficient sequential and parallel algorithms based on it are developed.