A new classification method based on Minimum Spanning Trees

• URL: http://arxiv.org/abs/2606.21639v1
• Date: Fri, 19 Jun 2026 17:48:15 GMT
• Title: A new classification method based on Minimum Spanning Trees
• Abstract summary: We propose a classification algorithm based on Minimum Spanning Trees.<n>We introduce a robust version of the method that is also computationally more efficient.<n>We also apply the proposed methodology to a real-world case study involving aircraft trajectories.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Minimum Spanning Trees have been used in unsupervised learning, particularly in clustering tasks, due to their ability to recognize clusters by removing edges that are considered inconsistent in defining those clusters. This paper aims to study the use of Minimum Spanning Trees in supervised learning. Specifically, we propose a classification algorithm based on Minimum Spanning Trees. To improve its performance, we introduce a robust version of the method that is also computationally more efficient. We evaluate the effectiveness of our proposed method through an extensive simulation study. We also apply the proposed methodology to a real-world case study involving aircraft trajectories.

Related papers

• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePO is a self-guided rollout algorithm that views sequence generation as a tree-structured searching process.<n>TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity.
  arXiv  Detail & Related papers  (2025-08-24T16:52:37Z)
• TreeLoRA: Efficient Continual Learning via Layer-Wise LoRAs Guided by a Hierarchical Gradient-Similarity Tree [52.44403214958304]
  In this paper, we introduce TreeLoRA, a novel approach that constructs layer-wise adapters by leveraging hierarchical gradient similarity.<n>To reduce the computational burden of task similarity estimation, we employ bandit techniques to develop an algorithm based on lower confidence bounds.<n> experiments on both vision transformers (ViTs) and large language models (LLMs) demonstrate the effectiveness and efficiency of our approach.
  arXiv  Detail & Related papers  (2025-06-12T05:25:35Z)
• Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
  We propose a Deep Tree-based Retriever (DTR) for efficient recommendation. DTR frames the training task as a softmax-based multi-class classification over tree nodes at the same level. To mitigate the suboptimality induced by the labeling of non-leaf nodes, we propose a rectification method for the loss function.
  arXiv  Detail & Related papers  (2024-08-21T05:09:53Z)
• Learning Decision Trees and Forests with Algorithmic Recourse [11.401006371457436]
  Algorithmic Recourse (AR) aims to provide a recourse action for altering the undesired prediction result given by a model. We formulate the task of learning an accurate classification tree under the constraint of ensuring the existence of reasonable actions for as many instances as possible.
  arXiv  Detail & Related papers  (2024-06-03T08:33:42Z)
• A Novel Memetic Strategy for Optimized Learning of Classification Trees [0.0]
  We propose a novel evolutionary algorithm for the induction of classification trees that exploits a memetic approach that is able to handle datasets with thousands of points. Our procedure combines the exploration of the feasible space of solutions with local searches to obtain structures with generalization capabilities that are competitive with the state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-05-13T16:29:10Z)
• A Mathematical Programming Approach to Optimal Classification Forests [1.0499611180329806]
  This paper introduces Weighted Optimal Classification Forests (WOCFs)<n>WOCFs take advantage of an optimal ensemble of decision trees to derive accurate and interpretable classifiers.<n>Overall, WOCFs complement existing methods such as CART, Optimal Classification Trees, Random Forests and XGBoost.
  arXiv  Detail & Related papers  (2022-11-18T20:33:08Z)
• Semi-supervised Predictive Clustering Trees for (Hierarchical) Multi-label Classification [2.706328351174805]
  We propose a hierarchical multi-label classification method based on semi-supervised learning of predictive clustering trees. We also extend the method towards ensemble learning and propose a method based on the random forest approach.
  arXiv  Detail & Related papers  (2022-07-19T12:49:00Z)
• MCDAL: Maximum Classifier Discrepancy for Active Learning [74.73133545019877]
  Recent state-of-the-art active learning methods have mostly leveraged Generative Adversarial Networks (GAN) for sample acquisition. We propose in this paper a novel active learning framework that we call Maximum Discrepancy for Active Learning (MCDAL) In particular, we utilize two auxiliary classification layers that learn tighter decision boundaries by maximizing the discrepancies among them.
  arXiv  Detail & Related papers  (2021-07-23T06:57:08Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.