什么是DBSCAN？

DBSCAN代表基于密度的应用空间聚类算法(Density-Based Spatial Clustering of Applications with Noise)。它是一种基于密度的聚类算法。该算法将具有足够高密度的区域增长为簇，并在包含噪声的空间数据库中找到任意结构的簇。它将簇表示为密度连接点的最大组。

基于密度的聚类概念包括以下一些新的定义：

• 给定对象的半径为ε的邻域称为该对象的ε邻域。

• 如果对象的ε邻域包含至少最小数量MinPts的对象，则该对象被称为核心对象。

• 给定一组对象D，如果p在q的ε邻域内，且q是核心对象，则可以说对象p可由对象q直接密度可达。

• 在一组对象D中，如果存在对象链p₁,..., p_n，其中p₁ = q且p_n = p，并且p_i+1关于ε和MinPts可由p_i直接密度可达（1 ≤ i ≤ n），p_i ε D，则对象p关于ε和MinPts可由对象q密度可达。

• 在一组对象D中，如果存在对象o ε D，使得p和q都关于ε和MinPts可由o密度可达，则对象p与对象q关于ε和MinPts密度连接。

密度可达性是直接密度可达性的传递闭包，这种连接是不对称的。只有核心对象是相互密度可达的。密度连接是对称关系。

基于密度的簇是一组关于密度可达性是最大的密度连接的对象。每个不包含在任何簇中的对象都被视为噪声。

DBSCAN通过测试数据库中每个点的ε邻域来搜索簇。如果一个点p的ε邻域包含超过MinPts个点，则创建一个以p为核心对象的新簇。DBSCAN重复地从这些核心对象中收集直接密度可达的对象，这可能包含几个密度可达簇的合并。当没有新的点可以插入到任何簇中时，该过程结束。

如果使用空间索引，DBSCAN的计算复杂度为O(nlogn)，其中n是数据库对象的个数。否则，为O(n²)。通过适当设置用户指定的参数ε和MinPts，该算法能够有效地发现任意形状的簇。

Ginni

更新于：2022年2月16日

5K+ 浏览量

开启你的职业生涯

完成课程获得认证

开始学习