t-分布随机邻域嵌入 t-SNE (t-distributed stochastic neighbor embedding)

t-SNE 是 Laurens van der Maaten 和 Geoffrey Hinton 于 2008 年共同发表的一种非线性降维方法。

基本原理

在高维空间构建一个概率分布（条件概率）拟合高维样本点之间的相对位置关系。

\[ 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)} \]

在低维空间也构建一个概率分布（条件概率）拟合低维样本点之间的相对位置关系。

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

通过学习，调整低维数据点令两个分布接近。具体而言是利用 KL 散度（Kullback-Leibler Divergence）来衡量两个分布之间的差异，通过梯度下降调整 y 使 C 变小从而实现降维。

\[ C=\sum_{i}KL(P_i\Vert Q_j)=\sum_{i}\sum_{j}p_{j|i}\log\frac{p_{j|i}}{q_{j|i}} \]

一些改进

距离度量不对称

t-SNE 使用条件分布来度量样本点之间的相对位置关系，意味着这种距离度量应该是对称的。但是观察 $p_{j|i}$ 和 $q_{j|i}$ 的公式不难发现：交换 $i$ 与 $j$ 的位置得到的条件概率并不相等！这与实际不符。一种改进的方法是使用联合概率去替代条件概率：

\[ \begin{aligned} p_{ij}&=\frac{\exp(-{\Vert x_i-x_j \Vert}^2/2\sigma_{i}^2)}{\sum_{k\neq l}\exp(-{\Vert x_k-x_l\Vert}^2 /2\sigma_{i}^2)}\\ q_{ij}&=\frac{\exp(-{\Vert y_i-y_j\Vert}^2)}{\sum_{k\neq l}\exp(-{\Vert y_k-y_l\Vert}^2)} \end{aligned} \]

但是实际上使用的是另一种更简单的方法保证对称性和归一化：

\[ \begin{aligned} p_{ij}&=p_{i|j}+p_{j|i}\\ p_{ij}&=\frac{p_{ij}}{\sum_{i}\sum_{j}p_{ij}} \end{aligned} \]

拥挤现象

从高维到低维进行转换的过程中，低维点之间的位置关系无法建模高维点之间的位置关系，即高维空间中距离较大的点在低维空间中距离会变小（距离的度量不够稳健）。解决办法是使用尾部较厚的 student-t 分布来度量低维点之间的距离，即：

\[ q_{ij}=\frac{(1+{\Vert y_i-y_j\Vert}^2)^{-1}}{\sum_{k\neq l}(1+{\Vert y_k-y_l\Vert}^2)^{-1}} \]

改进后的一般步骤

计算 $p_{ij}$

\[ \begin{aligned} 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)}\\ p_{ij}&=p_{i|j}+p_{j|i}\\ p_{ij}&=\frac{p_{ij}}{\sum_{i}\sum_{j}p_{ij}} \end{aligned} \]

随机生成低维随机数并计算 $q_{ij}$

\[ q_{ij}=\frac{(1+{\Vert y_i-y_j\Vert}^2)^{-1}}{\sum_{k\neq l}(1+{\Vert y_k-y_l\Vert}^2)^{-1}} \]

利用梯度下降法令 C 最小

\[ \begin{aligned} C&=\sum_{i}KL(P_i\Vert Q_j)=\sum_{i}\sum_{j}p_{ij}\log\frac{p_{ij}}{q_{ij}}\\ \frac{\partial C}{\partial y_i}&=4\sum_{j}(p_{ij}-q_{ij})(y_i-y_j)({1+\Vert y_i- y_j \Vert}^2)^{-1} \end{aligned} \]

特点

t-SNE 不直接采用欧式距离计算点和点之间的相邻关系，而是将数据点之间的相似度转换为概率，目的是希望数据在高维空间和低维空间的相似度接近，相似程度用KL 散度 (Kullback-Leibler Divergence)计算。
原始空间中的相似度由高斯联合概率表示。
嵌入空间的相似度由 t 分布表示（不使用正态分布是因为 t 分布在尾部比正态分布更稳健，从概率密度函数可以看出 t 分布的左右尾部比正态分布更厚）。

缺点：

速度慢，占用内存大，不适用于大样本场合。
没有保留全局结构。即，只有簇内的距离才有意义，而簇间的相似性却无法保证。
t-SNE 实际上只能嵌入 2 或 3 个维度，即仅用于可视化目的。因此很难将 t-SNE 当作一般的降维技术来使用，例如产生 10D 或 50D 的低维表示。
t-SNE 不能直接处理高维数据，通常在使用 t-SNE 前会先执行 PCA 或 Autoencoder 对高维数据作降维预处理。

Tip

正因为以上缺点，t-SNE 更适合用来做降维可视化。

t-sne 的 R 语言实现

读取数据

Code

iris.test <- iris[ , -5]
knitr::kable(head(iris.test))

Sepal.Length	Sepal.Width	Petal.Length	Petal.Width
5.1	3.5	1.4	0.2
4.9	3.0	1.4	0.2
4.7	3.2	1.3	0.2
4.6	3.1	1.5	0.2
5.0	3.6	1.4	0.2
5.4	3.9	1.7	0.4

`tsne` 包降维

Code

# 数据标准化
library(dplyr)
iris_norm <- scale(iris.test, center = TRUE, scale = TRUE) %>%
  as.data.frame()

# tsne
library(tsne)

#设置随机种子
set.seed(123)

# t-sne
tsne <- tsne(iris_norm, k = 2, perplexity = 50)

# 提取数据
iris_tsne <- data.frame(tsne)

# 添加标签
iris_tsne$label <- iris[ , 5]

# 更改列名
colnames(iris_tsne) <- c("X", "Y", "label")

# 查看前5行数据
knitr::kable(iris_tsne[1:5, ])

X	Y	label
-5.452238	-3.690582	setosa
-3.228025	-2.064315	setosa
-3.577453	-3.816123	setosa
-2.693852	-4.741877	setosa
-5.459421	-4.905469	setosa

Code

#画图
library(ggplot2)

p_tsne <- ggplot(iris_tsne, aes(x = X, y = Y, colour = label)) + 
  geom_point(size = 2) +
  xlab("tsne_1") +
  ylab("tsne_2")

p_tsne <- p_tsne + 
  theme(
    panel.grid.major = element_blank(),
    panel.grid.minor = element_blank(),
    legend.title = element_blank(),
    panel.border = element_blank(),
    axis.line.x = element_line(color = "black", size = 0.5),
    axis.line.y = element_line(color = "black", size = 0.5),
    panel.background = element_blank()
  )

p_tsne

`Rtsne` 包降维

Code

library(Rtsne)

# 必须要去除重复值
iris <- unique(iris) 

# 设置随机种子
set.seed(123)

# 数据标准化
iris_norm <- scale(iris[ , -5], center = TRUE, scale = TRUE) %>%
  as.data.frame()

# tsne
tsne <- Rtsne(iris_norm, pca = FALSE, theta = 0)
names(tsne)
##  [1] "N"                   "Y"                   "costs"              
##  [4] "itercosts"           "origD"               "perplexity"         
##  [7] "theta"               "max_iter"            "stop_lying_iter"    
## [10] "mom_switch_iter"     "momentum"            "final_momentum"     
## [13] "eta"                 "exaggeration_factor"

其中 tsne$Y 是 t-sne 降维结果。

Code

iris_tsne <- tsne$Y %>% as.data.frame() %>% cbind(iris$Species)
colnames(iris_tsne) <- c("X", "Y", "label")

Code

p_tsne <- ggplot(iris_tsne, aes(x = X, y = Y, colour = label)) + 
  geom_point(size = 2) +
  xlab("tsne_1") +
  ylab("tsne_2") +
  theme_bw()

p_tsne

更多 t-SNE 可视化详见：https://datavizpyr.com/how-to-make-tsne-plot-in-r/

--- title: "非线性降维t-SNE" author: "Rui" date: "2023-5-28" categories: [R, tsne] image: "QueenVictoriaAgave.jpg" format: html: code-fold: true code-tools: true --- ```{r setup, include = FALSE} # 设置默认参数 knitr::opts_chunk$set( echo = TRUE, fig.align = "center", message = FALSE, warning = FALSE, collapse = TRUE ) ``` ![](QueenVictoriaAgave.jpg) # t-分布随机邻域嵌入 t-SNE (t-distributed stochastic neighbor embedding) >t-SNE 是 Laurens van der Maaten 和 Geoffrey Hinton 于 2008 年共同发表的一种非线性降维方法。 ## 基本原理 * 在**高维空间**构建一个概率分布（条件概率）拟合高维样本点之间的相对位置关系。 $$ 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)} $$ * 在**低维空间**也构建一个概率分布（条件概率）拟合低维样本点之间的相对位置关系。 $$ q_{j|i}=\frac{\exp(-{\Vert y_i-y_j\Vert}^2)}{\sum_{k\neq i}\exp(-{\Vert y_i-y_k\Vert}^2)} $$ * 通过学习，调整低维数据点令两个分布接近。具体而言是利用 KL 散度（Kullback-Leibler Divergence）来衡量两个分布之间的差异，通过梯度下降调整 y 使 C 变小从而实现降维。 $$ C=\sum_{i}KL(P_i\Vert Q_j)=\sum_{i}\sum_{j}p_{j|i}\log\frac{p_{j|i}}{q_{j|i}} $$ ## 一些改进 * 距离度量不对称 t-SNE 使用条件分布来度量样本点之间的**相对位置关系**，意味着这种距离度量应该是对称的。但是观察 $p_{j|i}$ 和 $q_{j|i}$ 的公式不难发现：交换 $i$ 与 $j$ 的位置得到的条件概率并不相等！这与实际不符。一种改进的方法是使用联合概率去替代条件概率： $$ \begin{aligned} p_{ij}&=\frac{\exp(-{\Vert x_i-x_j \Vert}^2/2\sigma_{i}^2)}{\sum_{k\neq l}\exp(-{\Vert x_k-x_l\Vert}^2 /2\sigma_{i}^2)}\\ q_{ij}&=\frac{\exp(-{\Vert y_i-y_j\Vert}^2)}{\sum_{k\neq l}\exp(-{\Vert y_k-y_l\Vert}^2)} \end{aligned} $$ 但是实际上使用的是另一种更简单的方法保证对称性和归一化： $$ \begin{aligned} p_{ij}&=p_{i|j}+p_{j|i}\\ p_{ij}&=\frac{p_{ij}}{\sum_{i}\sum_{j}p_{ij}} \end{aligned} $$ * 拥挤现象从高维到低维进行转换的过程中，低维点之间的位置关系无法建模高维点之间的位置关系，即高维空间中距离较大的点在低维空间中距离会变小（距离的度量不够稳健）。解决办法是使用尾部较厚的 student-t 分布来度量低维点之间的距离，即： $$ q_{ij}=\frac{(1+{\Vert y_i-y_j\Vert}^2)^{-1}}{\sum_{k\neq l}(1+{\Vert y_k-y_l\Vert}^2)^{-1}} $$ ## 改进后的一般步骤 1. 计算 $p_{ij}$ $$ \begin{aligned} 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)}\\ p_{ij}&=p_{i|j}+p_{j|i}\\ p_{ij}&=\frac{p_{ij}}{\sum_{i}\sum_{j}p_{ij}} \end{aligned} $$ 2. 随机生成低维随机数并计算 $q_{ij}$ $$ q_{ij}=\frac{(1+{\Vert y_i-y_j\Vert}^2)^{-1}}{\sum_{k\neq l}(1+{\Vert y_k-y_l\Vert}^2)^{-1}} $$ 3. 利用梯度下降法令 C 最小 $$ \begin{aligned} C&=\sum_{i}KL(P_i\Vert Q_j)=\sum_{i}\sum_{j}p_{ij}\log\frac{p_{ij}}{q_{ij}}\\ \frac{\partial C}{\partial y_i}&=4\sum_{j}(p_{ij}-q_{ij})(y_i-y_j)({1+\Vert y_i- y_j \Vert}^2)^{-1} \end{aligned} $$ ## 特点 - t-SNE 不直接采用欧式距离计算点和点之间的相邻关系，而是将数据点之间的**相似度转换为概率**，目的是希望数据在高维空间和低维空间的相似度接近，相似程度用**KL 散度 (Kullback-Leibler Divergence)**计算。 - 原始空间中的相似度由高斯联合概率表示。 - 嵌入空间的相似度由 t 分布表示（不使用正态分布是因为 t 分布在尾部比正态分布更稳健，从概率密度函数可以看出 t 分布的左右尾部比正态分布更厚）。 **缺点：** - 速度慢，占用内存大，不适用于大样本场合。 - 没有保留全局结构。即，只有簇内的距离才有意义，而簇间的相似性却无法保证。 - t-SNE 实际上只能嵌入 2 或 3 个维度，即仅用于可视化目的。因此很难将 t-SNE 当作一般的降维技术来使用，例如产生 10D 或 50D 的低维表示。 - t-SNE 不能直接处理高维数据，通常在使用 t-SNE 前会先执行 PCA 或 Autoencoder 对高维数据作降维预处理。 :::{.callout-tip} 正因为以上缺点，t-SNE 更适合用来做降维可视化。 ::: # t-sne 的 R 语言实现 ## 读取数据 ```{r} iris.test <- iris[ , -5] knitr::kable(head(iris.test)) ``` ## `tsne` 包降维 ```{r} # 数据标准化 library(dplyr) iris_norm <- scale(iris.test, center = TRUE, scale = TRUE) %>% as.data.frame() # tsne library(tsne) #设置随机种子 set.seed(123) # t-sne tsne <- tsne(iris_norm, k = 2, perplexity = 50) # 提取数据 iris_tsne <- data.frame(tsne) # 添加标签 iris_tsne$label <- iris[ , 5] # 更改列名 colnames(iris_tsne) <- c("X", "Y", "label") # 查看前5行数据 knitr::kable(iris_tsne[1:5, ]) ``` ```{r} #画图 library(ggplot2) p_tsne <- ggplot(iris_tsne, aes(x = X, y = Y, colour = label)) + geom_point(size = 2) + xlab("tsne_1") + ylab("tsne_2") p_tsne <- p_tsne + theme( panel.grid.major = element_blank(), panel.grid.minor = element_blank(), legend.title = element_blank(), panel.border = element_blank(), axis.line.x = element_line(color = "black", size = 0.5), axis.line.y = element_line(color = "black", size = 0.5), panel.background = element_blank() ) p_tsne ``` ## `Rtsne` 包降维 ```{r} library(Rtsne) # 必须要去除重复值 iris <- unique(iris) # 设置随机种子 set.seed(123) # 数据标准化 iris_norm <- scale(iris[ , -5], center = TRUE, scale = TRUE) %>% as.data.frame() # tsne tsne <- Rtsne(iris_norm, pca = FALSE, theta = 0) names(tsne) ``` 其中 `tsne$Y` 是 t-sne 降维结果。 ```{r} iris_tsne <- tsne$Y %>% as.data.frame() %>% cbind(iris$Species) colnames(iris_tsne) <- c("X", "Y", "label") ``` ```{r} p_tsne <- ggplot(iris_tsne, aes(x = X, y = Y, colour = label)) + geom_point(size = 2) + xlab("tsne_1") + ylab("tsne_2") + theme_bw() p_tsne ``` >更多 t-SNE 可视化详见：<https://datavizpyr.com/how-to-make-tsne-plot-in-r/>

t-分布随机邻域嵌入 t-SNE (t-distributed stochastic neighbor embedding)

基本原理

一些改进

改进后的一般步骤

特点

t-sne 的 R 语言实现

读取数据

tsne 包降维

Rtsne 包降维

`tsne` 包降维

`Rtsne` 包降维