Statistical Guarantees for Consensus Clustering
Statistical Guarantees for Consensus Clustering
复制标题
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Zhixin Zhou;Gautam Dudeja;A. Amini
中科院分区：
文献类型：
--
作者：
Zhixin Zhou;Gautam Dudeja;A. Amini
考虑聚类n个对象的问题。可以应用多个算法来产生相同对象的N个潜在不同的集群，即，将n个对象划分成K个组。即使是单一的随机化算法也可以输出不同的聚类。当一个人从贝叶斯模型的后部采样，或者从随机初始化运行多个MCMC链时，通常会发生这种情况。于是，一项自然的任务就是在这些不同的群体中形成共识。在无监督环境中的挑战是，不同输入的聚类之间的最佳匹配是未知的。我们将这个问题建模为找到一个相对于错别率的重心(也称为Fréchet平均值)。我们证明，通过将问题提升到关联矩阵空间，可以推导出绕过最优匹配知识的聚集算法。我们分析了随机标签扰动模型下聚集算法的统计性能，并证明了K-Means类算法和局部求精步骤可以获得接近最优的性能，并且速率在N中以指数级的速度衰减。数值实验表明了所提方法的有效性。
Consider the problem of clustering n objects. One can apply multiple algorithms to produce N potentially different clustersings of the same objects, that is, partitions of the n objects into K groups. Even a single randomized algorithm can output different clusterings. This often happens when one samples from the posterior of a Bayesian model, or runs multiple MCMC chains from random initializations. A natural task is then to form a consensus among these different clusterings. The challenge in an unsupervised setting is that the optimal matching between clusters of different inputs is unknown. We model this problem as finding a barycenter (also known as Fréchet mean) relative to the misclassification rate. We show that by lifting the problem to the space of association matrices, one can derive aggregation algorithms that circumvent the knowledge of the optimal matchings. We analyze the statistical performance of aggregation algorithms under a stochastic label perturbation model, and show that a K-means type algorithm followed by a local refinement step can achieve near optimal performance, with a rate that decays exponentially fast in N . Numerical experiments show the effectiveness of the proposed methods.