## 4 Algorithm  
We propose a new and efficient Subgroup Discovery (SD) algorithm called VLSD (Vertical List Subgroup Discovery) that combines an equivalence class exploration strategy [24] and a pruning strategy based on optimistic estimate [9]. The implementation of this proposal is based on vertical list data structure, making it easily parallelizable [24]. The pruning based on optimistic estimate implies that, for all the nodes generated (i.e., subgroups), their optimistic estimate values are computed and compared with the threshold in order to discover whether they must be pruned (and it is, therefore, not necessary to explore their refinements), or whether their refinements (i.e., the next depth level) must also be explored. Our proposal is described in the VLSD function (Algorithm 1) that is accompanied by a function that generates all subgroups whose descriptions have size one (GENERATE_SUBGROUPS_S1 function, described in Algorithm 2) and by a function that explores the search space and computes pruning (SEARCH function, described in Algorithm 3). ```
0:\(d\) {dataset }, target {selector }, \(q\) {quality measure }, \(q\)_threshold {\(\mathbb{R}\) }, oe {optimistic estimate of \(q\)}, oe_threshold {\(\mathbb{R}\) }, sort_criterion_in_S1 {criterion }, sort_criterion_in_other_sizes {criterion }
0:\(\mathcal{F}\): list of subgroups. 1:\(\mathcal{F}:=<>\)
2:\(TP:=TP((<>,target),d)\) ; \(FP:=FP((<>,target),d)\)
3:\(\mathcal{S}1:=\) GENERATE_SUBGROUPS_S1(\(d,target,oe,oe\)_threshold, sort_criterion_in_S1,TP,FP)
4:for each subgroup \(s\in\mathcal{S}1\)do
5:\(q\_value:=q(tp(s,d),fp(s,d),TP,FP)\)
6:if\(q\_value\geq q\_threshold\)then
7:\(\mathcal{F}add(s)\)
8:endif
9:endfor
10:\(\mathcal{M}:=2\)-dimensional \(|\mathcal{S}1|\times|\mathcal{S}1|\) triangular matrix, initialized \(\mathcal{M}[i,j]=NULL\), in which \(\mathcal{M}[i,j]\) is a subgroup (\(i\) and \(j\) selectors acting as indices). Figure 1: Search space of a problem visually illustrated as a lattice. ```
11:for each\(s_{x},s_{y}\) in \(\mathcal{S}1=<s_{1},s_{2},\ldots,s_{n}>\), being \(x<y\)do
12:\(s_{xy}:=refine(s_{x},s_{y})\)
13:\(oe\_quality:=oe(tp(s_{xy},d),fp(s_{xy},d),TP,FP)\)
14:if\((tp(s_{xy},d)+fp(s_{xy},d)>0)\) AND \((oe\_quality\geq oe\_threshold)\)then
15:\(\mathcal{M}[\mathit{last}(s_{x}\_description)][\mathit{last}(s_{y}\_description)]:=s_{xy}\)
16:endif
17:endfor
18:if\(|\mathcal{S}1|\geq 2\)then
19:for\(i:=0\) to \((|\mathcal{S}1|-2)\)do
20:\(selector\_{i}:=\mathit{last}(\mathcal{S}1[i]\_description)\)
21:\(\mathcal{P}:=\mathcal{M}[selector\_i]\) { All subgroups whose descriptions have the size two and start with selector\_i}
22:\(\mathcal{P}:=\mathcal{P}.sort(sort\_criterion\_in\_other\_sizes)\)
23:for each subgroup \(s\in\mathcal{P}\)do
24:\(q\_value:=q(tp(s,d),fp(s,d),TP,FP)\)
25:if\(q\_value\geq q\_threshold\)then
26:\(\mathcal{F}\_add(s)\)
27:endif
28:endfor
29:\(\mathcal{F}\_add\_all(SEARCH(d,\mathcal{P},\mathcal{M},q,q\_threshold,oe,oe\_threshold, sort\_criterion\_in\_other\_sizes,TP,FP))\)
30:endfor
31:endif
32:return\(\mathcal{F}\)
```
**Algorithm 1**_Cont._
```
1:\(d\) { dataset }, \(target\) { selector }, \(oe\) { optimistic estimate }, \(oe\_threshold\) { \(\mathbb{R}\) }, \(sort\_criterion\_in\_S1\) { criterion }, \(TP\) { \(\mathbb{N}\) }, \(FP\) { \(\mathbb{N}\) }
2:\(\mathcal{S}1\): list of subgroups whose descriptions have the size one. 3:\(\mathcal{S}1:=<>\)
4:\(\mathcal{S}2:=\) scan \(d\) (except the target attribute) to generate the selector list. 5:for each selector \(e\in\mathcal{E}\)do
6:\(s:=(<e>,target)\)
7:\(oe\_quality:=oe(tp(s,d),fp(s,d),TP,FP)\)
8:if\(oe\_quality\geq oe\_threshold\)then
9:\(\mathcal{S}1\_add(s)\)
10:endif
11:endfor
12:\(\mathcal{S}1:=sort(\mathcal{S}1,sort\_criterion\_in\_S1)\)
13:return\(\mathcal{S}1\)
```
**Algorithm 2** GENERATE_SUBGROUPS_S1 function.