{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:18:24Z","timestamp":1740122304856,"version":"3.37.3"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"CIFAR AI Chairs program"},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s10601-023-09348-1","type":"journal-article","created":{"date-parts":[[2023,7,8]],"date-time":"2023-07-08T05:01:26Z","timestamp":1688792486000},"page":"166-202","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["SAT-based optimal classification trees for non-binary data"],"prefix":"10.1007","volume":"28","author":[{"given":"Pouya","family":"Shati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5767-6683","authenticated-orcid":false,"given":"Eldan","family":"Cohen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheila A.","family":"McIlraith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,8]]},"reference":[{"key":"9348_CR1","doi-asserted-by":"crossref","unstructured":"Aghaei, S., Azizi, M.J., & Vayanos, P. (2019). Learning optimal and fair decision trees for non-discriminative decision-making. In: AAAI Conference on artificial intelligence (AAAI) (pp. 1418\u20131426)","DOI":"10.1609\/aaai.v33i01.33011418"},{"key":"9348_CR2","doi-asserted-by":"crossref","unstructured":"Aglin, G., Nijssen, S., & Schaus, P. (2020). Learning optimal decision trees using caching branch-and-bound search. In: AAAI Conference on Artificial Intelligence (AAAI) (pp. 3146\u20133153)","DOI":"10.1609\/aaai.v34i04.5711"},{"key":"9348_CR3","first-page":"1","volume":"18","author":"E Angelino","year":"2018","unstructured":"Angelino, E., Larus-Stone, N., Alabi, D., Seltzer, M., & Rudin, C. (2018). Learning certifiably optimal rule lists for categorical data. Journal of Machine Learning Research, 18, 1\u201378.","journal-title":"Journal of Machine Learning Research"},{"key":"9348_CR4","doi-asserted-by":"crossref","unstructured":"Avellaneda, F. (2020). Efficient inference of optimal decision trees. In: AAAI Conference on artificial intelligence (AAAI) (pp. 3195\u20133202)","DOI":"10.1609\/aaai.v34i04.5717"},{"key":"9348_CR5","first-page":"156","volume":"26","author":"KP Bennett","year":"1994","unstructured":"Bennett, K. P. (1994). Global tree optimization: A non-greedy decision tree algorithm. Journal of Computing Science and Statistics, 26, 156\u2013160.","journal-title":"Journal of Computing Science and Statistics"},{"key":"9348_CR6","doi-asserted-by":"crossref","unstructured":"Berg, J., Demirovi\u0107, E., & Stuckey, P.J. (2019). Core-boosted linear search for incomplete MaxSAT. In: International conference on integration of constraint programming, artificial intelligence, and operations research (CPAIOR) (pp. 39\u201356). Springer","DOI":"10.1007\/978-3-030-19212-9_3"},{"issue":"7","key":"9348_CR7","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1007\/s10994-017-5633-9","volume":"106","author":"D Bertsimas","year":"2017","unstructured":"Bertsimas, D., & Dunn, J. (2017). Optimal classification trees. Machine Learning, 106(7), 1039\u20131082.","journal-title":"Machine Learning"},{"key":"9348_CR8","doi-asserted-by":"crossref","unstructured":"Bessiere, C., Hebrard, E., & O\u2019Sullivan, B. (2009). Minimising decision tree size as combinatorial optimisation. In: International conference on principles and practice of constraint programming (CP) (pp. 173\u2013187). Springer","DOI":"10.1007\/978-3-642-04244-7_16"},{"key":"9348_CR9","unstructured":"Biere, A., Heule, M., & van Maaren, H. (2009). Handbook of satisfiability, vol. 185. IOS press"},{"key":"9348_CR10","unstructured":"Breiman, L., Friedman, J.H., Olshen, R.A., & Stone, C.J. (1984). Classification and regression trees. Wadsworth & Brooks\/Cole Advanced Books & Software"},{"key":"9348_CR11","doi-asserted-by":"crossref","unstructured":"Cabodi, G., Camurati, P.E., Ignatiev, A., Marques-Silva, J., Palena, M., & Pasini, P. (2021). Optimizing binary decision diagrams for interpretable machine learning classification. In: 2021 Design, automation & test in europe conference & exhibition (DATE) (pp. 1122\u20131125). IEEE","DOI":"10.23919\/DATE51398.2021.9474083"},{"key":"9348_CR12","doi-asserted-by":"crossref","unstructured":"Dechter, R., & Mateescu, R. (2004). The impact of and\/or search spaces on constraint satisfaction and counting. In: International conference on principles and practice of constraint programming (CP) (pp. 731\u2013736)","DOI":"10.1007\/978-3-540-30201-8_56"},{"key":"9348_CR13","unstructured":"Dua, D., & Graff, C. (2017). UCI machine learning repository. http:\/\/archive.ics.uci.edu\/ml"},{"key":"9348_CR14","unstructured":"E\u00e9n, N., & S\u00f6rensson, N. (2003). Minisat SAT solver. http:\/\/minisat.se\/Main.html"},{"key":"9348_CR15","doi-asserted-by":"crossref","unstructured":"Fu, Z., & Malik, S. (2006). On solving the partial MAX-SAT problem. In: International conference on theory and applications of satisfiability testing (SAT) (pp. 252\u2013265). Springer","DOI":"10.1007\/11814948_25"},{"key":"9348_CR16","doi-asserted-by":"crossref","unstructured":"G\u00fcnl\u00fck, O., Kalagnanam, J., Li, M., Menickelly, M., & Scheinberg, K. (2021). Optimal decision trees for categorical data via integer programming. Journal of Global Optimization, 1\u201328","DOI":"10.1007\/s10898-021-01009-y"},{"key":"9348_CR17","unstructured":"Guyon, I. (2003). Design of experiments of the nips 2003 variable selection benchmark. In: NIPS 2003 workshop on feature extraction and feature selection, vol. 253"},{"key":"9348_CR18","doi-asserted-by":"crossref","unstructured":"Guyon, I., Bennett, K., Cawley, G., Escalante, H.J., Escalera, S., Ho, T.K., Maci\u00e0, N., Ray, B., Saeed, M., & Statnikov, A., et\u00a0al. (2015). Design of the 2015 chalearn automl challenge. In: 2015 International joint conference on neural networks (IJCNN) (pp. 1\u20138). IEEE","DOI":"10.1109\/IJCNN.2015.7280767"},{"issue":"2","key":"9348_CR19","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1006\/inco.1996.0040","volume":"126","author":"T Hancock","year":"1996","unstructured":"Hancock, T., Jiang, T., Li, M., & Tromp, J. (1996). Lower bounds on learning decision lists and trees. Information and Computation, 126(2), 114\u2013122.","journal-title":"Information and Computation"},{"key":"9348_CR20","doi-asserted-by":"crossref","unstructured":"Hastie, T., Tibshirani, R., Friedman, J.H., & Friedman, J.H. (2009). The elements of statistical learning: data mining, inference, and prediction, vol.\u00a02. Springer","DOI":"10.1007\/978-0-387-84858-7"},{"key":"9348_CR21","doi-asserted-by":"crossref","unstructured":"Hu, H., Siala, M., H\u00e9brard, E., & Huguet, M.J. (2020). Learning optimal decision trees with MaxSAT and its integration in AdaBoost. In: International joint conference on artificial intelligence and pacific rim international conference on artificial intelligence (IJCAI-PRICAI)","DOI":"10.24963\/ijcai.2020\/163"},{"key":"9348_CR22","doi-asserted-by":"crossref","unstructured":"Ignatiev, A., Lam, E., Stuckey, P.J., & Marques-Silva, J. (2021). A scalable two stage approach to computing optimal decision sets. arXiv preprint arXiv:2102.01904","DOI":"10.1609\/aaai.v35i5.16498"},{"key":"9348_CR23","doi-asserted-by":"crossref","unstructured":"Ignatiev, A., Marques-Silva, J., Narodytska, N., & Stuckey, P.J. (2021). Reasoning-based learning of interpretable ML models. In: International Joint Conference on Artificial Intelligence (IJCAI) p. in press","DOI":"10.24963\/ijcai.2021\/608"},{"key":"9348_CR24","doi-asserted-by":"crossref","unstructured":"Ignatiev, A., Pereira, F., Narodytska, N., & Marques-Silva, J. (2018). A sat-based approach to learn explainable decision sets. In: International joint conference on automated reasoning (pp. 627\u2013645). Springer","DOI":"10.1007\/978-3-319-94205-6_41"},{"key":"9348_CR25","doi-asserted-by":"crossref","unstructured":"Janota, M., & Morgado, A. (2020). Sat-based encodings for optimal decision trees with explicit paths. In: International conference on theory and applications of satisfiability testing (pp. 501\u2013518). Springer","DOI":"10.1007\/978-3-030-51825-7_35"},{"key":"9348_CR26","unstructured":"Kelleher, J.D., Mac Namee, B., & D\u2019arcy, A. (2020). Fundamentals of machine learning for predictive data analytics: algorithms, worked examples, and case studies. MIT press"},{"issue":"4","key":"9348_CR27","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10462-011-9272-4","volume":"39","author":"SB Kotsiantis","year":"2013","unstructured":"Kotsiantis, S. B. (2013). Decision trees: a recent overview. Artificial Intelligence Review, 39(4), 261\u2013283.","journal-title":"Artificial Intelligence Review"},{"issue":"1","key":"9348_CR28","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0020-0190(76)90095-8","volume":"5","author":"H Laurent","year":"1976","unstructured":"Laurent, H., & Rivest, R. L. (1976). Constructing optimal binary decision trees is np-complete. Information Processing Letters, 5(1), 15\u201317.","journal-title":"Information Processing Letters"},{"key":"9348_CR29","unstructured":"Maloof, M.A. (2003). Learning when data sets are imbalanced and when costs are unequal and unknown. In: ICML-2003 workshop on learning from imbalanced data sets II, (vol.\u00a02, pp. 2\u20131)"},{"key":"9348_CR30","unstructured":"Mosley, L. (2013). A balanced approach to the multi-class imbalance problem. Ph.D. thesis, Iowa State University"},{"key":"9348_CR31","doi-asserted-by":"crossref","unstructured":"Narodytska, N., Ignatiev, A., Pereira, F., Marques-Silva, J., & RAS, I. (2018). Learning optimal decision trees with SAT. In: International joint conference on artificial intelligence (IJCAI) (pp. 1362\u20131368)","DOI":"10.24963\/ijcai.2018\/189"},{"key":"9348_CR32","doi-asserted-by":"crossref","unstructured":"Nijssen, S., & Fromont, E. (2007). Mining optimal decision trees from itemset lattices. In: SIGKDD International conference on knowledge discovery and data mining (KDD) (pp. 530\u2013539)","DOI":"10.1145\/1281192.1281250"},{"issue":"1","key":"9348_CR33","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/s10618-010-0174-x","volume":"21","author":"S Nijssen","year":"2010","unstructured":"Nijssen, S., & Fromont, E. (2010). Optimal constraint-based decision tree induction from itemset lattices. Data Mining and Knowledge Discovery, 21(1), 9\u201351.","journal-title":"Data Mining and Knowledge Discovery"},{"key":"9348_CR34","unstructured":"OscaR Team (2012). OscaR: Scala in OR . https:\/\/bitbucket.org\/oscarlib\/oscar"},{"key":"9348_CR35","first-page":"2825","volume":"12","author":"F Pedregosa","year":"2011","unstructured":"Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., & Duchesnay, E. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12, 2825\u20132830.","journal-title":"Journal of Machine Learning Research"},{"issue":"4","key":"9348_CR36","doi-asserted-by":"publisher","first-page":"7","DOI":"10.5120\/ijca2017915495","volume":"175","author":"K Potdar","year":"2017","unstructured":"Potdar, K., Pardawala, T. S., & Pai, C. D. (2017). A comparative study of categorical variable encoding techniques for neural network classifiers. International Journal Of Computer Applications, 175(4), 7\u20139.","journal-title":"International Journal Of Computer Applications"},{"issue":"1","key":"9348_CR37","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF00116251","volume":"1","author":"JR Quinlan","year":"1986","unstructured":"Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81\u2013106.","journal-title":"Machine Learning"},{"key":"9348_CR38","unstructured":"Quinlan, J.R. (2014). C4. 5: programs for machine learning. Elsevier"},{"issue":"4","key":"9348_CR39","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1007\/s12532-018-0143-8","volume":"10","author":"C Rudin","year":"2018","unstructured":"Rudin, C., & Ertekin, \u015e. (2018). Learning customized and optimized lists of rules with mathematical programming. Mathematical Programming Computation, 10(4), 659\u2013702.","journal-title":"Mathematical Programming Computation"},{"key":"9348_CR40","doi-asserted-by":"crossref","unstructured":"Schaus, P., Aoga, J.O., & Guns, T. (2017). Coversize: A global constraint for frequency-based itemset mining. In: International conference on principles and practice of constraint programming (CP) (pp. 529\u2013546). Springer","DOI":"10.1007\/978-3-319-66158-2_34"},{"key":"9348_CR41","unstructured":"Shati, P., Cohen, E., & McIlraith, S. (2021). Sat-based approach for learning optimal decision trees with non-binary features. In: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"9348_CR42","doi-asserted-by":"crossref","unstructured":"Sinz, C. (2005). Towards an optimal cnf encoding of boolean cardinality constraints. In: International conference on principles and practice of constraint programming (pp. 827\u2013831). Springer","DOI":"10.1007\/11564751_73"},{"issue":"3","key":"9348_CR43","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/s10601-020-09312-3","volume":"25","author":"H Verhaeghe","year":"2020","unstructured":"Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C. G., & Schaus, P. (2020). Learning optimal decision trees using constraint programming. Constraints, 25(3), 226\u2013250.","journal-title":"Constraints"},{"key":"9348_CR44","doi-asserted-by":"crossref","unstructured":"Verwer, S., & Zhang, Y. (2019). Learning optimal classification trees using a binary linear program formulation. In: AAAI Conference on artificial intelligence (AAAI), (pp. 1625\u20131632)","DOI":"10.1609\/aaai.v33i01.33011624"},{"issue":"1","key":"9348_CR45","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/1007730.1007734","volume":"6","author":"GM Weiss","year":"2004","unstructured":"Weiss, G. M. (2004). Mining with rarity: a unifying framework. ACM Sigkdd Explorations Newsletter, 6(1), 7\u201319.","journal-title":"ACM Sigkdd Explorations Newsletter"},{"key":"9348_CR46","unstructured":"Yu, J., Ignatiev, A., Bodic, P.L., & Stuckey, P.J. (2020). Optimal decision lists using sat. arXiv preprint. arXiv:2010.09919"},{"key":"9348_CR47","doi-asserted-by":"crossref","unstructured":"Yu, J., Ignatiev, A., Stuckey, P.J., & Le\u00a0Bodic, P. (2020). Computing optimal decision sets with sat. In: International conference on principles and practice of constraint programming (CP) (pp. 952\u2013970). Springer","DOI":"10.1007\/978-3-030-58475-7_55"},{"key":"9348_CR48","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1613\/jair.1.12719","volume":"72","author":"J Yu","year":"2021","unstructured":"Yu, J., Ignatiev, A., Stuckey, P. J., & Le Bodic, P. (2021). Learning optimal decision sets and lists with sat. Journal of Artificial Intelligence Research, 72, 1251\u20131279.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1","key":"9348_CR49","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1109\/TKDE.2006.17","volume":"18","author":"ZH Zhou","year":"2005","unstructured":"Zhou, Z. H., & Liu, X. Y. (2005). Training cost-sensitive neural networks with methods addressing the class imbalance problem. IEEE Transactions on Knowledge And Data Engineering, 18(1), 63\u201377.","journal-title":"IEEE Transactions on Knowledge And Data Engineering"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09348-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-023-09348-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09348-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,4]],"date-time":"2023-08-04T02:10:30Z","timestamp":1691115030000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-023-09348-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["9348"],"URL":"https:\/\/doi.org\/10.1007\/s10601-023-09348-1","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"17 April 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant conflicts of interest\/competing interests to declare","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interests\/Competing interests"}}]}}