Hinweis
Zum Ende springen, um den vollständigen Beispielcode herunterzuladen oder dieses Beispiel über JupyterLite oder Binder in Ihrem Browser auszuführen.
Ungefähre nächste Nachbarn in TSNE#
Dieses Beispiel zeigt, wie KNeighborsTransformer und TSNE in einer Pipeline verknüpft werden. Es zeigt auch, wie die Pakete nmslib und pynndescent gekapselt werden können, um KNeighborsTransformer zu ersetzen und ungefähre nächste Nachbarn durchzuführen. Diese Pakete können mit pip install nmslib pynndescent installiert werden.
Hinweis: In KNeighborsTransformer verwenden wir die Definition, die jeden Trainingspunkt als seinen eigenen Nachbarn in der Zählung von n_neighbors einschließt. Aus Kompatibilitätsgründen wird ein zusätzlicher Nachbar berechnet, wenn mode == 'distance'. Bitte beachten Sie, dass wir dasselbe in unserem vorgeschlagenen nmslib-Wrapper tun.
# Authors: The scikit-learn developers
# SPDX-License-Identifier: BSD-3-Clause
Zuerst versuchen wir, die Pakete zu importieren und den Benutzer zu warnen, falls diese fehlen.
Wir definieren eine Wrapper-Klasse zur Implementierung der scikit-learn-API für nmslib sowie eine Ladefunktion.
import joblib
import numpy as np
from scipy.sparse import csr_matrix
from sklearn.base import BaseEstimator, TransformerMixin
from sklearn.datasets import fetch_openml
from sklearn.utils import shuffle
class NMSlibTransformer(TransformerMixin, BaseEstimator):
"""Wrapper for using nmslib as sklearn's KNeighborsTransformer"""
def __init__(self, n_neighbors=5, metric="euclidean", method="sw-graph", n_jobs=-1):
self.n_neighbors = n_neighbors
self.method = method
self.metric = metric
self.n_jobs = n_jobs
def fit(self, X):
self.n_samples_fit_ = X.shape[0]
# see more metric in the manual
# https://github.com/nmslib/nmslib/tree/master/manual
space = {
"euclidean": "l2",
"cosine": "cosinesimil",
"l1": "l1",
"l2": "l2",
}[self.metric]
self.nmslib_ = nmslib.init(method=self.method, space=space)
self.nmslib_.addDataPointBatch(X.copy())
self.nmslib_.createIndex()
return self
def transform(self, X):
n_samples_transform = X.shape[0]
# For compatibility reasons, as each sample is considered as its own
# neighbor, one extra neighbor will be computed.
n_neighbors = self.n_neighbors + 1
if self.n_jobs < 0:
# Same handling as done in joblib for negative values of n_jobs:
# in particular, `n_jobs == -1` means "as many threads as CPUs".
num_threads = joblib.cpu_count() + self.n_jobs + 1
else:
num_threads = self.n_jobs
results = self.nmslib_.knnQueryBatch(
X.copy(), k=n_neighbors, num_threads=num_threads
)
indices, distances = zip(*results)
indices, distances = np.vstack(indices), np.vstack(distances)
indptr = np.arange(0, n_samples_transform * n_neighbors + 1, n_neighbors)
kneighbors_graph = csr_matrix(
(distances.ravel(), indices.ravel(), indptr),
shape=(n_samples_transform, self.n_samples_fit_),
)
return kneighbors_graph
def load_mnist(n_samples):
"""Load MNIST, shuffle the data, and return only n_samples."""
mnist = fetch_openml("mnist_784", as_frame=False)
X, y = shuffle(mnist.data, mnist.target, random_state=2)
return X[:n_samples] / 255, y[:n_samples]
Wir benchmarken die verschiedenen exakten/ungefähren Transformer für nächste Nachbarn.
import time
from sklearn.manifold import TSNE
from sklearn.neighbors import KNeighborsTransformer
from sklearn.pipeline import make_pipeline
datasets = [
("MNIST_10000", load_mnist(n_samples=10_000)),
("MNIST_20000", load_mnist(n_samples=20_000)),
]
max_iter = 500
perplexity = 30
metric = "euclidean"
# TSNE requires a certain number of neighbors which depends on the
# perplexity parameter.
# Add one since we include each sample as its own neighbor.
n_neighbors = int(3.0 * perplexity + 1) + 1
tsne_params = dict(
init="random", # pca cannot be used with precomputed distances
perplexity=perplexity,
method="barnes_hut",
random_state=42,
max_iter=max_iter,
learning_rate="auto",
)
transformers = [
(
"KNeighborsTransformer",
KNeighborsTransformer(n_neighbors=n_neighbors, mode="distance", metric=metric),
),
(
"NMSlibTransformer",
NMSlibTransformer(n_neighbors=n_neighbors, metric=metric),
),
(
"PyNNDescentTransformer",
PyNNDescentTransformer(
n_neighbors=n_neighbors, metric=metric, parallel_batch_queries=True
),
),
]
for dataset_name, (X, y) in datasets:
msg = f"Benchmarking on {dataset_name}:"
print(f"\n{msg}\n" + str("-" * len(msg)))
for transformer_name, transformer in transformers:
longest = np.max([len(name) for name, model in transformers])
start = time.time()
transformer.fit(X)
fit_duration = time.time() - start
print(f"{transformer_name:<{longest}} {fit_duration:.3f} sec (fit)")
start = time.time()
Xt = transformer.transform(X)
transform_duration = time.time() - start
print(f"{transformer_name:<{longest}} {transform_duration:.3f} sec (transform)")
if transformer_name == "PyNNDescentTransformer":
start = time.time()
Xt = transformer.transform(X)
transform_duration = time.time() - start
print(
f"{transformer_name:<{longest}} {transform_duration:.3f} sec"
" (transform)"
)
Beispielhafte Ausgabe
Benchmarking on MNIST_10000:
----------------------------
KNeighborsTransformer 0.007 sec (fit)
KNeighborsTransformer 1.139 sec (transform)
NMSlibTransformer 0.208 sec (fit)
NMSlibTransformer 0.315 sec (transform)
PyNNDescentTransformer 4.823 sec (fit)
PyNNDescentTransformer 4.884 sec (transform)
PyNNDescentTransformer 0.744 sec (transform)
Benchmarking on MNIST_20000:
----------------------------
KNeighborsTransformer 0.011 sec (fit)
KNeighborsTransformer 5.769 sec (transform)
NMSlibTransformer 0.733 sec (fit)
NMSlibTransformer 1.077 sec (transform)
PyNNDescentTransformer 14.448 sec (fit)
PyNNDescentTransformer 7.103 sec (transform)
PyNNDescentTransformer 1.759 sec (transform)
Beachten Sie, dass PyNNDescentTransformer beim ersten fit und dem ersten transform mehr Zeit benötigt, aufgrund des Overheads des Numba Just-in-Time-Compilers. Aber nach dem ersten Aufruf wird der kompilierte Python-Code von Numba im Cache gehalten und nachfolgende Aufrufe leiden nicht unter diesem anfänglichen Overhead. Sowohl KNeighborsTransformer als auch NMSlibTransformer werden hier nur einmal ausgeführt, da sie stabilere fit- und transform-Zeiten aufweisen würden (sie haben nicht das Cold-Start-Problem von PyNNDescentTransformer).
import matplotlib.pyplot as plt
from matplotlib.ticker import NullFormatter
transformers = [
("TSNE with internal NearestNeighbors", TSNE(metric=metric, **tsne_params)),
(
"TSNE with KNeighborsTransformer",
make_pipeline(
KNeighborsTransformer(
n_neighbors=n_neighbors, mode="distance", metric=metric
),
TSNE(metric="precomputed", **tsne_params),
),
),
(
"TSNE with NMSlibTransformer",
make_pipeline(
NMSlibTransformer(n_neighbors=n_neighbors, metric=metric),
TSNE(metric="precomputed", **tsne_params),
),
),
]
# init the plot
nrows = len(datasets)
ncols = np.sum([1 for name, model in transformers if "TSNE" in name])
fig, axes = plt.subplots(
nrows=nrows, ncols=ncols, squeeze=False, figsize=(5 * ncols, 4 * nrows)
)
axes = axes.ravel()
i_ax = 0
for dataset_name, (X, y) in datasets:
msg = f"Benchmarking on {dataset_name}:"
print(f"\n{msg}\n" + str("-" * len(msg)))
for transformer_name, transformer in transformers:
longest = np.max([len(name) for name, model in transformers])
start = time.time()
Xt = transformer.fit_transform(X)
transform_duration = time.time() - start
print(
f"{transformer_name:<{longest}} {transform_duration:.3f} sec"
" (fit_transform)"
)
# plot TSNE embedding which should be very similar across methods
axes[i_ax].set_title(transformer_name + "\non " + dataset_name)
axes[i_ax].scatter(
Xt[:, 0],
Xt[:, 1],
c=y.astype(np.int32),
alpha=0.2,
cmap=plt.cm.viridis,
)
axes[i_ax].xaxis.set_major_formatter(NullFormatter())
axes[i_ax].yaxis.set_major_formatter(NullFormatter())
axes[i_ax].axis("tight")
i_ax += 1
fig.tight_layout()
plt.show()
Beispielhafte Ausgabe
Benchmarking on MNIST_10000:
----------------------------
TSNE with internal NearestNeighbors 24.828 sec (fit_transform)
TSNE with KNeighborsTransformer 20.111 sec (fit_transform)
TSNE with NMSlibTransformer 21.757 sec (fit_transform)
Benchmarking on MNIST_20000:
----------------------------
TSNE with internal NearestNeighbors 51.955 sec (fit_transform)
TSNE with KNeighborsTransformer 50.994 sec (fit_transform)
TSNE with NMSlibTransformer 43.536 sec (fit_transform)
Wir können beobachten, dass der Standard-TSNE-Schätzer mit seiner internen NearestNeighbors-Implementierung in Bezug auf die Leistung ungefähr gleichwertig mit der Pipeline mit TSNE und KNeighborsTransformer ist. Dies ist zu erwarten, da beide Pipelines intern auf derselben NearestNeighbors-Implementierung basieren, die eine exakte Nachbarschaftssuche durchführt. Der ungefähre NMSlibTransformer ist bereits geringfügig schneller als die exakte Suche auf dem kleinsten Datensatz, aber dieser Geschwindigkeitsunterschied wird voraussichtlich bei Datensätzen mit einer größeren Anzahl von Stichproben signifikanter.
Beachten Sie jedoch, dass nicht alle ungefähren Suchmethoden garantiert die Geschwindigkeit der Standardmethode für die exakte Suche verbessern: Tatsächlich hat sich die Implementierung der exakten Suche seit scikit-learn 1.1 erheblich verbessert. Darüber hinaus erfordert die Brute-Force-Methode für die exakte Suche kein Erstellen eines Index während der fit-Zeit. Um also eine allgemeine Leistungssteigerung im Kontext der TSNE-Pipeline zu erzielen, müssen die Gewinne der ungefähren Suche bei transform größer sein als die zusätzliche Zeit, die zum Erstellen des Index für die ungefähre Suche während der fit-Zeit aufgewendet wird.
Schließlich ist auch der TSNE-Algorithmus selbst rechnerisch aufwendig, unabhängig von der Nachbarschaftssuche. Eine Beschleunigung des Schritts der Nachbarschaftssuche um den Faktor 5 würde also nicht zu einer Beschleunigung der Gesamtpipeline um den Faktor 5 führen.
Verwandte Beispiele
t-SNE: Der Effekt verschiedener Perplexitätswerte auf die Form
Manifold Learning Methoden auf einer abgetrennten Sphäre
Vergleich von Nächsten Nachbarn mit und ohne Neighborhood Components Analysis