提出在线版局部深度算法，高效处理半监督学习中的新数据点。
Online Partitioned Local Depth for semi-supervised applications
- 基于预构建的凝聚网络，实现新数据点的快速扩展
- 构建后每点扩展仅需O(n²)时间，显著提升效率
- 适合医疗数据等场景下的在线异常检测与分类
我们提出一种适用于在线应用（如半监督预测）的分块局部深度（PaLD）算法扩展。尽管PaLD以无参数聚类著称，其鲁棒性依赖于三元组数据点，导致精确分析计算成本高。现有研究致力于提升底层离散算法的可扩展性并拓展应用范围。本文提出的在线PaLD算法，可在预先从参考数据集构建凝聚网络后，以O(n³)步骤完成数据结构构建，随后在O(n²)时间内将该网络扩展至新数据点。该方法补充了基于近似与并行化的加速策略。实际应用中，它使更大规模数据集能进行精确分析，且实现简单。我们以医疗数据集为例，展示了在线PaLD在在线异常检测与半监督分类中的潜力。
原文摘要 · Abstract (English)
We introduce an extension of the partitioned local depth (PaLD) algorithm that is adapted to online applications such as semi-supervised prediction. PaLD is best known for unsupervised, parameter-free clustering, but its robustness is based on triples of data points, making exact analysis computationally expensive. Research is ongoing to improve the scalability of the underlying discrete algorithm and expand the breath of PaLD's applications. The new algorithm we present, online PaLD, is well-suited to situations where it is possible to pre-compute a cohesion network from a reference dataset. After $O(n^3)$ steps to construct a queryable data structure, online PaLD can extend the cohesion network to a new data point in $O(n^2)$ time. Our approach complements previous speed up approaches based on approximation and parallelism. In practical terms, online PaLD makes larger datasets accessible to exact analysis with a relatively simple implementation. We present applications to online anomaly detection and semi-supervised classification for health-care datasets as initial illustrations of online PaLD's potential to expand applications of the PaLD framework.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。