Scaling log-linear analysis to datasets with thousands of variables by François Petitjean and Geoffrey I. Webb.
Abstract:
Association discovery is a fundamental data mining task. The primary statistical approach to association discovery between variables is log-linear analysis. Classical approaches to log-linear analysis do not scale beyond about ten variables. We have recently shown that, if we ensure that the graph supporting the log-linear model is chordal, log-linear analysis can be applied to datasets with hundreds of variables without sacrificing the statistical soundness [21]. However, further scalability remained limited, because state-of-the-art techniques have to examine every edge at every step of the search. This paper makes the following contributions: 1) we prove that only a very small subset of edges has to be considered at each step of the search; 2) we demonstrate how to efficiently find this subset of edges and 3) we show how to efficiently keep track of the best edges to be subsequently added to the initial model. Our experiments, carried out on real datasets with up to 2000 variables, show that our contributions make it possible to gain about 4 orders of magnitude, making log-linear analysis of datasets with thousands of variables possible in seconds instead of days.
The authors reduce the number of edges required to be examined in one example from 10,000,000 to 10,000, with corresponding savings in computation time. That was not an artifact of the data set but has been generalized by the authors and released as open source code: Chordalysis (GitHub).
If you prefer numbers, the analysis of a data set with 10,000,000 edges went from 39 hours to 27 seconds, a speedup of more than 5200X.
Definitely an addition to your data mining toolkit!