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

Journal of Computer & Robotics

مقاله 5، دوره 8، شماره 2، مهر 2015، صفحه 33-41   

نویسندگان

Tahereh Esmaeili Abharian^{* 1}؛ Mohammad Bagher Menhaj²

¹Faculty of Computer and Information Technology Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

²Department of Electrical Engineering Amirkabir University of Technology, Tehran, Iran

چکیده

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(n²) to O(n).

کلیدواژه‌ها

convex data clustering؛ initialization؛ global minimizer