DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN
DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN
复制标题
DOI：
10.1145/3068335
复制
发表时间：
2017-08-01
影响因子：
1.8
通讯作者：
Xu, Xiaowei
中科院分区：
文献类型：
--
作者：
Schubert, Erich;Sander, Jorg;Xu, Xiaowei
在SIGMOD 2015上，一篇题为“DBSCAN重访：错误声明、不可修复性和近似”的文章获得了会议最佳论文奖。在这篇技术通信中，我们想指出DBSCAN表示方式中的一些不准确之处，以及为什么批评应该针对空间索引结构（如r树）的性能假设，而不是针对可以使用这些索引的算法。我们还将讨论DBSCAN性能与数据集可索引性的关系，并讨论选择适当的DBSCAN参数的一些启发式方法。本文将提出一些不良参数的指标，以帮助指导该算法未来的用户选择参数，如获得有意义的结果和良好的性能。在新的实验中，我们表明，如果DBSCAN参数选择得当，新的SIGMOD 2015方法似乎不会提供实际好处，因此它们主要具有理论意义。综上所述，具有有效指标和合理参数选择的原始DBSCAN算法与Gan和Tao提出的方法相比具有竞争力。
At SIGMOD 2015, an article was presented with the title "DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation" that won the conference's best paper award. In this technical correspondence, we want to point out some inaccuracies in the way DBSCAN was represented, and why the criticism should have been directed at the assumption about the performance of spatial index structures such as R-trees and not at an algorithm that can use such indexes. We will also discuss the relationship of DBSCAN performance and the indexability of the dataset, and discuss some heuristics for choosing appropriate DBSCAN parameters. Some indicators of bad parameters will be proposed to help guide future users of this algorithm in choosing parameters such as to obtain both meaningful results and good performance. In new experiments, we show that the new SIGMOD 2015 methods do not appear to offer practical benefits if the DBSCAN parameters are well chosen and thus they are primarily of theoretical interest. In conclusion, the original DBSCAN algorithm with effective indexes and reasonably chosen parameter values performs competitively compared to the method proposed by Gan and Tao.