Modified Convex Data Clustering Algorithm Based on Alternating Direction Method of Multipliers

Subject Areas : Journal of Computer & Robotics

Tahereh Esmaeili Abharian ¹ , Mohammad Bagher Menhaj ²

1 - Faculty of Computer and Information Technology Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran
2 - Department of Electrical Engineering Amirkabir University of Technology, Tehran, Iran

Received: 2015-05-10 Accepted : 2015-08-05 Published : 2015-03-01

Keywords: convex data clustering, initialization, global minimizer,

Abstract :

Knowing the fact that the main weakness of the most standard methods including k-means and hierarchical data clustering is their sensitivity to initialization and trapping to local minima, this paper proposes a modification of convex data clustering in which there is no need to be peculiar about how to select initial values. Due to properly converting the task of optimization to an equivalent convex optimization problem, the proposed data clustering algorithm can be indeed considered as a global minimizer. In this paper, a splitting method for solving the convex clustering problem is used called as Alterneting Direction Method of Multipliers (ADMM), a simple but powerful algorithm that is well suited to convex optimization. We demonstrate the performance of the proposed algorithm on real data examples. The simulation result easily approve that the Modified Convex Data Clustering (MCDC) algorithm provides separation more than the Convex Data Clustering (CDC) algorithm. Furthermore, complexity of solving the second part of MCDC problem is reduced from O(n2) to O(n).