2011 ModelOrderSelectionforBooleanMa

• (Miettinen & Vreeken, 2011) ⇒ Pauli Miettinen, and Jilles Vreeken. (2011). “Model Order Selection for Boolean Matrix Factorization.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020424

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Model+Order+Selection+for+Boolean+Matrix+Factorization
• http://dl.acm.org/citation.cfm?id=2020408.2020424&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; boolean matrix factorizations; data mining; experimentation; matrix decompositions; matrix factorizations; minimum description length principle; model order selection; model selection; theory

Abstract

Matrix factorizations - where a given data matrix is approximated by a product of two or more factor matrices - are powerful data mining tools. Among other tasks, matrix factorizations are often used to separate global structure from noise. This, however, requires solving the `model order selection problem' of determining where fine-grained structure stops, and noise starts, i.e., what is the proper size of the factor matrices.

Boolean matrix factorization (BMF) - where data, factors, and matrix product are Boolean - has received increased attention from the data mining community in recent years. The technique has desirable properties, such as high interpretability and natural sparsity. But so far no method for selecting the correct model order for BMF has been available.

In this paper we propose to use the Minimum Description Length (MDL) principle for this task. Besides solving the problem, this well-founded approach has numerous benefits, e.g., it is automatic, does not require a likelihood function, is fast, and, as experiments show, is highly accurate.

We formulate the description length function for BMF in general - making it applicable for any BMF algorithm. We extend an existing algorithm for BMF to use MDL to identify the best Boolean matrix factorization, analyze the complexity of the problem, and perform an extensive experimental evaluation to study its behavior.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 ModelOrderSelectionforBooleanMa	Pauli Miettinen Jilles Vreeken			Model Order Selection for Boolean Matrix Factorization				10.1145/2020408.2020424		2011