TY - JOUR
T1 - From K-means to higher-way co-clustering
T2 - multilinear decomposition with sparse latent factors
AU - Papalexakis, Evangelos E.
AU - D. Sidiropoulos, Nicholas
AU - Bro, Rasmus
PY - 2013
Y1 - 2013
N2 - Co-clustering is a generalization of unsupervised clustering that has recently drawn renewed attention, driven by emerging data mining applications in diverse areas. Whereas clustering groups entire columns of a data matrix, co-clustering groups columns over select rows only, i.e., it simultaneously groups rows and columns. The concept generalizes to data 'boxes' and higher-way tensors, for simultaneous grouping along multiple modes. Various co-clustering formulations have been proposed, but no workhorse analogous to $K$-means has emerged. This paper starts from $K$- means and shows how co-clustering can be formulated as a constrained multilinear decomposition with sparse latent factors. For three-and higher-way data, uniqueness of the multilinear decomposition implies that, unlike matrix co-clustering, it is possible to unravel a large number of possibly overlapping co-clusters. A basic multi-way co-clustering algorithm is proposed that exploits multilinearity using Lasso-type coordinate updates. Various line search schemes are then introduced to speed up convergence, and suitable modifications are proposed to deal with missing values. The imposition of latent sparsity pays a collateral dividend: it turns out that sequentially extracting one co-cluster at a time is almost optimal, hence the approach scales well for large datasets. The resulting algorithms are benchmarked against the state-of-art in pertinent simulations, and applied to measured data, including the ENRON e-mail corpus.
AB - Co-clustering is a generalization of unsupervised clustering that has recently drawn renewed attention, driven by emerging data mining applications in diverse areas. Whereas clustering groups entire columns of a data matrix, co-clustering groups columns over select rows only, i.e., it simultaneously groups rows and columns. The concept generalizes to data 'boxes' and higher-way tensors, for simultaneous grouping along multiple modes. Various co-clustering formulations have been proposed, but no workhorse analogous to $K$-means has emerged. This paper starts from $K$- means and shows how co-clustering can be formulated as a constrained multilinear decomposition with sparse latent factors. For three-and higher-way data, uniqueness of the multilinear decomposition implies that, unlike matrix co-clustering, it is possible to unravel a large number of possibly overlapping co-clusters. A basic multi-way co-clustering algorithm is proposed that exploits multilinearity using Lasso-type coordinate updates. Various line search schemes are then introduced to speed up convergence, and suitable modifications are proposed to deal with missing values. The imposition of latent sparsity pays a collateral dividend: it turns out that sequentially extracting one co-cluster at a time is almost optimal, hence the approach scales well for large datasets. The resulting algorithms are benchmarked against the state-of-art in pertinent simulations, and applied to measured data, including the ENRON e-mail corpus.
U2 - 10.1109/tsp.2012.2225052
DO - 10.1109/tsp.2012.2225052
M3 - Journal article
SN - 1053-587X
VL - 61
SP - 493
EP - 506
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
IS - 2
ER -