English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Clustering Boolean Tensors

Metzler, S., & Miettinen, P. (2015). Clustering Boolean Tensors. Retrieved from http://arxiv.org/abs/1501.00696.

Item is

Basic

show hide
Genre: Paper
Latex : Clustering {Boolean} Tensors

Files

show Files
hide Files
:
arxiv:1501.00696.pdf (Preprint), 692KB
Name:
arxiv:1501.00696.pdf
Description:
File downloaded from arXiv at 2015-01-08 15:14
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Metzler, Saskia1, Author           
Miettinen, Pauli1, Author           
Affiliations:
1Databases and Information Systems, MPI for Informatics, Max Planck Society, ou_24018              

Content

show
hide
Free keywords: Computer Science, Numerical Analysis, cs.NA,Computer Science, Data Structures and Algorithms, cs.DS
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2015-01-042015
 Publication Status: Published online
 Pages: 21 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1501.00696
URI: http://arxiv.org/abs/1501.00696
BibTex Citekey: metzler15clustering:arxiv
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show