## 3 Problem Definition
: _Given a subgroup \(s\), each of its refinements \(s^{\prime}\) (denoted as \(s<s^{\prime}\)) is a subgroup with the same target, \(s^{\prime}.\textit{target}=\textit{s.target}\), and with an extended description, \(s^{\prime}.\textit{description}=\textit{concat}(\textit{s.description}, \textit{<}e_{1},\ldots,e_{j}>)\)._  
**Definition 4** (Refine operator). : _Given two subgroups, \(s_{x}\) and \(s_{y}\), the \(\textit{ref}\)ine operator generates a refinement \(s_{x,y}\) of \(s_{x}\), extending its description with the non-common suffix of \(s_{y}\). For example, if \(s_{x}.\textit{description}=\textit{<}e_{1}\textit{>}\) and \(s_{y}.\textit{description}=\textit{<}e_{2}\textit{>}\), then \(s_{x,y}.\textit{description}=\textit{<}e_{1},\,e_{2}\textit{>}\); and if \(s_{x}.\textit{description}=\textit{<}e_{1},e_{2},e_{3}\textit{>}\) and \(s_{y}.\textit{description}=\textit{<}e_{1},e_{2},e_{4}\textit{>}\), then \(s_{x,y}.\textit{description}=\textit{<}e_{1},e_{2},e_{3},e_{4}\textit{>}\)._  
Given a subgroup \(s\) and a dataset \(d\), a quality measure \(q\) is a function that computes one numeric value according to that subgroup \(s\) and to certain characteristics from that dataset \(d\)[5]. Moreover, given a quality measure \(q\) and a dataset \(d\), an optimistic estimate \(oe\) of \(q\) is a quality measure that, for a certain subgroup, provides a quality upper bound for all its refinements [9]. Focusing on a specific subgroup \(s\) and on a specific dataset \(d\), different functions with which to compute quality measures can be defined. The function \(tp\) (true positives) is defined as the number of instances \(i_{x}\) from the dataset \(d\) that are covered by the subgroup description _s.description_ and by the subgroup target _s.target_. Formally:  
\[tp(s,d)=|\{i_{x}\in d:i_{x}\sqsubset s.\textit{description}\wedge i_{x}\sqsubset s.\textit{target}\}| \tag{1}\]  
The function \(fp\) (false positives) is defined as the number of instances \(i_{x}\) from the dataset \(d\) that are covered by the subgroup description _s.description_, but not by the subgroup target _s.target_. Formally:  
\[fp(s,d)=|\{i_{x}\in d:i_{x}\sqsubset s.\textit{description}\wedge i_{x}\sqsubset s.\textit{target}\}| \tag{2}\]  
The function \(TP\) (true population) is defined as the number of instances \(i_{x}\) from the dataset \(d\) that are covered by the subgroup target _s.target_. Formally:  
\[TP(s,d)=|\{i_{x}\in d:i_{x}\sqsubset s.\textit{target}\}| \tag{3}\]The function \(FP\) (false population) is defined as the number of instances \(i_{x}\) from the dataset \(d\) that are not covered by the subgroup target _s.target_. Formally:  
\[FP(s,d)=||i_{x}\in d:i_{x}\
ot\subseteq s.target|| \tag{4}\]  
A quality measure \(q\) can, therefore, be redefined using the previous four functions, given a subgroup \(s\) and a dataset \(d\), a quality measure \(q\) is a function that computes one numeric value according to the functions \(tp\), \(fp\), \(TP\), and \(FP\). They are sufficiently expressive to compute any quality measure. However, the following are also used in the literature. The function \(n\) is defined as the number of instances \(i_{x}\) from a dataset \(d\) that are covered by the subgroup description _s.description_. Formally:  
\[n(s,d)=||i_{x}\in d:i_{x}\sqsubset s.description|| \tag{5}\]  
The function \(N\) is defined as the number of instances \(i_{x}\) from the dataset \(d\). Formally:  
\[N(s,d)=||i_{x}\in d:i_{x}|| \tag{6}\]  
The function \(p\) is defined as the distribution of the subgroup target _s.target_ with respect to the instances \(i_{x}\) from a dataset \(d\) covered by the subgroup description _s.description_. Formally:  
\[p(s,d)=\frac{||i_{x}\in d:i_{x}\sqsubset s.description\wedge i_{x}\sqsubset s.target||}{||i_{x}\in d:i_{x}\sqsubset s.description||} \tag{7}\]  
The function \(p_{0}\) is defined as the distribution of the subgroup target _s.target_ with respect to all instances \(i_{x}\) from a dataset \(d\).