# Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
## 7 Experimental Evaluation
### True Frequent Sequential Patterns Results
\begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multicolumn{3}{c}{\(\mu_{VC}/2\)} & \multicolumn{3}{c}{\(\mu_{R}^{b}/2\)} & \multicolumn{3}{c}{\(\mu_{R}^{a}/2\)} \\  & **avg** & **max** & **std** & **avg** & **max** & **std** & **avg** & **max** & **std** \\  & **avg** & **max** & **(\(\times 10^{-3}\))** & **avg** & **max** & **(\(\times 10^{-3}\))** & **avg** & **max** & **(\(\times 10^{-3}\))** \\ \hline BIBLE & 0.0339 & 0.0340 & 0.1 & 0.0747 & 0.0748 & 0.1 & 0.0207 & 0.0223 & 1.5 \\ BMS1 & 0.0194 & 0.0197 & 0.3 & 0.0287 & 0.0294 & 0.6 & 0.0136 & 0.0153 & 1.0 \\ BMS2 & 0.0194 & 0.0196 & 0.1 & 0.0202 & 0.0207 & 0.5 & 0.0107 & 0.0115 & 0.5 \\ KOSARAK & 0.0334 & 0.0335 & 0.1 & 0.0957 & 0.0972 & 1.5 & 0.0145 & 0.0164 & 1.5 \\ LEVIATHAN & 0.0847 & 0.0850 & 0.3 & 0.1878 & 0.1904 & 1.6 & 0.0569 & 0.0636 & 5.5 \\ MSNBC & 0.0089 & 0.0090 & 0.1 & 0.0252 & 0.0257 & 0.9 & 0.0035 & 0.0041 & 0.4 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison of the upper bound \(\mu/2\) to the maximum deviation achieved respectively by ComputeMaxDevVC, ComputeMaxDevRadeBound, and ComputeMaxDevRadeApprox for each dataset. We show averages _avg_, maximum values _max_, and standard deviations _std_ for each dataset and method over the 4 pseudo-artificial datasets. We now we briefly analyze the sequential patterns extracted from the MSNBC dataset using our TFSP algorithms. Since we considered the FSP extracted from the whole dataset as ground truth, that is, as TFSP, the considerations reported for the most frequent sequential patterns extracted from the whole dataset and from the samples (see previous section) are still valid for the true frequent sequential patterns that have higher frequency. Using \(\theta=0.02\), as shown in Tables 5 and 6, we find 97 true frequent sequential patterns. In the four pseudo-artificial datasets we extracted on average \(\approx\)126 and \(\approx\)230 sequential patterns with guarantees on the false negatives, using respectively the approximation on the Rademacher complexity and the VC-dimension. With the algorithms with guarantees on the false positives, we mined \(\approx\)74 and \(\approx\)54 sequential patterns, respectively. \begin{table}
\begin{tabular}{l r r r r r r} \hline \hline
**Ground Truth** & \(\theta\) & \(|\)**TFSP\(|\)** & \begin{tabular}{c} **Times FNs in** \\ **FSP(\(\mathcal{D}_{i}\), \(\hat{\theta}_{VC}\))** \\ \end{tabular} & \begin{tabular}{c} **\(|\)**TFSP\(|\)/** \\ **FSP(\(\mathcal{D}_{i}\), \(\hat{\theta}_{VC}\))** \\ \end{tabular} & \begin{tabular}{c} **\(|\)**TFSP\(|\)/** \\ **FSP(\(\mathcal{D}_{i}\), \(\hat{\theta}_{R}\))** \\ \end{tabular} & \
\begin{tabular}{c} **\(|\)**TFSP\(|\)/** \\ **FSP(\(\mathcal{D}_{i}\), \(\hat{\theta}_{R}\))** \\ \end{tabular} &
\begin{tabular}{c} **\(|\)**TFSP\(|\)/** \\ **FSP(\(\mathcal{D}_{i}\), \(\hat{\theta}_{R}\))** \\ \end{tabular} \\ \hline BIBLE & 0.1 & 174 & 0 \% & 0.42 & 0 \% & 0.63 \\  & 0.05 & 774 & 0 \% & 0.09 & 0 \% & 0.33 \\ BMS1 & 0.025 & 13 & 0 \% & 0.07 & 0 \% & 0.21 \\  & 0.0025 & 17 & 0 \% & 0.04 & 0 \% & 0.19 \\ BMS2 & 0.025 & 10 & 0 \% & 0.03 & 0 \% & 0.32 \\  & 0.0025 & 11 & 0 \% & 0.01 & 0 \% & 0.19 \\ KOSARAK & 0.06 & 23 & 0 \% & 0.30 & 0 \% & 0.64 \\  & 0.04 & 41 & 0 \% & 0.04 & 0 \% & 0.49 \\  & 0.15 & 225 & 0 \% & 0.12 & 0 \% & 0.30 \\  & 0.1 & 651 & 0 \% & 0.01 & 0 \% & 0.13 \\  & 0.02 & 97 & 0 \% & 0.42 & 0 \% & 0.77 \\  & 0.015 & 143 & 0 \% & 0.24 & 0 \% & 0.65 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Results of our algorithm for the TFSPs with guarantees on the false negatives in 4 pseudo-artificial datasets \(\mathcal{D}_{i}\) for each ground truth.