Significant DBSCAN+: Statistically Robust Density-based Clustering
Significant DBSCAN+: Statistically Robust Density-based Clustering
复制标题
DOI：
10.1145/3474842
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Yiqun Xie;X. Jia;S. Shekhar;Han Bao;Xun Zhou
中科院分区：
文献类型：
--
作者：
Yiqun Xie;X. Jia;S. Shekhar;Han Bao;Xun Zhou
聚类检测在公共卫生、公共安全、交通等领域有着重要的应用和广泛的应用。给定一组数据点，我们的目标是在集群具有统计显著性的约束下，检测具有不同几何形状和密度的密度连接的空间集群。这个问题是具有挑战性的，因为许多社会应用和领域科学研究对虚假结果的容忍度很低，而且集群可能具有任意形状和不同的密度。作为数据挖掘和学习的经典主题，已经开发了无数的技术来检测具有不同形状和密度的聚类（例如，基于密度的，分层的，光谱的或深度聚类方法）。然而，这些技术中的绝大多数都没有考虑统计的严谨性，并且容易检测到由于自然随机性而形成的虚假集群。另一方面，扫描统计方法明确地控制了虚假结果的比率，但它们通常假设一个过度密度的单一“热点”，并且许多依赖于进一步的假设，例如细分的输入空间。为了结合这两种工作的优势，我们提出了一种统计上稳健的多尺度DBSCAN公式，即显著DBSCAN+，以识别密度连接的显著集群。正如我们将展示的，结合统计严密性是一种强大的机制，它允许新的显著DBSCAN+在各种场景中胜过最先进的集群技术。我们还提出了计算增强来加快所提出的方法。实验结果表明，显著DBSCAN+可以同时提高真簇检测的成功率（例如，F1绝对分数提高10-20%），并大幅降低虚假结果的比率（例如，在100个数据集上从数千/数百个虚假检测到没有或只有几个），并且加速方法可以提高聚类和非聚类数据的效率。
Cluster detection is important and widely used in a variety of applications, including public health, public safety, transportation, and so on. Given a collection of data points, we aim to detect density-connected spatial clusters with varying geometric shapes and densities, under the constraint that the clusters are statistically significant. The problem is challenging, because many societal applications and domain science studies have low tolerance for spurious results, and clusters may have arbitrary shapes and varying densities. As a classical topic in data mining and learning, a myriad of techniques have been developed to detect clusters with both varying shapes and densities (e.g., density-based, hierarchical, spectral, or deep clustering methods). However, the vast majority of these techniques do not consider statistical rigor and are susceptible to detecting spurious clusters formed as a result of natural randomness. On the other hand, scan statistic approaches explicitly control the rate of spurious results, but they typically assume a single “hotspot” of over-density and many rely on further assumptions such as a tessellated input space. To unite the strengths of both lines of work, we propose a statistically robust formulation of a multi-scale DBSCAN, namely Significant DBSCAN+, to identify significant clusters that are density connected. As we will show, incorporation of statistical rigor is a powerful mechanism that allows the new Significant DBSCAN+ to outperform state-of-the-art clustering techniques in various scenarios. We also propose computational enhancements to speed-up the proposed approach. Experiment results show that Significant DBSCAN+ can simultaneously improve the success rate of true cluster detection (e.g., 10–20% increases in absolute F1 scores) and substantially reduce the rate of spurious results (e.g., from thousands/hundreds of spurious detections to none or just a few across 100 datasets), and the acceleration methods can improve the efficiency for both clustered and non-clustered data.