# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 7 Experimental Evaluation
### Sampling Algorithm Results
Similar results between our sampling algorithm and the mining of the whole dataset have also been obtained with KOSARAK and MSNBC. As expected, for all the datasets, the execution time of the sampling algorithm to obtain an \(\varepsilon\)-approximation is larger than the execution time of the sampling algorithm to obtain a FPF \(\varepsilon\)-approximation, since the minimum frequency threshold used in the first case is lower, resulting in a higher number of extracted sequential patterns. \begin{table}
\begin{tabular}{l r r r r r} \hline \hline
**Dataset \(\mathcal{D}_{L}\)** & \(\theta\) & \(|S|/|\mathcal{D}_{L}|\) & \begin{tabular}{c} **Max\_Abs\_Err** \\ **(\(\times 10^{-4}\))** \\ \end{tabular} & \begin{tabular}{c} **Avg\_Abs\_Err** \\ **(\(\times 10^{-4}\))** \\ \end{tabular} & \
\begin{tabular}{c} **\(\varepsilon\)-approx** \\ **(\%)** \\ \end{tabular} &
\begin{tabular}{c} **FFF \(\varepsilon\)-approx** \\ **(\%)** \\ \end{tabular} \\ \hline BIBLE & 0.1 & 0.24 & 9.33 & 7.47 & 100 & 100 \\ BMS1 & 0.012 & 0.17 & 5.45 & 4.70 & 100 & 100 \\ BMS2 & 0.012 & 0.16 & 4.08 & 3.14 & 100 & 100 \\ FIFA & 0.25 & 0.50 & 8.68 & 7.07 & 100 & 100 \\ KOSARAK & 0.02 & 0.52 & 7.18 & 4.95 & 100 & 100 \\ LEVIATHAN & 0.15 & 0.30 & 9.19 & 7.84 & 100 & 100 \\ MSNBC & 0.02 & 0.37 & 4.33 & 3.63 & 100 & 100 \\ SIGN & 0.4 & 0.20 & 14.14 & 12.19 & 100 & 100 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Sampling algorithms results. For each enlarged dataset \(\mathcal{D}_{L}\), we report \(\theta\), the ratio \(|S|/|\mathcal{D}_{L}|\) between the sample size \(|S|\) and the size of the enlarged dataset \(|\mathcal{D}_{L}|\), \(\text{Max\_Abs\_Err}\), the maximum \(\max_{p\in C_{i}}|f_{D}(p)-f_{S_{i}}(p)|\), and \(\text{Avg\_Abs\_Err}\), the average \(\max_{p\in C_{i}}|f_{D}(p)-f_{S_{i}}(p)|\), over the 5 samples \(S_{i}\) and with \(C_{i}\) the set of frequent sequential patterns extracted from \(S_{i}\), the percentage of \(\varepsilon\)-approximations obtained over the 5 samples and the percentage of FPF \(\varepsilon\)-approximations obtained over the 5 samples. We now discuss some of the patterns extracted from the MSNBC dataset, for which richer information regarding the data is available. In particular, in MSNBC each transaction contains the sequence of click-stream data generated by a single view on the MSNBC website by a user, and each item represents the category of a visited webpage, such \"frontpage\", \"news\", \"sports\", and so forth. The two most frequent sequential patterns extracted in the enlarged datasets with a classic FSP algorithm are single categories, that is, sequential patterns of item-length 1: \(\langle\{frontpage\}\rangle\) is the most frequent while \(\langle\{on-air\}\rangle\) is the second one. They are also the two most frequent sequential patterns extracted in all the five samples using our sampling algorithms. The most frequent sequential patterns with item-length greater than one are the sequential patterns \(\langle\{frontpage\},\{frontpage\}\rangle\) and \(\langle\{frontpage\},\{frontpage\},\{frontpage\}\rangle\). For \(\langle\{frontpage\},\{frontpage\},75\%\) of the transactions in which it appears there is at least an instance of such pattern where the two items are consecutive. This means that users visited two consecutive webpages of the same category, \"frontpage\", or that they refreshed the same page twice, while in the 25% of the transactions in which it appears users visited webpages of other categories between the two \"frontpage\" webpages. Instead, for \(\langle\{frontpage\},\{frontpage\},\{frontpage\}\rangle\) the percentage of transactions in which the three items are consecutive is 59%. We also observed similar results with other categories: sequential patterns that are sequences of the same item, and so of the same category, have higher frequency. This fact highlights that users usually visit more frequently pages of the same category or that they refresh multiple times the same pages.