algorithm - ISOMAP算法中获取邻域大小

Question

我正在研究 ISOMAP 算法的原始文章，我无法理解如何根据经验获得适当的邻域大小 (epsilon)。

它说它可以通过“欧几里德中未考虑的测地距离估计方差的分数”和最近点的数量之间的权衡获得。

但事实上，我并没有流形中的真实测地距离，对吧？那么，如何计算实际距离与其欧几里得估计值之间的残差？

提前感谢所有愿意提供帮助的人。

最好的问候，

瓦伦蒂娜

Answer 1

简短回答:每个人都使用 8-12 的邻域大小。

更长的答案:您可能无法测量欧氏距离和流形距离之间的差异。 Isomap 近似测地线距离——使用附近邻居图上的最短路径距离。

这个近似值有多好？如果你有大量的点，这样你就可以，例如选择一个大小为 100 的邻域，并且所有 100 个点都在你的点附近，并且到所有 100 个点的路径都非常靠近流形，那么你可以使用100 的邻域大小和最短路径图可能非常接近测地线距离。

通常，你没有那么多积分。那么你就陷入了权衡:

使用的点太少，你的最短路径必须曲折一点

使用太多的点，并且可能有一个直接连接点的链接，这些点应该远离(在流形上)，但包含在您的邻居中。

您如何解决这个权衡问题？

嗯，选8-12分吧。如果你的流形是 2-3 维的(它可能存在于高维空间中，但流形上的点仅在每个点附近的几个维度上变化)，那么 8-12 个点为每个点提供了一些选项以链接成一个一堆不同的方向。

如果你的流形超过 2-3 维，那么 Isomap 可能不起作用，你需要有一个更大的邻域大小(更多的点!)这样你就有合理的选择来估计你的测地线路径链接到附近的邻居。

有趣的旁注:如果您选择邻域大小作为所有点，Isomap == PCA。