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

9

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?


la source
Est-ce purement académique ou doit-il être utilisé dans l'industrie?
Dr Rob Lang
1
La plupart de nos applications sont déployées dans l'industrie (donc l'empreinte mémoire et le temps de calcul sont des problèmes)

Réponses:

3

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.


la source
Merci pour votre réponse (et merci BartoszKP pour avoir essayé de l'améliorer). Il est vrai que knn ne peut pas trouver de modèles qui nécessitent une transformation (sauf si vous commencez à utiliser une métrique de distance étrange (et incorrecte)). C'est une bonne raison d'essayer un autre classificateur, je suppose que svm est alors un choix évident. Je ne suis pas suffisamment familier avec svm pour le dire, mais ne nécessiterait-il pas une connaissance spécifique du modèle que vous recherchez pour définir le noyau?
Oui. Le choix du noyau dépendra des modèles. Le noyau gaussien aura des propriétés similaires à la méthode k-NN. D'autres noyaux standard peuvent également sembler inappropriés. Cependant, au moins, on pourrait essayer de les utiliser.
Comme l'indique @ Necro0x0Der, toute amélioration dans ce sens dépendrait du fait que le modèle (dans l'exemple sinusoïdal, la périodicité) soit naturel pour la paramétrisation. C'est-à-dire que la paramétrisation (choix du noyau) définit la structure (en fait, la métrique) de l'espace de représentation. Si vous pouvez déterminer (peut-être par une supposition éclairée) une structure appropriée par certains moyens, essayez de paramétrer le modèle en conséquence. Notez qu'en fin de compte, cela permet à votre classificateur de trouver facilement certains types de fonctionnalités pertinentes.
3

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:

BartoszKP
la source
La dimension élevée n'est bien sûr pas une limite fixe, dans la plupart des cas, nos caractéristiques sont suffisamment expressives pour que la distance fonctionne. Bien sûr, cela pourrait être un point important. J'aurais peut-être dû clarifier avec un exemple. Disons que nous avons un classificateur qui a une précision de 93%, c'est acceptable, mais maintenant nous pouvons soit essayer d'améliorer le classificateur, soit trouver de nouvelles fonctionnalités. Tout dépend des nouvelles fonctionnalités possibles et des données, mais je cherchais des lignes directrices sur cette décision.
@Rhand me semble que c'est une décision au niveau de la gestion de projet. Si la solution actuelle est acceptable, pourquoi la bricoler? C'est une perte de temps. S'il n'est pas acceptable, définissez plus précisément ce que vous souhaitez améliorer (vitesse, précision, etc.).
BartoszKP
Ce n'est pas seulement la gestion de projet, la question est de savoir comment obtenir une précision maximale (c'est ma question) et quelle direction est la meilleure à prendre. Vous suggérez svm et random forest parce que la dimensionnalité peut être trop élevée, c'est une possibilité que je pourrais expérimenter pour voir si la précision s'améliore et c'est le genre de réponse que je cherchais.
Eh bien, cela, d'autre part, est une question très large. Il n'y a pas de règles générales selon lesquelles le classificateur X est meilleur que Y. Vous devez simplement essayer un certain nombre de classificateurs, puis effectuer une validation croisée pour la sélection du modèle par exemple.
BartoszKP
3

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.

Iancovici
la source
Je ne regarde pas le regroupement, mais le classement
@Rhand c'est parti, merci pour la note iliasfl
Iancovici