PCA와 t-SNE 비교
PCA와 t-SNE 비교
1. 개념
PCA(Principal Component Analysis)와 t-SNE(t-Distributed Stochasitc Neighbor Embedding)은 모두 차원축소(Dimensionality Reduction) 기법임. 차원축소란 매우 많은 feature로 구성된 다차원 데이터 세트의 차원을 축소해 새로운 차원의 데이터 세트를 생성하는 것을 말함.
2. 사용하는 이유
일반적으로 feature가 많을 수록 데이터 간 거리가 기하급수적으로 증가하기 때문에 sparse 구조를 가지게 되어 모델의 신뢰도가 떨어지는 것을 방지하기 위함.
3. 계산방법
PCA는 이전 post 참고. t-SNE는 고차원의 데이터를 2차원의 embedding vector를 학습함으로써, 2차원의 지도로 표현함. 때문에 vector visualiztion을 위해 자주 이용됨. t-SNE는 고차원 공간에서 유사한 두 벡터가 2차원 공간에서도 유사하도록(데이터간 neighbor structure를 보존하도록) 원 공간에서의 점들 간 유사도를 보존하면서 차원을 축소함.
3.1 절차
1) 고차원의 원 공간에서 데이터 간 유사도$p_{ij}$를 정의함. 2) 저차원의 임베딩(축소) 공간에서 데이터 간 유사도$q_{ij}$를 정의함. 3) 저차원의 공간이 고차원 공간에 가까워지도록 gradient descent로 계산해 데이터를 변환함. —
1) 고차원의 원 공간에서 데이터 간 유사도$p_{ij}$를 정의함.
| $p_{ij}$를 정의하기 위해 점 $x_i$에서 $x_j$로의 유사도인 $p_{j | i}$를 정의해야함. 그래서 먼저 기준점 $x_i$에서 다른 모든 점들과의 유클리드 거리 $ | x_i-x_j | $를 계산함. 그리고 이 거리를 기반으로 기준 점과 다른 점들 간의 거리가 얼마나 가까운지를 확률로 나타냄. 확률로 나타내는 방법은 점과 점의 거리를 $\sigma_i$로 나누고 negative expoential을 취하면 $\exp(- | x_i-x_j | ^2/2\sigma_i^2)$이 됨. 그리고 모든 점들과의 거리의 합은 $\exp(- | x_i-x_k | ^2/2\sigma_i^2)$으로 각각을 나눠주면 아래와 같은 확률 형식이 됨. |
| $p_{j | i}$=$\frac{\exp(- | x_i-x_j | ^2/2\sigma_i^2)}{\sum_{k\ne i}\exp(- | x_i-x_k | ^2/2\sigma_i^2)}$ |
| 여기서 $\sigma_i$는 모든 점마다 다르게 정의 되는데 t-SNE가 안정적인 학습 결과를 가지게 되는 부분임. 결과적으로 점과 점사이의 거리가 멀어서 분모가 작아지게 되면 $p_{j | i}$도 작아지게 되고 점과 점사이가 가까우게 되면 유사도가 커져서 유사도가 커지는 방향으로 점들이 이동하는 모델임. 점 간의 유사도를 대칭적으로 만들기 위하여 $p_{j | i}$와 $p_{i | j}$의 평균으로 두 점간의 유사도를 정의함. 그리고 $n$개의 점으로 나눠주면 모든 점들간의 유사도의 합이 1이 되도록 만들 수 있고 확률의 개념을 사용할 수 있는 것임. 따라서 원 공간에서의 유사도 $p_{ij} = \frac{p_{i | j}+p_{j | i}}{2n}$으로 정의가능함. |
2) 저차원의 임베딩(축소) 공간에서 데이터 간 유사도$q_{ij}$를 정의함.
저차원 공간에서의 유사도 $q_{ij}$도 고차원 공간에서의 유사도 $p_{ij}$와 동일하게 확률로 나타낼 수 있도록 $\sum_{ij}q_{ij}=1$로 정의함. 동일하게 두 점간의 거리가 작을수록 유사도는 큰 값을 갖도록 두 점간의 거리에 역수를 취하여 유사도로 이용함. 추가적으로 안정적인 역수를 얻기 위해 거리 값에 1을 더하고 역수를 취해주면 $(1+|y_i-y_j|^2)^{-1}$이 되고 이 값은 확률 분포인 t-분포가 됨. 또한 이도 모든 점들간의 합으로 나눠줌으로써 아래와 같이 유사도를 정의함
$q_{ij}=\frac{(1+|y_i-y_j|^2)^{-1}}{\sum_{k\ne l}(1+|y_k-y_l|^2)^{-1}}$
3) 저차원의 공간이 고차원 공간에 가까워지도록 gradient descent로 계산해 데이터를 변환함.
t_SNE는 $p_{ij}$에 가장 가깝도록 $q_{ij}$를 학습함. 이는 정확히 $q_{ij}$를 정의하는 $y_i, y_j$를 학습하는 것이고, 결국에는 정답지인 원 공간의 $p_{ij}$를 보면서 $y_i, y_j$를 이동하는 것과 같음. 학습에는 경사하강법을 이용하며, $q_{ij}$와 $p_{ij}$의 비용함수가 최소가 되는 방향으로 $y$의 점들을 이동함. 이동량은 아래와 같음
$\frac{\delta C}{\delta y_i}=\sum_j(p_{ij}-q_{ij})(y_i-y_j)\frac{1}{1+|y_i-y_j|^2}$
4. 파이썬 코드 구현
Iris data set으로 비교
# Import required libraries
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.decomposition import PCA
from sklearn.manifold import TSNE
# Load the iris dataset
iris = load_iris()
# Convert data to dataframe
iris_df = pd.DataFrame(iris.data, columns=iris.feature_names)
Original data set
# Visualize the original data
plt.scatter(iris_df['sepal length (cm)'], iris_df['sepal width (cm)'], c=iris.target)
plt.xlabel('sepal length (cm)')
plt.ylabel('sepal width (cm)')
plt.title('Iris Dataset')
plt.show()
/Figure_1.png)
Apply PCA
# Apply PCA
pca = PCA(n_components=2)
iris_pca = pca.fit_transform(iris.data)
# Visualize PCA output
plt.scatter(iris_pca[:,0], iris_pca[:,1], c=iris.target)
plt.xlabel('PC 1')
plt.ylabel('PC 2')
plt.title('PCA Output')
plt.show()
/Figure_2.png)
Apply t-SNE
# Apply t-SNE
tsne = TSNE(n_components=2)
iris_tsne = tsne.fit_transform(iris.data)
# Visualize t-SNE output
plt.scatter(iris_tsne[:,0], iris_tsne[:,1], c=iris.target)
plt.xlabel('t-SNE 1')
plt.ylabel('t-SNE 2')
plt.title('t-SNE Output')
plt.show()
/Figure_3.png)
4. PCA와 t-SNE 비교
t-SNE
- t-SNE는 local structure와 점 들간 관계는 보존하면서 저차원 공간(2차 평면)에 고차원 데이터를 시각화 하는데 특출남. 그래서 데이터분석에서 데이터 시각화나 데이터 탐색에 주로 사용됨.
- 마찬가지로 고차원에서 식별하기 어려운 군집이나 패턴을 찾는데 유용함.
- 복잡한 데이터와 비선형 구조의 데이터에서 잘 작동함.
PCA
- PCA는 데이터의 variability를 잘 보존하면서 거대 데이터 세트의 차원을 축소하기 위해 대중적이고 넓게 사용됨.
- PCA도 패턴이나 데이터에서 변수 간의 관계를 찾는데 유용함.
- t-SNE와 비교하여 상대적으로 빠르고 컴퓨터 비용도 효율적임.
5. 생각해보기
Q1. PCA와 비교하여 t-SNE의 계산비용이 많이 드는 이유는?
- t-SNE는 고차원의 데이터 간 유사도와 저차원의 데이터 간 유사도를 계산하기 위해서는 $n^2$번의 거리 계산을 수행해야됨. 또한 이상치의 영향력을 줄이기 위해 모든 점마다 $\sigma_i$를 다르게 정의하는 것도 작지만 한 몫함.
Q2. t-SNE의 많은 계산 비용에 대한 대안은?
- Barnes-hut tree라는 vector indexing 방법을 사용함. 구체적인 방법은 원 공간을 여러 개의 집단으로 나누고 t-SNE처럼 점과 점간의 거리가 아닌 집단과 집단의 거리를 계산하여 점이 아닌 집단을 움직임. 사이킷런의 t-SNE는 이 방식이 적용돼있음.
Q3. Perplexity란?
-
t-SNE는 임베딩 과정에서 nearest 점들과 그렇지 않은 점들을 칼처럼 양분하진 않음. 대신 유사도 $(p_{j i})$ 계산해 거리에 반비례하여 영향력을 정의함. 그리고 perplexity는 어느 범위까지 영향력을 미치게할지 정의함. - Perplexity는 $2^{entropy}$로 정의됨. 통계학에서 entropy는 확률분포의 불확실성을 나타내는 척도임. 이 불확실성의 척도는 확률분포에 대한 정보량의 기대값으로 표현됨. 즉, 어떠한 사건이 일어날 확률에 대한 불확실성이 클 수록 entropy가 크다고 볼 수 있음. 그리고 $\sigma$ 를 어떤 값으로 설정하느냐에 따라 $p_{j|i}$ 의 perplexity가 결정됨.
$entropy(p_x)=\sum -p_{xi}log(p_{xi})$
대체로 Perplexity가 매우 작으면 locality가 많이 반영되어 왜곡된 공간이 학습되고 거리 정보가 많이 보존되지만 집단을 구분하기 어렵고, 조금씩 높아질 수록 거리정도도 어느 정도 보존되면서 집단을 구분할 수도 있음. 너무 값이 커지면 점들 사이에 거리 정보가 보존되지 않음.
P.S. 이전에 LDA 공부할 때도 Perplexity가 있었는데 따로 포스팅하자
Q4. 모든 점들에 대해 거리를 계산할 때 사용되는 수식은?
- 기본적으로 앞서 절차1)에서 말했던 것처럼 유클리드 거리르를 사용한다. 다만 bag-of-words 모델과 같이 Sparse vector로 표현된 데이터라면 Cosine이나 Jaccard가 더 적절할 수 있다.
참고
t-SNE origin, 2008
t-SNE 관련 web blog1
t-SNE 관련 web blog2
t-SNE 관련 web blog3
Leave a comment