Clustering Boolean tensors
From MaRDI portal
Abstract: Tensor factorizations are computationally hard problems, and in particular, are often significantly harder than their matrix counterparts. In case of Boolean tensor factorizations -- where the input tensor and all the factors are required to be binary and we use Boolean algebra -- much of that hardness comes from the possibility of overlapping components. Yet, in many applications we are perfectly happy to partition at least one of the modes. In this paper we investigate what consequences does this partitioning have on the computational complexity of the Boolean tensor factorizations and present a new algorithm for the resulting clustering problem. This algorithm can alternatively be seen as a particularly regularized clustering algorithm that can handle extremely high-dimensional observations. We analyse our algorithms with the goal of maximizing the similarity and argue that this is more meaningful than minimizing the dissimilarity. As a by-product we obtain a PTAS and an efficient 0.828-approximation algorithm for rank-1 binary factorizations. Our algorithm for Boolean tensor clustering achieves high scalability, high similarity, and good generalization to unseen data with both synthetic and real-world data sets.
Recommendations
- Approximation algorithms for tensor clustering
- Dynamic tensor clustering
- Tensor clustering with planted structures: statistical optimality and computational limits
- Toward quality assessment of Boolean matrix factorizations
- Multiscale co-clustering for tensor data based on canonical polyadic decomposition and slice-wise factorization
Cites work
- Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
- Approximation algorithms for tensor clustering
- Closed and noise-tolerant patterns in \(n\)-ary relations
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- INDCLAS: a three-way hierarchical classes model
- Modeling by shortest data description
- On Tensors, Sparsity, and Nonnegative Factorizations
- On Two Segmentation Problems
- Optimal factorization of three-way binary data using triadic concepts
- Segmentation problems
- Tensor Decompositions and Applications
- Unsupervised methods for determining object and relation synonyms on the web
- Upper bound for the approximation ratio of a class of hypercube segmentation algorithms
Cited in
(3)
This page was built for publication: Clustering Boolean tensors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1715898)
