Please use this identifier to cite or link to this item: http://repositorio.inesctec.pt/handle/123456789/6955
Title: FastStep: Scalable Boolean Matrix Decomposition
Authors: Miguel Ramos Araújo
Pedro Manuel Ribeiro
Faloutsos,C
Issue Date: 2016
Abstract: 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.
URI: http://repositorio.inesctec.pt/handle/123456789/6955
http://dx.doi.org/10.1007/978-3-319-31753-3_37
metadata.dc.type: conferenceObject
Publication
Appears in Collections:CRACS - Articles in International Conferences

Files in This Item:
File Description SizeFormat 
P-00K-BG7.pdf1.02 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.