Generating CHAID Trees on Large and Distributed Data

• Activity Number: 245
• Type: Contributed
• Date/Time: Monday, August 5, 2013 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Damir Spisic*+ and Jing Xu and Xue Ying Zhang
• Companies: IBM and IBM and IBM
• Keywords: CHAID ; distributed data ; MapReduce

Abstract

CHAID is one of the most established and popular algorithms for building tree models. Target variable can be either continuous or categorical while the predictors must be all categorical. Any continuous predictors are binned before using them in the model. When generating the model, each node can be split into multiple children nodes. The original algorithm is effective for small and medium data sets. However, generating tree models on distributed data containing large number of records and predictors requires a new approach. We present a distributed algorithm for CHAID tree implemented in the MapReduce model of distributed computation. It executes the same number of data passes as the original approach, but the computation in each data pass is fully parallelized taking advantage of all available computational resources. We demonstrate scalability of the distributed algorithm through experiments on a Hadoop cluster.