KNN: 1 voisin le plus proche

Ma question porte sur le classificateur du plus proche voisin et concerne une déclaration faite dans l'excellent livre The Elements of Statistical Learning, par Hastie, Tibshirani et Friedman. La déclaration est (p. 465, section 13.3):

"Parce qu'il utilise uniquement le point d'apprentissage le plus proche du point d'interrogation, le biais de l'estimation du voisin le plus proche est souvent faible, mais la variance est élevée."

Le livre est disponible à
http://www-stat.stanford.edu/~tibs/ElemStatLearn/download.html

Pour commencer, nous pouvons définir ce que sont le biais et la variance. De la question "comment-peut-augmenter-la-dimension-augmenter-la-variance-sans-augmenter-le-bi" , nous avons ceci:

"Tout d'abord, le biais d'un classificateur est l'écart entre sa fonction estimée et vraie moyenne, tandis que la variance d'un classificateur est la divergence attendue de la fonction de prédiction estimée par rapport à sa valeur moyenne (c'est-à-dire à quel point le classificateur dépend du hasard échantillonnage effectué dans le kit de formation).

Par conséquent, la présence de biais indique quelque chose de fondamentalement erroné avec le modèle, alors que la variance est également mauvaise, mais un modèle avec une variance élevée pourrait au moins bien prédire en moyenne. "

Quelqu'un pourrait-il expliquer pourquoi la variance est élevée et le biais est faible pour le classificateur du plus proche voisin?

Le biais est faible, car vous ajustez votre modèle uniquement au point le plus proche. Cela signifie que votre modèle sera très proche de vos données d'entraînement.

La variance est élevée, car l'optimisation sur seulement 1 point le plus proche signifie que la probabilité que vous modélisez le bruit dans vos données est vraiment élevée. Suivant votre définition ci-dessus, votre modèle dépendra fortement du sous-ensemble de points de données que vous choisissez comme données d'entraînement. Si vous réorganisez au hasard les points de données que vous choisissez, le modèle sera radicalement différent à chaque itération. Donc

divergence attendue de la fonction de prédiction estimée par rapport à sa valeur moyenne (c.-à-d. dans quelle mesure le classificateur dépend-il de l'échantillonnage aléatoire effectué dans l'ensemble d'apprentissage)

sera élevé, car à chaque fois votre modèle sera différent.

Exemple En général, un modèle k-NN ajuste un point spécifique des données avec les N points de données les plus proches de votre ensemble d'entraînement. Pour 1-NN, ce point ne dépend que d'un seul autre point. Par exemple, vous voulez diviser vos échantillons en deux groupes (classification) - rouge et bleu. Si vous entraînez votre modèle pour un certain point p pour lequel les 4 voisins les plus proches seraient rouge, bleu, bleu, bleu (croissant par la distance à p). Ensuite, un 4-NN classerait votre point en bleu (3 fois bleu et 1 fois rouge), mais votre modèle 1-NN le classerait en rouge, car le rouge est le point le plus proche. Cela signifie que votre modèle est très proche de vos données d'entraînement et que le biais est donc faible. Si vous calculez le RSS entre votre modèle et vos données d'entraînement, il est proche de 0. Contrairement à cela, la variance dans votre modèle est élevée, car votre modèle est extrêmement sensible et ondulé. Comme indiqué ci-dessus, un brassage aléatoire de votre ensemble d'entraînement pourrait changer considérablement votre modèle. En revanche, le 10-NN serait plus robuste dans de tels cas, mais pourrait être trop rigide. Le choix de k dépend de votre ensemble de données. Cela dépend fortement de laBias-Variance-Tradeoff , qui se rapporte exactement à ce problème.

Vous devez garder à l'esprit que le classificateur de voisin le plus proche est en fait le modèle de voisin le plus complexe . Par plus complexe, je veux dire qu'il a la frontière de décision la plus dentelée et qu'il est le plus susceptible de s'ajuster. Si vous utilisez un classificateur N plus proche voisin (N = nombre de points d'entraînement), vous classerez tout comme la classe majoritaire. Différentes permutations des données vous donneront la même réponse, vous donnant un ensemble de modèles qui ont une variance nulle (ils sont tous exactement les mêmes), mais un biais élevé (ils sont tous systématiquement faux). Réduire le réglage de K vous rapproche de plus en plus des données d'entraînement (biais faible), mais le modèle dépendra beaucoup plus des exemples d'entraînement choisis (variance élevée).

Voici un article de blog très intéressant sur le biais et la variance. La section 3.1 traite de l'algorithme knn et explique pourquoi un k faible conduit à une variance élevée et à un biais faible.

La figure 5 est très intéressante: vous pouvez voir en temps réel comment le modèle évolue alors que k augmente. Pour un k faible, il y a beaucoup de sur-ajustement (certaines "îles" isolées) qui conduit à un biais faible mais à une variance élevée. Pour un k très élevé, vous avez un modèle plus lisse avec une faible variance mais un biais élevé. Dans cet exemple, une valeur de k entre 10 et 20 donnera un modèle de descente suffisamment général (variance relativement faible) et suffisamment précis (biais relativement faible).