This was my PhD project at Cadi Ayyad University in Marrakech, from 2014 to 2018. It asked a practical question: when a data-mining algorithm produces thousands of patterns from a large database, how does a decision-maker find the few that matter? The application was road safety in Morocco, using large databases of road accidents.
The problem
Association rules are patterns of the form “if A and B, then often C”: for example, at night, on a wet road outside town, accidents are more often severe. They are easy to read and useful for understanding data, which makes them popular in knowledge discovery.
Their weakness is volume. On real datasets, a rule-mining algorithm returns thousands of rules, many redundant or uninteresting, and dozens of quality measures (support, confidence, lift and many more) that often disagree about which rules are best. The size of transportation data adds a computational challenge of its own.
The approach
The key idea was to bring decision analysis into the data-mining process:
- Rules as options, measures as criteria. Instead of picking one quality measure, the methods treat each rule as an option and each quality measure as a criterion, then use multi-criteria decision analysis (MCDA), notably the ELECTRE TRI method, to rank and sort the rules, taking the decision-maker’s preferences into account.
- Mining at scale. Rules are extracted from big data with the FP-growth algorithm on Apache Spark, and prediction models such as decision trees run on the same platform.
- A multi-agent design models the steps of the extraction process as cooperating agents.
- Spatial patterns. A later extension used fuzzy set theory to mine spatial association rules from accident locations.
Results
- New approaches for selecting relevant association rules with multi-criteria analysis, published in the Journal of Big Data, the European Transport Research Review, the Vietnam Journal of Computer Science and the International Journal of Computational Science and Engineering.
- DM-MCDA, an open-source web platform that combines association rules, multi-criteria analysis and time series to identify accident hot spots, published in SoftwareX with its code on GitHub, and a web platform for mining and ranking association rules presented at ECIR 2020.
- The PhD thesis, Fouille de données et analyse de qualité des règles d’association dans les bases de données massives : application dans le domaine de la sécurité routière, available as a PDF and on HAL.
Multi-criteria decision analysis has stayed with me since: my Python library mcdakit and the blog series on multi-criteria decisions build on this work.