{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T07:04:06Z","timestamp":1790233446405,"version":"4.1.0"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,10,7]],"date-time":"2014-10-07T00:00:00Z","timestamp":1412640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Cluster of Excellence \u201cMultimodal Computing and Interaction\u201d within the Excellence Initiative of the German Federal Government"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2014,10,7]]},"abstract":"<jats:p>Matrix factorizations\u2014where a given data matrix is approximated by a product of two or more factor matrices\u2014are powerful data mining tools. Among other tasks, matrix factorizations are often used to separate global structure from noise. This, however, requires solving the \u201cmodel order selection problem\u201d of determining the proper rank of the factorization, that is, to answer where fine-grained structure stops, and where noise starts.<\/jats:p>\n                  <jats:p>Boolean Matrix Factorization (BMF)\u2014where data, factors, and matrix product are Boolean\u2014has in recent years received increased attention from the data mining community. The technique has desirable properties, such as high interpretability and natural sparsity. Yet, so far no method for selecting the correct model order for BMF has been available. In this article, we propose the use of the Minimum Description Length (MDL) principle for this task. Besides solving the problem, this well-founded approach has numerous benefits; for example, it is automatic, does not require a likelihood function, is fast, and, as experiments show, is highly accurate.<\/jats:p>\n                  <jats:p>We formulate the description length function for BMF in general\u2014making it applicable for any BMF algorithm. We discuss how to construct an appropriate encoding: starting from a simple and intuitive approach, we arrive at a highly efficient data-to-model--based encoding for BMF. 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.<\/jats:p>","DOI":"10.1145\/2601437","type":"journal-article","created":{"date-parts":[[2014,11,4]],"date-time":"2014-11-04T08:18:31Z","timestamp":1415089111000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["MDL4BMF"],"prefix":"10.1145","volume":"8","author":[{"given":"Pauli","family":"Miettinen","sequence":"first","affiliation":[{"name":"Max-Planck Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jilles","family":"Vreeken","sequence":"additional","affiliation":[{"name":"Max-Planck Institute for Informatics, Saarland University, University of Antwerp, Antwerp, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,10,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396816"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276313"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.05.002"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-006-0054-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1207\/s15327906mbr0102_10"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-006-0039-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.844059"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory. Wiley-Interscience New York.   Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory. Wiley-Interscience New York.","DOI":"10.1002\/047174882X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0209-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02294218"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2135\/cropsci2003.8650"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/09296179708590082"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1076\/jqul.7.3.227.4109"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-006-0057-3"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 9th International Conference on Uncertainty in Artificial Intelligence (UAI'93)","author":"Fayyad Usama"},{"key":"e_1_2_1_16_1","unstructured":"Mikael Fortelius and others. 2003. Neogene of the Old World Database of Fossil Mammals (NOW). Available at http:\/\/www.helsinki.fi\/science\/now\/.  Mikael Fortelius and others. 2003. Neogene of the Old World Database of Fossil Mammals (NOW). Available at http:\/\/www.helsinki.fi\/science\/now\/."},{"key":"e_1_2_1_17_1","unstructured":"A. Frank and A. Asuncion. 2010. UCI Machine Learning Repository. Available at http:\/\/archive.ics.uci.edu\/ml.  A. Frank and A. Asuncion. 2010. UCI Machine Learning Repository. Available at http:\/\/archive.ics.uci.edu\/ml."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD'11)","author":"Frank Mario"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0319-7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30214-8_22"},{"key":"e_1_2_1_21_1","unstructured":"Gene H. Golub and Charles F. Van Loan. 1996. Matrix Computations. Johns Hopkins University Press.  Gene H. Golub and Charles F. Van Loan. 1996. Matrix Computations. Johns Hopkins University Press."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Peter Gr\u00fcnwald. 2007. The Minimum Description Length Principle. MIT Press.  Peter Gr\u00fcnwald. 2007. The Minimum Description Length Principle. MIT Press.","DOI":"10.7551\/mitpress\/4643.001.0001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.49"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557069"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.14"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287435"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-009-0137-2"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"M. Li and P. Vit\u00e1nyi. 1993. An Introduction to Kolmogorov Complexity and Its Applications. Springer.   M. Li and P. Vit\u00e1nyi. 1993. An Introduction to Kolmogorov Complexity and Its Applications. Springer.","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497438"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.15"},{"key":"e_1_2_1_31_1","unstructured":"Claudio Lucchese Salvatore Orlando and R. Perego. 2014. A unifying framework for mining approximate top-k binary patterns. IEEE Transactions on Knowledge and Data Engineering (2014). In press.  Claudio Lucchese Salvatore Orlando and R. Perego. 2014. A unifying framework for mining approximate top-k binary patterns. IEEE Transactions on Knowledge and Data Engineering (2014). In press."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382577.2382580"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.05.007"},{"key":"e_1_2_1_34_1","unstructured":"Pauli Miettinen. 2009. Matrix Decomposition Methods for Data Mining: Computational Complexity and Algorithms. Ph.D. Dissertation. University of Helsinki.  Pauli Miettinen. 2009. Matrix Decomposition Methods for Data Mining: Computational Complexity and Algorithms. Ph.D. Dissertation. University of Helsinki."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.93"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.82"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489247.2489250"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.53"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020424"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 13th Annual Conference on Neural Information Processing Systems (NIPS'01)","author":"Minka T. P.","year":"2001"},{"key":"e_1_2_1_41_1","unstructured":"A. J. Mitchell-Jones G. Amori W. Bogdanowicz B. Krystufek P. J. H. Reijnders F. Spitzenberger M. Stubbe J. B. M. Thissen V. Vohralik and J. Zima. 1999. The Atlas of European Mammals. Academic Press.  A. J. Mitchell-Jones G. Amori W. Bogdanowicz B. Krystufek P. J. H. Reijnders F. Spitzenberger M. Stubbe J. B. M. Thissen V. Vohralik and J. Zima. 1999. The Atlas of European Mammals. Academic Press."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0329-5"},{"key":"e_1_2_1_43_1","first-page":"17","article-title":"A survey of clique and biclique coverings and factorizations of (0, 1)-matrices","volume":"14","author":"Monson Sylvia D.","year":"1995","journal-title":"Bulletin of the ICA"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1038\/sj.onc.1209717"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(78)90088-3"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1983.1095823"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-AOAS227"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/env.3170050203"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/645503.656256"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2007.12.030"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90010-2"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0005-1098(78)90005-5"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176346150"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 9th International Workshop on Artificial Intelligence and Statistics.","author":"Schein Andrew I."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00599-2_68"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176344136"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0505-x"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972764.35"},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","unstructured":"David Skillicorn. 2007. Understanding Complex Datasets: Data Mining with Matrix Decompositions. Chapman & Hall\/CRC Press.  David Skillicorn. 2007. Understanding Complex Datasets: Data Mining with Matrix Decompositions. Chapman & Hall\/CRC Press.","DOI":"10.1201\/9781584888338"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.21"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553498"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.167"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.39"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1266840.1266870"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.838346"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.40"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0202-x"},{"key":"e_1_2_1_68_1","unstructured":"C. S. Wallace. 2005. Statistical and Inductive Inference by Minimum Message Length. Springer-Verlag.   C. S. Wallace. 2005. Statistical and Inductive Inference by Minimum Message Length. Springer-Verlag."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150495"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/1032649.1033460"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0203-9"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401981"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.2307\/2987988"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-009-0145-2"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2005.09.010"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601437","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2601437","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:00:53Z","timestamp":1750262453000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601437"}},"subtitle":["Minimum Description Length for Boolean Matrix Factorization"],"short-title":[],"issued":{"date-parts":[[2014,10,7]]},"references-count":75,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,10,7]]}},"alternative-id":["10.1145\/2601437"],"URL":"https:\/\/doi.org\/10.1145\/2601437","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,7]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}