Significant DBSCAN towards Statistically Robust Clustering
Significant DBSCAN towards Statistically Robust Clustering
复制标题
DOI：
10.1145/3340964.3340968
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Yiqun Xie;S. Shekhar
中科院分区：
文献类型：
--
作者：
Yiqun Xie;S. Shekhar
给定一组地理分布的点，我们的目标是检测具有统计意义的不同形状和密度的集群。空间聚类已经被广泛地用于许多重要的社会应用，包括公共健康和安全、交通、环境等。该问题是具有挑战性的，因为许多应用领域对误报具有低容忍度（例如，在社区中谎称犯罪集群可能对居民产生严重的负面影响），而且集群往往形状不规则。在相关工作中，空间扫描统计是一种流行的技术，可以检测重要的聚类，但它要求聚类具有某些预定义的形状（例如，圆、环）。相反，基于密度的方法（例如，DBSCAN）可以有效地找到任意形状的簇，但不考虑统计意义，使它们容易受到虚假模式的影响。为了解决这些局限性，我们首先提出了一个基于DBSCAN聚类的统计显著性建模。然后，我们提出了一个基线蒙特卡罗方法来估计集群的重要性和双重收敛算法来加速计算。实验结果表明，显著DBSCAN算法能有效地去除随机模式，双收敛算法能大大减少执行时间。
Given a collection of geo-distributed points, we aim to detect statistically significant clusters of varying shapes and densities. Spatial clustering has been widely used many important societal applications, including public health and safety, transportation, environment, etc. The problem is challenging because many application domains have low-tolerance to false positives (e.g., falsely claiming a crime cluster in a community can have serious negative impacts on the residents) and clusters often have irregular shapes. In related work, the spatial scan statistic is a popular technique that can detect significant clusters but it requires clusters to have certain predefined shapes (e.g., circles, rings). In contrast, density-based methods (e.g., DBSCAN) can find clusters of arbitrary shape efficiently but do not consider statistical significance, making them susceptible to spurious patterns. To address these limitations, we first propose a modeling of statistical significance in DBSCAN based clustering. Then, we propose a baseline Monte Carlo method to estimate the significance of clusters and a Dual-Convergence algorithm to accelerate the computation. Experiment results show that significant DBSCAN is very effective in removing chance patterns and the Dual-Convergence algorithm can greatly reduce execution time.