Distance métrique et malédiction des dimensions

Certains où j'ai lu une note que si vous avez beaucoup de paramètres et que vous essayez de trouver une "métrique de similitude" entre ces vecteurs, vous pouvez avoir une "malédiction de dimensioalité". Je crois que cela signifiait que la plupart des scores de similitude seront égaux et ne vous donneront aucune information utile. En d'autres termes, presque tous les vecteurs partenaires auront un score de distance moyenne qui n'est pas utile pour la catégorisation ou le regroupement, etc. $(x_1, x_2, \ldots, x_n)$

Savez-vous où je peux en savoir plus à ce sujet?

Y a-t-il des mesures qui souffrent moins de cet effet?

distance similarities metric Gerenuk
la source

Réponses:

Quelques observations classiques sur les distances dans les données de grande dimension:

K. Beyer, J. Goldstein, R. Ramakrishnan et U. Shaft, ICDT 1999: "Quand les voisins les plus proches ont-ils un sens?"
CC Aggarwal, A. Hinneburg et DA Keim, ICDT 2001: "Sur le comportement surprenant des métriques de distance dans l'espace de grande dimension"

Quelques recherches plus récentes à ce sujet, qui impliquent des voisins et des hubs partagés:

ME Houle, H.-P. Kriegel, P. Kröger, E. Schubert et A. Zimek, SSDBM 2010: "Les distances entre voisins partagés peuvent-elles vaincre la malédiction de la dimensionnalité?"
T. Bernecker, ME Houle, H.-P. Kriegel, P. Kröger, M. Renz, E. Schubert et A. Zimek, SSTD 2011: "Qualité des classements de similarité dans les séries chronologiques"
N. Tomašev, M. Radovanović, D. Mladenić et M. Ivanović. Adv. KDDM 2011: "Le rôle du hubness dans le clustering de données de grande dimension"
Je ne me souviens pas des autres, cherchez "Hubness", c'était leur observation de grande dimension

Celles-ci sont intéressantes, car elles mettent en évidence certains malentendus populaires concernant la malédiction de la dimensionnalité. En substance, ils montrent que les résultats théoriques - qui supposent que les données sont iid - peuvent ne pas être généralement vrais pour les données qui ont plus d'une distribution. La malédiction entraîne des problèmes numériques et une perte de discrimination au sein d' une même distribution, tout en facilitant encore la différenciation de deux distributions bien séparées.

Cela devrait être assez évident. Supposons que vous ayez des objets qui sont iid dans chaque dimension et un autre ensemble d'objets qui sont iid dans chaque dimension. La différence entre les objets de deux ensembles différents sera toujours magnitudes supérieure à une distance dans un seul ensemble, et le problème sera même obtenir plus facile avec dimensionnalité de plus en plus . $A_i\sim \mathcal{N}(0;1)$ $B_i\sim \mathcal{N}(100;1)$

Je recommande la lecture de cet ouvrage de Houle et al., En grande partie parce qu'il montre qu'en affirmant que "ces données sont de grande dimension et qu'en raison de la malédiction de la dimensionnalité, elles ne peuvent pas être analysées", vous pourriez rendre les choses un peu trop faciles. C'est toujours une ligne qui est utilisée partout. "Notre algorithme ne fonctionne que pour les données de faible dimension, en raison de la malédiction de la dimensionnalité." "Notre indice ne fonctionne que jusqu'à 10 dimensions, en raison de la malédiction de la dimensionnalité." Yadda yadda yadda. Beaucoup de ces déclarations montrent simplement que ces auteurs n'ont pas compris ce qui se passe à haute dimensionnalité dans leurs données et algorithme (ou avaient besoin d'une excuse). Houle et al. ne résout pas complètement le casse-tête (encore? c'est assez récent), mais ils reconsidèrent au moins un grand nombre des déclarations populaires.

Après tout, si la dimensionnalité élevée était un gros problème, comment se fait-il que dans l'exploration de texte, les gens utilisent volontiers les dimensionnalités de l'ordre de 10000-100000, alors que dans d'autres domaines, les gens abandonnent à seulement 10 dimensions?!?

Quant à la deuxième partie de votre question: la similitude cosinus semble moins souffrir de la dimensionnalité . En dehors de cela, tant que vous souhaitez différencier différentes distributions, contrôler la précision numérique et ne pas compter sur des seuils choisis à la main (car vous devrez peut-être les donner avec beaucoup de chiffres significatifs), les -Norms classiques devraient toujours convenir. $L_p$

Cependant, Cosine est également affecté par la malédiction de la dimensionnalité , comme indiqué dans:

M. Radovanović, A. Nanopoulos et M. Ivanović, SIGIR 2010. «Sur l'existence de résultats obstinés dans les modèles spatiaux vectoriels».

A QUIT - Anony-Mousse
la source

Aggarwal CC, Hinneburg A., Keim, DA (2001), «Sur le comportement surprenant des métriques de distance dans l'espace à haute dimension»
Beyer K., Goldstein J., Ramakrishnan R., Shaft U. (1999), «Quand les voisins les plus proches ont-ils un sens?», Procédures de conférence ICDE.

user603
la source

Cela semble intéressant :) J'espère pouvoir en obtenir une copie. Savez-vous s'il existe des solutions à ce problème avec des mesures ordinaires?

Gerenuk

(+1) cela semble très intéressant.

Elvis

@Gerenuk: que voulez-vous dire par des mesures «ordinaires»? En outre, les deux documents sont disponibles. en ligne, non fermé, en tant que pdfs

user603

Merci. Je pense que je les ai trouvés par nom de titre. Par métrique ordinaire (je pense), je veux normes . La question est donc de savoir s'il existe un simple chercheur de similitudes qui fait un meilleur travail que les normes .

L_{k}

$L_k$

L_{k}

$L_k$

Gerenuk

Les normes L_p fractionnaires masquent uniquement le problème. Je crois que le résultat tend alors vers quelque chose comme la différence d'attribut minimale, qui pour un nombre élevé de dimensions devient tout aussi vide de sens dans la pratique. Cela ne résout que le problème de l'augmentation des nombres. La réduction de dimension fonctionne dans certains cas, mais considérez le cas quand elle ne vous mène pas plus loin. Et alors? De plus, la réduction de dimension est essentiellement "les dimensions 640k devraient être suffisantes pour n'importe qui". Le texte est généralement de l'ordre de 10 ^ 5. Et la vidéo?

A QUIT - Anony-Mousse

Aussi:

Robert J. Durrant, Ata Kabán: Quand le «plus proche voisin» a-t-il un sens: un théorème inverse et ses implications. J. Complexity 25 (4): 385-397 (2009)
Ata Kabán: Sur la concentration à distance de la conscience de certaines techniques de réduction de données. Reconnaissance de formes 44 (2): 265-277 (2011)
Ata Kabán: Détection non paramétrique de distances sans signification dans des données de grande dimension. Statistiques et informatique 22 (2): 375-385 (2012)

axk
la source