Discussion :

[xSonnyx]

Bonjour à toutes et tous,

Dans le but de faire un petit système de recommandations je dispose d'items qui possède un certain nombre (variable) de tags (variés). Ces tags possèdent eux même un poids en fonction de leur importance.

J'ai commencé à testé ce que donné les différentes fonctions de calcul de distance (jaccard, euclidienne, manhattan etc), à appliquer sur les vecteurs de poids de tags que les deux items possèdent en commun. C'est intéressant mais en plus de cela il faut que je prenne en compte deux élèments :
- plus les deux items ont de tags en commun, plus la recommandation doit être forte
- plus les poids sont forts, plus la recommandation doit l'être aussi.

J'imagine qu'il s'agit principalement de math (à moins qu'il n'existe des méthodes déjà toutes faites en python ou java, mais je n'ai, pour l'instant, pas trouvé), domaine où je suis loin d'exceller. Je peut bien bricoler un truc, mais un peu d'aide/conseil afin d'être le plus optimal possible n'est pas de refus

[tbc92]

Tu dis que tu as les outils pour calculer différentes distance ( Euclidiennes, Manhattan...), Et ce qui t'embête, c'est ces 2 critères supplémentaires que tu dois intégrer.

Critère n°1 : plus les deux items ont de tags en commun, plus la recommandation doit être forte
C'est exactement ce que tu obtiens déjà avec une distance euclidienne ou une distance de Manhattan toute bête. C'est juste une façon un peu différente de formuler les choses.

Critère n°2 : plus les poids sont forts, plus la recommandation doit l'être aussi.
Si tu as intégré les poids dans les calculs de distance, alors tu as déjà pris en compte ce critère. Rien à changer dans ton process.

Distance_manhattan (A,B) = Somme ( Poids des Tags pour lesquels A et B n'ont pas la même information)

[xSonnyx]

Merci pour ta réponse

J'ai du mal m'exprimer ou alors quelque chose m'échappe (ce qui est tout à fait possible).

Je reformule donc mon problème en étant plus explicite. Je veux, dans une base de donnée, admettons d'images, trouver pour chaque image, les plus similaires.
Chaque image possède des tags, et chaque tag est pondéré.
Ce qui donné par exemple :
photo1 : {'soleil':0.2, 'plage':0.5, 'vacances':0.9, 'farniente':0.01}
photo2 : {'vacances':0.8, 'montagne':0.4, 'soleil':0.1}
photo3 : {'plage':0.4, 'boissons':0.5, 'farniente':0.05, 'soleil':0.4}

Je veux donc que plus il y a de tags en commun plus la recommendation est forte (à pondéré avec leur distance evidemment).
Et que les poids plus fort pèse davantage que les plus faibles.

Or, de ce qu'il me semble la distance de manhattan c'est la somme des valeurs absolues des différences entre le poid de chaque tag que les deux photos on en commun. En python j'ai utilisé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

sum(abs(a-b) for a,b in zip(x,y))

Par exemple si :
v1 = [1,5,10,2]
v2 = [2,5,12,2]
distance de manhattan (v1,v2) : 3

mais si j'ai deux vecteurs avec moins de poids (c'est à dire moins de tags en commun) :
v1 = [1,5,10]
v2 = [2,5,12]
distance de manhattan (v1,v2) : 3

Ou avec des poids plus fort :
v1 = [1,5,10,200]
v2 = [2,4,10,201]
distance de manhattan (v1,v2) : 3

Donc ni le nombre d'élément en commun, ni la force des poids n'ai une influence. Mais peut être que je me plante quelque part avec la formule de manhattan ?

[tbc92]

Effectivement, ma réponse ne convient pas à ton besoin. C'est plus clair maintenant. Je reviendrai éventuellement plus tard.

[tatayo]

Bonjour,
Purement SQL, ça donne un truc du genre:

Code sql :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
select p2.id,sum(t1.poids + t2.poids)
from photo as p1
inner join tag as t1 on t1.idphoto = p1.id
inner join tag as t2 on t2.nom = t1.nom
inner join photo as p2 on p2.id = t2.idphoto
where p1.nom = 'Photo1'
group by 2.id
order by 2 desc

Cette requête va renvoyer toutes les photos qui ont au moins un tag en commun avec Photo1, en triant le résultat sur la somme des poids des tags communs (avec les sommes les plus importantes en premier).
Avec ton jeu d'exemple, si on part de photo1, on a comme score:

• photo2: 0.2+0.1 + 0.8+0.9, soit 2
• photo3 0.2+0.4 + 0.5+0.4 + 0.01 + 0.05 soit 1.76

Et le gagnant est photo2.

Tatayo.

[xSonnyx]

Merci c'est vrai que je peux commencer par regarder la somme des poids des tags. En revanche ça ne prend pas en compte la distance.
Par exemple avec un seul tag en commun :
v1 = 5
v2 = 15
Et pour deux autres :
v3 =10
v4 = 10

Le résultat (la somme), sera la même à savoir 20. Alors que le second est plus pertinent. Donc ça fonctionne (en tout cas l'ordre est pertinent) pour comparer une image avec toute une liste d'autres images. En revanche les valeurs ne pourront pas spécialement être comparé entre différentes images. Par exemple les scores de comparaison de img1 et img2 d'un côté et img3 et img4 d'un autre.

Mais c'est déjà une piste, il faut que je cherche à normaliser. Je pourrais pondérer ce résultat par un coef qui serait fonction de la distance.

[tbc92]

Peut-être : Somme( Min(V1,V2) )

C'est à dire, si Le tag soleil est présent avec 0.01 dans une image, et 0.8 dans l'autre, 0.01 est si faible que ce tag va compter quasiment comme 0 (quasiment comme si le tag était absent).
Et si le tag est présent avec x dans une image, et également x dans l'autre, c'est le cas idéal, on le garde comme x

[tatayo]

On peut aussi ajouter par exemple la somme des différences des tags, et en tenir compte dans l'ordre de tri:

Code sql :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
select p2.id,sum(t1.poids + t2.poids),sum(abs(t1.poids - t2.poids))
from photo as p1
inner join tag as t1 on t1.idphoto = p1.id
inner join tag as t2 on t2.nom = t1.nom
inner join photo as p2 on p2.id = t2.idphoto
where p1.nom = 'Photo1'
group by 2.id
order by 2 desc,3 asc

Reste à décider de ce qui prime: la somme des poids, la distance... et modifier l'ORDER BY en conséquence.

Tatayo.

[souviron34]

Je veux donc que plus il y a de tags en commun plus la recommendation est forte (à pondéré avec leur distance evidemment).
Et que les poids plus fort pèse davantage que les plus faibles.

Bonjour

D'après cet énoncé, on a donc 2 mesures différentes. Le tri est donc ensuite une question de détermination d'un ordre de priorité dans les critères..

• Soit le nombre de tags en commun est prépondérant.
  
  Dans ce cas, on commence par trier sur le nombre de tags communs, puis on fait des sous-tris par rapport aux poids. Exemple :
  
  nb tags au maximum = 4
  

  Code :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  3
  4
  5
  6
  7
  8
  intialiser last_poids(..) à 0
  
        pour tout élément i ayant 4 tags en commun
            si poids(1) > last_poids(1) ET poids(2) > last_poids(2) ET poids(3) > last_poids(3) ET poids(4) > last_poids(4) 
                last_poids(1) = poids(1)  // last_poids(2) = poids(2) // last_poids(3) = poids(3) // last_poids(4) = poids(4)
                résultat = i
            fin si
       fin pour

  
  
• Soit on veut que des éléments avec moins de tags en commun mais avec des poids supérieurs soient les plus forts, les poids etants prépondérants, le nombre de tags étant secondaire.
  
  On établit donc un tri sur les poids, puis (comme ci-dessus) pour ceux de poids les plus forts on tire ceux de tags les plus grands.
  
  
  
• Soit on veut que des éléments avec moins de tags en commun mais avec des poids supérieurs soient les plus forts, tout en tenant compte en même temps du nombre de tags. Il faut alors établir une mesure globale, avec des poids qui s'affectent pour les poids et pour le nombre de tags, une pondération des critères pour produire une liste unique.
  
  Dans ce cas, une pondération logique pourrait être (nb tags * poids)... Mais il peut y avoir une multitude de combinaisons, dépendant de VOS critères/priorités....
  
  

Enfin, le poids peut être soit la somme des poids de la ligne, la somme des poids max (telle que mentionné ci-dessus), ...

[xSonnyx]

Merci beaucoup à vous pour ces réponses. Cette semaine j'ai mis un peu de côté la formule pour développer le reste du projet, j'y reviendrais sûrement ensuite, cela sera plus pratique pour tester et voir ce qui donne les résultats les plus satisfaisant.

Pour l'instant j'ai donc une formule assez basique :
je fais la somme des poids des tags communs de image1
je fais la somme des poids des tags communs de image2
je fais la moyenne des deux

j'utilise cette moyenne pour la transformer en un coefficient multiplicateur ( coef = 1 - (1 / (1 + moy)) )

je multiplie mon nombre de tags communs aux deux images par ce coefficient.

Bref, très facilement améliorable mais pour l'instant ça fait le job (en tout cas ça à l'air de le faire, en gros) pour continuer le dev. Je reviendrais ici de toute façon quand je retournerais l'améliorer