{'fraction_non_alphanumeric': 0.03538461538461538, 'fraction_numerical': 0.008287841191066998, 'mean_word_length': 4.2641065830721, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Mining All Non-Derivable Frequent Itemsets

Recent studies on frequent itemset mining algorithms resulted in significant performance improvements. However, if the minimal support threshold is set too low, or the data is highly correlated, the number of frequent itemsets itself can be prohibitively large. To overcome this problem, recently several proposals have been made to construct a concise representation of the frequent itemsets, instead of mining all frequent itemsets. The main goal of this paper is to identify redundancies in the set of all frequent itemsets and to exploit these redundancies in order to reduce the result of a mining operation. We present deduction rules to derive tight bounds on the support of candidate itemsets. We show how the deduction rules allow for constructing a minimal representation for all frequent itemsets. We also present connections between our proposal and recent proposals for concise representations and we give the results of experiments on real-life datasets that show the effectiveness of the deduction rules. In fact, the experiments even show that in many cases, first mining the concise representation, and then creating the frequent itemsets from this representation outperforms existing frequent set mining algorithms.


Introduction
The frequent itemset mining problem [1] is by now well known. We are given a set of items I and a database D of subsets of I, together with a unique identifier. The elements of D are called transactions. An itemset I ⊆ I is some set of items; its support in D, denoted by support (I, D), is defined as the number of transactions in D that contain all items of I; and an itemset is called s-frequent in D if its support in D exceeds s. D and s are omitted when they are clear from the context. The goal is now, given a minimal support threshold and a database, to find all frequent itemsets.
The search space of this problem, all subsets of I, is clearly huge. Instead of generating and counting the supports of all these itemsets at once, several solutions have been proposed to perform a more directed search through all patterns.
However, this directed search enforces several scans through the database, which brings up another great cost, because these databases tend to be very large, and hence they do not fit into main memory.
The standard Apriori algorithm [2] for solving this problem is based on the monotonicity property: all supersets of an infrequent itemset must be infrequent. Hence, if an itemset is infrequent, then all of its supersets can be pruned from the search-space. An itemset is thus considered potentially frequent, also called a candidate itemset, only if all its subsets are already known to be frequent. In every step of the algorithm, all candidate itemsets are generated and their supports are then counted by performing a complete scan of the transaction database. This is repeated until no new candidate itemsets can be generated.
Recent studies on frequent itemset mining algorithms resulted in significant performance improvements. In the early days, the size of the database and the generation of a reasonable amount of frequent itemsets were considered the most costly aspects of frequent itemset mining, and most energy went into minimizing the number of scans through the database. However, if the minimal support threshold is set too low, or the data is highly correlated, the number of frequent itemsets itself can be prohibitively large. To overcome this problem, recently several proposals have been made to construct a concise representation of the frequent itemsets, instead of mining all frequent itemsets [13,3,6,5,14,15,7,11].
Our contributions The main goal of this paper is to present several new methods to identify redundancies in the set of all frequent itemsets and to exploit these redundancies, resulting in a concise representation of all frequent itemsets and significant performance improvements of a mining operation.
1. We present a complete set of deduction rules to derive tight intervals on the support of candidate itemsets.
2. We show how the deduction rules can be used to construct a minimal representation of all frequent itemsets, consisting of all frequent itemsets of which the exact support can not be derived, and present an algorithm that efficiently does so.
3. Also based on these deduction rules, we present an efficient method to find the exact support of all frequent itemsets, that are not in this concise representation, without scanning the database.
4. We present connections between our proposal and recent proposals for concise representations, such as free sets [6], disjunction-free sets [7], and closed sets [13]. We also show that known tricks to improve performance of frequent itemset mining algorithms, such as used in MAXMINER [4] and PASCAL [3], can be described in our framework.

5.
We present several experiments on real-life datasets that show the effectiveness of the deduction rules.
The outline of the paper is as follows. In Section 2 we introduce the deduction rules. Section 3 describes how we can use the rules to reduce the set of frequent itemsets. In Section 4 we give an algorithm to efficiently find this reduced set, and in Section 5 we evaluate the algorithm empirically. Related work is discussed in depth in Section 6.

Deduction Rules
In all that follows, I is the set of all items and D is the transaction database.
We will now describe sound and complete rules for deducing tight bounds on the support of an itemset I ⊆ I, if the supports of all its subsets are given. In order to do this, we will not consider itemsets that are no subset of I, and we can assume that all items in D are elements of I. Indeed, "projecting away" the other items in a transaction database does not change the supports of the subsets of I. • The I-projection of a transaction T , denoted π I T , is defined as π I T := {i | i ∈ T ∩ I}.
• The I-projection of a transaction database D, denoted π I D, consist of all I-projected transactions from D. Before we introduce the deduction rules, we introduce fractions and covers. If D is clear from the context, we will write f J I , and if J = I, we will write f I . The support of an itemset I is then I⊆I ′ ⊆I f I ′ .
From now on, we will denote the sum on the right-hand side of this last equation by σ(I, J).
Since f J I is always positive, we obtain the following theorem.
We will refer to the rule involving σ(I, J) as R J (I) and omit J when clear from the context.
If for each subset I ⊂ J, the support support (I, D) = s I is given, then the rules R J (.) allow for calculating lower and upper bounds on the support of J. Let l denote the greatest lower bound we can derive with these rules, and u the smallest upper bound we can derive. Since the rules are sound, the support of J must be in the interval [l, u]. In [8], we show also that these bounds on the support of J are tight ; i.e., for every smaller interval The proof of the completeness relies on the fact that for all I ⊆ J, we have support (I, D) = I⊆I ′ ⊆I f I ′ . We can consider the linear program consisting of all these equalities, together with the conditions f I ≥ 0 for all fractions f I . The existence of a database D ′ that satisfies the given supports is equivalent to the existence of a solution to this linear program in the f I 's and support (J, D ′ ). From this equivalence, tightness of the bounds can be proved. For the details of the proof we refer to [8].
Example 2.5. Consider the following transaction database. Figure 1: Tight bounds on s ABCD . s I denotes support (I) Figure 1 gives the rules to determine tight bounds on the support of ABCD.
Using these deduction rules, we derive the following bounds on s ABCD without counting in the database.
Lower bound: Therefore, we can conclude, without having to rescan the database, that the support of ABCD in D is exactly 1, while a standard monotonicity check would yield an upper bound of 2.

Non-Derivable Itemsets as a Concise Representation
Based on the deduction rules, it is possible to generate a summary of the set of frequent itemsets. Indeed, suppose that the deduction rules allow for deducing the support of a frequent itemset I exactly, based on the supports of its subsets. Then there is no need to explicitly count the support of I requiring a complete database scan; if we need the support of I, we can always simply derive it using the deduction rules. Such a set I, of which we can perfectly derive the support, will be called a Derivable Itemset (DI), all other itemsets are called Non-Derivable Itemsets (NDIs). We will show in this section that the set of frequent NDIs allows for computing the supports of all other frequent itemsets, and as such, forms a concise representation [12] of the frequent itemsets. To prove this result, we first need to show that when a set I is non-derivable, then also all its subsets are non-derivable. For each set I, let l I (u I ) denote the lower (upper) bound we can derive using the deduction rules.
This lemma gives us the following valuable insights. This remarkable fact is a strong indication that the number of large NDIs will be very small. This reasoning will be supported by the results of the experiments. Corollary 3.3. If I is a NDI, but it turns out that R I (J) equals the support of I, then all supersets I ∪ {i} of I will be a DI, with rules R I∪{i} (J) and R I∪{i} (J ∪ {i}).
We will use this observation to avoid checking all possible rules for I ∪ {i}. This avoidance can be done in the following way: whenever we calculate bounds on the support of an itemset I, we remember the lower and upper bound l I , u I . If I is a NDI; i.e., l I = u I , then we will have to count its support. After we counted the support, the tests support (I) = l I and support (I) = u I are performed. If one of these two equalities obtains, we know that all supersets of I are derivable, without having to calculate the bounds. Suppose that we want to build the entire set of frequent itemsets starting from the concise representation. We can then use this observation to improve the performance of deducing all supports. Suppose we need to deduce the support of a set I, and of a superset J of I; instead of trying all rules to find the exact support for J, we know in advance, because we already evaluated I, which rule to choose. Hence, for any itemset which is known to be a DI, we only have to compute a single deduction rule to know its exact support.
From Lemma 3.1, we easily obtain the following theorem, saying that the set of NDIs is a concise representation. We omit the proof due to space limitations. NDI(D, s) is a concise representation for the frequent itemsets, and for each itemset J not in NDI(D, s), we can decide whether J is frequent, and if J is frequent, we can exactly derive its support from the information in NDI(D, s).

The NDI-Algorithm
Based on the results in the previous section, we propose a level-wise algorithm to find all frequent NDIs. Since derivability is monotone, we can prune an itemset if it is derivable. This gives the NDI-algorithm as shown below. The correctness of the algorithm follows from the results in Lemma 3. up to depth k − 1 typically quickly decreases if k increases. Therefore, we can conclude that in practice most pruning is done by the rules of limited depth.

Experiments
For our experiments, we implemented an optimized version of the Apriori algorithm and the NDI algorithm described in the previous section. We performed our experiments on several real-life datasets with different characteristics, among which a dataset obtained from a Belgian retail market, which is a sparse dataset of 41 337 transaction over 13 103 items. The second dataset was the BMS-Webview-1 dataset donated by Z. Zheng et al. [16], containing 59 602 transactions over 497 items. The third dataset is the dense census-dataset as available in the UCI KDD repository [9], which we transformed into a transaction database by creating a different item for every attribute-value pair, resulting in 32 562 transactions over 22 072 items. The results on all these datasets were very similar and we will therefore only describe the results for the latter dataset. Figure 2 shows the average width of the intervals computed for all candidate itemsets of size k. Naturally, the interval-width of the singleton candidate itemsets is 32 562, and is not shown in the figure. In the second pass of the NDI-algorithm, all candidate itemsets of size 2 are generated and their intervals deduced. As can be seen, the average interval size of most candidate itemsets of size 2 is 377. From then on, the interval sizes decrease exponentially as was predicted by Corollary 3.2. Figure 3 shows the size of the concise representation of all NDIs compared to the total number of frequent patterns as generated by Apriori, for varying minimal support thresholds. If this threshold was set to 0.1%, there exist 990 097 frequent patterns of which only 162 821 are non-derivable. Again this shows the theoretical results obtained in the previous sections.
In the last experiment, we compared the strength of evaluating the deduction rules up to a certain depth, and the time needed to generate all NDIs w.r.t. the given depth. Figure 4 shows the results. On the x-axis, we show the depth up to which rules are evaluated. We denoted the standard Apriori monotonicity check by 0, although it is actually equivalent to the rules of depth 1. The reason for this is that we also used the other optimizations described in Section 3. More specifically, if the lower or upper bound of an itemset equals its actual support, we can prune its supersets, which is denoted as depth 1 in this figure. The left y-axis shows the number of NDIs w.r.t. the given depth and is represented by the line 'concise representation'. The line 'NDI' shows the time needed to generate these NDIs. The time is shown on the right y-axis. The 'NDI+DI' line shows the time needed to generate all NDIs plus the time needed to derive all DIs, resulting in all frequent patterns. As can be seen, the size of the concise representation drops quickly only using the rules of depth 1 and 2. From there on, higher depths result in a slight decrease of the number of NDIs. From depth 4 on, this size stays the same, which is not that remarkable since the number of NDIs of these sizes is also small. The time needed to generate these sets is best if the rules are only evaluated up to depth 2. Still, the running time is almost always better than the time needed to generate all frequent itemsets (depth 0), and is hardly higher for higher depths. For higher depths, the needed time increases, which is due to the number of rules that need to be evaluated. Also note that the total time required for generating all NDIs and deriving all DIs is also better than generating all frequent patterns at once, at depth 1,2,and 3. This is due to the fact that the NDI algorithm has to perform less scans through the transaction database. For larger databases this would also happen for the other depths, since the derivation of all DIs requires no scan through the database at all. 6 Related Work

Concise Representations
In the literature, there exist already a number of concise representations for frequent itemsets. The most important ones are closed itemsets, free itemsets, and disjunction-free itemsets. We compare the different concise representations with the NDI-representation.
Free sets [6] or Generators [11] An itemset I is called free if it has no subset with the same support. We will denote the set of all frequent free itemsets with FreqFree. In [6], the authors show that freeness is anti-monotone; the subset of a free set must also be free. FreqFree itself is not a concise representation for the frequent sets, unless if the set Border (FreqFree) := {I ⊆ I | ∀J ⊂ I : J ∈ FreqFree ∧ I / ∈ FreqFree} is added [6]. We call the concise representation consisting of these two sets ConFreqFree. Notice that free sets [6] and generators [13,11] are the same.
Disjunction-free sets [7] or disjunction-free generators [11] Disjunctionfree sets are essentially an extension of free sets. A set I is called disjunction-free if there does not exist two items i 1 , i 2 in I such that support (I) = support (I − . This rule is in fact our rule R I (I − {i 1 , i 2 }). Notice that free sets are a special case of this case, namely when i 1 = i 2 . We will denote the set of frequent disjunction-free sets by FreqDFree. Again, disjunction-freeness is anti-monotone, and FreqDFree is not a concise representation of the set of frequent itemsets, unless we add the border of FreqDFree. We call the concise representation containing these two sets ConFreqDFree.
Closed itemsets [13] Another type of concise representation that received a lot of attention in the literature [5,14,15] are the closed itemsets. They can be introduced as follows: the closure of an itemset I is the largest superset of I such that its support equals the support of I. This superset is unique and is denoted by cl(I). An itemset is called closed if it equals its closure. We will denote the set of all frequent closed itemsets by FreqClosed . In [13], the authors show that FreqClosed is a concise representation for the frequent itemsets.
In the following proposition we give connections between the different concise representations.
Proposition 6.1. For every dataset and support threshold, the following inequalities are valid.

The set of frequent closed itemsets is always smaller or equal in cardinality
than the set of frequent free sets.

The set of NDIs is always a subset of ConFreqDFree.
Proof.
1. We first show that Closed = cl (Free).
⊆ Let C be a closed set. Let I be a smallest subsets of C such that cl(I) = C. Suppose I is not a free set. Then there exist J ⊂ I such that support (J) = support (I). This rule however implies that support (J) = support (C). This is in contradiction with the minimality of I.
This equality implies that cl is always a surjective function from Free to Closed , and therefore, |Free| ≥ |Closed |.
2. Suppose I is not in ConFreqDFree. If I is not frequent, then the result is trivially satisfied. Otherwise, this means that I is not a frequent free set, and that there is at least one subset J of I that is also not a frequent free set (otherwise I would be in the border of FreqDFree.) Therefore, there exist i 1 , i 2 ∈ J such that support (J) = support (J − {i 1 }) + support (J − {i 2 }) − support (J − {i 1 , i 2 }) = σ(J, J − {i 1 , i 2 }). We now conclude, using Lemma 3.1, that I is a derivable itemset, and thus not in NDI.
Other possible inclusions between the described concise representations do not satisfy, i.e., for some datasets and support thresholds we have |NDI| < |Closed |, while other datasets and support thresholds have |Closed | < |NDI|. We omit the proof of this due to space limitations. We should however mention that even though FreqDFree is always a superset of NDI, in the experiments the gain of evaluating the extra rules is often small. In many cases the reduction of ConFreqDFree, which corresponds to evaluating rules up to depth 2 in our framework, is almost as big as the reduction using the whole set of rules. Since our rules are complete, this shows that additional gain is in many cases unlikely.

Counting Inference
MAXMINER [4] In MAXMINER, Bayardo uses the following rule to derive a lower bound on the support of an itemset: PASCAL [3] In their PASCAL-algorithm, Bastide et al. use counting inference to avoid counting the support of all candidates. The rule they are using to avoid counting is based on our rule R I (I − {i}). In fact the PASCAL-algorithm corresponds to our algorithm when we only check rules up to depth 1, and do not prune derivable sets. Instead of counting the derivable sets, we use the derived support. Here the same remark as with the ConFreqDFree-representation applies; although PASCAL does not use all rules, in many cases the performance comes very close to evaluating all rules, showing that for these databases PASCAL is nearly optimal.