# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 5 Sampling-Based Algorithm for Frequent Sequential Pattern Mining  
We now present a sampling algorithm for frequent sequential pattern mining. The aim of this algorithm is to reduce the amount of data to consider to mine the frequent sequential patterns, in order to speed up the extraction of the sequential patterns and to reduce the amount of memory required. We define a _random sample_ as a bag of \(m\) transactions taken uniformly and independently at random,with replacement, from \(\mathcal{D}\). Obtaining the exact set \(FSP(\mathcal{D},\theta)\) from a random sample is not possible, thus we focus on obtaining an \(\varepsilon\)-approximation with probability at least \(1-\delta\), where \(\delta\in(0,1)\) is a _confidence_ parameter, whose value, with \(\varepsilon\), is provided in input by the user. Intuitively, if a random sample is sufficiently large, then the set of frequent sequential patterns extracted from the random sample well approximates the set \(FSP(\mathcal{D},\theta)\). The challenge is to find the number of transactions that are necessary to obtain the desired \(\varepsilon\)-approximation. To compute such sample size, our approach uses the VC-dimension of sequential patterns (see Section 3.1). **Theorem 8**. : _Given \(\varepsilon,\delta\in(0,1)\), let \(S\) be a random sample of size \(m\) sequential transactions taken independently at random with replacement from the dataset \(\mathcal{D}\) such that \(\sup_{p\in\mathbb{U}}|f_{\mathcal{D}}(p)-f_{S}(p)|\leq\varepsilon/2\) with probability at least \(1-\delta\). Then, given \(\theta\in(0,1]\), the set \(FSP(S,\theta-\varepsilon/2)\) is an \(\varepsilon\)-approximation to \(FSP(\mathcal{D},\theta)\) with probability at least \(1-\delta\)._  
Proof. : Suppose that \(\sup_{p\in\mathbb{U}}|f_{\mathcal{D}}(p)-f_{S}(p)|\leq\varepsilon/2\). In such a scenario, we have that for all sequential patterns \(p\in\mathcal{D}\), it results \(f_{S}(p)\in[f_{\mathcal{D}}(p)-\varepsilon/2,f_{\mathcal{D}}(p)+\varepsilon/2]\). This also holds for the sequential patterns in \(\mathcal{C}=FSP(S,\theta-\varepsilon/2)\). Therefore, the set \(\mathcal{C}\) satisfies Property 3 from Definition 1. It also means that for all \(p\in FSP(\mathcal{D},\theta)\), \(f_{S}(p)\geq\theta-\varepsilon/2\), so such \(p\in\mathcal{C}\) and \(\mathcal{C}\) also satisfies Property 1. Now, let \(p^{*}\) be a sequential pattern such that \(f_{\mathcal{D}}(p^{*})<\theta-\varepsilon\). Then, \(f_{S}(p^{*})<\theta-\varepsilon/2\), that is \(p^{*}\
otin\mathcal{C}\), which allows us to conclude that \(\mathcal{C}\) also has Property 2 from Definition 1. Since we know that \(\sup_{p\in\mathbb{U}}|f_{\mathcal{D}}(p)-f_{S}(p)|\leq\varepsilon/2\) with probability at least \(1-\delta\), then the set \(\mathcal{C}\) is an \(\varepsilon\)-approximation to \(FSP(\mathcal{D},\theta)\) with probability at least \(1-\delta\), which concludes the proof. Theorem 8 provides a simple sampling-based algorithm to obtain an \(\varepsilon\)-approximation to \(FSP(\mathcal{D},\theta)\) with probability \(\geq 1-\delta\): take a random sample of \(m\) transactions from \(\mathcal{D}\) such that the maximum deviation is bounded by \(\varepsilon/2\), that is, \(\sup_{p\in\mathbb{U}}|f_{\mathcal{D}}(p)-f_{S}(p)|\leq\varepsilon/2\); report in output the set \(FSP(S,\theta-\varepsilon/2)\). As illustrated in Section 3.1, such sample size can be computed using an efficient upper bound on the VC-dimension, given in input the desired upper bound on the maximum deviation \(\varepsilon/2\) (see Algorithm 2). Note that such sample size can not be computed with the Rademacher complexity, since the sample size appears in both terms of the right-hand side of Equation (23). Thus, it is not possible to fix the value of the bound on the maximum deviation to compute the sample size that provides such guarantees. Algorithm 6 shows the pseudo-code of the sampling algorithm. We now provide the respective theorem to find a FPF \(\varepsilon\)-approximation. **Theorem 9**.