En 1999, Beyer et al. a demandé: Quand le "plus proche voisin" a-t-il un sens?
Existe-t-il de meilleures façons d'analyser et de visualiser l'effet de la planéité des distances sur la recherche NN depuis 1999?
Un ensemble de données [donné] fournit-il des réponses significatives au problème 1-NN? Le problème des 10 NN? Le problème du 100-NN?
Comment les experts aborderaient-ils cette question aujourd'hui?
Modifications lundi 24 janvier:
Que diriez-vous de "distance blanche" comme un nom plus court pour "planéité de distance avec une dimension croissante"?
Un moyen simple de voir le "voile blanc de distance" consiste à exécuter 2-NN et à tracer les distances entre le voisin le plus proche et le deuxième voisin le plus proche. Le graphique ci-dessous montre dist 1 et dist 2 pour une gamme de nclusters et de dimensions, par Monte Carlo. Cet exemple montre un assez bon contraste de distance pour la différence absolue mise à l'échelle | dist 2 - dist 1 |. (Les différences relatives | dist 2 / dist 1 | → 1 comme dimension → ∞, deviennent donc inutiles.)
L'emploi d'erreurs absolues ou relatives dans un contexte donné dépend bien entendu du "vrai" bruit présent: difficile.
Suggestion: exécutez toujours 2-NN; 2 voisins sont utiles lorsqu'ils sont proches et utiles lorsqu'ils ne le sont pas.
Réponses:
Je n'ai pas de réponse complète à cette question, mais je peux donner une réponse partielle sur certains aspects analytiques. Avertissement: je travaille sur d'autres problèmes depuis le premier article ci-dessous, il est donc très probable qu'il y ait d'autres bonnes choses dont je ne suis pas au courant.
Tout d'abord, je pense qu'il convient de noter que malgré le titre de leur article "Quand est le" plus proche voisin "significatif", Beyer et al ont répondu à une question différente, à savoir quand NN n'a pas de sens. Nous avons démontré l'inverse de leur théorème, sous quelques hypothèses supplémentaires légères sur la taille de l'échantillon, dans When Is 'Nearest Neighbor' Signful: A Converse Theorem and Implications. Journal of Complexity, 25 (4), août 2009, pp 385-397.et a montré qu'il existe des situations où (en théorie) la concentration des distances ne se produira pas (nous donnons des exemples, mais en substance le nombre de caractéristiques non sonores doit croître avec la dimensionnalité, donc bien sûr, elles surviennent rarement dans la pratique). Les références 1 et 7 citées dans notre article donnent quelques exemples de façons dont la concentration de distance peut être atténuée dans la pratique.
Un article de mon superviseur, Ata Kaban, examine si ces problèmes de concentration à distance persistent malgré l'application de techniques de réduction de dimensionnalité dans On the Concentration Awareness of Certain Data Reduction Techniques. La reconnaissance de formes. Vol. 44, numéro 2, février 2011, pp.265-277. . Il y a aussi de belles discussions là-dedans.
la source
Vous pourriez tout aussi bien être intéressé par l' analyse des composantes du quartier par Goldberger et al.
Ici, une transformation linéaire est apprise pour maximiser les points correctement classés attendus via une sélection de voisinage stochastique la plus proche.
Comme effet secondaire, le nombre (attendu) de voisins est déterminé à partir des données.
la source