Gérer les liens, les poids et voter en kNN

Je programme un algorithme kNN et j'aimerais savoir ce qui suit:

Tie-breaks:

1. Que se passe-t-il s'il n'y a pas de gagnant clair dans le vote majoritaire? Par exemple, tous les k voisins les plus proches sont de classes différentes, ou pour k = 4, il y a 2 voisins de classe A et 2 voisins de classe B?
2. Que se passe-t-il s'il n'est pas possible de déterminer exactement k voisins les plus proches car il y a plus de voisins qui ont la même distance? Par exemple, pour la liste des distances, (x1;2), (x2;3.5), (x3;4.8), (x4;4.8), (x5;4.8), (x6;9.2)il ne serait pas possible de déterminer les k = 3 ou k = 4 voisins les plus proches, car les 3e à 5e voisins ont tous la même distance.

Poids:

1. J'ai lu qu'il est bon de pondérer les k-voisins les plus proches avant de sélectionner la classe gagnante. Comment ça marche? C'est-à-dire comment les voisins sont-ils pondérés et comment la classe est-elle alors déterminée?

Alternatives au vote majoritaire:

1. Existe-t-il d'autres règles / stratégies pour déterminer la classe gagnante que le vote majoritaire?

Le moyen idéal de rompre une égalité pour un k voisin le plus proche à mon avis serait de diminuer k de 1 jusqu'à ce que vous ayez rompu l'égalité. Cela fonctionnera toujours quel que soit le schéma de pondération des voix, car une égalité est impossible lorsque k = 1. Si vous deviez augmenter k , en attendant votre schéma de pondération et le nombre de catégories, vous ne seriez pas en mesure de garantir une égalité.

Lorsque vous faites kNN, vous devez garder une chose à l'esprit, à savoir que ce n'est pas un algorithme strictement dérivé mathématiquement, mais plutôt un classificateur / régresseur simple basé sur une intuition - la fonction sous-jacente ne change pas beaucoup lorsque les arguments ne changent pas beaucoup. Ou en d'autres termes, la fonction sous-jacente est localement presque constante. Avec cette hypothèse, vous pouvez estimer la valeur de la fonction sous-jacente en tout point donné, par une moyenne (éventuellement pondérée) des valeurs des k points les plus proches.

En gardant cela à l'esprit, vous pouvez réaliser qu'il n'y a pas d'impératif clair sur ce qu'il faut faire quand il n'y a pas de gagnant clair au vote majoritaire. Vous pouvez toujours utiliser un k impair ou utiliser une pondération injective.

Dans le cas où les voisins 3 à 5 sont à la même distance du point d'intérêt, vous pouvez soit utiliser seulement deux, soit utiliser tous les 5. Encore une fois, gardez à l'esprit que kNN n'est pas un algorithme dérivé d'une analyse mathématique complexe, mais juste un intuition simple. C'est à vous de décider comment vous souhaitez gérer ces cas particuliers.

$\frac{1}{||x-y||^2}$

Cette année, Samory Kpotufe et Abdeslam Boularias ont également publié un article intéressant sur le NIPS, qui aborde la question de trouver la bonne pondération. Leur intuition générale est que la fonction sous-jacente varie différemment dans différentes directions (c'est-à-dire que ses différentes dérivées partielles sont de magnitude différente), il serait donc sage dans un certain sens de changer les métriques / pondérations en fonction de cette intuition. Ils prétendent que cette astuce améliore généralement les performances de kNN et de la régression du noyau, et je pense qu'ils ont même des résultats théoriques pour étayer cette affirmation (bien que je ne sois pas sûr de ce que prétendent ces résultats théoriques, je n'ai pas eu le temps d'aller dans tout le document). Le document peut être téléchargé gratuitement à partir de leurs sites, ou après googler "Gradient Weights help Nonparametric Regressors".

Maintenant, vous voudrez probablement savoir comment trouver le bon k, la métrique, la pondération, l'action à effectuer quand il y a des tirages et ainsi de suite. Ce qui est triste, c'est qu'il est fondamentalement difficile d'arriver aux bons hyperparamètres après une réflexion approfondie, vous devrez probablement tester différents groupes d'hyperparamètres et voir lesquels fonctionnent bien sur un ensemble de validation. Si vous avez des ressources de calcul et que vous souhaitez arriver automatiquement aux bons paramètres avec un bon ensemble d'hyperparamètres, il y a une idée récente (que j'aime beaucoup) d'utiliser des processus gaussiens pour une optimisation sans dérivé dans ce paramètre.

Permettez-moi d'élaborer - la recherche de l'ensemble d'hyperparamètres (c'est-à-dire qui minimisent l'erreur sur les données de validation) peut être considérée comme un problème d'optimisation. Malheureusement, dans ce paramètre, nous ne pouvons pas obtenir le gradient de la fonction que nous essayons d'optimiser (ce que nous voulons généralement faire, pour effectuer une descente de gradient ou d'autres méthodes plus avancées). Les processus gaussiens peuvent être utilisés dans ce contexte, pour trouver des ensembles d'hyperparamètres, qui ont de grandes chances, de fonctionner mieux que les meilleurs que nous avons trouvés jusqu'à présent. Par conséquent, vous pouvez exécuter l'algorithme de manière itérative avec un ensemble d'hyperparamètres, puis demander au processus gaussien quels sont les meilleurs à essayer ensuite, essayez-les, etc.

Pour plus de détails, recherchez le document "Practical Bayesian Optimization of Machine Learning Algorithms" par Jasper Snoek, Hugo Larochelle et Ryan P Adams (également disponible sur leurs sites Web ou via Google).

À propos de cette partie de lien, la meilleure idée de base pour les liens est généralement la rupture aléatoire, donc sélectionner une classe aléatoire de tous les gagnants et sélectionner au hasard un sous-ensemble d'objets liés suffisamment grand pour remplir k.

Une telle solution souligne le fait qu'il s'agit de cas pathologiques qui ne fournissent tout simplement pas suffisamment d'informations pour prendre une décision en régime kNN. BTW s'ils sont communs à vos données, peut-être devriez-vous essayer une distance plus différenciante?

Une façon possible consiste à faire augmenter ou diminuer automatiquement l'algorithme jusqu'à ce que vous obteniez un gagnant clair.