DBSCAN

引入

链接： https://youtu.be/RDZUdRSDOok?si=iBr5hZVCeWpNDbPy

DB扫描聚类的效果如同人工分类一样直观统计探索大家好，我是乔希·斯塔默，欢迎来到《统计探索》今天我们将深入解析DB扫描聚类算法保证让您彻底理解其中的原理

假设我们收集了人群的体重与身高数据这些数据来自不同个体我们将这些数据绘制在二维散点图上其中X轴（第一维度）代表体重Y轴（第二维度）则对应身高

通过肉眼观察，我们可以识别出两个不同的聚类它们呈现为两个相对密集的人群分布区域而那些远离主要群体的离散点则明显属于异常值由此可见，对这种数据进行人工聚类相当直观

然而由于这些聚类存在嵌套关系具体来说绿色聚类完全环绕着蓝色聚类这种情况下，传统的聚类方法比如k均值聚类法可能难以准确识别这两个聚类由于嵌套结构的存在简单聚类方法可能产生如此异常结果：这些本应属于绿色聚类的数据点却被错误地划分到蓝色聚类中因此我们需要能够处理嵌套聚类的算法

请注意，这个二维图表仅使用了体重和身高数据若要加入年龄维度，就需要引入第三根坐标轴这样我们的图表就变成了三维空间在二维屏幕上绘制三维图表虽然不够直观，但技术上可以实现然而若需纳入四个及以上特征，就需要绘制四维或更高维度的图表——这显然无法实现既然无法通过肉眼观察高维空间中的聚类分布幸而存在能够识别高维嵌套聚类的算法体系其中dbScan算法正是我们今天要探讨的解决方案

原理

现在让我们回到初始的二维图表，观察dbScan如何模拟人类的视觉识别机制请记住，人类通过数据点分布密度来识别聚类聚类通常形成于高密度区域，而离散点则分布于低密度区域接下来我们将看到dbScan如何运用密度原理识别这两个聚类

注意看！从原始未聚类数据出发，首先需要计算每个点邻近区域的数据点数量以这个红点为例，我们以其为中心绘制橙色圆圈可见橙色圆圈至少与八个其他点存在重叠区域说明该红点与八个相邻点距离相近注意：橙色圆圈的半径由用户自定义，使用dbScan时可能需要调整此参数

当前这个红点与五个相邻点距离相近，因为橙色圆圈至少与五个点存在重叠这个红点邻近六个点，而那个红点则与七个点相邻近这个红点仅邻近两个点，而那个红点则没有任何邻近点——因为橙色圆圈未与其他任何点重叠同理，我们需要计算所有剩余数据点的邻近点数量

在本示例中，我们将核心点定义为至少邻近四个其他数据点的点注意：核心点的最小邻近点数同样由用户自定义，使用dbScan时也需要调整此参数

这四个点属于核心点，因为它们的橙色圆圈至少与四个其他点重叠太棒了！但这些点都不是核心点，因为它们的橙色圆圈未能与四个或更多点重叠唉...最终我们可以将这些红点都判定为核心点，因为它们都邻近至少四个其他点，其余点则为非核心点

现在随机选取一个核心点划入第一个聚类随后，与首个聚类相邻（即橙色圆圈存在重叠）的核心点都将加入该聚类随着聚类不断扩展，邻近的核心点会持续加入并推动聚类边界延伸这里我们看到两个核心点和一个非核心点都与正在扩展的首个聚类相邻现阶段我们仅将核心点纳入首个聚类虽然最终会吸收这个非核心点，但当前阶段只添加核心点最终，所有与扩展中首个聚类相邻的核心点都会被纳入，并进一步推动聚类扩展砰！

注意：此时首个聚类中的所有点都是核心点由于无法继续添加核心点，现在将所有与核心点相邻的非核心点纳入首个聚类例如这个非核心点，它与首个聚类中的某个核心点相邻因此将其纳入首个聚类但由于它不是核心点，不能通过它来扩展聚类边界这意味着另一个非核心点——虽然与刚加入聚类的非核心点相邻——不会被纳入，因为它不与任何核心点相邻因此与核心点不同，非核心点只能加入聚类，无法扩展聚类现在将所有与首个聚类中核心点相邻的非核心点纳入至此首个聚类构建完成双响炮！

总结首个聚类的形成过程：随机选取核心点作为种子相邻核心点不断加入并扩展聚类范围非核心点仅能加入已形成的聚类砰！

由于这些核心点与首个聚类不相邻它们相互邻近形成第二个新聚类与第二聚类相邻的非核心点也被纳入其中最终，当所有核心点都已归属聚类便停止创建新聚类

剩余的非核心点若与任何聚类中的核心点都不相邻则不被纳入任何聚类，称为离群点以上就是dbScan算法的工作原理三连击！

注意：如我们所见，聚类是按顺序创建的这意味着如果存在一个与两个聚类都相邻的非核心点当构建首个聚类时...哔哔哔哔哔哔哔哔哔哔哔...该非核心点会因为与核心点相邻而被纳入首个聚类同时所有其他相邻的非核心点也会被纳入一旦该点归属首个聚类，便不再具备加入其他聚类的资格小成就达成

Now it's time for some shameless self-promotion.If you want to review statistics and machine learning offline, check out the StatQuest study guides at statquest.org.There's something for everyone.Hooray! We've made it to the end of another exciting StatQuest.If you like this StatQuest and want to see more, please subscribe.And if you want to support StatQuest, consider contributing to my Patreon campaign, becoming a channel member,buying one or two of my original songs, or a t-shirt, or a hoodie, or just donate.The links are in the description below.Alright, until next time, quest on!