多维空间中的随机单位向量

Question

我正在研究一个数据挖掘算法，在其中我想从特征空间的一个特定点选择一个随机方向。

如果我为每个 n 个维度选取 [-1,1] 中的一个随机数，然后将向量标准化到长度为 1，这样做是否能够获得所有可能方向上的均匀分布？

我这里仅在理论上讨论，因为计算机生成的随机数实际上并不是真正的随机。

- Matt

Answer 1

一个简单的技巧是从高斯分布中选择每个维度，然后进行归一化：

from random import gauss

def make_rand_vector(dims):
    vec = [gauss(0, 1) for i in range(dims)]
    mag = sum(x**2 for x in vec) ** .5
    return [x/mag for x in vec]

例如，如果你想要一个7维的随机向量，选择7个随机值（从均值为0、标准差为1的高斯分布中选择）。然后，使用勾股定理计算出所得向量的大小（将每个值平方、相加并对结果取平方根）。最后，将每个值除以向量大小以获得归一化的随机向量。

如果您的维数很大，那么这样做的强有力的好处是总是能立即得到结果，而随机生成向量直到找到一个其大小小于1的向量会导致您的计算机在大约十几个维度时停滞不前，因为任何一个向量符合要求的概率都变得非常小。

- Bram Cohen

---

顺便说一下，这就是boost http://www.boost.org/doc/libs/1_47_0/boost/random/uniform_on_sphere.hpp的实现方式。;) - Jorge Leitao

这是一个有关为什么这种方法正确的参考资料：http://mathworld.wolfram.com/HyperspherePointPicking.html。 - yoavram

为什么这个方法可行的简要解释：一个点位于给定的<x,y>位置上的概率P为P(x)*P(y)。高斯分布大致形式为e^(-x^2)，因此e^(-x^2)*e^(-y^2)可以表示为e^(-(x^2+y^2))。这是一个仅与点到原点距离相关的函数，因此得到的分布具有径向对称性。这个方法可以很容易地推广到更高的维度。 - mindoftea

附加说明：Box-Muller变换可用于从独立的均匀分布对生成独立的正态分布对（没有“浪费”）。 - Rhubbarb

使用 numpy，这将是 vec = numpy.random.randn(dims); return vec / numpy.linalg.norm(vec)。 - stav

Answer 2

使用您描述的算法将无法获得角度的均匀分布集合。 角度将偏向于n维超立方体的角落。

可以通过消除距离原点大于1的任何点来解决此问题。 然后，您处理的是球形而不是立方体（n维）体积，您的角度集应在样本空间上均匀分布。

伪代码：

设n为维数，K为所需向量数：

vec_count=0
while vec_count < K
   generate n uniformly distributed values a[0..n-1] over [-1, 1]
   r_squared = sum over i=0,n-1 of a[i]^2
   if 0 < r_squared <= 1.0
      b[i] = a[i]/sqrt(r_squared)  ; normalize to length of 1
      add vector b[0..n-1] to output list
      vec_count = vec_count + 1
   else
      reject this sample
end while

- Jim Lewis

---

这正是我担心的事情。我只是无法像你描述的那样在脑海中形式化它。直觉上，我知道我希望我的可能随机向量描述一个圆。我只是没有看到如何在代码中实现它。 - Matt

@Matt：我对我的回答进行了扩展，希望能有所帮助。 - Jim Lewis

如果你可以用一个封闭形式的表达式解决问题，为什么要使用具有非确定性运行时间和分支的算法呢？ - John Shedletsky

在高维空间中，这非常低效。例如，在6个维度中，只有8%的样本会被接受。在10个维度中，这一比例降至0.25%。 - trbabb

Answer 3

有一种使用正态分布进行采样的算法，它是boost实现的：random::uniform_on_sphere

- killogre

Answer 4

在开发机器学习算法时，我也曾经有过同样的问题。

在绘制2D样本并绘制角度分布后，我得出了与Jim Lewis相同的结论。

此外，如果您尝试从[-1,1]中随机抽取x轴和y轴的值，并推导出2D方向的密度分布，则会发现：

f_X(x) = 1/(4*cos²(x))，如果 0 < x < 45⁰
且
f_X(x) = 1/(4*sin²(x))，如果 x > 45⁰

其中x是角度，f_X是概率密度分布。

关于这个问题，我在这里写了一篇文章： https://aerodatablog.wordpress.com/2018/01/14/random-hyperplanes/

- cmhteixeira

Answer 5

#define SCL1 (M_SQRT2/2)
#define SCL2 (M_SQRT2*2)

// unitrand in [-1,1].
double u = SCL1 * unitrand();
double v = SCL1 * unitrand();
double w = SCL2 * sqrt(1.0 - u*u - v*v);

double x = w * u;
double y = w * v;
double z = 1.0 - 2.0 * (u*u + v*v);

- MC Pee Pants

---

对于像我这样的非机械类人来说，代码不再难以阅读。对此有什么评论吗？为什么它比已接受的答案更好，或者有其他什么看法？ - Nikana Reklawyks