本記事は、当社オウンドメディア「Doors」に移転しました。

約5秒後に自動的にリダイレクトします。

当社データサイエンティストが、高次元のデータをできる限り重要な情報を保持したまま低次元データに変換する「次元削減手法」について代表的な3つの手法をご紹介します。また、実際に画像データを用いて手法を試してみましたので、その結果もご紹介します！

こんにちは。アナリティクスサービス部の西條です。

今回は、高次元データを可視化する際に使用する手法の1つである次元削減についてご紹介します。

次元削減とは
次元削減の手法
- PCA
- t-SNE
- UMAP
各手法の比較
おわりに
参考文献

次元削減とは

次元削減とは、高次元のデータをできる限り重要な情報を保持したまま低次元データに変換する手法のことです。我々が取り扱うデータの中には画像や音声といった高次元データが存在しますが、これらを直接可視化して特徴把握をすることは困難です。そこで、高次元データを人が理解できる次元数（主に2次元や3次元）まで落とし、可視化することによってデータの特徴把握をすることがあります。上記は可視化用途での次元削減について説明しましたが、他にもモデルに使用する特徴量の生成やデータ圧縮によるメモリ使用量の削減などの用途に使用されています。

次元削減の手法

次元削減の手法は色々とありますが、今回は代表的な手法である「PCA」「t-SNE」「UMAP」の3つについてご紹介します。

PCA

PCA（主成分分析）は、学習データ $x_i = (x_{i1}, ..., x_{id})^T (i = 1, ..., N)$ の分散が最大になる方向への線形変換を求める手法です。次元削減の手法としては最も一般的な手法かと思います。

データ行列を $X = (x_1, ..., x_N)^T$ 、平均ベクトル $\bar{x} = \frac{1}{N} \sum_{i=1}^N x_i$ を引き算したデータ行列を $\bar{X} = (x_1-\bar{x}, ..., x_N-\bar{x})^T$ とすると、共分散行列は以下の式で定義できます。

$\displaystyle \sum = \rm{Var} \it{\{\bar{X}\}} = \frac{\rm{1}}{\it{N}} \bar{X}^T \bar{X}$

$N$ 個のデータ $x_i-\bar{x}$ を係数ベクトル $a_j = (a_{j1}, ..., a_{jd})^T (j = 1, ..., d)$ を用いて線形変換すると、以下の式が得られます。

$\displaystyle s_j = (s_{1j}, ..., s_{Nj})^T = \bar{X}a_j$

すなわち、 $s_j$ の分散が最大になるような係数ベクトル $a_j$ を $\lVert a_j \rVert = 1$ という制約下で求めれば良いということになります。 $s_j$ の分散は以下の式で表せます。

$\displaystyle \rm{Var}\{\it{s_j}\} = \frac{\rm{1}}{\it{N}} s_j^T s_j = \frac{\rm{1}}{\it{N}} (\bar{X}a_j)^T (\bar{X}a_j) = a_j^T \rm{Var} \it{\{\bar{X}\}} a_j$

$\rm{Var}\lbrace\it{s_j}\rbrace$ を最大化する係数ベクトル $a_j$ をラグランジュの未定乗数法で求めます。ラグランジュ未定乗数を $\lambda$ としたとき、ラグランジュ関数は以下の式で表せます。

$\displaystyle E(a_j) = a_j^T \rm{Var} \it{\{\bar{X}\}} a_j - \lambda(a_j^Ta_j - 1)$

$a_j$ で微分して0とおくと、以下の式が得られます。

$\displaystyle \rm{Var} \it{\{\bar{X}\}a_j = \lambda a_j}$

つまり、元データの共分散行列の固有値問題を解くことで、分散が最大となる射影ベクトルを得ることができます。

t-SNE

t-SNE（t-distributed Stochastic Neighbor Embedding）は主に高次元データを低次元（2次元や3次元）に圧縮して可視化する際に用いられる手法です。高次元空間上で近い点が圧縮した低次元空間でも近くなるように圧縮します。ただし、計算コストが大きいため4次元以上への圧縮は不向きです。t-SNEはSNE （Stochastic Neighbor Embedding）という手法の発展系なので、まずSNEについて説明します。

SNEでは高次元空間におけるデータ点 $x_i$ とデータ点 $x_j$ の類似度を、ユークリッド距離から計算される条件付き確率として表します。

$\displaystyle p_{j|i} = \frac{\exp(-\lVert x_i-x_j \rVert^2 / 2\sigma_i^2)}{\sum_{k \neq i} \exp(-\lVert x_i-x_k \rVert^2 /2\sigma_i^2)}$

一方で、低次元空間に圧縮後のデータ点 $y_i$ とデータ点 $y_j$ の類似度を同様にユークリッド距離から計算される条件付き確率として表します。こちらでは標準偏差を $\frac{1}{\sqrt{2}}$ と固定します。

$\displaystyle q_{j|i} = \frac{\exp(-\lVert y_i-y_j \rVert^2)}{\sum_{k \neq i} \exp(-\lVert y_i-y_k \rVert^2)}$

低次元空間に圧縮後の $y_i$ と $y_j$ が、高次元空間の $x_i$ と $x_j$ の類似度を正しく再現できているならば、条件付き確率 $p_{j|i}$ と $q_{j|i}$ は同じ値になるはずです。したがってSNEでは、全てのデータ点におけるカルバック・ライブラー情報量の和を最小化します。

$\displaystyle{} C = \sum_i KL(P_i \lVert Q_i) = \sum_i \sum_j p_{j|i} \log \frac{p_{j|i}}{q_{j|i}}$

以上がSNEのアルゴリズムになります。しかし、SNEの問題点として以下の2つが挙げられます。

目的関数の最適化が難しい
Crowding問題

そこでt-SNEでは、1についてはSNEの対称化、2についてはt分布の導入を行うことでこれらの問題を解決しています。

目的変数の最適化

目的関数の最小化は勾配降下法で行い、以下のような式になります。

$\frac{\delta C}{\delta y_i} = 2 \sum_j (p_{j|i}-q_{j|i}+p_{i|j}-q_{i|j})(y_i-y_j)$

ここで、SNEの対象化を行います。 $p_{ij} = \frac{(p_{j|i} + p_{i|j})}{2n}$ として、条件付き確率から同時確率を導入することで、

$\frac{\delta C}{\delta y_i} = 4 \sum_j (p_{ij}-q_{ij})(y_i-y_j)$

と勾配の計算をシンプルにすることが可能です。
Crowding問題

多次元のデータを低次元に射影する際には、様々な問題が生じます。例えば3次元における正四面体の頂点はいずれも等距離な関係にありますが、2次元上にマッピングした際に等距離で表現することはできません。これと同様に一般的に次元が増加すると、ある点から等間隔な距離に位置する点は増加します。

この問題を解決するために、低次元空間での類似度表現の際には、正規分布よりも裾野の広い自由度1のt分布を用います。高次元での類似度を正規分布で、低次元での類似度をt分布で表現することで、ある点から遠い点が低次元へのマッピング後により遠くなる、という現象を正しく可視化に反映させることが可能となります。

以上がt-SNEの概要となります。より詳細について興味がある方は、原論文も合わせてご確認いただければと思います。

UMAP

UMAP（Uniform Manifold Approximation and Projection）は2018年に提案された比較的新しい手法で、t-SNEと同様に、元の特徴空間上で近い点が圧縮後にも近くなるように圧縮される手法です。t-SNEよりも実行時間が高速であると言われており、4次元以上への圧縮も可能です。

UMAPは代数トポロジーとリーマン幾何学の理論が元になっているアルゴリズムです。fuzzy simplicial setという概念を利用して高次元データをグラフ化し、低次元で作成したグラフとの類似をクロスエントロピーを用いて最適化しています。アルゴリズムの詳細については、原論文やumap 0.5 documentationなどが参考になるかと思いますので、興味がある方はこちらも合わせてご確認いただければと思います。

各手法の比較

今回はsklearnにある手書き数字の画像データセットを使用して各手法を試してみようと思います。このデータは手書き数字0～9の8×8画像（64次元）が合計で1797枚入っているデータセットとなっています。

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_digits

digits = load_digits()
X, y = digits.data, digits.target

先ほど紹介した3つの手法を用いて2次元に次元削減してみます。PCAとt-SNEはそれぞれsklearnに存在します。UMAPはpipでumap-learnをインストールする必要があります。

# PCA
from sklearn.decomposition import PCA

pca = PCA(n_components=2, random_state=0)
X_reduced_pca = pca.fit_transform(X)


# t-SNE
from sklearn.manifold import TSNE

tsne = TSNE(n_components=2, random_state=0)
X_reduced_tsne = tsne.fit_transform(X)


# UMAP
!pip install umap-learn
import umap
from scipy.sparse.csgraph import connected_components

umap = umap.UMAP(n_components=2, random_state=0)
X_reduced_umap = umap.fit_transform(X)

各手法で次元削減したものを可視化してみます。

# 可視化
Figure = plt.figure(figsize=(24, 7))
ax1 = Figure.add_subplot(1,3,1)
ax2 = Figure.add_subplot(1,3,2)
ax3 = Figure.add_subplot(1,3,3)

ax1.scatter(X_reduced_pca[:, 0], X_reduced_pca[:, 1],
            c=y, cmap='jet', alpha=0.5)
ax2.scatter(X_reduced_tsne[:, 0], X_reduced_tsne[:, 1],
            c=y, cmap='jet', alpha=0.5)
ax3.scatter(X_reduced_umap[:, 0], X_reduced_umap[:, 1],
            c=y, cmap='jet', alpha=0.5)

ax1.set_title("PCA")
ax2.set_title("t-SNE")
ax3.set_title("UMAP")

plt.show()

左からそれぞれPCA、t-SNE、UMAPで次元削減したものを可視化した結果になります。正解ラベル毎に色を変えてプロットしています。PCAではなんとなく同じラベルのものが集まってはいるものの、各ラベルが混ざっている部分が多く見られます。一方で、t-SNEやUMAPではPCAと比較してラベル毎にプロットの位置がまとまっているように見えます。高次元の情報をうまく保持しながら次元削減ができていそうです。また、UMAPの方が同じものがより近く集まっているように見えます。

次元削減＋可視化を行う場合には、可視化した結果を確認して定性的にうまくプロットできているかを評価する場合が多いです。（次元削減したデータをモデルの特徴量に使用する場合には、モデルの精度で評価できます。）次元削減手法に対して直接的な定量評価は難しいので、ここでは各手法で2次元に圧縮したベクトルを用いてk-means法でクラスタリングし、シンプルな指標であるPurity（純度）を用いて比較してみます。

Purityは、クラスタリングの評価指標の1つで、分類したクラスに最も多く含まれる正解ラベルの割合です。分類したクラスを $C = \{C_1, ..., C_i \}$ 、正解ラベルを $L = \{L_1, ..., L_j \}$ とした時に以下の式で表せます。

$\displaystyle Purity = \frac{1}{\it{N}} \sum_{i} \max_j |C_i \cap L_j |$

Purityが1のとき、全てのクラスにおいて正解ラベルが一致している状態であり、1に近いほどうまくクラスタリングできているということになります。

# 次元削減したものをk-meansでクラスタリング
from sklearn.cluster import KMeans
from sklearn import metrics

kmeans = KMeans(n_clusters = 10,
                init = 'k-means++',
                random_state = 0
                ) 

# Purityを求める関数
def purity_score(y_true, y_pred):
    contingency_matrix = metrics.cluster.contingency_matrix(y_true, y_pred)
    purity = np.sum(np.amax(contingency_matrix, axis=0)) / np.sum(contingency_matrix) 
    return purity

X_reduced = [X_reduced_pca, X_reduced_tsne, X_reduced_umap]

for i in X_reduced:
    y_kmeans = kmeans.fit_predict(i)
    purity = purity_score(y, y_kmeans)
    print(purity)

各手法で2次元に圧縮したベクトルを用いてk-means法でクラスタリングした際のPurityおよび、元データ（64次元）を直接クラスタリングした際のPurityは以下のようになりました。

手法	k-measでクラスタリングした際のPurity
PCA	0.594
t-SNE	0.943
UMAP	0.956
（参考）元データを直接クラスタリング	0.794

t-SNE, UMAPでは元データを直接クラスタリングした場合と比較してPurityが高くなっており、UMAPが最も高いPurityとなりました。高次元のデータをクラスタリングしやすいように次元削減ができていそうです。（そもそも分類することが目的であれば、深層学習などを使用した方が精度は高くなります。）

一方で、PCAでは元データを直接クラスタリングした場合と比較してPurityが低くなっており、次元削減した際に情報がかなり失われていそうです。参考までに、2次元まで累積寄与率を確認したところ0.285でした。（累積寄与率は0~1の値をとり、次元削減したベクトルが元データに対してどのくらいの情報を説明できているかという値です。）

また、各手法の実行にかかった時間は以下のようになりました。（Google Colaboratoryで実行、CPUコア数1、メモリ12.69GB）

手法	実行時間(second)
PCA	0.0353
t-SNE	28.7
UMAP	14.5

実際にやってみた結果でもt-SNEよりもUMAPの方が実行にかかる時間が短いことがわかります。

今回分析に使用した手書き画像のデータセットでは、UMAPが精度および実行時間の両方の観点から優れていそうです。ただし、分析するデータによっても変わってくると思いますので、実際に使用する場合には今回ご紹介した手法などをいくつか試してみて、最適なものを使用すると良いと思います。また今回深く取り上げませんでしたが、各手法にはハイパーパラメータが存在するのでそれらをチューニングすることでも多少良し悪しが変わる可能性があります。