---
title: "Oblivious Decision Trees, Graphs, and Top-Down Pruning"
authors:
  - "Ron Kohavi"
  - "Chia-Hsin Li"
doi: ""
url: "https://ijcai.org/proceedings/1995/139"
pdf: "https://ijcai.org/proceedings/1995/0139.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "1071-1078"
track: "Learning"
keywords:
---

# Oblivious Decision Trees, Graphs, and Top-Down Pruning

Ron Kohavi, Chia-Hsin Li

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 1071-1078.

## Abstract

We describe a supervised learning algorithm, EODG, that uses mutual information to build an oblivious decision tree. The tree is then converted to an Oblivious read-Once Decision Graph (OODG) by merging nodes at the same level of the tree. For domains that are appropriate for both decision trees and OODGs, performance is approximately the same as that of C4.5, but the number of nodes in the OODG is much smaller. The merging phase that converts the oblivious decision tree to an OODG provides a new way of dealing with the replication problem and a new pruning mechanism that works top down starting from the root. The pruning mechanism is well suited for finding symmetries and aids in recovering from splits on irrelevant features that may happen during the tree construction.