Splitting Methods for Convex Clustering.
Splitting Methods for Convex Clustering.
复制标题
DOI：
10.1080/10618600.2014.948181
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Lange K
中科院分区：
文献类型：
--
作者：
Chi EC;Lange K
聚类是许多科学应用中的一个基本问题。然而，k-means、高斯混合模型和分层聚类等标准方法受到局部最小值的困扰，有时会出现严重的次优情况。最近引入的k-means和分层聚类的凸松弛使聚类质心彼此收缩，并确保一个唯一的全局最小化。在这项工作中，我们提出了两种分裂方法来解决凸聚类问题。第一种是乘法器交替方向法（ADMM）的实例；第二种是交替最小化算法（AMA）的实例。与先前考虑的算法相比，我们的ADMM和AMA公式为解决先前研究规范下的凸聚类问题提供了简单而统一的框架，并为潜在的新规范打开了大门。我们在模拟和真实数据示例上演示了算法的性能。虽然两种算法之间的差异表面上看起来很小，但复杂性分析和数值实验表明，AMA的效率要高得多。这篇文章在网上有补充材料。
Clustering is a fundamental problem in many scientific applications. Standard methods such as k-means, Gaussian mixture models, and hierarchical clustering, however, are beset by local minima, which are sometimes drastically suboptimal. Recently introduced convex relaxations of k-means and hierarchical clustering shrink cluster centroids toward one another and ensure a unique global minimizer. In this work we present two splitting methods for solving the convex clustering problem. The first is an instance of the alternating direction method of multipliers (ADMM); the second is an instance of the alternating minimization algorithm (AMA). In contrast to previously considered algorithms, our ADMM and AMA formulations provide simple and unified frameworks for solving the convex clustering problem under the previously studied norms and open the door to potentially novel norms. We demonstrate the performance of our algorithm on both simulated and real data examples. While the differences between the two algorithms appear to be minor on the surface, complexity analysis and numerical experiments show AMA to be significantly more efficient. This article has supplemental materials available online.