Skewing: An efficient alternative to lookahead for decision tree induction


Conference Paper

This paper presents a novel, promising approach that allows greedy decision tree induction algorithms to handle problematic functions such as parity functions. Lookahead is the standard approach to addressing difficult functions for greedy decision tree learners. Nevertheless, this approach is limited to very small problematic functions or subfunctions (2 or 3 variables), because the time complexity grows more than exponentially with the depth of lookahead. In contrast, the approach presented in this paper carries only a constant run-time penalty. Experiments indicate that the approach is effective with only modest amounts of data for problematic functions or subfunctions of up to six or seven variables, where the examples themselves may contain numerous other (irrelevant) variables as well.

Duke Authors

Cited Authors

  • Page, D; Ray, S

Published Date

  • December 1, 2003

Published In

Start / End Page

  • 601 - 607

International Standard Serial Number (ISSN)

  • 1045-0823

Citation Source

  • Scopus