前回の記事で紹介した、Johnson–Lindenstraussの補題を理論的背景に持つ次元削減の手法として、
Random projection と呼ばれるものがあります。
参考: Random projection – Wikipedia
手法は至ってシンプルで、乱数で生成した行列を掛けるによってデータを低次元へと埋め込んでしまうようです。
補題が主張する、距離を維持できる線形写像があるぞって話と、
ランダムに生成した行列で定義される線型写像で距離が維持できるぞと言う話は、
かなり論理にギャップがあるように感じ、その間のロジックをまだ正確には追えていないのですが、
scikit-learnに実装があるのでまずは試してみることにしました。
2000次元のデータを1000件用意し、Gaussian Random Projection という要するに正規分布で生成した行列で低次元にうつす手法を使い、
距離が保たれていることを確認します。
まずはデータの生成です。
import numpy as np
X = np.random.randn(1000, 2000)*10
print(X.shape)
# (1000, 2000)
続いて、Gaussian Random Projection のモデルのインスタンスを生成して、学習、変換します。
ハイパーパラメーター$\varepsilon$は$0.5$としました。
ドキュメントによると、次元削減後の次元は
$n\_components >= 4 \log(n\_samples) / (eps^2 / 2 – eps^3 / 3)$
となるようです。
print(4*np.log(len(X))/(eps**2/2-eps**3/3))
# 331.5722533911425
ですから、 332次元に圧縮されるかと思いきや、結果は331次元になります。
(ドキュメントのミスなのかバグなのか不明)
from sklearn.random_projection import GaussianRandomProjection
eps = 0.5
grp = GaussianRandomProjection(eps=eps)
grp.fit(X)
X_new = grp.transform(X)
print(X_new.shape)
# (1000, 331)
これで、元々2000次元だったデータを331次元に圧縮することができました。
それも、331×2000次元のランダム行列を掛けただけという、超単純な方法でです。
ちなみにその行列自体は grp.components_で取得できます。
print(grp.components_.shape)
# (331, 2000)
print(grp.components_.mean())
# -7.730060662586934e-05
print(grp.components_.var())
# 0.0030132642015398016
要素の平均はほぼ$0$であり、分散は$1/331=0.0030211…$に近い値になっており、ドキュメント通りであることが確認できます。
さて、最後に距離がある程度保存できていることを確認しておきましょう。
元のデータ X と、変換後のデータX_new それぞれについて距離行列を算出します。
そして、比率(変化率)を算出しその最小最大を見てみましょう。
X_pdist = pdist(X)
X_new_pdist = pdist(X_new)
print((X_new_pdist/X_pdist).min(), (X_new_pdist/X_pdist).max())
# 0.8230255694414008 1.18365715425175
eps が 0.5 だったので、 0.5倍〜1.5倍の範囲に収まる想定だったのですが、それよりもずっと良い精度で距離を維持できていることがわかりました。
今回は元のデータが正規分布だったので簡単だったのかもしれませんね。