Minimum Spanning Trees ensemble framework: A geometric classifier

Classifiers based on the Minimum Spanning Tree (MST) capture complex, non-linear class geometries that elude many standard models, but a single MST is inherently unstable: small changes in the training data can reshape the tree and degrade classification performance. Existing MST-based ensembles address this only partially, either collapsing structural evidence into hard voting decisions or re-analyzing the graph topology at every prediction, limiting scalability and inductive capability. To resolve both limitations, a two-phase framework is introduced that permanently decouples topological analysis from inference. In Phase I, an ensemble of MSTs is built on subsamples drawn with a randomly perturbed class ratio, exposing it to diverse density regimes. A local model is then trained on the pure instances of each subsample, identified through the label homogeneity of the MST neighborhood, and used to infer the affinity of the remaining ambiguous ones, without manual calibration of where the ensemble should specialize. Averaging these local affinities across the ensemble yields a continuous, per-instance affinity score quantifying class membership, replacing hard voting with a graded, ensemble-aggregated measure. In Phase II, this pre-computed score is reused for prediction through interchangeable strategies, such as k-nearest-neighbor interpolation or a dedicated regression model, without ever reconstructing the graph. This separation makes the framework modular, adapting the prediction mechanism to the problem while preserving the topological sensitivity of the underlying MST ensemble.