DAG-Structured Clustering by Nearest Neighbors
DAG-Structured Clustering by Nearest Neighbors
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Nicholas Monath;M. Zaheer;Kumar Avinava Dubey;Amr Ahmed;A. McCallum
中科院分区：
文献类型：
--
作者：
Nicholas Monath;M. Zaheer;Kumar Avinava Dubey;Amr Ahmed;A. McCallum
分层聚类对树结构内的聚类的多粒度进行压缩编码。根据定义，层次结构无法捕获不包含在彼此中的不同分区。在本文中，我们提倡一种替代结构，用于表示多个聚类，有向无环图（DAG）。通过允许节点有多个父节点，DAG结构不仅比树更灵活，而且还允许点成为多个簇的成员。我们描述了一个可扩展的算法，Llama，它只是合并最近的邻居子结构，形成一个DAG结构。Llama发现了比最先进的基于树的技术更准确的结构，同时保持了对大规模集群基准的可扩展性。此外，我们支持所提出的算法与理论保证分离的数据，包括数据类型，不能正确聚类的基于树的算法。
Hierarchical clusterings compactly encode multiple granularities of clusters within a tree structure. Hierarchies, by definition, fail to capture di ↵ erent flat partitions that are not subsumed in one another. In this paper, we advocate for an alternative structure for representing multiple clusterings, a directed acyclic graph (DAG). By allowing nodes to have multiple parents, DAG structures are not only more flexible than trees, but also allow for points to be members of multiple clusters. We describe a scalable algorithm, Llama , which simply merges nearest neighbor substructures to form a DAG structure. Llama discovers structures that are more accurate than state-of-the-art tree-based techniques while remaining scalable to large-scale clustering benchmarks. Additionally, we support the proposed algorithm with theoretical guarantees on separated data, including types of data that cannot be correctly clustered by tree-based algorithms.