×

zbMATH — the first resource for mathematics

DC programming algorithm for clusterwise linear \(L_1\) regression. (English) Zbl 1390.90437
Summary: The aim of this paper is to develop an algorithm for solving the clusterwise linear least absolute deviations regression problem. This problem is formulated as a nonsmooth nonconvex optimization problem, and the objective function is represented as a difference of convex functions. Optimality conditions are derived by using this representation. An algorithm is designed based on the difference of convex representation and an incremental approach. The proposed algorithm is tested using small to large artificial and real-world data sets.

MSC:
90C26 Nonconvex programming, global optimization
90C56 Derivative-free methods and methods using generalized derivatives
Software:
Algorithm 39; UCI-ml
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Preda, C; Saporta, G, Clusterwise PLS regression on a stochastic process, Comput. Stat. Data Anal., 49, 99-108, (2005) · Zbl 1429.62299
[2] Wedel, M; Kistemaker, C, Consumer benefit segmentation using clusterwise linear regression, Int. J. Res. Mark., 6, 45-59, (1989)
[3] Späth, H, Algorithm 39: clusterwise linear regression, Computing, 22, 367-373, (1979) · Zbl 0387.65028
[4] Gaffney, S., Smyth, P.: Trajectory clustering using mixtures of regression models. In: Chaudhuri, S., Madigan, D. (eds.) Proceedings of the ACM Conference on Knowledge Discovery and Data Mining, pp. 63-72 (1999)
[5] DeSarbo, W; Cron, W, A maximum likelihood methodology for clusterwise linear regression, J. Classif., 5, 249-282, (1988) · Zbl 0692.62052
[6] Garsia-Escudero, L.A., Gordaliza, A., Mayo-Iscar, A., San Martin, R.: Robust clusterwise linear regression through trimming. Comput. Stat. Data Anal. 54, 3057-3069 (2010) · Zbl 1284.62198
[7] DeSarbo, WS; Oliver, RL; Rangaswamy, A, A simulated annealing methodology for clusterwise linear regression, Psychometrika, 54, 707-736, (1989)
[8] Carbonneau, RA; Caporossi, G; Hansen, P, Extensions to the repetitive branch-and-bound algorithm for globally-optimal clusterwise regression, Comput. Oper. Res., 39, 2748-2762, (2012) · Zbl 1251.90313
[9] Bagirov, A; Ugon, J; Mirzayeva, H, Nonsmooth nonconvex optimization approach to clusterwise linear regression problems, Eur. J. Oper. Res., 229, 132-142, (2013) · Zbl 1317.90242
[10] Bagirov, A; Ugon, J; Mirzayeva, H, An algorithm for clusterwise linear regression based on smoothing techniques, Optim. Lett., 9, 375-390, (2015) · Zbl 1311.90106
[11] Bagirov, A; Ugon, J; Mirzayeva, H, Nonsmooth optimization algorithm for solving clusterwise linear regression problems, J. Optim. Theory Appl., 164, 755-780, (2015) · Zbl 1311.65067
[12] Spath, H, Clusterwise linear least absolute deviations regression, Computing, 37, 371-378, (1986) · Zbl 0594.65100
[13] Meier, J, A fast algorithm for clusterwise linear absolute deviations regression, OR Spektrum, 9, 187-189, (1987) · Zbl 0628.65150
[14] Rockafellar, R.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[15] Clarke, F.: Optimization and Nonsmooth Analysis. Canadian Mathematical Society Series of Monographs. Wiley, New York (1983) · Zbl 0582.49001
[16] 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
[17] Horst, R; Thoai, N, DC programming: overview, J. Optim. Theory Appl., 103, 1-43, (1999) · Zbl 1073.90537
[18] Strekalovsky, A, On local search in DC optimization problems, Appl. Math. Comput., 255, 73-83, (2015) · Zbl 1338.90327
[19] Tao, P; An, L, Convex analysis approach to DC programming: theory, Acta Math. Vietnam., 22, 289-355, (1997) · Zbl 0895.90152
[20] Tuy, H.: Convex Analysis and Global Optimization. Kluwer, Dordrecht (1998) · Zbl 0904.90156
[21] Demyanov, V., Rubinov, A.: Constructive Nonsmooth Analysis. Approximation & Optimization. Peter Lang, Frankfurt am Main (1995) · Zbl 0887.49014
[22] Bagirov, A., Karmitsa, N., Makela, M.: Introduction to Nonsmooth Optimization. Springer, Cham (2014) · Zbl 1312.90053
[23] Feng, Z; Yiu, K; Teo, K, A smoothing approach for the optimal parameter selection problem with continuous inequality constraint, Optim. Methods Softw., 28, 689-705, (2013) · Zbl 1278.93002
[24] Bagirov, A; Taheri, S; Ugon, J, Nonsmooth dc programming approach to the minimum sum-of-squares clustering problems, Pattern Recognit., 53, 12-24, (2016) · Zbl 1412.68200
[25] Carbonneau, R.: Datasets for clusterwise linear regression. http://rcarbonneau.com/ClusterwiseRegressionDatasets.htm (2015)
[26] Bache, K., Lichman, M.: UCI Machine Learning Repository. University of California, Irvine, School of Information and Computer Sciences, 2013. http://www.ics.uci.edu/ mlearn/MLRepository.html · Zbl 0594.65100
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.