次元削減とは

次元削減とは、高次元のデータをできる限り重要な情報を保持したまま低次元データに変換する手法のことです。我々が取り扱うデータの中には画像や音声といった高次元データが存在しますが、これらを直接可視化して特徴把握をすることは困難です。そこで、高次元データを人が理解できる次元数（主に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\)を\(\Vert a_j \Vert = 1\)=\( 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(-\Vert x_i-x_j \Vert^2 / 2\sigma_i^2)}{\sum_{k \neq i} \exp(-\Vert x_i-x_k \Vert^2 /2\sigma_i^2)} $$

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

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

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

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

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

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

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

1. 目的変数の最適化目的関数の最小化は勾配降下法で行い、以下のような式になります。\(\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)\)と勾配の計算をシンプルにすることが可能です。
2. 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は以下のようになりました。

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

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

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

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

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

おわりに

今回は、高次元データに対する次元削減手法についていくつかご紹介し、画像データを用いて実際に試してみました。データの質や量、分析の目的などによってどの手法が最適かというのは異なるので難しい部分もありますが、色々と試せる手法はあるのかなと思います。

当社では、データサイエンティストを積極的に募集しています。 新卒採用・キャリア採用ともに、ご応募をお待ちしています。

参考文献

• はじめてのパターン認識
• Kaggleで勝つデータ分析の技術
• Visualizing Data using t-SNE
• UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
• UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction — umap 0.5 documentation
• Understanding UMAP