IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v212y2011i1p213-222.html
   My bibliography  Save this article

Globally optimal clusterwise regression by mixed logical-quadratic programming

Author

Listed:
  • Carbonneau, Réal A.
  • Caporossi, Gilles
  • Hansen, Pierre

Abstract

Exact global optimization of the clusterwise regression problem is challenging and there are currently no published feasible methods for performing this clustering optimally, even though it has been over thirty years since its original proposal. This work explores global optimization of the clusterwise regression problem using mathematical programming and related issues. A mixed logical-quadratic programming formulation with implication of constraints is presented and contrasted against a quadratic formulation based on the traditional big-M, which cannot guarantee optimality because the regression line coefficients, and thus errors, may be arbitrarily large. Clusterwise regression optimization times and solution optimality for two clusters are empirically tested on twenty real datasets and three series of synthetic datasets ranging from twenty to one hundred observations and from two to ten independent variables. Additionally, a few small real datasets are clustered into three lines.

Suggested Citation

  • Carbonneau, Réal A. & Caporossi, Gilles & Hansen, Pierre, 2011. "Globally optimal clusterwise regression by mixed logical-quadratic programming," European Journal of Operational Research, Elsevier, vol. 212(1), pages 213-222, July.
    • Handle: RePEc:eee:ejores:v:212:y:2011:i:1:p:213-222
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(11)00019-1
    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. John N. Hooker, 2007. "Integrated Methods for Optimization," International Series in Operations Research and Management Science, Springer, number 978-0-387-38274-6, July-Dece.
    2. Wayne DeSarbo & Richard Oliver & Arvind Rangaswamy, 1989. "A simulated annealing methodology for clusterwise linear regression," Psychometrika, Springer;The Psychometric Society, vol. 54(4), pages 707-736, September.
    3. Aurifeille, Jacques-Marie & Quester, Pascale G., 2003. "Predicting business ethical tolerance in international markets: a concomitant clusterwise regression analysis," International Business Review, Elsevier, vol. 12(2), pages 253-272, April.
    4. Wayne DeSarbo & William Cron, 1988. "A maximum likelihood methodology for clusterwise linear regression," Journal of Classification, Springer;The Classification Society, vol. 5(2), pages 249-282, September.
    5. Michel Wedel & Wayne DeSarbo, 1995. "A mixture likelihood approach for generalized linear models," Journal of Classification, Springer;The Classification Society, vol. 12(1), pages 21-55, March.
    6. Lau, Kin-nam & Leung, Pui-lam & Tse, Ka-kit, 1999. "A mathematical programming approach to clusterwise regression model and its extensions," European Journal of Operational Research, Elsevier, vol. 116(3), pages 640-652, August.
    7. John N. Hooker, 2002. "Logic, Optimization, and Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 295-321, November.
    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. Reis dos Santos, M. Isabel & Reis dos Santos, Pedro M., 2016. "Switching regression metamodels in stochastic simulation," European Journal of Operational Research, Elsevier, vol. 251(1), pages 142-147.
    2. Adil M. Bagirov & Julien Ugon & Hijran G. Mirzayeva, 2015. "Nonsmooth Optimization Algorithm for Solving Clusterwise Linear Regression Problems," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 755-780, March.
    3. Réal Carbonneau & Gilles Caporossi & Pierre Hansen, 2014. "Globally Optimal Clusterwise Regression By Column Generation Enhanced with Heuristics, Sequencing and Ending Subset Optimization," Journal of Classification, Springer;The Classification Society, vol. 31(2), pages 219-241, July.
    4. Roberto Mari & Roberto Rocci & Stefano Antonio Gattone, 2020. "Scale-constrained approaches for maximum likelihood estimation and model selection of clusterwise linear regression models," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 29(1), pages 49-78, March.
    5. Young Woong Park & Yan Jiang & Diego Klabjan & Loren Williams, 2017. "Algorithms for Generalized Clusterwise Linear Regression," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 301-317, May.
    6. Bagirov, Adil M. & Ugon, Julien & Mirzayeva, Hijran, 2013. "Nonsmooth nonconvex optimization approach to clusterwise linear regression problems," European Journal of Operational Research, Elsevier, vol. 229(1), pages 132-142.
    7. Joki, Kaisa & Bagirov, Adil M. & Karmitsa, Napsu & Mäkelä, Marko M. & Taheri, Sona, 2020. "Clusterwise support vector linear regression," European Journal of Operational Research, Elsevier, vol. 287(1), pages 19-35.

    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. Réal Carbonneau & Gilles Caporossi & Pierre Hansen, 2014. "Globally Optimal Clusterwise Regression By Column Generation Enhanced with Heuristics, Sequencing and Ending Subset Optimization," Journal of Classification, Springer;The Classification Society, vol. 31(2), pages 219-241, July.
    2. D'Urso, Pierpaolo & Santoro, Adriana, 2006. "Fuzzy clusterwise linear regression analysis with symmetrical fuzzy output variable," Computational Statistics & Data Analysis, Elsevier, vol. 51(1), pages 287-313, November.
    3. Ana Oliveira-Brochado & Francisco Vitorino Martins, 2008. "Segmentação de Mercado e modelos mistura de regressão para variáveis normais," FEP Working Papers 262, Universidade do Porto, Faculdade de Economia do Porto.
    4. Hye Suk & Heungsun Hwang, 2010. "Regularized fuzzy clusterwise ridge regression," 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. 4(1), pages 35-51, April.
    5. Bagirov, Adil M. & Ugon, Julien & Mirzayeva, Hijran, 2013. "Nonsmooth nonconvex optimization approach to clusterwise linear regression problems," European Journal of Operational Research, Elsevier, vol. 229(1), pages 132-142.
    6. Tom Frans Wilderjans & Eva Gaer & Henk A. L. Kiers & Iven Mechelen & Eva Ceulemans, 2017. "Principal Covariates Clusterwise Regression (PCCR): Accounting for Multicollinearity and Population Heterogeneity in Hierarchically Organized Data," Psychometrika, Springer;The Psychometric Society, vol. 82(1), pages 86-111, March.
    7. Joki, Kaisa & Bagirov, Adil M. & Karmitsa, Napsu & Mäkelä, Marko M. & Taheri, Sona, 2020. "Clusterwise support vector linear regression," European Journal of Operational Research, Elsevier, vol. 287(1), pages 19-35.
    8. Wayne S. DeSarbo & Qian Chen & Ashley Stadler Blank, 2017. "A Parametric Constrained Segmentation Methodology for Application in Sport Marketing," Customer Needs and Solutions, Springer;Institute for Sustainable Innovation and Growth (iSIG), vol. 4(4), pages 37-55, December.
    9. Pennings, Joost M.E. & Garcia, Philip & Irwin, Scott H. & Good, Darrel L., 2003. "How To Group Market Participants? Heterogeneity In Hedging Behavior," 2003 Annual meeting, July 27-30, Montreal, Canada 21963, American Agricultural Economics Association (New Name 2008: Agricultural and Applied Economics Association).
    10. Heungsun Hwang & Marc Tomiuk, 2010. "Fuzzy clusterwise quasi-likelihood generalized linear models," 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. 4(4), pages 255-270, December.
    11. Salvatore Ingrassia & Simona Minotti & Giorgio Vittadini, 2012. "Local Statistical Modeling via a Cluster-Weighted Approach with Elliptical Distributions," Journal of Classification, Springer;The Classification Society, vol. 29(3), pages 363-401, October.
    12. Adil M. Bagirov & Julien Ugon & Hijran G. Mirzayeva, 2015. "Nonsmooth Optimization Algorithm for Solving Clusterwise Linear Regression Problems," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 755-780, March.
    13. Salvatore Ingrassia & Antonio Punzo, 2020. "Cluster Validation for Mixtures of Regressions via the Total Sum of Squares Decomposition," Journal of Classification, Springer;The Classification Society, vol. 37(2), pages 526-547, July.
    14. Chen, Cathy W.S. & Chan, Jennifer S.K. & So, Mike K.P. & Lee, Kevin K.M., 2011. "Classification in segmented regression problems," Computational Statistics & Data Analysis, Elsevier, vol. 55(7), pages 2276-2287, July.
    15. Martínez-Zarzoso, Inmaculada & Maruotti, Antonello, 2011. "The impact of urbanization on CO2 emissions: Evidence from developing countries," Ecological Economics, Elsevier, vol. 70(7), pages 1344-1353, May.
    16. Ana Oliveira-Brochado & Francisco Vitorino Martins, 2008. "Aspectos Metodológicos da Segmentação de Mercado: Base de Segmentação e Métodos de Classificação," FEP Working Papers 261, Universidade do Porto, Faculdade de Economia do Porto.
    17. repec:jss:jstsof:11:i08 is not listed on IDEAS
    18. Allen, Eric J. & Larson, Chad R. & Sloan, Richard G., 2013. "Accrual reversals, earnings and stock returns," Journal of Accounting and Economics, Elsevier, vol. 56(1), pages 113-129.
    19. Ana Oliveira-Brochado & Francisco Vitorino Martins, 2014. "Identifying Small Market Segments with Mixture Regression Models," International Journal of Finance, Insurance and Risk Management, International Journal of Finance, Insurance and Risk Management, vol. 4(4), pages 812-812.
    20. Van Aelst, Stefan & (Steven) Wang, Xiaogang & Zamar, Ruben H. & Zhu, Rong, 2006. "Linear grouping using orthogonal regression," Computational Statistics & Data Analysis, Elsevier, vol. 50(5), pages 1287-1312, March.
    21. Michele Battisti & Filippo Belloc & Massimo Del Gatto, 2015. "Unbundling Technology Adoption and tfp at the Firm Level: Do Intangibles Matter?," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 24(2), pages 390-414, June.

    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:ejores:v:212:y:2011:i:1:p:213-222. 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/eor .

    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.