We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A novel heuristic algorithm to solve penalized regression-based clustering model.
- Authors
Hasanzadeh Tavakkoli, Shadi; Forghani, Yahya; Sheibani, Reza
- Abstract
Penalized regression-based clustering model (PRClust) is an extension of "sum-of-norms" clustering model. Three previously proposed heuristic algorithms for solving PRClust are: (1) DC-CD, which combines the difference of convex programming (DC) and a coordinate-wise descent algorithm (CD), (2) DC-ADMM, which combines DC with the alternating direction method of multipliers (ADMM), and (3) ALT, which uses alternate optimization. DC-CD uses p × n × n - 1 / 2 scalar slack variables to solve PRClust, where n is the number of data and p is the number of their features. In each iteration of DC-CD, these slack variables and cluster centers are updated using a second-order cone programming (SOCP). DC-ADMM uses p × n × n - 1 scalar slack variables. In each iteration of DC-ADMM, these slack variables and cluster centers are updated with a standard ADMM. In this paper, first, PRClust is reformulated into an equivalent model. Then, a novel heuristic algorithm is proposed to solve the reformulated model. Our proposed algorithm needs only n × n - 1 / 2 scalar slack variables which are much less than those of DC-CD and DC-ADMM, and updates them using a simple equation in each iteration of the algorithm. Therefore, updating slack variables in our proposed algorithm is less time-consuming than that of DC-CD and DC-ADMM. Our proposed algorithm updates only cluster centers using an unconstrained convex quadratic problem. Therefore, our proposed unconstrained convex quadratic problem is much smaller than the SOCP of DC-CD which is used to update both cluster centers and slack variables. Meanwhile, ALT updates cluster centers using a SOCP, while our proposed algorithm updates cluster centers using an unconstrained convex quadratic problem with the same number of variables. Solving an unconstrained convex quadratic problem is less time-consuming than a SOCP with the same number of variables. Our experimental results on 12 datasets confirm that the runtime of our proposed algorithm is better than that of DC-ADMM and DC-CD.
- Subjects
CONVEX programming; HEURISTIC algorithms; ALGORITHMS; CONES
- Publication
Soft Computing - A Fusion of Foundations, Methodologies & Applications, 2020, Vol 24, Issue 12, p9215
- ISSN
1432-7643
- Publication type
Article
- DOI
10.1007/s00500-019-04448-8