Learning Decision Trees with Flexible Constraints and Objectives Using Integer Optimization

Sicco Verwer, Yingqian Zhang

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

34 Citations (Scopus)
346 Downloads (Pure)

Abstract

We encode the problem of learning the optimal decision tree of a given depth as an integer optimization problem. We show experimentally that our method (DTIP) can be used to learn good trees up to depth 5 from data sets of size up to 1000. In addition to being efficient, our new formulation allows for a lot of flexibility. Experiments show that we can use the trees learned from any existing decision tree algorithms as starting solutions and improve the trees using DTIP. Moreover, the proposed formulation allows us to easily create decision trees with different optimization objectives instead of accuracy and error, and constraints can be added explicitly during the tree construction phase. We show how this flexibility can be used to learn discrimination-aware classification trees, to improve learning from imbalanced data, and to learn trees that minimise false positive/negative errors.
Original languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming
Subtitle of host publicationCPAIOR 2017
EditorsD. Salvagnin, M. Lombardi
Place of PublicationCham
PublisherSpringer
Pages94-103
Number of pages10
ISBN (Electronic)978-3-319-59776-8
ISBN (Print)978-3-319-59775-1
DOIs
Publication statusPublished - 2017
EventInternational Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: CPAIOR 2017 - Padua, Italy
Duration: 5 Jun 20178 Jun 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10335
ISSN (Electronic)0302-9743

Conference

ConferenceInternational Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Country/TerritoryItaly
CityPadua
Period5/06/178/06/17

Bibliographical note

Accepted author manuscript

Fingerprint

Dive into the research topics of 'Learning Decision Trees with Flexible Constraints and Objectives Using Integer Optimization'. Together they form a unique fingerprint.

Cite this