标题： 确定性聚类的恢复 显示英文标题

标题： Guaranteed Recovery of Unambiguous Clusters

摘要： 聚类通常是一个具有挑战性的问题，因为“正确的”聚类应该是什么存在固有的模糊性。 即使簇的数量$K$已知，这种模糊性往往仍然存在，尤其是在不同簇之间的密度存在变化时，且簇具有多个相对分离的高密度区域。 本文提出了一种信息论方法来表征何时一个$K$-聚类是模糊的，并设计了一个算法，只要聚类是明确的，就可以恢复该聚类。 这一表征形式化了当一个簇内的两个高密度区域足够分离以至于看起来更像两个不同的簇，而不是$K$-聚类中的两个真正不同的簇的情况。 该算法首先使用基于密度的方法识别出$K$个部分簇（或“种子”），然后以贪婪的方式将未聚类点添加到初始的$K$个部分簇中，以形成完整的聚类。 我们实现并测试了一种经过修改的算法版本，以有效处理重叠簇，并观察到它在许多数据集上需要较少的参数选择，并且性能优于广泛使用的非凸簇恢复算法。 显示英文摘要

摘要： Clustering is often a challenging problem because of the inherent ambiguity in what the "correct" clustering should be. Even when the number of clusters $K$ is known, this ambiguity often still exists, particularly when there is variation in density among different clusters, and clusters have multiple relatively separated regions of high density. In this paper we propose an information-theoretic characterization of when a $K$-clustering is ambiguous, and design an algorithm that recovers the clustering whenever it is unambiguous. This characterization formalizes the situation when two high density regions within a cluster are separable enough that they look more like two distinct clusters than two truly distinct clusters in the $K$-clustering. The algorithm first identifies $K$ partial clusters (or "seeds") using a density-based approach, and then adds unclustered points to the initial $K$ partial clusters in a greedy manner to form a complete clustering. We implement and test a version of the algorithm that is modified to effectively handle overlapping clusters, and observe that it requires little parameter selection and displays improved performance on many datasets compared to widely used algorithms for non-convex cluster recovery.