暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / SIGMOD 2022| DenForest：在滑动窗口上实现增量密度聚类的快速删除

SIGMOD 2022| DenForest：在滑动窗口上实现增量密度聚类的快速删除

时空实验室 2023-09-11
87
应用程序产生时变和流式数据，对基于密度的聚类提出了实时服务的需求。为了更有效和快速地实现集群的更新，许多增量密度聚类算法应运而生，但仍然存在缓慢删除问题，导致性能严重下降。本次为大家带来国际顶级会议SIGMOD 2022上的论文《DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows》。

一．背景
基于密度的聚类被用于热点或分割区域的检测、地理社会网络分析等。为了实时地服务于这些应用程序，对时变或流式数据进行分析，我们希望通过只捕获最近的数据来增量地更新集群。举个例子来说，交通监控系统需要定期提醒当地公众拥堵的地区。拥堵情况是根据近10分钟车辆GPS数据确定的，每30秒更新一次。那么，基于密度的聚类方法需要逐步更新拥塞区域，而不是每30秒从头重新计算一次。如图1所示，增量集群通过插入新的数据点（ΔDin）以及删除过时的数据点（ΔDout）来有效地更新拥挤区域。
图1 在滑动窗口上的基于密度的聚类实例
以往的增量密度聚类算法通常将聚类表示为图，当删除一个点时，需要一个昂贵的图遍历来检查集群是否仍然连接，导致性能严重下降。也有研究者提出DISC方法，通过最小化批处理操作的计算负担，减轻了性能下降。但它时间复杂度仍然很高，并不能从根本上解决问题。ExtraN方法在未来窗口中预计算集群的缓慢删除问题，但消耗的内存过多。ρ2-Approx方法实现了删除的多对数时间复杂度，但该方法需要大量的近似计数和最近邻查询，以至于实际性能更差。
文章提出了一种新的基于增量密度的聚类算法DenForest，它将集群保持为一组生成树而不是图，删除一个点的时间复杂度为O(logN)。考虑到删除时被分割的生成树并不总是意味着底层图也被分割了。因此，文章还设计了名为DenTree的新数据结构，它可以准确地判断底层图是否正在被分割。文章进行了大量实验，DenForest的性能显著优于最先进的基于密度的聚类算法，并达到了可与DBSCAN相媲美的聚类质量。
二．前置知识
2.1 基于密度的聚类（DBSCAN）
（1）两个参数
  • 距离阈值ε：用于确定邻居点。点p的邻居点集合为所有与p距离小于ε的点，即Nε(p)={q∈D : d(p,q)≤ε}，其中，D表示数据集。
  • 密度阈值MinPts：用于确定核心点。若p的邻居点数量≥MinPts，则p为核心点。
（2）三种对象类型
  • 核心点
  • 边界点：不满足核心点的条件，但它是核心点的邻居。
  • 噪声点：除以上两种点之外的点。
（3）三种关系
  • 直接密度可达：满足| Nε(q) |≥MinPts且p∈Nε(q) ，称p可从q直接密度可达。
  • 密度可达：存在一条点链p1,...,pn∈D，p1=q,pn=p，pi+1可从pi直接密度可达，则称p可从q密度可达。
  • 密度相连：p，q都能从点o密度可达，则称p，q是密度连接的。
2.2 滑动窗口模型
滑动窗口模型被广泛用于捕获流数据的最新状态。模型具有两个参数：
（1）窗口W：大小为|W|，受窗口中的点数（基于计数的窗口）或窗口持续时间（基于时间的窗口）的限制。
（2）步幅S：由在窗口滑动时更新聚类结果的时间间隔定义。大小为|S|。例如，假设滑动窗口是基于时间的，其步幅被设置为30秒。每当窗口滑动30秒时，可能有一组新的点在此期间被添加到窗口中，并被一起处理以更新集群。
2.3 滑动窗口上的密度聚类
文章的目标是在流数据中寻找集群，因此需要在窗口滑动时，捕获最近的数据点更新基于密度的集群。如图2所示，有六种类型的集群演化可能发生：出现、扩张、合并、消失、收缩和分裂。当新的点插入时，一些现有的点可能会成为核心点。而新核心点可能会导致其周围连接点的扩展，甚至产生集群的合并。相反，删除旧的点，一些现有的核心点可能变成非核点。由于核心点的消失，现有的集群可能会收缩、消失或者分裂为多个集群。
图2集群更新的六种类型
三．DenForest
图3 DenForest基本框架
3.1 缓慢删除问题
缓慢删除的原因在于，一个集群可能会被一个消失的核心点所分割，因此需要遍历剩余的核心点来检查彼此之间的可达性。而遍历需要大量的范围搜索使得聚类性能下降。问题本质在于一个消失的核心点，它的过期时间是不可预测性的。而DenForest可以做到在核心点p进入滑动窗口后，就确定它什么时候会成为非核心点。
3.2 相关定义
论文定义了怀旧核心点，它与DBSCAN中的核心点相似，但增加了与时间相关的条件。由此，对边界点和噪声点的定义也随之改变，具体如下：
（1）怀旧核心点：也是在密集区域发现的点，但会过期并成为非核心点。具体定义如下，当点p满足且时，就称p为怀旧核心点。其中，Nε代表p的邻居点，T代表时间戳。简单来说，就是若满足p的邻居点且比p先进入窗口的点数量大于阈值τ，p就是怀旧核心点。
（2）边界点：不是一个怀旧核心点，但在怀旧核心点ε范围内。
（3）噪声点：除以上两种点之外的点。
3.3 DenTree数据结构
为了有效地处理点删除，文章提出了DenTree树状结构，由DenGraph的最大生成树（简称MST）和与之相关联的边界点组成。
（1）DenGraph：无向边加权图。每个顶点对应窗口的一个怀旧核心点，每条边对应一对顶点的距离在ε范围内，每个权重设置为两个顶点中较小的时间戳。即
。
（2）最大生成树：如图4是生成MST的实例。一对怀旧核心点之间可能存在多条路径，分割一条路径并不总是会使它们断开连接。但如果被分割的路径是MST上的一条，那就肯定不再连接了。因此MST的这个属性是解决缓慢删除问题的关键。也就是说，确定集群是否会被某即将消失的怀旧核心点所分割，只需检查它是否与MST中的两个或多个的怀旧核心点相邻。
图4 DenTree例子
3.4 插入
插入操作指的是在添加新数据点到窗口时更新集群。包含以下四个步骤：
（1）点分类：根据怀旧核心点的定义判断点的类型。
（2）确定核心到期时间Tc：怀旧核心点的核心过期时间由它的ε邻居计算得到，其中涉及对它们的时间戳顺序进行排序。
（3）添加连接到MST：MST通过添加怀旧核心点p和与其相邻的新边来更新。若p不与任何MST相邻，就会有新集群出现；若p与某个MST相邻，该集群得到扩展；若p与多个MST相邻，将产生集群合并。当MST中出现环时，通过Connect函数将权重最小的从环中除去，Connect依赖链接切割树的原理来进行切割去环，具体实现感兴趣的读者可以细读论文4.1.1节。
（4）更新边界点：若p是怀旧核心点，ε距离内的现有边界点可能会重新连接到p。若p不是怀旧核心点，也可能存在一个怀旧核心点，使p成为一个边界点。
图5 算法：插入一个点并更新集群
3.5 删除
删除操作指的是从滑动窗口中删除现有数据点时更新集群。包含以下两个步骤：
（1）寻找过期怀旧点：一个点p从窗口移除时，某些怀旧核心点可能变为非核心点，而这些点可以在不执行任何范围搜索的情况下找到。原因在于，怀旧核心点的核心到期时间在插入时确定并保持不变，因此当前窗口中的所有怀旧核心点都可以以核心到期时间为键，在补充的数据结构（如哈希图）中进行索引。
（2）从MST切断：检查所有过期的怀旧核心点以确定是否有任何MST要被分割。对于每一个即将过期的怀旧核心点，根据其所邻接的怀旧核心点个数|L|来判断集群的三种演化。若|L|=0，集群消失；若|L|=1，集群收缩；若|L|≥2，集群分裂。
图6 算法：插入一个点并更新集群
四．实验
4.1实验设置
（1）数据集：四个真实世界的数据集如表1所示。
表1 数据集维度及阈值和窗口大小
（2）对比方法：IncDBSCAN, Extra-N，DISC，ρ-双近似DBSCAN
（3）衡量标准：更新延迟时间，衡量聚类质量的指标（ARI调整兰德系数、AMI调整互信息和NMI标准化互信息）
4.2 基线评估
基线性能评估会测试每种聚类方法在滑动窗口模型下的更新延迟，更新延迟分为插入和删除延迟，每个度量都是5次运行的平均值。如图7所示，在所有数据集上，DenForest及其非优化版本（DenForest-NO）都优于其他所有方法。
图7更新延迟
4.3 不同大小的窗口/步幅
窗口和步幅的大小可以根据应用程序的不同而有所不同。在不同的窗口大小（图8）和不同的步幅大小（图9）下测量了更新延迟，DenForest和DenForest-NO都显著优于其他聚类方法。
图8 窗口大小不同
图9 步幅大小不同
4.4 密度和距离阈值的影响
使用DTG数据集来测量密度和距离阈值对性能的影响。图10显示了具有不同距离阈值ε下的插入和删除延迟，较大的ε值通常需要更多的时间来进行范围搜索。而DenForest和DenForest-NO不需要任何范围搜索来进行删除。因此，除DenForest和DenForest-NO删除外，其它方法的延迟都随着ε的增加而增加。
图10距离阈值不同
密度阈值几乎没有影响性能，除了Appro-High和Appro-Low，如图11所示。原因在于随着密度阈值的增加，Appro方法需要更多的时间来确定一个点是否为核心点。
图11密度阈值不同
4.5 在滑动窗口上的集群质量
如图12，DenForest对所有数据集都达到了接近1的聚类质量测量值，并在窗口滑动时能够保持其质量。平均质量测量值分别为0.96（ARI）、0.91（AMI）和0.93（NMI）。
图12在滑动窗口上的集群质量评估
五．总结
论文提出了一种新的基于增量密度的聚类算法DenForest，以解决以往最先进的聚类方法中固有的缓慢删除问题。它提出了怀旧核心点的概念，通过将集群作为一组DenTrees树状结构而不是图，实现了更高的性能。通过大量数据进行广泛的比较评估，证明了DenForest的有效性和性能的优越性。DenForest有望通过以较低的计算成本有效地聚类时变数据，来支持流媒体环境中的许多数据分析任务。
-End-
本文作者
李文慧
重庆大学计算机科学与技术（卓越）专业在读大四学生，重庆大学START团队成员。主要研究方向：时空数据挖掘


重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有2~3名研究生名额，欢迎计算机、GIS等相关专业的学生报考！

聚类滑动窗口阈值分割集群技术增量模型
文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论