# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 7 Experimental Evaluation
### Sampling Algorithm Results  
In this section, we describe the results obtained with our sampling algorithm (Algorithm 6). As explained above, the typical scenario to apply sampling is that the dataset to mine is very large. Thus, we aim to reduce the size of such dataset, considering only a sample of it. In addition, from the sample, we aim to obtain a good approximation of the results that would have been obtained from the \begin{table}
\begin{tabular}{l r r r r} \hline \hline
**Dataset \(\mathcal{D}\)** & **Size \(|\mathcal{D}|\)** & \(|\mathcal{I}|\)** & **Avg. Item-Length** & **Max. Item-Length** \\ \hline BIBLE & 36,369 & 13,905 & 21.6 & 100 \\ BMS1 & 59,601 & 497 & 2.5 & 267 \\ BMS2 & 77,512 & 3340 & 4.6 & 161 \\ FIFA & 20,450 & 2990 & 36.2 & 100 \\ KOSARAK & 69,999 & 14,804 & 8.0 & 796 \\ LEVIATHAN & 5835 & 9025 & 33.8 & 100 \\ MSNBC & 989,818 & 17 & 4.8 & 14,795 \\ SIGN & 730 & 267 & 52.0 & 94 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Datasets characteristics. For each dataset \(\mathcal{D}\), we report the number \(|\mathcal{D}|\) of transactions, the total number \(|\mathcal{I}|\) of items, the average transaction item-length and the maximum transaction item-length. entire dataset. In all our experiments we fixed \(\varepsilon=0.01\) and \(\delta=0.1\). The steps of the evaluation are the following (Algorithm 6): given a dataset \(\mathcal{D}_{L}\) as input, we compute the sample size \(m\), using Algorithm 2, to obtain an \(\varepsilon=0.01\)-approximation (resp. FPF 0.01-approximation) with probability at least \(1-\delta=0.90\). Then, we extract a random sample \(S\) of \(m\) transactions from \(\mathcal{D}_{L}\) and we run the algorithm to mine the frequent sequential patterns on \(S\). Finally, we verify whether the set of frequent sequential patterns extracted from the sample is a 0.01-approximation (resp. FPS 0.01-approximation) to \(FSP(\mathcal{D}_{L},\theta)\). For each dataset \(\mathcal{D}_{L}\) we repeat the experiment 5 times, and then we compute the fraction of times the sets of frequent sequential patterns extracted from the samples have the properties described in Definition 1 (resp. Definition 2). Table 2 shows the results. We observe that the samples obtained from the datasets are about 2 to 5 times smaller than the whole datasets. Moreover, in all the runs for all the datasets, we obtain an \(\varepsilon\)-approximation (resp. FPF \(\varepsilon\)-approximation). Such results are even better than the theoretical guarantees, that ensure to obtain such approximations with probability at least 90%. We also reported \(\text{Max\_Abs\_Err}=\max_{S_{i},i\in[1,5]}\max_{p\in C_{i}}|f_{D}(p)-f_{S_{i}} (p)|\) and \(\text{Avg\_Abs\_Err}=\frac{1}{5}\sum_{S_{i},i\in[1,5]}\max_{p\in C_{i}}|f_{D}( p)-f_{S_{i}}(p)|\), where \(C_{i}\) is the set of frequent sequential patterns extracted from the sample \(S_{i}\), \(i=1,...,5\) (since we run each experiment 5 times, there are 5 samples). They represent the maximum and the average, over the 5 runs, of the maximum absolute difference between the frequency that the sequential patterns have in the entire dataset and that they have in the sample, over all the sequential patterns extracted from the sample. Again, the results obtained are better than the theoretical guarantees, that ensure a maximal absolute difference lower than \(\varepsilon/2=0.005\). Figure 3 shows the comparison between the average execution time of the sampling algorithm and the average execution time of the mining of the entire dataset, over the 5 runs. For all the datasets, the sampling algorithm requires less time than the mining of the whole dataset. For BMS1 and BMS2, the mining of the whole dataset is very fast since the number of frequent sequential patterns extracted from it is low. Thus, there is not a large difference between the execution time to mine the whole dataset and the execution time for the sampling algorithm, which is most due to the computation of the sample size.