Keywords: decision tree; interpretability; irrelevant condition; relevance-aware rule; pruning

1 Introduction↩︎

Decision trees translate model decisions into explicit root-to-leaf rules. A terminal leaf defines a rule of the form \[C_1 \wedge C_2 \wedge \cdots \wedge C_r \Rightarrow y=c,\] where \(C_1,\ldots,C_r\) are the conditions on the root-to-leaf path and \(c\) is the leaf class. Root-to-leaf rules support local interpretation, but recursive tree induction forces each descendant leaf to inherit every upstream condition. As a result, the root-to-leaf path rule is often over-specified, accumulating irrelevant conditions (IRCs) that do not contribute to its decision. Because these IRCs hinder interpretability, their deletion is necessary to ensure clear and concise explanations.

IRC deletion addresses a distinct problem from global tree simplification, which encompasses both tree pruning and optimal tree induction. While tree pruning removes or replaces leaves and subtrees to reduce the overall tree size, IRC deletion removes an internal antecedent from a surviving path. A globally simplified tree may therefore still contain IRCs. In addition, IRCs frequently remain even in optimal sparse tree induction algorithms that generate small-sized trees [1].

To perform the path-level IRC deletion, existing literature has largely explored two prominent directions. Empirical rule post-pruning deletes antecedents using statistical test or certainty criteria and may convert a partitioning tree into an overlapping rule-set classifier that requires conflict resolution [2], [3]. Logical path-redundancy testing instead certifies whether antecedent deletion preserves the decision tree’s class consequence [1]. They do not provide a structural explanation for why certain conditions become irrelevant in certain paths of trees.

We propose a structural IRC deletion method that uncovers the underlying mechanics of why a condition of a path becomes irrelevant. Our starting point is an elementary but useful structural fact: in a binary split, the parent class proportion is a weighted average of the two child proportions. Hence, if one child increases the class-1 proportion, the other child necessarily increases the class-0 proportion. We call the corresponding outgoing links class-1-increasing links (C1-links) and class-0-increasing links (C0-links). This \(C1/C0\) link annotation serves as the primary structural signal used in this paper.

The \(C1/C0\) annotation itself is merely a local diagnostic signal, not a judgment of relevance. To formulate such a judgment, we evaluate this signal relative to a specific leaf node of class \(c\). A link in the path is matched when its orientation aligns with the leaf class \(c\), and mismatched when it points toward the opposite class. This leaf-relative diagnosis provides a structural warning, yet it remains inconclusive; a mismatched link is structurally suspicious but not inherently irrelevant.

To rigorously assess whether a condition should be deleted, we define relevance-aware rules—rules that preserve conditions essential for class support or reliability refinement, while removing only those that are structurally and empirically redundant. To this end, we distinguish three analytical layers:

1. Local annotation: where a link is tagged as C1, C0, or neutral;

2. Leaf-relative diagnosis: where a link is classified as matched or mismatched;

3. Path-level effect: where deleting the condition is evaluated by its impact on the rule.

At the third layer, we identify a positive-relevance effect (where a condition preserves path reliability), a negative-relevance effect (where a condition identifies a lower-reliability subregion), or a probabilistic IRC effect (where the condition is redundant). By explicitly separating these layers, we avoid the false assumption that every mismatched link is inherently irrelevant, ensuring that our final relevance-aware rules are both compact and structurally faithful.

Analytical-layer application depends on how each procedure certifies reliable deletion within a rule domain. Structural candidate generation is domain-independent. The acceptance criterion that converts a candidate into an accepted deletion, however, must be specialized by domain to remain reliable.

Two complementary procedures implement this separation. Method 1, the broader mismatch-guided procedure, generates candidates from leaf-relative C1/C0 mismatches. Its acceptance criterion is domain-specific: for deterministic rules, a candidate set is accepted only through a joint hard-implication certificate, guaranteeing \(R \Rightarrow y=c\); for class-probability rules, mismatches within label-homogeneous ancestor subtrees are preserved by default, while mismatches elsewhere are deleted only after verifying path-level reliability preservation within a two-sided tolerance. Method 2, the narrower sibling-certified procedure, certifies deletion directly from same-class sibling-leaf topology: whenever one child of a split is a same-class leaf and the opposite subtree contains a descendant leaf of that class, the link into that subtree is removable regardless of orientation. This certificate requires no domain-specific criterion, and guarantees exact preservation of the fitted tree’s predictions, full coverage, and zero opposite-class rule conflict in either domain. Method 1 thus prioritizes broader relevance-aware compression, whereas Method 2 offers conservative simplification with exact source-tree preservation.

The study makes three contributions:

• Find the structural mechanics of IRC in decision trees.

• Formalize path-level relevance semantics to diagnose the functional role of path conditions across three distinct analytical layers.

• Develop a structural IRC deletion framework that efficiently identifies and removes IRCs, achieving scalability linear in the number of leaf rules.

The remainder of the paper is organized as follows. Section 2 positions the study relative to tree pruning, rule post-pruning, and logical path-redundancy testing. Section 3 defines the problem and notation. Section 4 presents the proposed methods, Section 5 reports the experiments, Section 6 discusses, and Section 7 concludes the paper.

2 Related Work↩︎

Structural IRC deletion differs from global tree simplification, empirical rule post-pruning, and logical path-redundancy testing in both the object simplified and the behavior preserved.

2.1 Global tree simplification↩︎

Subtree pruning reduces global tree complexity but does not directly shorten a surviving leaf rule. Cost-complexity, reduced-error, and pessimistic pruning replace subtrees with leaves or select a smaller tree according to predictive and complexity criteria [4], [5]. Subtree-pruning methods can reduce the number of nodes and leaves, but every retained leaf still inherits all conditions on its retained root-to-leaf path. A globally smaller tree may therefore still produce a locally over-specified rule.

Optimization-based tree induction reduces dependence on greedy split selection but does not directly address path-internal condition deletion. Optimization-based tree-induction methods optimize tree-level objectives under structural constraints rather than relying only on greedy top-down growth [6], [7]. Global tree optimization, however, does not preclude path-internal IRCs [1]. The proposed IRC-deletion methods can therefore post-process both greedy and optimization-based fitted trees.

2.2 Empirical rule post-pruning↩︎

Rule post-pruning directly shortens antecedents, but its primary objective is the predictive performance of the resulting rule-set classifier. [2] extracts rules from a decision tree and deletes antecedents using statistical relevance and certainty criteria. C4.5rules further combines antecedent deletion with estimated-error evaluation, subset selection, and rule ordering [3]. Related rule-learning methods, including PRISM, RIPPER, and PART, construct or select rule sets outside the original tree partition through modular or separate-and-conquer procedures [8]–[10]. Independent rule simplification may create overlapping rules with different class predictions. The resulting classifier behavior therefore depends on rule ordering, conflict resolution, coverage, and fallback policies.

Empirical antecedent deletion can improve aggregate rule quality while changing the population represented by an individual leaf rule. Removing an antecedent expands the descendant rule beyond the original leaf region, and the expanded rule may cover cases from sibling or ancestor regions with different structural meanings. A higher empirical class probability can therefore reflect broader coverage rather than faithful simplification of the original leaf. Section 4.2 defines expansion that absorbs a descendant rule into a broader ancestor region as ancestor-rule assimilation and evaluates ancestor-rule assimilation separately from predictive accuracy.

Rule compactness alone does not establish explanation quality. Work on comprehensible and interpretable rule models emphasizes that a short rule may omit conditions that identify scientifically or operationally meaningful subgroups [11], [12]. For decision-tree path rules, a condition may be unnecessary for preserving the final class label but still distinguish leaf regions with different class reliability. The distinction between label preservation and reliability preservation motivates evaluating the resulting rule rather than judging deletion only by antecedent count or one-sided reliability improvement.

2.3 Logical path-redundancy testing↩︎

Logical path-redundancy methods provide exact preservation guarantees for individual path decisions. [1] test whether deleting a path condition preserves the class consequence under the fitted tree. The path condition is the unit of analysis, and the acceptance criterion prohibits changes to the fitted tree’s class decision. Exact fitted-tree preservation is stronger than an empirical tolerance criterion but may be more conservative when limited behavioral change is acceptable. Logical path-redundancy testing certifies deletion safety after tree fitting but does not identify structurally suspicious conditions before evaluation.

2.4 Position of Relevance-Aware Structural IRC Deletion↩︎

Our structural IRC deletion procedure closes the methodological gap that global tree simplification, empirical rule post-pruning, and logical path-redundancy testing leave open between aggressive antecedent deletion and exact fitted-tree preservation. It does so by using split-induced tree structure to identify suspicious inherited conditions and by associating each accepted deletion with an explicit preservation target. The resulting procedure removes path conditions from a fixed fitted tree while retaining one output rule for every source leaf.

The proposed framework uses two complementary forms of structural evidence. Method 1 uses leaf-relative C1/C0 mismatch together with setting-specific deterministic or reliability-based acceptance criteria, whereas Method 2 uses same-class sibling-leaf topology as a sample-independent certificate for exact source-tree preservation.

3 Problem Setting and Notation↩︎

Relevance-aware structural IRC deletion requires explicit definitions of tree links, rule regions, deletion sets, and training-rule reliability.

Let \[\mathcal{S}=\{(x_i,y_i)\}_{i=1}^{M}\] be the training sample, where \(M\) is the number of training instances and \(y_i\in\{0,1\}\), and let \(T\) be the fitted binary source tree. For node \(N\), \(n(N)\) is its training count, \(n^c(N)\) is its class-\(c\) count, \(p_c(N)=n^c(N)/n(N)\) is its class-\(c\) proportion, and \(\operatorname{Re}(N)\) is its predicted class.

Table 1 summarizes the notation; quantities indexed by \(\mathcal{S}\) are computed on the training sample.

Each link \(e\) has an associated path condition \(C(e)\). Let \(\mathcal{P}(L)=(e_1,\ldots,e_r)\) denote the ordered root-to-leaf link sequence for leaf \(L\). The generated rule is \[\operatorname{GR}(L)=\bigwedge_{j=1}^{r}C(e_j).\] For a deletion set \(Q\subseteq\{e_1,\ldots,e_r\}\), define \[R^{-Q}=\bigwedge_{e_j\notin Q}C(e_j).\] For a singleton, \(R^{-e}=R^{-\{e\}}\). The sequence order is used when candidates are evaluated; \(Q\) and the accepted deletion set are sets of links. Deleting a link means deleting its associated path condition; links and conditions remain distinct objects. Each structural deletion variant produces exactly one output rule per input leaf and performs neither cross-rule deduplication nor redundant-rule elimination.

The training-sample rule region, support, and rule reliability are \[\mathcal{D}_{\mathcal{S}}(R)=\{i:x_i\models R\},\qquad \operatorname{supp}_{\mathcal{S}}(R)=|\mathcal{D}_{\mathcal{S}}(R)|,\] \[\hat{p}_{c,\mathcal{S}}(R)= \frac{|\{i\in\mathcal{D}_{\mathcal{S}}(R):y_i=c\}|}{\operatorname{supp}_{\mathcal{S}}(R)}.\] We call \(\hat{p}_{c,\mathcal{S}}(R)\) rule reliability throughout and omit \(\mathcal{S}\) when the training sample is unambiguous.

3.1 C1/C0 link orientation↩︎

Lemma 1 justifies complementary C1/C0 link orientation for proportion-changing binary splits. Figure 1 uses both line style and text labels, so its two orientations do not depend on color.

3.2 Entropy is not link-level relevance↩︎

Define the scalar binary-entropy function \[h(t)=-t\log t-(1-t)\log(1-t)\] and node entropy \(\operatorname{Ent}(N)=h(p_1(N))\). This notation separates the scalar function from a node quantity.

Table 2 shows the scientific distinction: complementary C1/C0 orientation is fixed by the proportion change, whereas the sibling entropy can be either higher or lower than the parent’s.

Entropy explains split selection but does not define link-level relevance; the path-level deletion effect on a complete generated rule defines condition relevance.

4 Relevance-Aware Structural IRC Deletion↩︎

Relevance-aware structural IRC deletion separates structural candidate generation from setting-specific deletion acceptance. Strict mismatch provides a broader diagnostic candidate source, whereas same-class sibling topology provides a narrower exact-preservation certificate independent of link orientation. The implementation names the mismatch-guided branch Method 1 and the sibling-certified branch Method 2; the D/P suffix identifies the deterministic or class-probability setting. Table 3 summarizes the candidate sources, acceptance rules, and preservation targets.

4.1 Deterministic structural certificates↩︎

In the deterministic rule setting, an accepted deletion must preserve the hard class implication. C1/C0 mismatch is a candidate signal rather than a certificate, so the complete proposed deletion set is evaluated jointly. Same-class sibling topology instead supplies exact local evidence independently of link orientation.

When a finite deterministic domain \(\mathcal{X}_0\) is explicitly listed, the joint M1-D certificate can be evaluated directly: a deletion set \(Q\) is accepted only if every \(x\in\mathcal{X}_0\) satisfying \(R^{-Q}\) has class \(c\). This establishes the weakened implication on \(\mathcal{X}_0\), without extending it to unlisted attribute combinations. When a class-oriented order is available, the following theorem supplies an analytic sufficient certificate on the stated feasible domain.

Repeated predicates on the same feature are intersected before the feasibility test. Failure of the complete-set certificate preserves the original rule. Individually plausible conditions are not accumulated as though singleton certificates implied joint soundness.

Formally, \(e=(N_p,N_b)\in\operatorname{SIB}(L)\) when \(e\in\mathcal{P}(L)\), \(N_b\) is the internal child of \(N_p\) containing \(L\), and the other child of \(N_p\) is a leaf with predicted class \(\operatorname{Re}(L)\).

Figure 2 illustrates the same-class sibling certificate for a class-1 descendant.

The sibling certificate is independent of C1/C0 orientation. Consequently, \(\operatorname{SIB}(L)\) may include a matched link or a link inside \(H_c(L)\); neither property changes sibling-certified candidacy.

4.2 Class-probability relevance↩︎

For a class-\(c\) generated rule \(R\) and a deletion set \(Q\), define \[D_c(Q;R)=\hat{p}_c(R^{-Q})-\hat{p}_c(R).\] The single-condition effect is \(D_c(\{e\};R)\), abbreviated \(D_c(e;R)\). The set-level definition covers both joint and cumulative greedy trials.

For tolerance \(\epsilon\ge0\), a deletion set is reliability-decreasing when \(D_c(Q;R)<-\epsilon\), reliability-increasing when \(D_c(Q;R)>\epsilon\), and reliability-preserving when \(|D_c(Q;R)|\le\epsilon\).

Table 4 summarizes the set-level terminology and the corresponding singleton interpretation.

For node \(N\), define \[\Lambda(N)=\{\operatorname{Re}(L'):L'\in\operatorname{Leaves}(N)\}.\] For a leaf \(L\) with \(c=\operatorname{Re}(L)\), let \(S\) be the highest ancestor of \(L\) such that \(\Lambda(S)=\{c\}\). The subtree rooted at \(S\) is denoted \(H_c(L)\) and is the largest \(c\)-label-homogeneous ancestor subtree containing \(L\). If no nonleaf ancestor satisfies the condition, set \(H_c(L)=L\). A link lies inside \(H_c(L)\) when both its parent and child belong to the rooted subtree; otherwise the link lies outside.

The mismatch-guided mechanism preserves matched links by construction; matched status alone does not establish positive relevance. Mismatched links inside \(H_c(L)\) are treated as negative-relevance-presumed and protected because the links may encode same-label reliability refinement. Mismatched links outside \(H_c(L)\) are treated as IRC-presumed structural candidates and become accepted deletions only after the two-sided reliability criterion is satisfied. The three presumptions govern mismatch-guided deletion only; sibling-certified candidacy is independent of C1/C0 orientation and does not use \(H_c(L)\).

4.2.0.1 Ancestor-rule assimilation.

Ancestor-rule assimilation occurs when condition deletion reduces a descendant generated rule to a strict root-to-ancestor prefix and thereby expands the rule region: \[\mathcal{D}_{\mathcal{S}}(R_L) \subsetneq \mathcal{D}_{\mathcal{S}}(R_A).\] The operational diagnostic records a strict-prefix output only when the retained predicates equal a proper root-to-ancestor prefix and the corresponding training region expands strictly. A zero or low strict-prefix rate therefore means that few resulting rules satisfy this exact structural criterion; it does not exclude other forms of overlap with ancestor or sibling regions.

Figure 3 illustrates the distinction between the descendant rule, the retained ancestor prefix, and the additional sibling-region support.

The two-sided criterion controls this set-level reliability change for M1-P. It is not an acceptance condition for M2-P.

4.3 Executable procedure↩︎

Tree-level annotations and candidate structures are computed once and reused across leaf rules. The mismatch-guided branch uses C1/C0 orientation and, in class-probability mode, ReliabilitySelect. The sibling-certified branch uses only the sibling sets \(\operatorname{SIB}(L)\). Appendix 8 summarizes the shared preprocessing steps.

4.3.1 Mismatch-Guided Relevance-Aware Deletion (Method 1)↩︎

Algorithms 4 and 5 specify the deterministic and class-probability variants of mismatch-guided deletion. M1-D submits the complete strict-mismatch set to either direct finite-domain verification or the joint certificate in Theorem 1. M1-P treats mismatches inside \(H_c(L)\) as negative-relevance-presumed and protects them; Algorithm 8 evaluates the IRC-presumed candidates outside \(H_c(L)\).

4.3.2 Sibling-Leaf-Certified Exact-Preservation Deletion (Method 2)↩︎

Algorithms 6 and 7 specify the deterministic and class-probability variants of sibling-certified deletion. Both variants delete the complete set \(\operatorname{SIB}(L)\) certified by Theorem 2. The sample-independent structural operation is identical in both settings, and every sibling-certified link is deleted jointly.

4.3.2.1 Two-sided relevance-aware acceptance for M1-P.

ReliabilitySelect implements the two-sided relevance-aware acceptance criterion for class-probability mismatch candidates. The subroutine receives the original rule \(R\), class \(c\), ordered candidates \(I\), training sample \(\mathcal{S}\), and operational tolerance \(\epsilon\), and returns an accepted set \(J\subseteq I\). The helper Evaluate returns the reliability and acceptance decision for a trial set \(Q\). The subroutine evaluates set-level reliability preservation and does not assign intrinsic relevance labels to individual links.

The tolerance \(\epsilon\) is operational rather than a sampling-confidence guarantee. Antecedent deletion broadens a nonempty leaf region, so the resulting rule cannot have lower training support than its original leaf rule.

4.3.3 Procedure Flow Charts↩︎

Figures 9 and 10 summarize the setting-specific procedures. The mismatch-guided flow sends C1/C0 candidates to either the joint deterministic certificate or the \(H_c(L)\)-protected reliability selector, according to the rule setting. The sibling-certified flow applies the sample-independent sibling certificate in both settings and then assigns the corresponding output notation.

4.4 Complexity↩︎

Let \(V\) be the number of tree nodes, \(n_L\) the number of leaf rules, \(D\) the maximum path length, \(M\) the number of training instances, and \(k_i\le d_i\le D\) the M1-P candidate count and original length of rule \(i\). Shared preprocessing for link orientation, descendant-label sets, and sibling candidates requires \(O(V+n_LD)\) time.

M1-P additionally constructs cached link masks in \(O(MV)\) time. For rule \(i\), one baseline trial, one joint-deletion trial, and at most \(k_i\) fallback trials each intersect at most \(d_i\) masks over \(M\) instances. Therefore, \[T_{\mathrm{M1-P}} =O\!\left( V+n_LD+MV+ M\sum_{i=1}^{n_L}d_i(2+k_i) \right) \subseteq O\!\left(V+n_LD+MV+Mn_LD^2\right),\] with \(O(MV+n_LD+M)\) auxiliary space.

M2-P uses only tree topology and path entries, giving \(T_{\mathrm{M2-P}}=O(V+n_LD)\) time and \(O(V+n_LD)\) auxiliary space, independent of \(M\). The deterministic variants have corresponding bounds: \(T_{\mathrm{M2-D}}=O(V+n_LD)\), while \(T_{\mathrm{M1-D}}=O(V+n_LD+C_{\mathrm{cert}})\), where \(C_{\mathrm{cert}}\) is the joint-certificate cost. Precomputed monotone feature bounds give \(C_{\mathrm{cert}}=O(n_LD)\); direct verification on a finite table of \(M_0\) rows instead requires \(O(M_0\sum_{i=1}^{n_L}d_i)\subseteq O(M_0n_LD)\).

For the implementations considered here, repeated condition rescoring in the Quinlan procedure [2] gives \(T_{\mathrm{Quinlan}}=O(M\sum_{i=1}^{n_L}d_i^3)\subseteq O(Mn_LD^3)\), whereas opposite-class path comparisons in the Izza procedure [1] give \(T_{\mathrm{Izza}}=O(n_L^2D^2)\).

One output rule is retained for each source leaf, and the full binary source trees considered here satisfy \(V=2n_L-1\). With \(M\) fixed and lower-order preprocessing terms suppressed, M2 and M1-P scale as \(O(n_LD)\) and \(O(n_LD^2)\), respectively, whereas the Izza and Quinlan procedures scale as \(O(n_L^2D^2)\) and \(O(n_LD^3)\). Thus, the proposed methods retain linear dependence on the number of rules; M2 is linear and M1-P is quadratic in path length.

For fixed \(n_L\) and \(D\), M2 and the Izza procedure are \(O(1)\) in \(M\), whereas M1-P and the Quinlan procedure are \(O(M)\). These bounds isolate the principal sources of growth but do not impose a strict runtime ordering for every combination of \(M\), \(n_L\), and \(D\).

5 Experiments↩︎

The experiments compare the broader mismatch-guided and narrower sibling-certified structural deletion mechanisms with established IRC-deletion procedures. The deterministic variants M1-D and M2-D are first evaluated on decision tables that permit exhaustive case-wise checking. The class-probability evaluation then examines simplification and fidelity: simplification measures how frequently and how strongly source rules are shortened, whereas fidelity measures how closely the resulting rule sets retain the predictive and class-wise behavior of the fitted tree. A runtime study evaluates scalability with respect to the training-sample size and the number of leaf rules.

5.1 Experimental Setting↩︎

The experiments use two deterministic decision tables and eight class-probability datasets. The Weather data contain 14 cases described by Outlook, Temperature, Humidity, and Windy, with Play as the binary decision [13]. The Human Identification (human-id) data contain eight cases described by Height, Hair, and Eyes, with a binary \(+/-\) class [14]. The remaining eight binary-classification datasets are drawn from the UCI Machine Learning Repository and OpenML [15], [16]. Table 5 summarizes the inputs used for tree induction.

For the deterministic evaluation, all nominal levels, including both Windy values, are represented by full one-hot indicator columns. An unpruned Gini CART with deterministic best-split selection is fitted to each listed decision table and is required to reproduce every supplied class label. M1-D accepts a complete strict-mismatch set only when direct enumeration validates the weakened rule on all supplied cases; M2-D applies the sibling-leaf certificate; and the Izza procedure [1] applies exact fitted-tree path-redundancy testing. The post-deletion audit checks rule validity, cumulative coverage, agreement with source-tree predictions, and opposite-class conflict on every listed case.

For each class-probability dataset, the evaluation reuses 30 stratified 70/30 train–test splits and the corresponding depth-6 CART trees using Gini impurity and saved depth-6 IAI trees representing optimization-based induction [4], [6]. M1-P, M2-P, and the procedures of [2] and [1] receive the same source tree and leaf-rule set for every learner, dataset, and split. For M1-P, \(\epsilon\in\{0,0.01,0.03,0.05,0.10,0.20\}\) is selected separately for each dataset by descriptive grid optimization and shared by CART and IAI. The selection maximizes mean condition deletion subject to nonnegative mean accuracy change and a 5% mean-conflict ceiling for each learner. M2-P uses only the fitted-tree topology.

Where multiple rules cover the same instance, M1-P and the Quinlan procedure rank them by decreasing training reliability, decreasing training support, increasing rule length, and source-leaf order. M2-P and the Izza procedure have zero opposite-class rule conflict, so their predictions are invariant to this ranking. Results are averaged first across the 30 paired splits within each dataset and then equally across the eight dataset means.

5.2 Deterministic Rule Setting↩︎

Table 6 compares M1-D, M2-D, and the Izza procedure on Weather and human-id. Each source CART fits its listed decision table exactly. The audit enumerates every supplied case and verifies class-valid simplified rules, complete cumulative coverage, unchanged source-tree predictions, and zero opposite-class rule conflict.

3pt

M1-D matches the Izza procedure on both deterministic tables and removes more conditions than M2-D on Weather. The Weather source contains 23 conditions across seven rules: M1-D and the Izza procedure each remove seven conditions (30.43%) from five rules, whereas M2-D removes five conditions (21.74%) from four rules. Thus, M1-D removes two additional conditions, or 8.69 percentage points more, because finite-domain verification accepts two conditions without a same-class sibling-leaf certificate. On human-id, all three procedures remove the same one of five conditions (20.00%) from one of three rules. Every simplified rule set preserves complete listed-case coverage, source-tree predictions, and zero opposite-class rule conflict.

5.3 Class-Probability Rule Setting↩︎

The class-probability evaluation compares the relevance-aware mismatch-guided variant M1-P and the sibling-certified exact-preservation variant M2-P with the Quinlan procedure [2] and the Izza procedure [1] on the eight datasets in Table 5. Table 7 defines the three evaluation dimensions: simplification, fidelity, and scalability.

5.3.1 Simplification↩︎

Table 8 reports the percentage of source rules containing at least one deleted condition and the average within-rule deletion percentage among affected rules. The relevance-aware mismatch-guided variant M1-P shortens 72.66% of IAI rules and 70.98% of CART rules, approximately 2.22 and 2.35 times the corresponding M2-P rates. Relative to the Izza procedure, the M1-P RuleIRC rate is higher by 40.00 percentage points for IAI and 30.63 percentage points for CART. Within affected rules, M1-P deletes 34.88% and 37.13% of antecedents, exceeding M2-P by 11.63 and 12.97 percentage points and the Izza procedure by 11.13 and 13.16 percentage points. The Quinlan procedure remains the most aggressive, shortening 96.32%/98.05% of rules and deleting 63.43%/64.49% of antecedents within affected rules. The results place broader reliability-controlled structural deletion between the empirical Quinlan procedure and the source-prediction-preserving M2-P and Izza procedures.

5.3.2 Fidelity↩︎

Greater condition deletion does not by itself establish better fidelity. Deleting an antecedent expands the covered rule region and can trade compactness for class-wise deviation or opposite-class overlap. Tables 9 and 10 quantify this trade-off through accuracy change, rule conflict, absolute class-wise changes, and MacroDev; absolute accuracy is omitted because every comparison uses the same fitted source tree.

The broader reliability-controlled variant M1-P removes 27.19% of IAI conditions and 27.30% of CART conditions, exceeding M2-P by 18.84 and 18.71 percentage points and the Izza procedure by 18.89 and 16.53 percentage points. The broader deletion is accompanied by conflict rates of 2.82%/2.31%, MacroDev values of 0.98/0.99 percentage points, and mean accuracy changes of \(+0.51\)/\(+0.63\) percentage points.

The sibling-certified exact-preservation variant M2-P and the Izza procedure produce zero accuracy change, zero class-wise deviation, and zero opposite-class rule conflict. The M2-P outcomes agree with the structural preservation result for the fitted source tree.

The Quinlan procedure removes 62.21%/63.60% of all conditions, 35.02/36.30 percentage points more than M1-P, but its dataset-balanced conflict rates reach 50.59%/55.44% and its MacroDev reaches 6.03/5.36 percentage points. The positive mean accuracy changes of \(+0.75\)/\(+1.04\) percentage points therefore do not establish preservation of source-tree class-wise or rule-set behavior.

5.3.3 Scalability↩︎

The two-panel runtime analysis in Figure 11 examines the scaling dimensions identified in Section 4.4. Figure 11 (a) fixes the training-sample size at \(M=2{,}048\) and varies the leaf-rule target over \(4,8,16,32,64,128\). Figure 11 (b) holds a 32-leaf fitted tree and source-rule signature fixed and evaluates five training-sample sizes from \(M=4{,}096\) to \(M=1{,}048{,}576\). All four procedures receive the same fitted CART and source rules. Three tree seeds, one warm-up, three timed repetitions, and rotating method order are used; the curves show the median and interquartile range.

M2-P and the Izza procedure do not scan the training sample during simplification, and their runtime curves remain nearly flat as \(M\) increases. At 128 leaves, M2-P requires 0.0073 s, compared with 0.166 s for the Izza procedure, making M2-P approximately 23 times faster in this setting. M1-P evaluates instance-level reliability and therefore increases with \(M\), consistently with its linear sample-size term. Cached condition masks nevertheless keep the leaf-scaling cost low: at 128 leaves, M1-P requires 0.0193 s, compared with 18.223 s for the Quinlan procedure, making M1-P approximately 944 times faster in this setting. At \(M=1{,}048{,}576\) with the 32-leaf tree fixed, M1-P requires 0.271 s versus 64.722 s for the Quinlan procedure, and M2-P requires 0.0017 s versus 0.0084 s for the Izza procedure. The corresponding measured speedups are approximately 239-fold and 4.9-fold.

5.3.3.1 Summary.

The mismatch-guided class-probability variant M1-P occupies an intermediate simplification regime between the conservative Izza procedure and the aggressive Quinlan procedure. Protection of negative-relevance-presumed mismatches inside \(H_c(L)\) and two-sided reliability selection outside the protected subtree retain low rule conflict and small class-wise deviation while providing substantially faster processing than the Quinlan procedure. The sibling-certified variant M2-P follows a conservative simplification pattern close to exact path-redundancy deletion, exactly preserves the fitted source-tree predictions, and produces zero rule conflict. Within the measured runtime ranges, M2-P is also faster than the Izza procedure, yielding the fastest topology-only simplification among the four procedures.

6 Discussion↩︎

Why are shorter rules not necessarily relevance-aware? Condition relevance is a path-level effect of deletion rather than a local property of a split or link. For a single condition \(e\), \(D_c(e;R)<-\epsilon\) denotes a positive-relevance effect because deletion lowers leaf-class reliability; \(D_c(e;R)>\epsilon\) denotes a negative-relevance effect because deletion raises reliability but may erase a lower-reliability same-label refinement; and \(|D_c(e;R)|\le\epsilon\) denotes a probabilistic IRC effect. For multiple conditions, only reliability-decreasing, reliability-increasing, or reliability-preserving set-level terminology applies because individual effects may interact. Rule length and condition deletion must therefore be interpreted together with reliability change, coverage, rule conflict, accuracy, and class-wise deviation.

What does mismatch evidence reveal? C1/C0 orientation records the local class-proportion change induced by a split. Relative to a class-\(c\) leaf, a C\(c\) link is matched and a C\((1-c)\) link is mismatched, but neither status alone determines condition relevance. The mismatch-guided mechanism preserves matched links by construction, treats mismatches inside \(H_c(L)\) as negative-relevance-presumed refinements, and treats mismatches outside \(H_c(L)\) as IRC-presumed candidates. Deterministic deletion requires a joint hard-implication certificate, whereas class-probability deletion applies the two-sided effect \(D_c(Q;R)\). The resulting M1-D and M1-P variants therefore provide broader structural deletion under explicit setting-specific control.

What does sibling evidence certify? Same-class sibling-leaf topology supplies an exact local certificate independently of C1/C0 orientation and \(D_c(Q;R)\). A sibling-certified link may be matched or located inside \(H_c(L)\), so the sibling and mismatch candidate sets are non-nested. The rootmost-divergence result guarantees source-tree predictions, full coverage, and zero opposite-class rule conflict for the M2-D and M2-P outputs. The narrower sibling-certified set yields less deletion but provides exact source-tree preservation without \(M\) or \(\epsilon\).

What trade-off defines a relevance-aware rule? M1-P removes approximately three times as many source conditions as M2-P for both IAI and CART while keeping aggregate MacroDev below one percentage point and rule conflict below 3%. M2-P provides narrower topology-only deletion with exact preservation, whereas the Quinlan procedure provides substantially greater deletion with conflict on more than half of the test cases and markedly larger class-wise deviation. Relevance-aware rule generation therefore does not maximize deletion but instead makes the structural evidence, acceptance criterion, and preserved rule meaning explicit.

7 Conclusion↩︎

Condition relevance in a decision-tree path rule is defined by the effect of deletion on the complete rule, not by a local link orientation alone. C1/C0 orientation and matched/mismatched status provide structural diagnostics that generate candidates without declaring relevance. The mismatch-guided mechanism converts structural candidates into accepted deletions only through a joint deterministic certificate or a two-sided class-probability reliability criterion. Same-class sibling topology supplies a separate exact-preservation certificate independent of the path-level reliability effect. A relevance-aware rule is therefore not a globally shortest rule; the deletion rationale and preservation target remain explicit for every accepted condition set.

On Weather, M1-D, M2-D, and the Izza procedure [1] remove 30.43%, 21.74%, and 30.43% of conditions; on human-id, all three remove 20.00%. Every deterministic rule set preserves listed-case validity, coverage, source-tree predictions, and zero opposite-class rule conflict. On saved CART and IAI trees, M1-P provides substantially greater deletion than M2-P and the Izza procedure while maintaining small accuracy changes, low conflict, and sub-one-percentage-point aggregate MacroDev. M2-P and the Izza procedure preserve source-tree predictions, whereas the Quinlan procedure [2] achieves the largest reduction at the cost of the greatest rule conflict and class-wise change. The two-axis runtime results further distinguish sample-dependent reliability evaluation from topology-only deletion. Decision-tree rule simplification should be evaluated by which conditions are removed, why deletion is justified, and what rule meaning is preserved.

Acknowledgments↩︎

This work was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF), funded by the Ministry of Education (Grant Number: NRF-2021R1A6A1A03039981). This work was also supported by the NRF under Grant RS-2019-NR040071, funded by the Ministry of Science and ICT.

8 Shared Preprocessing and Parameters↩︎

The preprocessing stage converts the fitted tree into reusable structural annotations without deleting conditions. Algorithm 12 computes C1/C0 link orientation, descendant-label sets, sibling-leaf candidates, and label-homogeneous ancestor subtrees once before the leaf rules are processed.

The postorder union computes \(\Lambda(N)\), and the ancestor scan obtains the highest label-homogeneous ancestor used by the mismatch-guided class-probability variant M1-P. Sibling detection records the link into an internal child only for same-class descendant leaves when the opposite child is already a class-\(c\) leaf. The sibling-certified mechanism deletes all such links using the resulting topology alone. The numerical \(\texttt{rf\_tol}\) affects C1/C0 diagnostic annotation but cannot change the M2 deletion set.

Table 11 summarizes the experimental and implementation settings used throughout the analysis.

9 Detailed Experimental Results↩︎

The following learner-specific tables report the dataset-level results underlying the three class-probability analyses. Their columns match the main-text simplification and fidelity tables: RuleIRC and IRC/rule quantify simplification; \(\Delta\)Accuracy and conflict summarize prediction preservation; and the absolute class-wise changes with MacroDev describe shifts in precision and recall. IAI and CART are presented separately, and each entry averages the 30 paired splits within one dataset.

Tables 12 and 13 show that M1-P has a higher RuleIRC rate than M2-P and the Izza procedure on every dataset. Within affected rules, M1-P also deletes a larger antecedent share on every dataset except adult with IAI, where its 25.08% deletion rate is slightly below the 26.53% rate of the Izza procedure. The largest M1-P RuleIRC rates occur on spambase for both IAI and CART, at 91.99% and 89.80%, whereas EEG yields the smallest rates, at 33.60% and 45.82%.

Tables 14–17 show the corresponding preservation pattern. M2-P and the Izza procedure retain zero accuracy change, zero rule conflict, and zero class-wise deviation on every dataset. M1-P conflict remains at or below 4.29%, and its largest MacroDev is 1.77 percentage points for IAI and 1.97 percentage points for CART, both on backache. The Quinlan procedure reaches 100% conflict on german and heart-h for IAI and on heart-h for CART, while its largest MacroDev occurs on german at 16.81 and 14.36 percentage points. Spambase is a notable exception: the Quinlan and M1-P MacroDev values are similar, although the Quinlan procedure still produces substantially greater rule conflict.

References↩︎

---

1. Corresponding author.↩︎