Mining Consistent, Non-Redundant and Minimal Negative Rules Based on Minimal Generators
Koji Iwanuma, Kento Yajima, Yoshitaka Yamamoto · 2020
Essentially, any negative association rules are constructed over infrequent underling itemsets, thus the number of valid negative rules is always quite huge, and effective extraction of negative rules is quite difficult. In this paper, we study an efficient mining algorithm of negative rules over minimal generators, where a set of negative rules can be effectively compressed by using minimal generators, especially for dense data. We first propose new two concepts, so called consistency and non-redundancy, for a set consisting of both positive and negative association rules. Next, we prove some a fundamental but important property for minimal generators, which enables us to construct a suffix tree over minimal generators. We show a new top-down algorithm for mining a consistent and non-redundant set of negative association rules. The top-down search uses the suffix tree in order to restrict some negative rules to be right-minimal, which also suppress the burst of negative rules. Finally, we show preliminary results of experimental evaluation for the proposed negative rule mining method.