EUVIMEDEUVIMED entdecken
Crossref

SAT-based Decision Tree Learning for Large Data Sets

Andre Schidler, Stefan Szeider

Journal of Artificial Intelligence Research · 03.07.2024 · 80 · 875-918

DOI: 10.1613/jair.1.15956 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 03.07.2024. Verfasst von Andre Schidler und 1 weiteren Autor:innen. Die Arbeit wurde bisher 26-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Decision trees of low depth are beneficial for understanding and interpreting the data they represent. Unfortunately, finding a decision tree of lowest complexity (depth or size) that correctly represents given data is NP-hard. Hence known algorithms either (i) utilize heuristics that do not minimize the depth or (ii) are exact but scale only to small or medium-sized instances. We propose a new hybrid approach to decision tree learning, combining heuristic and exact methods in a novel way. More specifically, we employ SAT encodings repeatedly to local parts of a decision tree provided by a standard heuristic, leading to an overall reduction in complexity. This allows us to scale the power of exact SAT-based methods to comparatively very large data sets. We evaluate our new approach experimentally on a range of real-world instances that contain up to several thousand samples. In almost all cases, our method successfully decreases the complexity of the initial decision tree; often, the decrease is significant.

Zitieren

APA

Schidler, A., & Szeider, S. (2024). SAT-based Decision Tree Learning for Large Data Sets. Journal of Artificial Intelligence Research, 80, 875-918. https://doi.org/10.1613/jair.1.15956

Vancouver

Schidler A, Szeider S. SAT-based Decision Tree Learning for Large Data Sets. Journal of Artificial Intelligence Research. 2024;80:875-918. doi:10.1613/jair.1.15956

BibTeX
@article{Schidler2024,
  author = {Schidler, Andre and Szeider, Stefan},
  title = {SAT-based Decision Tree Learning for Large Data Sets},
  journal = {Journal of Artificial Intelligence Research},
  year = {2024},
  volume = {80},
  pages = {875--918},
  doi = {10.1613/jair.1.15956}
}
Kostenlos starten →