Recherche approximative du voisin le plus proche pour une analyse d'image similaire (pour les débutants) (1)

Je voudrais écrire sur des images similaires, mais d'abord à partir de l'explication de la méthode K-NN.

Méthode K-NN

Identifiez à partir de k données proches de certaines données. Ceux dont le nombre est élevé sont considérés comme appartenant à la même classe que la classe de données. ex) Lorsque k = 3, puisqu'il y a un carré et deux triangles, il est considéré comme un groupe de triangles. Lorsque k = 5, il y a 3 carrés et 2 triangles, il est donc considéré comme un groupe de carrés.

Selon le k que vous prenez, la solution sera différente, vous devez donc trouver un k approprié. Utilisez la validation croisée pour trouver l'erreur de généralisation pour chaque k et définissez la plus petite comme k optimum. Erreur de généralisation (= erreur des résultats réels sur la base des données de test) Effectuer tous ces calculs pour chaque k nécessiterait un temps de traitement énorme lorsque la conversion vectorielle est effectuée à l'aide d'images. Par conséquent, la recherche approximative du voisin le plus proche.

Recherche approximative du voisin le plus proche

Même si le quartier le plus proche est éloigné, il est autorisé et adopté. d(q,x) <= (1+ε)d(q,x)* Distance où d (q, x) est la solution approximative Distance au d le plus proche (q, x *)

La solution approximative est déterminée par la meilleure recherche La meilleure recherche est un algorithme de recherche qui sélectionne le nœud le plus souhaitable pour rechercher ensuite selon certaines règles.

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):
    #Partie de création de modèle de recherche de quartier la plus proche approximative, c'est le foie.
    def __init__(self, n_trees, metric='angular', n_neighbors=1, search_k=-1):
        # k-nombre d'arbres d
        self.n_trees_ = n_trees
        #Distance utilisée pour le calcul
        self.metric_ = metric
        #Nombre de voisins
        self.n_neighbors_ = n_neighbors
        #Paramètres utilisés pour la précision
        self.search_k_ = search_k
        #modèle
        self.clf_ = None
        #Joindre une étiquette de classe pour les données d'entraînement
        self.train_y_ = None

    def fit(self, X, y):
        #Partie d'entrée
        check_X_y(X, y)
        #Enregistrez le libellé de classe des données d'entraînement
        self.train_y_ = y
        #Préparez un modèle d'Annoy
        self.clf_ = AnnoyIndex(X.shape[1], metric=self.metric_)
        #Apprendre
        for i, x in enumerate(X):
            self.clf_.add_item(i, x)
        # k-d partie d'arbre
        self.clf_.build(n_trees=self.n_trees_)
        return self

    def predict(self, X):
        check_array(X)
        #Renvoie le résultat
        y_pred = [self._predict(x) for x in X]
        return y_pred

    def _predict(self, x):
        #Trouvez un quartier
        neighbors = self.clf_.get_nns_by_vector(x, self.n_neighbors_, search_k=self.search_k_)
        #Convertir l'index en étiquette de classe
        neighbor_classes = self.train_y_[neighbors]
        #Extraire la valeur la plus fréquente
        counter = Counter(neighbor_classes)
        most_common = counter.most_common(1)
        #Renvoie le libellé de classe le plus fréquent
        return most_common[0][0]

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

def main():
    #Charger le jeu de données Iris
    dataset = datasets.load_iris()
    X, y = dataset.data, dataset.target
    #Trieur
    clf = AnnoyClassifier(n_trees=10)
    # 3-fold CV
    skf = StratifiedKFold(n_splits=3, shuffle=True, random_state=42)
    #Mesurer les performances de généralisation en utilisant la précision comme indice d'évaluation
    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()

résultat

python

acc: 0.98

référence

[Machine learning_k voisinage method_theory] (https://dev.classmethod.jp/machine-learning/2017ad_20171218_knn/#sec4)