Dans Elements of Statistical Learning , un problème est introduit pour mettre en évidence les problèmes de k-nn dans les espaces de grande dimension. Il y a points de données qui sont uniformément distribués dans une boule d'unité dimensionnelle.
La distance médiane de l'origine au point de données le plus proche est donnée par l'expression:
Lorsque , les pauses de formule vers le bas à la moitié du rayon de la balle, et je peux voir comment le point le plus proche se rapproche de la frontière comme p → ∞ , rendant ainsi l'intuition derrière KNN briser les dimensions élevées. Mais je ne comprends pas pourquoi la formule dépend de N. Pourriez-vous clarifier quelque chose?
Le livre aborde également ce problème en déclarant: "... la prédiction est beaucoup plus difficile près des bords de l'échantillon d'apprentissage. Il faut extrapoler à partir des points d'échantillonnage voisins plutôt qu'interpoler entre eux". Cela semble être une déclaration profonde, mais je n'arrive pas à comprendre ce que cela signifie. Quelqu'un pourrait-il reformuler?
la source
Réponses:
Le volume d'une hyperbille de dimension de rayon r a un volume proportionnel à r p .p r rp
Donc, la proportion du volume supérieure à une distance de l'origine est r p - ( k r ) pkr .rp−(kr)prp=1−kp
La probabilité que tous les points d' choisis au hasard sont plus d'une distance k r de l'origine est ( 1 - k p ) N . Pour obtenir la distance médiane au point aléatoire le plus proche, définissez cette probabilité égale à 1N kr (1−kp)N . Donc(1-kp)N=112
la source
Et maintenant sans agiter la main
Ainsi, si nous avons iid uniformément distribué dans la boule unitaire en dimensions, alors où est la CDF commune des distances, . Enfin, quel est le CDF, , pour un point uniformément distribué dans la boule unitaire dans ? La probabilité que le point se trouve dans la boule de rayon r à l'intérieur de la boule de rayon unitaire est égale au rapport des volumes:N Xi p
Ainsi, la solution à
est
De plus , votre question sur la dépendance de la taille de l' échantillon, . Pour fixe, au fur et à mesure que la balle se remplit de plus de points, la distance minimale à l'origine devrait naturellement devenir plus petite.pN p
Enfin, il y a quelque chose qui cloche dans votre rapport de volumes. Il semble que devrait être le volume de la boule unitaire dans .R pk Rp
la source
Aussi concis mais en mots:
Nous voulons trouver la distance médiane du point le plus proche de l'origine en points uniformément répartis dans la balle à l'origine du rayon unitaire en dimensions. La probabilité que la plus petite distance dépasse , (appelons cette expression de quantité [1]) est la puissance de la probabilité qu'un seul point uniformément distribué dépasse , en raison de l'indépendance statistique. Ce dernier est un moins la probabilité qu'un seul point uniformément distribué soit inférieur à . Ce dernier est le rapport des volumes de la boule de rayon à la boule de rayon unitaire, ou . Nous pouvons maintenant écrire l'expression [1] commeN p r Nth r r r rp
Pour trouver la médiane de la distribution du minimum des distances, définissez la probabilité ci-dessus à et résolvez pour , en obtenant la réponse.1/2 r
la source