Model-based probabilistic frequent itemset mining

Let \(V\) be a set of items. In the attribute uncertainty model [10, 23, 32, 39], each attribute value carries some uncertain information. Here, we adopt the following variant [39]: a database \(D\) contains \(n\) tuples, or transactions. Each transaction \(t_j\) is associated with a set of items taken from \(V\). Each item \(v \in V\) exists in \(t_j\) with an existential probability \(Pr(v \in t_j) \in (0,1]\), which denotes the chance that \(v\) belongs to \(t_j\). In Table 1, for instance, the existential probability of video in \(t_{Jack}\) is \(Pr(video_{Jack}) = 1/2\). This model can also be used to describe uncertainty in binary attributes. For instance, the item \(video\) can be considered as an attribute, whose value is one, for Jack’s tuple, with probability \(\frac{1}{2}\), in tuple \(t_{Jack}\).

Under the possible world semantics (PWS), \(D\) generates a set of possible worlds \(\mathcal W \). Table 2 lists all possible worlds for Table 1. Each world \(w_i \in \mathcal W \), which consists of a subset of attributes from each transaction, occurs with probability \(Pr(w_i)\). For example, \(Pr(w_2)\) is the product of: (1) the probability that Jack purchases food but not video (equal to \(\frac{1}{2}\)) and (2) the probability that Mary buys clothing and video only (equal to \(\frac{1}{9}\)). As shown in Table 2, the sum of possible world probabilities is one, and the number of possible worlds is exponentially large. Our goal is to discover frequent patterns without expanding \(D\) into possible worlds.

In the tuple uncertainty model, each tuple or transaction is associated with a probability value. We assume the following variant [13, 31]: each transaction \(t_j \in D\) is associated with a set of items and an existential probability \(Pr(t_j) \in (0,1]\), which indicates that \(t_j\) exists in \(D\) with probability \(Pr(t_j)\). Again, the number of possible worlds for this model is exponentially large. Table 4 summarizes the symbols used in this paper.

Let \(I \subseteq V\) be a set of items, or an itemset. The support of \(I\), denoted by \(s(I)\), is the number of transactions in which \(I\) appears in a transaction database [5]. In precise databases, \(s(I)\) is a single value. This is no longer true in uncertain databases, because in different possible worlds, \(s(I)\) can have different values. Let \(S(w_j, I)\) be the support count of \(I\) in possible world \(w_j\). Then, the probability that \(s(I)\) has a value of \(i\), denoted by \(\Pr ^I(i)\), is:Hence, \(Pr^I(i) (i=1,\ldots ,n)\) form a probability mass function (or pmf) of \(s(I)\). We call \(Pr^I\) the support pmf (or s-pmf) of \(I\). In Table 2, for instance, \(Pr^{\{\textit{video}\}}(2)=Pr(w_6) + Pr(w_8) = \frac{1}{6}\), since \(s(I)=2\) in possible worlds \(w_6\) and \(w_8\). Figure 1 shows the s-pmf of {video}.

Now, let \(minsup \in (0, n]\) be an integer. An itemset \(I\) is said to be frequent if \(s(I) \ge minsup\) [5]. For uncertain databases, the frequentness probability of \(I\), denoted by \(Pr_{freq}(I)\), is the probability that an itemset is frequent [39]. Notice that \(Pr_{freq}(I)\) can be expressed as:In Fig. 1, if \(minsup=1\), then \(Pr_{freq}(\{\textit{video}\}) = Pr^{\{\textit{video}\}}(1) + Pr^{\{\textit{video}\}}(2) = \frac{2}{3}\).

Using frequentness probabilities, we can determine whether an itemset is frequent. We identify two classes of Probabilistic Frequent Itemsets (or PFI) below:Before we move on, we would like to mention the following theorem, which was discussed in [39]:

This theorem will be used in our algorithms.

Next, we derive efficient s-pmf computation methods in Sect. 4. Based on these methods, we present algorithms for retrieving threshold-based and rank-based PFIs in Sects. 5 and  6, respectively.

A simple and efficient way to evaluate the frequentness of an itemset in an uncertain transaction database is to use the expected support [3, 12]. The expected support converges to the exact support when increasing the number of transactions according to the “law of large numbers.”

For notational convenience, let \(p_j^I\) be \(Pr(I \subseteq t_j)\). Since the expectation of a sum is the sum of the expectations, the expected value of \(X^I\), denoted by \(\mu _I\), can be computed by:Given the expected support \(\mu _I\), we can approximate the cdf \(Pr_{\le }^I(i)\) of \(X^I\) as follows:According to the above equation, the frequentness probability \(Pr_{freq} (I)\) of itemset \(I\) is approximated by 1, if \(\mu _I\) is at least \(minsup\) and 0 otherwise. The computation of \(\mu _I\) can be efficiently done by scanning \(D\) once and summing up \(p_j^I\)’s for all tuples \(t_j\) in \(D\). As an example, consider the support of itemset \(\{video\}\) in Table 1. Computing \(\mu _I=0.5+0.33\) yields the approximated pmf depicted in Fig. 2a. Obviously, the expected support is only a very coarse approximation of the exact support distribution. Important information about the distribution, for example the variance, is lost with this approximation. In fact, we do not know how confident the results are. In the following, we provide a more accurate approximation for \(Pr_{\le }^I(i)\) by taking the (exact) distribution into consideration.

A Poisson binomial distribution can be well approximated by a Poisson distribution [8] following the “Poisson law of small numbers”.

According to this law, Eq. 10 can be written as:where \(F_{p}\) is the cdf of the Poisson distribution with mean \(\mu _I\), that is, \(F_{p}({ minsup} - 1,\mu _I)=1 - \frac{\varGamma ({ minsup}, \mu _I)}{({ minsup} - 1)!}\), where \(\varGamma ({ minsup}, \mu _I) = \int _{\mu _I}^\infty {t^{{ minsup}-1}e^{-t}dt}\).

As an example, consider again the support of itemset \(\{video\}\) in Table 1. Computing \(\mu =\lambda ^I=0.5+0.33\) yields the approximated pmf depicted in Fig. 2b. A theoretical analysis of the approximation quality is shown in Appendix 8. The upper bound of the error is small. According to our experimental results, the approximation is quite accurate.

To estimate \(Pr_{freq}(I)\), we can first compute \(\mu _I\) by scanning \(D\) once as described above and evaluate \(F_{p}({ minsup} - 1, \mu _I)\). Then, Eq. 13 is used to approximate \(Pr_{freq}(I)\).

Provided \(|D|\) is large enough which usually holds for transaction databases, \(X^I\) converges to the normal distribution with mean \(\mu _I\) and variance \(\sigma _{I}^{2}\), whereaccording to the “Central Limit Theorem”.

Computing \(\mu =0.5+0.33\) and \(sigma^{2}=0.5\cdot 0.5+0.33\cdot 0.67=0.471\) yields the approximated pmf depicted in Fig. 3a. The continuity correction which is achieved by running the integral up to \(minsup-0.5\) instead of \(minsup-1\) is an important and common method to compensate the fact that \(X^I\) is a discrete distribution approximated by a continuous normal distribution. The effect of the continuity correction is shown in Fig. 3b.

The estimation of \(Pr_{freq}(I)\) can be done by first computing \(\mu _I\) by scanning \(D\) once, summing up \(p_j^I\)’s for all tuples \(t_j\) in \(D\) and using Eq. 14 to approximate \(Pr_{freq}(I)\). For an efficient evaluation of \(F_{n}( {minsup} - 1, \mu _I)\), we use the Abromowitz and Stegun approximation [2] which is necessary because the cumulative normal distribution has no closed-form solution. The result is a very fast parametric test to evaluate the frequentness of an itemset.

While the above method still requires a full scan of the database to evaluate one frequent itemset candidate, threshold- and rank-based PFIs can be found more efficiently.

In this section, we have described three models to approximate the Poisson binomial distribution. Now, we will discuss the advantages and disadvantages of each model theoretically, while in Sect. 7 we will experimentally support the claims made here.

Each of the approximation models is based on a fundamental statistics theorem. In particular, the Expected approach exploits the Law of Large Numbers [35], the Normal Approximation approach exploits the Central Limit Theorem [16], and the Poisson Approximation approach exploits the Poisson Law of Small Numbers [34].

Approximation based on expected support In consideration of the “Law of large numbers,” the Expected approach requires a large \(n\), that is, a large number of transactions, where the respective itemset is contained with a probability greater than zero. A thorough evaluation of this parameter can be found in the experiments.

Normal distribution-based approximation The rule of thumb for the central limit theorem is, is that for \(n\ge 30\), that is, for at least 30 transactions containing the respective itemset with a probability larger than zero, the normal approximation yields good results. This rule of thumb, however, depends on certain circumstances, namely, the probabilities \(P(X_i=1)\) should be close to 0.5. In our experiments, we will evaluate for what settings (e.g., databases size, itemset probabilities) the normal approximation yields good results.

Poisson distribution-based approximation In consideration of the Poisson Law of Small Numbers, the Poisson approximation theoretically yields good results, if all probabilities \(P(X_i)\) are small. This seems to be a harsh assumption, since it forbids any probabilities of one, which are common in real data sets. However, it can be argued that, for large itemsets, the probability may always become small in some applications. In the experiments, we will show how small \(\max \{P(X_1),\ldots ,P(X_n)\}\) is required to be, in order to achieve good approximations, and how “a few” large probabilities impact the approximation quality. In addition, our experiments aim to give an intuition, in what setting which approximation should be used to achieve the best approximation results.

Computational complexity Each approximation technique requires to compute the expected support \(E(X)=\mu =\lambda =\sum _{i=1}^{n}P(X_i)\), which requires a full scan of the database requiring \(O(n)\) time and \(O(1)\) space. The normal approximation additionally requires to compute the sum of variances, which has the same complexity. This is all that has to be done to compute the parameters of all three approximations. After that, the Expected approach only requires to compare \(E(X)\) with \(MinSupp\), at a cost of \(O(1)\) time. The normal approximation approach in contrast requires to compute the probability that \(X>MinSupp\), which requires numeric integration, since the normal distribution it has no closed-form expression. However, there exist very efficient techniques (such as the Abromowitz and Stegun approximation [2]) to quickly evaluate the normal distribution. Regardless, this evaluation is independent of the database size and also requires constant time. The same rationale applies for the Poisson approximation, which does also not have a closed-form solution, but for which there exist manifold fast approximation techniques. In summary, each of the approximation techniques has a total runtime complexity of \(O(n+C_i)\) and a space complexity of \(O(1)\). The constant \(C_i\) depends on the approximation technique. In the experiments, we will see that the impact of \(C_i\) can be neglected in runtime experiments. In summary, each of the proposed approximation techniques runs in O(n) time. These are more scalable methods compared to solutions in [39, 46], which evaluate \(Pr_{freq}(I)\) in \(O(n^2)\) time.

Given the values of \(minsup\) and \(minprob\), we need to test whether \(I\) is a threshold-based PFI. Therefore, we first need the following definition:

The computation of the p-value is an inherent method in any statistical program package. For instance, in the statistical computing package R, the p-value of a value \(x\) of a normal distribution with mean \(\mu \) and variance \(\sigma ^{2}\) is obtained using the function \(pnorm(x,\mu ,\sigma ^2)\). For the Poisson distribution, the function \(ppois(x,\mu )\) is used. For the expected approximation, simply return \(1\) is \(\mu >minsup\) and \(0\) otherwise.

Since \(p\text{-}value(minsup,support(I))\) corresponds to the probability that the support of itemset \(I\) is equal or less than \(minsup\), we can derive the probability \(Pr_{freq}(I)\) that the support is at least \(minsup\) simply as follows:which is approximated bywhere \(P(support(I)=minsup)\) is the probability that the support of \(I\) is exactly minsup, and \(\epsilon \) is a very small number (e.g., \(\epsilon =10^{\{-10\}}\)).

Now, to decide whether \(I\) is a threshold-based PFI, given the values of \(minsup\) and \(minprob\) we apply the following three steps:

In the following, we show pruning techniques which are applicable for the expected support model as well as the Poisson approximation model. For the normal approximation, we give a counter-example, why the proposed pruning strategy may yield wrong results.

In Step 1 of the last section, \(D\) has to be scanned once to obtain \(\mu _I\) and \(\sigma ^{2}_I\), for every itemset \(I\). This can be costly if \(D\) is large, and if many itemsets need to be tested. For example, in the Apriori algorithm [39], many candidate itemsets are generated first before testing whether they are PFIs. In the following, we will define a monotonicity criterion which can be used to decide if \(I\) is frequent by only scanning a subset of the database. In the following, we will show that for the model using expected support and for the Poisson approximation model, the above lemma holds, that is, \((Pr_{freq}(I))_i\) increases monotonically in \(i\). For the normal approximation, however, we will show a counter-example to illustrate that the above property does not hold.

The cdf of a Poisson distribution, \(F_{p}(i, \mu )\), can be written as: \(F_{p}(i, \mu ) = \frac{\varGamma (i+1, \mu )}{ i !} = \frac{\int _\mu ^\infty {t^{(i+1)-1}e^{-t} dt}}{i !}\)

Since \(minsup\) is fixed and independent of \(\mu \), let us examine the partial derivative w.r.t. \(\mu \).Thus, the cdf of the Poisson distribution \(F_{p}(i, \mu )\) is monotonically decreasing w.r.t. \(\mu \), when \(i\) is fixed. Consequently, \(1 - F_{p}(i - 1, \mu )\) increases monotonically with \(\mu \). Theorem 2 follows immediately by substituting \(i=\textit{minsup}\).

Note that intuitively, Theorem 2 states that the higher value of \(\mu _I\), the higher is the chance that \(I\) is a PFI.

Property 6 leads to the following:

Using Lemma 5, a PFI can be verified by scanning only a part of the database.

True hits Let \((\mu _I)_l = \sum _{j=1}^l p_j\) and \((\sigma ^{2}_I)_l= \sum _{j=1}^l p_j\cdot (1-p_j)\), where \(l \in (0,n]\). Essentially, \((\mu _I)_l\) (\((\sigma ^{2}_I)_l\)) is the “partial value” of \(\mu _I\) (\(\sigma ^{2}_I\)), which is obtained after scanning \(l\) tuples. Notice that \((\mu _I)_n=\mu _I\) and \((\sigma ^{2}_I)_n=\sigma ^{2}_I\).

To perform pruning based on the values of \((\mu _I)_l\) and \((\sigma ^{2}_I)_l\), we first define the following property:

Avoiding integration We next show the following. To perform the true hit detection as proposed above, we require to evaluate \((Pr_{freq}(I))_i\) for each \(i \in 1,\ldots ,n\). In the case of the expected support approximation, this only requires to check if \((\mu _I)_i>minsup\). However, for the Poisson approximation, this requires to evaluate a poisson distribution at minsup. Since the Poisson distribution has no closed-form solution, this requires a large number of numeric integrations, which can be, depending on their accuracy, computationally very expensive. In the following, we show how to perform pruning using the Poisson approximation model, while avoiding the integrations.²

Given the values of \(minsup\) and \(minprob\), we can test whether \((Pr_{freq}(I))_i>minprob\) as follows:To understand why this works, first notice that the right side of Eq. 16 is the same as that of Eqs. 13 or 14, an expression of frequentness probability. Essentially, Step 1 finds out the value of \((\mu )_m\) that corresponds to the frequentness probability threshold (i.e., minprob). In Steps 2 and 3, if \(\mu _I \ge (\mu )_m\), Theorem 2 allows us to deduce that \(Pr_{freq}(I) > \textit{minprob}\). Hence, these steps together can test whether an itemset is a PFI.

In order to verify whether \(I\) is a PFI, once \((\mu )_m\) is found, we do not have to evaluate \((Pr_{freq}(I))_i\). Instead, we compute \((\mu _I)_i\) in Step 2, which can be done in \(O(1)\) time using \((\mu _I)_{i-1}\). In the next paragraph, we show how the observation made in this paragraph can be used to efficiently detect true drops, that is, itemsets for which we can decide that \(\mu _I<(\mu )_m\) by only considering \((\mu _I)_i\).

This lemma leads to the following corollary.

We use an example to illustrate Corollary 1. Suppose that \((\mu )_m = 1.1\) for the database in Table 1. Also, let \(I\) = {clothing, video}. Using Corollary 1, we do not have to scan the whole database. Instead, only the tuple \(t_{Jack}\) needs to be read. This is because:Since Eq. 19 is satisfied, we confirm that \(I\) is not a PFI without scanning the whole database.

We use the above results to improve the speed of the PFI testing process. Specifically, after a tuple has been scanned, we check whether Lemma 5 is satisfied; if so, we immediately conclude that \(I\) is a PFI. After scanning \(n- \lfloor {(\mu )_m}\rfloor \) or more tuples, we examine whether \(I\) is not a PFI, by using Corollary 1. These testing procedures continue until the whole database is scanned, yielding \(\mu _I\). Then, we execute Step 3 (Sect. 5.1) to test whether \(I\) is a PFI.

The testing techniques just mentioned are not associated with any specific threshold-based PFI mining algorithms. Moreover, these methods support both attribute and tuple uncertainty models. Hence, they can be easily adopted by existing algorithms. We now explain how to incorporate our techniques to enhance the Apriori [39] algorithm, an important PFI mining algorithms.

The resulting procedures (Algorithm 1 for Poisson approximation and expected support, and Algorithm 2 for normal approximation) use the “bottom-up” framework of the Apriori: starting from \(k=1\), size-\(k\) PFIs (called \(k\)-PFIs) are first generated. Then, using Theorem 1, size-\((k+1)\) candidate itemsets are derived from the \(k\)-PFIs, based on which the \(k\)-PFIs are found. The process goes on with larger \(k\), until no larger candidate itemsets can be discovered.

The main difference of Algorithm 1 and Algorithm 2 compared with that of Apriori [39] is that all steps that require frequentness probability computation are replaced by our PFI testing methods. In particular, Algorithm 1 first computes \((\mu )_m\) (Line 2–3) depending on whether the expected support model or the Poisson approximation model is used.

Then, for each candidate itemset \(I\) generated on Line 4 and Line 17, we scan \(D\) and compute its \((\mu _I)_i\) (Line 10) and \((\sigma ^{2}_I)_i\). Unless the normal approximation is used, pruning can now be performed: If Lemma 5 is satisfied, then \(I\) is put to the result (Lines 11–13). However, if Corollary 1 is satisfied, \(I\) is pruned from the candidate itemsets (Lines 14–16). This process goes on until no more candidates itemsets are found.

Complexity. In Algorithm 1, each candidate item needs \(O(n)\) time to test whether it is a PFI. This is much faster than the Apriori [39], which verifies a PFI in \(O(n^2)\) time. Moreover, since \(D\) is scanned once for all \(k\)-PFI candidates \(C_k\), at most a total of \(n\) tuples is retrieved for each \(C_k\) (instead of \(|C_k|\cdot n\)). The space complexity is \(O(|C_k|)\) for each candidate set \(C_k\), in order to maintain \(\mu _I\) for each candidate.

Given an itemset \(I\) retrieved from \(Q\), in [39] a candidate itemset is generated from \(I\) by unioning \(I\) with every single item in \(V\). Hence, the maximum number of candidate itemsets generated is \(|V|\), which is the number of single items.

We argue that the number of candidate itemsets can actually be fewer, if the contents of \(Q\) are also considered. To illustrate this, suppose \(Q\) = {{abc}, {bcd}, {efg}}, and \(I\)={abc} has the highest frequentness probability. If the generation step of [39] is used, then four candidates are generated for \(I\): {{abcd}, {abce}, {abcf}, {abcg}}). However, \(Pr_{freq}(\{\textit{abce}\}) \le Pr_{freq}(\{\textit{bce}\})\), according to Theorem 1. Since \(\{bce\}\) is not in \(Q\), \(\{bce\}\) must also be not a top-\(k\) PFI. Using Theorem 1, we can immediately conclude that \(\{abce\}\), a superset of \(\{bce\}\), cannot be a top-\(k\) PFI. Hence, \(\{abce\}\) cannot be a top-k PFI candidate. Using similar arguments, {abcf} and {abcg} do not need to be generated, either. In this example, only \(\{abcd\}\) should be a top-k PFI candidate.

Algorithm. Based on this observation, we redesign the generation step (Line 9 of Algorithm 3) as follows: for any itemsets \(I^{\prime } \in Q\), if \(I\) and \(I^{\prime }\) contain the same number of items, and there is only one item that differentiates \(I\) from \(I^{\prime }\), we generate a candidate itemset \(I \cup I^{\prime }\). This guarantees that \(I \cup I^{\prime }\) contains items from both \(I\) and \(I^{\prime }\).

Since \(Q\) has at most \(k\) itemsets, the new algorithm generates at most \(k\) candidates. In practice, the number of single items (\(|V|\)) is large compared with \(k\). For example, in the accidents Dataset used in our experiments, \(|V|=572\). Hence, our algorithm generates fewer candidates and significantly improves the performance of the solution in [39], as shown in our experimental results.

After the set of candidate itemsets, \(C\), is generated, [39] performs testing on them by first computing their exact frequentness probabilities, then comparing with the minimal frequentness probability, \(Pr_{min}\), for all itemsets in \(Q\). Only those in \(C\) with probabilities larger than \(Pr_{min}\) are added to \(Q\). As explained before, computing frequentness probabilities can be costly. Here, we propose a faster solution based on the results in Sect. 4. The main idea is that instead of ranking the itemsets in \(Q\) based on their frequentness probabilities, we order them according to their \(\mu _I\) values. Also, for each \(I^{\prime } \in C\), instead of computing \(Pr_{freq}(I^{\prime })\), we evaluate \(\mu _{I^{\prime }}\). These values are then compared with \((\mu )_{min}\), the minimum value of \(\mu _I\) among the itemsets stored in \(Q\). Only candidates whose \(\mu _{I^{\prime }}\)s are not smaller than \((\mu )_{min}\) are placed into \(Q\). An itemset \(I^{\prime }\) selected in this way has a good chance to satisfy \(Pr_{freq}(I^{\prime }) \ge Pr_{min}\), according to Theorem 2, as well as being a top-\(k\) PFI. Hence, by comparing the \(\mu _I\) values, we avoid computing any frequentness probability values.

Complexity. The details of the above discussions are shown in Algorithm 3. As we can see, \(\mu _{I^{\prime }}\), computed for every itemset \(I^{\prime } \in C\), is used to determine whether \(I^{\prime }\) should be put into \(Q\). During each iteration, the time complexity is \(O(n+k)\). The overall complexity of algorithm is \(O(kn + k^2)\). This is generally faster than the solution in [39], whose complexity is \(O(kn^2 + k|V|)\).

We conclude this section with an example. Suppose we wish to find top-2 PFIs from the dataset in Table 1. There are four single items, and the initial capacity of \(Q\) is \(k = 2\). Suppose that after computing the \(\mu _I\)s of single items, {food} and {clothing} have the highest values. Hence, they are put to \(Q\) (Table 5). In the first iteration, {food}, the PFI with the highest \(\mu _I\) is returned as the top-1 PFI. Based on our generation step, {food, clothing} is the only candidate. However, \(\mu _{\{\textit{food, clothing}\}}\) is smaller than \((\mu )_{min}\), which corresponds to the minimum \(\mu _I\) among itemsets in \(Q\). Hence, {food, clothing} is not put to \(Q\). Moreover, the capacity of \(Q\) is reduced to one. Finally, {clothing} is popped from \(Q\) and returned.

We now compare the performance of five threshold-based PFI mining algorithms mentioned in this paper: (1) DP, the Apriori algorithm used in [39]; (2) Expected, the modified Apriori algorithm that uses the expected support only [12]; (3) Poisson, the modified Apriori algorithm that uses the Poisson approximation employing the PFI testing method (Sect. 5.1); (4) Normal, the modified Apriori algorithm that uses the normal approximation, also employing the PFI testing method (Sect. 5.1); and (5) MBP, the algorithm that uses the Poisson approximation utilizing the improved version of the PFI testing method (Sect. 5.2).

(i) Accuracy. Since the model-based approaches Expected, Poisson and Normal each approximate the exact s-pmf, we first examine their respective accuracy with respect to DP, which yields PFIs based on exact frequentness probabilities. Here, we use the standard recall and precision measures [7], which quantify the number of negatives and false positives. Specifically, let MB \(\in \) {Expected, Poisson, Normal} be one of the model-based approximation approaches, and let \(F_{DP}\) be the set of PFIs generated by DP and \(F_{MB}\) be the set of PFIs produced by MB. Then, the recall and the precision of MB, relative to DP, can be defined as follows: In these formulas, both recall and precision have values between 0 and 1. Also, a higher value reflects a better accuracy.

Table 6(a) to (c) shows the recall and the precision of the MB approaches, for a wide range of \(minsup\), \(n\), and \(minprob\) values. As we can see, the precision and recall values are generally very high. Hence, the PFIs returned by the MB approaches are highly similar to those returned by DP. In particular, we see that the Expected approach generally yields the worst results, having precision and recall values of less than 95 % in some setting. The Poisson approach performs significantly better in these experiments. Yet in some settings, the Poisson approach reports false hits, while in other settings, it performs false dismissals. The Normal approach is most notable in this experiment. In this set of experiments, the Normal approach never had a false dismissal, nor did it report a single false hit. This observation also remained true for further experiments in this line, which are not depicted here. In the next set of experiments, we will experimentally investigate the effectivity of the MB approach.

Figure 4 shows the exact pmf, as well as the pmfs approximated by the Poisson and the Normal approach, for a variety of settings. In particular, we scaled both the dataset size and the size of the itemsets whose pmf is to be approximated. Since, in this setting, the probabilities of individual items are uniformly sampled in the \([0,1]\) interval, and since due to the assumption of item independence, it holds that \(P(I)=\prod _{i\in I}P(i)\), a large itemset \(I\) implies smaller existence probabilities. In Fig. 4a, it can be seen that for single itemsets (i.e., large probability values), the pmf acquired by the Poisson approximation is too shallow—that is, for support values close to \(\mu _I\) the exact pmf is underestimated, while for support values far from \(\mu _I\), the pmf is overestimated. In Fig. 4d, g it can be observed that this situation does not improve for the Poisson approximation. However, this shortcoming of the Poisson approximation can be explained: Since the Poisson approximation does only have one parameter \(\mu _I\), but no variance parameter \(\sigma {^2}{_I}\), it is not able to differ between a set of five transactions with occurrence probabilities of \(1\), and five million transactions with occurrence probabilities of \(10^{-6}\), since in both scenarios it holds that \(\mu _I=5\cdot 1=5\cdot 10^6\cdot 10^{-6}=5\). Clearly, the variance is much greater in the later case, and so are the tails of the corresponding exact pmf. Since the Poisson distribution is the distribution of the low probabilities, the Poisson assumes the later case, i.e., a case of very many transactions, each having a very low probability. In contrast, the normal distribution is able to adjust to these different situations by adjusting its \(\sigma {^2}{_I}\) parameter accordingly. Figure 4b, e, h show the same experiments for itemsets consisting of two items, that is, for lower probabilities \(I\subseteq t_i\). It can be observed that with lower probabilities, the error of the Poisson approximation decreases, while (as we will see later, in Table 7) the quality of the normal approximation decreases. Finally, for itemsets of size \(5\), the Poisson approximation comes very close to the exact pmf.

To gain a better intuition of the approximation errors, we have repeated each of the experiments shown in Fig. 4 one hundred times and measured the total approximation error. That is, we have measured for each approximation DP \(\in \){Normal, Poisson} the distance to the exact pmf, computed by the DP approach:The results of this experiment are shown in Table 7. Clearly, the approximation quality of the Normal approach decreases when the size of the itemsets increases (i.e., the probabilities become smaller), while the Poisson approach actually improves. An increase in the database size, is beneficial for both approximation approaches.

The impact of increasing the database size on the individual approximation models has been investigated further in Fig. 5. In this experiment, we use a synthetic itemset where each item is given a random probability uniformly distributed in \([0,1]\). In Fig. 5a–c, the average frequentness probability \(Pr_{freq}(I)\) that item \(I\) is frequent is depicted for all itemsets \(I\) consisting of one item. Since all probabilities are uniformly \([0,1]\) distributed, it is clear that \(\mu _I\) is about \(\frac{n}{2}\). Thus, for minsup=0.49, the probability that an item is frequent increases in the database size, for minsup = 0.5, about half of the items are frequent, and for minsup = 0.51, the number of frequent items decreases in the database size. First, it can be observed that the Normal approximation is nearly perfect, since no error between the exact \(Pr_{freq}(I)\) and it’s Normal approximated value can be observed visually. This is also confirmed by Fig. 5d–f, which show the respective error, that is, the differences between the exact frequentness probability and the approximated frequentness probabilities. In contrast, the Poisson approximation does show a significant error for smaller databases. For minsup = 0.49 and minsup = 0.51, the Poisson approximation is also able to yield very good approximation for database sizes larger than 50.000 while the expected support yields good results for even smaller databases. The reason is that in this case, all the exact frequentness probabilities quickly converge to 1 (0), which can easily be guessed by the expected approach. However, the interesting case is the case where minsup = 0.5, since in this case, the items are expected to have an average frequentness probability of 0.5. However, in this case, the expected approach is forced to guess, since it may only take the values \(0\) and \(1\). This explains the large error of the expected approach, which does not decrease in the database size. The Poisson approach performs significantly better than the expected approach, but still the error is relatively high, which matches our previous experiments for large probabilities. To achieve a better setting for the Poisson approximation, we changed the interval from which the item probabilities are sampled, from \([0,1]\) to \([0,0.1]\), and repeated the experiment for minsup=0.5. The results are depicted in Fig. 5g, h). It can be observed that in this setting, the Poisson approximation achieves extremely good results, even slightly outperforming the Normal approximation. In Fig. 5i, the expected approach is omitted, to give a better view on the difference of the normal and the Poisson error.

In the previous setting, we have evaluated the performance of the model-based approximation approaches in the case where all items have the same occurrence probabilities. We have seen that for small probabilities, the Poisson approximation works well. Next we will evaluate how many probability values are allowed to be large, in order for the Poisson approximation to still yield good results. In the following experiment, we introduce a new parameter \(lowP\), which denotes the fraction of the item probabilities, which are chosen from a smaller interval, such as the interval \([0,0.01]\), while the remaining \(1-lowP\) fraction of the items has their probabilities chosen from the \([0,1]\) interval. The result of the experiment evaluating the impact of \(lowP\) is given in Fig. 6. It can be seen that the mean absolute approximation error of the Normal approximation increases as the fraction \(lowP\) of small probabilities increases. In contrast, the approximation error of the Poisson approximation slightly decreases. However, only for \(lowP>0.98\), the Poisson approximation begins to outperform the Normal approximation. Thus, if the dataset only contains a few probability values that are not small, then the Normal approximation outperforms the Poisson approximation.

While in the previous experiment, the approximation quality has been measured for individual itemsets, we now compare the effectivity of the model-based approaches for the complete Apriori-based algorithm.

(ii) MB vs.DP. Next, we compare the performance (in log scale) of the model-based approaches (MB) and the dynamic programming-based DP. First, we will compare the runtime of the three (MB)s to each other. The result is shown in Fig. 7. It can be seen that the approach using expected support, since it only has to perform a single value comparison (\(\mu _I\ge minsup\)), is faster than the other model-based approaches by a factor of about two. The normal and the Poisson approximation take about the same time to compute. While in our Java experiments (shown here), the Poisson approximation slightly outperforms the normal approximation, our experiments in \(R\) (not depicted here) show the opposite situation. In summary, we can say that Poisson and normal approximation take about the same time to evaluate, except for some possibly implementation specific differences.

In the following runtime experiments, we will for simplicity only show one graph for the model-based (MB) approaches, which corresponds to the runtime of the normal and Poisson approximation. For the runtime of the expected approach, simply divide the result by two due to the observations made in Fig. 7.

Figure 8a. Observe that MB is about two orders of magnitude faster than DP, over a wide range of minsup. This is because MB does not compute exact frequentness probabilities as DP does; instead, MB only computes the \(\mu _I\) values, which can be obtained faster. We also notice that the running times of both algorithms decrease with a higher minsup. This is explained by Figure 8b, which shows that the number of PFIs generated by the two algorithms, \(|PFI|\), decreases as minsup increases. Thus, the time required to compute the frequentness probabilities of these itemsets decreases. We can also see that \(|PFI|\) is almost the same for the two algorithms, reflecting that the results returned by MB closely resemble those of DP.

Figure 8c examines the performance of MB and DP (in log scale) over different minprob values. Their execution times drop by about 6 % when minprob changes from 0.1 to 0.9. We see that MB is faster than DP. For instance, at \(minprob=0.5\), MB needs 0.3 s, while DP requires 118 s, delivering an almost 400-fold performance improvement.

(iii) MB vs. MBP. We then examine the benefit of using the improved PFI testing method (MBP) over the basic one (MB). Figure 9(a) shows that MBP runs faster than MB over different minsup values. For instance, when \(minsup = 0.5\), MBP has about 25 % of performance improvement. Moreover, as minsup increases, the performance gap increases. This can be explained by Fig. 9b, which presents the fraction of the database scanned by the two algorithms. When minsup increases, MBP examines a smaller fraction of the database. For instance, at \({ minsup}=0.5\), MBP scans about 80 % of the database. This reduces the I/O cost and the effort for interpreting the retrieved tuples. Thus, MBP performs better than MB.

(iv) Scalability. Figure 10a examines the scalability of the three algorithms. Both MB and MBP scale well with \(n\). The performance gap between MB/MBP and DP also increases with \(n\). At \(n = 20k\), MB and DP need 0.62 and 657.7 s, respectively; at \(n = 100k\), MB finishes in 3.1 s while DP spends 10 h. Hence, the scalability of our approaches is clearly better than that of DP.

(v) Existential probability. We also examine the effect of using different distributions to characterize an attribute’s probability, in Fig. 10b. We use Un to denote a uniform distribution and \(G_i\) (\(i=1,\ldots ,4\)) to represent a Gaussian distribution. The details of these distributions are shown in Table 8.

We observe that MB and MBP perform better than DP over different distributions. All algorithms run comparatively slower on \(G_1\). This is because \(G_1\) has high mean (0.8) and low standard deviation (0.125), which generates high existential probability values. As a result, many candidates and PFIs are generated. Also note that \(G_3\) and \(Un\), which have the same mean and standard deviation, yield similar performance. Lastly, we found that the precision and the recall of MB and MBP over these distributions are the same and are close to 1. Hence, the PFIs retrieved by our methods closely resemble those returned by DP.

We now compare the first top-\(k\) solution proposed in [39] (called top-k) and our enhanced algorithm (called E-top-k).

(vi) Accuracy. We measure the recall and precision of E-top-k relative to that of top-k, by using formulas similar to Eqs. 21 and 22. Table 9 shows the recall and the precision of E-top-k for a wide range of \(n\), \(k\) and \(minsup\) values. We observe that the recall values are equal to the precision values. This is because number of PFIs returned by top-k and E-top-k are the same. As We can also see the recall and precision values are always higher than 98 %. Hence, E-top-k can accurately return top-\(k\) PFIs.

(vii) Performance. Figure 11a–c compare the two algorithms under different values of \(n\), \(k\), and \(minsup\). Similar to the case of threshold-based PFIs, our solution runs much faster than top-k. When \(n=10k\), for example, E-top-k finishes in only 0.2 s, giving an almost 20,000-fold improvement over that of top-k, which completes in 1.1 hours. In Fig. 11a, we see that the runtime of top-k increases faster than that of E-top-k with a bigger database. In Fig. 11b, observe that the E-top-k is about four orders of magnitude faster than top-k.In Fig. 11c, with the increase in \(minsup\), top-k needs more time, but the runtime of E-top-k only slightly increases. This is because (1) fewer candidates are produced by our generation step and (2) the testing step is significantly improved by using our model-based methods.

We have also performed experiments on the tuple uncertainty model and the synthetic dataset. Since they are similar to the results presented above, we only describe the most representative ones. For the accuracy aspect, the recall and precision values of approximate results on these datasets are still higher than 98 %. Thus, our approaches can return accurate results.

Tuple uncertainty. We compare the performance of DP, TODIS, MB, and MBP in Figure 12(a). TODIS [38] is proposed to retrieve threshold-based PFIs from tuple-uncertain databases. It shows that both MB and MBP perform much better than DP and TODIS, under different minsup values. For example, when \(minsup = 0.3\), MB needs 1.6 s, but DP and TODIS complete in 581 and 81 s, respectively. In Fig. 12b, we also see that E-top-k consistently outperforms top-k by about two orders of magnitude. This means that our approach, which avoids computing frequentness probabilities, also works well for the tuple uncertainty model.

Synthetic dataset. Finally, we run the experiments on the synthetic dataset. Figure 13a compares the performance of MB, MBP, and DP, for attribute uncertainty model. We found that MB and MBP still outperform DP. Figure 13b tests the performance of top-k and E-top-k, for tuple uncertainty model. Again, E-top-k runs faster than top-k, by around two orders of magnitude. Thus, our approach also works well for this dataset.