このガイドは、ランダム投影と呼ばれる教師なし次元削減技法について詳しく紹介するものである。
ランダムプロジェクションは、データの複雑さとサイズを縮小し、データの処理と可視化を容易にするために使用できます。
また、分類器やリグレッサへの入力準備のための前処理技法でもあります。
>
ランダムプロジェクションは一般的に、主成分分析(PCA)などの他の手法ではデータを正しく扱うことができない、高次元データに適用されます。
このガイドでは、ランダムプロジェクションの数学的な基礎となるジョンソン-リンデンストラウスのレンマの詳細について説明します。
また、PythonのScikit-Learnライブラリを使ってランダムプロジェクションを実行し、入力データを低次元空間に変換する方法についても紹介します。
>
> 理論には理論が、実践には実践が必要です。
実践編として、ロイター・コーパス第1巻データセットを読み込み、ガウスランダム射影とスパースランダム射影を適用してみます。
データセットのランダム投影とは？
簡単に言うと
>
ランダム投影は、高次元のデータセットの複雑さを単純化する、次元削減とデータ可視化の手法です。
この方法は、ランダムに選ばれた一連の方向に沿って各データ点の投影を取ることで、新しいデータセットを生成する。
データ点のベクトルへの投影は、点とベクトルの内積を取ることと数学的に等価である。
次元mxnmxnmxnのデータ行列XXXと、ランダムな方向を表すベクトルを列とするdxndxndxnの行列RRRが与えられたとき、XXXのランダム投影はXpXpXpha_pで与えらる。
Xp=XRXp=XR となる。
Xp
</msub
=XR
ランダムな方向を表す各ベクトルの次元はnnnであり、これはXXXの全データ点と同じである。
もし、ddd個のランダムな方向をとると、ddd次元の変換されたデータセットができあがります。
このチュートリアルのために、いくつかの表記を修正します。
-
m: 入力データのサンプル点数/サンプルの総数。 -
n: 入力データの特徴量/属性の総数。これは、元データの次元数でもあります。 -
d: 変換後のデータの次元数
ランダムプロジェクションの考え方は，基本的には主成分分析 (PCA) と非常によく似ている．しかし，PCA では射影行列は固有ベクトルを介して計算されるため，大きな行列では計算量が多くなってしまいます．
>
ランダムプロジェクションを行うと、ベクトルがランダムに選ばれるため、非常に効率的です。
投影」という名前は、ベクトルがランダムに選択されるため、少し誤解を招くかもしれませんが、変換された点は数学的には真の投影ではありませんが、真の投影に近いものになります。
次元を減らしたデータは扱いやすくなります。
可視化できるだけでなく、前処理の段階で元データのサイズを小さくすることができます。
簡単な例
この変換がどのように機能するかを理解するために，次のような簡単な例を挙げてみよう。
入力行列XXXは次のように与えられるとします。
X=⎡⎢⎣132001211300⎤⎥⎦X=[132001211300]X=
<モ>[<モ
1
</mtd
3となります。
</mtd
2の場合
</mtd
0の場合
</mtd
</mtr
0となります。
</mtd
1の場合
</mtd
2の場合
</mtd
1の場合
</mtd
</mtr
1となります。
</mtd
3となります。
</mtd
0の場合
</mtd
0の場合
</mtd
]のようになります。
そして、射影行列は次式で与えられる。
R=12⎡⎢
⎢
⎢⎣1-1111-111⎤⎥
⎥
⎥⎦R=12[1−1111−111]R=12[のように
1
</mtd
-のように
1</mn
</mtd
</mtr
1となります。
</mtd
1となります。
</mtd
</mtr
1となります。
</mtd
-のように
1</mn
</mtd
</mtr
1となります。
</mtd
1となります。
Xp=XR=12⎡⎢⎣604042⎤⎥⎦Xp=XR=12[604042]の場合
Xp
</msub
=XR=12[のように
6
</mtd
0の場合
</mtd
</mtr
4</mn
</mtd
0の場合
</mtd
</mtr
4</mn
</mtd
2の場合
</mtd
]のように
</math
>
4次元空間の3点から始めて、巧みな行列演算によって、2次元空間の3点を変換することに成功しました。
投影行列RRRのいくつかの重要な属性に注意してください。
各列は単位行列であり、すなわち各列のノルムは1である。
また、すべての列を対にして（この場合は列1と列2のみ）とった内積は0であり、これは両方の列ベクトルが互いに直交していることを示しています。
このことから、この行列は「正規直交行列」であることがわかります。
しかし、ランダムプロジェクション法では、高次元のデータを扱う場合、投影行列は正規直交行列である必要はありません。
ランダムプロジェクションの成功は、ジョンソン・リンデンストラウスのレンマと呼ばれる素晴らしい数学的発見に基づいています。
ジョンソン・リンデンストラウスのレンマ
ジョンソン-リンデンストラウスのレンマはランダム射影の数学的基礎である。
の数学的基礎となるものです。
Johnson-Lindenstrauss のレンマは、データ点が非常に高次元の空間にある場合、その点を単純なランダムな方向に投影すると、それらの対の距離が保存されることを述べている。
対距離の保存は、元の空間における点間の対距離が、投影された低次元空間における対距離と同じか、ほとんど同じであることを意味する。
>
このように、データの構造やデータ内のクラスターは低次元空間でも維持され、データの複雑さやサイズは大幅に削減される。
本手引きでは、新しい空間に投影することによって生じる、実際のペアワイズ距離と投影距離の差を、データの「歪み」と呼ぶことにする。
Johnson-Lindenstrauss のレンマは、誤差や歪みがある範囲に収まるようにデータ点を投影する次元数の「安全な」指標も提供しており、目標とする次元数を容易に見つけることができる。
数学的には、点 (x1,x2)(x1,x2)(x´_1,x´2) とそれに対応する射影 (x′1,x′2)(x1′,x´2′)(x´_1′,x´2′) の組があれば、eps-embedding が定義されます。
(1−ϵ)|x1−x2|2<|x′1−x′2|2<(1+ϵ)|x1−x2|2(1−ϵ)|x1−x2|2<|x1′−x2′|2<(1+ϵ)|x1−x2|2
(1 – epsilon) |x_1 – x_2|^2 < |x1′ – x2’|^2 < (1 + epsilon) |x___1 – x_2|^2
Johnson-Lindenstrauss lemmaは、上記のeps-embeddingが維持されるような低次元空間の最小次元を規定している。
投影行列のランダムな方向の決定
射影行列を決定する方法としてよく知られているのは次の2つである。
- ガウスランダム射影: 平均が0のガウス分布からランダムに要素を選んで投影行列を構成する．
- スパースランダム射影．比較的単純な方法で，各ベクトル成分は {-k,0,+k} の集合から値をとる（k は定数）．この行列の要素を生成する簡単な方法の1つは、
Achlioptas法とも呼ばれ、 k=√3k=3k=sqrt 3 とすることである。
Rij=√3⎧⎪。
⎪⎨⎪
⎪⎩+Sm_23AA↩⎩1で確率160、確率23-1で確率16Rij=3{+1、確率160、確率23-1で確率16となる。
の
Rの場合
ij
</mrow
の
=3
</msqrt
{+1
</mtd
確率で。
</mtd
1の場合
6となります。
</mfrac
</mtd
</mtr
0の場合
</mtd
確率で。
</mtd
2の場合
3
</mfrac
</mtd
</mtr
-のように
1
</mtd
確率で。
</mtd
1の場合
6となります。
</mfrac
</mtd
の
となります。
</mrow
上の方法は、サイコロを振って出た目の数だけ、{+k,0,-k} から数字を選ぶのと同じです。
サイコロの目が1であれば、+kを選ぶ。
サイコロの目が[2,5]`の場合は0を選び、サイコロの目が6の場合は-kを選びます。
より一般的な方法は、 density パラメータを使用してランダム投影行列を選択する方法です。
s=1densitys=density} とすると、Random Projection matrix の要素は以下のように選ばれます。
Rij=⎧⎪とする。
⎪
⎪
⎪⎨⎪
⎪
⎪
⎩+√AA⎠確率12sd確率1-1s-√sd確率12sRij={+sd確率12s0確率1-1s-sd確率12sの場合
Rの場合
ij
</mrow
の
={+sd
</msqrt
</mtd
確率で。
</mtd
1</mn
2</mn
s
</mtr
0の場合
</mtd
確率で。
</mtd
1-となります。
1s
</mtr
-のように
sd
</msqrt
</mtd
確率で。
</mtd
1</mn
2</mn
sとなります。
</mrow
</math
一般的には、densityパラメータを1√n1nfrac{1}{sqrt n}に設定することが推奨されています。
前述したように、ガウス法とスパース法の両方において、投影行列は真の直交正規行列ではありません。
しかし、高次元空間では、上記2つの方法のいずれかを用いてランダムに選ばれた行列は、正則行列に近いことが示されている。
Scikit-Learnを用いたランダムプロジェクション
Scikit-Learn ライブラリは random_projection モジュールを提供しており、これには3つの重要なクラス/モジュールがあります。
-
johnson_lindenstrauss_min_dim(): サンプルサイズmが与えられたときに、変換されたデータの最小次元数を決定するためのものです。 -
GaussianRandomProjection: ガウスランダム射影を行う。ガウスランダム射影を行う。 -
SparseRandomProjection: スパースランダム射影を行う。スパースランダム射影を行う。
以下の節で上記3つのデモを行いますが、まず、使用するクラスと関数をインポートしましょう。
from sklearn.random_projection import SparseRandomProjection, johnson_lindenstrauss_min_dim
from sklearn.random_projection import GaussianRandomProjection
import numpy as np
from matplotlib import pyplot as plt
import sklearn.datasets as dt
from sklearn.metrics.pairwise import euclidean_distances
ジョンソン・リンデンストラウスのレンマによる次元数の最小値の決定
関数 johnson_lindenstrauss_min_dim() は、例数 m と eps または ϵepsilon パラメータが与えられたときに入力データをマップできる最小の次元数 d を決定する。
以下のコードでは、異なるサンプル数で実験し、データの歪みをある「安全な」状態に保つ低次元空間の最小サイズを決定しています。
さらに、異なるサンプルサイズ m に対して、 log(d) を eps の異なる値に対してプロットしています。
注意すべき重要な点は、ジョンソン・リンデンストラウス・レンマは、低次元空間のサイズdddを入力データ中の例点の数mmmに基づいてのみ決定することである。
元データの属性や特徴の数nnnは関係ない。
eps = np.arange(0.001, 0.999, 0.01)
colors = ['b', 'g', 'm', 'c']
m = [1e1, 1e3, 1e7, 1e10]
for i in range(4):
min_dim = johnson_lindenstrauss_min_dim(n_samples=m[i], eps=eps)
label = 'Total samples = ' + str(m[i])
plt.plot(eps, np.log10(min_dim), c=colors[i], label=label)
plt.xlabel('eps')
plt.ylabel('log$_{10}$(d)')
plt.axhline(y=3.5, color='k', linestyle=':')
plt.legend()
plt.show()
上のプロットから、epsが小さいうちはdが非常に大きく、epsが1に近づくと小さくなることがわかる。
また、中程度から大きな値のeps` では、次元数は3500以下（黒の点線）であることがわかります。
>
このことから、ランダムプロジェクションの適用が意味を持つのは、数千の特徴量のオーダーを持つ高次元データのみであることがわかります。
このような場合、高い次元削減が達成できる。
したがって、ランダム投影法は、主成分分析では困難な、多数の入力特徴を持つテキストや画像データに対して非常に有効である。
データ変換
Python は sklearn ライブラリにガウスランダム射影とスパースランダム射影を実装しており、それぞれ GaussianRandomProjection と SparseRandomProjection というクラスがあります。
これらのクラスの重要な属性は以下の通りです（リストは完全なものではありません）。
-
n_components: 変換されたデータの次元数．この属性がautoに設定されている場合、投影の前に最適な次元が決定されます。 -
eps: Johnson-Lindenstrauss lemma のパラメータ．投影データの歪みが一定の範囲内に収まるように，次元数を制御する． -
density: SparseRandomProjectionに対してのみ適用されます。デフォルト値はauto` で、投影行列の選択に s=1√ns=1ns=httpd{1}{sqrt n} を指定します。
他の sklearn の次元削減クラスと同様に、これらのクラスも標準的な fit() と fit_transform() メソッドを備えています。
便利な属性として、以下のようなものがあります。
-
n_components: データが投影される新しい空間の次元数． -
components_: 変換行列または射影行列． -
density_: SparseRandomProjectionに対してのみ適用されます．投影行列の要素を計算する際の基準となるdensity` の値です．
GaussianRandomProjection によるランダムプロジェクション
まずは、 GaussianRandomProjection クラスから始めましょう。
射影行列の値はヒストグラムとしてプロットされ、平均が 0 のガウス分布に従うことがわかります。
データ行列のサイズは、5000 から 3947 に減少します。
X_rand = np.random.RandomState(0).rand(100, 5000)
proj_gauss = GaussianRandomProjection(random_state=0)
X_transformed = proj_gauss.fit_transform(X_rand)
# Print the size of the transformed data
print('Shape of transformed data: ' + str(X_transformed.shape))
# Generate a histogram of the elements of the transformation matrix
plt.hist(proj_gauss.components_.flatten())
plt.title('Histogram of the flattened transformation matrix')
plt.show()
このコードの結果は
Shape of transformed data: (100, 3947)
SparseRandomProjection によるランダムプロジェクション
以下のコードは、Sparse Random Projection を使って、どのようにデータ変換を行うかを示しています。
変換行列全体は、3つの異なる値で構成され、その頻度プロットは下にも示されています。
この変換行列は、 SciPy の疎な csr_matrix であることに注意してください。
以下のコードでは、 csr_matrix の 0 ではない値にアクセスし、それらを p に格納します。
次に、 p を用いて、疎な射影行列の要素の個数を求めます。
proj_sparse = SparseRandomProjection(random_state=0)
X_transformed = proj_sparse.fit_transform(X_rand)
# Print the size of the transformed data
print('Shape of transformed data: ' + str(X_transformed.shape))
# Get data of the transformation matrix and store in p.
# p consists of only 2 non-zero distinct values, i.e., pos and neg
# pos and neg are determined below
p = proj_sparse.components_.data
total_elements = proj_sparse.components_.shape[0] *
proj_sparse.components_.shape[1]
pos = p[p>0][0]
neg = p[p<0][0]
print('Shape of transformation matrix: '+ str(proj_sparse.components_.shape))
counts = (sum(p==neg), total_elements - len(p), sum(p==pos))
# Histogram of the elements of the transformation matrix
plt.bar([neg, 0, pos], counts, width=0.1)
plt.xticks([neg, 0, pos])
plt.suptitle('Histogram of flattened transformation matrix, ' +
'density = ' +
'{:.2f}'.format(proj_sparse.density_))
plt.show()
この結果は、以下のようになります。
Shape of transformed data: (100, 3947)
Shape of transformation matrix: (3947, 5000)
このヒストグラムは、前のセクションで説明した疎なランダム投影行列の生成方法と一致しています。
ゼロは確率的に（1-1/100 = 0.99）で選択されるので、この行列の値の約99%はゼロです。
疎行列のデータ構造とルーチンを利用することで、この変換方法は大規模なデータセットに対して非常に高速かつ効率的に行うことができます。
ロイター・コーパス第1巻のデータセットによる実用的なランダム投影法
このセクションでは、ロイター・コーパス第1巻のデータセットを使ったランダムプロジェクションを説明します。
このデータセットはオンラインで自由にアクセスできますが、我々の目的には、Scikit-Learnで検索するのが最も簡単です。
sklearn.datasetsモジュールには、データセットをダウンロードしてインポートするfetch_rcv1()` 関数が含まれています。
注意：この方法で事前にインポートしたことがない場合、データセットのダウンロードに数分かかることがあります。
プログレスバーがないので、スクリプトが先に進まずに止まっているように見えるかもしれません。
最初に実行するときは、少し時間をおいてください。
RCV1データセットは、各データ点が同時に複数のクラスに属することができるマルチラベルデータセットであり、103個のクラスから構成されています。
各データポイントの次元数はなんと47,236であり、高速かつ安価なランダムプロジェクションの適用に理想的なケースと言えます。
ランダムプロジェクションの有効性を実証するために、そして物事をシンプルにするために、最初の3つのクラスのうち少なくとも1つに属する500個のデータポイントを選択することにします。
fetch_rcv1()` 関数は、データセットを取得し、データとターゲットを含むオブジェクトを返します。
それでは、ロイター・コーパスを取得して、データ変換の準備をしましょう。
total_points = 500
# Fetch the dataset
dat = dt.fetch_rcv1()
# Select the sparse matrix's non-zero targets
target_nz = dat.target.nonzero()
# Select only indices of target_nz for data points that belong to
# either of class 1,2,3
ind_class_123 = np.asarray(np.where((target_nz[1]==0) |
(target_nz[1]==1) |
(target_nz[1] == 2))).flatten()
# Choose only 500 indices randomly
np.random.seed(0)
ind_class_123 = np.random.choice(ind_class_123, total_points,
replace=False)
# Retreive the row indices of data matrix and target matrix
row_ind = target_nz[0][ind_class_123]
X = dat.data[row_ind,:]
y = np.array(dat.target[row_ind,0:3].todense())
データ準備の後、投影されたデータの視覚化を行う関数が必要です。
データ変換の品質を知るために、以下の3つの行列を計算することができます。
-
dist_raw: 実際のデータ点のペアワイズユークリッド距離の行列． -
dist_transform: 変換後のデータ点のペアワイズユークリッド距離の行列 *abs_diff: 変換後のデータ点のペアワイズユークリッド距離の行列． -
abs_diff: dist_rawとdist_actual` の差の絶対値を表す行列．
abs_diff_dist` 行列は，データ変換の品質を表す良い指標となります．この行列の値が 0 に近いか小さい場合は、歪みが少なく、良好な変換が行われていることを示します。
この行列の画像を直接表示したり、その値のヒストグラムを生成したりして、変換を視覚的に評価することができます。
関数 create_visualization() は，3つのプロットを作成します．最初のグラフは，最初の2つのランダムな方向に沿って点を投影した散布図です．2番目のプロットは，差の絶対値行列の画像であり，3番目のプロットは，差の絶対値行列の値のヒストグラムです．
def create_visualization(X_transform, y, abs_diff):
fig,ax = plt.subplots(nrows=1, ncols=3, figsize=(20,7))
plt.subplot(131)
plt.scatter(X_transform[y[:,0]==1,0], X_transform[y[:,0]==1,1], c='r', alpha=0.4)
plt.scatter(X_transform[y[:,1]==1,0], X_transform[y[:,1]==1,1], c='b', alpha=0.4)
plt.scatter(X_transform[y[:,2]==1,0], X_transform[y[:,2]==1,1], c='g', alpha=0.4)
plt.legend(['Class 1', 'Class 2', 'Class 3'])
plt.title('Projected data along first two dimensions')
plt.subplot(132)
plt.imshow(abs_diff)
plt.colorbar()
plt.title('Visualization of absolute differences')
plt.subplot(133)
ax = plt.hist(abs_diff.flatten())
plt.title('Histogram of absolute differences')
fig.subplots_adjust(wspace=.3)
ロイターデータセット ガウシアン・ランダム・プロジェクション
ロイターのデータセットにガウスランダム射影を適用してみましょう。
以下のコードでは、異なる eps 値に対して for ループを実行します。
johnson_lindenstrauss_min_dimが返す最小安全次元が実際のデータ次元よりも小さい場合、GaussianRandomProjectionのfit_transform()メソッドが呼び出されます。
そして、create_visualization()関数が呼び出され、その値のeps` に対する可視化画像が作成されます。
また、反復処理ごとに、平均絶対差分とガウスランダム射影によって得られた次元削減率が格納されます。
reduction_dim_gauss = []
eps_arr_gauss = []
mean_abs_diff_gauss = []
for eps in np.arange(0.1, 0.999, 0.2):
min_dim = johnson_lindenstrauss_min_dim(n_samples=total_points, eps=eps)
if min_dim > X.shape[1]:
continue
gauss_proj = GaussianRandomProjection(random_state=0, eps=eps)
X_transform = gauss_proj.fit_transform(X)
dist_raw = euclidean_distances(X)
dist_transform = euclidean_distances(X_transform)
abs_diff_gauss = abs(dist_raw - dist_transform)
create_visualization(X_transform, y, abs_diff_gauss)
plt.suptitle('eps = ' + '{:.2f}'.format(eps) + ', n_components = ' + str(X_transform.shape[1]))
reduction_dim_gauss.append(100-X_transform.shape[1]/X.shape[1]*100)
eps_arr_gauss.append(eps)
mean_abs_diff_gauss.append(np.mean(abs_diff_gauss.flatten()))
差の絶対値行列とそれに対応するヒストグラムの画像から、ほとんどの値がゼロに近いことがわかります。
したがって、大多数の点のペアは、低次元空間において実際の距離を維持し、データの元の構造を保持しています。
変換の質を評価するために、平均絶対差を eps に対してプロットしてみましょう。
また、epsの値が高いほど、次元の減少が大きいことを意味する。
また、2番目のサブプロットで、削減率対epsをプロットしてみましょう。
fig,ax = plt.subplots(nrows=1, ncols=2, figsize=(10,5))
plt.subplot(121)
plt.plot(eps_arr_gauss, mean_abs_diff_gauss, marker='o', c='g')
plt.xlabel('eps')
plt.ylabel('Mean absolute difference')
plt.subplot(122)
plt.plot(eps_arr_gauss, reduction_dim_gauss, marker = 'o', c='m')
plt.xlabel('eps')
plt.ylabel('Percentage reduction in dimensionality')
fig.subplots_adjust(wspace=.4)
plt.suptitle('Assessing the Quality of Gaussian Random Projections')
plt.show()
ガウスランダム射影を用いると、データの次元を99%以上削減できることがわかります。
しかし、その代償として、データの歪みが大きくなっています。
ロイターデータセット スパースランダム射影
Sparse Random Projectionでも同様の比較ができる。
reduction_dim_sparse = []
eps_arr_sparse = []
mean_abs_diff_sparse = []
for eps in np.arange(0.1, 0.999, 0.2):
min_dim = johnson_lindenstrauss_min_dim(n_samples=total_points, eps=eps)
if min_dim > X.shape[1]:
continue
sparse_proj = SparseRandomProjection(random_state=0, eps=eps, dense_output=1)
X_transform = sparse_proj.fit_transform(X)
dist_raw = euclidean_distances(X)
dist_transform = euclidean_distances(X_transform)
abs_diff_sparse = abs(dist_raw - dist_transform)
create_visualization(X_transform, y, abs_diff_sparse)
plt.suptitle('eps = ' + '{:.2f}'.format(eps) + ', n_components = ' + str(X_transform.shape[1]))
reduction_dim_sparse.append(100-X_transform.shape[1]/X.shape[1]*100)
eps_arr_sparse.append(eps)
mean_abs_diff_sparse.append(np.mean(abs_diff_sparse.flatten()))
ランダム投影の場合、差の絶対値の行列はガウス投影のものと似ているように見えます。
しかし、最初の2次元の投影データは、多くの点が座標軸上に写像され、より興味深いパターンを持っています。
また、パラメータ eps の値を変えて、差の絶対値の平均と次元の減少率をプロットしてみましょう。
fig,ax = plt.subplots(nrows=1, ncols=2, figsize=(10,5))
plt.subplot(121)
plt.plot(eps_arr_sparse, mean_abs_diff_sparse, marker='o', c='g')
plt.xlabel('eps')
plt.ylabel('Mean absolute difference')
plt.subplot(122)
plt.plot(eps_arr_sparse, reduction_dim_sparse, marker = 'o', c='m')
plt.xlabel('eps')
plt.ylabel('Percentage reduction in dimensionality')
fig.subplots_adjust(wspace=.4)
plt.suptitle('Assessing the Quality of Sparse Random Projections')
plt.show()
2つのグラフの傾向は、ガウス射影の場合と似ています。
しかし、Gaussian Projection の平均絶対差は Random Projection のそれよりも小さい。
結論
本書では、主に2種類のランダム射影法、すなわち、ガウス型ランダム射影法とスパース型ランダム射影法について、その詳細を説明した。
また、これらの手法の数学的な基礎となるJohnson-Lindenstraussのレンマの詳細について紹介しました。
次に、Pythonの sklearn ライブラリを用いて、この方法を用いてデータを変換する方法を紹介した。
また、実際にロイター・コーパス第1巻のデータセットを用いて、2つの方法を説明した。
我々は、読者が非常に高次元のデータセットを扱う際に、前処理段階で教師あり分類や回帰タスクでこの方法を試してみることを推奨する。