降维实现性能比较
不同的降维技术可能有截然不同的计算复杂度。除了算法本身之外，还存在如何精确实现算法的问题。这两个因素对于实际运行特定降维所需的时间有重要影响。此外，你试图降维的数据的性质也很重要——这主要涉及原始数据的维度。在这里，我们将简要介绍一些降维实现的性能特征。
首先，让我们加载所需的常用工具——显然是 numpy 和 pandas，还有用于获取和重采样数据的工具，以及 time 模块，以便我们可以进行一些基本的基准测试。
import numpy as np
import pandas as pd
from sklearn.datasets import fetch_openml
from sklearn.utils import resample
import time
接下来我们需要实际的降维实现。为了解释目的，我们将主要使用 scikit-learn，但为了比较，我们还将包括 t-SNE 的 MulticoreTSNE 实现和 openTSNE，这两者在历史上都比 scikit-learn 的 t-SNE 性能显著更好（scikit-learn 的较新版本已改进了 t-SNE 的性能）。
from sklearn.manifold import TSNE, LocallyLinearEmbedding, Isomap, MDS, SpectralEmbedding
from sklearn.decomposition import PCA
from MulticoreTSNE import MulticoreTSNE
from openTSNE import TSNE as OpenTSNE
from umap import UMAP
接下来我们需要绘图工具，当然还有一些用于处理的数据。对于这次性能比较，我们将默认使用流形学习的现有标准基准：MNIST 数字数据集。我们可以使用 scikit-learn 的 fetch_openml 来获取它。
import matplotlib.pyplot as plt
import seaborn as sns
%matplotlib inline
sns.set(context='notebook',
rc={'figure.figsize':(12,10)},
palette=sns.color_palette('tab10', 10))
mnist = fetch_openml('mnist_784', version=1, return_X_y=True)
mnist_data = mnist[0]
mnist_labels = mnist[1].astype(int)
现在是时候开始考察性能了。首先，让我们看看性能如何随数据集大小的增加而扩展。
按数据集大小进行的性能扩展
随着数据集大小的增加，特定降维算法的运行时间将以不同的速率增加。如果你想在更大的数据集上运行算法，你不仅会关心在单个小数据集上的比较运行时间，还会关心随着数据集变大性能如何扩展。我们可以通过从 MNIST 数字中进行子采样（通过 scikit-learn 便捷的 resample 工具）并观察不同大小子样本的运行时间来模拟这一点。由于这里涉及一些随机性（子样本选择和一些具有随机性的算法都存在随机性），我们将需要对每种数据集大小运行几个示例。我们可以轻松地将所有这些打包到一个简单的函数中，该函数将返回一个包含给定算法对应数据集大小和运行时间的便捷 pandas dataframe。
def data_size_scaling(algorithm, data, sizes=[100, 200, 400, 800, 1600], n_runs=5):
result = []
for size in sizes:
for run in range(n_runs):
subsample = resample(data, n_samples=size)
start_time = time.time()
algorithm.fit(subsample)
elapsed_time = time.time() - start_time
del subsample
result.append((size, elapsed_time))
return pd.DataFrame(result, columns=('dataset size', 'runtime (s)'))
现在我们只需对各种降维实现运行此操作，以便查看结果。由于我们不知道这些运行可能需要多长时间，我们将从一组非常小的样本开始，最多扩展到仅 1600 个样本。
all_algorithms = [
PCA(),
UMAP(),
MulticoreTSNE(),
OpenTSNE(),
TSNE(),
LocallyLinearEmbedding(),
SpectralEmbedding(),
Isomap(),
MDS(),
]
performance_data = {}
for algorithm in all_algorithms:
if 'openTSNE' in str(algorithm.__class__):
alg_name = "OpenTSNE"
elif 'MulticoreTSNE' in str(algorithm.__class__):
alg_name = "MulticoreTSNE"
else:
alg_name = str(algorithm).split('(')[0]
performance_data[alg_name] = data_size_scaling(algorithm, mnist_data, n_runs=5)
print(f"[{time.asctime(time.localtime())}] Completed {alg_name}")
[Sat Feb 22 09:50:24 2020] Completed PCA
[Sat Feb 22 09:51:23 2020] Completed UMAP
[Sat Feb 22 09:53:24 2020] Completed MulticoreTSNE
[Sat Feb 22 10:00:50 2020] Completed OpenTSNE
[Sat Feb 22 10:02:22 2020] Completed TSNE
[Sat Feb 22 10:02:44 2020] Completed LocallyLinearEmbedding
[Sat Feb 22 10:03:06 2020] Completed SpectralEmbedding
[Sat Feb 22 10:03:31 2020] Completed Isomap
[Sat Feb 22 10:11:45 2020] Completed MDS
现在让我们绘制结果，看看发生了什么。我们将使用 seaborn 的回归图来插值有效扩展。对于某些算法，这可能有点嘈杂，尤其是在这个相对较小的数据集范围内，但这会让我们很好地了解情况。
for alg_name, perf_data in performance_data.items():
sns.regplot('dataset size', 'runtime (s)', perf_data, order=2, label=alg_name)
plt.legend()
我们可以立即看到这里有一些异常值。值得注意的是，openTSNE 在小数据集上表现不佳。然而，它不具备 MDS 的扩展特性；对于更大的数据集大小，MDS 会很快变得完全无法管理，而 openTSNE 则具有相当平坦的扩展。同时，MulticoreTSNE 表明 t-SNE 可以相当高效地运行。除了 PCA 是迄今为止最快的选项之外，很难看出其他实现有什么特别之处。为了看到更多，我们需要查看在更大数据集大小上的运行时间。MDS、Isomap 和 SpectralEmbedding 的运行时间实际上会太长，所以让我们将注意力限制在性能最快的实现上，看看当我们扩展到更大的数据集大小时会发生什么。
fast_algorithms = [
PCA(),
UMAP(),
MulticoreTSNE(),
OpenTSNE(),
TSNE(),
LocallyLinearEmbedding(),
]
fast_performance_data = {}
for algorithm in fast_algorithms:
if 'openTSNE' in str(algorithm.__class__):
alg_name = "OpenTSNE"
elif 'MulticoreTSNE' in str(algorithm.__class__):
alg_name = "MulticoreTSNE"
else:
alg_name = str(algorithm).split('(')[0]
fast_performance_data[alg_name] = data_size_scaling(algorithm, mnist_data,
sizes=[1600, 3200, 6400, 12800, 25600], n_runs=4)
print(f"[{time.asctime(time.localtime())}] Completed {alg_name}")
[Sat Feb 22 10:12:15 2020] Completed PCA
[Sat Feb 22 10:14:51 2020] Completed UMAP
[Sat Feb 22 11:16:05 2020] Completed MulticoreTSNE
[Sat Feb 22 11:50:17 2020] Completed OpenTSNE
[Sat Feb 22 13:06:38 2020] Completed TSNE
[Sat Feb 22 14:14:36 2020] Completed LocallyLinearEmbedding
for alg_name, perf_data in fast_performance_data.items():
sns.regplot('dataset size', 'runtime (s)', perf_data, order=2, label=alg_name)
plt.legend()
此时，我们开始看到不同实现之间的一些显著差异。在较早的图中，OpenTSNE 看起来表现相对较差，但现在扩展效应开始显现，我们看到它比大多数实现更快。同样，MulticoreTSNE 在较早的图中看起来比其他一些算法慢，但当我们扩展到更大的数据集时，我们看到它的相对扩展性能优于 scikit-learn 的 TSNE 和局部线性嵌入实现。
可能值得进一步扩展——直到完整的 MNIST 数字数据集。为了在任何合理的时间内做到这一点，我们将不得不将注意力限制在更小的实现子集上。我们将只保留 OpenTSNE、MulticoreTSNE、PCA 和 UMAP。
very_fast_algorithms = [
PCA(),
UMAP(),
MulticoreTSNE(),
OpenTSNE(),
]
vfast_performance_data = {}
for algorithm in very_fast_algorithms:
if 'openTSNE' in str(algorithm.__class__):
alg_name = "OpenTSNE"
elif 'MulticoreTSNE' in str(algorithm.__class__):
alg_name = "MulticoreTSNE"
else:
alg_name = str(algorithm).split('(')[0]
vfast_performance_data[alg_name] = data_size_scaling(algorithm, mnist_data,
sizes=[3200, 6400, 12800, 25600, 51200, 70000], n_runs=2)
print(f"[{time.asctime(time.localtime())}] Completed {alg_name}")
[Sat Feb 22 14:15:22 2020] Completed PCA
[Sat Feb 22 14:18:59 2020] Completed UMAP
[Sat Feb 22 17:04:58 2020] Completed MulticoreTSNE
[Sat Feb 22 17:54:14 2020] Completed OpenTSNE
for alg_name, perf_data in vfast_performance_data.items():
sns.regplot('dataset size', 'runtime (s)', perf_data, order=2, label=alg_name)
plt.legend()
在这里，我们真正看到了 UMAP 相对于 t-SNE 的优势。虽然 UMAP 显然比 PCA 慢，但其扩展性能显著优于 MulticoreTSNE，而且尽管 openTSNE 具有令人印象深刻的扩展性能，UMAP 仍继续超越它。根据曲线的斜率，对于更大的数据集，UMAP 和 t-SNE 之间的差异只会越来越大。
到此为止，我们对按数据集大小进行的扩展分析结束了。简而言之，PCA 是迄今为止最快的选项，但为了速度，你可能会放弃很多。UMAP 虽然与 PCA 不具有竞争力，但在本文探讨的实现中，其性能显然是次优的选择。鉴于 UMAP 能够提供的结果质量，我们认为它显然是降维的一个好选择。