引言
t-SNE（t-Distributed Stochastic Neighbor Embedding）是2008年由Laurens van der Maaten和Geoffrey Hinton提出的非线性降维算法，特别适用于高维数据的可视化。与PCA等线性方法不同，t-SNE能够在低维空间中更好地保留数据的局部结构，使相似样本聚集、不相似样本分离。本文将用Java完整实现t-SNE算法，帮助读者理解其概率建模与梯度优化过程。
核心原理
高维空间中的相似度
对于高维数据点 x_i 和 x_j，t-SNE首先将其相似度建模为条件概率：
p_{j|i} = exp(-||x_i – x_j||² / 2σ_i²) / Σ_{k≠i} exp(-||x_i – x_k||² / 2σ_i²)
然后对称化为联合概率：
p_{ij} = (p_{j|i} + p_{i|j}) / 2n
其中 σ_i 通过二分查找确定，使得以 x_i 为中心的邻域具有固定的困惑度（Perplexity）。
低维空间中的相似度
在低维空间中，t-SNE使用自由度为1的t分布（柯西分布）来建模相似度：
q_{ij} = (1 + ||y_i – y_j||²)^(-1) / Σ_{k≠l} (1 + ||y_k – y_l||²)^(-1)
使用t分布而非高斯分布的原因是其长尾特性，能够有效缓解”拥挤问题”（Crowding Problem），给低维空间中相距较远的点更多空间。
目标函数：KL散度
t-SNE通过最小化高维分布 P 与低维分布 Q 之间的KL散度来优化低维表示：
C = KL(P || Q) = Σ_i Σ_j p_{ij} log(p_{ij} / q_{ij})
低维点 y_i 的梯度为：
∂C/∂y_i = 4 Σ_j (p_{ij} – q_{ij}) (y_i – y_j) / (1 + ||y_i – y_j||²)
Java实现
项目结构
src/
├── TSNE.java // 核心t-SNE算法
├── MatrixUtils.java // 矩阵/向量工具类
└── TSNEDemo.java // 演示主类
核心算法实现
import java.util.Random;
/**
* t-SNE降维算法实现
*/
public class TSNE {
private final int outputDims; // 输出维度(通常为2)
private final int maxIterations; // 最大迭代次数
private final double perplexity; // 困惑度
private final double learningRate; // 学习率
private final double momentum; // 动量系数
private final Random rand;
public TSNE(int outputDims, int maxIterations, double perplexity) {
this.outputDims = outputDims;
this.maxIterations = maxIterations;
this.perplexity = perplexity;
this.learningRate = 200.0;
this.momentum = 0.8;
this.rand = new Random(42);
}
/**
* 计算高维空间中的成对距离
*/
private double[][] computePairwiseDistances(double[][] X) {
int n = X.length;
double[][] dist = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double sum = 0;
for (int k = 0; k < X[0].length; k++) {
double diff = X[i][k] - X[j][k];
sum += diff * diff;
}
dist[i][j] = sum;
dist[j][i] = sum;
}
}
return dist;
}
/**
* 计算给定sigma下的条件概率分布和困惑度
* @return [P, H] P是概率分布，H是困惑度
*/
private Object[] computeGaussianPerplexity(double[] distI, double sigma) {
int n = distI.length;
double[] p = new double[n];
double sum = 0;
for (int j = 0; j < n; j++) {
if (i != j) { // 实际使用时通过索引控制
p[j] = Math.exp(-distI[j] / (2 * sigma * sigma));
sum += p[j];
}
}
double H = 0;
for (int j = 0; j < n; j++) {
if (i != j && sum > 0) {
p[j] /= sum;
if (p[j] > 1e-7) {
H -= p[j] * Math.log(p[j]);
}
}
}
return new Object[]{p, Math.exp(H)};
}
/**
* 二分查找确定最优sigma使困惑度匹配目标值
*/
private double binarySearchSigma(double[] distI, double targetPerplexity) {
double sigmaMin = 1e-20, sigmaMax = 1e20;
double sigma = 1.0;
for (int iter = 0; iter < 50; iter++) {
// 简化的困惑度计算
double[] p = new double[distI.length];
double sum = 0;
for (int j = 0; j < distI.length; j++) {
p[j] = Math.exp(-distI[j] / (2 * sigma * sigma));
sum += p[j];
}
double H = 0;
for (int j = 0; j < distI.length; j++) {
if (sum > 0) p[j] /= sum;
if (p[j] > 1e-7) H -= p[j] * Math.log(p[j]);
}
double perp = Math.exp(H);
if (perp > targetPerplexity) {
sigmaMax = sigma;
sigma = (sigma + sigmaMin) / 2;
} else {
sigmaMin = sigma;
sigma = (sigma + sigmaMax) / 2;
}
if (Math.abs(perp - targetPerplexity) < 1e-5) break;
}
return sigma;
}
/**
* 计算高维联合概率P
*/
private double[][] computeP(double[][] X) {
int n = X.length;
double[][] dist = computePairwiseDistances(X);
double[][] P = new double[n][n];
for (int i = 0; i < n; i++) {
double sigma = binarySearchSigma(dist[i], perplexity);
double sum = 0;
for (int j = 0; j < n; j++) {
if (i != j) {
P[i][j] = Math.exp(-dist[i][j] / (2 * sigma * sigma));
sum += P[i][j];
}
}
for (int j = 0; j < n; j++) {
if (i != j && sum > 0) P[i][j] /= sum;
}
}
// 对称化: p_ij = (p_j|i + p_i|j) / 2n
double[][] Psym = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
Psym[i][j] = (P[i][j] + P[j][i]) / (2 * n);
Psym[j][i] = Psym[i][j];
}
}
return Psym;
}
/**
* 执行t-SNE降维
*/
public double[][] fitTransform(double[][] X) {
int n = X.length;
double[][] P = computeP(X);
// 初始化低维表示Y，服从N(0, 1e-4)
double[][] Y = new double[n][outputDims];
double[][] Yprev = new double[n][outputDims];
for (int i = 0; i < n; i++) {
for (int d = 0; d < outputDims; d++) {
Y[i][d] = rand.nextGaussian() * 0.0001;
}
}
// 梯度下降优化
for (int iter = 0; iter < maxIterations; iter++) {
// 计算低维成对距离和Q分布
double[][] Q = new double[n][n];
double[][] num = new double[n][n];
double sumQ = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double dist = 0;
for (int d = 0; d < outputDims; d++) {
double diff = Y[i][d] - Y[j][d];
dist += diff * diff;
}
num[i][j] = 1.0 / (1.0 + dist);
num[j][i] = num[i][j];
sumQ += num[i][j];
}
}
sumQ *= 2;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
Q[i][j] = Math.max(num[i][j] / sumQ, 1e-12);
Q[j][i] = Q[i][j];
}
}
// 计算梯度并更新Y
double[][] grads = new double[n][outputDims];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
double factor = 4 * (P[i][j] - Q[i][j]) * num[i][j];
for (int d = 0; d < outputDims; d++) {
grads[i][d] += factor * (Y[i][d] - Y[j][d]);
}
}
}
// 更新Y = Y + lr * grads + momentum * (Y - Yprev)
for (int i = 0; i < n; i++) {
for (int d = 0; d < outputDims; d++) {
double update = learningRate * grads[i][d] + momentum * (Y[i][d] - Yprev[i][d]);
Yprev[i][d] = Y[i][d];
Y[i][d] += update;
}
}
// 早期压缩: 前100轮增大P的值
if (iter < 100) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
P[i][j] *= 4;
}
}
}
if ((iter + 1) % 100 == 0) {
double loss = computeLoss(P, Q);
System.out.println("迭代 " + (iter + 1) + ", KL散度: " + String.format("%.6f", loss));
}
}
return Y;
}
private double computeLoss(double[][] P, double[][] Q) {
double loss = 0;
int n = P.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (P[i][j] > 1e-7) {
loss += P[i][j] * Math.log(P[i][j] / Q[i][j]);
}
}
}
return loss;
}
}
演示主类
/**
* t-SNE降维演示
*/
public class TSNEDemo {
public static void main(String[] args) {
// 构造模拟数据: 3个簇的高维点
int nPerCluster = 30;
int dims = 50;
double[][] X = new double[3 * nPerCluster][dims];
Random rand = new Random(123);
double[][] centers = {{1,1,1,1,1}, {5,5,5,5,5}, {9,9,9,9,9}};
for (int c = 0; c < 3; c++) {
for (int i = 0; i < nPerCluster; i++) {
for (int d = 0; d < 5; d++) {
X[c * nPerCluster + i][d] = centers[c][d] + rand.nextGaussian() * 0.3;
}
for (int d = 5; d < dims; d++) {
X[c * nPerCluster + i][d] = rand.nextGaussian() * 0.1;
}
}
}
System.out.println("输入数据: " + X.length + "个样本, " + dims + "维");
// 执行t-SNE降维到2维
TSNE tsne = new TSNE(2, 1000, 30.0);
double[][] Y = tsne.fitTransform(X);
System.out.println("\n降维结果 (2D坐标):");
for (int c = 0; c < 3; c++) {
System.out.println("簇 " + (c + 1) + " 样本坐标:");
for (int i = 0; i < Math.min(5, nPerCluster); i++) {
int idx = c * nPerCluster + i;
System.out.printf(" [%.4f, %.4f]%n", Y[idx][0], Y[idx][1]);
}
}
}
}
复杂度分析
| 阶段 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 高维距离计算 | O(n² · D) | O(n²) |
| 二分查找sigma | O(n² · log(V) · iter) | O(n²) |
| 低维梯度计算 | O(n² · d · iter) | O(n²) |
| 总计 | O(n² · (D + d · iter)) | O(n²) |
其中 n 为样本数，D 为原始维度，d 为目标维度（通常为2），iter 为迭代次数。t-SNE的 O(n²) 复杂度限制了其在大规模数据上的直接应用，此时可采用Barnes-Hut近似将复杂度降至 O(n log n)。
总结
本文用Java完整实现了t-SNE降维算法，涵盖高斯相似度建模、困惑度驱动的sigma搜索、t分布低维映射与KL散度梯度下降优化。t-SNE是理解高维数据结构的重要工具，读者可将其应用于图像特征可视化、文本聚类分析等场景，或进一步探索UMAP等更高效的降维方法。
