作者单位：Danial Lashkari, Polina Golland, MIT
发表时间：NIPS’07
聚类问题是一个很重要的无监督学习的问题。传统方法将输入空间转换到某种空间中，然后使用传统的聚类方法如K-means方法进行聚类，即最大化类间间距和最小化类内间距。Soft k-means方法通过EM(Expertation Maximization)算法来求极大似然参数的。然而，这种方法由于是非凸的，参数容易陷在初值附近的局部最小值中，因此对于大数据集而言表现并不理想。作者希望能够将问题转化为凸问题，这样就可以无条件的达到全局最优了。
有工作证明：对数据进行混合模型建模（回忆一下高斯混合分布，对数据做聚类，可以理解成我们先构造了一个高斯混合分布，然后再利用它得到了我们的聚类，虽然你在实现过程中并没有看到任何高斯混合分布的影子）的过程，可以认为是在迭代地最小化两组概率分布。这证明了（笔者注：这怎么证明了？）对数据进行混合模型建模（从而求聚类）的过程中的cost function的“非凸性”来自于这个混合模型各个部件的参数化。换句话说，高斯混合分布中的参数是不确定的，正是由于这个不确定，需要通过某种方式估计出来，才让最终的cost function变得不稳定。所以显然，如果我们能让它确定，则就可以免去这个“非凸性”。
作者提出了一个重要的假设：对于每一个聚类（到底有多少个聚类我们并不知道，但是假设数据是有聚类的），总存在一个数据（称为exemplar），它恰恰好处在这个聚类的聚类中心上。这个假设还是挺合理的，当我们的数据足够多的时候，可以近似的认为存在这么一个数据。毕竟当数据少的时候，k-means做得很好，只有当数据多的时候，k-means才会失败。这样的话，聚类中心变成确定的（虽然我们并不知道到底哪个数据点是聚类中心，但是毕竟我们省略了聚类中心这个未知的参数）。作者说，如果我们让每个样本点都是exemplar，就可以让cost function变成凸的。
这个方法的好处是：1、可以保证得到全局最小值。2、无需给定类数。
具体而言，我们知道，利用极大似然法估计数据的混合高斯分布从而进行聚类的方法，使用的是这个cost function：
式中的$\bf m$指的就是上面说的高斯分布的均值，也就是所谓的聚类中心。在传统方法中它是一个未知量，需要估计出来。而$\bf q$是各部件的权重（可以理解为调节混合高斯分布的一组参数，没有了它的话，就是一堆高斯分布求和，并不能做到千变万化）。式中的$f(\cdot)$是指数函数家族中的一个。但是在实际应用中，就是正态分布的那个概率密度函数。
作者提出的cost function是：
可以注意到，由于上文提到的exemplar假设，作者把待定系数$\bf m$去掉了，改成了$x_j$，再由于作者假设每一个样本点都是一个聚类中心，因此就有$k = n$。
可以看到，这样的cost function，关于待定系数q是单调的，因此自然就是凸的，可以求解全局最小值。
作者同样提出了训练未知参数$\bf q$的方法，定义$P(x)$为数据x出现的概率，$f_j(x)=e^{-\beta d(x, x_j)}$：
这个update方法的复杂度是O(n^2)，而且需要看一遍所有的数据。这在当前的情况下是不实用的。后续一些工作使用了Nearest neighbor算法来简化这个过程（“Weakly SUpervised Object Detection with Convex Clustering”）。这篇工作对比起Soft k-means取得了5%至15%的提升。
