[Algo] Les K voisins les plus proches

Version imprimable

21/05/2007, 17h23
GyZmoO

[Algo] Les K voisins les plus proches

Salut a tous !

Je rencontre un problème : je souhaite classer un texte dans un classe A ou B. Je dispose de deux tableaux de X cases qui contiennent les distances du texte que je veux classer avec des textes témoins de deux classes A et B. Pour déterminer la classe du texte, j'applique l'algo des K plus proches voisins. Cependant, par exemple si K vaut 11, qu'on trouve 6 voisins de classe A et 5 de classe B, naïvement on classe le texte dans la classe A. Seulement, il se peut que les 5 voisins de la classe B soient bien plus proches que les 6 de l'autre classe. Mon problème : il me faudrait pondérer ces résultats pour prendre en compte ça ! Et je sais pas du tout comment m'y prendre, vous auriez une idée svp ? J'ai bien regardé sur le net, et effectivement chaque fois qu'il est question de K voisins, y'a une histoire de pondération, mais quelle est exactement l'opération à appliquer??

J'espère avoir été clair !

Merci pour vos (nombreuses, j'espère :D )futures réponses !
21/05/2007, 19h51
pseudocode

heu...:roll:

Il suffit de ponderer chaque voisin par une fonction inverse de la distance: plus la distance au voisin est faible, plus le poids est fort. non ?

par exemple: Poid(voisin) = 1 / ( 1 + distance(voisin) )
22/05/2007, 09h50
GyZmoO

Ok merci pour ta réponse, et dans le cas ou j'ai le contraire c'est a dire qu'a la place d'avoir les distances (c'est a dire plus la distance est grande moins les fichiers se ressemblent) j'ai un contenu commun en information (plus ce contenu est grand, plus les fichiers se ressemblent) il me suffit de faire ça :

1/(1+ContenuCommun) et la, plus le poinds va être faible, plus les 2 fichiers se ressemblent ???

PS : je suis une quiche a ce niveau :D
22/05/2007, 10h16
Matthieu Brucher

(Ca ne donen pas envie, ce manque de réflexion...)

1/(1+x) augmente quand x tend vers 0, donc plus les points sont proches, plus le poids est fort (cours de terminale...)
22/05/2007, 10h32
GyZmoO

Oui non j'entend bien, mais dans le cas ou je n'ai pas une distance mais l'inverse d'une distance (plus la valeur est grande plus les points sont proches) si je fais
1/1+MaValeur, <------- plus ça, ça va être petit, plus les points seront proches alors, mea culpa peut être me suis je mal exprimé, mais j'aimerai savoir si y'a une autre opération a faire dans le cas ou on a l'inverse d'une distance.

Merci.
22/05/2007, 10h35
Matthieu Brucher

...
C'est pas pour rien que c'est la distance qu'on met ici. Ca a presque le même comportement que si tu mets à la place l'inverse de la distance.
22/05/2007, 10h40
GyZmoO

Ok merci, j'ai eu un peu de mal a saisir :oops: Sorry .
22/05/2007, 15h20
pseudocode

Citation:

Envoyé par GyZmoO

j'aimerai savoir si y'a une autre opération a faire dans le cas ou on a l'inverse d'une distance.

et bien utilise cette valeur directement comme un poids.
25/05/2007, 11h33
ol9245

Citation:

Envoyé par pseudocode

et bien utilise cette valeur directement comme un poids.

oui, c'est bien ca. mais tu va certainement preferer prendre le carre de ton poids car 1 seul mot avec 6 lettres en commun vaut bien mieux que 6 mots avec une seule lettre. au carre, tu obtiens 6*6 bien meilleur que 6*(1*1).
OL