acceptodds
Under review as a conference paper at ICLR 2027

A Multiclass Decision Tree with Balanced Topology via Label-Constrained K-means Grouping and SVM Learning

Abstract

In multiclass scenarios, effectively performing classification tasks with decision tree models is of great importance in fields such as medical analysis, intrusion detection, and data mining. This task faces numerous challenges, including accurate classification on large datasets and in imbalanced scenarios. Existing decision tree methods have the following shortcomings: (1) the learned tree topology is not sufficiently compact and requires pruning to control tree depth; (2) node splitting is performed through multiple sequential steps and has not been incorporated into a unified mathematical framework; (3) tree node splitting is often measured by distance or splitting criteria such as Shannon entropy, information gain, and the Gini index, without fully considering the global structure and information of nodes. To address these issues, we propose SLtree, a multiclass decision tree that obtains a balanced topology via label-constrained K-means grouping and learns nonlinear decision boundaries using support vector machines. During decision tree construction, SLtree introduces the clustering principle of the K-means algorithm, fully leveraging global relationships among samples. Moreover, label constraints are imposed to constrain the tree topology to a structurally optimized balanced binary tree, thereby yielding a compact topology construction. Node splitting can be mathematically represented by a constrained formulation and does not require multiple steps. To probe the classification limits of SLtree, we introduce an improved particle swarm optimization algorithm to individually optimize the parameters of each splitting node, yielding an improved variant of the algorithm, ISLtree. Experimental evaluation on 41 datasets demonstrates that our SLtree algorithm achieves a leading ranking among the compared algorithms, while its improved variant, ISLtree, significantly outperforms other methods. Moreover, ISLtree exhibits outstanding performance on imbalanced datasets and datasets with high classification difficulty, and it has clear advantages over other methods on datasets with large sample sizes.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Decision Tree, Multi-class Classification, Support Vector Machine, Particle Swarm Optimization (PSO), K-means Algorithm

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_8ktbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes SLtree, a multiclass classifier that constructs a balanced binary hierarchy by grouping entire classes through a label-constrained KK-means objective, then trains an SVM at each internal node to route samples toward class-specific leaves. Its extension, ISLtree, uses an improved particle swarm optimizer to select each node’s SVM hyperparameters independently.

Critical strengths

The label-constrained grouping formulation keeps each class within a single branch while controlling the number of classes assigned to each child. This provides a clear way to construct a shallow hierarchy without post-hoc pruning, which is the method’s main structural advantage.

Critical weaknesses
  1. The optimization procedure does not substantiate the claimed optimality or scalability. Equations (3.7)–(3.8) define a discrete, nonconvex grouping problem, while Appendix Algorithm 2 enumerates class assignments and alternates updates without establishing global optimality. The number of candidate groupings grows combinatorially, yet evaluation is limited to 3–18 classes. This limits confidence in the central claim of an efficient, generally applicable construction procedure.
  2. The empirical comparisons do not clearly establish the source or reliability of the gains. ISLtree receives extensive node-specific tuning without a demonstrated matched search budget for competing methods, and its accuracy improvement over SLtree is not statistically significant in the reported test. Moreover, Tables 2 and 3 list inconsistent baseline ranks. These issues make it difficult to determine whether the improvements reflect the proposed method, additional tuning effort, or errors in the statistical analysis.
Questions for authors
  1. Could you clarify whether Algorithm 2 exhaustively evaluates all (lh)\binom{l}{h} groupings at each update, and what optimality guarantee applies to the final solution? Please also specify the rounding convention in Equation (3.8), particularly for even numbers of classes.
  2. What hyperparameter-search budgets were used for each baseline? Does any existing comparison separate the benefit of node-specific tuning from the choice of the improved PSO optimizer?
  3. Could you explain the different baseline ranks in Tables 2 and 3 and clarify whether correcting them changes the Holm-adjusted significance conclusions?
4 comments

We thank the reviewer for the constructive comments. Our responses are organized by point.

  1. In Algorithm 2, all possible GG matrices are exhaustively enumerated at initialization; during the alternating optimization of the CC matrix and the GG matrix, the GG matrix is likewise exhaustively searched to find the optimal GG matrix satisfying the constraints, whereas the CC matrix is the closed-form least-squares solution obtained with the GG matrix fixed. The rounding convention in Equation~(3.8) is rounding to the nearest integer with .5.5 rounded up. Assuming an even number of classes, l=2kl=2k, then h=kh=k and l−h=kl-h=k; assuming an odd number of classes, l=2k+1l=2k+1, then h=kh=k and l−h=k+1l-h=k+1. That is, if the number of classes is 1010, they should be grouped into 55 classes and 55 classes; if the number of classes is 1111, they should be grouped into 55 classes and 66 classes.

  2. Each baseline uses the default parameters set by its authors, and no hyperparameter search was performed. The proposed methods SLtree and ISLtree in this paper also did not undergo hyperparameter tuning; in fact, the node-level SVM parameter optimization implemented in ISLtree should be regarded as an integral part of the proposed model, constituting an adaptive parameter optimization scheme.

  3. The baseline rankings in Table 2 and Table 3 differ because the sets of algorithms in the two tables are different. Table 2 uses SLtree as the control algorithm and excludes ISLtree, with the main purpose of comparing the classification performance of the proposed SLtree method with that of other decision tree methods. Table 3 uses ISLtree as the control algorithm, mainly to compare the degree of improvement of ISLtree over SLtree and to compare its performance with that of other methods. Table 3 is in fact the rank table of all experimental methods.

Thanks for the response. The explanation of the rank differences between Tables 2 and 3 makes sense, and the rounding convention is now clear.

I still have two concerns:

  1. If all valid assignments are enumerated and the centroids have a closed-form solution, the global optimum can be found directly, so I'm not sure what the alternating step adds. Could you clarify which procedure is actually used? Since the number of groupings grows combinatorially, how does construction time scale beyond 18 classes?
  2. The node-level PSO in ISLtree is a form of hyperparameter tuning, while the baselines use default settings. Which data is used to evaluate the PSO objective, and does any experiment isolate the effect of node-specific tuning from that of the optimizer itself? The improvement of ISLtree over SLtree also wasn't statistically significant, which needs some discussion.

We thank the reviewer for this incisive observation, and we agree with it. We address the first question below. With a complete enumeration of valid groupings and a closed-form solution for the centroids, the joint problem min⁡Gmin⁡C∥X−CF⊤∥F2\min_G \min_C \|X - C F^\top\|_F^2 can indeed be evaluated directly by scoring each GG with its closed-form C∗(G)=X⊤(F⊤)+C^*(G)=X^\top(F^\top)^{+}, and the global optimum is then obtained in one pass. In that regime the alternating update adds nothing. The procedure actually used in this work is therefore the exact search over groupings, whose global optimality follows from the completeness of the enumeration rather than from the alternation.

That said, we would like to clarify that we also have a variant that genuinely follows the alternating-optimization idea, and it is this variant that we have in mind as the scalable generalization. Once CC is fixed, the decision unit is the class rather than the individual sample, because the label constraint requires all samples of a class to enter the same child. Each class cc therefore has only two options, with closed-form costs Dc0D_c^0 and Dc1D_c^1 for going left or right, and the total reconstruction error is the sum of Dc0D_c^0 over the classes sent left and Dc1D_c^1 over those sent right. Since the classes are chosen independently, the optimum under the balance constraint is simply to send the hh classes with the smallest Δc=Dc0−Dc1\Delta_c = D_c^0 - D_c^1 to the left branch. This is exactly optimal and requires only sorting, at cost O(llog⁡l)O(l\log l), or O(l)O(l) with linear-time selection, rather than enumerating all (l⌊(l−1)/2⌋)\binom{l}{\lfloor(l-1)/2\rfloor} groupings. Combined with the closed-form centroid update, this gives a block-coordinate descent whose per-node cost is polynomial in the number of classes. The trade-off is a modest loss in accuracy, since it converges to a block-coordinate stationary point rather than the global optimum, and for the small class counts considered here the runtime saving is limited. Because every dataset in this paper has at most 18 classes, the enumerative version is affordable throughout and is the one underlying all reported results. The alternating variant is intended for settings with far larger numbers of classes, where enumeration becomes prohibitive.

We thank the reviewer for these points, and we address the second question below.

The PSO objective at each node is evaluated on the same node-level training data used by SLtree, so the comparison between ISLtree and SLtree is conducted on identical data under the same splitting framework.

We agree that our comparisons do not separate node-specific tuning from the choice of optimizer. ISLtree is not intended to show that PSO is a better optimizer, but to probe the performance ceiling of the nonlinear-SVM splitting strategy when each node is allowed its own (C,γ)(C, \gamma), and the relevant comparison for our contribution is ISLtree versus SLtree under the same framework. A fully factorized study comparing default settings, grid search, and PSO under a matched number of SVM fits would be needed to attribute the gain precisely, and we now state this as a limitation.

We also agree that the advantage of ISLtree over SLtree is modest across the full benchmark, and that its statistical significance is marginal rather than strong. SLtree is now positioned as the recommended default given its much lower training cost, while ISLtree is presented as a performance-ceiling probe preferable when accuracy is the priority and the training budget permits.

Reviewer_KW1AOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a multiclass decision tree that achieves a balanced tree structure through label-constrained K-means clustering and learns nonlinear decision boundaries using support vector machines.

Critical strengths

The paper presents extensive experiments and statistical analyses across more than 40 datasets, using cross-validation and statistical tests.

Critical weaknesses

The paper's main strength is its comprehensive experimental evaluation across 41 datasets. However, ISLtree incurs a high training cost, its performance improvement over SLtree is not statistically significant, and its advantages are inconsistent on complex datasets. More importantly, its major weakness is the lack of novelty. The main contribution is to combine label-constrained K-means clustering, a balanced tree structure, and SVMs, while using PSO to optimize the SVM hyperparameters. Based on the current presentation, the paper appears to be more of a combination and refinement of existing techniques than a genuinely novel method with clear original contributions. In terms of novelty, I do not think this work makes a sufficiently original contribution to warrant publication at ICLR.

Questions for authors

How much computational cost does ISLtree incur to achieve better performance?

3 comments

Thank you for the detailed review. We address the main concerns below. Based on the analysis of actual experimental results, ISLtree requires approximately 10–11 times more training time, in exchange for an average increase of 2.5 percentage points in Accuracy and an average increase of 5.9 percentage points in Macro-F1, with greater benefits on large-scale/imbalanced data, while prediction time remains essentially unchanged.

We thank the reviewer for the careful reading and for acknowledging the breadth of our experimental evaluation.

On computational cost: on average over all datasets, ISLtree requires 319.42 s for training versus 30.16 s for SLtree (about 10.6×), while prediction cost remains low (0.32 ms vs 1.58 ms per sample); the overhead comes from the PSO search at each splitting node. We agree this is a genuine limitation and have addressed it directly. We have added a new subsection (Section 3.3) introducing two accelerated variants, SLtree++ and ISLtree++, which first cluster the training data into blocks of at most StS_t samples and then train the independent subtrees in parallel. As reported in Table 1, SLtree++ cuts average training time from 30.16 s to 0.72 s (97.6%) and prediction time from 1.58 ms to 0.89 ms (43.5%) while improving accuracy (0.8316 → 0.8415) and Macro F1 (0.7199 → 0.7534); ISLtree++ cuts training time from 319.42 s to 6.99 s (97.8%) and prediction time from 0.32 ms to 0.10 ms (69.1%) with only marginal changes in accuracy (0.8562 → 0.8536) and Macro F1 (0.7793 → 0.7711). This makes ISLtree practical on large-scale data.

Regarding the significance of the gain and its inconsistency on complex datasets, we have clarified the role of ISLtree in the revised text: it is not proposed as a universally superior replacement for SLtree, but as an explicit probe of the performance ceiling of the nonlinear-SVM splitting strategy, at the price of training time. SLtree is therefore the recommended default, while ISLtree is preferable when accuracy is the priority and the training budget permits.

On novelty, we respectfully clarify that the contribution is not a mere combination of existing components. The core novelty is a unified optimization formulation of node splitting: we cast the partition problem at each node as a label-constrained K-means-style objective, solved by alternating iteration in which every subproblem is convex or admits a closed-form solution, which yields the class-grouping matrix GG directly and replaces multi-step search or pairwise voting with a single principled procedure. The balance constraint is embedded inside the objective, so the compact, balanced binary topology emerges from optimization itself and requires no pruning to control depth or complexity. The nonlinear SVM boundary and the per-node PSO search are integrated into this same framework, so that hyperparameter adaptation follows each node's local sample distribution rather than a global setting. Finally, the clustering-based pre-partitioning with parameter-free parallel subtree training is, to our knowledge, new for SVM-based decision trees. We have rewritten the Introduction and the contributions list to make these points explicit, and we hope the reviewer finds the originality argument clearer. We thank the reviewer again; these comments have substantially improved the paper.

Thank you to the authors for their detailed responses and clarifications. I maintain my original rating.

Reviewer_tApCOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces a nonlinear SVM decision tree multi-class algorithm, termed SLtree. SLtree is based on the iterative idea of K-means and simultaneously incorporates label constraints into theiterative process, thereby achieving more thorough and comprehensive node splitting. Experimentsdemonstrate that the proposed method performs well across a wide range of domains (41 datasets),with its four average metrics surpassing those of other excellent decision tree multi-class algorithms, which also demonstrates the advancement of this novel node splitting strategy.

Critical strengths
  1. Experiments demonstrate that the proposed method performs well across a wide range of domains (41 datasets) with its four average metrics surpassing those of other excellent decision tree multi-class algorithms, which also demonstrates the advancement of this novel node splitting strategy.
  2. The study further introduces the particle swarm optimization algorithm to tune the hyperparameters of the SVM that controls node splitting, exploring the performance limits of decision tree classification. 3)The proposed ISLtree algorithm not only improves decision tree performance but also performs excellently on imbalanced datasets, complex datasets, and large-scale datasets.
Critical weaknesses

The limitation of the ISLtree method lies in its compexity. Since multiple parameter searches are performed within a single training process, although the classification limits of the nonlinear SVM are fully explored and performance gains are thereby obtained, this comes at thecost of training time.

  1. In the first step of the method, the algorithm requires a balanced partitioning of the categories; however, the authors did not conduct a thorough analysis of how the number of categories affects the algorithm’s complexity. Both theoretical analysis and analysis of experimental runtime are crucial.
  2. The K-means clustering method inherently involves a certain degree of randomness, and the impact of this randomness on classification performance also requires experimentation and analysis.
Questions for authors
  1. In the first step of the method, the algorithm needs to partition the categories in a balanced manner; however, the authors did not fully analyze the impact of the number of categories on the algorithm’s complexity. Please address this in terms of both theoretical analysis and experimental runtime results.
  2. The K-means clustering method inherently involves a certain degree of randomness, and the impact of this randomness on classification performance also requires experimental investigation and analysis. Please address this based on the experimental results.
  3. What is the current scale of data that the algorithm can handle? If the dimensionality of the data features is too high, will the experimental performance decline sharply?
2 comments

Thank you for the detailed review. We address the main concerns below.

  1. The impact of the number of classes on algorithmic complexity mainly lies in computing the GG matrix during node grouping. The code adopts direct enumeration, and the time complexity can be roughly approximated as O(2l)O(2^{l}), where ll is the number of classes. However, this approach was also adopted because only ten of the experimental datasets have more than 10 classes, and the maximum number of classes among them is 18. Considering that when the number of classes is less than 20, direct enumeration is simple and easy to understand and has low complexity, this method was adopted. Other computational methods for solving the GG matrix were also attempted, and experiments verified that there was no significant difference in training time. In fact, when facing datasets with a larger number of classes, the method for computing the GG matrix can be adjusted according to special cases, for example, approximate solution and sorting-based search. Regarding experimental runtime results, due to the influence of dataset size, it is difficult to analyze solely the effect of the number of classes on training runtime. For a rigorous analysis, it would be necessary to find two datasets that differ only in the number of classes while being identical in all other respects and to complete the analysis using them.

  2. The proposed algorithm does not directly use the KK-means algorithm. It only uses its idea of recursive approximation and iterative optimization to solve the GG matrix. The resulting GG matrix is unique and optimal, with no randomness.

  3. The largest completed dataset contains 32,485 instances. Dataset 11 has the highest dimensionality (100). For Dataset 11, as can be seen in the appendix, the experimental performance does not degrade sharply: SLtree and ISLtree achieve accuracies of 0.8669±0.02090.8669\pm0.0209 and 0.8811±0.02930.8811\pm0.0293, respectively, the best among all methods.

We thank the reviewer for these constructive comments again.

Response to the randomness of K-means. We agree that K-means initialization introduces randomness. In our evaluation protocol, each (algorithm, dataset) pair is evaluated by ten runs of five-fold cross-validation (10×5 CV), and K-means is re-executed in every run. Therefore, the reported mean±std already captures the influence of K-means randomness on classification performance, and the relatively small standard deviations and stable rankings indicate that this randomness does not materially affect our conclusions. We have added a clarifying sentence on this protocol in the revised manuscript.

Response to the training-time limitation of ISLtree. We agree that the multiple PSO searches within a single training process make ISLtree costly to train. To address this weakness, we have added a new subsection (Section 3.3) introducing two accelerated variants, SLtree++ and ISLtree++. Specifically, when a node contains more than StS_t samples, the training data are pre-partitioned by one or more K-means runs until every block has at most StS_t samples; the root then has k′k' branches, and the resulting k′k' subtrees are independent, share no parameters, and are trained in parallel. Prediction simply assigns a test sample to its nearest cluster center and then to the corresponding subtree.

As reported in Table 4:

  • SLtree++ reduces the average training time of SLtree from 30.16 s to 0.72 s (a 97.6% reduction) and the average prediction time from 1.58 ms to 0.89 ms, while improving accuracy from 0.8316 to 0.8415 and Macro F1 from 0.7199 to 0.7534.
  • ISLtree++ reduces the average training time of ISLtree from 319.42 s to 6.99 s (a 97.8% reduction) and the average prediction time from 0.32 ms to 0.10 ms, with only a slight accuracy decrease from 0.8562 to 0.8536 and a Macro F1 decrease from 0.7793 to 0.7711.

These results show that the proposed acceleration strategy substantially alleviates the training-time limitation while preserving performance. The default pre-partitioning thresholds are St=500S_t = 500 and St=1000S_t = 1000 for SLtree++ and ISLtree++, respectively; tuning StS_t per dataset is expected to yield further gains. We have revised the abstract and conclusion accordingly.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.