ModalFP-Growth: Efficient Extraction of Modal Association Rules from Non-Tabular Data

This paper explores the extraction of modal association rules from non-tabular data using a novel algorithm, ModalFP-Growth. By extending the FP-Growth algorithm to modal logic, ModalFP-Growth processes instances represented as Kripke models, facilitating efficient rule extraction from temporal, spatial, and spatio-temporal datasets. Each instance is transformed into a tabular form where worlds correspond to rows and literals to columns, enabling the application of the original FP-Growth. The algorithm, then, aggregates locally frequent itemsets from individual instances to identify globally supported itemsets across the dataset. We prove the soundness and completeness of ModalFP-Growth, ensuring that all and only frequent itemsets are included in the final output. Additionally, we present an open-source implementation within the Sole learning and reasoning suite. Experimental evaluations using Halpern and Shoham’s Interval Temporal Logic on a public temporal dataset demonstrate the algorithm’s practical efficiency and the interpretability of the extracted rules.