Virginia Tech
    • Log in
    View Item 
    •   VTechWorks Home
    • College of Engineering (COE)
    • Grado Department of Industrial and Systems Engineering
    • Scholarly Works, Industrial and Systems Engineering
    • View Item
    •   VTechWorks Home
    • College of Engineering (COE)
    • Grado Department of Industrial and Systems Engineering
    • Scholarly Works, Industrial and Systems Engineering
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    An Optimal Constrained Pruning Strategy for Decision Trees

    Thumbnail
    View/Open
    Main article (304.4Kb)
    Downloads: 725
    Date
    2009
    Author
    Sherali, Hanif D.
    Hobeika, Antoine G.
    Jeenanunta, Chawalit
    Metadata
    Show full item record
    Abstract
    This paper is concerned with the optimal constrained pruning of decision trees. We present a novel 0-1 programming model for pruning the tree to minimize some general penalty function based on the resulting leaf nodes, and show that this model possesses a totally unimodular structure that enables it to be solved as a shortest-path problem on an acyclic graph. Moreover, we prove that this problem can be solved in strongly polynomial time while incorporating an additional constraint on the number of residual leaf nodes. Furthermore, the framework of the proposed modeling approach renders it suitable to accommodate different (multiple) objective functions and side-constraints, and we identify various such modeling options that can be applied in practice. The developed methodology is illustrated using a numerical example to provide insights, and some computational results are presented to demonstrate the efficacy of solving generically constrained problems of this type. We also apply this technique to a large-scale transportation analysis and simulation system (TRANSIMS), and present related computational results using real data to exhibit the flexibility and effectiveness of the proposed approach.
    URI
    http://hdl.handle.net/10919/25833
    Collections
    • Scholarly Works, Civil and Environmental Engineering [464]
    • Scholarly Works, Industrial and Systems Engineering [205]

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us
     

     

    VTechWorks

    AboutPoliciesHelp

    Browse

    All of VTechWorksCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Log inRegister

    Statistics

    View Usage Statistics

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us