一句话总结

兰卡斯特大学的研究人员提出了一种高效的降维方法，通过构建最近邻对的矩阵来捕获局部协方差，得到密度信息矩阵（一种费舍尔信息矩阵的非参数类似物）的一致估计量，能够为聚类分析和异常检测等任务生成高信息量的投影，同时避免了以往基于替代密度估计方法的计算成本。

核心贡献

• 提出了一种降维方法，该方法通过最近邻对的谱分解构建投影矩阵，编码局部协方差，旨在增强最近邻关系。
• 在标准正则条件下，该矩阵是密度信息矩阵（DIM）的一致估计量，DIM是费舍尔信息的非参数类似物，克服了以往DIM估计方法的高计算成本和替代密度限制。
• 该方法在下游聚类分析和异常检测任务中展示了实用性。

引言

降维旨在保留多变量数据中的有用结构，可通过基于全局方差的方法（如主成分分析）或基于局部图的流形学习来实现。另一种信息论观点认为，在考虑尺度后熵较低的投影包含更多信息，因为多峰性和长尾性与聚类和异常点相关。密度信息矩阵提供了费舍尔信息矩阵的非参数类似物，并与独立成分分析和偏离高斯性有关联，但直接估计较困难。先前的工作主要估计与数据密度平方成比例的替代密度的DIM，作者发现这在高维环境中效果不佳。作者提出了一种基于DIM的k近邻估计的简单线性降维方法。该方法将数据投影到局部紧凑度矩阵乘以总协方差的前几个特征向量上，突出高密度局部结构，产生用于聚类和异常检测的低熵投影。

方法

作者开发了一种基于最近邻的密度信息矩阵（DIM）估计量，并使用它构建降维过程。核心量是矩阵 $I(\mathcal{X}, k)$I(X,k)，它根据样本 $\mathcal{X}$X 中第 $k$k 和第 $(k+1)$(k+1) 近邻距离及差向量计算。对每个点 $X_i$Xi​，识别其第 $k$k 和第 $(k+1)$(k+1) 近邻，并对它们差的外积用距离平方进行归一化。对所有点求和得到一个估计量，在正则条件下，当 $n\to\infty$n→∞ 且 $k(n)\to\infty$k(n)→∞ 且 $k(n)^{2-p/4}/n^{1-p/4}\to 0$k(n)2−p/4/n1−p/4→0 时，它以概率收敛到总体DIM $I(f_X)$I(fX​)。

理论分析分两阶段进行。首先，对固定点 $\mathbf{x}$x，展开第 $k$k 和第 $(k+1)$(k+1) 近邻差的归一化外积的条件期望。利用顺序统计量的条件独立结构和密度的泰勒展开，作者展示了

分解为一个主导的各向同性项，包含 $E[1/D_{\mathbf{x},n-1,(k)}^2 + 1/D_{\mathbf{x},n-1,(k+1)}^2]$E[1/Dx,n−1,(k)2​+1/Dx,n−1,(k+1)2​]，以及一项与 $\frac{1}{f_X(\mathbf{x})^2}\nabla f_X(\mathbf{x})\nabla f_X(\mathbf{x})^\prime$fX​(x)21​∇fX​(x)∇fX​(x)′ 成比例的项，加上来自Hessian矩阵的高阶贡献。对样本进行平均并使用顺序统计量的性质，$I(\mathbf{X}_n, k)$I(Xn​,k) 的期望被证明收敛到 $I(f_X)$I(fX​)，而在 $k(n)$k(n) 的速率条件下方差消失。引理2给出了连续近邻距离比的一致收敛性，确保依赖于Hessian的偏差项渐近积分到零。

为了改进有限样本性能，作者引入了三个实际修改。首先，通过在一定范围的 $k$k 值上对 $I(\mathcal{X}, k)$I(X,k) 求平均来减小方差，定义 $I(\mathcal{X}, k_0, k_1) = \frac{1}{k_1 - k_0 + 1}\sum_{k=k_0}^{k_1} I(\mathcal{X}, k)$I(X,k0​,k1​)=k1​−k0​+11​∑k=k0​k1​​I(X,k)。只要 $k_0(n)$k0​(n) 和 $k_1(n)$k1​(n) 满足定理1的条件，该平均估计量仍保持一致。

其次，对平均估计量的谱分解应用偏差调整。令 $I(\mathcal{X}, k_0, k_1) = \mathbf{U}\mathbf{D}\mathbf{U}^\prime$I(X,k0​,k1​)=UDU′。用 $\mathbf{D}_{ii}^* = \max\{\mathbf{D}_{ii}, (\mathbf{u}_i^\prime \Sigma_{\mathcal{X}} \mathbf{u}_i + \epsilon)^{-1}\}$Dii∗​=max{Dii​,(ui′​ΣX​ui​+ϵ)−1} 替换 $\mathbf{D}$D 的对角元素，其中 $\Sigma_{\mathcal{X}}$ΣX​ 为样本协方差矩阵，\epsilon} 为一个小的常数。该修正利用了一个已知的下界：对于总体 DIM，每个特征值 $\Delta_{ii}$Δii​ 满足 $\Delta_{ii} \ge 1/\mathrm{Var}(\mathbf{v}_i^\prime X)$Δii​≥1/Var(vi′​X)，其中 $\mathbf{v}_i$vi​ 为对应的特征向量。因此，调整后的矩阵 $I(\mathcal{X}, k_0, k_1)^*$I(X,k0​,k1​)∗ 遵守该界限，并且也收敛到 $I(f_X)$I(fX​)。

最后，从矩阵乘积 $I(\mathcal{X}, k_0, k_1)^* \Sigma_{\mathcal{X}}$I(X,k0​,k1​)∗ΣX​ 获得投影基。通过奇异值分解对其特征向量进行正交化：若 $\mathbf{W}$W 包含特征向量，则最终的投影方向为 $\mathbf{W}^* = \mathbf{W}_u \mathbf{W}_v^\prime$W∗=Wu​Wv′​ 的列，其中 $\mathbf{W}_u$Wu​ 和 $\mathbf{W}_v$Wv​ 分别为 $\mathbf{W}$W 的左、右奇异向量。该步骤确保投影后的数据保留了更多的总方差，改善聚类和异常检测等下游任务。因此，整个流程从最近邻统计量估计 DIM，通过平均和偏差修正进行精化，并生成保留 DIM 捕获结构的正交投影。

实验

实验将提出的最近邻 DIM（nnDIM）与 PCA、稳健 PCA、LPP 和 kDIM 作为降维工具，在 45 个分类数据集上对聚类和异常检测进行评估，并在高斯数据上验证估计精度。对于聚类，nnDIM 是唯一在应用于高维数据时在所有四种聚类算法上持续改进性能的方法。在异常检测中，nnDIM 与 sLOF 和隔离森林良好配合，适用于有一或两个内点类的数据集，但单一异常类设置下的改进不够确定。