FastStep: Scalable Boolean Matrix Decomposition

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2016

Autores

araujo, mr (Autor) Outra; Pedro Ribeiro (Autor) FCUP; Faloutsos, C (Autor) Outra

Ata de Conferência Internacional

Título: ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PAKDD 2016, PT I

Páginas: 461-473

20th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)

Univ Auckland, Auckland, NEW ZEALAND, APR 19-22, 2016

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 5 Citações

Outras Informações

ID Authenticus: P-00K-BG7

DOI: 10.1007/978-3-319-31753-3_37

Abstract (EN): Matrix Decomposition methods are applied to a wide range of tasks, such as data denoising, dimensionality reduction, co-clustering and community detection. However, in the presence of boolean inputs, common methods either do not scale or do not provide a boolean reconstruction, which results in high reconstruction error and low interpretability of the decomposition. We propose a novel step decomposition of boolean matrices in non-negative factors with boolean reconstruction. By formulating the problem using threshold operators and through suitable relaxation of this problem, we provide a scalable algorithm that can be applied to boolean matrices with millions of non-zero entries. We show that our method achieves significantly lower reconstruction error when compared to standard state of the art algorithms. We also show that the decomposition keeps its interpretability by analyzing communities in a flights dataset (where the matrix is interpreted as a graph in which nodes are airports) and in a movie-ratings dataset with 10 million non-zeros.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 13