Search

In this paper we present an incremental algorithm for computing the transversal hypergraph. Our algorithm is an optimized version of Berge's algorithm [2] for solving the transversal hypergraph problem. The original algorithm of Berge is the simplest and most direct scheme for generating all minimal transversals of a hypergraph. Here we present an optimized version of Berge's algorithm that we call BergeOpt. We show that BergeOpt can significantly reduce the number of expensive inclusion tests. [ABSTRACT FROM AUTHOR]

In this paper we present a new basis for association rules called Closed Association Rules (CR). This basis contains all valid association rules that can be generated from frequent closed itemsets. CR is a lossless representation of all association rules. Regarding the number of rules, our basis is between all association rules (AR) and minimal non-redundant association rules (MNR), filling a gap between them. The new basis provides a framework for some other bases and we show that MNR is a subset of CR. Our experiments show that CR is a good alternative for all association rules. The number of generated rules can be much less, and beside frequent closed itemsets nothing else is required. [ABSTRACT FROM AUTHOR]

Apriori is the most well-known algorithm for finding frequent itemsets (FIs) in a dataset. For generating interesting association rules, we also need the so-called frequent closed itemsets (FCIs) that form a subset of FIs. Apriori has a simple extension called Apriori-Close that can filter FCIs among FIs. However, it is known that vertical itemset mining algorithms outperform the Apriori-like levelwise algorithms. Eclat is another well-known vertical miner that can produce the same output as Apriori, i.e. it also finds the FIs in a dataset. Here we propose an extension of Eclat, called Eclat-Close that can filter FCIs among FIs. This way Eclat-Close can be used as an alternative of Apriori-Close. Experimental results show that Eclat-Close performs much better than Apriori-Close, especially on dense, highly-correlated datasets. [ABSTRACT FROM AUTHOR]