A Partitioning Algorithm withApplication inPattern Classirication and theOptimization of Decision Trees
Demetrios A. Michalopoulos · 1973
space byadecision tree, eachnodeofwhichcorresponds toacomparison involving asingle variable, isaproblem occurring inpattern classification, piecewise-constant approximation, andintheefficient programming ofdecision trees. A two-stage algorithm isproposed. Thefirst stage obtains asufficient partition suboptimally, either by methods suggested inthepaper ordeveloped elsewhere; thesecond stage optimizes theresults ofthefirst stage through adynamic programming approach. Inpattern classification, theresulting decision ruleyields theminimumaverage numberofcalculations toreach a decision. Inapproximation, arbitrary accuracy forafinite numberof unique samples ispossible. Inprogramming decision trees, theexpected numberofcomputations toreach adecision isminimized. IndexTerms-Decision rules, decision trees, dynamicprogramming, invariant imbedding, pattern classification, piecewiseconstant approximation. I.INTRODUCTION T HE EFFICIENTpartitioning ofametric space sothateachsubregion hasadistinct character is aproblem ofbroadapplication. Inpattern classification, theobject istopartition thespacesuchthat pattern classes areeasily separable, thatis, sothateach subregion ofthepartition contains predominantly samples ofonlyoneclass. Inpiecewise-constant approximation, thepartition should besuchthateachsubregion contains samples whosevalues aresufficiently close to allowapproximation witha prespecified degree ofaccuracy. Inapplications programming, itisquite often necessary, given apartitioning ofthespace, todefine a decision treewhichdetermines intowhichsubregion a given point falls asefficiently aspossible. We suggest in this paperanalgorithm applicable tothese andsimilar applications. Theproblem attacked isthatoffinding a decision treethattends tominimize theaverage number ofcomparisons required toarrive atadecision. Thepartition considered takes aparticular form. IfX isthespacetobepartitioned, thenthesubregions Xi, which wewill call modes, aregiven by