Modélisation des Réseaux (M1 SIREN, 2022)/Activité F

Pour la dernière activité du cours, on va calculer une recommandation à partir de notre réseau crée au début du cours et harmonisé à partir d'un format et vocabulaire commun.

Instructions

Donnée

On va considérer l'union des rapports orientés entre items décrits dans toutes nos activités C. Chaque phrase <item A> <propriété X> <item B> correspondra à un lien de <item A> vers <item B>, peu importe la propriété qui les lie. On constate qu'il y a deux types de nœuds dans ce réseau:

les participants du cours, en tant que sujets des phrases
les items de nos récits, en tant qu'objets des phrases

On représente le réseau sous la forme d'une double liste d'adjacence. C'est-à-dire, dans une première section, dite sortante, le document liste pour chaque nœud les nœuds auxquels il se connecte ; dans une deuxième section, dite entrante, le document liste pour chaque nœud les nœuds qui se connectent à lui. Comme dans notre réseau tous les liens vont d'une personne à un item de son récit, la première section aura seulement une liste par personne, et la deuxième section seulement une liste pour chaque item qui apparaît dans l'un des récits.

Voici nos réseaux consolidés en un seul document :

Réseau harmonisé et consolidé, sans propriétés, en forme de double liste d'adjacence

Note: Comme on verra, ce format facilitera notre exécution de l'algorithme. On a vu au long du cours que le choix de format peux rendre plus facile ou difficile certaines opérations.

Enrichir la donnée si nécessaire

Avant de commencer le calcul, vous allez regarder si parmi vos objets il y a au moins trois dont vous partagez avec un collègue. Cela se fait facilement avec le document du réseau consolidé : allez dans la liste sortante qui vous correspond, puis pour chaque objet allez regarder s'il y a d'autres personnes dans la liste entrante que lui correspond. Si vous ne comptez pas trois objets partagées avec d'autres :

Trouvez un item dans la liste entrante qui n'est pas dans votre liste mais correspond à un item dans votre liste dans un niveau plus élevé d'abstraction - c'est-à-dire, ils appartiennent au même genre de musique, ou au même pays etc. Vous allez alors travailler comme si ces deux items étaient le même.
Répétez jusqu'à ce que vous aurez au moins trois objets que vous partagez avec au moins un collègue.

Algorithme

On a vu dans le cours que les algorithmes de recommandation, qu'on appelle aussi du « filtrage collaboratif », partent d'une similarité entre personnes établie par leur rapport aux items de récit à recommander, items auxquels on appellera « activités ». Cette similarité est en suite utilisé pour construire un score entre la personne et chaque activité possible de recommander. L'algorithme qu'on va suivre ici réduit à l'essentiel cette démarche pour qu'on puisse l'exécuter manuellement.

Pour un participant p du cours :

Pour chacun des autres participants q, calculer la similarité s(p, q):
- La similarité s(p, q) est le nombre de voisins communs entre p et q - c'est-à-dire, le nombre de voisins de p qui sont aussi voisins de q.
Pour chaque activité a, calculer le score r(p, a):
- Pour expédier le travail, on va considérer uniquement les activités liées au participant à plus haute similarité de p, tirant au sort le participant en cas d'égalité.
- On ne veut pas recommander des activités déjà connues de p, donc pas besoin de calculer le score pour chaque activité a à laquelle le participant p se trouve déjà lié.
- Le score r(p, a), pour recommander au participant p une activité a, est la somme de la similarité s(p, q) pour chacun des voisins entrants q de a.
Choisir l'activité à recommander:
1. Exclure les activités déjà liées au participant p.
2. Trouver les activités avec le plus haut score r(p, a).
  - Si il n'y a qu'une seule activité avec le plus haut score:
    - Recommander cette activité.
  - S'il y a plusieurs activités avec le plus haut score:
    - Parmi ces activités à plus haut score, trouver celles avec le plus haut nombre de voisins entrants.
      - Si il n'y a qu'une seule activité trouvée:
        Recommander cette activité.
      - S'il y a plusieurs activités trouvées:
        Recommander une parmi elles, au hasard.

Astuces

Grace au format double liste d'adjacence, on peut profiter de certains raccourcis pour les calculs:

Pour s(p, q):

Sous la liste sortante du participant p on voit les activités auxquelles il est connecté.
- On peut alors chercher la liste entrante pour chacune de ses activités.
  - Dans chacune de ces listes, on voit qui sont les autres participants q qui partagent l'activité avec p, et alors il suffit de sommer 1 à la similarité s(p, q) de chacun de ces participants.

Pour r(p, a):

Dans la liste entrante d'une activité a, on voit qui sont les participants q qui s'y connectent et il suffit de sommer ses similarités s(p, q) pour obtenir le score r(p, a).

.~´

Activités