Mining of frequent sets using pruning, based on background knowledge

Abstract

Association rule mining is a technique to find useful patterns and associations in transactional databases. There have been developed a lot of algorithms for this purpose, among which are also APriori and FP-Growth. Though you can find new patterns and associations, the technique of association rule mining usually results in too many rules through which the user has to find those that are interesting to him/her. Among this large amount of association rules, there are also ones that are non-interesting, simply because they are known a priori, like for example isPregnant ! isFemale. Since these rules are not useful, their frequent itemsets also do not need to be generated. This method was already described in [Bog06], where the idea of knowledge constraints was applied to APriori. Because the FP-Growth algorithm is a lot faster than APriori, it seems logical to also apply this method to FP-Growth. The only drawback for this new algorithm (and also for APriori-KC) was that there were removed too many rules through this elimination of dependences. Therefore, we developed a method to recover the rules that were lost, without too much time going lost. The main advantage of this new algorithm is that it reduces the number of frequent itemsets significantly and thus also the total number of association rules that is generated.