×

zbMATH — the first resource for mathematics

Clusterwise support vector linear regression. (English) Zbl 1443.90281
Summary: In clusterwise linear regression (CLR), the aim is to simultaneously partition data into a given number of clusters and to find regression coefficients for each cluster. In this paper, we propose a novel approach to model and solve the CLR problem. The main idea is to utilize the support vector machine (SVM) approach to model the CLR problem by using the SVM for regression to approximate each cluster. This new formulation of the CLR problem is represented as an unconstrained nonsmooth optimization problem, where we minimize a difference of two convex (DC) functions. To solve this problem, a method based on the combination of the incremental algorithm and the double bundle method for DC optimization is designed. Numerical experiments are performed to validate the reliability of the new formulation for CLR and the efficiency of the proposed method. The results show that the SVM approach is suitable for solving CLR problems, especially, when there are outliers in data.
MSC:
90C26 Nonconvex programming, global optimization
49J52 Nonsmooth analysis
62J05 Linear regression; mixed models
62H30 Classification and discrimination; cluster analysis (statistical aspects)
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bagirov, A. M.; Karmitsa, N.; Mäkelä, M. M., Introduction to nonsmooth optimization: Theory, practice and software (2014), Springer: Springer Cham, Heidelberg · Zbl 1312.90053
[2] Bagirov, A. M.; Mahmood, A.; Barton, A., Prediction of monthly rainfall in Victoria, Australia: Clusterwise linear regression approach, Atmospheric Research, 188, 15, 20-29 (2017)
[3] Bagirov, A. M.; Taheri, S., DC programming algorithm for clusterwise linear L1 regression, Journal of the Operations Research Society of China, 5, 2, 233-256 (2017) · Zbl 1390.90437
[4] Bagirov, A. M.; Ugon, J., Nonsmooth DC programming approach to clusterwise linear regression: Optimality conditions and algorithms, Optimization Methods and Software, 33, 1, 194-219 (2018) · Zbl 1390.90436
[5] Bagirov, A. M.; Ugon, J.; Mirzayeva, H., Nonsmooth nonconvex optimization approach to clusterwise linear regression problems, European Journal of Operational Research, 229, 1, 132-142 (2013) · Zbl 1317.90242
[6] Bagirov, A. M.; Ugon, J.; Mirzayeva, H., An algorithm for clusterwise linear regression based on smoothing techniques, Optimization Letters, 9, 2, 375-390 (2015) · Zbl 1311.90106
[7] Bagirov, A. M.; Ugon, J.; Mirzayeva, H., Nonsmooth optimization algorithm for solving clusterwise linear regression problems, Journal of Optimization Theory and Applications, 164, 3, 755-780 (2015) · Zbl 1311.65067
[8] Bertsimas, D.; Shioda, R., Classification and regression via integer optimization, Operations Research, 55, 2, 252-271 (2007) · Zbl 1167.90593
[9] Carbonneau, R. A.; Caporossi, G.; Hansen, P., Globally optimal clusterwise regression by mixed logical-quadratic programming, European Journal of Operational Research, 212, 1, 213-222 (2011)
[10] Carbonneau, R. A.; Caporossi, G.; Hansen, P., Extensions to the repetitive branch and bound algorithm for globally optimal clusterwise regression, Computers & Operations Research, 39, 11, 2748-2762 (2012) · Zbl 1251.90313
[11] Clarke, F. H., Optimization and nonsmooth analysis (1983), Wiley-Interscience: Wiley-Interscience New York · Zbl 0582.49001
[12] Collobert, R.; Bengio, S., SVMTorch: Support vector machines for large-scale regression problems, Journal of Machine Learning Research, 1, 143-160 (2001) · Zbl 1052.68111
[13] Data set available in UCI machine learning repository http://archive.ics.uci.edu/ml (June 11th, 2016).
[14] DeSarbo, W. S.; Cron, W. L., A maximum likelihood methodology for clusterwise linear regression, Journal of Classification, 5, 2, 249-282 (1988) · Zbl 0692.62052
[15] DeSarbo, W. S.; Oliver, R. L.; Rangaswamy, A., A simulated annealing methodology for clusterwise linear regression, Psychometrika, 54, 4, 707-736 (1989)
[16] Dempster, A. P.; Laird, N. M.; Rubin, D. B., Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society, Series B (Methodological), 39, 1, 1-38 (1977) · Zbl 0364.62022
[17] Available in web page http://archive.ics.uci.edu/ml (April 8th, 2016).
[18] D’Urso, P.; Massari, R.; Santoro, A., A class of fuzzy clusterwise regression models, Information Sciences, 180, 24, 4737-4762 (2010) · Zbl 1204.62112
[19] Gaffney, S.; Smyth, P., Trajectory clustering using mixtures of regression models, Proceedings of the 5th ACM SIGKDD international conference on knowledge discovery and data mining, 63-72 (1999)
[20] Ganjigatti, J.; Pratihar, D. K.; Choudhury, A. R., Global versus cluster-wise regression analyses for prediction of bead geometry in MIG welding process, Journal of Materials Processing Technology, 189, 1-3, 352-366 (2007)
[21] Garcìa-Escudero, L. A.; Gordaliza, A.; Mayo-Iscar, A.; San Martin, R., Robust clusterwise linear regression through trimming, Computational Statistics & Data Analysis, 54, 12, 3057-3069 (2010) · Zbl 1284.62198
[22] Grün, B.; Leisch, F., FlexMix version 2: Finite mixtures with concomitant variables and varying and constant parameters, Journal of Statistical Software, 28, 4, 1-35 (2008)
[23] Haarala, M.; Miettinen, K.; Mäkelä, M. M., New limited memory bundle method for large-scale nonsmooth optimization, Optimization Methods and Software, 19, 6, 673-692 (2004) · Zbl 1068.90101
[24] Haarala, N.; Miettinen, K.; Mäkelä, M. M., Globally convergent limited memory bundle method for large-scale nonsmooth optimization, Mathematical Programming, 109, 1, 181-205 (2007) · Zbl 1278.90451
[25] Horst, R.; Thoai, N. V., DC programming: Overview, Journal of Optimization Theory and Applications, 103, 1, 1-43 (1999) · Zbl 1073.90537
[26] Hubert, L.; Arabie, P., Comparing partitions, Journal of Classification, 2, 193-218 (1985)
[27] Joki, K.; Bagirov, A. M.; Karmitsa, N.; Mäkelä, M. M., A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes, Journal of Global Optimization, 68, 3, 501-535 (2017) · Zbl 1369.90137
[28] Joki, K.; Bagirov, A. M.; Karmitsa, N.; Mäkelä, M. M.; Taheri, S., New bundle method for clusterwise linear regression utilizing support vector machines, TUCS technical report no 1190 (2017), Turku Centre for Computer Science, Turku
[29] Joki, K.; Bagirov, A. M.; Karmitsa, N.; Mäkelä, M. M.; Taheri, S., Double bundle method for finding Clarke stationary points in nonsmooth DC programming, SIAM Journal on Optimization, 28, 2, 1892-1919 (2018) · Zbl 1401.90170
[30] Joki, K.; Bagirov, A. M., A bundle methods for nonsmooth DC optimization, (Bagirov, A.; Gaudioso, M.; Karmitsa, N.; Mäkelä, M. M.; Taheri, S., Numerical nonsmooth optimization (2020), Springer: Springer Cham)
[31] Karmitsa, N.; Bagirov, A. M.; Taheri, S., Limited memory bundle method for solving large clusterwise linear regression problems, TUCS technical report no 1172 (2016), Turku Centre for Computer Science, Turku
[32] Data set available in UCI machine learning repository http://archive.ics.uci.edu/ml (June 11th, 2016).
[33] Kiwiel, K. C., Proximity control in bundle methods for convex nondifferentiable minimization, Mathematical Programming, 46, 1-3, 105-122 (1990) · Zbl 0697.90060
[34] Lau, K.; Leung, P.; Tse, K., A mathematical programming approach to clusterwise regression model and its extensions, European Journal of Operational Research, 116, 3, 640-652 (1999) · Zbl 0993.62052
[35] Le Thi, H. A.; Pham Dinh, T., Solving a class of linearly constrained indefinite quadratic problems by D.C. algorithms, Journal of Global Optimization, 11, 3, 253-285 (1997) · Zbl 0905.90131
[36] Le Thi, H. A.; Pham Dinh, T., The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Annals of Operations Research, 133, 1-4, 23-46 (2005) · Zbl 1116.90122
[37] Mäkelä, M. M., Survey of bundle methods for nonsmooth optimization, Optimization Methods and Software, 17, 1, 1-29 (2002) · Zbl 1050.90027
[38] Mäkelä, M. M.; Neittaanmäki, P., Nonsmooth optimization: Analysis and algorithms with applications to optimal control (1992), World Scientific Publishing Co: World Scientific Publishing Co Singapore · Zbl 0757.49017
[39] McComb, C., Adjusted rand index, GITHUB (2020), https://www.github.com/cmccomb/rand_index (December 23rd, 2019)
[40] Park, Y. W.; Jiang, Y.; Klabjan, D.; Williams, L., Algorithms for generalized clusterwise linear regression, INFORMS Journal on Computing, 29, 2, 301-317 (2017) · Zbl 06785476
[41] Pham Dinh, T.; Le Thi, H. A., Convex analysis approach to D.C. programming: Theory, algorithms and applications, Acta Mathematica Vietnamica, 22, 1, 289-355 (1997) · Zbl 0895.90152
[42] Poggi, J.-M.; Portier, B., PM10 forecasting using clusterwise regression, Atmospheric Environment, 45, 38, 7005-7014 (2011)
[43] Preda, C.; Saporta, G., Clusterwise PLS regression on a stochastic process, Computational Statistics & Data Analysis, 49, 1, 99-108 (2005) · Zbl 1429.62299
[44] Rockafellar, R. T., Convex analysis (1970), Princeton University Press: Princeton University Press Princeton, New Jersey · Zbl 0202.14303
[45] Lukšan, L., Dual method for solving a special problem of quadratic programming as a subproblem at linearly constrained nonlinear minmax approximation, Kybernetika, 20, 6, 445-457 (1984) · Zbl 0552.90074
[46] Schramm, H.; Zowe, J., A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM Journal on Optimization, 2, 1, 121-152 (1992) · Zbl 0761.90090
[47] Smola, A. J.; Schölkopf, B., A tutorial on support vector regression, Statistics and Computing, 14, 3, 199-222 (2004)
[48] Späth, H., Algorithm 39: Clusterwise linear regression, Computing, 22, 4, 367-373 (1979) · Zbl 0387.65028
[49] Späth, H., Clusterwise linear least absolute deviations regression, Computing, 37, 4, 371-378 (1986) · Zbl 0594.65100
[50] Strekalovsky, A. S., On local search in d.c. optimization problems, Applied Mathematics and Computation, 255, 73-83 (2015) · Zbl 1338.90327
[51] Data set available in UCI machine learning repository http://archive.ics.uci.edu/ml (June 11th, 2016).
[52] Tuy, H., Convex analysis and global optimization (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0904.90156
[53] Wedel, M.; Kistemaker, C., Consumer benefit segmentation using clusterwise linear regression, International Journal of Research in Marketing, 6, 1, 45-59 (1989)
[54] Data set available in UCI machine learning repository http://archive.ics.uci.edu/ml (June 11th, 2016).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.