Base de données orientées Graphe, similarité et modèles prédictifs

Il y a de nos jours énormément de données a traiter (Big Data) avec internet, et pour pouvoir gérer et analyser ces données l'utilisation des bases de données est devenu primordial. De nos jours, les utilisateurs ne peuvent plus faire directement le choix d'un produit, d’un média... Pour cela, la plupart des entreprises utilisent un système de recommandations. Ces systèmes de recommandations utilisent des algorithmes qui identifie des utilisateurs similaires et leurs recommande des éléments susceptible de les intéresser. Ces algorithmes utilisent des base de données orientées graphe et non des bases de données relationnels traditionnels car elles sont beaucoup plus appropriée lorsqu'il s'agit d'exploiter les relations entre les données ce qui est notre cas car nous nous intéressons au liens entre les utilisateur et les « produits ».

L'objectif final de ce projet va être de créer un système de recommandation de film en utilisant les bases de données orienté graphes et des algorithmes de recherche de similarité.

Création de bases de données orienté graphe :

Pour réaliser ce projet, j'ai du créer des bases de données orientées graphe. Pour ce faire, j'ai utilisé le système de gestion de base de données (SGBD) orienté graphe Neo4j. Ce SGBD utilise le langage de requête Cypher qui a la particularité d'être basé sur de l'art ASCII (ASCII Art) pour créer ces requêtes ce qui rends le langage visuel et facile à lire. Pour héberger les bases de données Neo4j , j'ai utilisé l'hebergeur Graphendb.

Apprentissage du langage Cypher

Dans le langage Cypher il y a quatre éléments importants pour pouvoir créer une base de données orienté graphe : -Les Noeuds (Nodes) (Les principales instances) -Les relations (Relationships) (Qui relient les noeuds entre eux) -Les propriétés (Properties) (Les caracteristique specifique des noeuds et relations) -Les fonction permettant de gérer ces objets

Créer des noeuds et des relations

Pour créer des noeuds (et les relations) il faut utiliser la fonction CREATE. Dans cypher un noeud est composé comme ceci : (nomNoeudRacc:labelNoeud {propriétés}) nomNoeudRacc est un nom du noeuds raccourci pour le manipuler plus rapidement et facilement dans les requêtes. Les propriétés sont definis comme ceci : {nomParametre:valeurParametre} Enfin les relations sont crées ainsi : -[:NOMRELATION {propriétés}]->

Exemple :
// Création des noeuds
CREATE (f:Film {titre:"Jurassic Park"})
CREATE (r:Realisateur {prenom:"Steven", nom:"Spielberg", metier:"Realisateur"})
// Création de la relation
MATCH (r:Realisateur) WHERE r.nom = "Spielberg"
MATCH (f:Film) WHERE f.titre = "Jurassic Park"
CREATE (r)-[rel:REALISE {annee:1993}]->(f)
RETURN r,rel,f //Affiche le résultat

Importer une base de donnée CSV

Nous voulons dans ce projet utiliser la base de donnée de MovieLens qui donne la notation de films par des utilisateurs. Le format de cette base de donnée est CSV et à une en-tête (header).
Pour importer cette base dans Neo4j j'ai utilisé les commandes suivantes : On commence par créer des noeuds films avec des paramètres:

LOAD CSV WITH HEADERS FROM "https://www.dropbox.com/s/fq44x3m11y9yozs/u.item.csv?dl=1" as line
fieldterminator '|' WITH line LIMIT 200 
CREATE (f:Film)
SET f.titre = line.title,
f.idFilm = toInteger(line.id),
f.date = line.release

Puis on crée des noeuds Genre avec des paramètres:

LOAD CSV WITH HEADERS FROM "https://www.dropbox.com/s/fq44x3m11y9yozs/u.item.csv?dl=1" as line
fieldterminator '|' WITH line LIMIT 250 
WHERE line.action = "1"
CREATE (:Genre{genre:"Action", idGenre:toInteger(line.id)})

LOAD CSV WITH HEADERS FROM "https://www.dropbox.com/s/fq44x3m11y9yozs/u.item.csv?dl=1" as line
fieldterminator '|' WITH line LIMIT 250  
WHERE line.adventure = "1"
CREATE (:Genre{genre:"Aventure", idGenre:toInteger(line.id)})
...
...

On utilise cette requête pour chaque genre

On crée les relations entre les Films et les Genres :

MATCH (f:Film)
MATCH (g:Genre)
WHERE f.idFilm = g.idGenre
CREATE (f)-[:DU_GENRE]->(g)

On peux observer le résultat avec la commande :

MATCH (f:Film)-[r]->(g:Genre)
RETURN f,r,g LIMIT 50

On crée des noeuds Utilisateur avec des paramètres :

LOAD CSV WITH HEADERS FROM "https://www.dropbox.com/s/piz58gre87s9miu/u.user.csv?dl=1" as line
fieldterminator '|' WITH line LIMIT 250 CREATE (u:Utilisateur)
SET u.age = toInteger(line.age),
u.sexe = line.gender,
u.travail = line.occupation,
u.idUtilisateur = toInteger(line.id)

Pour finir, on ajoute les relations entre les utilisateurs et les films avec comme paramètre la note qu'ils ont donné au film :

LOAD CSV WITH HEADERS FROM "https://www.dropbox.com/s/vt28mlhaz129mcb/u.data.csv?dl=1" as line
fieldterminator '|' WITH line LIMIT 8000
MATCH (u:Utilisateur)
MATCH (f:Film)
WHERE u.idUtilisateur = toInteger(line.userid) AND f.idFilm = toInteger(line.itemid)
CREATE (u)-[:A_VU {note:toInteger(line.rating)}]->(f)

La base de donée est prête on peux commencer à créer un système de recommandation.

Utilisation d'algorithmes de recherche de similarité et système de recommandation

Similarité de Jaccard

Une manière de mesurer la similarité entre deux ensemble est de calculer l'indice de Jaccard (ou coefficient de Jaccard).

Pour calculer l'indice de Jaccard on calcule le rapport entre le cardinal (la taille) de l'intersection des ensembles considérés et le cardinal de l'union des ensembles, soit la formule suivante :

En appliquant cette formule aux films vu par les utilisateur, je peux regarder les utilisateurs les plus similaire par rapport au même films qu'ils ont vu. Pour ceci, j'ai utilisé les commandes suivantes :

MATCH (u1)-[:A_VU]->(f:Film)<-[:A_VU]-(u2)
WITH u1, u2, count(distinct f) as inter
MATCH (u1)-[:A_VU]->(f:Film)
WITH u1, count(distinct f) as nb_u1, u2,inter
MATCH (u2)-[:A_VU]->(f:Film)
WITH u2, count(distinct f) as nb_u2, u1, inter, nb_u1
RETURN u1.idUtilisateur, u2.idUtilisateur, inter, nb_u1, nb_u2, inter*1.0/(nb_u1+nb_u2-inter) as jaccard ORDER BY jaccard DESC LIMIT 10 

Cependant ma base de donnée étant "petite" je trouve que les utilisateurs qui se ressemblent le plus sont ceux ayant vu un même unique film. Pour contrer ce problème j'ai ajouter qu'il fallait que les utilisateurs aient au moins 5 films en commun ce qui me donne la requête suivante :

MATCH (u1)-[:A_VU]->(f:Film)<-[:A_VU]-(u2)
WITH u1, count(distinct f) as inter, u2
WHERE inter >= 5
MATCH (u1)-[:A_VU]->(f:Film)
WITH u1, count(distinct f) as nb_u1, u2,inter
MATCH (u2)-[:A_VU]->(f:Film)
WITH u2, count(distinct f) as nb_u2, u1, inter, nb_u1
RETURN u1.idUtilisateur, u2.idUtilisateur, inter, nb_u1, nb_u2, inter*1.0/(nb_u1+nb_u2-inter) as jacard ORDER BY jacard DESC LIMIT 10

Et voici le resultat :
Les utilisateurs se resemblant le plus sont donc celui avec l'id 162 et celui avec l'id 117.

Création de liste de recomandation :

Maintenant que j'ai deux utilisateurs similaires je peux trouver des films qui sont suseptible d'intérerser un des deux utilisateur en regardant les films qu'un utilisateur a regardé mais pas l'autre. Pour obtenir une liste de recomandation pour l'utilisateur avec l'id 117 j'ai utiliser la requête suivante :

MATCH (u1)-[:A_VU]->(f1:Film), (u2)-[:A_VU]->(f2:Film)
WHERE u1.idUtilisateur = 162 AND u2.idUtilisateur = 117
WITH collect(distinct f1.titre) AS l1, collect(distinct f2.titre) AS l2
RETURN filter(film IN l1 WHERE NOT film IN l2) AS recomandationPrU2

J'obtient les films suivants :

Donc Bridcage, Clerks et Rock sont susceptible d'intéresser l'utilisateur 117.

Dans l'autre sens je trouve :

Donc Toy Story, Usual Suspect, Mr. Holland's Opus, Sacré Grall et Aliens sont susceptible d'intéresser l'utilisateur 162.

Application des bases de données orienté graphes et recherche de similarité sur la contamination du COVID-19

Importation de la base de donnée sur les patients contaminés

Pour étudier les données de la base j'ai importer la base de donnée sous la forme :
(Patient)-[:RESIDE]->(Ville)-[:LOCALISE]->(Pays)

J'ai obtenu ceci avec les commandes :

LOAD CSV WITH HEADERS FROM "https://www.dropbox.com/s/po34ry4oil634yg/COVID19_line_list_data.csv?dl=1" as line 
WITH line LIMIT 800
MERGE (p:Pays {nom:line.country})
MERGE (v:Ville {nom:line.location})
CREATE (pa:Patient)
SET
pa.date_symptome = line.symptom_onset,
pa.age = toInteger(line.age),
pa.sexe = line.gender,
pa.a_visite_wuhan = toInteger(line.`visiting Wuhan`),
pa.id = toInteger(line.id)
CREATE (pa)-[:RESIDE]->(v)
MERGE (v)-[:LOCALISE]->(p)

Les noeuds Pays et Villes possède l'unique paramètre "nom".
Les noeuds Patient eux ont des parametres sur l'age, date d'aparition des symptomes, le sexe, si le patient a visité Wuhan et un id.
On peut voir le resultat suivant en France par exemple :

Création de relations de contamination potentiel

J'ai par la suite ajouté des relations de contamination potentiel entre les individus de même ville et selon la date des symptômes.

Pour commencer j'ai regarder tout les patient qui possède un date de symptôme (qui non pas la date "NA"). Ensuite il fallait trouver un moyen de convertir les chaîne de caractères date, qui sont sous la forme "mois/jour/année", en 3 paramètres jour, mois, annee des entiers pour pouvoir comparer les dates. Pour ceci j'ai utiliser la fonction split pour supprimer les "/" et les mettre dans une liste. Puis j'ai utilisé la fonction SET pour créer les paramètres. J'ai utilisé les requêtes suivantes :

MATCH (p:Patient)
WHERE p.date_symptome <> "NA"
WITH split(p.date_symptome, '/') AS liste,p
SET p.mois = toInteger(liste[0]), p.jour = toInteger(liste[1]), p.annee = toInteger(liste[2])

Puis j'ai comparé les personnes venant des même ville et qui on eu des symptômes avant un autre patient. J'ai utiliser les requêtes suivantes :

MATCH (p1:Patient)-[]->(v:Ville)<-[]-(p2:Patient)
WHERE (p1.date_symptome <> "NA") AND (p2.date_symptome <> "NA") AND ((p2.annee < p1.annee) OR (p2.annee = p1.annee AND p2.mois < p1.mois) OR (p2.annee = p1.annee AND p2.mois = p1.mois AND p2.jour < p1.jour))
CREATE (p2)-[r:CONTAMINATION_POTENTIEL]->(p1)

Exploitation de la base de donnée :

Voici le résultat pour la ville de Sichuan en Chine :
Voici le résultat pour la Chine entière. On remarque que des "Clusters" (regroupements de noeuds) se sont formé sur Wuhan (le foyer de l'épidémie) et sur les plus grosses métropoles chinoise comme Beijing (la capitale de la Chine), Shaanxi ou Tianjin. Cela montre que le virus se propage plus facilement dans les lieu avec une forte démographie.

Ensuite j'ai décidé de regarder le nombre de personnes ayants visité Wuhan et vivant a Wuhan parmi les infectés pour voir si il y avait une relation. J'ai utilisé les commandes suivantes :

MATCH (p1:Patient)
WHERE p1.a_visite_wuhan = 1 AND (p1.vient_de_wuhan = 0 OR p1.vient_de_wuhan IS NULL) //Il y a 1 cas ou a visité wuhan et vient de wuhan = 1
WITH count(p1) AS nbrWuhan
MATCH (p2:Patient)
WHERE (p2.a_visite_wuhan = 0 AND p2.vient_de_wuhan = 0) OR (p2.vient_de_wuhan IS NULL AND p2.a_visite_wuhan = 0) //Il ya 4 cas ou il n'y a pas d'infos sur vient de wuhan
WITH nbrWuhan, count(p2) AS nbrNonWuhan
MATCH (p3:Patient)
WHERE p3.vient_de_wuhan = 1
WITH nbrWuhan, nbrNonWuhan, count(p3) AS nbrVientDeWuhan
RETURN nbrWuhan, nbrVientDeWuhan, nbrNonWuhan, nbrWuhan+nbrVientDeWuhan AS totalWuhan, nbrWuhan+nbrNonWuhan+nbrVientDeWuhan AS total

Le resultat est :

On remarque que sur les 800 contaminés, 170 personnes ont visité Wuhan et 143 vivait a Wuhan. Cela nous donne un pourcentage de (313/800)*100 = 39,125% il y a donc plus d'un contaminé sur 3 qui a été à Wuhan. On peut donc supposer qu'il y a une relation entre le fait d'avoir visité ou vécu a Wuhan et d'être contaminé.

J'ai voulu ensuite regarder d'ou venait les premiers infectés (de la base de donné). Je peux voir les 30 premiers infectés avec les commandes suivante :

MATCH (p:Patient)-[r]->(v:Ville)-[]->(py)
WHERE p.date_symptome IS NOT NULL AND p.date_symptome <> "NA"
WITH v, r, py, p AS liste ORDER BY p.annee,p.mois,p.jour
RETURN v, py, liste LIMIT 30

On remarque que 28 infecté sur 30 ont été à Wuhan parmis ces premiers infecté ce qui montre bien que l'épidémie a commencé la bas.

Enfin j'ai voulu voir dans quel ordre de pays s'est propagé le virus. J'ai utilisé les commandes suivantes :

MATCH (pa:Patient)-[]->(:Ville)-[]->(p:Pays)
WHERE pa.date_symptome IS NOT NULL AND pa.date_symptome <> "NA"
WITH p AS listePays ORDER BY pa.annee,pa.mois,pa.jour
RETURN DISTINCT listePays

Et voici le resultat :