×

zbMATH — the first resource for mathematics

Nonsmooth nonconvex optimization approach to clusterwise linear regression problems. (English) Zbl 1317.90242
Summary: Clusterwise regression consists of finding a number of regression functions each approximating a subset of the data. In this paper, a new approach for solving the clusterwise linear regression problems is proposed based on a nonsmooth nonconvex formulation. We present an algorithm for minimizing this nonsmooth nonconvex function. This algorithm incrementally divides the whole data set into groups which can be easily approximated by one linear regression function. A special procedure is introduced to generate a good starting point for solving global optimization problems at each iteration of the incremental algorithm. Such an approach allows one to find global or near global solution to the problem when the data sets are sufficiently dense. The algorithm is compared with the multistart Späth algorithm on several publicly available data sets for regression analysis.

MSC:
90C26 Nonconvex programming, global optimization
62H30 Classification and discrimination; cluster analysis (statistical aspects)
62J05 Linear regression; mixed models
Software:
Algorithm 39; UCI-ml
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrews, R. L.; Brusco, M. J.; Currim, I. S., Amalgamation of partitions from multiple segmentation bases: a comparison of non-model-based and model-based methods, European Journal of Operational Research, 201, 608-618, (2010) · Zbl 1179.90202
[2] Bagirov, A. M., Modified global k-means algorithm for minimum sum-of-squares clustering problems, Pattern Recognition, 41, 10, 3192-3199, (2008) · Zbl 1147.68669
[3] Bagirov, A. M.; Rubinov, A. M.; Soukhoroukova, N.; Yearwood, J., Supervised and unsupervised data classification via nonsmooth and global optimisation, TOP: Spanish Operations Research Journal, 11, 1-93, (2003) · Zbl 1048.65059
[4] Bagirov, A. M.; Ugon, J.; Webb, D., Fast modified global k-means algorithm for incremental cluster construction, Pattern Recognition, 44, 866-876, (2011) · Zbl 1213.68514
[5] Bagirov, A. M.; Yearwood, J., A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems, European Journal of Operational Research, 170, 2, 578-596, (2006) · Zbl 1085.90045
[6] Bazaraa, M. S.; Goode, J. J.; Rardin, R. L., A finite steepest ascent algorithm for maximizing piecewise linear concave functions, Journal of Optimization Theory and Applications, 26, 3, 437-442, (1978) · Zbl 0362.90114
[7] Boztug¨, Y.; Reutterer, Th., A combined approach for segment-specific market basket analysis, European Journal of Operational Research, 187, 294-312, (2008) · Zbl 1149.90083
[8] G. Caporossi, P. Hansen, Variable neighborhood search for least squares clusterwise regression, Technical report, Les Cahiers du GERAD, 2007.
[9] Carbonneau, R. A.; Caporossi, G.; Hansen, P., Globally optimal clusterwise regression by mixed logical-quadratic programming, European Journal of Operational Research, 212, 213-222, (2011)
[10] P. Cortez, A. Morais, A Data mining approach to predict forest fires using meteorological data, in: J. Neves, M.F. Santos, J. Machado (Eds.), New Trends in Artificial Intelligence, Proceedings of the 13th EPIA 2007 - Portuguese Conference on Artificial Intelligence, December, Guimaraes, Portugal, 2007, pp. 512-523.
[11] Cortez, P.; Cerdeira, A.; Almeida, F.; Matos, T.; Reis, J., Modeling wine preferences by data mining from physicochemical properties, Decision Support Systems, 47, 4, 547-553, (2009)
[12] 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
[13] DeSarbo, W. S.; Oliver, R. L.; Rangaswamy, A., A simulated annealing methodology for clusterwise linear regression, Psychometrika, 54, 4, 707-736, (1989)
[14] 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.
[15] García-Escudero, L. A.; Gordaliza, A.; Mayo-Iscar, A.; San Martín, R., Robust clusterwise linear regression through trimming, Computational Statistics and Data Analysis, 54, 3057-3069, (2010) · Zbl 1284.62198
[16] Lau, K. N.; Leung, P. L.; Tse, K. K., A mathematical programming approach to clusterwise regression model and its extensions, European Journal of Operational Research, 116, 640-652, (1999) · Zbl 0993.62052
[17] Likas, A.; Vlassis, N.; Verbeek, J., The global k-means clustering algorithm, Pattern Recognition, 36, 2, 451-461, (2003)
[18] Moore, D. S.; McCabe, G. P., Introduction to the practice of statistics, (1998), W.H. Freeman New York
[19] Nocedal, J.; Wright, S. J., Numerical optimization, (2006), Springer · Zbl 1104.65059
[20] Preda, C.; Saporta, G., Clusterwise PLS regression on a stochastic process, Computational Statistics & Data Analysis, 49, 99-108, (2005) · Zbl 1429.62299
[21] Qian, G.; Wu, Y.; Shao, Q., A procedure for estimating the number of clusters in logistic regression clustering, Journal of Classification, 26, 183-199, (2009) · Zbl 1337.62138
[22] Shao, Q.; Y. Wu, A consistent procedure for determining the number of clusters in regression clustering, Journal of Statistical Planning and Inference, 135, 461-476, (2005) · Zbl 1074.62042
[23] Späth, H., Algorithm 39: clusterwise linear regression, Computing, 22, 367-373, (1979) · Zbl 0387.65028
[24] Späth, H., Algorithm 48: a fast algorithm for clusterwise linear regression, Computing, 29, 175-181, (1981) · Zbl 0485.65030
[25] A. Tsanas, M.A. Little, P.E. McSharry, L.O. Ramig, Accurate telemonitoring of Parkinson’s disease progression by non-invasive speech tests, in: IEEE Transactions on Biomedical Engineering, to appear.
[26] UCI repository of machine learning databases. <http://www.ics.uci.edu/mlearn/MLRepository.htmlS>.
[27] P.F. Velleman, DASL, the Data and Story Library, 2010. <http://lib.stat.cmu.edu/DASL/DataArchive.html>.
[28] Wedel, M.; Kistemaker, C., Consumer benefit segmentation using clusterwise linear regression, International Journal of Research in Marketing, 6, 1, 45-59, (1989)
[29] Yeh, I-Cheng, Modeling of strength of high performance concrete using artificial neural networks, Cement and Concrete Research, 28, 12, 1797-1808, (1998)
[30] Yeh, I-Cheng, Modeling slump flow of concrete using second-order regressions and artificial neural networks, Cement and Concrete Composites, 29, 6, 474-480, (2007)
[31] Zhang, B., Regression clustering, (Proceedings of the Third IEEE International Conference on Data Mining (ICDM03), (2003), IEEE Computer Society), 451-458
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.