## 3 Problem Definition
Formally:  
\[p_{0}(s,d)=\frac{||i_{x}\in d:i_{x}\sqsubset s.target||}{||i_{x}\in d:i_{x}||} \tag{8}\]  
The function \(tn\) (true negatives) is defined as the number of instances \(i_{x}\) from the dataset \(d\) that are covered by neither the subgroup description _s.description_ nor the subgroup target _s.target_. Formally:  
\[tn(s,d)=||i_{x}\in d:i_{x}\sqsubset s.description\wedge i_{x}\sqsubset s.target|| \tag{9}\]  
The function \(fn\) (false negatives) is defined as the number of instances \(i_{x}\) from the dataset \(d\) that are not covered by the subgroup description _s.description_, but are covered by the subgroup target _s.target_. Formally:  
\[fn(s,d)=||i_{x}\in d:i_{x}\sqsubset s.description\wedge i_{x}\sqsubset s.target|| \tag{10}\]  
Table 1 shows the confusion matrix of a subgroup \(s\) with respect to a dataset \(d\). This matrix summarizes the functions describe above. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & & \multicolumn{3}{c}{_s.target_} \\ \hline \multirow{3}{*}{_s.description_} & \multicolumn{2}{c}{**True**} & \multicolumn{2}{c}{**False**} \\ \cline{2-5}  & **True** & tp & fp & n = tp + fp \\ \cline{2-5}  & **False** & fn = TP - tp & tn = FP - fp & TP + FP - tp - fp \\ \hline \multirow{3}{*}{_s.description_} & \multicolumn{2}{c}{TP = tp + fn} & FP = fp + tn & N = TP + FP \\ \cline{2-5}  & & & & \\ \cline{1-1} \cline{2-5}  & & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Confusion matrix of a subgroup \(s\) with respect to a dataset \(d\). With regard to the functions defined previously, the following equivalences can be highlighted:  
\[p(s,d)=\frac{tp(s,d)}{tp(s,d)+fp(s,d)}=\frac{tp(s,d)}{n(s,d)} \tag{11}\]  
\[p_{0}(s,d)=\frac{TP(s,d)}{TP(s,d)+FP(s,d)}=\frac{TP(s,d)}{N(s,d)} \tag{12}\]  
Having described the four functions with which to compute quality measures, some popular quality measures for SD presented in the literature can be rewritten as follows:  
\[\textit{Sensitivity}=\frac{tp}{TP} \tag{13}\]  
\[\textit{Specificity}=\frac{FP-fp}{FP} \tag{14}\]  
\[\textit{Piatetsky Shapiro}=(tp+fp)\cdot(\frac{tp}{tp+fp}-\frac{TP}{TP+FP}) \tag{15}\]  
\[\textit{WRAcc}=\frac{tp+fp}{TP+FP}\cdot(\frac{tp}{tp+fp}-\frac{TP}{TP+FP}) \tag{16}\]  
The WRAcc quality measure is defined between \(-1\) and \(1\) (both included). Moreover, an optimistic estimate of this quality measure [9] can be rewritten as follows:  
\[\textit{WRAcc optimistic estimate}=\frac{tp^{2}}{tp+fp}\cdot(1-\frac{TP}{TP+ FP}) \tag{17}\]  
Note that, in this case, the parameters of the functions have not been shown for the sake of brevity and for reasons of space. It is essential to keep in mind from the beginning that, although only WRAcc quality measure and its optimistic estimate are used in this research, they are only an example and, therefore, all quality measures which have an optimistic estimate could be used. Finally, given a dataset \(d\), a quality measure \(q\) and a numeric value _quality_threshold_, the subgroup discovery problem consists of exploring the search space of \(d\) in order to enumerate the subgroups that have a quality measure value above the selected threshold. Formally  
\[\mathcal{R}=\{(s,q(s,d))|q(s,d)\geq quality\_threshold\} \tag{18}\]  
The search space of a problem (i.e., of a dataset \(d\)) can be visually illustrated as a lattice [24] (see Figure 1). According to this comparison, the first level of the search space of a problem contains all those subgroups \(s\) whose descriptions have a size of \(1\) (i.e., _|s_._description_| is equal to one), the second level of the search space of a problem contains all those subgroups \(s\) whose descriptions have a size of \(2\) (i.e., _|s_._description_| is equal to two) and, in general, the level \(n\) of the search space of a problem contains all those subgroups \(s\) whose descriptions have the size \(n\) (i.e., _|s_._description_| is equal to \(n\)).