Discussion :

[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 !

[Aleph69]

Bonjour,

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

Cette distance est définie à partir de la norme de l'espace des suites l^p :

||x||_p=(|x1|^p+|x2|^p+...+|xn|^p)^{1/p}

Cela pourra éventuellement t'aider de regarder les propriétés de cet espace normé sur google.

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)

La première chose est de savoir si tes entiers correspondent à des variables quantitatives ou qualitatives. Dans le dernier cas, utiliser des distances n'a pas vraiment de sens. On utilise plutôt des dissimilarités, dont les distances ne sont que des cas particuliers : une dissimilarité ne vérifie ni l'axiome de séparation, ni l'inégalité triangulaire. Elle est seulement symétrique, alternée et positive.

La distance canonique entre deux ensembles est l'infinimum parmi les quantités dist(x,y) où x appartient au premier ensemble et y au second. Je te conseille de regarder ce qui se fait dans le cadre de la classification hiérarchique par agrégation (typiquement la classification ascendante hiérarchique). Tu trouveras plein d'exemples de dissimilarités et de distances entre individus et ensembles.

[Alexis.M]

Tu as la famille des distances de type Mahalanobis.
d(x,y)^2 = (x-y)^T M (x-y)

La distance de Mahalanobis correspond à M = S^-1
où S^-1 est l'inverse de la matrice de covariance des points de
données.

Avec M=I (l'identité) tu as la distance euclidienne habituelle.

Il existe aussi des algorithmes qui apprennent explicitement la matrice M de sorte à regrouper au mieux les classes. Tu as par exemple
"Large Margin Nearest Neighbors" ou "Pairwise constrained component analysis".

[Alexis.M]

Sinon tu peux construire des mesures de distances basées sur des noyaux (semi-définis positfs) autre que le noyau linéaire.

Pour un noyau SDP k(x,y), la distance correspondante est:

d(x,y)^2 = k(x,x) + k(y,y) - 2*k(x,y)

Dans le cas linéaire, le noyau est simplement k(x,y) = x^T y est la distance
correspondante est simplement la distance euclidienne.

Sinon pour des histogrammes du peux utiliser le noyau chi^2:
k(x,y) = \sum_i 2*x_i*y_i / (x_i + y_i)
ce qui donne la distance
d(x,y)^2 = \sum_i (x_i - y_i)^2/(x_i + y_i)
(attention au cas d(0,0))


Un noyau très utiles car plus "local" est le noyaux gaussien

k(x,y) = exp( - alpha * d(x,y)^2 )

qui utilise typiquement la distance d(x,y) euclidienne où tout autre mesure de distance plus adaptée comme la mesure de distance issue du noyau chi^2 dans le cas d'histogrammes.

Faire attention a normaliser correctement les données si besoins (norme l1 pour les histogrammes, par exemple)

Sinon il existe d'autres méthodes de classification que les plus proches voisins, comme les machines à vecteurs supports (SVM), qui utilisent soit la distance euclidienne soit différents noyaux.

[M.Max]

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)

Fais des recherches de type "Shape matching", la littérature est pléthorique.

D'ailleurs cet article liste qlq formules de calcul de distance, cela pourrait t'intéresser : Shape Matching: Similarity Measures and Algorithms,Remco C. Veltkamp