[PYTHON] Ungefähre Suche nach dem nächsten Nachbarn für eine ähnliche Bildanalyse (für Anfänger) (1)

Ich möchte über ähnliche Bilder schreiben, aber zuerst aus der Erklärung der K-NN-Methode.

K-NN-Methode

Identifizieren Sie aus k Daten, die sich in der Nähe bestimmter Daten befinden. Diejenigen mit einer großen Anzahl werden als dieselbe Klasse wie die Datenklasse beurteilt. ex) Wenn k = 3 ist, wird es als eine Gruppe von Dreiecken angesehen, da es ein Quadrat und zwei Dreiecke gibt. Wenn k = 5 ist, gibt es 3 Quadrate und 2 Dreiecke, daher wird es als eine Gruppe von Quadraten betrachtet.

Je nachdem, welches k Sie nehmen, ist die Lösung unterschiedlich, daher müssen Sie ein geeignetes k finden. Verwenden Sie die Kreuzvalidierung, um den Generalisierungsfehler für jedes k zu ermitteln, und legen Sie den kleinsten als optimales k fest. Generalisierungsfehler (= Fehler aus tatsächlichen Ergebnissen basierend auf Testdaten) Das Durchführen all dieser Berechnungen für jedes k würde eine große Verarbeitungszeit erfordern, wenn die Vektorkonvertierung unter Verwendung von Bildern durchgeführt wird. Daher die ungefähre Suche nach dem nächsten Nachbarn.

Ungefähre Suche nach dem nächsten Nachbarn

Auch wenn die nächste Nachbarschaft weit entfernt ist, ist sie erlaubt und adoptiert. d(q,x) <= (1+ε)d(q,x)* Abstand wobei d (q, x) die ungefähre Lösung ist Abstand zum nächsten d (q, x *)

Die ungefähre Lösung wird durch die beste Suche bestimmt Die beste Suche ist ein Suchalgorithmus, der den wünschenswertesten Knoten für die nächste Suche nach bestimmten Regeln auswählt.

python

pip install annoy scikit-learn

python

from collections import Counter
from sklearn import datasets
from annoy import AnnoyIndex
from sklearn.base import BaseEstimator
from sklearn.base import ClassifierMixin
from sklearn.model_selection import StratifiedKFold
from sklearn.model_selection import cross_validate
from sklearn.utils import check_X_y
from sklearn.utils import check_array


class AnnoyClassifier(BaseEstimator, ClassifierMixin):
    #Dies ist die Leber.
    def __init__(self, n_trees, metric='angular', n_neighbors=1, search_k=-1):
        # k-Anzahl d Bäume
        self.n_trees_ = n_trees
        #Für die Berechnung verwendete Entfernung
        self.metric_ = metric
        #Anzahl der Nachbarn
        self.n_neighbors_ = n_neighbors
        #Für die Genauigkeit verwendete Parameter
        self.search_k_ = search_k
        #Modell-
        self.clf_ = None
        #Fügen Sie ein Klassenetikett für Trainingsdaten hinzu
        self.train_y_ = None

    def fit(self, X, y):
        #Eingabeteil
        check_X_y(X, y)
        #Speichern Sie die Klassenbezeichnung der Trainingsdaten
        self.train_y_ = y
        #Bereiten Sie ein Modell von Annoy vor
        self.clf_ = AnnoyIndex(X.shape[1], metric=self.metric_)
        #Lernen
        for i, x in enumerate(X):
            self.clf_.add_item(i, x)
        # k-d Baumteil
        self.clf_.build(n_trees=self.n_trees_)
        return self

    def predict(self, X):
        check_array(X)
        #Gibt das Ergebnis zurück
        y_pred = [self._predict(x) for x in X]
        return y_pred

    def _predict(self, x):
        #Finde eine Nachbarschaft
        neighbors = self.clf_.get_nns_by_vector(x, self.n_neighbors_, search_k=self.search_k_)
        #Index in Klassenbezeichnung konvertieren
        neighbor_classes = self.train_y_[neighbors]
        #Extrahieren Sie den häufigsten Wert
        counter = Counter(neighbor_classes)
        most_common = counter.most_common(1)
        #Gibt die häufigste Klassenbezeichnung zurück
        return most_common[0][0]

    def get_params(self, deep=True):
        #Klassifikatorparameter
        return {
            'n_trees': self.n_trees_,
            'metric': self.metric_,
            'n_neighbors': self.n_neighbors_,
            'search_k': self.search_k_,
        }

def main():
    #Laden Sie den Iris-Datensatz
    dataset = datasets.load_iris()
    X, y = dataset.data, dataset.target
    #Sorter
    clf = AnnoyClassifier(n_trees=10)
    # 3-fold CV
    skf = StratifiedKFold(n_splits=3, shuffle=True, random_state=42)
    #Messen Sie die Generalisierungsleistung anhand der Genauigkeit als Bewertungsindex
    score = cross_validate(clf, X, y, cv=skf, scoring='accuracy')
    mean_test_score = score.get('test_score').mean()
    print('acc:', mean_test_score)


if __name__ == '__main__':
    main()

Ergebnis

python

acc: 0.98

Referenz

[Maschinelles Lernen_k Nachbarschaft Methodentheorie] (https://dev.classmethod.jp/machine-learning/2017ad_20171218_knn/#sec4)