Approximative nächste Nachbarn in TSNE

Einführung

In diesem Lab lernen wir, wie wir annähernde Nachbarn in TSNE mit der scikit-learn-Bibliothek von Python verwenden.

Tipps für die VM

Nachdem der VM-Start abgeschlossen ist, klicken Sie in der oberen linken Ecke, um zur Registerkarte Notebook zu wechseln und Jupyter Notebook für die Übung zu nutzen.

Manchmal müssen Sie einige Sekunden warten, bis Jupyter Notebook vollständig geladen ist. Die Validierung von Vorgängen kann aufgrund von Einschränkungen in Jupyter Notebook nicht automatisiert werden.

Wenn Sie bei der Lernphase Probleme haben, können Sie Labby gerne fragen. Geben Sie nach der Sitzung Feedback, und wir werden das Problem für Sie prompt beheben.

Skills Graph

Installieren Sie die erforderlichen Pakete

Wir müssen das nmslib- und das pynndescent-Paket installieren. Diese Pakete können mit dem pip-Befehl installiert werden.

!pip install nmslib pynndescent

Importieren Sie die erforderlichen Bibliotheken

Wir müssen die erforderlichen Bibliotheken importieren, einschließlich nmslib, pynndescent, sklearn, numpy, scipy und matplotlib.

import sys
import joblib
import numpy as np
import matplotlib.pyplot as plt
from scipy.sparse import csr_matrix
from sklearn.base import BaseEstimator, TransformerMixin
from sklearn.datasets import fetch_openml
from sklearn.utils import shuffle
from sklearn.manifold import TSNE
from sklearn.neighbors import KNeighborsTransformer
from sklearn.pipeline import make_pipeline
from pynndescent import PyNNDescentTransformer
import nmslib

Definieren Sie eine Wrapper-Klasse für nmslib

Wir definieren eine Wrapper-Klasse für nmslib, um die scikit-learn-API für nmslib zu implementieren, sowie eine Ladefunktion. Die NMSlibTransformer-Klasse nimmt n_neighbors, metric, method und n_jobs als Parameter. Die fit()-Methode initialisiert nmslib und fügt die Datenpunkte hinzu. Die transform()-Methode findet die nächsten Nachbarn und gibt eine dünn besetzte Matrix zurück.

class NMSlibTransformer(TransformerMixin, BaseEstimator):
    """Wrapper für die Verwendung von nmslib als KNeighborsTransformer von sklearn"""

    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]

        ## Weitere Metriken im Handbuch finden Sie unter
        ## 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]

        ## Aus Kompatibilitätsgründen, da jede Probe als eigene
        ## Nachbarin betrachtet wird, wird ein zusätzlicher Nachbar berechnet.
        n_neighbors = self.n_neighbors + 1

        if self.n_jobs < 0:
            ## Die gleiche Behandlung wie in joblib für negative Werte von n_jobs:
            ## insbesondere bedeutet `n_jobs == -1`, "so viele Threads wie 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

Definieren Sie eine Funktion zum Laden des MNIST-Datensatzes

Wir definieren eine Funktion load_mnist(), um den MNIST-Datensatz zu laden, die Daten zu mischen und nur die angegebene Anzahl von Proben zurückzugeben.

def load_mnist(n_samples):
    """Laden Sie MNIST, mischen Sie die Daten und geben Sie nur n_samples zurück."""
    mnist = fetch_openml("mnist_784", as_frame=False, parser="pandas")
    X, y = shuffle(mnist.data, mnist.target, random_state=2)
    return X[:n_samples] / 255, y[:n_samples]

Benchmarkieren verschiedener Transformer für die nächsten Nachbarn

Wir benchmarken die verschiedenen exakten/approximativen Transformer für die nächsten Nachbarn. Wir definieren die Datensätze, die Transformer und die Parameter, einschließlich n_iter, perplexity, metric und n_neighbors. Wir messen die Zeit, die es dauert, um jeden Transformer auf jedem Datensatz anzupassen und zu transformieren. Wir geben die Zeit aus, die es für das Anpassen und die Transformation jedes Transformers gedauert hat.

datasets = [
    ("MNIST_10000", load_mnist(n_samples=10_000)),
    ("MNIST_20000", load_mnist(n_samples=20_000)),
]

n_iter = 500
perplexity = 30
metric = "euclidean"
n_neighbors = int(3.0 * perplexity + 1) + 1

tsne_params = dict(
    init="random",  ## pca nicht unterstützt für dünn besetzte Matrizen
    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)"
            )

Visualisieren Sie die TSNE-Einbettung

Wir visualisieren die TSNE-Einbettungen mit verschiedenen Transformer für die nächsten Nachbarn. Wir definieren transformers als Liste, die drei Pipelines enthält: TSNE mit internem NearestNeighbors, TSNE mit KNeighborsTransformer und TSNE mit NMSlibTransformer. Wir iterieren über die Datensätze und die Transformer und plotten die TSNE-Einbettungen, die sich über die Methoden ähnlich sein sollten. Wir zeigen das Diagramm am Ende an.

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),
        ),
    ),
]

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()

Zusammenfassung

In diesem Lab haben wir gelernt, wie man approximative nächste Nachbarn in TSNE mit der scikit-learn-Bibliothek in Python verwendet. Wir haben die erforderlichen Bibliotheken importiert, eine Wrapper-Klasse für nmslib definiert, eine Funktion zum Laden des MNIST-Datensatzes definiert, verschiedene Transformer für die nächsten Nachbarn benchmarkt und TSNE-Einbettungen visualisiert. Wir haben gelernt, dass der standardmäßige TSNE-Schätzer mit seiner internen NearestNeighbors-Implementierung in Bezug auf die Leistung ungefähr der Pipeline mit TSNE und KNeighborsTransformer entspricht. Wir haben auch gelernt, dass der approximative NMSlibTransformer bereits auf dem kleinsten Datensatz etwas schneller als die exakte Suche ist, aber dieser Geschwindigkeitsunterschied wird bei Datensätzen mit einer größeren Anzahl von Proben wahrscheinlich noch deutlicher werden.