t-SNE を用いた次元圧縮方法のご紹介

こんにちは。データ分析部の越水です。

以前、 弊社ブログ記事
高次元データの可視化の手法をSwiss rollを例に見てみよう
にて、高次元データの可視化手法を複数ご紹介いたしました。
今回は、 Kaggle などのデータコンペで最近注目を集めている可視化手法として、
t-SNE をご紹介したいと思います。

t-SNE は、高次元データの次元を圧縮するアルゴリズムであり、特に高次元データを可視化する際に有用です。
高次元データの関係性をうまく捉えられるという特徴があり、
最近 Kaggle などのデータコンペでよく用いられるようになりました。

t-SNE はどんな仕組みなのか?

まず、 t-SNE のアルゴリズムを紹介したいと思います。
厳密さよりも分かりやすさを重視した説明なので、詳細を知りたい方は原論文をご覧ください。

2点間の「近さ」を確率分布で表現する

このアルゴリズムの一番の特徴は、 2 点間の「近さ」を確率分布で表現するところにあります。

t-sneのイメージ

例えば、点 x_i とそれ以外の全ての点との距離を考えましょう。
t-SNE では、基準となる点 x_i を中心とした正規分布を考え、
距離を測りたい点 x_j が抽出される確率密度を、点 x_i から見た点 x_j の近さ p_{j|i} とします。
これにより、x_i の近くにある点ほど p_{j|i} は大きくなり、遠くにある点ほど p_{j|i} は小さくなります。
数式で表すと、条件付き確率 p_{j|i} と同時確率 p_{ij} は次のように表されます。


p_{j|i} = \frac{\exp(-||x_i - x_j||^2 / 2\sigma_i^2)}{\sum_{k\neq i}\exp(-||x_i - x_k||^2 / 2\sigma_i^2)},    p_{i|i} = 0
p_{ij} = \frac{p_{j|i}+p_{i|j}}{2N}.

次に、次元圧縮後の点 y_i と点 y_j の「近さ」 q_{j|i} を考えます。これらは、次元圧縮前の点 x_i と点 x_j に対応します。
こちらも同様に確率分布で表現するのですが、
次元圧縮後の近さは正規分布ではなく自由度 1 の t 分布で考えるところがミソです。
裾の重い t 分布を用いることで、圧縮前の x_ix_j が近くないデータの場合、圧縮後の y_iy_j をより遠くに配置することが可能になります。


q_{ij} = \frac{(1+||y_i - y_j||^2)^-1}{\sum_{k\neq i}(1+||y_i - y_k||^2)^-1},    q_{ii} = 0.

圧縮前と圧縮後の確率分布の KL 情報量を最小化する

では、この圧縮後の点 y_i はどのようにして決定すればよいでしょうか?
もし、圧縮前の点 x_i と点 x_j の近さを点 y_i と点 y_j で正確に表すことができたなら、条件付き確率 p_{j|i}q_{j|i} は一致するはずです。
完璧に一致させることは難しいので、なるべく近づけるようにしましょう。
ここでは、分布間の近さを測る方法として、KL (カルバック・ライブラー)情報量を用います。
圧縮前の確率分布と圧縮後の確率分布の KL 情報量を計算し、これを最小化することを目指します。

この KL 情報量を損失関数 C とし、C が最小になるような y_i を求め、それを圧縮後の点とします。


C = \sum_{i}\sum_{j}p_{ij} \log \frac{p_{ij}}{q_{ij}}

以上が、 t-SNE のアルゴリズムの概要です。

t-SNE を用いて、データ可視化を行う

それでは、実際に t-SNE を実行してみましょう。

t-SNE は様々なプログラミング言語に対応したパッケージが用意されています。
R などのパッケージで実装されているのは、通常の t-SNE を高速化した Barnes-Hut t-SNE と呼ばれる手法です。

この手法は、簡単に言えば、

  • 十分に離れている 2 点間の確率を 0 と近似
  • quadtree (3 次元に圧縮する場合は Octree) を用いて空間を分割し、同じセルに含まれている点はまとめて中心点で近似

という 2 つの近似により、通常の t-SNE よりも高速かつ省メモリで実行可能な手法です。

また、t-SNE のパッケージは、デフォルトで事前に PCA (主成分分析) を実行しています。
これは、事前に 30 次元ほどに落としてから t-SNE を行うことで計算時間を節約するためであり、原論文でも推奨されているテクニックです。

今回は、t-SNE と、比較のために PCA で可視化を試みます。

データセット

http://www.cs.columbia.edu/CAVE/software/softlib/coil-20.php

今回、データセットは Coil-20 を使います。
Coil-20 は、20 種類の物体を 5 度ずつ角度を変えて撮影した画像データセットです。
画像は全て白黒であり、20 種類 × 72 = 1440 枚の画像が用意されています。
これらを 32 × 32 pixel に圧縮し、全 1024 区画のグレースケールを取得します。

この 1440 枚、 1024 次元のデータに対し、可視化を試みます。

PCA の実行結果

まず、PCA を実行した結果は下記のとおりです。

PCAの結果

散布図を見ると、各物体が混ざってしまっていて、
まったく分類できていないことがわかります。

PCA を実行する R コードは下記のとおりです。

# Coil-20 データセットの読み込み
coil20 <- read.csv("coil20_train.csv")
# PCA の実行
d_pca <- prcomp(coil20[,-ncol(coil20)], scale=TRUE)

# plot のための準備
coil20.levels <- levels(coil20$class)
coil20.levels.colors <- rainbow(length(coil20.levels))
coil20.idx <- sapply(coil20$class, function(cls){match(cls, coil20.levels)})
coil20.colors <- sapply(coil20.idx, function(idx){coil20.levels.colors[idx]})

# plot
par(mar=c(3,3,3,7))
plot(d_pca$x[,1:2], t='n', xlab='', ylab='')
text(d_pca$x[,1:2], labels=coil20.idx, col=coil20.colors)
par(xpd=T)
legend(par()$usr[2] + 0.2, par()$usr[4]
, legend=paste(as.character(seq(1,20)), coil20.levels, sep=": ")
, pch=16
, col=coil20.levels.colors
, cex=1.0)

t-SNE の実行結果

では、t-SNE を実行してみましょう。
下記のような実行結果が得られました。

t-SNEの実行結果

20 種の写真が、おおむね綺麗に分類できていることが分かります。

Coil-20 の画像データは、ひとつの物体を5度ずつ角度を変えて撮影したものです。
正面から撮った写真と、 360 度近くの回転をして撮った写真は、当然似た写真になります。
t-SNE では、そういった構造をループ状に表しており、
多次元空間での構造を低次元空間に表すことができていると考えられます。
なかなか面白い結果ですよね。

よく見ると、右上あたりに、いくつかの線状に連なっているものがありますね。。。
これらは、3 種のミニカーの写真のようです。

minicars

実際に写真を見ればわかりますが、
同じ車種で異なる角度のミニカーより、異なる車種でも同じ角度のミニカーのほうが、
類似した写真であるため、t-SNE では近い空間に配置されているというわけです。

t-SNE を実行する R コードは下記のとおりです。
上述の通り、t-SNE は様々なプログラミング言語に対応したパッケージが用意されており、
今回は {Rtsne} パッケージを使用しました。

実行は非常に簡単です。
{Rtsne} パッケージを読み込み、 Rtsne() 関数の引数にデータセットとオプションを指定するだけで実行できます。

# Rtsne パッケージの読み込み
# install.packeges("Rtsne") # インストール
library(Rtsne)

# t-SNE の実行
d_tsne.coil20 <- Rtsne(coil20[,-ncol(coil20)])

# plot
par(mar=c(3,3,3,7))
plot(d_tsne.coil20$Y, t='n', xlab='', ylab='')
text(d_tsne.coil20$Y, labels=coil20.idx, col=coil20.colors)
par(xpd=T)
legend(par()$usr[2] + 0.2, par()$usr[4]
, legend=paste(as.character(seq(1,20)), coil20.levels, sep=": ")
, pch=16
, col=coil20.levels.colors
, cex=1.0)

他の手法と比較するとどうなのか

原論文では、 Coil-20 データセットに対して Isomap や LLE など他の次元削減手法を適用した結果が掲載されています。
その結果を見ると、 t-SNE 以外はうまく可視化できていないことがわかります。

Isomap や LLE などの手法は、Swissroll のようなデータがつながっている構造を捉えるのは得意ですが、Coil-20 のようないくつかの部分に分かれているデータには不向きのようです。
t-SNE ではデータが分かれている構造をしていても有効なので、複数のクラスタがあるデータを可視化したいときには便利な手法であるといえるでしょう。

原論文の Supplemental Material には、
さらに他の手法と比較した結果も掲載されているので、興味のある方は是非ご覧ください。

おわりに

以上、t-SNE の紹介および実行結果でした。
高次元データの関係性をうまく捉えることができる手法であることをご理解いただけたと思います。

注意点として、t-SNE で圧縮する次元は、 2・3 次元が推奨されています。
4 次元や 5 次元でも計算できないことはないのですが、計算コストがかなり高くなってしまうので実用的ではありません。
そのため、 2・3 次元以外の次元に圧縮したい場合は別のアルゴリズムを用いるべきです。
しかし、t-SNE の主な用途は可視化であるので、特に大きな問題ではないかと思われます。

高次元データを可視化する際には、多様体学習に加え、 t-SNE を是非お試しください。

また、多様体学習と t-SNE の得意領域はデータのつながり度合いの構造によって決まりそうですが、高次元データにおいてその構造はどのように解明できるのでしょうか?
このような高次元データの構造を解明する方法の一つとして、「トポロジカルデータアナリシス(TDA)」という分野を用いる方法があります。
こちらについても、後日 弊社ブログにてご紹介させていただく予定ですので、お楽しみに!

参考文献

  • L.J.P. van der Maaten and G.E. Hinton. Visualizing High-Dimensional Data Using t-SNE. Journal of Machine
    Learning Research
    , 9(Nov):2431–2456, 2008.
  • L.J.P. van der Maaten. Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research 15(Oct):3221-3245, 2014.

koshimizu

データ分析部 koshimizuです。RとSQLを用いて業務に取り組んでおります。トピックモデル勉強会開催中です。→ http://topicmodel.connpass.com/