Bayesian hierarchical cross-clustering

Most clustering algorithms assume that all dimensions of the data can be described by a single structure. Cross-clustering (or multi-view clustering) allows multiple structures, each applying to a subset of the dimen-sions. We present a novel approach to cross-clustering, based on approximating the so-lution to a Cross Dirichlet Process mixture (CDPM) model [Shafto et al., 2006, Mans-inghka et al., 2009]. Our bottom-up, de-terministic approach results in a hierarchi-cal clustering of dimensions, and at each node, a hierarchical clustering of data points. We also present a randomized approxima-tion, based on a truncated hierarchy, that scales linearly in the number of levels. Re-sults on synthetic and real-world data sets demonstrate that the cross-clustering based algorithms perform as well or better than the clustering based algorithms, our determinis-tic approaches models perform as well as the MCMC-based CDPM, and the randomized approximation provides a remarkable speed-up relative to the full deterministic approxi-mation with minimal cost in predictive error.