Quand devrais-je aller au-delà de k voisin le plus proche

Pour de nombreux projets d'apprentissage automatique que nous faisons, nous commençons par le classificateur k le plus proche voisin. Il s'agit d'un classificateur de départ idéal car nous avons généralement suffisamment de temps pour calculer toutes les distances et le nombre de paramètres est limité (k, métrique de distance et pondération)

Cependant, cela a souvent pour effet de nous en tenir au classificateur knn car plus tard dans le projet, il n'y a pas de place pour passer à un autre classificateur. Quelle serait une bonne raison d'essayer un nouveau classificateur. Les contraintes évidentes sont la mémoire et le temps, mais existe-t-il des cas où un autre classificateur peut réellement améliorer la précision?

k-NN se généralise dans un sens très restrictif. Il utilise simplement des antérieurs de douceur (ou hypothèse de continuité). Cette hypothèse implique que les modèles qui sont proches dans l'espace d'entités appartiennent très probablement à la même classe. Aucune régularité fonctionnelle dans la distribution des motifs ne peut être récupérée par k-NN.

Ainsi, il nécessite des échantillons d'apprentissage représentatifs, qui peuvent être extrêmement grands, en particulier dans les cas d'espaces de caractéristiques très dimensionnels. Pire, ces échantillons peuvent ne pas être disponibles. Par conséquent, il ne peut pas apprendre les invariants. Si les motifs peuvent être soumis à certaines transformations sans changer d'étiquette et que l'échantillon d'apprentissage ne contient pas de motifs transformés de toutes les manières admissibles, k-NN ne reconnaîtra jamais les motifs transformés qui n'ont pas été présentés pendant la formation. Cela est vrai, par exemple, pour les images décalées ou tournées, si elles ne sont pas représentées sous une forme invariante avant d'exécuter k-NN. k-NN ne peut même pas faire abstraction de caractéristiques non pertinentes.

Un autre exemple quelque peu artificiel suit. Imaginez ce modèle appartenant à différentes classes réparties périodiquement (par exemple, conformément au sinus - s'il est inférieur à 0, alors les modèles appartiennent à une classe, et il est supérieur, alors les modèles appartiennent à une autre classe). L'ensemble d'entraînement est fini. Il sera donc situé dans une région finie. En dehors de cette région, l'erreur de reconnaissance sera de 50%. On peut imaginer la régression logistique avec des fonctions de base périodiques qui fonctionneront beaucoup mieux dans ce cas. D'autres méthodes pourront apprendre d'autres régularités dans les distributions de motifs et bien extrapoler.

Donc, si l'on soupçonne que l'ensemble de données disponible n'est pas représentatif, et qu'une invariance à certaines transformations de motifs devrait être obtenue, alors c'est le cas, dans lequel on devrait aller au-delà de k-NN.

Si vous êtes contraint par la complexité du calcul, les arbres de décision (Quinal, 1986) sont difficiles à battre (en particulier lorsqu'un framework propose une conversion directe du modèle DT en un tas d' ifinstructions - comme Accord.NET ).

Pour les données de grande dimension, la notion de distance, sur laquelle est basé le k-NN, devient sans valeur (Kriegel, Kröger, Zimek, 2009) (aussi: article Wikipedia ). Ainsi, d'autres classificateurs, comme SVM (Corter, Vapnik, 1995) ou Random Forests (Breiman, 2001) , pourraient mieux fonctionner.

Références:

• Kriegel, Hans-Peter; Kröger, Peer; Zimek, Arthur (2009), «Clustering high-dimensions data: A survey on subpace clustering, pattern-based clustering, and correlation clustering», ACM Transactions on Knowledge Discovery from Data (New York, NY: ACM) 3 (1): 1–58

• Cortes, Corinna; et Vapnik, Vladimir N .; "Support-Vector Networks", Machine Learning, 20, 1995

• Leo Breiman. 2001. Forêts aléatoires. Mach. Apprendre. 45, 1 (octobre 2001), 5-32.

• JR Quinlan. 1986. Induction d'arbres de décision. Mach. Apprendre. 1, 1 (mars 1986), 81-106.

kNN est utile pour les grands échantillons de données

Cependant, ses inconvénients sont:

1. Biaisée par la valeur de k.
2. Complexité de calcul
3. Limitation de mémoire
4. Être un algorithme d'apprentissage paresseux supervisé
5. Facilement trompé par des attributs non pertinents.
6. La précision des prédictions peut rapidement se dégrader lorsque le nombre d'attributs augmente.

Il n'est généralement efficace que si les données d'entraînement sont volumineuses et que l'entraînement est très rapide.