动态更新数据时，快速计算相似性并支持高效谱聚类。
Dynamic Similarity Graph Construction with Kernel Density Estimation
- 用核密度估计构建可动态维护的相似性图
- 支持数据增删下的实时聚类计算
- 适合需要持续更新聚类结果的应用场景
在核密度估计（KDE）问题中，给定一组数据点 $X$、核函数 $k: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$ 及查询点 $\mathbf{q} \in \mathbb{R}^d$，目标是快速估算 $\sum_{\mathbf{x} \in X} k(\mathbf{q}, \mathbf{x})$。本文研究动态设置下的KDE问题，提出一种数据结构，可在数据点随时间不断加入 $X$ 时高效维护多个查询点的估计值。基于此，设计了一个动态数据结构，用于维护 $X$ 上全连接相似性图的稀疏近似，并开发了一种快速的动态谱聚类算法。我们在合成数据和真实世界数据集上评估了算法的有效性。
原文摘要 · Abstract (English)
In the kernel density estimation (KDE) problem, we are given a set $X$ of data points in $\mathbb{R}^d$, a kernel function $k: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$, and a query point $\mathbf{q} \in \mathbb{R}^d$, and the objective is to quickly output an estimate of $\sum_{\mathbf{x} \in X} k(\mathbf{q}, \mathbf{x})$. In this paper, we consider $\textsf{KDE}$ in the dynamic setting, and introduce a data structure that efficiently maintains the estimates for a set of query points as data points are added to $X$ over time. Based on this, we design a dynamic data structure that maintains a sparse approximation of the fully connected similarity graph on $X$, and develop a fast dynamic spectral clustering algorithm. We further evaluate the effectiveness of our algorithms on both synthetic and real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。