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

Pour la dernière activité du cours, on va calculer une recommandation à partir de notre réseau crée et harmonisé depuis le début du cours, au cours des activités A et C. Le voici consolidé en un seul document:

Réseau d'activités consolidé, sans propriétés, en format double liste d'adjacence

Instructions

Données

On va considérer le réseau comme un réseau orienté entre les éléments décrits dans vos activités C, où deux éléments sont connectés s'ils apparaissent dans la même phrase <elem_1> <prop> <elem_2>, peu importe la propriété qui les lie. On constate qu'il y a deux types de nœuds dans ce réseau:

participants du cours, normalement les sujets des phrases
objet d'activités, normalement les objets des phrases

Pour faciliter les opérations de l'algorithme, on représente le réseau comme une double liste d'adjacence : dans une première section sortante le document liste pour chaque nœud les nœuds auxquels il est connecté; dans une deuxième section entrante le document liste pour chaque nœud les nœuds qui s'y connectent. Comme dans notre réseau tous les liens sont depuis des personnes vers les objets d'activités, la première section aura seulement une liste par personne, et la deuxième section seulement pour les activités.

Note: On ne choisit pas le format au hasard: comme discuté dans le cours, le format sous lequel on stocke la donnée peut rendre plus facile ou difficile certaines opérations.

Préparation

Avant de commencer le calcul, vous allez regarder si parmi vos activités il y a au moins trois dont vous partagez avec un collègue. Cela se fait facilement avec le document du réseau (allez dans votre liste puis utilisez la fonction "rechercher dans la page" de votre navigateur pour chaque objet). Si vous ne comptez pas trois activités partagées, vous avez deux options qui peuvent être combinées :

Sans la modifier, revenez sur votre Activité A et trouvez des activités que vous n'avez pas transcrit en URIs dans l'activité C. Corrigez votre activité C et travaillez la présente activité comme si elles étaient dans la votre liste d'adjacence (mais ne modifiez pas le document Réseau).
Trouvez une activité de vos collègues qui se ressemble assez à une de vos activités que vous ne partagez avec personne. Justifiez comment ces deux activités pourraient être identifiés avec l'usage d'une ontologie, e travaillez comme si votre activité était celle de vos collègues (mais ne modifiez pas le document Réseau).

Une fois que vous avez au moins trois activités que vous partagez avec au moins un collègue, continuez pour le calcul de votre recommandation.

Algorithme

On a vu dans le cours que les algorithmes de recommandation partent d'une similarité entre personnes, par leur rapport aux objets à recommander, pour informer un score entre la personne et les possibles recommandations. Alors, celui qu'on va suivre ici, réduit à l'essentiel pour qu'on puisse l'exécuter manuellement, consiste de ...

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é.
- le score r(p, a) est la somme, sur chacun des voisins entrants q de a, de la similarité s(p, q) qu'on vient de calculer.
- on ne veut pas recommander des activités déjà faites, donc pas besoin de calculer le score pour les activités déjà liées au participant p.
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 du participant p on voit les activités auxquelles il est connecté.
- On peut alors chercher dans la section entrante la liste de chacune de ses activités.
  - On verra qui sont les autres participants (q) qui la partagent avec p, et il suffit de sommer 1 à la similarité s(p, q) de chacun.

Pour r(p, a):

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

.~´

Activités