Примечание
Перейти к концу для скачивания полного кода примера или для запуска этого примера в вашем браузере через JupyterLite или Binder
Приближенные ближайшие соседи в TSNE
Этот пример демонстрирует, как объединить KNeighborsTransformer и TSNE в конвейер. Он также показывает, как обернуть пакеты nmslib и pynndescent для замены KNeighborsTransformer и выполнения приближенных ближайших соседей. Эти пакеты можно установить с помощью pip install nmslib pynndescent.
Примечание: В KNeighborsTransformer используется определение, которое включает каждую обучающую точку в качестве собственного соседа в подсчёте n_neighbors, и по соображениям совместимости вычисляется один дополнительный сосед при mode == 'distance'. Обратите внимание, что мы делаем то же самое в предложенном nmslib обёртке.
# Authors: The scikit-learn developers # SPDX-License-Identifier: BSD-3-Clause
Сначала мы пытаемся импортировать пакеты и предупредить пользователя в случае их отсутствия.
import sys
try:
import nmslib
except ImportError:
print("The package 'nmslib' is required to run this example.")
sys.exit()
try:
from pynndescent import PyNNDescentTransformer
except ImportError:
print("The package 'pynndescent' is required to run this example.")
sys.exit()
Мы определяем класс-обёртку для реализации API scikit-learn для nmslib, а также функцию загрузки.
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]
Мы проводим бенчмаркинг различных трансформаторов точных/приближенных ближайших соседей.
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)),
]
n_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 not supported for sparse matrices
perplexity=perplexity,
method="barnes_hut",
random_state=42,
n_iter=n_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)"
)
Пример вывода:
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)
Обратите внимание, что PyNNDescentTransformer занимает больше времени в течение первой fit и первой transform из-за накладных расходов компилятора numba just in time. Но после первого вызова скомпилированный Python-код сохраняется в кэше numba, и последующие вызовы не страдают от этой начальной накладной. И KNeighborsTransformer и NMSlibTransformer запускаются только один раз здесь, так как они бы показали более стабильное fit и transform время (у них нет проблемы холодного запуска 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()
Пример вывода:
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)
Мы можем наблюдать, что по умолчанию TSNE оценочный с его внутренней NearestNeighbors реализацией примерно эквивалентен конвейеру с TSNE и KNeighborsTransformer с точки зрения производительности. Это ожидаемо, так как оба конвейера полагаются на ту же внутреннюю NearestNeighbors реализацию, которая выполняет точный поиск ближайших соседей. Приближенный NMSlibTransformer уже немного быстрее, чем точный поиск на самом маленьком наборе данных, но это различие в скорости ожидается, что станет более значительным на наборах данных с большим количеством образцов.
Однако обратите внимание, что не все методы приближенного поиска гарантируют повышение скорости по умолчанию метода точного поиска: на самом деле, реализация точного поиска значительно улучшилась с момента выпуска scikit-learn 1.1. Кроме того, метод точного поиска с полным перебором не требует построения индекса на момент fit времени. Таким образом, для получения общего повышения производительности в контексте конвейера TSNE прирост от приближенного поиска на момент transform должен быть больше, чем дополнительное время, затраченное на построение индекса приближенного поиска на момент fit времени.
В конечном итоге, сам алгоритм TSNE также является вычислительно интенсивным, независимо от поиска ближайших соседей. Поэтому ускорение шага поиска ближайших соседей в 5 раз не приведет к ускорению всего конвейера в 5 раз.
Связанные примеры
© 2007–2025 The scikit-learn developers
Licensed under the 3-clause BSD License.
https://scikit-learn.org/1.6/auto_examples/neighbors/approximate_nearest_neighbors.html
