IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v55y2011i1p123-131.html
   My bibliography  Save this article

Exact and approximate algorithms for variable selection in linear discriminant analysis

Author

Listed:
  • Brusco, Michael J.
  • Steinley, Douglas

Abstract

Variable selection is a venerable problem in multivariate statistics. In the context of discriminant analysis, the goal is to select a subset of variables that accomplishes one of two objectives: (1) the provision of a parsimonious, yet descriptive, representation of group structure, or (2) the ability to correctly allocate new cases to groups. We present an exact (branch-and-bound) algorithm for variable selection in linear discriminant analysis that identifies subsets of variables that minimize Wilks' [Lambda]. An important feature of this algorithm is a variable reordering scheme that greatly reduces computation time. We also present an approximate procedure based on tabu search, which can be implemented for a variety of objective criteria designed for either the descriptive or allocation goals associated with discriminant analysis. The tabu search heuristic is especially useful for maximizing the hit ratio (i.e., the percentage of correctly classified cases). Computational results for the proposed methods are provided for two data sets from the literature.

Suggested Citation

  • Brusco, Michael J. & Steinley, Douglas, 2011. "Exact and approximate algorithms for variable selection in linear discriminant analysis," Computational Statistics & Data Analysis, Elsevier, vol. 55(1), pages 123-131, January.
  • Handle: RePEc:eee:csdana:v:55:y:2011:i:1:p:123-131
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167-9473(10)00238-0
    Download Restriction: Full text for ScienceDirect subscribers only.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Antonie Stam, 1997. "Nontraditional approaches to statistical classification: Some perspectives on L_p-norm methods," Annals of Operations Research, Springer, vol. 74(0), pages 1-36, November.
    2. Pacheco, Joaquín & Casado, Silvia & Núñez, Laura, 2009. "A variable selection method based on Tabu search for logistic regression models," European Journal of Operational Research, Elsevier, vol. 199(2), pages 506-511, December.
    3. Gordon D. Murray, 1977. "A Cautionary Note on Selection of Variables in Discriminant Analysis," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 26(3), pages 246-250, November.
    4. Li, Baibing & Martin, Elaine B. & Morris, A. Julian, 2002. "On principal component analysis in L1," Computational Statistics & Data Analysis, Elsevier, vol. 40(3), pages 471-474, September.
    5. Michael Brusco & Renu Singh & Douglas Steinley, 2009. "Variable Neighborhood Search Heuristics for Selecting a Subset of Variables in Principal Component Analysis," Psychometrika, Springer;The Psychometric Society, vol. 74(4), pages 705-726, December.
    6. Pacheco, Joaquin & Casado, Silvia & Nunez, Laura & Gomez, Olga, 2006. "Analysis of new variable selection methods for discriminant analysis," Computational Statistics & Data Analysis, Elsevier, vol. 51(3), pages 1463-1478, December.
    7. Kaoru Fueda & Masaya Iizuka & Yuichi Mori, 2009. "Variable selection in multivariate methods using global score estimation," Computational Statistics, Springer, vol. 24(1), pages 127-144, February.
    8. Yutaka Kano & Akira Harada, 2000. "Stepwise variable selection in factor analysis," Psychometrika, Springer;The Psychometric Society, vol. 65(1), pages 7-22, March.
    9. Cadima, Jorge & Cerdeira, J. Orestes & Minhoto, Manuel, 2004. "Computational aspects of algorithms for variable selection in the context of principal components," Computational Statistics & Data Analysis, Elsevier, vol. 47(2), pages 225-236, September.
    10. Krzanowski, Wojtek J. & Hand, David J., 2009. "A simple method for screening variables before clustering microarray data," Computational Statistics & Data Analysis, Elsevier, vol. 53(7), pages 2747-2753, May.
    11. Douglas Steinley & Michael Brusco, 2008. "Selection of Variables in Cluster Analysis: An Empirical Comparison of Eight Procedures," Psychometrika, Springer;The Psychometric Society, vol. 73(1), pages 125-144, March.
    12. Kristine Hogarty & Jeffrey Kromrey & John Ferron & Constance Hines, 2004. "Selection of variables in exploratory factor analysis: An empirical comparison of a stepwise and traditional approach," Psychometrika, Springer;The Psychometric Society, vol. 69(4), pages 593-611, December.
    13. Trendafilov, Nickolay T. & Jolliffe, Ian T., 2007. "DALASS: Variable selection in discriminant analysis via the LASSO," Computational Statistics & Data Analysis, Elsevier, vol. 51(8), pages 3718-3736, May.
    14. Michael Brusco & J. Cradit, 2001. "A variable-selection heuristic for K-means clustering," Psychometrika, Springer;The Psychometric Society, vol. 66(2), pages 249-270, June.
    15. Duarte Silva, António Pedro, 2001. "Efficient Variable Screening for Multivariate Analysis," Journal of Multivariate Analysis, Elsevier, vol. 76(1), pages 35-62, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. du Jardin, Philippe & Séverin, Eric, 2012. "Forecasting financial failure using a Kohonen map: A comparative study to improve model stability over time," European Journal of Operational Research, Elsevier, vol. 221(2), pages 378-396.
    2. Michael Fop & Pierre-Alexandre Mattei & Charles Bouveyron & Thomas Brendan Murphy, 2022. "Unobserved classes and extra variables in high-dimensional discriminant analysis," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 16(1), pages 55-92, March.
    3. Fouskakis, D., 2012. "Bayesian variable selection in generalized linear models using a combination of stochastic optimization methods," European Journal of Operational Research, Elsevier, vol. 220(2), pages 414-422.
    4. Pacheco, Joaquín & Casado, Silvia & Porras, Santiago, 2013. "Exact methods for variable selection in principal component analysis: Guide functions and pre-selection," Computational Statistics & Data Analysis, Elsevier, vol. 57(1), pages 95-111.
    5. Chan, Ngai Hang & Wong, Hoi Ying & Zhao, Jing, 2012. "Structural model of credit migration," Computational Statistics & Data Analysis, Elsevier, vol. 56(11), pages 3477-3490.
    6. Brusco, Michael J., 2014. "A comparison of simulated annealing algorithms for variable selection in principal component analysis and discriminant analysis," Computational Statistics & Data Analysis, Elsevier, vol. 77(C), pages 38-53.
    7. Paz, Alexander & Arteaga, Cristian & Cobos, Carlos, 2019. "Specification of mixed logit models assisted by an optimization framework," Journal of choice modelling, Elsevier, vol. 30(C), pages 50-60.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Brusco, Michael J., 2014. "A comparison of simulated annealing algorithms for variable selection in principal component analysis and discriminant analysis," Computational Statistics & Data Analysis, Elsevier, vol. 77(C), pages 38-53.
    2. Pacheco, Joaquín & Casado, Silvia & Porras, Santiago, 2013. "Exact methods for variable selection in principal component analysis: Guide functions and pre-selection," Computational Statistics & Data Analysis, Elsevier, vol. 57(1), pages 95-111.
    3. Michael Brusco & Renu Singh & Douglas Steinley, 2009. "Variable Neighborhood Search Heuristics for Selecting a Subset of Variables in Principal Component Analysis," Psychometrika, Springer;The Psychometric Society, vol. 74(4), pages 705-726, December.
    4. Gao, Jinxin & Hitchcock, David B., 2010. "James-Stein shrinkage to improve k-means cluster analysis," Computational Statistics & Data Analysis, Elsevier, vol. 54(9), pages 2113-2127, September.
    5. Fouskakis, D., 2012. "Bayesian variable selection in generalized linear models using a combination of stochastic optimization methods," European Journal of Operational Research, Elsevier, vol. 220(2), pages 414-422.
    6. Casado Yusta, Silvia & Nœ–ez Letamendía, Laura & Pacheco Bonrostro, Joaqu’n Antonio, 2018. "Predicting Corporate Failure: The GRASP-LOGIT Model || Predicci—n de la quiebra empresarial: el modelo GRASP-LOGIT," Revista de Métodos Cuantitativos para la Economía y la Empresa = Journal of Quantitative Methods for Economics and Business Administration, Universidad Pablo de Olavide, Department of Quantitative Methods for Economics and Business Administration, vol. 26(1), pages 294-314, Diciembre.
    7. Trendafilov, Nickolay T. & Vines, Karen, 2009. "Simple and interpretable discrimination," Computational Statistics & Data Analysis, Elsevier, vol. 53(4), pages 979-989, February.
    8. Pedro Duarte Silva, A., 2017. "Optimization approaches to Supervised Classification," European Journal of Operational Research, Elsevier, vol. 261(2), pages 772-788.
    9. Unler, Alper & Murat, Alper, 2010. "A discrete particle swarm optimization method for feature selection in binary classification problems," European Journal of Operational Research, Elsevier, vol. 206(3), pages 528-539, November.
    10. du Jardin, Philippe & Séverin, Eric, 2012. "Forecasting financial failure using a Kohonen map: A comparative study to improve model stability over time," European Journal of Operational Research, Elsevier, vol. 221(2), pages 378-396.
    11. A. Pedro Duarte Silva, 2009. "Exact and heuristic algorithms for variable selection: Extended Leaps and Bounds," Working Papers de Economia (Economics Working Papers) 01, Católica Porto Business School, Universidade Católica Portuguesa.
    12. Susan Brudvig & Michael J. Brusco & J. Dennis Cradit, 2019. "Joint selection of variables and clusters: recovering the underlying structure of marketing data," Journal of Marketing Analytics, Palgrave Macmillan, vol. 7(1), pages 1-12, March.
    13. Tangian, Andranik S., 2017. "Selection of questions for VAAs and the VAA-based elections," Working Paper Series in Economics 100, Karlsruhe Institute of Technology (KIT), Department of Economics and Management.
    14. Nkiet, Guy Martial, 2012. "Direct variable selection for discrimination among several groups," Journal of Multivariate Analysis, Elsevier, vol. 105(1), pages 151-163.
    15. Naoto Yamashita & Kohei Adachi, 2020. "A Modified k-Means Clustering Procedure for Obtaining a Cardinality-Constrained Centroid Matrix," Journal of Classification, Springer;The Classification Society, vol. 37(2), pages 509-525, July.
    16. Tanguiane, Andranick S., 2019. "Combining the third vote with traditional elections," Working Paper Series in Economics 132, Karlsruhe Institute of Technology (KIT), Department of Economics and Management.
    17. Plat, Richard, 2009. "Stochastic portfolio specific mortality and the quantification of mortality basis risk," Insurance: Mathematics and Economics, Elsevier, vol. 45(1), pages 123-132, August.
    18. Kondylis, Athanassios & Whittaker, Joe, 2008. "Spectral preconditioning of Krylov spaces: Combining PLS and PC regression," Computational Statistics & Data Analysis, Elsevier, vol. 52(5), pages 2588-2603, January.
    19. Ouyang, Yaofu & Li, Peng, 2018. "On the nexus of financial development, economic growth, and energy consumption in China: New perspective from a GMM panel VAR approach," Energy Economics, Elsevier, vol. 71(C), pages 238-252.
    20. Paschalis Arvanitidis & Athina Economou & Christos Kollias, 2016. "Terrorism’s effects on social capital in European countries," Public Choice, Springer, vol. 169(3), pages 231-250, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:csdana:v:55:y:2011:i:1:p:123-131. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/csda .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.