# A Random PRIM Based Algorithm for Interpretable Classification and Advanced Subgroup Discovery
## 2 Related Works
### The Patient Rule-Induction Method  
#### 2.1.1 Overview of PRIM  
Introduced by [PERSON] and [PERSON] in 1999 [PERSON] and [PERSON] (1999), the patient rule-induction method is an algorithm used for identifying and interpreting patterns in data, relying on the procedure of bump hunting. PRIM is a flexible and interpretable method that aims to uncover regions in the feature space where the response variable is significantly different from the overall mean or median. PRIM is particularly useful for identifying segments or subgroups within data that exhibit particular characteristics or behaviors. It is often applied in various domains such as medicine, finance, and marketing to find patterns that could help with decision-making and understanding of the data. Therefore, PRIM is considered as a subgroup-discovery method, since it contributes to pattern discovery in datasets. This method relies on two main steps: the top-down peeling and the bottom-up pasting. In PRIM, the rules are shaped as rectangles, and hence, they are named boxes. Figure 1 shows the construction of the first box containing the red data. As observed, the construction is performed iteratively, and the refinement at each iteration does not peel a lot of data; thus the name _patient_ given to the algorithm. This procedure ensures that no area of the data is missed.  
To better understand the search in the input space according to the type of variables, numeric or categorical, here is a more formal statement of the problem:  
Let p be the number of the input variables denoted by x\({}_{1}\), x\({}_{2}\ldots\), x\({}_{\text{p}}\) and y be a target variable in the same dataset. If y is a multiclass variable, then the problem has to be reformulated as binary subproblems. Let S\({}_{\text{j}}\) denote the set of possible values of x\({}_{\text{j}}\) (j = 1, \(\ldots\), p). The input space is then:  
\[\text{S}=\text{S}_{1}\;\text{x}\;\text{S}_{2}\;\text{x}\ldots\ldots\;\text{x} \;\text{S}_{\text{p}} \tag{1}\]  
The objective is to find subregions R \(\subset\) S for which:  
\[\overline{y}_{R}\;\gg\;\overline{y} \tag{2}\]  
where \(\overline{y}\) is the global mean of y and \(\overline{y}_{R}\) the mean of y in R.  
Let s\({}_{\text{i}}\subset\) S\({}_{\text{j}}\), we define a box by:  
\[\text{B}=\text{s}_{1}\;\text{x}\;\text{s}_{2}\;\text{x}\ldots\ldots\;\text{x} \;\text{s}_{\text{p}} \tag{3}\]  
where x \(\in\) B \(\equiv\;\cap_{j=1}^{p}(\text{x}_{\text{j}}\in\text{s}_{\text{j}})\). When s\({}_{\text{i}}=\) S\({}_{\text{j}}\), we leave x\({}_{\text{i}}\) out of the box definition since it may take any value in its domain. Figure 2 shows an example of a box defined on two numeric  
Figure 1: Illustration of the top-down peeling phase to find one box.  
variables, where \(x\in B\equiv x_{1}\in[a,b]\cap x_{2}\in[c,d]\). Figure 3 shows the definition of a box if the variables are categorical, where \(x\in B\equiv x_{1}\in[a,b]\cap x_{2}\in[c,d]\). A box can also be defined by numeric and categorical variables at the same time.  
Following top-down peeling, we are left with a series of boxes, each of which was created by peeling a portion of its predecessor. We only consider the next step at a time while conducting our searches, which is to select the peel that leads to the ideal sub-box. In other words, box boundaries are established without taking into account potential peels. Thus, redrawing the final box's boundaries can occasionally make it better. Using bottom-up pasting, we recursively enlarge the last box until the next paste causes the value of \(\overline{y}\) in the box to decrease.  
PRIM is known as a hill-climbing algorithm because, at each search step, the single sub-box that improves the target mean the most is peeled off. The peeling process comes to an end when the current box's support falls below the user-specified minimum support value of \(\beta_{0}\) fixed by the user.