We introduce Grinch, a new algorithm for large-scale, non-greedy hierarchical clustering with general linkage functions that compute arbitrary similarity between two point sets. The key components of Grinch are its rotate and graft subroutines that efficiently reconfigure the hierarchy as new points arrive, supporting discovery of clusters with complex structure. Grinch is motivated by a new notion of separability for clustering with linkage functions: we prove that when the model is consistent with a ground-truth clustering, Grinch is guaranteed to produce a cluster tree containing the ground-truth, independent of data arrival order. Our empirical results on benchmark and author coreference datasets (with standard and learned linkage functions) show that Grinch is more accurate than other scalable methods, and orders of magnitude faster than hierarchical agglomerative clustering.

Grinch是一种新的算法，用于支持具有任意相似度的非贪婪层次聚类，该算法以其旋转和嫁接子程序为关键组件，可以快速重新配置层次结构，支持发现具有复杂结构的聚类，并且在数据到达顺序独立的情况下能够保证生成包含基本真值的聚类树。该算法在基准和作者共现数据集上（使用标准和学习链接函数）得到了良好的实验结果，其准确性超过了其他可扩展方法，并快了数个数量级以上。

可扩展的树嫁接层次聚类