Distance entre deux ensembles de valeurs

[sonyc91]

Bonjour,

je travaille actuellement sur un projet à la fac en fouille de données. L'objectif est de prédire la classe (positive ou négative) d'un certain nombre d'instances d'une base de validation, à partir d'instances d'une base d'apprentissage pour lesquelles la classe est connue.

J'ai choisi d'utiliser un algorithme de type proches voisins pour faire ma prédiction. Je calcule donc la distance entre l'instance à classer et les instances de ma base d'apprentissage et je procède par un vote à la majorité parmi les plus proches voisins pour choisir la classe de l'instance à classer.

Je crois comprendre qu'on appelle distance de Minkowski une distance telle que :

J'ai essayé de calculer mes distances avec différentes valeurs de p mais les résultats ne changent pas beaucoup en fonction de p. J'aimerais donc tester d'autres distances.

Ma question est donc la suivante : savez-vous s'il existe d'autres formules pour calculer la distance entre deux ensembles de valeurs ? (Les valeurs sont essentiellement des entiers)

Merci de m'avoir lu !

[arthur.27]

Bonjour, et bienvenue sur le forum.

Après avoir considéré , tu peux prendre la limite de cette valeur lorsque p tend vers l'infini.
Cela donne :.

Cette idée est probablement intéressante pour toi par son interprétation: tu vois que pour , on ne considère que la valeur maximale de . Les autres valeurs de i ne sont pas du tout prises en compte. C'est donc généralement un très mauvais indicateur : il est extrêmement sensible aux valeurs aberrantes, et ne tient pas compte de la globalité de l'instance.

De retour à ta formule , plus p sera grand, plus on s'approchera de la situation décrite ci-dessus.

Fais des tests avec des valeurs aberrantes, et tu verras leur influence diminuer au fur et à mesure que p diminue.


Tu peux encore trouver d'autres formules de la distance, adaptées au cas où certaines valeurs de i
seraient plus importantes que d'autres.

Tu introduis alors des coefficients positifs et tu te retrouves avec la formule : .

[sonyc91]

Merci pour la réponse !

Bonjour, et bienvenue sur le forum.

Après avoir considéré , tu peux prendre la limite de cette valeur lorsque p tend vers l'infini.
Cela donne :.

Cette idée est probablement intéressante pour toi par son interprétation: tu vois que pour , on ne considère que la valeur maximale de . Les autres valeurs de i ne sont pas du tout prises en compte. C'est donc généralement un très mauvais indicateur : il est extrêmement sensible aux valeurs aberrantes, et ne tient pas compte de la globalité de l'instance.

Effectivement, quand j'augmente p, les performances ont tendance à se dégrader.

De retour à ta formule , plus p sera grand, plus on s'approchera de la situation décrite ci-dessus.

Fais des tests avec des valeurs aberrantes, et tu verras leur influence diminuer au fur et à mesure que p diminue.

Tout à fait ! Au moins c'est cohérent !

Tu peux encore trouver d'autres formules de la distance, adaptées au cas où certaines valeurs de i
seraient plus importantes que d'autres.

Tu introduis alors des coefficients positifs et tu te retrouves avec la formule : .

Effectivement, j'ai essayé de pondéré ma distance avec p=2, mais ça ne donne pas de très bon résultats et je ne suis pas certains qu'une optimisation des pondérations soit une bonne idée. J'ai l'impression que je vais faire du surapprentissage, non ?

Hors distance de Minkowski, pas d'autre moyen de mesurer une distance alors ?

[fatal_error]

salut,

On peut représenter ton ensemble de points par un vecteur v, qu'on dit qu'il appartient à un espace vectoriel normé.
Et du coup, l'idée, c'est de munir cet espace d'une norme autre que la norme euclidienne.

Genre par exemple, si ton ensemble de points que j'appèle x est de taille n, et qu'on pose la matrice A=I_n, alors le produit scalaire est donné par phi(x,y) = x'Ay et la distance d(x,y) est donnée par sqrt(Q(x-y)) où Q(x) = x'Ax
et sqrt(Q(x)) est une norme, parce que A est définie positive.

Donc t'as qu'à chopper A une forme définie positive (toutes les valeurs propres positives), et ca te file une distance associée.

Par exemple, tu prends A la matrice de covariance, semi positive, donc tu peux rajouter 0.1 sur la diago (pour avoir les valeurs propres strictement positives), et ca te donne la distance
d(x,y) = sqrt((x-y)A(x-y))

Tu peux aussi envisager de mapper ton x vers un ensemble F dans lequel tu as une forme définie positive en tant que norme