Please use this identifier to cite or link to this item: http://ktisis.cut.ac.cy/handle/10488/6766
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.
URI: http://ktisis.cut.ac.cy/handle/10488/6766
ISSN: 1061-8600 (print)
1537-2715 (online)
DOI: 10.1198/106186006X100290
Rights: © 2006 American Statistical Association.
Appears in Collections:Άρθρα/Articles

Show full item record

SCOPUSTM   
Citations 5

39
checked on Apr 23, 2017

WEB OF SCIENCETM
Citations 5

37
checked on Apr 16, 2017

Page view(s) 50

27
Last Week
0
Last month
7
checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric


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