{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:19:49Z","timestamp":1760170789641,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>Knowledge discovery from data is an inherently iterative process. That is, what we know about the data greatly determines our expectations, and therefore, what results we would find interesting and\/or surprising. Given new knowledge about the data, our expectations will change. Hence, in order to avoid redundant results, knowledge discovery algorithms ideally should follow such an iterative updating procedure.<\/jats:p>\n          <jats:p>With this in mind, we introduce a well-founded approach for succinctly summarizing data with the most informative itemsets; using a probabilistic maximum entropy model, we iteratively find the itemset that provides us the most novel information\u2014that is, for which the frequency in the data surprises us the most\u2014and in turn we update our model accordingly. As we use the maximum entropy principle to obtain unbiased probabilistic models, and only include those itemsets that are most informative with regard to the current model, the summaries we construct are guaranteed to be both descriptive and nonredundant.<\/jats:p>\n          <jats:p>\n            The algorithm that we present, called mtv, can either discover the top-\n            <jats:italic>k<\/jats:italic>\n            most informative itemsets, or we can employ either the Bayesian Information Criterion (bic) or the Minimum Description Length (mdl) principle to automatically identify the set of itemsets that together summarize the data well. In other words, our method will \u201ctell you what you need to know\u201d about the data. Importantly, it is a one-phase algorithm: rather than picking itemsets from a user-provided candidate set, itemsets and their supports are mined on-the-fly. To further its applicability, we provide an efficient method to compute the maximum entropy distribution using Quick Inclusion-Exclusion.\n          <\/jats:p>\n          <jats:p>Experiments on our method, using synthetic, benchmark, and real data, show that the discovered summaries are succinct, and correctly identify the key patterns in the data. The models they form attain high likelihoods, and inspection shows that they summarize the data well with increasingly specific, yet nonredundant itemsets.<\/jats:p>","DOI":"10.1145\/2382577.2382580","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Summarizing data succinctly with the most informative itemsets"],"prefix":"10.1145","volume":"6","author":[{"given":"Michael","family":"Mampaey","sequence":"first","affiliation":[{"name":"University of Antwerp, Antwerp, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jilles","family":"Vreeken","sequence":"additional","affiliation":[{"name":"University of Antwerp, Antwerp, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolaj","family":"Tatti","sequence":"additional","affiliation":[{"name":"University of Antwerp, Antwerp, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,12,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275490"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jbi.2004.08.009"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021571501451"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312241"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253327"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11733492_6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-006-0054-6"},{"key":"e_1_2_1_8_1","unstructured":"Cover T. M. and Thomas J. A. 2006. Elements of Information Theory. Wiley-Interscience New York.   Cover T. M. and Thomas J. A. 2006. Elements of Information Theory. Wiley-Interscience New York."},{"key":"e_1_2_1_9_1","unstructured":"Cowell R. G. Dawid A. P. Lauritzen S. L. and Spiegelhalter D. J. 1999. Probabilistic networks and expert systems. In Statistics for Engineering and Information Science M. Jordan S. L. L. nad Jeral F. Lawless and V. Nair Eds. Springer.  Cowell R. G. Dawid A. P. Lauritzen S. L. and Spiegelhalter D. J. 1999. Probabilistic networks and expert systems. In Statistics for Engineering and Information Science M. Jordan S. L. L. nad Jeral F. Lawless and V. Nair Eds. Springer."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996454"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177692379"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020497"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0209-3"},{"key":"e_1_2_1_14_1","unstructured":"Frank A. and Asuncion A. 2010. UCI machine learning repository. http:\/\/archive.ics.uci.edu\/ml.  Frank A. and Asuncion A. 2010. UCI machine learning repository. http:\/\/archive.ics.uci.edu\/ml."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3120747.3120794"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0319-7"},{"volume-title":"Proceedings of Discovery Science Conference. 278--289","author":"Geerts F.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Gelman A. Carlin J. Stern H. and Rubin D. 2004. Bayesian Data Analysis. CRC Press.  Gelman A. Carlin J. Stern H. and Rubin D. 2004. Bayesian Data Analysis. CRC Press.","DOI":"10.1201\/9780429258480"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132960.1132963"},{"volume-title":"Proceedings of the 82nd Annual Transportation Research Board. 1--18","author":"Geurts K.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297332.1297338"},{"key":"e_1_2_1_22_1","unstructured":"Goethals B. and Zaki M. 2004. Frequent itemset mining dataset repository (FIMI). http:\/\/fimi.ua.ac.be\/.  Goethals B. and Zaki M. 2004. Frequent itemset mining dataset repository (FIMI). http:\/\/fimi.ua.ac.be\/."},{"volume-title":"Advances in Minimum Description Length","author":"Gr\u00fcnwald P.","key":"e_1_2_1_23_1","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1114.001.0001"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Gr\u00fcnwald P. 2007. The Minimum Description Length Principle. MIT Press.  Gr\u00fcnwald P. 2007. The Minimum Description Length Principle. MIT Press.","DOI":"10.7551\/mitpress\/4643.001.0001"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557065"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-2699.2006.01664.x"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014074"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1982.12425"},{"volume-title":"Proceedings of the 10th SIAM International Conference on Data Mining (SDM)","author":"Kontonasios K.-N.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Li M. and Vit\u00e1nyi P. 1993. An Introduction to Kolmogorov Complexity and its Applications. Springer.   Li M. and Vit\u00e1nyi P. 1993. An Introduction to Kolmogorov Complexity and its Applications. Springer.","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020499"},{"volume-title":"Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD). Springer, 321--336","author":"Mampaey M.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","unstructured":"Mitchell-Jones A. Amori G. Bogdanowicz W. Krystufek B. Reijnders P. H. Spitzenberger F. Stubbe M. Thissen J. Vohralik V. and Zima J. 1999. The Atlas of European Mammals. Academic Press.  Mitchell-Jones A. Amori G. Bogdanowicz W. Krystufek B. Reijnders P. H. Spitzenberger F. Stubbe M. Thissen J. Vohralik V. and Zima J. 1999. The Atlas of European Mammals. Academic Press."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1038\/sj.onc.1209717"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557092"},{"volume-title":"Proceedings of the 7th International Conference on Database Theory (ICDT). ACM, 398--416","author":"Pasquier N.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0005-1098(78)90005-5"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176344136"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.ps.46.020195.003021"},{"volume-title":"Proceedings of the 11th SIAM International Conference on Data Mining (SDM). SIAM, 558--569","author":"Siebes A.","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972764.35"},{"volume-title":"Slim: Directly mining descriptive patterns. In Proceedings of the 12th SIAM International Conference on Data Mining (SDM)","year":"2012","author":"Smets K.","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775053"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.02.003"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-008-0128-4"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835843"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/3121525.3121557"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0188-4"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jbi.2010.12.001"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.25"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0202-x"},{"key":"e_1_2_1_52_1","unstructured":"Wallace C. 2005. Statistical and Inductive Inference by Minimum Message Length. Springer.   Wallace C. 2005. Statistical and Inductive Inference by Minimum Message Length. Springer."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022646101185"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150495"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5006-x"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644873.1644876"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081912"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2382577.2382580","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2382577.2382580","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:38Z","timestamp":1750239278000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2382577.2382580"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2382577.2382580"],"URL":"https:\/\/doi.org\/10.1145\/2382577.2382580","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2011-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}