Please use this identifier to cite or link to this item:
Title: Branch-and-bound algorithms for computing the best-subset regression models
Authors: Gatu, Cristian 
Kontoghiorghes, Erricos John 
Keywords: Least squares;Algorithms
Issue Date: 2006
Publisher: Taylor & Francis Online
Source: Journal of Computational and Graphical Statistics, 2006, Volume 15, Issue 1, Pages 139-156
Abstract: An efficient branch-and-bound algorithm for computing the best-subset regression models is proposed. The algorithm avoids the computation of the whole regression tree that generates all possible subset models. It is formally shown that if the branch-and-bound test holds, then the current subtree together with its right-hand side subtrees are cut. This reduces significantly the computational burden of the proposed algorithm when compared to an existing leaps-and-bounds method which generates two trees. Specifically, the proposed algorithm, which is based on orthogonal transformations, outperforms by O(n 3) the leaps-and-bounds strategy. The criteria used in identifying the best subsets are based on monotone functions of the residual sum of squares (RSS) such as R 2, adjusted R 2, mean square error of prediction, and C p. Strategies and heuristics that improve the computational performance of the proposed algorithm are investigated. A computationally efficient heuristic version of the branch-and-bound strategy which decides to cut subtrees using a tolerance parameter is proposed. The heuristic algorithm derives models close to the best ones. However, it is shown analytically that the relative error of the RSS, and consequently the corresponding statistic, of the computed subsets is smaller than the value of the tolerance parameter which lies between zero and one. Computational results and experiments on random and real data are presented and analyzed.
ISSN: 1061-8600 (print)
1537-2715 (online)
DOI: 10.1198/106186006X100290
Rights: © 2006 American Statistical Association.
Type: Article
Appears in Collections:Άρθρα/Articles

Show full item record


checked on Apr 28, 2018

Citations 50

checked on Oct 14, 2019

Page view(s) 50

Last Week
Last month
checked on Oct 17, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.