## 4 Algorithm
## Appendix A Extended Problem Definition

The fundamental concepts of the Subgroup Discovery (SD) technique are extended and detailed as follows:

**Definition A1** (Attribute _a_). : _An attribute \(a\) is a unique characteristic of an object, which has an associated value. An example of an attribute is a = age:30._

**Definition A2** (Domain of an attribute _a_). : _The domain of an attribute (denoted as \(\text{dom}(a)\)) is the set of all the unique values that said attribute can take. An attribute can be nominal or numeric, depending on its domain._

**Definition A3** (Instance _i_). : _An instance \(i\) is a tuple \(i=(a_{1},\ldots,a_{M})\) of attributes. Given the attributes \(a_{1}=\) age:25 and \(a_{2}=\) sex:woman, an example of an instance is \(i\) = (age:25, sex:woman)._

**Definition A4** (Dataset _d_). : _A dataset \(d\) is a tuple \(d=(i_{1},\ldots,i_{N})\) of instances. Given the instances \(i_{1}=\) (age:30, sex:man) and \(i_{2}=\) (age:25, sex:woman), an example of a dataset is \(d=\) ((age:30, sex:man), (age:25, sex:woman))._

The dataset space is denoted as \(\mathcal{D}\). All values from a dataset \(d\) can be indexed with two integers, \(x\) and \(y\). We use the notation \(v_{x,y}\) to indicate the value of the x-th instance \(i_{x}\) and of the y-th attribute \(a_{y}\) from a dataset \(d\). **Definition A5** (Selector _e_). : _Given an attribute \(a_{y}\) from a dataset \(d\), a binary operator \(\in\{=,\
eq,<,>,\leq,\geq\}\) and a value \(w\in\text{dom}(a_{y})\), a selector \(e\) is a 3-tuple of the form \((a_{y}\).characteristic, operator, \(w)\). Note that when an attribute \(a_{y}\) is nominal, only the \(=\) and \(\
eq\) operators are permitted._

Informally, a selector is a binary relation between an attribute from a dataset and a value in the domain of that attribute. This relation represents a property of a subset of instances from that dataset. It is essential to bear in mind that the first element of a selector refers only to the attribute name, i.e., the characteristic, and not to the complete attribute itself. **Definition A6** (Selector covering). : _Given an instance \(i_{x}\) and an attribute \(a_{y}\) from a dataset \(d\), and a selector \(e=(a_{y}.characteristic, operator,w\in\text{dom}(a_{y}))\), then \(i_{x}\) is covered by \(e\) (denoted as \(i_{x}\sqsubset e\)) if the binary expression \"\(v_{x,y}\) operator \(w\)\" holds true. Otherwise, we say that it is not covered by \(e\) (denoted as \(i_{x}\sqsubset e\))._

For example, given the instance \(i_{x}=\) (_age:25, sex:woman_) and the selectors \(e_{1}=\) (_age_, \(<\), 20) and \(e_{2}=\) (_sex_, \(=\), _woman_), it will be noted that \(i_{x}\sqsubset e_{1}\) and \(i_{x}\sqsubset e_{2}\). **Definition A7** (Pattern _p_). : _A pattern \(p\) is a list of selectors \(<e_{1},\ldots,e_{j}>\) in which all attributes of the selectors are different. Moreover, its size (denoted as \(|p|\)) is defined as the number of selectors that it contains._

In general, a pattern is interpreted as a list of selectors (i.e., as a conjunction) that represents a list of properties of a subset of instances from a dataset. **Definition A8** (Pattern covering). : _Given an instance \(i_{x}\) from a dataset \(d\) and a pattern \(p\), then \(i_{x}\) is covered by \(p\) (denoted as \(i_{x}\sqsubset p\)) if \(\forall e\in p,i_{x}\sqsubset e\). Otherwise, we say that it is not covered by \(p\) (denoted as \(i_{x}\sqsubset p\))._

**Definition A9** (Subgroup \(s\)). : _A subgroup \(s\) is a pair (pattern, selector) in which the pattern is denoted as \(s\).description and the selector is denoted as \(s\).target. Given the dataset \(d\) = ((fever.yes, sex:man, flu:yes), (fever:yes, sex:woman, flu:no)), an example of a subgroup is \(s=(<(fever,=,yes),(sex,=woman)>,(flu,=,yes))\)._

The subgroup space is denoted as \(\mathcal{S}\). **Definition A10** (Subgroup refinement \(s^{\prime}\)).