ou

14

Quelqu'un utilise-t-il les métriques L1 ou L.5 pour le clustering, plutôt que L2 ?
Aggarwal et al., A propos du comportement surprenant des mesures de distance dans un espace de grande dimension, a déclaré (en 2001) que

L1 est toujours plus préférable que la métrique de distance euclidienne L2 pour les applications d'exploration de données à haute dimension

et a affirmé que L.5 ou L.1 peut être encore mieux.

Les raisons d'utiliser L1 ou L.5 pourraient être théoriques ou expérimentales, par exemple la sensibilité aux valeurs aberrantes / articles de Kabán, ou des programmes exécutés sur des données réelles ou synthétiques (reproductibles s'il vous plaît). Un exemple ou une image aiderait l'intuition de mon profane.

Cette question fait suite à la réponse de Bob Durrant à Quand est le plus proche voisin significatif aujourd'hui . Comme il le dit, le choix de p dépendra à la fois des données et de l'application; néanmoins, des rapports d'expérience réelle seraient utiles.


Notes ajoutées mardi 7 juin:

Je suis tombé sur "L'analyse des données statistiques basée sur la norme L1 et les méthodes associées", Dodge ed., 2002, 454p, isbn 3764369205 - des dizaines de documents de conférence.

Quelqu'un peut-il analyser la concentration de distance pour les caractéristiques exponentielles iid? Une des raisons des exponentielles est que ; un autre (non expert) est que c'est la distribution max-entropie 0; un troisième est que certains ensembles de données réels, en particulier les EIPD, semblent à peu près exponentiels.|expexp|exp

denis
la source
Il est important de mentionner qu'Aggarwal et al. dans cet article spécifique où la recherche du comportement des normes dans des problèmes comme le clustering, le plus proche voisin et l'indexation. Lp
deps_stats
vous vouliez probablement dire métriques pour les séquences plutôt que L p pour les fonctions? À mon avis, s'il existe un critère d'optimisation, le problème pourrait être résolu en l'optimisant. La règle générale sera généralement liée à la solution exacte de ce type. Quoi qu'il en soit, essayez de penser aux propriétés de la solution tricotée qui sont préférées. Après avoir lu les articles, je pourrais probablement en dire plus sur le sujet. lpLp
Dmitrij Celov
@deps_stats, oui, merci; changé le titre et la première ligne. @Dmitrij, 1) oui petit-l est correct à proprement parler, mais grand-L est commun et compréhensible. 2) oui on peut trouver un p optimal pour un problème donné, mais quel est votre premier choix, et pourquoi?
denis

Réponses:

6

La clé ici est de comprendre la «malédiction de la dimensionnalité» que les références papier. De wikipedia: lorsque le nombre de dimensions est très grand,

presque tout l'espace de grande dimension est "loin" du centre, ou, pour le dire autrement, l'espace unitaire de grande dimension peut être considéré comme composé presque entièrement des "coins" de l'hypercube, avec presque aucun "milieu"

En conséquence, il devient difficile de penser à quels points sont proches de quels autres points, car ils sont tous plus ou moins également éloignés. C'est le problème dans le premier document auquel vous avez lié.

Le problème avec un p élevé est qu'il met l'accent sur les valeurs les plus élevées - cinq carrés et quatre carrés sont à neuf unités l'un de l'autre, mais un carré et deux carrés ne sont séparés que par trois unités. Ainsi, les plus grandes dimensions (les choses dans les coins) dominent tout et vous perdez le contraste. C'est donc cette inflation de grandes distances que vous voulez éviter. Avec un p fractionnaire, l'accent est mis sur les différences dans les petites dimensions - les dimensions qui ont en fait des valeurs intermédiaires - ce qui vous donne plus de contraste.

David J. Harris
la source
(+1) Donc @David, en général y a-t-il un critère qui décrit la qualité du contraste?
Dmitrij Celov
Il semble que le premier article que vous avez lié suggère une distance maximale moins une distance minimale. Il pourrait y avoir de meilleures façons, cependant.
David J. Harris
bonne intuition claire, +1 (bien qu'il ne soit pas clair où se trouvent les coins dans les distributions de distance). Avez-vous utilisé ou L .5 sur des données réelles? L1L.5
denis
1
@Denis Merci! Je pense que le bit de coins a le plus de sens si les données sont délimitées au maximum ou dans toutes les dimensions. Quoi qu'il en soit, je crains de ne pas avoir suffisamment d'expérience avec le clustering pour avoir de bonnes intuitions sur les différentes métriques pour vous. Aussi ennuyeux soit-il, la meilleure approche pourrait être d'en essayer quelques-uns et de voir ce qui se passe
David J. Harris
1

Il existe un document utilisant la métrique Lp avec p compris entre 1 et 5 que vous pouvez consulter:

Amorim, RC et Mirkin, B., Minkowski Metric, Pondération des caractéristiques et initialisation de cluster anormale dans le clustering K-Means, Pattern Recognition, vol. 45 (3), p. 1061-1075, 2012

Télécharger, https://www.researchgate.net/publication/232282003_Author's_personal_copy_Minkowski_metric_feature_weighting_and_anomalous_cluster_initializing_in_K-Means_clustering / file / d912f508115a040b45.pdf

Homer Simpson
la source
0

Je ne sais pas si le vôtre est un problème d'inférence. Si le problème consiste à déduire un vecteur de sous certaines contraintes (qui devraient définir un ensemble convexe fermé) lorsqu'une supposition préalable dit u est donnée, alors le vecteur est inféré en minimisant la distance 2 de u sur l'ensemble de contraintes (si le u précédent n'est pas donné alors son juste en minimisant la 2 -norm). Le principe ci-dessus est justifié comme étant la bonne chose à faire dans certaines circonstances dans cet article http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1176348385 .Rnu2uu2

Ashok
la source
la tradition et Csiszar disent , Aggarwal et quelques autres L 1 ou L .5 ou ... Que faire? Sans raisons solides, je suppose que cela dépend de votre état d'esprit / de vos croyances antérieures. L2L1L.5
denis