LOG-Means: Efficiently Estimating the Number of Clusters in Large Datasets
LOG-Means: Efficiently Estimating the Number of Clusters in Large Datasets
复制标题
DOI：
10.14778/3407790.3407813
复制
发表时间：
2020-07-01
影响因子：
2.5
通讯作者：
Schwarz, Holger
中科院分区：
文献类型：
--
作者：
Fritz, Manuel;Behringer, Michael;Schwarz, Holger
聚类是多方面应用中的一个基本要素。为了获得有价值的结果，聚类算法的参数，例如，集群的数量必须适当地设置，这是一个巨大的陷阱。为此，分析师依赖于他们的领域知识，以定义参数搜索空间。虽然有经验的分析师可能能够定义一个小的搜索空间，特别是新手分析师往往定义相当大的搜索空间，由于缺乏深入的领域知识。这些搜索空间可以通过估计聚类数的方法以不同的方式进行探索。在最坏的情况下，估计方法在给定的搜索空间中执行详尽的搜索，这会导致大数据集和大搜索空间的运行时间不可行。我们提出了对数均值，这是能够克服现有方法的这些问题。我们表明，对数均值提供了关于定义的搜索空间的次线性时间估计，因此非常适合大数据集和大搜索空间。在我们对Apache Spark集群的综合评估中，我们将LOG-Means与13种现有的估计方法进行了比较。评估结果表明，LOG-Means显着优于这些方法的运行时间和准确性。据我们所知，这是迄今为止对大型数据集和搜索空间进行的最系统的比较。
Clustering is a fundamental primitive in manifold applications. In order to achieve valuable results, parameters of the clustering algorithm, e.g., the number of clusters, have to be set appropriately, which is a tremendous pitfall. To this end, analysts rely on their domain knowledge in order to define parameter search spaces. While experienced analysts may be able to define a small search space, especially novice analysts often define rather large search spaces due to the lack of in-depth domain knowledge. These search spaces can be explored in different ways by estimation methods for the number of clusters. In the worst case, estimation methods perform an exhaustive search in the given search space, which leads to infeasible runtimes for large datasets and large search spaces. We propose LOG-Means, which is able to overcome these issues of existing methods. We show that LOG-Means provides estimates in sublinear time regarding the defined search space, thus being a strong fit for large datasets and large search spaces. In our comprehensive evaluation on an Apache Spark cluster, we compare LOG-Means to 13 existing estimation methods. The evaluation shows that LOG-Means significantly outperforms these methods in terms of runtime and accuracy. To the best of our knowledge, this is the most systematic comparison on large datasets and search spaces as of today.