×

Incremental DC optimization algorithm for large-scale clusterwise linear regression. (English) Zbl 1460.62108

Summary: The objective function in the nonsmooth optimization model of the clusterwise linear regression (CLR) problem with the squared regression error is represented as a difference of two convex functions. Then using the difference of convex algorithm (DCA) approach the CLR problem is replaced by the sequence of smooth unconstrained optimization subproblems. A new algorithm based on the DCA and the incremental approach is designed to solve the CLR problem. We apply the Quasi-Newton method to solve the subproblems. The proposed algorithm is evaluated using several synthetic and real-world data sets for regression and compared with other algorithms for CLR. Results demonstrate that the DCA based algorithm is efficient for solving CLR problems with the large number of data points and in particular, outperforms other algorithms when the number of input variables is small.

MSC:

62J05 Linear regression; mixed models
62H30 Classification and discrimination; cluster analysis (statistical aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Wedel, M.; Kistemaker, C., Consumer benefit segmentation using clusterwise linear regression, Int. J. Res. Mark., 6, 1, 45-59 (1989)
[2] Preda, C.; Saporta, G., Clusterwise pls regression on a stochastic process, Comput. Statist. Data Anal., 49, 99-108 (2005) · Zbl 1429.62299
[3] Bagirov, A.; Mahmood, A.; Barton, A., Prediction of monthly rainfall in Victoria, Australia: Clusterwise linear regression approach, Atmos. Res., 188, 20-29 (2017)
[4] Poggi, J.-M.; Portier, B., PM10 forecasting using clusterwise regression, Atmos. Environ., 45, 38, 7005-7014 (2011)
[5] Späth, H., Algorithm 39: Clusterwise linear regression, Computing, 22, 367-373 (1979) · Zbl 0387.65028
[6] Späth, H., Algorithm 48: A fast algorithm for clusterwise linear regression, Computing, 29, 175-181 (1981) · Zbl 0485.65030
[7] Späth, H., Mathematical Algorithms for Linear Regression (2014), Academic Press
[8] S. Gaffney, P. Smyth, Trajectory clustering using mixtures of regression models, in: S. Chaudhuri, D. Madigan (Eds.), Proceedings of the ACM Conference on Knowledge Discovery and Data Mining, New York, 1999, pp. 63-72.
[9] DeSarbo, W.; Cron, W., A maximum likelihood methodology for clusterwise linear regression, J. Classification, 5, 2, 249-282 (1988) · Zbl 0692.62052
[10] Garcìa-Escudero, L.; Gordaliza, A.; Mayo-Iscar, A.; San Martin, R., Robust clusterwise linear regression through trimming, Comput. Statist. Data Anal., 54, 3057-3069 (2010) · Zbl 1284.62198
[11] Park, Y.; Jiang, Y.; Klabjan, D.; Williams, L., Algorithms for generalized cluster-wise linear regression, INFORMS J. Comput., 29, 301-317 (2017) · Zbl 1528.62036
[12] Bagirov, A.; Taheri, S., DC programming algorithm for clusterwise linear l1 regression, J. Oper. Res. Soc. China, 5, 2, 233-256 (2017) · Zbl 1390.90437
[13] Bagirov, A.; Ugon, J.; Mirzayeva, H., Nonsmooth nonconvex optimization approach to clusterwise linear regression problems, European J. Oper. Res., 229, 1, 132-142 (2013) · Zbl 1317.90242
[14] Bagirov, A.; Ugon, J.; Mirzayeva, H., An algorithm for clusterwise linear regression based on smoothing techniques, Optim. Lett., 9, 2, 375-390 (2015) · Zbl 1311.90106
[15] Bertsimas, D.; Shioda, R., Classification and regression via integer optimization, Oper. Res., 55, 252-271 (2007) · Zbl 1167.90593
[16] Carbonneau, R.; Caporossi, G.; Hansen, P., Globally optimal clusterwise regression by column generation enhanced with heuristics, sequencing and ending subset optimization, J. Classification, 31, 2, 219-241 (2014) · Zbl 1360.62318
[17] Carbonneau, R.; Caporossi, G.; Hansen, P., Globally optimal clusterwise regression by mixed logical-quadratic programming, European J. Oper. Res., 212, 213-222 (2011)
[18] Carbonneau, R.; Caporossi, G.; Hansen, P., Extensions to the repetitive branch-and-bound algorithm for globally-optimal clusterwise regression, Comput. Oper. Res., 39, 11, 2748-2762 (2012) · Zbl 1251.90313
[19] DeSarbo, W.; Oliver, R.; Rangaswamy, A., A simulated annealing methodology for clusterwise linear regression, Psychometrika, 54, 4, 707-736 (1989)
[20] Bagirov, A.; Ugon, J., Nonsmooth DC programming approach to clusterwise linear regression: optimality conditions and algorithms, Optim. Methods Softw., 33, 1, 194-219 (2018) · Zbl 1390.90436
[21] An, L.; Tao, P., The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133, 23-46 (2005) · Zbl 1116.90122
[22] Bagirov, A.; Ugon, J.; Mirzayeva, H., Nonsmooth optimization algorithm for solving clusterwise linear regression problems, J. Optim. Theory Appl., 164, 3, 755-780 (2015) · Zbl 1311.65067
[23] Leisch, F., FlexMix: A general framework for finite mixture models and latent class regression in R, J. Stat. Softw., 11, 8, 1-18 (2004)
[24] Faria, S.; Soromenho, G., Fitting mixtures of linear regressions, J. Stat. Comput. Simul., 80, 201-225 (2010) · Zbl 1184.62118
[25] Clarke, F., (Optimization and Nonsmooth Analysis. Optimization and Nonsmooth Analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts (1983), Wiley) · Zbl 0582.49001
[26] Bagirov, A. M.; Karmitsa, N.; Mäkelä, M., Introduction to Nonsmooth Optimization (2014), Springer: Springer Cham · Zbl 1312.90053
[27] Horst, R.; Thoai, N., DC programming: overview, J. Optim. Theory Appl., 103, 1, 319-350 (1999)
[28] Tao, P.; An, L., Convex analysis approach to DC programming: theory, algorithms and applications, Acta Math. Vietnam., 22, 1, 289-355 (1997) · Zbl 0895.90152
[29] Tuy, H., (Convex Analysis and Global Optimization. Convex Analysis and Global Optimization, Nonconvex Optimization and Its Applications, vol. 22 (1998), Kluwer: Kluwer Dordrecht) · Zbl 0904.90156
[30] Gaudioso, M.; Giallombardo, G.; Miglionico, G.; Bagirov, A., Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations, J. Global Optim., 71, 1, 37-55 (2018) · Zbl 1418.90201
[31] Joki, K.; Bagirov, A.; Karmitsa, N.; Mäkelä, M.; Taheri, S., Double bundle method for nonsmooth DC optimization, SIAM J. Optim., 28, 2, 1892-1919 (2018) · Zbl 1401.90170
[32] Aragón Artacho, F.; Vuong, P., The boosted difference of convex functions algorithm for nonsmooth functions, SIAM J. Optim., 30, 1, 980-1006 (2020) · Zbl 1461.65119
[33] Byrd, R.; Lu, P.; Nocedal, J.; Zhu, C., A limited memory algorithm for bound constrained optimization, SIAM J. Sci. Comput., 16, 5, 1190-1208 (1995) · Zbl 0836.65080
[34] Zhu, C.; Byrd, R.; Lu, P.; Nocedal, J., L-bfgs-b: Fortran subroutines for large scale bound constrained optimization (1994)
[35] Dua, D.; Graff, C., UCI machine learning repository, irvine, ca: University of California, school of information and computer science (2019), http://archive.ics.uci.edu/ml
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.