Clustering multi-way data via adaptive subspace iteration

Wei Peng, Tao Li, Bo Shao2008 · DOI

TL;DR

This paper introduces ASI-T, a novel algorithm for clustering multi-way (tensor) data. By adaptively iterating between subspace identification (using 2DSVD) and data clustering (using K-Means), ASI-T effectively captures the rich, multi-dimensional structures inherent in such datasets, outperforming existing methods on both synthetic and real-world benchmarks.

What Problem Does This Paper Address?

Many real-world datasets are inherently multi-dimensional, meaning they can't be adequately represented by a simple table (a two-way matrix). Think of data with dimensions like "users," "items," and "time," or "documents," "features," and "topics." These are called "tensors" or "multi-way arrays." Traditional clustering methods, which typically work on two-way data, often struggle with tensors because they either lose valuable information by flattening the data or fail to exploit the complex interdependencies across all dimensions. Subspace clustering, which aims to find clusters within lower-dimensional representations of the data, has shown promise for two-way data, but extending these techniques to the more complex world of multi-way data has been a significant challenge. This paper tackles this gap by proposing a method that can effectively cluster multi-way data by simultaneously learning both the underlying subspace structure and the cluster assignments.

Methods

The core of the proposed method is ASI-T (Adaptive Subspace Iteration on Tensor). ASI-T is framed as a special adaptation of the High Order SVD (HOSVD) model. Its novelty lies in its iterative, dual approach:

  1. Subspace Identification: It uses a technique related to 2DSVD to identify the relevant subspace structure within the data. This step essentially figures out the most important "directions" or "components" in the tensor that are relevant to the current data clusters.
  2. Data Clustering: Simultaneously, it employs K-Means clustering on the data units (mode 1 of the tensor). This step assigns data points to clusters based on their current representation.

These two steps are performed alternatively and iteratively. The algorithm refines the subspace representation based on the current clusters, and then refines the clusters based on the updated subspace. This adaptive process allows ASI-T to converge to stable clustering partitions and subspace representations. Mathematically, the objective function is designed to minimize the reconstruction error of the tensor while enforcing specific constraints on the learned matrices, effectively linking it to both K-Means and 2DSVD.

Datasets

The authors evaluated ASI-T on:

  • Synthetic Data: Five datasets were generated using an algorithm proposed by Milligan [7] with varying configurations.
  • Real-World Data: Two datasets were extracted from the DBLP computer science bibliography. These are three-way arrays with modes representing "authors," "terms," and "year."
    • DBLP1000 (1000 authors × 1000 terms × 20 years)
    • DBLP100 (100 authors × 200 terms × 20 years)

Key Insights and Ideas

  • Bridging Subspace Clustering and Tensor Decomposition: The paper elegantly connects two powerful data analysis paradigms: subspace clustering (for two-way data) and tensor decomposition (for multi-way data). ASI-T shows how these can be integrated for more effective multi-way clustering.
  • Adaptive Iteration is Key: The success of ASI-T hinges on the alternating optimization of subspace and cluster assignments. This iterative refinement allows the algorithm to adapt to the complex structure of multi-way data, which a single-step approach might miss.
  • Overcoming the Curse of Dimensionality: The authors suggest that ASI-T's ability to learn subspace structures is particularly beneficial for higher-dimensional tensors, where traditional methods might struggle due to the "curse of dimensionality."

Key Results

ASI-T demonstrated superior performance compared to a range of existing methods on both synthetic and real-world datasets.

  • Synthetic Data: ASI-T achieved the best performance across all measures on all synthetic datasets.
  • DBLP Datasets: In Table 1, ASI-T consistently outperformed other methods (including Rank-1 approximation, HOSVD, various K-Means variants, and co-clustering algorithms) on both DBLP100 and DBLP1000 datasets, as measured by ARI (Adjusted Rand Index), ACC (Accuracy), and NMI (Normalized Mutual Information). For instance, on DBLP1000, ASI-T achieved an ARI of 0.657, ACC of 0.825, and NMI of 0.672, which were the highest reported values.
  • Dimensionality Advantage: The paper notes that the advantages of ASI-T become more pronounced in higher dimensions, where it effectively combats the curse of dimensionality.

Limitations and Future Work

  • Computational Complexity: While not explicitly detailed as a limitation, the iterative nature of the algorithm and the use of tensor operations suggest that computational cost could be a factor for extremely large tensors.
  • Choice of K: Like standard K-Means, the performance of ASI-T would likely depend on the pre-specified number of clusters (K).
  • Future Work: The paper implies that ASI-T can be extended to other tensor decomposition models and potentially applied to a wider range of multi-way data applications. The authors also mention that the derivation for ASI-T as an extension of two-way subspace clustering is omitted, suggesting potential for further theoretical exploration.

Summary updated

Abstract

Clustering multi-way data is a very important research topic due to the intrinsic rich structures in real-world datasets. In this paper, we propose the subspace clustering algorithm on multi-way data, called ASI-T (Adaptive Subspace Iteration on Tensor). ASI-T is a special version of High Order SVD (HOSVD), and it simultaneously performs subspace identification using 2DSVD and data clustering using K-Means. The experimental results on synthetic data and real-world data demonstrate the effectiveness of ASI-T.
BibTeX
@misc{peng2008clustering,
  author = {Wei Peng and Tao Li and Bo Shao},
  title = {{Clustering multi-way data via adaptive subspace iteration}},
  year = {2008},
  doi = {10.1145/1458082.1458365},
}
Figure