提出谱压缩方法，让DBSCAN高效处理超大规模高维数据
Enabling DBSCAN for Very Large-Scale High-Dimensional Spaces
- 用谱压缩保留数据关键结构，减少冗余与噪声
- 在高维大数据下仍保持准确聚类与异常检测能力
- 适合需要高效处理海量高维数据的场景
DBSCAN 是重要的非参数无监督分析工具，可基于密度分布聚类数据点并识别异常值。然而其时间复杂度为 $O(n^2 β)$，其中 $n$ 为数据点数，$β = O(D)$，$D$ 为数据维度。当 $n$ 与 $D$ 均较大时，计算变得不可行。本文提出一种基于谱数据压缩的 DBSCAN 方法，能高效处理大规模数据点数 ($n$) 和高维数据空间 ($D$)。通过压缩过程保留最关键的结构信息，有效去除冗余与噪声，显著提升 DBSCAN 的解质量，实现更准确可靠的分析结果。
原文摘要 · Abstract (English)
DBSCAN is one of the most important non-parametric unsupervised data analysis tools. By applying DBSCAN to a dataset, two key analytical results can be obtained: (1) clustering data points based on density distribution and (2) identifying outliers in the dataset. However, the time complexity of the DBSCAN algorithm is $O(n^2 β)$, where $n$ is the number of data points and $β= O(D)$, with $D$ representing the dimensionality of the data space. As a result, DBSCAN becomes computationally infeasible when both $n$ and $D$ are large. In this paper, we propose a DBSCAN method based on spectral data compression, capable of efficiently processing datasets with a large number of data points ($n$) and high dimensionality ($D$). By preserving only the most critical structural information during the compression process, our method effectively removes substantial redundancy and noise. Consequently, the solution quality of DBSCAN is significantly improved, enabling more accurate and reliable results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。