次元削除 ( t-SNE ) - puyokwの日記

　今回は、kaggle のOtto Group Production Classification Challenge の上位の方々が次元削除の手法としてt-SNE(t-distributed stochastic neighbor embedding) を使用されていたので調べてみようと思いました。個人的には、pca(主成分分析) ぐらいしか思い付かなかったのですが、それぞれ比較しながら見ていきます。
t-sne の詳細についてこちらを参考にするといいかと思います。
http://jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf
こちらに書かれているようにt-SNE は高次元のものを2 または3 次元に写像するように作られています。とりあえず、R のtsne package を試してみます。(あとでより高速なRtsne package を用います)

library(tsne)
colors = rainbow(length(unique(iris$Species)))
names(colors) = unique(iris$Species)
set.seed(1)
iris.tsne = tsne(iris[,1:4], max_iter=200) # 時間短縮のため max_iter=200
plot(iris.tsne, t='n', main="tsne")
text(iris.tsne, labels=as.integer(as.factor(iris$Species)), col=colors[iris$Species])

# PCA と比較
dev.new()
iris.pca = princomp(iris[,1:4])$scores[,1:2]
plot(iris.pca, t='n', main="pca")
text(iris.pca, labels=as.integer(as.factor(iris$Species)),col=colors[iris$Species])

これを実行すると次のような図を得ます。
まず、t-sne
f:id:puyokw:20150620094617j:plain
次に、pca
f:id:puyokw:20150620234024j:plain
これを見た感じだとpca の方が良さそうです。
　次に、先ほどの例ではt-SNE の良さがあまり分からなかったので、別の例として手書き文字(数字)の認識を例としてみていきたいと思います。t-SNE とpca を比較したスクリプトがkaggle の"script of the week" で取り上げていただきました！ので、そちらにリンクを張っておきます。
https://www.kaggle.com/puyokw/digit-recognizer/clustering-in-2-dimension-using-tsnewww.kaggle.com
結果はこのようになっています。
t-sne
f:id:puyokw:20160522131238p:plain
pca
f:id:puyokw:20160522131256p:plain
こちらでは、t-SNE がかなりきれいにクラス分類されているのが分かります。ただこの場合でも、pca はダメという分けではなく、単にどのような処理をしたいかに合わせてpca とt-SNE を選択する必要があるということです。

　R にはt-SNE の高速版のRtsne package があり、これは主成分分析をしてからt-SNE を実行します(prcomp を使用しています)。
　Rtsne についての論文はこちらになります。
http://arxiv.org/pdf/1301.3342v2.pdf
上記のページが意外と重かったので、アブストが書かれているページにもリンクしておきます。
[1301.3342] Barnes-Hut-SNE
ここに書かれているように、この方法は Barnes-Hut-SNE と呼ばれていてこのアルゴリズムではO(nlogn) で実行できます。元のアルゴリズムはO(n^2) です。これはvantage-point trees やBarnes-Hut のアルゴリズムを使用しています。　使い方はtsne とほぼ同じ感じです。

library(Rtsne)
set.seed(1) # 再現性の確保
# verbose=TRUE で途中経過が出力されます
iris.tsne <- Rtsne(as.matrix(iris[,1:4]), check_duplicates = FALSE, verbose=TRUE)
colors = rainbow(length(unique(iris$Species)))
plot(iris.tsne$Y, t='n', main="Rtsne")
text(iris.tsne$Y, labels=as.integer(as.factor(iris$Species)), col=colors[iris$Species])

　Rtsne のパラメータ中にtheta(=0.5 :default) が含まれています(上記のコードには入れていません)が、これを0 に近づけるほど精度は良くなりますがその代わりに実行時間が長くなります。

追記(2016/06/04)
一応、python での例も載せておきます。

import numpy as np
import pandas as pd
from sklearn.manifold import TSNE
from sklearn import datasets
import matplotlib.pyplot as plt

# import iris data 
iris = datasets.load_iris()
X = iris.data
Y = iris.target

model = TSNE(n_components=2, perplexity=50, n_iter=500, verbose=3, random_state=1)
X = model.fit_transform(X)

# Plot the points
plt.figure(2, figsize=(8, 6))
plt.clf()
plt.scatter(X[:, 0], X[:, 1], c=Y, cmap=plt.cm.Paired)
plt.xlabel('tsne1')
plt.ylabel('tsne2')
plt.show()

追記(2016/05/23)
t-sne の利点:
他の視覚化よりも綺麗に図示されることが多い。(特にクラス分類)

t-sne の欠点:
計算に非常に時間がかかる
メモリの消費量が多い(特に、python)

kaggle における実例：
otto: Otto Group Product Classification Challenge | Kaggle
digit recognizer(上記のもの): Digit Recognizer | Kaggle
spring leaf marketing response(コードのみ): Solution Sharing - Springleaf Marketing Response | Kaggle

こちらのサイトに有名なデータセットに対するいくつかの例がExmaples の項目に載っています。t-SNE – Laurens van der Maaten

追記(2015/08/02)：実際に、t-SNE で3次元にしたものと元のデータを結合してrandomForest などを用いたコード(kaggle のdigit recognizerで用いたもの)をgithub 上にupload しました。精度は若干向上します。
GitHub - puyokw/kaggle_digitRecognizer: Scripts for digit Recognizer in kaggle