“维度灾难”之Hubness现象

“维度灾难”是一个很宽泛的概念，所有在高维空间中与相应的二维、三维空间版本出入很大的结论，都可以称之为“维度灾难”，比如《n维空间下两个随机向量的夹角分布》中介绍的“高维空间中任何两个向量机几乎都是垂直的”。其中，有不少维度灾难现象有着同一个源头——“高维空间单位球与其外切正方体的体积之比逐渐坍缩至0”，包括本文的主题“Hubness现象”亦是如此。

Hubness现象，它说的是在高维空间中随机选一批点，那么“总有一些点经常出现在其他点的 $k$ 邻近中”。
具体怎么理解这句话呢？假设我们有 $N$ 个点 $x_{1}, x_{2}, \dots, x_{N}$ ，对于每个xixi，我们都可以找出与之最相近的 $k$ 个点，这 $k$ 个点都称为“ $x_{i}$ 的 $k$ 邻近”。有了 $k$ 邻近的概念后，我们可以统计每个点出现在其他点的 $k$ 邻近的次数，这个次数称为“Hub值”，也就是说Hub值越大，它就越容易出现在其他点的 $k$ 邻近中。

所以，Hubness现象说的是：总有那么几个点，它的Hub值显然特别大。如果Hub值代表着“财富”，那么一个形象的比喻就是“80%的财富集中在20%的人手中”，并且随着维度增大，这个“贫富差距”就越来越大；如果Hub值代表着“人脉”，那么也可以形象地比喻为“社群中总有那么几个人拥有非常广泛的人脉资源”。

Hubness现象是怎么出现的呢？其实也跟前一节说的nn维球的坍缩有关。我们知道，与所有点距离平方和最小的点，正好是均值点：

\frac{1}{N} \sum_{i = 1}^{N} x_{i} = c^{*} = \underset{c}{\arg min} \sum_{i = 1}^{N} {‖ x_{i} - c ‖}^{2}

这也就意味着，在均值向量附近的点，与所有点的平均距离较小，有更大的机会成为更多点的kk邻近。而nn维球的坍缩现象则告诉我们，“均值向量附近的点”，即以均值向量为球心的一个球邻域，其占比是非常小的。于是就出现了“非常少的点出现在很多点的kk邻近中”这一现象了。当然，这里的均值向量是比较直观的理解，在一般的数据点中，应该是越靠近密度中心的点，其Hub值会变得越大。