Adapting the Gini Impurity Criterion for Splitting and Merging Strategies in Extended Automata Learning

Abstract

Learning Extended Deterministic Finite Automata (EDFAs) from traces provides an interpretable way to model sequential behavior, but the quality of the learned automaton strongly depends on the heuristic evaluation function used during state refinement. This paper investigates a new heuristic evaluation function for EDSM-based EDFA learning, inspired by the Gini impurity criterion used in CART decision trees. Three Gini-based variants are introduced: a local variant that evaluates impurity at the immediate split, a future-state variant that evaluates impurity over the affected future states, and a weighted variant that uses a parameter λ to balance the influence of final and intermediate tails.

The variants are implemented in FlexFringe and evaluated on several time-series classification datasets and the CTU-13 network traffic dataset. Hyperparameters are selected using validation data, and final performance is measured on test sets using accuracy, specificity, EDFA size, and final-state consistency. The results show that Gini-based refinement can improve the structural quality of learned EDFAs compared to RTI by producing smaller automata and more class-consistent final states while maintaining competitive accuracy. The weighted variant achieves the best average EDFA accuracy among the proposed variants, although among the Gini variants, higher consistency often comes at the cost of larger automata. These findings suggest that Gini impurity is a promising basis for heuristic evaluation in EDSM-based EDFA learning, especially when interpretable and class-consistent automata are desired