Random intersection trees

By Rajen Dinesh Shah, Nicolai Meinshausen. 2013

48 citations recorded by the source corpus.

Finding interactions between variables in large and high-dimensional data sets is often a serious computational challenge. Most approaches build up interaction sets incrementally, adding variables in a greedy fashion. The drawback is that potentially informative high-order interactions may be overlooked. Here, we propose an alternative approach for classification problems with binary predictor variables, called Random Intersection Trees. It works by starting with a maximal interaction that includes all variables, and then gradually removing variables if they fail to appear in randomly chosen observations of a class of interest. We show that informative interactions are retained with high probability, and the computational complexity of our procedure is of order pκ, where p is the number of predictor variables. The value of κ can reach values as low as 1 for very sparse data; in many more general settings, it will still beat the exponent s obtained when using a brute force search constrained to order s interactions. In addition, by using some new ideas based on min-wise hash schemes, we are able to further reduce the computational cost. Interactions found by our algorithm can be used for predictive modelling in various forms, but they are also often of interest in their own right as useful characterisations of what distinguishes a certain class from others.

Subfields: Artificial Intelligence, Information Systems, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Signal Processing

Citations in the corpus

Iterative random forests to discover predictive and stable high-order interactions (2017, methodology): “We briefly present the basic RIT algorithm and refer readers to the original paper (20) for a complete description.”
A Brief Review of Random Forests for Water Scientists and Practitioners and Their Recent History in Water Resources (2019, background): “, Shah and Meinshausen [101], Basu et al.”