创手机网站,wordpress 5.0文章编辑教程,全国最大的外发加工网,在哪一个网站上做劳务合同备案在进行组会汇报的时候#xff0c;为了引出本研究动机#xff08;论文尚未发表#xff0c;暂不介绍#xff09;#xff0c;需要对DBSCAN、OPTICS、和HDBSCAN算法等进行详细介绍。在查询相关资料的时候#xff0c;发现网络上对于DBSCAN算法的介绍非常多与细致#xff0c;但… 在进行组会汇报的时候为了引出本研究动机论文尚未发表暂不介绍需要对DBSCAN、OPTICS、和HDBSCAN算法等进行详细介绍。在查询相关资料的时候发现网络上对于DBSCAN算法的介绍非常多与细致但是对于OPTICS或者HDBCCAN算法的介绍要么是直接照抄一个在线文档的算法介绍要么就是未能完整的讲出该算法的原理。为了能够给大家提供一个都能看懂的HDBSCAN算法介绍于是有了该篇文章。 下面进入关于HDBSCAN算法的正文内容主要包括HDBSCAN算法提出的动机、HDBSCAN算法的原理、HDBSCAN算法的优缺点、HDBSCAN算法的优缺点、HDBSCAN算法的实例介绍等。 文章目录 从DBSCAN到HDBSCANDBSCANOPTICSOPTICS 算法的优化与原理 HDBSCANHDBSCAN 的引入 HDBSCAN 算法的原理与具体步骤1. 样本点互达距离计算距离空间变换压缩层次聚类树提取稳定簇打标签 HDBSCAN算法的优势HDBSCAN算法的不足 总结Reference 从DBSCAN到HDBSCAN
DBSCAN
为了理解HDBSCAN首先需要理解DBSCAN算法的原理。
DBSCANDensity-based Spatial Clustering of Applications with Noise是一种基于密度扩展的聚类算法。顾名思义从该算法名称中可以发现该算法的核心思想在于样本密度的定义以及如何基于样本的密度扩展类簇。
DBSCAN算法认为类簇是由一系列被稀疏区域分隔开来的密集区域组成的。
该算法通过两个关键参数Eps邻域半径和MinPts邻域内包含的最小样本数量定义样本的密度。 如果一个样本点在用户指定的邻域半径中包含至少MinPts个样本那么该样本被定义为一个**核心对象**。核心样本邻域内的其他样本被称为直接可达对象 。如何直接可达对象满足Eps和MinPts参数约束其也是一个核心对象。核心对象可以用来吸引其他对象加入同一个簇。 对于位于核心对象邻域内、但是不满足核心对象定义的样本被称为边界对象。 既不是核心对象也不是边界对象的样本则被称为噪声点。通过该定义可以发现DBSCAN算法能够识别噪声点的原因。
DBSCAN算法的原理就是通过寻找核心对象并不断扩展加入核心对象邻域内的样本判断是否为核心对象然后继续扩展从而形成一个簇。不在任何核心对象邻域内的样本且无法形成核心对象的样本则被视为异常值不被分配到任何簇。
DBSCAN算法能够发现任意形状和大小的簇并且能够识别噪声对噪声具有很强的鲁棒性。但是同时由于这两个参数是全局的导致DBSCAN算法无法发现不同密度尤其是密度差异较大、并且与密集簇邻近分布的簇。
此外这两个参数的设置依赖于对数据集的先验认知也可以使用网格搜索等方法进行参数优化。
OPTICS
为了克服DBSCAN算法参数设置的局限性学者Ankerst等提出了OPTICSOrdering Points to Identify the Clustering Structure算法。OPTICS 是 DBSCAN 的一种改进版本它不再需要通过固定的全局参数Eps 和 MinPts来定义密度而是通过一种排序方式来揭示数据集中的聚类结构从而解决DBSCAN算法参数设置的困难。
OPTICS 算法的优化与原理
OPTICS 的核心思想是通过记录每个点的 核心距离Core Distance和 可达距离Reachability Distance以一种可视化的方式展示数据的聚类结构。具体来说 核心距离 (Core Distance): 对于一个点如果其邻域内有足够的点至少 MinPts 个点则核心距离定义为该点到其邻域内第 MinPts 个最近点的距离点到邻域内点的最大距离。如果一个点的邻域内不足 MinPts 个点则核心距离未定义Undefined表示为无穷大。 可达距离 (Reachability Distance): 对于两个点 A 和 B点 B 相对于点 A 的可达距离是点 A 的核心距离和点 A 到点 B 的欧氏距离之间的较大值。 直观上可达距离表示一个点从另一个点“被密度连接”的难易程度量化了两个样本点之间被密集区域所连接的最大距离。可达距离越小说明两个点之间连线经过的稀疏区域越小它们之间的密集程度越高。 数据排序:
OPTICS 通过一个类似于 DBSCAN 的过程对数据进行排序优先处理核心距离较小的点即更密集区域的点将点按照密度从高到低进行访问。每个点在被访问时会更新其邻域中未访问点的可达距离。
密度聚类结构:
OPTICS 不直接输出聚类结果而是生成一个可视化的“可达距离图”Reachability Plot。通过观察图中呈现的“山谷”低可达距离的区域可以识别不同密度的簇。 OPTICS算法的优点包括不需要提前固定Eps参数可以通过核心距离和可达距离动态调整密度阈值能够发现不同密度的簇。其次与 DBSCAN 类似OPTICS 也能够识别噪声点即在可达距离图中位于高可达距离的点。
然而OPTICS算法也存在一定的局限性主要体现在**复杂度较高**需要维护可达距离和排序。其次簇提取困难OPTICS输出一个有序的点序列不显式给出聚类结果仍需要额外的步骤和方法从序列中提取真正的簇。参数敏感性仍然需要指定参数minPts其选择对最终聚类结果有很大影响尤其是在处理高维数据或密度分布不均匀的数据集时。可达距离的局限性不对称仅考虑了从一个点到另一个点的距离
HDBSCAN
HDBSCAN 的引入
为了进一步改进密度聚类算法的灵活性和效率学者们提出了 HDBSCANHierarchical Density-Based Spatial Clustering of Applications with Noise算法。HDBSCAN 是 DBSCAN 的一种层次化扩展结合了密度聚类和层次聚类的思想其核心在于通过一个密度分层树Density Hierarchy Tree来表征数据的聚类结构。
密度定义的改进: HDBSCAN使用相对密度的概念而不是固定的绝对密度阈值如DBSCAN的固定Eps参数。相对密度考虑了数据点与其核心距离(core distances)的比较,而不是单纯的邻域半径这使得算法能够自动适应不同区域的密度差异。通过计算互达距离Mutual Reachability Distance来定义点之间的密度连接关系而不是简单的欧式距离。互达距离更加稳健保持密集区域的数据点密度不变降低稀疏区域的数据点的密度能过更好处理不同密度的区域从而识别出不同密度的轨迹。互达距离其实是对OPTICS算法中可达距离的一种改进同时考虑两个样本点的局部点分布 密度层次化聚类: HDBSCAN 通过对密度逐步降低的过程进行跟踪生成一个密度分层树。在密度分层树中叶子节点代表高密度区域的簇而根节点表示整个数据集。 自动化簇提取: 与 OPTICS 需要手动观察可达距离图不同HDBSCAN 提供了一个自动化的簇提取方法通过定义一个稳定性指标Stability来评估每个簇的持久性并自动选择最稳定的簇作为最终聚类结果。
HDBSCAN 算法的原理与具体步骤 关于HDBSCAN算法的原理与步骤目前网络上最出名的两个博客分别是https://www.biaodianfu.com/hdbscan.html和https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.html前者其实是后者的中文版。网络上的其他博客大多也会这两个内容的搬运本文在撰写的过程中也难免会借鉴其中的内容但是会加上自己对该算法的思考以及更加详细的原理讲解确保提供一个大家都能看到的HDBSCAN原理介绍博客。 1. 样本点互达距离计算距离空间变换
在开源的各种聚类算法的代码库中我们可以发现有一个参数metric该参数的可取值包括Euclidean, pre-computed 等。其中pre-computed表示提前计算好样本数据之间的距离直接输入一个 N ∗ N N*N N∗N的距离矩阵 (其中 N N N是样本数据的数量)。该距离可以是欧式距离网络距离曼哈顿距离等。
在HDBSCAN算法中需要将输入的预先计算好的原始距离矩阵如欧式距离进行一个距离空间转换原始距离空间转换为互达距离(mutual reachability distance)空间。距离空间转换旨在更好地识别数据中的密集区域和稀疏区域。
距离空间转换需要解决以下两个问题
密度差异问题在同一数据集中可能存在密度相差很大的聚类。简单使用原始距离可能会导致密度较低的聚类被忽略。距离空间转换可以放大稀疏区域使得不同密度的聚类能够被更好地识别。噪声数据识别问题噪声数据通常分布较为稀疏,与聚类之间的距离较远。使用原始距离可能难以区分噪声与真实聚类。距离空间转换通过压缩密集区域从而使噪声点与聚类之间的距离差异更加明显有助于识别噪声数据。
HDBSCAN算法采用了一种称为互达距离(mutual reachability distance)的距离空间转换方式。具体来说对于任意两个样本点 p p p和 q q q首先计算他们各自的核心距离反应其局部密度
计算点 p p p到其所有 k k k近邻点的核心距离,取最大值作为 p p p的核心距离 c o r e k ( p ) core_k(p) corek(p)计算点 q q q到其所有 k k k近邻点的核心距离,取最大值作为 q q q的核心距离 c o r e k ( q ) core_k(q) corek(q)
然后取他们的核心距离和原始距离之间的最大值作为互达距离。可以看出互达距离“放大了稀疏区域的距离同时压缩了密集区域内的距离。这种转换能更好地反映数据本身的密度分布特征有利于后续的聚类分析。 d m r e a c h − k ( p , q ) m a x { c o r e k ( p ) , c o r e k ( q ) , d ( p , q ) } d_{mreach-k}(p,q)max\{{core_k(p),core_k(q),d(p,q)}\} dmreach−k(p,q)max{corek(p),corek(q),d(p,q)} ### 2. 构建最小生成树Minimum Spanning TreeMST
在新的距离空间中基于数据点之间的互达距离构建一个最小生成MST。每个节点代表一个数据点边的权重为两个节点之间的互达距离。
数据点之间的互达距离矩阵首先会形成一个加权的完全连通图图上任意两个节点都是连通的。为了有效地表示数据点的密度连接关系并降低计算复杂度需要从完全连通图中提取一个最小生成树MST。
最小生成树提供了一种划分数据的自然方式。通过移除MST中权重最大的边整个图就被分割成了两个连通分量对应着两个密集的数据簇。重复这个过程移除下一个最大权重的边整个图就被进一步分割成更多的连通分量。这个连续的裁剪过程会产生一个分层的簇结构从而揭示出数据的层次聚类关系。
在具体实现中可以选择Prime算法构建生成树。Prime算法的原理为 选择一个任意节点作为起始节点并将其添加到MST中。 创建一个优先队列Q用于存储与MST中节点相邻的边并按照边的权重互达距离升序排列。 将起始节点的所有邻边添加到Q中。 重复以下步骤直到MST中包含 n-1 条边 从Q中取出权重最小的边。 如果该边连接的另一个节点不在MST中则将该边和节点添加到MST中并将该节点的邻边添加到Q中。
生成的MST包含了所有数据点并且边的权重总和最小。这棵树保留了数据点之间最重要的密度连接信息并为后续的层次聚类提供了基础。
注意MST可能不是唯一的如果有多个权重相同的最小生成树算法会返回其中一个。
下图给出了一个简单的构建的最小生成树的示例[在这里插入图片描述](https://i- ### 构建层次聚类树
基于最小生成树构建层次聚类树Hierarchy Tree是HDBSCAN算法的核心步骤。最小生成树的每个节点表示一个数据点边的权重表示数据点之间的互达距离。为了生成层次聚类树可以按照如下步骤 初始化将 MST 中的每条边按照其权重即两点之间的可达距离排序。 构建层次结构初始化一个森林每个数据点都是一个独立的簇。然后便利排序后的MST从权重最小的边开始逐步添加边到聚类树中。每当添加一条边时,都会有两种可能情况: 该边连接的两个点属于两个不同的簇则将这两个簇合并为一个新簇该边连接的两个点在同一个簇内则不进行合并操作。 重复这个过程直到遍历完所有的边得到一个包含多层次结构的层次树结构。 如下的GIF图是基于上述示例的最小生成树构建层次聚类树的动态过程。
根据如图所示的层次聚类树为了得到不同的簇我们可以直接画一条水平线将层次树切分为不同的簇其实就是根据一个单一的互达距离的阈值将层次树分为不同的子树每个子树表示一个簇如下图所示。 但是这样根据一个全局、单一的互达距离阈值存在以下问题
无法处理不同密度的簇。由于使用了全局阈值,在密集区域可能会将不同的簇合并在一起,而在稀疏区域可能会将本应属于同一簇的点分割开来。噪声点可能会被错误地划分到某个簇中。全局阈值无法很好地区分真正的簇和噪声点。无法识别层次结构中最稳定的簇 - 某些簇可能在较宽的距离范围内都保持稳定,而另一些簇可能仅在特定距离下才显著。单一阈值无法捕获这种差异。
因此我们需要一个更加稳健的方法从构建的聚类层次结构中提取簇。
压缩层次聚类树
在层次聚类树构建完成后需要进行树的压缩即将一颗大的层次树压缩为多个小的子簇结构。
在压缩树的过程中HDBSCAN定义了一个参数minimum cluster size用于控制层次聚类树的拆分这是一个自顶向下的过程。具体来说:
① 从层次树的根节点开始,将整个数据集视为一个大簇。② 对于当前簇如果其包含的数据点数量小于minimum cluster size,则将其标记为噪声簇不予考虑。③ 如果当前簇的大小大于或等于minimum cluster size则进一步检查它的子节点(子簇): 如果所有子簇的大小都小于minimum cluster size,则将当前簇标记为一个稳定簇保留下来。如果存在子簇的大小大于或等于minimum cluster size则对这些大的子簇递归执行步骤②和③继续向下拆分。 ④ 重复步骤②和③直到没有可拆分的大簇为止。最终层次树被拆分成多个互不相交的子树每个子树的根节点都minimum cluster size的约束。
通过这种自顶向下的拆分策略HDBSCAN逐步将原始的整体层次树压缩为规模较小、互不重叠的子树结构。每个子树代表一个相对稳定、大小合理的簇。同时噪声簇和过小的簇被剔除。
通过这种方式,HDBSCAN能够自动确定合适的簇数量而不需要人为指定簇数或其他聚类参数。生成的簇的形状、大小和密度也可以是任意的。
该压缩过程的关键是minimum cluster size参数它控制着簇被切分或保留的阈值。较大的值会导致更大规模、更扁平的簇较小的值会产生更多层次细节。因此可以根据具体应用场景调整该参数来获得理想的聚类粒度。
提取稳定簇打标签
虽然通过上述压缩树的方式我们将一颗大的层次树分解为多个小的子簇每个子簇满足minimum cluster size约束但是这样会忽略簇的稳定性与生命周期因为我们希望所提取的簇不仅能够稳定存在而且具有更长的生命周期能在较大密度范围内保持簇的稳定性。为了达到这目标HDBSCAN引入了对簇稳定性与生命周期的考量。
具体来说HDBSCAN 引入两个重要概念簇的稳定性和用于度量簇稳定性的指标 λ {λ} λ。 λ {λ} λ被定义为数据点之间互达距离的倒数即 λ 1 / d i s t a n c e λ1/distance λ1/distance。基于 λ {λ} λHDBSCAN通过引入 λ b i r t h {λ_{birth}} λbirth和 λ d e a t h {λ_{death}} λdeath和 λ p {λ_p} λp 对簇的稳定性和生命周期进行了量化其中 λ b i r t h {λ_{birth}} λbirth 指使得当前簇作为独立簇存在的最大 λ {λ} λ值。 λ d e a t h {λ_{death}} λdeath 指使当前簇不再作为一个独立簇簇的消失、开始分裂为更小子簇的λ值即当前簇失去独立性的密度阈值。这个值表示在该密度水平下簇不再作为一个独立的实体存在而是被分解为更小的子簇。 λ p {λ_p} λp 则是指簇中数据点 p p p 脱离簇’时的 λ {λ} λ值。对于簇内的每个点 p p p其 λ λ λ 值介于 λ b i r t h {λ_{birth}} λbirth和 λ d e a t h {λ_{death}} λdeath λ p {λ_p} λp实际上反映了点 p p p到所在簇的最小“边缘”距离。如果 p p p接近 λ b i r t h {λ_{birth}} λbirth说明点 p p p 处于簇的内部离群倾向较小如果 λ p {λ_p} λp接近 λ d e a t h {λ_{death}} λdeath说明点 p p p 处于簇的边缘离群倾向较大如果 λ p {λ_p} λp大于 λ d e a t h {λ_{death}} λdeath说明点 p p p 已经不再属于该簇。 λ p {λ_p} λp 值可以作为评估点 p p p 相对于簇的内外倾向的一个度量标准。HDBSCAN利用了这一度量在提取稳定簇时保留 λ p {λ_p} λp值较小的内部点剔除 λ p {λ_p} λp值较大的边缘噪音点从而获得相对稳定的簇结构。
因此簇的稳定性stability可以定义为 s c l u s t e r ∑ p ∈ c l u s t e r ( λ p − λ b i r t h ) s_{cluster}\sum_{p∈cluster} (λ_p-λ_{birth}) sclusterp∈cluster∑(λp−λbirth) 当所有点的 λ p {λ_p} λp都等于 λ d e a t h {λ_{death}} λdeath时 s c l u s t e r 0 s_{cluster}0 scluster0, 表示簇内所有点具有相同的密度水平。否则 s c l u s t e r s_{cluster} scluster小于0因为 λ b i r t h ≤ λ p {λ_{birth}}≤{λ_p} λbirth≤λp≤ λ d e a t h {λ_{death}} λdeath所以 s c l u s t e r ≤ 0 s_{cluster}≤0 scluster≤0。
压缩簇是自顶向下分裂的过程提取簇则是自底向上合并簇和过程。
具体提取的过程如下
① 自底向上遍历压缩树
② 对每个节点
计算该节点的稳定性 s c l u s t e r s_{cluster} scluster;计算其直接子节点的稳定性总和比较这两个值选择稳定性更大的方案 当遇到“子簇稳定性之和 父簇自身稳定性”的情况时 (分裂成两个簇更好) 将保留子簇们作为独立的平坦簇输出而放弃父簇不会作为一个独立的簇输出。 该簇的稳定性被设置为子簇稳定性之和该簇的所有子簇保留选定状态。 当遇到“父簇稳定性 子簇稳定性之和”的情况时 (两个子簇合并为一个簇更好) 将保留父簇作为平坦簇输出而放弃子簇们不会被单独输出。 该簇被选定该簇所有子簇的选定状态被取消
③ 遍历完成后根节点处的选定簇就是要输出的平坦簇集合
这样的策略可以确保输出的每个平坦簇不仅满足最小簇大小而且具有良好的生命周期和stability即规模合理、内部紧密且在较大密度范围内保持稳定稳定持久的簇结构。同时它避免了将稳定性较低的簇不适当地保留或合并。每个输出的平坦簇代表一个在全局上相对分离且内部相对紧凑的数据模式。
提取的簇满足最小尺寸要求簇具有足够的稳定性避免过度分裂或不当合并保留数据中最显著的层次结构
HDBSCAN算法的优势
HDBSCAN是一种基于密度的层次聚类算法能够自动确定簇的数量不需要提前指定簇的数量或者借助其他手段评估可能的簇数量。与DBSCAN一样能够发现任意形状的簇但是相比DBSCAN算法无法区分不同密度的簇尤其是密度差异较大的簇HDBSCAN算法能够处理密度分布差异较大的数据集。不同于 OPTICSHDBSCAN 提供了自动的簇提取机制无需手动调整参数或观察可达距离图。更少的参数依赖HDBSCAN 只需要一个主要参数 MinClusterSize最小簇大小易于设置。
HDBSCAN算法的不足
虽然HDBSCAN在处理不同形状和密度的簇方面表现出色但也存在一些局限性。
**参数敏感性: **HDBSCAN 的性能仍受 min_cluster_size 和 min_samples 参数的影响。min_cluster_size 控制最小簇的大小min_samples 影响单个点的密度估计。不合适的参数设置可能导致识别出过少或过多的簇或者产生不符合预期的簇结构。计算复杂度: HDBSCAN 需要构建层次聚类树并计算每个点的核心距离这在大型数据集上可能非常耗时。虽然有一些优化策略可以提高计算效率但在大规模数据场景下HDBSCAN 的计算成本仍然较高。
总结
DBSCAN、OPTICS 和 HDBSCAN 都是基于密度的聚类算法它们在处理复杂数据分布、发现任意形状簇和识别噪声点方面表现良好。DBSCAN 是密度聚类的基础算法OPTICS 改进了其对不同密度簇的适应性而 HDBSCAN 进一步结合了层次聚类的思想并提供了自动化的簇提取方法适用于更广泛的场景。
Reference
[1] Ester M, Kriegel H P, Sander J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//kdd. 1996, 96(34): 226-231.
[2] Campello R J G B, Moulavi D, Sander J. Density-based clustering based on hierarchical density estimates[C]//Pacific-Asia conference on knowledge discovery and data mining. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013: 160-172.
[3] Ankerst M, Breunig M M, Kriegel H P, et al. OPTICS: Ordering points to identify the clustering structure[J]. ACM Sigmod record, 1999, 28(2): 49-60.
[4] Schubert E, Sander J, Ester M, et al. DBSCAN revisited, revisited: why and how you should (still) use DBSCAN[J]. ACM Transactions on Database Systems (TODS), 2017, 42(3): 1-21.
[5] https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.html#condense-the-cluster-tree
[6] https://www.biaodianfu.com/hdbscan.html
