如何在d维球/球体内生成均匀的随机点? [英] How to generate uniform random points inside d-dimension ball / sphere?

问题描述

我环顾四周，所有在单位球内/上生成均匀随机点的解决方案都是为 2 维或 3 维设计的.

什么是(易处理的)在任意维度的球内生成均匀随机点的方法?特别是，不仅仅是在表面上球.

作为序言，在多维数据集中生成随机点并丢弃范数大于 1 的点在高维中不可行.单位球的体积与高维单位立方体的体积之比为0.即使在10维中，单位立方体中也只有约0.25%的随机点也在单位球内部.

解决方案

在 d 维球中生成均匀分布的随机点的最佳方法似乎是考虑极坐标(方向而不是位置).代码如下.

1. 在单位球上随机选取一个均匀分布的点.
2. 选择一个随机半径，其中半径的可能性对应于 d 维度中具有该半径的球的表面积.

此选择过程将 (1) 使所有方向的可能性相等，以及 (2) 使单位球内的球表面上的所有点的可能性均等.这将在球的整个内部生成我们想要的均匀随机分布.

选择一个随机方向(在单位球上)

为了实现 (1)，我们可以从 d 独立绘制的归一化为单位长度的高斯分布随机生成一个向量.与 成正比r^d，这意味着我们可以在 [0,1] 范围内使用它作为 CDF.现在通过将 [0,1] 范围内的随机数映射到逆r^(1/d) 来生成随机样本.

这是x^2(二维)的CDF的视觉效果，[0,1]中随机生成的数字将映射到相应的x这条曲线上的坐标.(例如 .1 ➞ .317)

<小时>

以上代码

最后，这里有一些 Python 代码(假设您安装了 NumPy)，用于计算上述所有内容.

# 在维度"中生成num_points"个具有均匀性的随机点# 由半径"(点的长度)缩放的单位球的概率# 在范围 [0, "radius"]) 内.def random_ball(num_points, 维度, 半径=1):从 numpy 导入随机，linalg# 首先通过对a的长度进行归一化来生成随机方向# 随机正态值向量(这些在球上均匀分布).random_directions = random.normal(size=(dimension,num_points))random_directions/= linalg.norm(random_directions,axis=0)# 第二个随机半径与概率成正比# 给定半径的球的表面积.random_radii = random.random(num_points) ** (1/dimension)# 返回随机(方向和长度)点的列表.返回半径 * (random_directions * random_radii).T

为了后代，这里是使用上述代码生成的 5000 个随机点的视觉效果.

I've looked around and all solutions for generating uniform random points in/on the unit ball are designed for 2 or 3 dimensions.

What is a (tractable) way to generate uniform random points inside a ball in arbitrary dimension? Particularly, not just on the surface of the ball.

To preface, generating random points in the cube and throwing out the points with norm greater than 1 is not feasible in high dimension. The ratio of the volume of a unit ball to the volume of a unit cube in high dimension goes to 0. Even in 10 dimensions only about 0.25% of random points in the unit cube are also inside the unit ball.

解决方案

The best way to generate uniformly distributed random points in a d-dimension ball appears to be by thinking of polar coordinates (directions instead of locations). Code is provided below.

1. Pick a random point on the unit ball with uniform distribution.
2. Pick a random radius where the likelihood of a radius corresponds to the surface area of a ball with that radius in d dimensions.

This selection process will (1) make all directions equally likely, and (2) make all points on the surface of balls within the unit ball equally likely. This will generate our desired uniformly random distribution over the entire interior of the ball.

Picking a random direction (on the unit ball)

In order to achieve (1) we can randomly generate a vector from d independent draws of a Gaussian distribution normalized to unit length. This works because a Gausssian distribution has a probability distribution function (PDF) with x^2 in an exponent. That implies that the joint distribution (for independent random variables this is the multiplication of their PDFs) will have (x_1^2 + x_2^2 + ... + x_d^2) in the exponent. Notice that resembles the definition of a sphere in d dimensions, meaning the joint distribution of d independent samples from a Gaussian distribution is invariant to rotation (the vectors are uniform over a sphere).

Here is what 200 random points generated in 2D looks like.

---

Picking a random radius (with appropriate probability)

In order to achieve (2) we can generate a radius by using the inverse of a cumulative distribution function (CDF) that corresponds to the surface area of a ball in d dimensions with radius r. We know that the surface area of an n-ball is proportional to r^d, meaning we can use this over the range [0,1] as a CDF. Now a random sample is generated by mapping random numbers in the range [0,1] through the inverse, r^(1/d).

Here is a visual of the CDF of x^2 (for two dimensions), random generated numbers in [0,1] would get mapped to the corresponding x coordinate on this curve. (e.g. .1 ➞ .317)

---

Code for the above

Finally, here is some Python code (assumes you have NumPy installed) that computes all of the above.

# Generate "num_points" random points in "dimension" that have uniform
# probability over the unit ball scaled by "radius" (length of points
# are in range [0, "radius"]).
def random_ball(num_points, dimension, radius=1):
    from numpy import random, linalg
    # First generate random directions by normalizing the length of a
    # vector of random-normal values (these distribute evenly on ball).
    random_directions = random.normal(size=(dimension,num_points))
    random_directions /= linalg.norm(random_directions, axis=0)
    # Second generate a random radius with probability proportional to
    # the surface area of a ball with a given radius.
    random_radii = random.random(num_points) ** (1/dimension)
    # Return the list of random (direction & length) points.
    return radius * (random_directions * random_radii).T

For posterity, here is a visual of 5000 random points generated with the above code.

这篇关于如何在d维球/球体内生成均匀的随机点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！