Adaptive Options for Decision Trees in Evolving Data Stream Classification

Abstract

Decision trees are fundamental components of data stream mining frameworks and pipelines. However, their inherent instability - where small variations in training data can lead to significant structural changes- has motivated research into methods that either (i) mitigate this instability or (ii) exploit it for improved performance. Option trees provide an alternative approach to instability reduction by allowing non-leaf nodes to have multiple subtrees as child nodes. This enables instances to traverse multiple paths within a single decision tree structure, offering greater processing time and memory efficiency compared to ensemble methods–key advantages for streaming data mining, where data arrives continuously and potentially without bounds. This paper introduces LASTO, an algorithm with adaptive mechanisms for splitting and dynamically adding option nodes. Our primary contribution lies in the option node addition mechanism, where change detectors monitor branch performance and introduce option nodes when a decline in predictive quality is observed. An option node is only added if the split gain surpasses that of the previous split, ensuring its necessity and effectiveness. Experimental results demonstrate that LASTO achieves statistically significant differences in predictive performance while maintaining computational efficiency comparable to state-of-the-art decision trees for data stream classification.