Base de données orientées Graphe et similarité

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.

Dans ce projet nous n'allons pas utiliser des bases de données relationnels (qui sont les bases de données les plus courantes) car contrairement à ce qu'indique leur nom, elles ne sont pas efficaces pour gérer les relations. A l'inverse, les bases de données orientés graphe, qui reprennent la théorie des graphes en utilisant de noeuds et des arcs pour représenter et stocker les données, rends ces bases de données très efficace pour traiter les relations. Nous allons utiliser ce type de base de donnée 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é. Nous allons également faire une application des bases de données orienté graphe avec des données sur la contamination de la maladie du COVID-19.

Creation 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’hébergeur Graphendb.

Exemple d'une requête sous forme d'ASCII Art en Cypher

Apprentissage du langage Cypher

Dans le langage cypher il y a quatre éléments important 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 caractéristique spécifique 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 des 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.
labelNoeud est le nom d'un "type" de noeud.

Les propriétés sont définis comme ceci : {nomParametre:valeurParametre}

Enfin les relations sont crées ainsi : -[:NOMRELATION {propriétés}]->

Voici un exemple de création de noeuds et d'une relation qui les relient ainsi que le résultat obtenu :

// 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 resultat

Importer une base de donnée CSV et mise en place de la base de donnée

Nous voulons dans ce projet utiliser la base de donnée de MovieLens qui donne la notions de films par des utilisateurs. Le format de cette base de donnée est CSV et à une en-tête (header).

Voici un lien qui vous mène vers la base de donnée sur les utilisateurs : [1]
Pour importer cette base dans Neo4j j'ai utilisé les fonctions suivantes :
LOAD CSV WITH HEADERS FROM "lien de la base de donnée" AS line
Puis vous pouvez utiliser "line" pour récupérer les données et les utiliser dans vos noeuds, relations ou propriété.

J'ai crée ainsi des noeuds et des relations sous la forme : (Film)-[DU_GENRE]->(Genre)
Les noeuds films ont en paramètre le nom du film et la date de sortie du film.
Les noeuds Genre ont en paramêtre le genre du film (Action, Comedie, Horreur...).
Voici le résultat pour le film Toy Story :

Par la suite j'ai crée des noeuds Utilisateur en relation avec des noeuds Film sous la forme :(Utilisateur)-[:A_VU {note}]->(Film)

Les noeuds Utilisateur ont en paramètre l'id, l'âge, le sexe et le travail de l'utilisateur.
Les relations A_VU ont en paramètre la note que l'utilisateur a mit au film.
Voici le résultat pour Toy Story :

Chaque relation A_VU possède la note de l'utilisateur sur le film relié

La base de données 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 (également appelé coefficient de Jaccard ou coefficient de communauté).

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 :

Plus l'indice de Jaccard est proche de 1 plus les ensembles sont similaire.

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 // inter est le cardinal de u1 inter u2
MATCH (u1)-[:A_VU]->(f:Film)
WITH u1, count(distinct f) as nb_u1, u2,inter //nb_u1 est le cardinal de u1
MATCH (u2)-[:A_VU]->(f:Film)
WITH u2, count(distinct f) as nb_u2, u1, inter, nb_u1 //nb_u2 est le cardinal de u2
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 vu 5 films en commun j'ai ajouter la requêtes suivante : WHERE inter >= 5
Et voici le resultat pour les 10 utilisateur les plus similaires dans l'ordre décroissant :

Les utilisateurs se ressemblant le plus sont ceux avec l'id 162 et 117 car ce sont les utilisateurs avec l'indice de Jaccard le plus proche de 1.

Création de liste de recommandation :

Maintenant que j'ai deux utilisateurs similaires je peux trouver des films qui sont susceptible d’intéresser ces utilisateurs en regardant les films qu'un utilisateur a regardé mais pas l'autre.
Pour obtenir une liste de recommandation pour l'utilisateur avec l'id 117 j'ai filtrer les résultats en prenant les films que l'utilisateur 162 à vu mais pas l'utilisateur 117.
Voici la liste de films que je trouve :

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

Dans l'autre sens je trouve :

Toy Story, Usual Suspect, Mr. Holland's Opus, Sacré Grall et Aliens sont donc 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 et mise en place de la base de donnée

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

Les noeuds Pays et Villes possède l'unique paramètre "nom".
Les noeuds Patient eux ont des paramètres sur l'age, date d’apparition des symptômes, le sexe, si le patient a visité Wuhan, si le patient vient de Wuhan et un id.

On peut voir le résultat suivant en France :

On remarque qu'il y a une erreur dans la base de donnée, ils ont mit France en tant que ville

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 si un individu a une date d'apparition des symptôme antérieur à un autre individu.

Pour commencer je ne me suis interéssé qu'aux patients qui posède un date de sypmtome (qui non pas la date "NA").
Ensuite il falait trouver un moyen de convertir les chaine de caractere date, qui sont sous la forme "mois/jour/année", en 3 parametres jour, mois, annee des entiers pour pouvoir comparer les dates.
Pour ceci j'ai utiliser la fonction split pour suprimer les "/" et les metre dans une liste.
Puis j'ai utilisé la fonction SET pour créer les parametres nouveau 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 pour créer les relations de contamination potentiel.

Exploitation de la base de donnée :

Dans les résultats qui suit j'ai enlevé les noeuds qui n'avait pas de date de symptôme car il ne ne fournissent pas d'information.

Voici le résultat pour la ville de Gansu en Chine :

Les individus 89 et 150 ont une date d’apparition des symptôme antérieur à l'individus 151. Ils ont également le même jour d’apparition des symptôme pour cette raison il n'y a pas de lien entre eux.

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 Beijin (la capitale de la Chine), Shaanxi ou Tianjin. Bien que cette information est évidente, 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 infectes pour voir si il y avait une relation.
J'ai calculer le nombre de personne ayants visité Wuhan, venant de Wuhan, ne venant pas de Wuhan et le total des individus dans la base de données, je trouve ce résultat :

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 peut être 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é).
Avec les résultats de requêtes j'ai trouvé que 27 infecté sur 30 ont été à Wuhan parmi 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 c'est propagé le virus.
Voici la liste des Pays que j'ai trouvé par ordre de contamination à partir de la base de donnée :

Code source

Vous pouvez voir toutes les requêtes que j'ai utilisé lors de ce projet dans le fichier txt dans le lien GitHub ci-dessous :
[2]

Source

Documentation sur le langage Cypher
[3]

Pages sur les bases de données :
Pour les bases de données relationelles
[4]
Pour les bases de données orienté graphe
[5]

Fonctionement de la similarité de Jaccard :
[6]

Site de Neo4j :
[7]

Site de Graphendb :
[8]

Conclusion

A travers ce projet j'ai pu découvrir en général l'univers des bases de donnée que je ne connaissais pas auparavant et voir l'importance qu'elles ont dans le monde actuel. Lors de ce projet j'ai vu plus en détail les bases de données orienté graphe. J'ai pu voir qu'elles offraient beaucoup plus d'avantages lors de la manipulation de relations par rapport au base de donnée relationnelles.

J'ai appris à me servir du langage Cypher pour manipuler les bases de donnée avec le système de gestion de base de donnée Neo4j. J'ai trouvé ce langage assez simple à apprendre car le format en ASCII Art le rends très visuel et facile à comprendre.

J'ai beaucoup aimé le fait que l'on puisse observer facilement les résultats de nos manipulations avec l'affichage des bases de données sous forme de graphes.

J'ai également appris différentes manière de calculer la similarité entre des éléments notamment avec l'indice de Jaccard mais j'ai également découvert d'autres moyen de la calculer comme la similarité cosinus, cependant je n'ai pas réussi à l'appliquer.

J'ai également découvert que la plupart des bases de données ne sont pas parfaite et possède des données manquantes ou erronée. Pour ceci, il faut fournir un travail supplémentaire pour pouvoir quand même exploiter des résultats malgré les donnée lacunaire.

Au final, j'ai trouvé ce projet très enrichissant et intéressant, j'ai pu voir une partie de toute les possibilité qu'offrait ce type de base de donnée et me rendre compte que savoir les manipuler à haut niveau peut réellement apporter des nouvelles perspective pour la recherche.