random - 多次元空間のランダム単位ベクトル

Question

特徴空間の特定のポイントからランダムな方向を選択したいデータ マイニング アルゴリズムに取り組んでいます。

[-1,1] から n 次元ごとに乱数を選択し、ベクトルを長さ 1 に正規化すると、考えられるすべての方向に均等に分布しますか?

コンピューターで生成された乱数は実際にはランダムではないため、ここでは理論的にのみ話しています。

Answer 1

簡単なトリックの 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 次元のランダム ベクトルが必要な場合は、(平均 0、標準偏差 1 のガウス分布から) 7 つのランダム値を選択します。次に、ピタゴラスの公式を使用して結果のベクトルの大きさを計算します (各値を 2 乗し、2 乗を加算し、結果の平方根をとります)。最後に、各値を大きさで割り、正規化されたランダム ベクトルを取得します。

次元数が多い場合、これには常にすぐに機能するという大きな利点がありますが、たまたま大きさが 1 より小さいベクトルが見つかるまでランダムなベクトルを生成すると、コンピュータが 12 以上の次元でハングアップするだけです。それらのいずれかが資格を得る可能性が非常に小さくなるためです。

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

Answer 3

正規分布からサンプリングするアルゴリズムのブースト実装があります: random::uniform_on_sphere

Answer 4

#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);