Optimal Pattern Detection Tree for Symbolic Rule-Based Classification
Authors: Young-Chae Hong
Yangho Chen
Venue: Accepted by TMLR ()

Abstract: Pattern discovery in data plays a crucial role across diverse domains, including healthcare, risk assessment, and machinery maintenance. In contrast to black-box deep learning models, symbolic rule discovery emerges as a key data mining task, generating human-interpretable rules that offer both transparency and intuitive explainability. This paper introduces the Optimal Pattern Detection Tree (OPDT), a rule-based machine learning model based on novel mixed-integer programming to discover a single optimal pattern in data through binary classification. To incorporate prior knowledge and compliance requirements, we further introduce the Branching Structure Constraints (BSC) framework, which enables decision makers to encode domain knowledge and constraints directly into the model. This optimization-based approach discovers a hidden underlying pattern in datasets, when it exists, by identifying an optimal rule that maximizes coverage while minimizing the false positive rate due to misclassification. Our computational experiments show that OPDT discovers a pattern with optimality guarantees on moderately sized datasets within reasonable runtime.

Published in Transactions on Machine Learning Research (04/2026)
Optimal Pattern Detection Tree for Symbolic Rule-Based Classification
Young-Chae Hong
hongych@amazon
Amozon Seatile, USA
Yangho Chen
yanghoc Cawazon.cccooooo com
Amazon Seattle, USA
Reviewed on OpenReview: https: // openreview. net/ fort/m id= /J6
Abstract
Pattern discovery in data plays crucial role across diverse domains, including healtheare, risk assessment, and machinery maintenance In contrast to black-box deep learning models, symbolic rule discovery emerges key data mining task, generating human-interpretabl rules that offer both transparency and intuitive explainability. This paper introduces the Optimal Pattern Detection Tree (OPDT), a rule-based machine learning model based on novel mixed-integer programming to discover single optimal pattern data through binary classification. To incorporate prior knowledge and compliance requirements, we further introduce the Branching Structure Constraints (BSC) framework, which enables decision makers to encode domain knowledge and constraints directly into the model. This optimization-based approach discovers a hidden underlying pattern in datasets, when it exists, by identifying an optimal rule that maximizes coverage while minimizing the false positive rate due to misclassification. Our computational experiments show that OPDT discovers a pattern with optimality guarantees on moderately sized datasets within reasonable runtime.
1 Introduction
Data mining is the process of discovering and extracting hidden patterns from datasets to gain valuable insights and support decision-making. In particular, symbolic rule discovery is an important data mining lask that generates human-inten iimman-nteerreetbble rules in a natural and intuitive manner. However, recent developments in artificial intelligence (AI) and machine learning (ML) have driven attention toward black-box models, particularly deep learning approaches. This trend has led, in turn, to growing demand for developing algorithms that inherently learn interpretable white-box models, especially in high-stakes domains such as healthcare, personalized medicine, criminal justice, and financial risk assessment, where decisions can significantly impact human lives (Rudin) 2019 Rudin et al.) 2022). The exponential growth in healthcare data collection, driven by advanced monitoring technologies and digital health systems, has resulted a growing volume of biological and medical data at unprocedented speed and scale (Luo et al. 2016). While the tremendous amounts of data collected from electronic health records monitoring devices can be utilized for more effective and enhanced clinical decision making (Rea et al. 2012), it poses significant challenges in efficiently analyzing and extracting useful information and actionable insights from such overwhelming volumnes of data (Najarian et al. 2013
Over the last decade, various pattern recognition techniques have been developed for medical decision support systems to help clinicians effectively utilize the overwhelming amount of healthcare data. These techniques are applied biomedical data. for automated clinical diagnosis or therapeutic support, integrating data- driven knowledge and patient-specifie information to enhance cost-effective healthcare delivery (Moja et al.

---

Published in Transactions on Machine Learning Research (04/2026)
2014p. The development of novel pattern recognition methods and algorithms with high performance, in terms of accuracy and time complexity, improves healthcare delivery by allowing clinicians to make better- informed and timely decision (Asgari et al. 2019). To take reliable actions in high-stakes domains, the patterns extracted from data must be understood by human domain experts, unlike the opaque solutions provided by black-box ML approaches (Rudin 2019). TI domain experts do not fully comprehend the reasoning behind these patterns, there is a risk of making misinformed or potentially harmful decisions life-threatening situations. Therefore, developing human-readable rules is crucial for addressing emerging challenges in critical decision-making processes and ensuring accountability, transparency, and trust in automated systems.
Rule-based machine learning (RBML) models offer a promising solution by combining the interpretability of traditional rule-based systems with the automated learning capabilities of ML approaches. Unlike conventional black-box MI. models, RBML generates explicit decision rules that can be readily understood and validated by domain experts. Furthermore, for high-risk tasks requiring accountability, not only is interpretability crucial, but. models must. also comply with domain expert-specified constraints to be trustworthy (Nanfack et al.) (022).. For example, learned patterns may not make sense from a medical or clinical perspective, as algorithms typically consider only information extracted from medical datasets without incorporating domain knowledge (López-Vallverdúi Vallverdú et al. 2007). Therefore, ML models can become more trustworthy and reliable if they incorporate additional domain knowledge in the form of constraints. However, existing RBML methods are designed to extract a ruleset (i.e., a collection of multiple rules) rather than a single optimal pattern in data. In many real-world scenarios, such as an epidemic outbreak, credit fraud, or intrusion detection, positive samples originate from single underlying cause, and single high- precision rule is both sufficient and more actionable than complex ruleset. To the best of our knowledge, prior method has conducted research on extracting a single optimal pattern.
This paper proposes a novel algorithm to extract a single rule through binary classification that adheres to user-defined structural constraints, ensuring high interpretability while incorporating prior domain knowledge. We develop the Optimal Pattern Delection Tree (OPDT) based on optimal decision trees with branching structure constraints that control: 1) the tree's topology through split decisions, and 2) the feature group assignments for each branch node. This optimization-baade rule extracting approach discovers a hidden underlying pattern in datasets, when it exists, by identifying optimal rule that maximizes coverage while minimizing the false positive rate due to misclassification The remainder of the paper is structured as follows. In Section 2, we discuss the related work regarding the interpretable RBML and optimal decision tree (ODT). In Section 3, we present our proposed approach, OPDT to extract an optimal pattern from a dataset. In Section 4, we demonst rate the performance of the OPDT over different real-world datasets from the UCT repository and compare it with other RBML, methods.
2 Related Literature
2.1 Rule-Based Machine Learning
Among advanced AT and MI. technologies, the ability to extract valuable insights from complex datasets has become crucial for various fields, including healthcare, criminal justice, and financial risk assessment. However, the lack of interpretability in ML models can potentially lead to adverse or even life-threatening consequences (Ahmad et al., 2018). There is a growing demand for interpretable ML that allows end-users to understand the logic and reasoning behind predictions, especially in domains such as healthcare and criminal justice systems. This demand for improved interpretability has also increased to mitigate the risk of making unjustifiable decisions. In particular, studies in domains like healthcare and criminal justice have revealed that ML systems can systematically exhibit unfair biases (Burrell 2016). Thus, interpretability is needed to ensure such systems are free from bias (Hajian et al. 2016). Recent rescarch has focused on
developing explainable or interpretable AI models (Murdoch et al. 2019 Vilone & Longo (202)) because model interpretability and explainability are crucial for clinical and healthcare practices (Ahmad et al. 2018 Kolyshkina & Simoff, 2021), where misclassification costs can be potentially high. To address this, data mining techniques have emerged to discover interpretable rules by generating symbolic rules that humans can readily understand. By providing understandable patterns rules from training data, we can involve
2

---

Published in Transactions on Machine Learning Research (04/2026)
human experts such as doctors murses, allowing them to review AI model results and provide feedback or corrections. Consequently, this approach can improve the reliability of life-critical decision-making in healthcare.
Unlike deep learning- based models that often operate as black boxes, RBML is an algorithm that induces a set of symbolic rules from training data. RBML automatically identifies regularities or patterns that can be expressed in the form of "IF-THEN" statements. Here, the left hand side ("IF" part) is called the rule antecedent condition, which can be expressed in logical operators like disjunction, conjunction, and negation. The right hand side ("THEN" part) of a rule is called the rule consequent or conclusion. In particular, rule conditions represented in disjunctive normal form (DNF: OR-of-ANDs) or conjunctive normal form (CNF: AND-of-ORs) are intuitively understandable to humans as they mirror natural reasoning processes. For example, a medical diagnosis rule might state: "IF (patient age > 65 AND white blood cell count > 11,000) OR (body temperature > 100 AND patient has chest pain) THEN (further diagnostic tests for potential infection)". A natural choice for interpretability to represent ML output as logical operators like disjunction, conjunction, and negation with the IF-THEN structure, and these can be expressed through rule sets, decision trees, and decision lists. RBML's full transparency and intuitive explainability make it particularly valuable in applications where decision-making processes must be clear and explainable. The principles of RBML are most commonly implemented through the form of rule-based classifiers in modern MT. applications. Rule-based classifiers can be seen as a generalization of decision tree classifier since the obtained rules do not need to be represented in the form of a tree, thus being more flexible (Palliser-Sann) 2021). Unlike trees, DNF rules need not be mutually exclusive. These rules are potentially more compact and predictive than trees. Regarding the induced rules, it uses conjunctive antecedents: "IF condition 01 AND condition_0? 02 AND ... THEN conclusion". Each individual condition, also called selector, is formed by an attribute-value pair, where the pair refers to a specific feature of the data and its corresponding value. Rule-based classifiers have already demonstrated suecessful application across diverse domains, including medical diagnosis (Asgari et al.) 2019), financial fraud detection (Ali et al. 2022). intrusion detection (Lee
et al. 1999), and machine failure diagnosis in manufacturing systems (Jiang hong & Xiao'li 2009).
Research on RBML has introduced various approaches to extract rules from data. First, Rules Extraction System (RULES) (Pham & Aksoyy 1995) is simple algorithm for extracting set of classification rules from set of training instances given set of classes. It follows general-to-specifi approach and enforces perfect precision (100%) in the generated rules unless there are inconsistencies in the data. RRULES (Palliser-Sans 2021) was proposed as an optimization of RULES by focusing on two key points: the mechanism to detect irrelevant rules and the stopping condition. PRISM (Cendrowska) 1988) introduced a unique approach of generating rules by selecting examples of specific class and ileratively adding conditions until the obtained rule has perfect precision. As non-ordered and non-incremental algorithm, PRISM builds rules from general to specific patterns, with rule order being irrelevant for predictions. Interpretable Decision Sets (IDS) (Lakkaraju et al.) 2016) presented a method for generating decision sets which are sets of independent if-then rules. Since each rule can be applied independently, decision sets are simple, concise, and easily interpretable compared to a decision list. Bayesian Rule Scts (BRS) (Wang et al. 2017) introduced a novel Bayesian framework for learning rule sets that uses generative model to incorporate prior knowledge about interpretable rules while maintaining strong predictive performance. Incremental Reduced Error Pruning (IREP) (Fürnkranz & Widmer) 1994) addressed the computational inefficiencies of standard reducod error pruning in rule learning by integrating the pruning process directly into rule learning rather than as a post- processing step. This innovation laid the foundation for RIPPER (Cohen et al., 1995), which demonstrated that incremental pruning could achieve comparable or better results than standard pruming while being substantially more efficient. RuleFit (Friedman & Popescul 2008) extracts rules from an ensemble of trees by aut oumaicallly detecting interact ion effects in the form of decision rules and builds a weighted combination of these rules using LI Ll-regularized optimization over the weights (Friedman & Popescu 2004). SkopeRules
(Goix et al., (2000] is based on RuleFit's approach, utilizing a Random Forest model to fit class labels. The two methods differ only in their rule pruning strategy: RuleFit uses a linear model whereas SkopeRules heuristically deduplicates overlapping rules.
3

---

Published in Transactions on Machine Learning Research (04/2026)
2.2 Optimal Classification
In recent years, rescarchers have increasingly applied discrete optimization techniques to learn optimal docision trees in ML problems. The problem of learning an optimal dccision tree NP-hard (Laurent & Rivest, 1976), which has led to the widespread adoption of greedy heuristics such as Classification and Regression Trees (CART) (Breiman et al, 1984), which constructs univariate classification trees. However, over the last decades, there has been an overall 800 billion-fold speedup in the computational power of optimization solvers (Bertsimas & Dunn 2017). This astonishing increase in optimization solver performance has made it possible to apply modern mixed-integer optimization (MTO) methods to solve optimal decision trees. An overview of recent developments in optimization techniques for ML is presented in Bottou et al. [Bottou et al. 2018) and Gambella et al. (Gambella et al. 2021).
Recently, Bertsimas & Dunn (2017) introduced optimal classification tree (OCT), which is a mixed-integer programming (MIP) formulation to learn optimal decision trees given fixed depth. The constraints and variables of the formulation can be decomposed into three sets: those defining the structure of the tree through split decisions at each node, those routing data samples from root to leaf nodes, and those counting misclassifications. The objective function balances minimizing training set misclassification against tree complexity to preserve interpretability (Ales et al. 22044p. The MIP model supports both axis-aligned and oblique splits with exponential complexity in tree depth, and can handle both continuous and categorical features. Günlük et al. (2021) proposed an alternative formulation for optimal decision trees that specializes in categorical features. Their formulation exploits the combinatorial structure of categorical variables, enabling branching on subsets of categorical feature values. However, both models can easily become intractable as the size of training dataset grows. To address this issue, Verwer & Zhang (2019) proposed BinOCT, which represents decision thresholds through binary encoding, drastically reducing the number of decision variables. The number of decision variables is largely independent of the training set size. It only depends logarithmically on the number of unique feature values. To further improve scalability, Firat et al.) (2020) introduced a new formulation based on root-to-leaf paths for fixed-depth trees, which is solved using column generation- based heuristic. Finally, Aghaci et al. (2024) introduced a flow-based MIP formulation that represents optimal classification trees as a maximum flow problem. The flowOCT formulation avoids big-M constraints, resulting in stronger linear programming (LP) relaxations compared to previous OCT models. However, it only works with binary features.
In addition to classification decision trees, recent work has explored discrete optimization techniques to learn boolcan rules and rule sets. Su et al. (2016) developed an integer programming (IP) formulation for interpretable two-level boolean rules, expressed in either CNF or DNF, with a predefined maximum number of clauses, enabling controlled model complexity and enhanced transparency in classification tasks for high- stakes domains such as healthcare and law. Lawless et al. (2023) proposed an IP framework using column generation to learn sparse and interpretable boolean rule sets in DNF form, while incorporating fairness constraints.
3 Methods
This section presents a structure-constrained decision tree approach to identify patterns in datasets while adhering to prior domain knowledge and structural constraints defined by domain experts. In ruse- classification, any pattern or rule can be expressed through a nested if-then statement since their logical structure inherently consists of conditions (IF clause) and consoquenecs (THEN clause). On the other hand, decision trees effectively extract meaningful patterns from data and transform them into interpretable rules by linearizing conditions along paths from root to leaf nodes. Therefore, utilize decision tree approach that discovers classification patterns through nested if-then-else structures, ensuring all possible combinations of conditions, including negation scenarios.
Most business domains have domain-specific prior knowledge about their data. For example, in medical diagnosis, physicians know that elevated blood pressure and high cholesterol levels are key risk factors for cardiovaseular discase. Similarly, in diabetes prediction, medical experts rely on crucial diagnostic indicators such as body mass index (BMT), fasting blood glucose levels, and age. Furthermore, domain
4

---

Published in Transactions on Machine Learning Research (04/2026)
experts recognize that features can be naturally grouped based on their relevance. In cardiovascular discase assessment, for instance, blood test results (cholesterol levels, triglycerides, and blood glucose) form one group, while vital signs (blood pressure, heart rate, and body temperature) form another. Even when domain knowledge is unavailable, various ML methods can extract prior information about features. For example, model-agnostic method that explains the contribution of each
SHAP (SHapley Additive exPlanations) feature to model outputs (Lundberg & Leo 2017). Similarly, Boruta is a feature selection algorithm that identifies which features are statistically significant or relevant to the outcome variable (Kursa & Rudnicki, 2010). Additionally, feature importance in decision trees quantifies the relative contribution of each imput feature to the model's predictions. Therefore, we can reasonably assume two types of prior knowledge: 1) feature groupings based on feature correlation and 2) feature impact on the target variable based on feature importance. Given the prior knowledge, we propose a structure-constrainee decision tree to identify optimal patterns in data. This paper develops an optimization based model that utilizes prior information from either domain experts or ML algorithms.
3.1 Structure Constrained Decision Tree
A structure-constrained decision tree (SCDT) refers to a decision tree where the learning process guided and restricted by specific constraints imposed on its structure. These constraints aim to improve the interpretability, fairness, compliance, other desired properties of the resulting tree. In pattern discovery, we incorporate prior domain knowledge into the decision tree through structural constraints, following three steps to detect patterns in data. First, given the prior knowledge from domain experts or feature relevance determined by ML algorithms, we define a feature group as a subset of features that captures a distinct semantic or conceptual aspect of the classification problem, where feature groups are not required to be disjoint and may overlap. For instance, in diabetes diagnosis, laboratory measurements (fasting blood glucose, HbAlc levels) and patient characteristies (age, BMI, family history) can be formed into separate groups, reflecting their distinct roles in diagnosis. As shown in Figure D our framework allows feature groups to be overlapping, providing flexibility in capturing features that may belong to multiple semantic or conceptual categories. Additionally, we define GA as a special feature group containing all features, which serves as a default group when prior domain knowledge is insufficient to establish meaningful feature groupings. Second, we define the topology of the binary tree using the feature groups, which restricts feature availability al each branching node and the depth of the tree. For example, in medical diagnosis, blood test results might be restricted to upper-level nodes while patient symptoms are considered lower levels, following clinical diagnostic procedures. Finally, we the SCDT where feature selection at cach branching node is guided by predefined feature groups. This approach ensures the learning process follows the branching constraints imposed on the decision tree.
Prior Domain
Decision Topology
Structure Constrained
Knowledge
Decision (SCDT)
Feature Groups:
Tree Depth:
SCDT:
Ga [X)..., Xp)
[g
(x))
[x3,x55
64 (Xa, X6. X7)
Gs
Figure 1: Structure Constrained Decision Tree (SCDT). The tree uses breadth-fistt indexing scheme where nodes are numbered sequentially from the root (index 1) through internal nodes to leaf nodes. Feature groups (G G1 G2....) can be overlapping, where GA denotes special feature group containing all features, used when prior domain knowledge for defining feature groups is unavailable.
3.2 Optimal Pattern Detection Tree
In this section, we first introduce the volume-impurity index that measures coverage volume and misclassification by a rule and then present the basic concepts of OPDT. Subsequently, we present the TP
5

---

Published in Transactions on Machine Learning Research (04/2026)
formulation of OPDT. Finally, describe branching structure constraints OPDT and their enhancements to improve computational efficiency.
Metrics Prior RBML methods employ heuristic approaches with no optimality guarantees, focusing on precision maximization while treating coverage as a byproduct (Cendrowska, 1988). balancing precision with rule complexity such as the number of rules and conditions per rule (Lakkaraju et al., 2016). adopting a
two-phase strategy that prioritizes coverage in the growing phase before shifting precision improvement through pruning on separate validation sets (Fürnkranz & Widmer 1994; Cohen et al.
1995 or balancing
accuracy and interpretability through Bayesian likelihood and prior terms (Wang et al.
2017
Unlike these traditional implicit or sequential evaluation approaches employed in heuristic rule learning, we define a novel metric specifically designed for optimization- based frameworks that explicitly balances coverage volume with misclassification control through the weight parameter w, allowing domain experts to specify misclassification tolerance directly within the objective function before model training. Specifically, we propose a volume-impurity (VI) index that balances classification volume and classification impurity, defined as:
volume-impurity (VI) index = ="oolume gain"
-w x "misclassification loss"
where w is the weight controlling precision.
In rule discovery, volume gain refers to the size of samples covered by the rule, while misclassification loss represents the size of incorrectly classified samples among the covered samples. The goal of OPDT is to identify rule (i.c., root-to-lcaf path in a decision tree) that maximizes the VI index the leaf node.
Approach The primary focus in rule discovery is identifying patterns and regularities within a dataset. In this paper, aim to identify optimal rule that maximizes coverage volume while controlling misclassification through given weight. We utilize a decision tree approach to discover this optimal rule, where each rule corresponds to root-to-leaf path that maximizes the VT index through nested if-then-else structures handling negation scenarios while incorporating prior knowledge via structural constraints. As shown in Figure 2 given feature groups (c.g., G1, G2,...,Gop from prior domain knowledge or hcuristic algorithms, we initially assume a fixed length of rule conditions, allowing us to assign feature groups to specific depths in the chain of rule conditions (e.g., {G₁ - G2
GD}) under the SCDT framework. While SCDT allows different feature groups at each branching node as shown in Figure [ OPDT enforces the same feature group at each level of the decision tree to systematically explore all negation combinations (i.e., 2 or < for each feature within a feature group) across the chain of rule conditions. This determines the topology of the nested if-then-else tree. Using discrete optimization, we formulate our rule learning framework as a decision tree where leaf nodes are measured by the VI index and find rule conditions that maximize this value, yielding the optimal pattern among all possible combinations of rule conditions. We call this approach the Optimal Pattern Detection Troe.
Methiiaiiaal Formulation We use discrete optimization to solve the OPDT problem. Since OPDT aims to discover rule conditions rather than making predictions based on majority class of training samples in leaf nodes, the approach discards most nodes except for the node with maximal VI value. It extracts splitting conditions along the path from root to the leaf node with maximal VI value to form the IF part of the decision rule. The learned rule is represented as a chain of conditions and a label prediction. When a sample meets all conditions in the IF part, we say the rule fires, and we define such a sample as coverod by the rule. The rule is then evaluated by two metries: coverage (measured by fired volume) and precision (measured by misclassification loss). We formulate OPDT as mixed-integer program as follows:

---

Published in Transactions on Machine Learning Research (04/2026)
Feature Groups:
Struchure Constraints:
{G
G2
D
G,
X2
Gp xp-1 or Xp
of X6
X; Xr X
OPDT:
(xp-1,
[xp-1
(Xs) bi
x3)
(Xg)
(xx) 2 by
(ur)
{2 x4. X63
C max VI
Pxp Xp3
(xx]
bz
{..)
(xp-1. Xp3
G1
G2
GD
Leaf Nodes
Figure 2: Optimal Pattern Detection Tree (OPDT). All nodes the same depth are restricted to identical feature groups for the chain of rule conditions {G1 G2 -... GD).
Table Sets for OPDT
Symbol
Definition
P
set of features dataset with one-hot encoded categorical variables of samples in dataset ith sample in a dataset, E N
N
y
ith sample's label in dataset, i E N
K
set of class label
class label, & one-hot encoded matrix 1(y, k), AA E K, N maximum depth the optimal decision tree maximum possible nodes by tree with depth of T 2(0+1) - set of branch nodes with split a x < b, Ta = f1...., [T/2]} set of leaf nodes with class prediction, Tz [[T/2] + +.....,7 T}
Ya
T
TB
T
Tas
set of target leaf nodes where the VI index is evaluated in the objective function, Tass C Tr. index of each node, E (Z'
weight on misclassified samples in node, 2
p(t)
parent node of node
A(t)
set of ancestors of node A(t) (t)
Az(t)
set of left- left-branch ancestors of node whose left branch has been followed on the path from the root node node
AR(()
set of right-branch ancestors of node i whose right branch has been followed on the path from the rool node node
(t(
set of all leaf nodes from a left. child of node t
En(()
containing rightmost leaf nodes, from each child (left and right) of node t binary value indicating whether branching node t in T's contains split, [B(spiit) = [T's]
B (splitt) [t]
B ([grou)) [t]
feature group assigned branching node TB, [ggroup)] = [T'l
L [arget)][ [
binary value indicating whether leaf node f in Tz is target leaf node, |[(target) = [Tz]

---

Published in Transactions on Machine Learning Research (04/2026)
Table 2: Variables for OPDT
Symbol
Definition
Opt
slope element of split applied node i, Vp E P, Tи
de
slope vector of split applied at node i, where âe = (aie, (ppp)) Vt E Tb
intercept of split applied at node i, Vt E Te 1 1(node& t applies a split), vt E TB 1e, is in node 2), Vi N, E TT 1 (leaf contains any sample], VI E Tτ total number of samples node 4, V Tı number of samples of label & in node f, Ak K, Vt Tи
de
Rat
4
No
Na
Cht
1 (the most common labels in node is k), Ckt = 1 {arg maxker [Nkt) = k), A4: E K
Le
the number of misclassified samples (L. No- MM) in the leaf node 1, where M, is total number of the most common labels in node t, M, = maXKEk Nux, Vt Tay
volume-impurity (VT) value calculated the total number of samples minus the misclassified samples in a leaf node, I = {N₂ wL,), Vt E Totj
Iax
maximum number of I, over all target leaf nodes, Imo max
binary variable indicating whether leaf node t has the maximum VI index, Vt E Toos
max T Iax
(1)
subject to:
P
Opt = de,
Vt E TB
(2)
p=1
de S dp(t):
Vt TB \ {1}
(3)
1, S d,,
AI TB Ys E Fl)(()
1, 2 dr,
1I E Tn. Vs E En(()
2a 44
vi N Tn
(6)
N = Σ
2B EET
(7)
i=1
Σ Zit 1, ViEN
(8)
1ET2
d. (14 + ē) < b, + (1 + mmax) z1e);
(9)
Vi N, Vt E T2, Vs E At(t)
A 0g Ti > 4y - -(1 2z)
(10)
N V& AR(()
K
Σ
Cke 41
Vt T
(11)
Nga Σ
Yazzit
4k K, T
(12)
==1 T4 2 N₁ Nut M(1 ckt);
(13)
Wk K, Vt Tob
T4 < N₂ Net + Mc
(14)
Wk K, Vt Tob
Imar 2 N₂ wh,,
1I E Tobj
(15)
8

---

Published in Transactions on Machine Learning Research (04/2026)
max S No- -ww + M(1 9c).
Vt E Tobj
(16)
Σ qt =1
(17)
(ETob)
de E(,,1)
(18)
Opt [0,11)
DVEEE TB
(19)
0 05 Sd, WE
(20)
Au E(0,1), MEN,VIEN
(21)
4 1( VIETL
(22)
Cue E( AKE K, E TL
(23)
N, EN, WEE
(24)
Nu: EN, vk E M.
(25)
L. EN, V Tobj
(26)
qi 1(,
Vt Tobj
(27)
I Imxx ER
(28)
Our OPDT formulation adopts three fundamental constraints from Bertsimas & Dumn 2017)'s 's OCT: tree structure raists (split decisions at branching nodes), sample routing constraints (directing samples from root to leaf), and misclassification constraints (counting misclassified samples at each leaf node). On top of these, we introduce constraints that force samples rightmost lcaf nodes when parent nodes do not split, correcting sample routing behavior for accurate VI evaluation at branching-termin terginaedd parent nodes, and constraints that linearize the logical condition for maximal VT selection among leaf nodes. The objective of the leaf nodes while minimizing misclassification loss through the VI index,
(1) maximizes volume which combines volume and misclassification loss with weight w. Constraint Ope for a branching node can be activated if the node applies a split. Constraint (3) allows a branch node lo split only if its parent node splits. Constraint ( ensures that all leaf nodes from a left child of a branching node have zero samples if the node doesn't 't split, forcing samples to be assigned to the rightmost leaf nodes. Constraint 5 ensures that the two rightmost leaf nodes from both left and right children of a branching node must be active if the branching node splits. Constraint (6) guarantees that samples can be assigned to leaf node if the node is active. Constraint 7 counts the total number of samples at leaves. Constraint (8) forces each sample to be assigned to exactly one leaf. Constraints gg and 10p formulate the branching rules at each node, where ? denotes a vector of sufficiently small positive values Ep for each feature E P and Cmax = maxp Cp- These Cp and Cmax arise from a tochnical neccssity in MIP formulations: strict incquality constraints of the form a, x4 < by are not directly supported by MIP solvers and must be converted to non-strict form. Practically, 6p can be any sufficiently small positive number that does not cause numerical instabilities in the MIP solver. On the other hand, the largest valid value of ep is the smallest non-zero distance between adjacent values of feature p in the data. We use the largest valid value of cp for numerical stability. The parameter émax acts as the big-M constant since the maximum possible value of a, (ar; + + b, is 1 Emaxx Constraints [13 and 14h represent misclassification loss in each target leaf node, where M denotes a big-M constant. Here, we take M |N| as a sufficiently large value since the misclassification loss at any leaf node bounded by [.V. Constraints 15 16 and 17 represent the maximum value of the VI index over all target leaf nodes, where the largest valid value of M is w|N]. Finally, decision variables 18). 19 and (20) specify the branching structure, where de indicates whether node & has split, apt selects features for the split, and b, defines the threshold for split a²x x < b at each branch node. Variables 21 22 and (23
2 cnsures that slope variable
determine sample assignments to leaf nodes, leaf node activation, and class predictions, respectively. Count variables 24 25), and (26) track the number of samples in cach Icaf node, the number of samples per class in each leaf node, and the number of misclassified samples in target leaf nodes, respectively. Binary variable (27) indicates whether leaf node t has the maximum VI index. Finally, Imax (28) represents the maximum VI index value across all target leaf nodes. For a fixed tree depth D, the formulation scales lincarly in both [N] and PP) but exponentially in D, an inherent characteristic shared with Bertsimas & Dunn (2017)'s OCT. Since the new constraints and variables introduced in OPDT add only 0(2%) additional variables
9

---

Published in Transactions on Machine Learning Research (04/2026)
and constraints, which are dominated by the OCT routing constraints, they do not alter the asymptotic complexity. Therefore, OPDT maintains the same O(2P (|P) + [N]) model size complexity as OCT.
Branching Structure Constraints We incorporate Branching Structure Constraints (BSC) into OPDT to integrate prior knowledge from domain experts. These constraints aim to improve the interpretability and compliance of the resulting rule while enhancing computational efficiency. We design a decision tree that complies with BSC lo control: 1) the tree topology through splitting decisions and 2) feature allocation at each branching node through predefined feature groups. Specifically, we define two arrays for branching nodes: B(split), which indicates whether each branching node ncods to be split or not, and (grouu)) which specifies feature group G5 for branching node where Gj is a subset of features used for branching. These arrays enable to construct. the desired tree structure and feature allocations over branching nodes to solve the OPDT problem. For leaf nodes, L(target) is a binary array that identifies which leaf nodes are target nodes in the objective function, determined by domain expert to be aligned with Bssplit). We assume that feature subgroups for B(group) can be determined by domain expert knowledge. However, this feature grouping is optional as mentioned in Scction 3.1 When predefined feature groups are unavailable, OPDT has the flexibility to use a default feature group GA containing all features. By assigning GA to all branching nodes, OPDT can enumerate all feature combinations without any subgrouping constraints (e.g-; not even requiring separation into numerical and categorical features). Finally, BSC adds additional constraints on di, Opti be, and Tobj from Algorithm I to the main OPDT MIP formulation.
In this paper, we use only the basic numerical group separation without considering domain- specific knowledge for feature grouping. Specifically, we define GN as the set of numerical feature groups (i.e., feature groups containing only numerical features) and Ge as the set of categorical feature groups (i.e., feature groups containing only one-hot encoded categorical features). Px(g) denotes the set of features in numerical feature group g Gn and Po(g) denotes the set of features in categorical feature group 9 Go, where Pc())) S P. This basic grouping strategy demonstratos that even without sophisticated domain knowledge, OPDT can achieve significant computational gains through feature subgrouping, we demonstrate in Section 4
Algorithm 1: Branching Structure Constraints (BSC)
Input:
((split)),, [B(rrou))) ((grou)) [targett)
// B(split): binary array to indicate branching splits // B(group): subset of features allocated to each branching node
// L(target): binary array to indicate target leaf nodes
1/ Px(g): set of features in numerical feature group 9 E Gn // (g): set of features in categorical feature group E Go
2 foreach t e TB do
d, = B(split) it]
g + (grooup)
if g G then apt 2 0,
Vp E P
else if E Gn then
8
Gyt = 0,
Vp E P Px(g)
elsc if g E Go then
10
Apt = 0,
Vp E P Polg); b, = 0.5
11 Tosj = {t E Ty [targget)) =}
4 Computational Results
In this section, we evaluate the performance of OPDT on datasets from the UCI Machine Learning Repository (Kelly et al. (2017p. Since the purpose of this paper is to identify a single pattern in data that maximizes coverage while minimizing the false positive rate due to misclassification, for algorithms that generate
10

---

Published in Transactions on Machine Learning Research (04/2026)
multiple rules, analyze the best candidate rule among the set of rules generated by ruleset extracting models such as BRS (Wang et al., 2017]. IDS (Lakkaraju et al. 2016), IREP (Fürnkranz & Widmer 1994). PRISM (Cendrowska, 1988). and Ripper (Cohen et al. 19955. All experiments were conducted on an Apple M2 system with an 8-core CPU and 8GB of RAM. In all experiments, we set the weight w for the VI index to as the default value.
4.1 Datasets
For our experiments, we use all 15 publicly available datasets from the UCI Machine Learning Repository
(Kllly et al. 2017) as detailed in Table 3 For domains that require high interpretability and reliability, we
focus on healthcare and finance datasets (Quinlan
1987
Hofmann
1994
Ych 2008 WWlberg al., 1995
Rubini et. al.
2015 Islam et. al., 2020; Salzberg
1988
Gi Girela
2012 2
Janosi
al.
1988
Chicco &
Jurman 2020 Gong 1983 Ramana et al. 2012
Little
2007
Sigillito
1990
Lubicz et al.
2014
We apply
an 80/20 train-test split for our experiments.
Table 3: UCT Dataset
Dataset
i_instaannes
feaatuures [num, cat)
weights
description
(r1 mimmsii)
(neg, pos)
Australian
653 (37)
15 (6, 9)
(357, 296)
credit approval
German
1000 (0)
20 (7, 13)
(300, 700)
credit approval
Blood Trranfussonn
748 (0)
4 (4, 0)
(570, 178)
healthcare
Breast Cancer
569 (0)
30 (30, 0)
(212, 357)
healthcare
Chronic Kidney
215 (185)
24 (11, 13)
(128, 87)
healthcare
Early Stage Diabetes
520 (0)
16 (1, 15)
(320, 200)
healtheare
Echocardiogram
62 (69)
7 (4, 3)
(44, 18)
healtheare
Fertility
100 (0)
9 (2, 7)
(88, 12)
healthcare
Heart Disease
297 (6)
13 (6. 7)
(160, 137)
healthcare
Heart Failure
299 (0)
12 (7, 5)
(203, 96)
healthcare
Hepatitis
80 (75)
19 (6, 13)
(67, 13)
healtheare
Indian Liver Patient
379 (4)
(9, 1)
(414, 165)
healthcare
Parkinsons
195 (0)
(22, 1)
(147,
healthcare
Pima Indlans Diahetes
768 (0)
(8, 0)
(500, 268)
healthcare
Thoracic Surgery
470 (0)
(3, 13)
(400, 70)
healthcare
4.2 Performance Enhancements
Generally, solving an ODT is known to be an NP-hard problem (Laurent & Rivest 1976 To address this computational challenge, we propose three complementary techniques to enhance performance: 1) Branching Structure Constraints (BSC), which leverages prior knowledge about feature relationships to reduce the search space, 2) warmstart initialization, which provides a quality initial solution to accelerate convergence, and 3) branching priority orders, which guides the search process by prioritizing promising decision variables. These techniques work synergistically- BSC narrows the fcasible region, warmstart provides good starting point within this reduced space, and priority ordering helps efficiently navigate toward optimal solutions. Our empirical results demonstrate that this combination significantly reduces computational time while maintaining or improving solution quality across diverse datasets.
First, BSC enhances both interpretability and computational efficiency by imposing meaningful constraints on the branching structure of decision trees. Table 4 with a 10-minute time limit, demonstrates significant computational savings when prior knowledge about rule structure is incorporated. The impact is particularly dramatic for certain rule structures for instance, employing {categori Caategoricall-fnumeric....
constraints
reduces runtime from 1232 seconds to 23 seconds for Heart Disease and from 924 seconds to 21 seconds for Thoracic Surgery. Furthermore, decomposing fcatures into numerical and categorical subgroups proves highly eveective. In the case of Chronic Kidney Disease, this systematic decompasition strategy reduces the total runtime from 978 seconds (by all features) to approximately 45 seconds (by decomposing features). Beyond runtime improvements, the systematic feature decomposition assists feature pruning by identifying essential structural patterns for optimality. For example, in Thoracic Surgery, while optimality of the solution with VT 42 remains uncertain due to the time limit being hit one of feature decomposition,
11

---

Published in Transactions on Machine Learning Research (04/2026)
any potential better solution must exist under the feature combinations involving categorical features were solved to optimality within the time limit. This effectively eliminates categorical features from the search space for an optimal solution. Such insights significantly reduce the search space by allowing us to focus computational resources on the most promising Teature combinations. In real-world applications, prior domain knowledge could enable even finer feature groupings beyond the basic numerical-cttegorical group separation. Therefore, BSC not only enhances computational efficiency but also provides valuable guidance toward optimal solutions through strategic feature decomposition.
rule structure, all other
Table 4: OPDT Runtime (in seconds) and VI by Branching Structure Constraints (BSC)
Structure Constraints (solver time limit 600 sec)
all-all
num-nurm
mum-cat
cat- mimmmm
cat-cat
Dataset
Runtime
VI
Runtime
VI
Runtime
VI
Runtime
VI
Runtime
VI
Australian
600.04
143
982.97
49
975.71
143
45.66
143
7.29
124
Cerman
1475.81
31
631.47
35
1065.43
45
1006.65
45
968.56
44
Chronic Kidney
977.94
99
23.35
93
16.66
99
4.64
99
0.57
88
Early Stage Diahetes
23.07
151
3.53
25
130
1.32
130
8.27
151
Echocardiogram
13
0.85
13
13
0.05
Fertility
31
0.36
31
30
0.23
30
24
Heart Discase
1232.85
31
1061.62
26
947.29
31
22.67
31
1.93
17
Heart Failure
1017.01
61
1410.82
61
4.01
21
79.37
21
Hepatitis
10.70
40
1.82
40
0.50
38
0.15
38
0.11
35
Indian Liver Patient.
1421.23
75
600.02
75
0.41
45
6.18
45
Parkinsons
600.02
86
954.41
86
4.08
64
0.96
64
Thoracic Surgery
924.10
39
964.28
34
77.15
42
20.54
42
2.34
42
For warmstart initialization, develop novel heuristic algorithm adapted from CART (Breiman et al, 1984h for structure constraints, called Branching Structure Constrained Classification and Regression Tree (BSCCART), as no existing heuristics for struclure-constrained decision trees are available. BSCCART modifies CART's branching criteria. by restricting feature select al each node to comply with the branching structure constraints. By applying the same structure constraints used OPDT, the BSCCART solution can serve as a warmstart for OPDT. The performance comparison between BSCCART and OPDT presented in Tables and [ For example, Figure 3 illustrates that the pattern discovered by BSCCART is improved by OPDT on the German dataset. While BSCCART produces best VI of 8, OPDT improves this to 32 in 12 seconds (highlighted in red), progressing toward the optimal solution. This example demonstrates how OPDT can improve upon heuristic solution obtained from ML algorithms or prior knowledge. For branching priority orders, we assign higher priorities to topology variables (e.g., Opt and de), guiding the MIP solver to decide the tree structure variables before others.
Table presents the computational runtime and VI values across different configurations of warmstart and branching priority orders, where on/on denotes the of both strategies. Generally, the on/on configuration demonstrates superior equivalent performance compared to other configurations, showing trends toward higher VI values or faster runtimes. This is particularly evident in datasets solved to optimality within the time limit, such as Early Stage Diabetes, Echocardiogram, Fertility, and Hepatitis, which show identical VI values across all configurations. For those datasets, the runtime analysis clearly demonstrates that both warmstart and branching priority orders contribute to faster computation times compared their off counterparts. Furthermore, the on/on configuration exhibits more stable performance with moderate standard deviations, while the off/off configuration often shows larger variability. However, the optimal configuration appears to be dataset-dependenn with some exceptions: Blood Transfusion achieves slightly better VI with on/off, Indian Liver Patient performs best with on/off, and Breast Cancer shows optimal results with on.. Overall, despite some dataset-specifie variations, the combined use of warmstart and branching priority orders (on/on) enhances both solution quality and computational efficiency across diverse datasets.
12

---

Runtime Published in Transactions on Machine Learning Research (04/2026)
Optimal Pattern Detection Tree (OPOT)
BSCCART
LeFT
RIGHTTI TiVe
IDV
Best
tireger
Bmnt te:ns
9:l. (1:00
IF X[R2] 36.5
5-080
2.4
THEN X(AS) 10073.5
THEN 743(189) == Class 18810.25) Class 53510.75)
1880 -1,137
000
10%
228
754
6.089
C201 2185
Dafr1 635
3.69
41033
Class
219
9.58M
111-0
ELSE IF X[A13]
248
1-480
0.8.
THN 2x(2)
Class 2418.779 77) Class 7(0.23)
-39
16
190
218
5.089
090 27.-290
51084
ELSC 115(38) Class 50(8,42) 42)
Class 8818.500
VI 500
139
10h
311
5:588
090 0180
395
125
890 2180
51358
2-1
Ww.
intesible
29.2000
Optimal Pattern
46
356
511
6.489
85--800
123549
I7 X[R2] 9.00
603
1.000
0m. mm
THEN X[AS]
3384.00
716
69
540
5:000
598 218
19079
THEN 72(4)
:e Class 4(0.86)
Class 68(6.94)
72
5.000
9[4)
tlass
-31
30t
16
19.099
14:210
ELSE IF X[AS]
11816.00
172
14L
165-7544
518
15-430
17.2180
13/01
THEN 800K2481
Class 24810.313
Class 35218.69)
2480 -1,690
214
2H
30.40 09.000
29. 0100
-3095
RLSE 19(5) Class 14(8. 74)
Class 1: 5(8.26)
vI: 19 50 -51
Pla
(R/1 1ibh,
301
574
00007
450133
307
100
32.000 3..899
69. 68--100
+0/01
Figure 3: VI improvement by OPDT over BSCCART on the German dalaset given w = 10. BSCCART, heuristic method, yields best value of S. OPDT enhances it 32 (highlighted red), achieved in 12 seconds.
Table 5: OPDT Runtime (in seconds) and VI by Warmstart and Branching Priority Orders. Bold represents the highest VI value
Warmstart from BSCCART/ / Branching Priority Orders (solver time limit 120 sec)
on on
on / off
/ on
off / off
Dataset
Runtime
VI
Runtime
VI
Runtime
VI
VI
Australian
18.715
134.300
26.616
134.300
23.496
132.400
54.946
134.300
(L16.804)
(112.996)
(133.923)
(112,996)
(1211194) 194)
(+12.963)
(1-49.832)
(112.781)
German
29.296
53.800
11.331
51.300
42.333
33.800
108.27 277
24.600
(4:991422
(+17.568)
(+20.068)
(+17.468)
(=400.23)
(+12.109)
(+:297.112
(+19.856)
Blood Transfusion
7.574
51.000
18.458
51.200
9.565
50.100
6.575
50.800
(19.662)
(110.559)
(126.890)
(1100.44))
(112.220)
(112.387))
(106.00)
(110.696)
Breast Cancer
37.938
230.100
29.135
230.000
42.666
231.000
68,280
223.300
(273
(+5.782)
(+19.873)
(+5.774)
(+32.837)
(+7.630)
(+26.746)
(+1..95
Chronic Kidney
1.230
98.700
3.675
99.200
3.201
99.200
4.746
98.500
(11.101)
(#3.234)
(1:3.503)
(+3.327)
(4:2,730)
(+3.3277
(1:7.048)
(#3.408)
Early Stage Diabetes
1.302
153.400
1.811
153.400
3.230
153.400
4.536
153.400
(+1.032)
(#3.565)
(+1.275)
(+3.565)
(+1.231)
(+3.565)
(+1.904)
(#3.565)
Echocardiogram
0.162
18.667
0.233
18.667
0.664
18.667
0.654
18.667
(80018
(+4.743)
(+002633)
(+4.743)
(+0.552)
(+44743)
(+0.563)
(+4.743)
Fartility
0.073
34.300
0.101
34.300
0.252
34.300
0.342
34.300
(#0.089)
(+1.947)
(1:0,141)
(+1.947)
(+0.118)
(+1.947)
(#0.164)
(+1.947)
Heart Disease
14.438
28.200
18.029
26. 76.
9.782
26.100
15.690
27.700
(+1..564)
(#4.709)
(+:9.863)
(+4.423)
(+12.683)
(#3.178)
(+16.870)
(+4.832)
Heart Failure
10.971
62.100
11.723
61.800
11.219
60.200
16.533
61.500
(117.315)
(15.859)
(119.361)
(15.996)
(+11.942)
(1-4.467)
(+14.937)
(16.329)
Hepatitis
0.667
42.200
0.869
42.200
0.653
42.200
0.703
42.200
(11))
(13.393)
(114834)
(13.393)
(+00551)
(+3.3933
(+0.428)
(+3.3933
Indian Liver Patient
14.701
82.300
21.831
84.000
27.622
83.800
23.099
76.200
(115.843)
(L8.220 (20)
(121.734)
(17.454)
(131.831)
(17.361)
(128..15) 159)
(115.817)
Parkinsous
25.639
82.700
15.436
82.500
30.355
82.700
15.611
82.700
(+34.000)
(#3.268)
(+23.398)
(+3.308)
(2.3)28)
(+3.268)
(+15.215)
(+3.268)
Pima Indians Diabetes
22.204
91.200
26.598
90.900
21.091
91.100
54.652
89.500
(1:33.173)
(15.329)
(4:20.140)
(166.73)
(1:23.32))
(+5.322)
(1300200)
(1:6.704)
Thoracic Surgery
29.033
46.200
21.901
45.600
26.106
45.444
32.679
46.200
(+28.946)
(=5.095)
(+14.735)
(+4.812)
(#27)370)
(+5.223)
(+20.418)
(#5.095)
13

---

Published in Transactions on Machine Learning Research (04/2026)
4.3 Computational Experiments
In this paper, we preprocess features differently according each algorithm's requirements. For RSCRULES, IREP, PRISM, IDS, and RIPPER, discretize numerical features into ten equal bins. For BRS, binarize features into binary format. For OPDT and BSCRULES, while continuous numerical features can be used without transformation, categorical features must. be one-hot encoded. Regarding rule complexity, the length of rule conditions to two for RIPPER, BRS in ruleset extracting models, and all structure- constrained models as shown Tables 6 and Other algorithms, having no such rule length parameter, rule generation. To
limit
can generate rules with conditions longer than two as they have more flexibility provide another structure-constrrinee method alongside BSCCART, we develop a simple rule structure- constrained (RSC) algorithm based on Rules Extraction System (RULES) (Pham & Aksoy 1995). which we call RSCRULES. Finally, impose 10-minute time limit OPDT runtime.
For experiments, we create 10 random data splits through shuffling. For each split, we compute performance metrics and report their averages across the splits. Additionally, since RIPPER and BRS are non- deterministic algorithms, we run them with multiple random seeds on each split: 50 different seeds for BRS and different seeds for RIPPER. The computational details are provided Table i the Appendix. We compare the induced rules basod on their precision, coverage, and colume-impurity. Precision calculatod the ralio between the number of samples correctly classified by a rule and the total number of samples covered by the rule. Coverage is computed the ratio between the number of samples covered by the rule and the total number of samples in the dataset. VI is computed based on volume and misclassified samples with respect to weight w = 10. We use test data to evaluate how well the induced rule caplures a common pattern in unseen data.
Table 6: OPDT Performance Compared to Benchmark Methods Training Datasets (80%). Bold indicates ranking top 4 methods, and underlined represents the best performance across all methods.
Training Data (80%)
Structure-constraancc Models
Rulesct Extracting Models
Dataset
OPD'
BSCCART
RSCRULES
BRS
IDS
IREP
PRISM
Ripper
VI
135.60
130.50
103.40
116.72
36.30
103.40
44.20
114.38
Australian
Time
602.00
0.25
0.04
0.36
0.22
0.08
3.03
2.01
VI
60.00
49.80
57.80
16.27
19.20
-32.20
20.10
47.62
German
Time
749.82
0.20
0.10
0.53
0.25
0.09
7.20
0.17
Blood
VI
51.20
45.50
24.00
-583.40
12.20
10.72
15.10
18.17
Transfusion
Time
90.70
0.13
0.02
0.23
0.23
0.04
0.53
0.07
230.00
183.50
124.60
114.00
111.70
50.51
114.30
50.50
Breast Cancer
Time
790.97
7.25
0.59
0.39
2.95
99.20
98.10
52.90
46.31
79.10
84.00
Chronic Kidney
0.24
0.33
0.13
0.29
0.15
Early Stage
153.40
153.40
121.20
151.83
119.30
118.16
90.60
151.75
Diabetes
Time
3.71
0.03
0.02
0.54
0.21
0.04
0.63
0.08
18.10
14.50
9.90
-8.13
7.50
4.31
7.10
5.74
Bchocardiogram
Time
0.80
0.07
0.01
0.24
0.18
0.05
0.18
0.07
VI
34.30
34.30
17.40
18.71
20.30
16.19
15.00
17.18
Fertility
Time
0.25
0.02
0.01
0.27
0.19
0.03
0.13
0.04
VI
29.20
16.80
20.50
15.01
15.10
-5.89
13.30
13.59
Heart. Disease
Time
524.81
0.14
0.03
0.36
0.20
0.06
1.01
0.10
VI
62.10
29.60
16.30
-41.97
19.40
17.58
20.70
21.41
Heart Failure
Time
729.32
0.36
0.03
0.30
0.19
0.07
0.82
0.11
VI
42.20
40.10
17.50
29.31
25.00
26.33
21.80
28.00
Hepatitis
Time
0.82
0.10
0.01
0.27
0.19
0.06
0.15
0.07
Indian Liver
82.50
54.50
19.60
-790.93
17.40
42.62
18.10
46.09
Patient
Time
999.70
0.61
0.04
0.27
0.21
0.09
2.98
0.14
82.00
70.20
28.50
52.25
17.56
26.70
18.16
Parkinsons
Time
863.11
1.77
0.37
0.35
Pima Indians
89.10
36.20
-920.73
21.50
22.69
22.80
26.88
Diabetes
Time
1047.67
0.76
0.07
0.35
0.08
3.35
0.13
Thoracie.
46.20
20.20
31.70
-21.07
14.40
-2.14
16.90
26.36
Surgery
Time
133.21
0.10
0.02
2.13
0.21
0.05
1.70
2.16
14

---

Published in Transactions on Machine Learning Research (04/2026)
First, Table [ shows that OPDT can find better common patterns in data compared to other models, including ruleset extracting models that have more flexibility in rule length. Regarding runtime in Table 10 in the Appendix, we measure total runtime including warmstart generation, model initialization, and 10 minutes of solver time, which can exceed 600 seconds. In other words, a runtime less than 600 seconds indicates the problem was solved to optimality. Table 10 demonstrates that several datasets were solved within the time limit, showing that OPDT is applicable for finding an optimal rule in moderate-sized datasets. Furthermore, as shown in Table even for datasets that do not reach optimality within the 10-minute limit, the best solutions are typically found within the first 2 minutes. Second, among the structure-constrained heuristic methods we developed, Fable@shooee that BSCCART performs better than RSCRULES. Moreover, BSCCART achieves the second-best performance in finding high-quality rules among all methods while complying with structure constraints given by domain experts. Among the ruleset extracting models, RIPPER shows comparably good performance to other methods, As shown in Table [0 OPDT requires more than 10 minutes to prove optimality for some datascts. This could raise concerns about the scalability of OPDT to real-world applications. However, in this paper, we use only the basic numerical-categorree group separation without considering domain-specifer knowledge for feature grouping. As shown in Table 4 if feature grouping is actively utilized, computational efficiency can be enhanced significantly. We further evaluate the induced rules from each model on test datasets. Table shows that OPDT achieves the best VT scores in 6 datasets, which is double that of BSCCART or RIPPER that have the best VT in 3 datasets. Furthermore, OPDT performs within the top 4 in most datasets, with exceptions in 5 datasets. BSCCART and RIPPER maintain their strong performance on test datasets, consistent with their performance in training datasets, showing the second-best results after OPDT.
However, it is worth noting that OPDT's strong training performance does not always transfer to the test set. For example, even though OPDT achieves a higher VI value than BSCCART on training data for the German and Heart Disease datasets, it fails to show better VI on test data. Specifically, in the German dataset, OPDT achieves precision 0.936 and coverage 0.225 on training data, but precision 0.883 and coverage 0.231 on test data, resulting in a test VI of -7.9. In contrast, BSCCART achieves precision 0.920 and coverage 0.315 on training data, and precision 0.896 and coverage 0.326 on test data, resulting in a test VI of 1.8. A similar pattern is observed in the Heart Disease dataset: OPDT achieves precision 0.979 and coverage 0.165 on training data, but procision 0.800 and coverage 0.180 on test data, yiclding test VI of -9.2, whereas BSCCART achieves precision 0.926 and coverage 0.269 on training data and precision 0.944 and coverage 0.250 on test data, yielding a test VI of 5.0. In both cases, OPDT identifies a narrower region (lower coverage than BSCCART on training data) to achieve higher precision. However, this precision advantage is not stable on the test set. This suggests that the weight parameter w may force OPDT toward a narrow region that fails to represent the whole dataset, implying that w = 10 may not be an appropriate value for representing the dominant pattern in these datasets. As another case, in the Thoracic Surgery dataset, while BSCCART, IDS, and PRISM identify rules with very narrow coverage (0.064, 0.038, and 0.045, respectively) but near-perfect precision (0.991, 1.000, and 1.000) on training data, OPDT identifies substantially broader rule with coverage 0.264 and precision 0.949, resulting in a higher training VI of 46.2 compared to 20.2, 14.4, and 16.9 for BSCCART, IDS, and PRISM, respectively. However, on test data, OPDT's broader rule yields a test VI of -9,8, whereas BSCCART, IDS, and PRISM achieve better test VI values of -3.8, -0.1, and 4.5, respectively. Even though OPDT discovers a more representative pattern in data with broader coverage (0.247) and reasonable precision (0.855) than BSCCART (precision 0.521, coverage 0.066), IDS (precision 0.933, coverage 0.031), and PRISM (precision 1.000, coverage 0.048), the weight parameter penalizes OPDT's broader coverage rule. This further supports the observation that the choice of w is critical to finding representative pattern in data. Additionally, it is worth noting that IDS and PRISM are not constrained to rules with only two conditions, unlike OPDT, potentially giving them an advantage in searching for patterns having more than two conditions.
Finally, Table g presents the sensitivity analysis of the weight parameter w on the UCI Hepatitis dataset. As w decreases from 10 to 2, OPDT exhibits a monotone precision-coverage coverage trade-off, yielding higher coverage at the cost of reduced precision, confirming that w functions as an adjustable precision requirement. Runtime remains stable across all w values, and test performance closely tracks training performance, indicating strong out-of-sample performance.
15

---

Published in Transactions on Machine Learning Research (04/2026)
Table 7: OPDT Runtime and Time to Solution (in seconds) without BSC. Runtime represents the total computational
time including optimality proof, while Time Solution represents when the final improvement the best solution was made.
Dataset
Runtime
Time to Solution
Australian
139.363 (=45.693)
11.625
(=14.371)
German
930.113 (=382.954)
104.823
(=141.195)
Blood Transfusion
776.287 (#534.019)
2.771
(=2.539)
Breast Cancer
1096.570 (1:234.988)
125.454
(=300.844)
Chronic Kidney
916.377 (=292.314)
119.097
(-169.979)
Early Stage Diabetes
112.018 (=311.394)
2.764 (=2.390)
Echocardiogram
109.457 (=321.932)
0.176 (=0.487)
Pertility
4.687 (11.996)
0.213 (10.449
Heart Discase
904.345 (=380.713)
41.966 (185.544)
Heart Failure
187. 187.302 302 (=3))433
17.734 (=27.696)
Hepatitis
8.601 (3354)
0.560 (=1.711)
Indian Liver Patient
1161.727 (1196.88) 850)
10.659 (112.828)
Parkinsons
999.464 (1338,915)
14.228
(1294471)
Pima Indians Diabetes
600 030 (10.007)
140.321
( 182.179)
Thoracie Surgery
585.05 (=.47339)
28. 28.280
32.392)
Table 8: OPDT Performance Compared Benchmark Methods Testing Datasets (20%). Bold indicates ranking in top 4 methods, and underlined represents the best performance across all methods.
Test Data (20%)
Strncture-coonstrained Models
Ruleset Extracting Models
Dataset
OPD'
BSCCART
RSCRULES
BRS
IDS
IREP
PRISM
Ripper
Australian
22.80
21.70
20.60
20.93
5.00
-41.30
8.20
-8.26
German
-7.90
-1.80
-4.20
-0.71
1.80
-37.32
0.80
10.52
Blood Transfusion
-6.50
-6.60
-6.30
299.24
-13.30
-28.31
-10.10
-31.68
Breast Cancer
48.20
38.60
25.60
21.22
21.30
10.04
25.30
10.62
Chronic Kidney
16.80
17.60
13.10
9.33
10.10
19.83
13.10
21.80
Early Stage Diabetes
38.10
39.60
31.80
38.31
27.20
26.44
24.00
38.74
Echocardiogram
-2.20
-1.60
-2.80
-8.98
-2.20
-0.10
-2.30
-1.33
Fertility
6.60
6.60
0.10
1.03
3.10
3.58
3.80
-1.4
Heart Disease
-9.20
5.00
-0.90
0.64
2.10
-19.49
0.20
-4.52
Heart Failure
5.10
-1.20
-5.20
-19.25
3.80
-8.55
1.00
-6.73
Hopatitis
0.50
-2.20
-5.40
3.43
1.10
4.55
2.70
5.66
Indian Liver Patient
12.70
2.30
4.20
-198.45
3.50
7.05
4.40
-7.92
Parkinsons
2.80
-5.80
8.60
9.06
0.00
4.06
3.20
4.60
Pima Indians Diabetes
4.90
-8.40
4.90
-237.90
3.70
-9.60
1.60
-8.96
Thoracic Surgery
-9.80
-3.80
-4.90
-27.67
-0.10
-12.72
4.50
-8.17
Table Sensitivity analysis the weight w on the UCI Hepatitis dataset (Training: 64, Test: 16). For precision, counts in parentheses denote the number of true positives out of the total fired samples (e.g., 0.978 (45/46) denotes 45 true positives out of 46 fired samples). For coverage, the counts in parentheses denote the total fired samples out of the total samples in the dataset (e.g., 0.719 (46/64) denotes 46 fired samples of 64 total samples). VI denoles the VI value in training data and Runtime denotes the total computational time in seconds.
Training Data (80%)
Test Data (20%)
Precision
Coverage
Precision
Coverage
VI
Runtime
10
1.000 (38/38)
0.594 (38/64)
1.000 (9/9)
0.562 (9/16)
38
13.83
9
1.000 (38/38)
0.594 (38/64)
1.000 (9/9)
0.562 (9/16)
38
11.45
8
0.978 (45/46)
0.719 (46/64)
0.923 (12/13)
0.812 (13/16)
38
9.62
7
0.978 (45/46)
0.719 (46/64)
0.923 (12/13)
0.812 (13/16)
39
8.92
6
0.978 (45/46)
0.719 (46/64)
0.923 (12/13)
0.812 (13/16)
40
10.25
5
0.978 (45/46)
0.719 (46/64)
0.923 (12/13)
0.812 (13/16)
41
8.34
4
0.960 (48/50)
0.781 (50/64)
0.923 (12/13)
0.812 (13/16)
42
9.45
Continuod on next page
16

---

Published in Transactions on Machine Learning Research (04/2026)
Table 9 continued from previons page
Train
Test
Precision
Coverage
Precision
Coverage
VI
Runtime
0.960 (48/50)
0.781 (50/64)
0.929 (13/14) 0.875 (14/16)
0.875 (14/16)
7.06
2
0.898 (53/59)
0.922 (59/64)
1.000 (16/16)
47
7.74
5 Conclusion and Future Work
In this paper, we introduce an RBML model that offers high interpretability and compliance for rule discovery. Our proposed model, OPDT, is based on an optimal decision tree, incorporating customizable rule structures based on a decision maker's needs. OPDT effectively identifies and describes significant patterns within reasonable time while adhering to desired rule structures and precision requirements. To enhance computational efficiency, develop three key techniques: Branching Structure Constraints (BSC), warmstart initialization with BSCCART, and branching priority orders. Our experimental results across 15 UCI datasets demonstrate that OPDT consistently finds high-quality rules that comply with given structure constraints. Moreover, the systematic feature decomposition approach not only improves computational efficiency but also provides valuable guidance toward optimal solutions through strategic feature grouping. This work contributes to rule-based machine learning by providing a flexible framework for discovering interpretable rules that balance solution quality, structure compliance, and computational time.
Despite the contributions presented in this paper, number of important challenges remain to be addressed in future work. First, even though OPDT can find an optimal pattern given specific rule structure and weight, it requires a decision maker to specify these parameters appropriately to identify representative pattern in data that generalizes beyond the training data. Second, while OPDT is designed to extract a single optimal pattern, it natural to extend to discover a set rules that represent data optimally, which remains an important direction for future work. Finally, by the inherent nature of optimization- methods, OPDT still has a scalability limitation on large-scale data. As demonstrated by the speedup achieved through BSC with different feature groupings, further research is needed develop systematic approaches for utilizing the BSC framework with prior knowledge tailored to specific datasets.
References
Sina Aghaci, Andrés Gómez, and Phebe Vayanos. Strong optimal classification trees. Operations Research, 2024.
Muhammad Aurangzeb Ahmad, Carly Eckert, and Ankur Teredesai. Interpretable machine learning in healthcare. In Proceedings of the 2018 ACM international conference on bioinformatics, computational biology, and health informatics, pp. 559 560, 2018
Zacharie Ales, Valentine Huré, and Amélie Lambert. New optimization models for optimal classification trees. Computers & Operalions Research, 164:106515, 2024.
Abdulalem Ali, Shukor Abd Razak, Siti Hajar Othman, Taiseer Abdalla Elfadil Eisa, Arafat Al-Dhaqm, Maged Nasser, Tusneem Elhassan, Hashim Elshafie, and Abdu Saif. Financial fraud detection based on machine learning: a systematic literature review. Applied Sciences, 12(19):9637, 2022.
Shadnaz Asgari, Fabien Scalzo, and Magdalena Kasprowicz. Pattern recognition in medical decision support. BioMed research international, 2019, 2019.
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106:1039 1082, 2017.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223 311, 2018.
Leo Breiman, Jerome H Friedman, Richard A Olshen, and Charles J Stone. Classifieation and regression Irees. Wadsworth, 1984.
17

---

Published in Transactions on Machine Learning Research (04/2026)
Jenna Burrell. How the machine 'thinks': Understanding opacity in machine learning algorithms. Big data & society, 3(1)2993317716222252 2016.
Jadzia Cendrowska. Prism: An algorithm for inducing modular rules. Knowledge Basedd Systems, 1:255 276, 1988.
Davide Chicco and Giuseppe Jurman. Heart Failure Clinical Records. UCI Machine Learning Repository, 2020. DOI:
C57289..
William W Cohen al. Fast effective rule induction. In Proceedings of the twelfth international conference on machine learning, pp. 115-123, 1995.
Murat Firat, Guillaume Crognier, Adriana F Gabor, Cor AJ Hurkens, and Yingqian Zhang. Column generation based heuristic for learning classification trees. Compulers & Operalions Research, 116:104866, 2020.
Jerome H. Friedman and Bogdan E. Popescu. Gradient directed regularization. September 2004. URL
https://apl semantccscholar wwwpaatteecccolaa..oooo/oo/ossss org/CorppsID:97778477 Technical Report.
Jerome Н Friedman and Bogdan E Popescu. Predictive learning via rule ensembles. The Annals of Applied Statistics, 2(3):916-955) 2008.
Johannes Fürnkranz and Gerhard Widmer. Incremental reduced error pruning, In Mochine learning proceedings 1994, pp. 70-77. Elscvier, 1994.
Claudio Gambella, Bissan Ghaddar, and Joe Naoum-Sawaya. Optimization problems for machine learning: A survey. European Journal of Operational Research, 290(3):807-822) -8800,88.--00 2021.
David Gil and Jose Girela. Fertility. https://doi.org// 11////100244//// C5701Z.
UCI Machine
Learning Repository, 2012.
DOI:
Nicolas Goix, Vighnesh Birodkar, Florian Gardin, Jean-Matthieu Schertzer, HOEBIN JEONG, manoj kumar, Alexandre Gramfort, Tim Staley, Tom Dupré la Tour, Boyuan Deng, C, Fabian Pedregosa, Lawrence Wu, Ariel Rokem, Kyle Jackson, and mrahim. sikkitleern-contiiee skope-rules v1.0.1. 12 2020. URL https:://do..org: org/ 1tt.////e22222/o.oo 4316671
doi:
Gail Gong. Hepatitis. UCI Machine Learning Repository, 1983. DOI: https://bbb.org//.2433////////
Oktay Günlük, Jayant Kalagnanam, Minhan Li, Matt Menickelly, and Katya Scheinberg. Optimal decision trees for categorical data via integer programming, Journal of global optimization, 81:233-200 2203,-66,,,00 2021.
Sara Hajian, Francesco Bonchi, and Carlos Castillo. Algorithmic bias: From discrimination discovery to lwire data mining. Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 2125-2126, 2016.
Hans Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994. DOL: http:////ooooor10.2/433333
M. M. Faniqul Islam, Rahatara Ferdousi, Sadikur Rahman, and Humayra Yasmin Bushra.
Early Stage Diabetes Risk Prediction.
UCI Machine Learning Repository, 2020.
DOI:
https://ddi..rrg. 0t.///0.244322 /CVGGHH.
Andras Janosi, William Steinbrunn, Marthias Pfisterer, and Robert Detrano. Heart Disease. UCT Machine Learning Repository, 1988. DOI: https://doi.org// 1oo.or//////1.3330 24432//522PXX.
Sun Jiang and Xu Xiao'li. Large rotating machinery fault diagnosis and knowledge rules acquiring basod on improved ripper. In 2009 Second International Conference on Intelligent Computation Technology and Automation, volume 2, pp. 549 552. IFFE,, 2009.
18

---

Published in Transactions on Machine Learning Research (04/2026)
Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Fie-Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. Advances in neural informalion processing systems, 30, 2017.
Markelle Kelly, Rachel Longjohn, and Kolby Nottingham. Uci machine learning repository, 2017. URL https://archiie..cet ics. eci.edu
Inna Kolyshkina and Simeon Simoff. Interpretability of machine learning solutions in public healthcare: The crisp-ml approach. Frontiers in big data, 4:660206, 2021.
Miron B Kursa and Witold R. Rudnicki. Feature selection with the boruta package. Journal of statistical software, 36:1-13, 2010.
Himabindu Lakkaraju, Stephen H Bach, and Jure Leskovec. Interpretable decision sets: A joint framework for description and prediction. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1675-1684, 2016.
Hyafil Laurent and Ronald L Rivest. Constructing optimal binary decision trees is up-complete. Information processing letters, 5(1):15 17, 1976.
Connor Lawless, Sanjeeb Dash, Oktay Gunluk, and Dennis Wei. Interpretable and fair boolean rule sets via column generation. Journal of Machine Learning Research, 24(229):1-50, 2023.
Wenke Lee, Salvatore J Stolfo, and Kui W Mok. A data mining framework for building intrusion detection models. In Proceedings of the 1999 IEEE symposium on security and privacy (Cat. No. 99CB36344), pp. 120-132. TEEE, 1999.
Max Little. Parkinsons. UCT Machine Learning Repository, 2007. DOT: https///bbiong//0224444,CCC
Joan Albert López- Vallveri,,,,, David Riano, and Antoni Collado. Increasing acceptability of decision trees with domain attributes partial orders. In Twentieth IEEE International Symposium on Computer- Based Medical Systems (CBMS'07), pp. 569-574. IEEE, 2007.
M. Lubicz, K. Pawelczyk, A. Rzechonek, and J. Kolodziej. Thoracic Surgery Data. UCI Machine Learning Repository, 2014. DOI: https://doiiorg///// 1rt.o..orr10.22432222 10.24432/C576ON. C5Z60N.
Scott Lundberg and Su-In Lee. unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017.
Jake Luo, Min Wu, Deepika Gopukumar, and Yiqing Zhao. Big data application in biomedical research and health care: a literature review. Biomedical informatics insights, 8:BII-33159, 2016.
Lorenzo Moja, Koren H Kwag, Thoodore Lytras, Lorenzo Bertizzolo, Linn Brandt, Valentina Pecoraro, Giulio
Rigon, Alberto Vaona, Francesca Ruggiero, Massimo Mangia, el al. Effectiveness of computerized decision support systems linked electronic health records: a systematic review and meta-analysis. American journal of public health, 104(12):e12-022, 2014.
W James Murdoch, Chandan Singh, Karl Kumbier, Reza Abbasi-Asl, and Bin Yu. Definitions, methods, and applications in interpretable machine learning. Proceedings of the National Academy of Sciences, 116 00l::207712220880 2019.
Kayvan Najarian, Kevin R. Ward, Shahram Shirani, et al. Biomedical signal and image processing for clinical decision support systems. Comput. Math. Methods Medicine, 2013:578320-1, 2013.
Géraldin Nanfack, Paul Temple, and Benoît Frénay. Constraint enforcement on decision trees: A survey. ACM Computing Surveys (CSUR), 54(10s))1-36,, 2022.
Rafel Palliscr-Sans. Rrules: An improvement of the rules rule-based classifier.
arxio preprint
XxXi:2106.072990 2021.
19

---

Published in Transactions on Machine Learning Research (04/2026)
DT Pham and MS Aksoy. Rules: A simple rule extraction system. 59-65, 1995.
Expert Systems with Applications, 8(1):
Ross Quinlan. Statlog (Australian Credit Approval). UCI Machine Learning Repository, 1987. DOL:
Bendi Venkata Ramana, M. Surendra Prasad Babu, and Nagasuri Bala Venkateswarlu. ILPD (Indian Liver Patient Dataset). UCI Machine Learning Repository, 2012. DOL: https///doi.org/1.22455533 CCDD02C
Susan Rea, Jyotishman Pathak, Guergana Savova, Thomas A Oniki, Les Westberg, Calvin E. Beebe, Cui Tao, Craig G Parker, Peter J Haug, Stanley M Huff, et al. Building robust, scalable and standards-driven infrastructure for secondary use of ehr data: the sharpn project. Journal of biomedical informatics, 45(4): 763 113-771, 2012.
L. Rubini, P. Soundarapandian, and P. Eswaran. Chronic Kidney Disease. UCI Machine Learning Repository, 2015. DOI: https://doi.org/iIe 1tt///00.24422/55 /C5G000..
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instcad. Nature machine intelligence, 1(5):206-215 225, 2019.
Cyuthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong. Interpretable machine learning: Fundamental principles and 10 grand challenges. Statistic Surveys, 16:1 85, 2022.
Steven Salzberg. Echocardiogram. http://oorrrr112244///5//555//
UCI Machine
Learning Repository, 1988.
DOI:
Vincent Sigillito. Pima indians diabetes database, 1990. URL
www.la.gg.... com coom/ddtaasts/ucinnll
pima-indians- diabetes-datatateeeeeeeeeee-ee-e and Digestive and Kidney Discases.
Donor of database, Originally from: National Institute of Diabetes
Guolong Su, Dennis Wei, Kush R Varshney, and Dmitry M Malioutov. Learning sparse two-level boolean rules. In 2016 IEEE 26th International Workshop Machine Learning for Signal Processing (MLSP), pp. 1-6. IEEE, 2016.
Sieco Verwer and Yingqian Zhang. Learning optimal classification trees using a binary linear program formulation. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 1625-1632 2019.
Giulia Vilone and Luca Longo. Notions of explainability and evaluation approaches for explainable artificial intelligence. Information Fusion, 76:89 106, 2021.
Tong Wang, Cynthia Rudin, Finale Doshi-Velez, Yimin Liu, Erica Klampfl, and Perry MacNeille. A bayesian framework for learning rule sets for interpretable classification. Journal of Machine Learning Research, 18 (70):1 37, 2017.
William Wolberg, Olvi Mangasarian, Nick Street, and W. Street. Breast Cancer Wisconsin (Diagnostic). UCT Machine Learning Repository, 1995. DOT: https:/ (ttpii.orr/1..224///CC//
I-Cheng Yeh. Blood Transfusion Service Center. UCI Machine Learning Repository, 2008. DOL:
https///do..rrg/1..244422 wtw.org///11..... C5GS39.
20

---

Published in Transactions on Machine Learning Research (04/2026)
Appendices
A OPDT and Benchmark Methods Performance
Table 10: OPDT and Benchmark Methods Performance on Training Data (80%) and Test Data (20%): mean (+
standard deviation) across 10 random data splits
Training Data (80%)
Test Data (20%)
Dataset
Rantime
Precision
Coverage
VI
Precision
Coverage
VI
Australian
OPDT
602.00
0.963
0.411
135.600
0.940
0.426
22.800
(82.99977
(+0.007)
(+0.018)
(#11.499))
(+0.028)
(+0.039)
(#:15.091)
BSCCART
0.25
0.957
0.442
130.500
0.937
0.456
21.700
(10.175)
(1000077
(10.015)
(114.2254)
(10.023)
(100.40)
(113.598)
RSCRULES
0.04
0.943
0.462
103.400
0.933
0.478
20.600
(+0.011)
(+0.006)
(+0.006)
(+14.010)
(+0.023)
(+0.026)
(+14.010)
BRS
0.36
0,950
0.453
116.720
0.934
0.470
20,930
(+0.009)
(#0.006)
(+0.020)
(+13.677)
(#0.022)
(#0.029)
(+136633)
IDS
0.22
1.000
0.070
36,300
0.955
0.069
5,000
(+0.005)
(+0.000)
(+0.028)
(+14.863)
(+0.065)
(+0.032)
(+5.598)
IREP
0.08
0.943
0.462
103.400
0.811
0.315
-41.303
(+0.001)
(#0.006)
(#0.006)
(+14.010)
(#0.043)
(#0.089)
(#227433)
PRISM
3.03
1,000
0.085
44,200
0.963
0.085
8,200
(10.133)
(1000000)
(10.007)
(133584)
(100078)
(10.025)
(18,135)
Ripper
2.01
0.952
0.428
114.384
0.826
0.106
-8,260
(+59924)
(10.006)
(10.014)
(111.649)
(100063)
(10.051)
(13.715)
German
-PPT
749.82
0.936
0,225
60.000
0,883
0,231
-7.900
(+370.714)
(+0.011)
(+0.085)
(+12.481)
(+0.020)
(+0.098)
(+10660))
BSCCART
0.20
0.920
0.315
49.800
0.896
0.326
-1.800
(+0.126)
(+0.008)
(+0.023)
(+18.920)
(+0.027)
(+0.043)
(111.498)
RSCRULES
0.10
0.938
0.205
57.800
0.895
0.199
-4,200
(100.06)
(10.012)
(10,087)
(113.815)
(100032)
(10.094)
(1100696)
BRS
0.53
0.908
0.349
16.266
0.901
0.361
-0.712
(+0.064)
(+0.010)
(+0.017)
298)
(#0.029)
(+0.030)
(1:20.104)
IDS
0.25
1.000
0.024
19.200
0.950
0.019
1.800
(10.009)
(10.000)
(10.004)
(13,360)
(10.112)
(100007)
(14..077)
IREP
0.09
0.867
0.209
-32,202
0.801
0.266
-37.322
(+0.002)
(+0.014)
(+0.043)
(+13.316)
(#0.023)
(+0.051)
(+137754)
PRISM
7.20
1.000
0.025
20.100
0.949
0.024
0.800
(+0.112)
(+0.000)
(+0.003)
(+2.079)
(+0.086)
(+0.013)
(+4.803)
Ripper
0.17
0.925
0,256
47.618
0.917
0,207
10.524
(+0.001)
(+0.010)
(+0.045)
(#17.287)
(+0.017)
(+0.095)
(+8.096)
Blood Transfusion
-OPDT
90.70
0.948
0.220
51.200
0.892
0.220
-6.500
(111.522)
(10.014)
(10.055)
(110.443)
(10.017)
(10.072)
(114))22)
BSCCART
0.13
0.955
0.195
45.500
0.889
0.195
-6.600
(+0.004)
(+0.023)
(+0.085)
(0...88)
(+0.025)
(+0.095)
(+15.079)
RSCRULES
0.02
0.963
0.088
24.000
0.841
0.087
-6.300
(+0.006)
(+0.021)
(+0.044)
(+5.416)
(+0.125)
(+0.053)
(+11.046)
BRS
0.23
0.775
0.922
-583.396
0.771
0.921
-299.236
(+0.042)
(+0.043)
(+0.14
(+1853377
(+0.044)
(+0.151)
(#:4.622)
IDS
0.23
1.000
0.024
12,200
0.552
0.023
-13.300
(+0.006)
(+0.000)
(+0.007)
(+3.676)
(+0.337)
(+0.012)
(+11.605)
IREP
0.04
0.931
0.085
10.720
0.785
0.124
-28.306
(100.001)
(10.025)
(10.012)
(111.740)
(10.040)
(10.018)
(11002668
PRISM
0.53
0.993
0.034
15.
0.707
0.036
-10.100
(+0.032)
(+0.015)
(#0.013)
(13.900)
(+0.263)
(+0.019)
(1:4.977)
Ripper
0.07
0.959
0.071
18.166
0.687
0.112
-31.678
(L0.000)
(L0.022)
(10.0233
(18.388)
(10.039)
(10.0554)
(114.771)
Breast Cancer
-OPDT
790.97
0.992
0.549
230.000
0.979
0.537
48.200
(+255.965) (6)
(#0.004)
(#0.013)
(+8.055)
(#0.018)
(#0.021)
(+10.185)
-BSCCART
7.25
0.966
0.617
183.500
0.958
0.602
38.600
(100.105)
(10.014)
(10.028)
(1.29.289)
(10.026)
(10.041)
(1116460)
Continued on next page
21

---

Published in Transactions on Machine Learning Research (04/2026)
Table 10 continued from previous page
Training Data (80%)
Test Data (20%)
Datasel
Runtime
Precision
Coverage
VI
Precision
Coverage
VI
RSCRULLES
0.06
0.971
0,386
124.600
0.962
0.365
25.600
(10.003)
(1.0.007
(10.029)
(1220.35)
(10..024)
(10.043)
(19.698)
BRS
0.59
1,000
0.251
113.998
0.982
0.235
21.216
(+0.092)
(+0.000)
(+0.025)
(+11.555)
(+00022)
(+0.045)
(+5.170))
IDS
0.22
1,000
0.245
111.700
0.982
0.231
21.300
(+0.027)
(#00000)
(#0.037)
(+:16.44))
(+0.031)
(+0.048)
(+7.973)
IREP
0.39
1,000
0,111
50.514
0.975
0,110
10.041
(+0.001)
(+0.000)
(+0.007)
(+3.355)
(+0.030)
(+0.014)
(+4.096)
PRISM
2.95
1,000
0,251
114.300
0.995
0.239
25.300
(+0.169)
(#0.000)
(#0.024)
(+:10,70)
(+0.017)
(+0.045)
(#4.762)
Ripper
0.49
1,000
0.111
50.502
0.993
0.100
10.618
(10.003)
(10.000)
(10.007)
(13.309)
(10.008)
(10.023)
(13.265)
Chronic Kidney
-OPDT
6.60
1.000
0.577
99.200
0.966
0,600
16.800
(=10.083)
(#0.000)
(#0.019)
(+33327)
(#0.021)
(+0.041)
(#4.237)
BSCCART
0.24
0.996
0.504
98.100
0.967
0.619
17.600
(+0.023)
(+0.005)
(+0.006)
(+4.433)
(+0.030)
(+0.025)
(+7.947)
RSCRULES
0.02
1.000
0.308
52.900
1.000
0.303
13.100
(000000)
(#0,000)
(#0.009)
(+1,544)
(#0.000)
(+0.035)
(+1.544)
BRS
0.33
0.999
0.276
46.305
0.982
0.276
9.332
(10.066)
(10.002)
(10.014)
(100.944)
(10.008)
(10..09)
(10.879)
IDS
0.19
1,000
0.288
49.600
0.983
0.281
10.100
(+0.003)
(+0.000)
(+0.017)
(+2.914)
(+0.053)
(+0.040)
(+6.500)
IREP
0.13
0.984
0.551
79.096
0.996
0.488
19.834
(10.001)
(10.003)
(10.012)
(13.668)
(10.004)
(10.046)
(11.621)
PRISM
0.29
1.000
0.308
52.900
1.000
0.305
13.100
(+0.135)
(+0.000)
(+0.009)
(+1.524)
(+0.000)
(+0.035)
(+1.54
Rippeer
0.15
0.987
0.563
84.004
0.998
0.520
21.796
(+0.001)
(+0.002)
(+0.006)
(+2.406)
(+0.002)
(+0.044)
(+1.456)
Early Stage Diabetes
OPDT
3.71
0.999
0.374
153.400
0.996
0.386
38.100
(+3.314)
(+0.004)
(+0.012)
(+3.565)
(+0.012)
(+0.045)
(+3.725)
BSCCART
0.03
1,000
0.369
153.400
1,000
0.381
39.600
(10.0000
(10.000)
(10.0009
(13.565)
(10.000)
(10.004))
(13.565)
RSCRULES
0.02
0.965
0.448
121.200
0.968
0.450
31.800
(+0.009)
(+0.006)
(+0.008)
(+10.163)
(+0.023)
(+0.032)
(+10.163)
BRS
0.54
1,000
0.365
151.830
1,000
0.369
38.314
(+0.086)
(#0.000)
(#0.009)
(#3.751)
(#0.001)
(#0.033)
(#3.537)
IDS
0.21
1,000
0.287
119.300
0.995
0.271
27,200
(+00003)
(+0.000)
(+0.067)
(+27.745)
(+0.015)
(+0.082)
(+9.953)
IREP
0.04
0.966
0.437
118.158
0.970
0.381
26.444
(+0.001)
(#0.006)
(#0.019)
(+:2.140)
(#0.017)
(#0.063)
(+7.322)
PRISM
0.63
1.000
0.218
90.600
1.000
0.231
24.000
(10.059)
(10.0000)
(10.056)
(12232001)
(10.0000
(10.062)
(16.446)
Ripper
0.08
0.999
0.371
151.746
0.999
0.375
38.740
(+0.002)
(+0.001)
(+0.010)
(+3.258)
(+0.001)
(+:0.03)
(+3.551)
Echocardiogram
-PDTT
0.80
0.988
0.430
18.100
0.762
0.369
-22200
(+0.618)
(+0.020)
(+0.094)
(+4.818)
(+0.317)
(+0.191)
(+6.477)
BSCCART
0.07
0.961
0,500
14.500
0,886
0.492
-1.600
(+0.013)
(#0.036)
(#0.040)
(+7.990)
(#0.136)
(#0.126)
(#9.477)
RSCRULES
0.01
0.986
0.263
9,900
0.598
0.246
-2.800
(10.001)
(10.022)
(10.163)
(14.886)
(10.430)
(10.248)
(15,138)
BRS
0.24
0.937
0.429
18.
0.782
0.428
-8.982
(+0.035)
(#0.041)
(+0.118)
(+15.676)
(#00110)
(#0.1174
(#3.871)
IDS
0.18
1.000
0.153
7,500
0.831
0.215
-2,200
(10.003)
(10.000)
(10.036)
(11,780)
(10.171)
(10..149)
(13.994)
IREP
0.05
0.949
0.267
4.307
0.935
0.229
-0.102
(+0.001)
(+0.032)
(+0.093)
(+5.100)
(+0.087)
(+0.095)
(+3.682)
PRISM
0.18
1.000
0.145
7,100
0.500
0.131
-2,300
(+0.016)
(#0.000)
(#0.095)
(+4.6544
(+0.456)
(+0.115)
(#4.644)
Ripper
0.07
0.966
0,223
5,740
0.894
0.166
-1.325
(100001)
(10.0077)
(10.
(1:4.441)
(10.065)
(10.080)
(12.444)
Fertility
Continued on next page
22

---

Published in Transactions on Machine Learning Research (04/2026)
Table 10 continued from previous page
Training Data (80%)
Test Data (20%)
Datasel
Runtime
Precision
Coverage
VI
Precision
Coverage
VI
OPDT
0.26
1,000
0,429
34.300
0.971
0,480
6,600
(10.132)
(10.000)
(10.024)
(11.947)
(10.009)
(10.098)
(144.477)
BSCCART
0.02
1,000
0.429
34.300
0.971
0,480
6.600
(+0.003)
(+0.000)
(+0.024)
(+1.947)
(+00049)
(+0.098)
(#:44777)
RSCRULES
0.01
0.969
0,342
17.400
0.912
0,405
0,100
(+0.001)
(+0.024)
(+0.095)
(+3.950)
(#0.072)
(+0.119)
(#5.021)
BRS
0.27
0.997
0,259
18.713
0,910
0.293
1,025
(+0.025)
(+0.006)
(+0.047)
(+4.0000
(+0.075)
(+0.074)
(+3.001)
IDS
0.19
1,000
0,254
20,300
0.965
0.255
3,100
(+0.003)
(+0.000)
(+0.034)
(+2.710)
(+0.082)
(+0.096)
(#3.604
IREP
0.03
0.958
0.375
16.192
0.954
0.371
3,577
(10.001)
(L0.019)
(10.053)
(L4,380)
(10.024)
(10.046)
(11.860)
PRISM
0.13
1,000
0.188
15.000
0.976
0.290
3.800
(+0.029)
(+0.000)
(+0.037)
(+2.981)
(#0.052)
(+0.115)
(#3.327)
Rippee
0.04
0.969
0.333
17.182
0.876
0.206
-1.999
(10.001)
(10.0009
(10.044)
(13.462)
(10.052)
(1001000)
(12.228)
Heart Disease
-OPTT
524.81
0.979
0.165
29.200
0,800
0.180
-9.200
(#634.168)
(+0.021)
(#0.047)
(+3.155)
(#0.063)
(#0.079)
(#5.160)
BSCCART
0.14
0.926
0.269
16.800
0.944
0,250
5,000
(10.019)
(10.011)
(10.021)
(166339)
(10.074)
(10.058)
(113.199)
RSCRULES
0.03
0.969
0.137
20.500
0.929
0.118
-0.900
(+0.005)
(+0.020)
(+0.052)
(+3.171)
(+0.097)
(+0.064)
(+7.937)
BRS
0.36
0.949
0,210
15.010
0.928
0,200
0.636
(10.049)
(10.037)
(10.079)
(1117.335)
(10.089)
(10.081)
(111.493)
IDS
0.20
1.000
0.064
15.100
0.955
0.068
2.100
(+0.002)
(+0.000)
(+0.015)
(+3.510)
(+0.096)
(+0.020)
(+4.175)
IREP
0.06
0,903
0.224
-5.888
0.827
0,342
-19.485
(+0.001)
(+0.020)
(+0.039)
(+11.122)
(+0.043)
(+0.025)
(+10.521)
PRISM
1.01
1,000
0.056
13,300
0.922
0.053
0,200
(40.040)
(+000000
(40.008)
(+1.889)
(40.130)
(+0.022)
(444.442)
Ripper
0.10
0.944
0.163
13.592
0.852
0.208
-4.524
(+0.001)
(+0.010)
(+0.046)
(+5.094)
(+0.042)
(+0.037)
(+5.392)
Heart Failure
OPDT
729.32
0.982
0.331
62.100
0.935
0.335
5.100
(+551.965)
(+0.017)
(+0.088)
(+5.859)
(+0.045)
(+0.124)
(+9.036)
BSCCART
0.36
0.927
0.513
29.600
0.884
0.530
-1.200
(+0.008)
(#0.012)
(#0.178)
(+11.987)
(#0.053)
(#0.178)
(=12.13))
RSCRULES
0.03
0.975
0.097
16.300
0.817
0.097
-5.200
(+00004)
(+0.023)
(+0.028)
(+:4,296)
(+0.114)
(+0.064)
(+4.211)
BRS
0.30
0.953
0.238
-41.974
0.782
0.239
199.254
(+0.062)
(#0.096)
(+0.318)
(-1260072
(#0.106)
(+0.333)
(#:30173)
IDS
0.19
1,000
0.081
19.400
0.975
0.080
3.800
(10.003)
(10.0000
(10.008)
(12.011)
(10.079)
(10.029)
(13.853)
IREP
0.07
0.975
0.103
17.578
0.823
0.123
-8.545
(+0.002)
(+0.018)
(+0.012)
(+5.046)
(+0.064)
(+0.037)
(18.333)
PRISM
0.82
1,000
0,087
20.700
0.955
0.067
1,000
(10.078)
(10.000)
(10.012)
(12.908)
(10.096)
(L0.039)
(14.944)
Ripper
0.11
0.994
0.096
21.412
0.792
0.088
-6.730
(+0.002)
(+0.012)
(+0.006)
(+3.611)
(+0.063)
(+0.025)
(+3.177)
Hepatitis
-OPDT
0.82
0.998
0.675
42,200
0.907
0.656
0.500
(L0.727)
(10.006)
(10.059)
(13,393)
(10.082)
(10.1107)
(17.7992)
BSCCART
0.10
0.986
0.736
40.
0.885
0.737
-2.200
(+0.028)
(#0.013)
(+0.053)
(+3.755)
(#00069)
(+00121))
(#8.804)
RSCRULES
0.01
0.947
0.664
17.500
0.873
0.662
-5.400
(10.002)
(10.024)
(10.198)
(.44.233)
(10.091)
(10.2338
(18..499)
BRS
0.27
1.000
0.458
29.314
0.962
0.446
3.429
(+0.022)
(+0.000)
180)187)
(11499
(+00049)
(+0.116)
(#3.645)
IDS
0.19
1.000
0.391
25.000
0.915
0,381
1.100
(+0.027)
(#0.000)
(+0.085)
(+5.416)
(+0.133)
(+0.133)
(+7.310)
IREP
0.06
0.967
0.646
26.330
0.970
0.475
4.554
(1.0.00))
(10.014)
(10.054)
(144966)
(10.020)
(10.113)
(+2.280)
PRISM
0.15
1.000
0.341
21.800
0.881
0.294
2.700
(+0.017)
(#0.000)
(#0,133)
(+8.496)
(#0.312)
(#0.213)
(+1.889)
Continued on next page
23

---

Published in Transactions on Machine Learning Research (04/2026)
Table 10 continued from previous page
Training Data (80%)
Test Data (20%)
Datasel
Runtime
Precision
Coverage
VI
Precision
Coverage
VI
Ripper
0.07
0.973
0.615
28.004
0.988
0,430
6.664
(10.001)
(10.012)
(10.045)
(14.501)
(10.0244
(10.174)
(22.723)
Indian Liver Patient
-OPTT
999.70
0.981
0.221
82.500
0.948
0.239
12.700
(+224.994)
(+0.008)
(#0.024)
(+:10066)
(+0.0433
(+0.028)
(+:10843)
BSCCART
0.61
0.942
0.297
54.500
0.907
0.313
2.300
(10.015)
(10.022)
(10.040)
(124.968)
(10.036)
(10.056)
(L13.679)
RSCRULES
0.04
0.996
0.044
19.600
0.986
0.045
4,200
(+0.016)
(+0.013)
(#0.006)
(+2.716)
(+0.045)
(+0.013)
(+2.860)
BRS
0.27
0.731
0.902
-790.932
0.730
0.896
-198.454
(L0.043)
(1.0.031)
(10.088)
(1996273)
(10.032)
(10.087)
(124.312)
IDS
0.21
1.000
0.038
17.400
0.975
0.039
3.500
(+0.003)
(+0.000)
(+0.005)
(+2.366)
(+0.079)
(+0.017)
(+3.866)
IREP
0.09
0.995
0.104
42.624
0.959
0.113
7.045
(+0.002)
(+0.005)
(#0.008)
(+7.690)
(+0.021)
(#0.021)
(+5.418)
PRISM
2.98
1.000
0.039
18.100
1.000
0.038
4,400
(+0.054)
(+0.000)
(+0.006)
(+2.923)
(+0.000)
(+0.022)
(+2.591)
-Ripper
0.14
0.999
0.101
46.088
0.775
0.064
-7.918
(+0.001)
(#0.001)
(#0.001)
(+0.820)
(#0.060)
(#0.014)
(#3.601)
Parkinsoms
OPDT
863.11
0.999
0.532
82.000
0.919
0.508
2.800
(+340.952)
(+0.003)
(+0.032)
(+4.447)
(+0.052)
(+0.077)
(+9.682)
BSCCART
1.77
0.977
0.597
70,200
0,884
0.621
-5.800
(+0.116)
(+0.018)
(#0.077)
(+10.633)
(+0.070)
(+0.109)
(+18.207)
RSCRULES
0.03
0.976
0,240
28.500
0.990
0.246
8,600
(+0.007)
(+0.009)
(+0.014)
(+3.689)
(+0.032)
(+0.058)
(+3.777)
BRS
0.37
1.000
0,335
52.247
0.978
0,315
9.064
(+0.061)
(+0.000)
(+0.058)
(+9.034)
(+0.027)
(+0.073)
(+4.337)
IDS
0.19
1,000
0.163
25.400
0.876
0.154
0.000
(10.0044)
(10.0000
(10.033)
(15.103)
(10.166)
(10.091))
(1443977)
IREP
0.35
0.998
0.116
17.560
0.983
0.120
4.056
(+0.002)
(+0.003)
(+0.009)
(+1.554)
(+0.012)
(+0.018)
(+0.831)
PRISM
1.56
1,000
0.171
26.700
0.954
0.185
3,200
(10.140)
(10.000)
(10.030)
(14.668)
(10.062)
(10.0677
(13.910)
Ripper
0.41
1,000
0.117
18.164
1.000
0.116
4.599
(+0.003)
(+0.000)
(+0.010)
(+15115)
(+0.001)
(+0.018)
(+0.687)
Pima Indians Diabetes
-OPTT
1047.67
0.979
0.187
89.100
0.925
0.201
4.900
(176.896)
(10.012)
(10.032)
(166590)
(10.049)
(10.047)
(.112.758)
BSCCART
0.76
0.922
0.297
36.200
0.889
0.309
-8.400
(+0.010)
(+0.039)
(00.
(+:46.492)
(#0.038)
(+0.117)
(#:21.287)
RSCRULES
0.07
0.962
0.105
37.400
0.953
0.097
4.900
(10.003)
(10.016)
(10.041)
(18.897)
(10.047)
(10.055)
(1773440)
BRS
0.35
0.727
0.859
-920.728
0.722
0.863
-237.996
(+0.025)
(+0.006)
(+0.022)
(+:6.483)
(+0.022)
(+0.037)
(+33.960)
IDS
0.22
1,000
0.035
21.500
0.963
0.037
3.700
(+0.008)
(+0.000)
(+0.010)
(+6.042)
(+0.078)
(+0.019)
(+5225
IREP
0.08
0.938
0.100
22.686
0.837
0.093
-9.601
(+0.001)
(+0.013)
(+0.005)
(+6.723)
(+0.026)
(+0.016)
(+3.598)
PRISM
3.35
1,000
0.037
22.800
0.924
0.049
1.600
(37)137)
(+0,000)
(#0.015)
(+8.942)
(#0.107)
(+0.021)
(#8.859)
Ripper
0.13
0.980
0.064
26.876
0.802
0.056
-8.958
(10.003)
(10.015)
(10.019)
(15.161)
(10.057)
(10.020)
(14.647)
Thoracic Surgery -OPDT
133.21
0.949
0,264
46.200
0.855
0.247
-9,800
++3275888
(#0.012)
(#0.058)
(+550055)
(#0.079)
(#0.037)
(+16.433)
BSCCART
0.10
0.991
0.064
20.200
0.521
0.066
-3.800
(+0.047)
(+0.015)
(#0.052)
(+15.483)
(#0.449)
(+0.054)
(+44392)
RSCRULES
0.02
0.937
0,244
31.700
0.867
0,214
-4,900
(+0.006)
(#0.010)
(#0.084)
(+7.009)
(#0.039)
(+00091)
(+:13.04)
BRS
2.13
0.898
0.706
-21.068
0.863
0.717
-27.672
(15.802)
(10.015)
(10.127)
(1145335)
(10.023)
(10.143)
(1 (1 (1122022
IDS
0.21
1.000
0.038
14.400
0.933
0.031
-0.100
(+00003)
(+0.000)
(+0.011)
(14.169)
(+0.200)
(+0.022)
(+8.950)
Coutinued on next page
24

---

Published in Transactions on Machine Learning Research (04/2026)
Table 10 continued from previous page
Training Data (80%)
Test Data (20%)
Datasel
Runtime
Precision
Coverage
VI
Precision
Coverage
VI
IREP
0.0G
0.902
0.322
-2.136
0.862
0,445
-12.724
(10.002)
(10.014)
(10.049)
(1188660)
(10.016)
(10.072)
(144.690)
PRISM
1.70
1,000
0.045
16,900
1,000
0.048
4.500
(+0.090)
(#0.000)
(+0.005)
(+1.912)
(#000000
(+0.020)
(+1.841)
Ripper
2.16
0.914
0,250
26.356
0,835
0.130
-8,167
(+6.556)
(+0.023)
(#0.044)
(+:102677)
(#0.069)
(+0.050)
(#5.930)
B
Feature Grouping Using ML-Based Feature Importance
As concrete demonstration that prior information extracted from MT can help feature grouping, we select the German dataset, which is the largest dataset among those in Table 3 Suppose that we need to find a pattern complying with the {categorical]- [numerical) structure. First, feature importance is extracted from a GBM (LGBM)) model (Ke et al. 2017) trained with 1,000 boosting iterations. Figure 4 presents the feature importance scores evaluated by two complementary metrics: information gain and split count. Based on this prior information, Figure to define two feature groups. Table 11 shows the VI improvement over time with runtime limit of 600 seconds. As shown in Table 11 OPDT with LGBM reaches the optimal VI of 41.0 in 5 seconds, whereas OPDT Only reaches the same optimal VI in 23 seconds, and reduces the total runtime to prove optimality from 446.4 seconds to 90.8 seconds, which is a fivefold reduction runtime. This experiment demonstrates a heuristic approach in which an ML method is used to extract feature importance rankings to define feature groups for the BSC framework.
select the top six features from each metric, as highlighted in red in
Numerical Features: 'A2', 'AS', 'A8', 'A11', 'A13', 'A16', 'A18' Categorical Features: 'A1', 'A3', 'A4', 'A6', 'A7', 'A9', 'A10', 'A12', 'A14', 'A15', 'A17', 'A19', 'A20'
renture Imp contelgantt
A14
170.201
ALS
123
435
A28
Testore erpertance
festure imgor tancelsplit
144
612
400
Figure 4: Feature grouping using LGBM feature importance (gain and split) on the German dataset. Features are ranked by information gain (top) and split count (bottom). The numerical and categorical features within the top six (highlighted in red) are selected for the (cam)-(num) rule.
25

---

Published in Transactions on Machine Learning Research (04/2026)
Table 11: VT improvement over time on the German dataset for the {cat)-(num) rule. OPDT with LGBM denotes OPDT using feature groups selected by LightGBM feature importance, while OPDT Only denotes OPDT without feature grouping. Each row shows the step at which VI improves and the corresponding elapsed time in seconds.
OPDT with LGBM
OPDT Only
Step
VI
Time (sCc)
VI
Time (scc)
0.0
0
0.0
2
1.0
2.0
3
2.0
5.0
4
4.0
2
14.0
5
5
5.0
2
20.0
21
6
12.0
3
41.0
23
7
41.0
Optimal
41.0
90.8
41.0
446.4
26


Reviews:
[{"review_id": "GcYLuCBy1e", "reviewer": "Reviewer_by7T", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**summary**\n\nThis paper proposes an optimal classification pattern discovery method using structural constraints based on prior knowledge.\nThe method is built on the concept of optimal decision trees and is solved using Mixed-Integer Programming (MIP).\nThe prior knowledge, which consists of grouping related features and applying length constraints, is designed to be intuitive for humans and helps reduce the search space.\nIn the experiments, the proposed method is compared with conventional pattern discovery techniques using various datasets, and its effectiveness is discussed.\n\n**strengths**\n* Previous literature on rule-based machine learning and optimal decision trees is well-summarized.\n* A new pattern evaluation metric, which was not present in conventional research, is proposed.\n* The approach is intuitive and clear.\n\n**weakness**\n* The experimental setup and discussion are insufficient for the claims made.\n* The proposed method lacks scalability.\n* The proposed method can only discover a single pattern.", "claims_and_evidence_yn": "No", "claims_explanation": "While the basic goals and ideas of this paper are clearly supported, the discussion and experiments are insufficient for some of the specific claims. Details are provided in the recommendations under **Requested Changes**.", "audience_yn": "Yes", "audience_explanation": "Since pattern discovery is a fundamental element of machine learning and the paper also addresses the recent trend of optimal decision trees, I believe there are a sufficient number of interested readers.", "requested_changes": "**recommendation**\n* While the authors claim that feature grouping can be automated using ML, the experiments only employ simple numerical-categorical grouping. Although this may be due to scalability issues, if the authors state that automation is possible, they should provide at least one specific example of an automated feature grouping process and conduct experiments using it.\n* The parameter $w$ used in the experiments does not appear to be explicitly stated. Furthermore, a sensitivity analysis should be performed to show how the coverage and precision of the rules obtained by the proposed method change with variations in $w$.\n* Table 8 shows not only the superior aspects of OPDT but also that it can easily overfit on training dataset; however, there is no mention of this.\n\n**strengthen**\n* The persuasiveness of the proposed method would be enhanced by providing visual examples showing how the patterns obtained by the proposed method differ from those of competing methods.\n* Since the proposed method finds only a single pattern, it is often insufficient as a classifier. In general, it is desirable to extract multiple different patterns. This could be easily achieved by repeatedly applying the proposed method to uncovered samples; do the authors envision such a use case? If so, the addition of relevant experiments is desired.", "broader_impact_concerns": "This paper has no ethical concerns.", "additional_comments": "* Since there is no mention of structural constraints (prior knowledge) in the title or the abstract, it is confusing while reading the main text.\n* Regarding the end of the second paragraph in Section 2.1, a technical reference is cited for a practical topic. Please verify if this is the correct citation.\n* Is the third sentence of the third paragraph in Section 2.1 a typo (prefect -> perfect)?", "extra_scores": {}, "extra_text": {}}, {"review_id": "y7tK4u5o6l", "reviewer": "Reviewer_ZhSs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes Optimal Pattern Detection Trees (OPDT), a rule-based binary classification model that uses mixed integer programming (MIP) to discover an optimal symbolic pattern in data.\nOPDT aims to find a rule that maximizes coverage of the target pattern while controlling misclassification.\nA key contribution is the ability to enforce rule structures to meet user requirements, while still providing optimality guarantees from the underlying optimization formulation.\nExperiments on a lot of datasets show that OPDT can produce high-quality, structure-compliant rules within reasonable runtime.\n\n## Strengths:\n1. Proposed model supports explicit structural constraints on rules, aligning outputs with prior knowledge and practical requirements.\n2. Unlike heuristic rule learners, OPDT provides to optimal solutions under its formulation.\n3. Experiments on 15 UCI datasets show that the proposed method is competitive across a wide range of healthcare and finance datasets.\n\n## Weaknesses:\n1. The MIP formulation is somewhat difficult to follow and validate, because it relies on a large number of inequality constraints and variables, which makes it hard for the reader to understand and verify the correctness of the encoding.\n2. The paper includes only limited theoretical discussion of the MIP formulation, such as how the number of decision variables and constraints scales with the number of instances or features, which makes it difficult to assess the scalability of this MIP problem from a theoretical perspective.\n3. Although the paper evaluates OPDT on many datasets, most of the benchmarks appear to be small in both the number of instances and the number of features, so the experiments are only somewhat convincing in demonstrating the method's effectiveness on larger-scale settings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Majority of the claims suggested in this paper have been experimentally verified. However, point 3 under the above weaknesses raises a slight concern about the credibility of the experimental results.", "audience_yn": "Yes", "audience_explanation": "Yes, I think this is definitely an interesting line of work that would interest the operations research community as a potential application area, as well as the machine learning community, especially researchers working on explainable AI and HCI.\nThis is because it enables the design and selection of rules that are robust in practical explanation and operational processes.", "requested_changes": "Especially for point 1 under the above weaknesses, please consider whether improvements are possible from the following perspectives.\n\n## For point1: \n- The studies cited in this paper ([1][2]), as well as others such as [3], convert decision tree learning into ILP or MIP formulations. There appear to be many commonalities in the constraints used in these papers when formulating MIPs. If such commonalities exist, this reviewer suggests the authors mention them, and at the same time, specify the particular constraints that are either additionally introduced or modified in this paper. I belive that it will improve readability.\n\n> [1] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106:1039–1082, 2017.\n\n> [2]Verwer, S., & Zhang, Y. Learning Optimal Classification Trees Using a Binary Linear Program Formulation. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1625-1632, 2019.\n\n> [3] Aghaei, S., Azizi, M. J., & Vayanos, P. (2019). Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1418-1426.\n\n- Constraint (4) and (5) seem to represent rules by activating the rightmost leaf node when the internal node $t$ does not split. If this understanding is correct, this convention for representing it in MIP should be described before.\n- Is Constraint (15) necessary? It seems that the variable constraint (27) is equivalent to this constraint.\n\n## Minor:\n- (p3, second paragraph) .. to extract rules from data. Frist, Rules Extraction => to extract rules from data. First, Rules Extraction", "broader_impact_concerns": "None", "additional_comments": "- Is it possible to extend the formulation to find top-k rules, rather than just a single optimal rule?\n- I feel that there are many situations where it is useful to find a small number of multiple rules, but how practical is it to find just a single rule?\n- (I have confirmed the revised paper, which was submitted on 21 February 2026.)", "extra_scores": {}, "extra_text": {}}, {"review_id": "vNRJaxOR1h", "reviewer": "Reviewer_83EL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript introduces a rule-based method for binary classification termed the Optimal Pattern Detection Tree (OPDT). OPDT is based on a *structure-constrained* approach, where the features form multiple feature groups, and each node in the decision tree can only query features in a specific feature group. The goal is to find a rule that maximizes its Volume-Impurity (VI) index, which is the number of training examples covered by the rule minus a parameter $w$ times the number of misclassified examples. The authors formulated a Mixed-Integer Program (MIP) for this problem, and the method is empirically shown to have comparable or better performance compared to baselines on several datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "The contribution of the paper could be presented more clearly if the authors put this work into the context of prior related work better. Below are some concrete questions:\n\n- **Volume-Impurity Index:** How did prior work evaluate the \"effectiveness\" of a decision rule? Are those metrics identical or related to the VI index? If not, what is the benefit of using this new metric?\n\n- **The MIP:** Is the MIP in Equations (1)-(20) largely similar or identical to previous MIP-based methods for decision rules/lists/trees? If not, what is \"new\" in the current formulation (apart from the VI objective and the \"Branching Structure Constraints\" added in Algorithm 1)?\n\nIn addition, as detailed in the \"Requested Changes\" section, the current manuscript seems to contain numerous inaccuracies in the presentation of the OPDT method. I would urge the authors to carefully proofread the maths before re-submitting the manuscript (or submitting a revision of it).", "audience_yn": "No", "audience_explanation": "While I found it interesting to use domain knowledge to guide the structure and feature selection in rule-based ML, I would doubt whether the present work would be of great interest given the (arguably) straightforward method and the resulting computational overhead. Given the problem definition, the OPDT method seems to be a natural MIP formulation of the VI index objective. The method takes significantly more time than the baselines (Table 6) on arguably small datasets (Table 3). This is partly because the MIP contains at least as many variables as the number of nodes ($2^D$) times the number of training examples.\n\nI have a question related to the comment above: Since the MIP in (1)-(20) maximizes the highest VI index among all leaves of the tree, why do we need to solve for the entire decision tree? (Intuitively, all nodes that are not ancestors of the leaf with the largest VI index are \"inactive\" in the solution.) An alternative would be to enumarate all the leaf nodes of the tree and, for each leaf node $\\ell$, solve a separate MIP to maximize the VI index at $\\ell$. This should reduce the number of nodes in each MIP from $2^D$ to $D$.", "requested_changes": "Writing suggestions:\n\n- The notion of a \"rule\" (considered in this paper) should be formally defined somewhere, e.g., as a root-to-leaf path in a decision tree, or an AND of the conditions induced by all non-leaf nodes on that path.\n\n- When introducing the VI index, it should be mentioned that the goal is to find a rule that maximizes this index. (The current writing might suggest that the VI index is used as a proxy for another objective.)\n\n- Section 3.1: Please clarify what it means (mathematically) for features to \"have mutually exclusive impacts on classification\". (The meaning wasn't perfectly clear even after reading the example in the next sentence.)\n\n- Figure 1: The figure is ambiguous in various aspects: (1) In the left part, why is $G_1$ surrounded by \"{}\"? (2) Can different feature groups be overlapping, as the left part suggests (e.g., $G_1$ and $G_4$)? (3) In the middle part, what are the numbers $0$ through $15$?\n\n- Bottom of Page 5: \"$G_1, G_2, \\cdots, G_D$\" $\\to$ \"$G_1, G_2, \\ldots, G_D$\" (\"\\cdots\" vs \"\\ldots\").\n\n- Figure 2: This figure was particular confusing---it differs from Figure 1 and the MIP formulation in that it enforces the same feature group at each level of the decision tree, while Figure 1 and the MIP allow each node to have a different feature group. Is this special case ever considered in the rest of the paper?\n\n- Table 1: $N$ and $K$ are used both as sets and as numbers.\n\n- Table 1: Is $G_A$ the same as $P$? If so, why is a different notation needed?\n\n- Table 1: \"Numerical feature group\" and \"categorical feature group\" are not introduced.\n\n- Table 1: \"$i \\in 1, \\ldots, N$\" should be $i \\in N$, if $N$ is a set.\n\n- Table 1: $Y_{ik}$ should be introduced after $K$ and $k$.\n\n- Table 1 (continued): If $T_B$ is a set, there should be \"{}\" around \"$1, \\ldots, \\lfloor T/2 \\rfloor$\". Same comment for $T_L$.\n\n- Table 1 (continued): What is the \"objective function\" when defining $T_{\\mathrm{obj}}$?\n\n- The MIP in (1)-(20): The \"type\" of each variable---in addition to those in (19) and (20)---should be specified, i.e., whether each of them is $\\{0, 1\\}$-, negative-, or real-valued.\n\n- Equation (9): What are $\\vec{\\epsilon}$ and $\\epsilon_{\\mathrm{max}}$?\n\n- Equations (13) and (14): What is $M$?\n\n- Equations (16)-(18): These constraints seem to be enforcing that $I_{\\mathrm{max}}$ is the maximum VI index over all leaves. However, I don't think they would function as intended. For instance, we could have $q_t = 1$ for the leaf $t$ with the maximum VI index, and $q_t = 0$ elsewhere. Then, $I_{\\mathrm{max}}$ could be as high as the maximum VI index plus $M$. (A simple workaround would be setting $I_{\\mathrm{max}}$ as a weighted sum of the VI indices by $q$ and enforcing that $q \\ge 0$ entrywise.)\n\n- Algorithm 1: It should be stated more clearly that Lines 6, 8, and 10 are constraints to be added to the MIP, rather than \"usual\" statements in a pseudocode.\n\n- Algorithm 1: It would be clearer if you write \"$a_{pt} = 0$\" instead of \"$a_{pt} \\le 0$\" on Lines 8 and 10.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)