用袋装法降低局部维度估计方差,提升准确性。
On the Use of Bagging for Local Intrinsic Dimensionality Estimation
- 采用子袋装法保留近邻距离的局部分布,减少估计波动。
- 在多数超参数范围内,袋装法显著降低方差与均方误差。
- 适合对估计稳定性要求高的数据挖掘与机器学习任务。
局部内在维度(LID)理论已成为刻画数据流形内及跨流形局部复杂性的有力工具,支持多种数据挖掘与机器学习任务。准确的LID估计需从每个查询点的小邻域中采样,以避免非局部效应和流形混叠带来的偏差,但此类邻域内样本有限会导致估计方差过高。为此,我们提出一种基于子袋装(subbagging)的集成方法,旨在保留近邻距离的局部分布。主要挑战在于,每个子样本总样本量的均匀减少会提高找到固定数量k个最近邻所需的邻域半径。在LID估计的特定场景下,采样率与k-NN数量之间存在复杂交互关系,二者共同决定样本量、局部性及估计分辨率。我们通过理论与实验分析了采样率、k值及集成规模对性能的影响,支持根据应用需求合理选择超参数。结果表明,在广泛且特征明确的超参数区域内,袋装估计器相比非袋装基线能显著降低方差与均方误差,且偏差可控。此外,我们还提出了并评估了袋装与邻域平滑结合的不同策略,进一步显著提升估计性能。
原文摘要 · Abstract (English)
The theory of Local Intrinsic Dimensionality (LID) has become a valuable tool for characterizing local complexity within and across data manifolds, supporting a range of data mining and machine learning tasks. Accurate LID estimation requires samples drawn from small neighborhoods around each query to avoid biases from nonlocal effects and potential manifold mixing, yet limited data within such neighborhoods tends to cause high estimation variance. As a variance reduction strategy, we propose an ensemble approach that uses subbagging to preserve the local distribution of nearest neighbor (NN) distances. The main challenge is that the uniform reduction in total sample size within each subsample increases the proximity threshold for finding a fixed number k of NNs around the query. As a result, in the specific context of LID estimation, the sampling rate has an additional, complex interplay with the neighborhood size, where both combined determine the sample size as well as the locality and resolution considered for estimation. We analyze both theoretically and experimentally how the choice of the sampling rate and the k-NN size used for LID estimation, alongside the ensemble size, affects performance, enabling informed prior selection of these hyper-parameters depending on application-based preferences. Our results indicate that within broad and well-characterized regions of the hyper-parameters space, using a bagged estimator will most often significantly reduce variance as well as the mean squared error when compared to the corresponding non-bagged baseline, with controllable impact on bias. We additionally propose and evaluate different ways of combining bagging with neighborhood smoothing for substantial further improvements on LID estimation performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。