Wiki du LAMA (UMR 5127) - Contributions [fr]

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

2020-05-17T16:24:56Z

Rpajean : /* Similarité de Jaccard */

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 devenue primordiale. Aujourd'hui, les utilisateurs ne peuvent plus faire directement le choix d'un produit, d’un média...
Pour cela, la plupart des entreprises utilisent des systèmes de recommandations. Ces systèmes de recommandations utilisent des algorithmes qui identifient des utilisateurs similaires et leurs recommandent des éléments susceptibles de les intéresser. 

Dans ce projet nous n'allons pas utiliser des bases de données relationnelles (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ées graphe, qui reprennent la théorie des graphes en utilisant des nœuds et des arcs pour représenter et stocker les données, rendent ces bases de données très efficaces pour traiter les relations. Nous allons utiliser ce type de base de donnée car nous nous intéressons aux liens entre les utilisateurs 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ées graphe et des algorithmes de recherche de similarité. Nous allons également utiliser les bases de données orientées 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 ses requêtes ce qui rend le langage visuel et facile à lire. Pour héberger les bases de données Neo4j , j'ai utilisé l’hébergeur Graphendb.
[[Fichier:Exemple_requete_ascii.png | frame | none | 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 importants pour pouvoir créer une base de données orientée graphe :
*Les Nœuds (Nodes) (Les éléments principaux)
*Les relations (Relationships) (Qui relient les nœuds entre eux)
*Les propriétés (Properties) (Les caractéristiques spécifiques des nœuds et relations)
*Les fonctions permettant de gérer ces objets

=== Créer des nœuds et des relations ===
Pour créer des nœuds (et des relations) il faut utiliser la fonction CREATE. 
Dans cypher un nœud est composé comme ceci : <code>(nomNoeudRacc:labelNoeud {propriétés})</code>
 
nomNoeudRacc est un nom du nœud raccourci pour le manipuler plus rapidement et facilement dans les requêtes. 
labelNoeud est le nom d'un "type" de nœud.
 
Les propriétés sont définies comme ceci : <code>{nomParametre:valeurParametre}</code>
 
Enfin les relations sont créées ainsi : <code>-[:NOMRELATION {propriétés}]-></code>
 
Voici un exemple de création de nœuds et d'une relation qui les relie ainsi que le résultat obtenu :
<nowiki>// 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</nowiki>
[[Fichier:Exemple_noeuds.png | center]]

=== Importer une base de données CSV et mise en place de la base de données ===
Nous voulons dans ce projet utiliser la base de données de MovieLens qui donne la notation des films par des utilisateurs. Le format de cette base de données est CSV et à un en-tête (header). 

Voici un lien qui vous mène vers la base de données sur les utilisateurs : [https://www.dropbox.com/s/piz58gre87s9miu/u.user.csv?] 
Pour importer cette base dans Neo4j j'ai utilisé les fonctions suivantes : 
<code>LOAD CSV WITH HEADERS FROM "lien de la base de données" AS line</code>
 
Puis vous pouvez utiliser "line" pour récupérer les données et les utiliser dans vos nœuds, relations ou propriétés.
 
J'ai créé ainsi des nœuds et des relations sous la forme : <code>(Film)-[DU_GENRE]->(Genre)</code>
 
Les nœuds films ont en paramètre le nom du film et la date de sortie du film. 
Les nœuds Genre ont en paramètre le genre du film (Action, Comédie, Horreur...). 
Voici le résultat pour le film Toy Story : 
[[Fichier:Exemple_genre.png | center]] 
Par la suite j'ai créé des nœuds Utilisateur en relation avec des nœuds Film sous la forme :<code>(Utilisateur)-[:A_VU {note}]->(Film)</code>
 
Les nœuds 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 mis au film. 
Voici le résultat pour Toy Story : 
[[Fichier:Exemple_utilisateur.png | 400px | thumb | none | Chaque relation A_VU possède la note de l'utilisateur sur le film relié]]
 
La base de données est prête on peut 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 ensembles 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 : 
[[Fichier:Formule_sim_jaccard.png | link=https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard | frame | center | Plus l'indice de Jaccard est proche de 1 plus les ensembles sont similaires. (Vous pouvez cliquer sur l'image pour en savoir plus]] 

En appliquant cette formule aux films vus par les utilisateurs, je peux regarder les utilisateurs les plus similaires par rapport aux mêmes films qu'ils ont vus. 
Pour ceci, j'ai utilisé les commandes suivantes : 
<nowiki>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</nowiki>
 
Cependant ma base de données é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 ajouté qu'il fallait que les utilisateurs aient au moins vu 5 films en commun j'ai ajouté la requête suivante : <code>WHERE inter >= 5</code>
 
Et voici le résultat pour les 10 utilisateurs les plus similaires dans l'ordre décroissant : 

[[Fichier:Resultats_sim_jaccard.png | thumb | center |1000px | 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 susceptibles 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 filtré 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 : 

[[Fichier:Resultat_recom_1.png | frame | center | Bridcage, Clerks et Rock sont donc susceptibles d’intéresser l'utilisateur 117.]]
 
Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png | frame | center | Toy Story, Usual Suspect, Mr. Holland's Opus, Sacré Grall et Aliens sont donc susceptibles d’intéresser l'utilisateur 162.]]

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

=== Importation de la base de données sur les patients contaminés et mise en place de la base de données ===
Pour étudier les données de la base j'ai importé la base de données sous la forme : <code>(Patient)-[:RESIDE]->(Ville)-[:LOCALISE]->(Pays)</code>
 
Les nœuds Pays et Villes possède l'unique paramètre "nom". 
Les nœuds 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 :
[[Fichier:Graphe_pays_ville.png | 700px | thumb | center| On remarque qu'il y a une erreur dans la base de données, ils ont mis France en tant que ville]]
 

=== Création de relations de contamination potentielle ===

J'ai par la suite ajouté des relations de contamination potentielle entre les individus de même ville et si un individu a une date d'apparition des symptômes antérieure à un autre individu.
 
Pour commencer je ne me suis intéressé qu'aux patients qui possèdent une date de symptôme (qui n'ont pas la date "NA"). 
Ensuite il fallait trouver un moyen de convertir les chaines de caractères "date", qui sont sous la forme "mois/jour/année", en 3 paramètres jour, mois, année en des entiers pour pouvoir comparer les dates. 
Pour ceci j'ai utilisé la fonction split pour supprimer les "/" et les mettre dans une liste. 
Puis j'ai utilisé la fonction SET pour créer les nouveaux paramètres. 
J'ai utilisé les requêtes suivantes : 
<nowiki>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])</nowiki>
 
Puis j'ai comparé les personnes venant des mêmes villes et qui ont eu des symptômes avant un autre patient pour créer les relations de contamination potentielle.

=== Exploitation de la base de données : ===

Dans les résultats qui suivent j'ai enlevé les nœuds qui n'avaient pas de date de symptôme car ils ne fournissent pas d'information. 

Voici le résultat pour la ville de Gansu en Chine : 
[[Fichier:Exemple_Gansu.png | frame | center | Les individus 89 et 150 ont une date d’apparition des symptômes antérieure à l'individu 151. Ils ont également le même jour d’apparition des symptômes; pour cette raison il n'y a pas de lien entre eux.]]
 
Voici le résultat pour la Chine entière : 

[[Fichier:Graphe_contamination_potentiel_Chine.png | 700px | thumb | center| On remarque que des "Clusters" (regroupements de nœuds) se sont formés sur Wuhan (le foyer de l'épidémie) et sur les plus grosses métropoles chinoises comme Beijin (la capitale de la Chine), Shaanxi ou Tianjin. Bien que cette information soit évidente, cela montre que le virus se propage plus facilement dans les lieux avec une forte démographie.]]
 
Ensuite j'ai décidé de regarder le nombre de personnes ayant visité Wuhan et vivant a Wuhan parmi les infectés pour voir si il y avait une relation. 
J'ai calculé le nombre de personnes ayant 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 : 
[[Fichier:Resultat_nbr_Wuhan.png | center]]
 
On remarque que sur les 800 contaminés, 170 personnes ont visité Wuhan et 143 vivaient à 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 venaient les premiers infectés (de la base de données). 
Avec les résultats de requêtes j'ai trouvé que 27 infectés sur 30 ont été à Wuhan parmi ces premiers infectés, ce qui montre bien que l'épidémie a commencé là-bas.
 
Enfin j'ai voulu voir dans quel ordre de pays s'est propagé le virus. 
Voici la liste des Pays que j'ai trouvé par ordre chronologique de contamination à partir de la base de données : 
[[Fichier:Resultat_liste_pays.png | center]]

== 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 : 
[https://github.com/TheSummer1502/VISI201.git https://github.com/TheSummer1502/VISI201.git]

== Source ==

Documentation sur le langage Cypher 
[https://neo4j.com/docs/cypher-manual/4.0/ https://neo4j.com/docs/cypher-manual/4.0/]
 
Pages sur les bases de données : 
Pour les bases de données relationelles 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle]
 
Pour les bases de données orientées graphe 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe]
 
Fonctionnement de la similarité de Jaccard : 
[https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard]
 
Site de Neo4j : 
[https://neo4j.com/ https://neo4j.com/]
 
Site de Graphendb : 
[https://www.graphenedb.com/ https://www.graphenedb.com/]

== Conclusion ==
A travers ce projet j'ai pu découvrir en général l'univers des bases de données 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ées graphe. J'ai pu voir qu'elles offraient beaucoup plus d'avantages lors de la manipulation de relations par rapport aux bases de données relationnelles.

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

De plus 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.

Egalement j'ai appris différentes manières de calculer la similarité entre des éléments notamment avec l'indice de Jaccard mais j'ai également découvert d'autres moyens 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 parfaites et possèdent des données manquantes ou erronées. Pour ceci, il faut fournir un travail supplémentaire pour pouvoir quand même exploiter des résultats malgré les données lacunaires.

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

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

2020-05-17T16:16:43Z

Rpajean : /* Similarité de Jaccard */

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 devenue primordiale. Aujourd'hui, les utilisateurs ne peuvent plus faire directement le choix d'un produit, d’un média...
Pour cela, la plupart des entreprises utilisent des systèmes de recommandations. Ces systèmes de recommandations utilisent des algorithmes qui identifient des utilisateurs similaires et leurs recommandent des éléments susceptibles de les intéresser. 

Dans ce projet nous n'allons pas utiliser des bases de données relationnelles (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ées graphe, qui reprennent la théorie des graphes en utilisant des nœuds et des arcs pour représenter et stocker les données, rendent ces bases de données très efficaces pour traiter les relations. Nous allons utiliser ce type de base de donnée car nous nous intéressons aux liens entre les utilisateurs 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ées graphe et des algorithmes de recherche de similarité. Nous allons également utiliser les bases de données orientées 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 ses requêtes ce qui rend le langage visuel et facile à lire. Pour héberger les bases de données Neo4j , j'ai utilisé l’hébergeur Graphendb.
[[Fichier:Exemple_requete_ascii.png | frame | none | 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 importants pour pouvoir créer une base de données orientée graphe :
*Les Nœuds (Nodes) (Les éléments principaux)
*Les relations (Relationships) (Qui relient les nœuds entre eux)
*Les propriétés (Properties) (Les caractéristiques spécifiques des nœuds et relations)
*Les fonctions permettant de gérer ces objets

=== Créer des nœuds et des relations ===
Pour créer des nœuds (et des relations) il faut utiliser la fonction CREATE. 
Dans cypher un nœud est composé comme ceci : <code>(nomNoeudRacc:labelNoeud {propriétés})</code>
 
nomNoeudRacc est un nom du nœud raccourci pour le manipuler plus rapidement et facilement dans les requêtes. 
labelNoeud est le nom d'un "type" de nœud.
 
Les propriétés sont définies comme ceci : <code>{nomParametre:valeurParametre}</code>
 
Enfin les relations sont créées ainsi : <code>-[:NOMRELATION {propriétés}]-></code>
 
Voici un exemple de création de nœuds et d'une relation qui les relie ainsi que le résultat obtenu :
<nowiki>// 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</nowiki>
[[Fichier:Exemple_noeuds.png | center]]

=== Importer une base de données CSV et mise en place de la base de données ===
Nous voulons dans ce projet utiliser la base de données de MovieLens qui donne la notation des films par des utilisateurs. Le format de cette base de données est CSV et à un en-tête (header). 

Voici un lien qui vous mène vers la base de données sur les utilisateurs : [https://www.dropbox.com/s/piz58gre87s9miu/u.user.csv?] 
Pour importer cette base dans Neo4j j'ai utilisé les fonctions suivantes : 
<code>LOAD CSV WITH HEADERS FROM "lien de la base de données" AS line</code>
 
Puis vous pouvez utiliser "line" pour récupérer les données et les utiliser dans vos nœuds, relations ou propriétés.
 
J'ai créé ainsi des nœuds et des relations sous la forme : <code>(Film)-[DU_GENRE]->(Genre)</code>
 
Les nœuds films ont en paramètre le nom du film et la date de sortie du film. 
Les nœuds Genre ont en paramètre le genre du film (Action, Comédie, Horreur...). 
Voici le résultat pour le film Toy Story : 
[[Fichier:Exemple_genre.png | center]] 
Par la suite j'ai créé des nœuds Utilisateur en relation avec des nœuds Film sous la forme :<code>(Utilisateur)-[:A_VU {note}]->(Film)</code>
 
Les nœuds 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 mis au film. 
Voici le résultat pour Toy Story : 
[[Fichier:Exemple_utilisateur.png | 400px | thumb | none | Chaque relation A_VU possède la note de l'utilisateur sur le film relié]]
 
La base de données est prête on peut 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 ensembles 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 : 
[[Fichier:Formule_sim_jaccard.png | link=https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard | frame | center | Plus l'indice de Jaccard est proche de 1 plus les ensembles sont similaires. (Vous pouvez cliquer sur l'image pour en savoir plus]] 

En appliquant cette formule aux films vus par les utilisateurs, je peux regarder les utilisateurs les plus similaires par rapport aux mêmes films qu'ils ont vus. 
Pour ceci, j'ai utilisé les commandes suivantes : 
<nowiki>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</nowiki>
 
Cependant ma base de données é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 ajouté qu'il fallait que les utilisateurs aient au moins vu 5 films en commun j'ai ajouté la requête suivante : <code>WHERE inter >= 5</code>
 
Et voici le résultat pour les 10 utilisateurs les plus similaires dans l'ordre décroissant : 

[[Fichier:Resultats_sim_jaccard.png | frame | none | 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 susceptibles 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 filtré 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 : 

[[Fichier:Resultat_recom_1.png | frame | center | Bridcage, Clerks et Rock sont donc susceptibles d’intéresser l'utilisateur 117.]]
 
Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png | frame | center | Toy Story, Usual Suspect, Mr. Holland's Opus, Sacré Grall et Aliens sont donc susceptibles d’intéresser l'utilisateur 162.]]

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

=== Importation de la base de données sur les patients contaminés et mise en place de la base de données ===
Pour étudier les données de la base j'ai importé la base de données sous la forme : <code>(Patient)-[:RESIDE]->(Ville)-[:LOCALISE]->(Pays)</code>
 
Les nœuds Pays et Villes possède l'unique paramètre "nom". 
Les nœuds 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 :
[[Fichier:Graphe_pays_ville.png | 700px | thumb | center| On remarque qu'il y a une erreur dans la base de données, ils ont mis France en tant que ville]]
 

=== Création de relations de contamination potentielle ===

J'ai par la suite ajouté des relations de contamination potentielle entre les individus de même ville et si un individu a une date d'apparition des symptômes antérieure à un autre individu.
 
Pour commencer je ne me suis intéressé qu'aux patients qui possèdent une date de symptôme (qui n'ont pas la date "NA"). 
Ensuite il fallait trouver un moyen de convertir les chaines de caractères "date", qui sont sous la forme "mois/jour/année", en 3 paramètres jour, mois, année en des entiers pour pouvoir comparer les dates. 
Pour ceci j'ai utilisé la fonction split pour supprimer les "/" et les mettre dans une liste. 
Puis j'ai utilisé la fonction SET pour créer les nouveaux paramètres. 
J'ai utilisé les requêtes suivantes : 
<nowiki>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])</nowiki>
 
Puis j'ai comparé les personnes venant des mêmes villes et qui ont eu des symptômes avant un autre patient pour créer les relations de contamination potentielle.

=== Exploitation de la base de données : ===

Dans les résultats qui suivent j'ai enlevé les nœuds qui n'avaient pas de date de symptôme car ils ne fournissent pas d'information. 

Voici le résultat pour la ville de Gansu en Chine : 
[[Fichier:Exemple_Gansu.png | frame | center | Les individus 89 et 150 ont une date d’apparition des symptômes antérieure à l'individu 151. Ils ont également le même jour d’apparition des symptômes; pour cette raison il n'y a pas de lien entre eux.]]
 
Voici le résultat pour la Chine entière : 

[[Fichier:Graphe_contamination_potentiel_Chine.png | 700px | thumb | center| On remarque que des "Clusters" (regroupements de nœuds) se sont formés sur Wuhan (le foyer de l'épidémie) et sur les plus grosses métropoles chinoises comme Beijin (la capitale de la Chine), Shaanxi ou Tianjin. Bien que cette information soit évidente, cela montre que le virus se propage plus facilement dans les lieux avec une forte démographie.]]
 
Ensuite j'ai décidé de regarder le nombre de personnes ayant visité Wuhan et vivant a Wuhan parmi les infectés pour voir si il y avait une relation. 
J'ai calculé le nombre de personnes ayant 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 : 
[[Fichier:Resultat_nbr_Wuhan.png | center]]
 
On remarque que sur les 800 contaminés, 170 personnes ont visité Wuhan et 143 vivaient à 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 venaient les premiers infectés (de la base de données). 
Avec les résultats de requêtes j'ai trouvé que 27 infectés sur 30 ont été à Wuhan parmi ces premiers infectés, ce qui montre bien que l'épidémie a commencé là-bas.
 
Enfin j'ai voulu voir dans quel ordre de pays s'est propagé le virus. 
Voici la liste des Pays que j'ai trouvé par ordre chronologique de contamination à partir de la base de données : 
[[Fichier:Resultat_liste_pays.png | center]]

== 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 : 
[https://github.com/TheSummer1502/VISI201.git https://github.com/TheSummer1502/VISI201.git]

== Source ==

Documentation sur le langage Cypher 
[https://neo4j.com/docs/cypher-manual/4.0/ https://neo4j.com/docs/cypher-manual/4.0/]
 
Pages sur les bases de données : 
Pour les bases de données relationelles 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle]
 
Pour les bases de données orientées graphe 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe]
 
Fonctionnement de la similarité de Jaccard : 
[https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard]
 
Site de Neo4j : 
[https://neo4j.com/ https://neo4j.com/]
 
Site de Graphendb : 
[https://www.graphenedb.com/ https://www.graphenedb.com/]

== Conclusion ==
A travers ce projet j'ai pu découvrir en général l'univers des bases de données 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ées graphe. J'ai pu voir qu'elles offraient beaucoup plus d'avantages lors de la manipulation de relations par rapport aux bases de données relationnelles.

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

De plus 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.

Egalement j'ai appris différentes manières de calculer la similarité entre des éléments notamment avec l'indice de Jaccard mais j'ai également découvert d'autres moyens 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 parfaites et possèdent des données manquantes ou erronées. Pour ceci, il faut fournir un travail supplémentaire pour pouvoir quand même exploiter des résultats malgré les données lacunaires.

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

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

2020-05-17T16:14:24Z

Rpajean : /* Exploitation de la base de données : */

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 devenue primordiale. Aujourd'hui, les utilisateurs ne peuvent plus faire directement le choix d'un produit, d’un média...
Pour cela, la plupart des entreprises utilisent des systèmes de recommandations. Ces systèmes de recommandations utilisent des algorithmes qui identifient des utilisateurs similaires et leurs recommandent des éléments susceptibles de les intéresser. 

Dans ce projet nous n'allons pas utiliser des bases de données relationnelles (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ées graphe, qui reprennent la théorie des graphes en utilisant des nœuds et des arcs pour représenter et stocker les données, rendent ces bases de données très efficaces pour traiter les relations. Nous allons utiliser ce type de base de donnée car nous nous intéressons aux liens entre les utilisateurs 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ées graphe et des algorithmes de recherche de similarité. Nous allons également utiliser les bases de données orientées 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 ses requêtes ce qui rend le langage visuel et facile à lire. Pour héberger les bases de données Neo4j , j'ai utilisé l’hébergeur Graphendb.
[[Fichier:Exemple_requete_ascii.png | frame | none | 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 importants pour pouvoir créer une base de données orientée graphe :
*Les Nœuds (Nodes) (Les éléments principaux)
*Les relations (Relationships) (Qui relient les nœuds entre eux)
*Les propriétés (Properties) (Les caractéristiques spécifiques des nœuds et relations)
*Les fonctions permettant de gérer ces objets

=== Créer des nœuds et des relations ===
Pour créer des nœuds (et des relations) il faut utiliser la fonction CREATE. 
Dans cypher un nœud est composé comme ceci : <code>(nomNoeudRacc:labelNoeud {propriétés})</code>
 
nomNoeudRacc est un nom du nœud raccourci pour le manipuler plus rapidement et facilement dans les requêtes. 
labelNoeud est le nom d'un "type" de nœud.
 
Les propriétés sont définies comme ceci : <code>{nomParametre:valeurParametre}</code>
 
Enfin les relations sont créées ainsi : <code>-[:NOMRELATION {propriétés}]-></code>
 
Voici un exemple de création de nœuds et d'une relation qui les relie ainsi que le résultat obtenu :
<nowiki>// 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</nowiki>
[[Fichier:Exemple_noeuds.png | center]]

=== Importer une base de données CSV et mise en place de la base de données ===
Nous voulons dans ce projet utiliser la base de données de MovieLens qui donne la notation des films par des utilisateurs. Le format de cette base de données est CSV et à un en-tête (header). 

Voici un lien qui vous mène vers la base de données sur les utilisateurs : [https://www.dropbox.com/s/piz58gre87s9miu/u.user.csv?] 
Pour importer cette base dans Neo4j j'ai utilisé les fonctions suivantes : 
<code>LOAD CSV WITH HEADERS FROM "lien de la base de données" AS line</code>
 
Puis vous pouvez utiliser "line" pour récupérer les données et les utiliser dans vos nœuds, relations ou propriétés.
 
J'ai créé ainsi des nœuds et des relations sous la forme : <code>(Film)-[DU_GENRE]->(Genre)</code>
 
Les nœuds films ont en paramètre le nom du film et la date de sortie du film. 
Les nœuds Genre ont en paramètre le genre du film (Action, Comédie, Horreur...). 
Voici le résultat pour le film Toy Story : 
[[Fichier:Exemple_genre.png | center]] 
Par la suite j'ai créé des nœuds Utilisateur en relation avec des nœuds Film sous la forme :<code>(Utilisateur)-[:A_VU {note}]->(Film)</code>
 
Les nœuds 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 mis au film. 
Voici le résultat pour Toy Story : 
[[Fichier:Exemple_utilisateur.png | 400px | thumb | none | Chaque relation A_VU possède la note de l'utilisateur sur le film relié]]
 
La base de données est prête on peut 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 ensembles 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 : 
[[Fichier:Formule_sim_jaccard.png | link=https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard | frame | center | Plus l'indice de Jaccard est proche de 1 plus les ensembles sont similaires.]] 

En appliquant cette formule aux films vus par les utilisateurs, je peux regarder les utilisateurs les plus similaires par rapport aux mêmes films qu'ils ont vus. 
Pour ceci, j'ai utilisé les commandes suivantes : 
<nowiki>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</nowiki>
 
Cependant ma base de données é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 ajouté qu'il fallait que les utilisateurs aient au moins vu 5 films en commun j'ai ajouté la requête suivante : <code>WHERE inter >= 5</code>
 
Et voici le résultat pour les 10 utilisateurs les plus similaires dans l'ordre décroissant : 

[[Fichier:Resultats_sim_jaccard.png | frame | none | 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 susceptibles 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 filtré 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 : 

[[Fichier:Resultat_recom_1.png | frame | center | Bridcage, Clerks et Rock sont donc susceptibles d’intéresser l'utilisateur 117.]]
 
Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png | frame | center | Toy Story, Usual Suspect, Mr. Holland's Opus, Sacré Grall et Aliens sont donc susceptibles d’intéresser l'utilisateur 162.]]

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

=== Importation de la base de données sur les patients contaminés et mise en place de la base de données ===
Pour étudier les données de la base j'ai importé la base de données sous la forme : <code>(Patient)-[:RESIDE]->(Ville)-[:LOCALISE]->(Pays)</code>
 
Les nœuds Pays et Villes possède l'unique paramètre "nom". 
Les nœuds 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 :
[[Fichier:Graphe_pays_ville.png | 700px | thumb | center| On remarque qu'il y a une erreur dans la base de données, ils ont mis France en tant que ville]]
 

=== Création de relations de contamination potentielle ===

J'ai par la suite ajouté des relations de contamination potentielle entre les individus de même ville et si un individu a une date d'apparition des symptômes antérieure à un autre individu.
 
Pour commencer je ne me suis intéressé qu'aux patients qui possèdent une date de symptôme (qui n'ont pas la date "NA"). 
Ensuite il fallait trouver un moyen de convertir les chaines de caractères "date", qui sont sous la forme "mois/jour/année", en 3 paramètres jour, mois, année en des entiers pour pouvoir comparer les dates. 
Pour ceci j'ai utilisé la fonction split pour supprimer les "/" et les mettre dans une liste. 
Puis j'ai utilisé la fonction SET pour créer les nouveaux paramètres. 
J'ai utilisé les requêtes suivantes : 
<nowiki>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])</nowiki>
 
Puis j'ai comparé les personnes venant des mêmes villes et qui ont eu des symptômes avant un autre patient pour créer les relations de contamination potentielle.

=== Exploitation de la base de données : ===

Dans les résultats qui suivent j'ai enlevé les nœuds qui n'avaient pas de date de symptôme car ils ne fournissent pas d'information. 

Voici le résultat pour la ville de Gansu en Chine : 
[[Fichier:Exemple_Gansu.png | frame | center | Les individus 89 et 150 ont une date d’apparition des symptômes antérieure à l'individu 151. Ils ont également le même jour d’apparition des symptômes; pour cette raison il n'y a pas de lien entre eux.]]
 
Voici le résultat pour la Chine entière : 

[[Fichier:Graphe_contamination_potentiel_Chine.png | 700px | thumb | center| On remarque que des "Clusters" (regroupements de nœuds) se sont formés sur Wuhan (le foyer de l'épidémie) et sur les plus grosses métropoles chinoises comme Beijin (la capitale de la Chine), Shaanxi ou Tianjin. Bien que cette information soit évidente, cela montre que le virus se propage plus facilement dans les lieux avec une forte démographie.]]
 
Ensuite j'ai décidé de regarder le nombre de personnes ayant visité Wuhan et vivant a Wuhan parmi les infectés pour voir si il y avait une relation. 
J'ai calculé le nombre de personnes ayant 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 : 
[[Fichier:Resultat_nbr_Wuhan.png | center]]
 
On remarque que sur les 800 contaminés, 170 personnes ont visité Wuhan et 143 vivaient à 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 venaient les premiers infectés (de la base de données). 
Avec les résultats de requêtes j'ai trouvé que 27 infectés sur 30 ont été à Wuhan parmi ces premiers infectés, ce qui montre bien que l'épidémie a commencé là-bas.
 
Enfin j'ai voulu voir dans quel ordre de pays s'est propagé le virus. 
Voici la liste des Pays que j'ai trouvé par ordre chronologique de contamination à partir de la base de données : 
[[Fichier:Resultat_liste_pays.png | center]]

== 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 : 
[https://github.com/TheSummer1502/VISI201.git https://github.com/TheSummer1502/VISI201.git]

== Source ==

Documentation sur le langage Cypher 
[https://neo4j.com/docs/cypher-manual/4.0/ https://neo4j.com/docs/cypher-manual/4.0/]
 
Pages sur les bases de données : 
Pour les bases de données relationelles 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle]
 
Pour les bases de données orientées graphe 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe]
 
Fonctionnement de la similarité de Jaccard : 
[https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard]
 
Site de Neo4j : 
[https://neo4j.com/ https://neo4j.com/]
 
Site de Graphendb : 
[https://www.graphenedb.com/ https://www.graphenedb.com/]

== Conclusion ==
A travers ce projet j'ai pu découvrir en général l'univers des bases de données 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ées graphe. J'ai pu voir qu'elles offraient beaucoup plus d'avantages lors de la manipulation de relations par rapport aux bases de données relationnelles.

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

De plus 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.

Egalement j'ai appris différentes manières de calculer la similarité entre des éléments notamment avec l'indice de Jaccard mais j'ai également découvert d'autres moyens 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 parfaites et possèdent des données manquantes ou erronées. Pour ceci, il faut fournir un travail supplémentaire pour pouvoir quand même exploiter des résultats malgré les données lacunaires.

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

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

2020-05-17T16:08:51Z

Rpajean :

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 devenue primordiale. Aujourd'hui, les utilisateurs ne peuvent plus faire directement le choix d'un produit, d’un média...
Pour cela, la plupart des entreprises utilisent des systèmes de recommandations. Ces systèmes de recommandations utilisent des algorithmes qui identifient des utilisateurs similaires et leurs recommandent des éléments susceptibles de les intéresser. 

Dans ce projet nous n'allons pas utiliser des bases de données relationnelles (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ées graphe, qui reprennent la théorie des graphes en utilisant des nœuds et des arcs pour représenter et stocker les données, rendent ces bases de données très efficaces pour traiter les relations. Nous allons utiliser ce type de base de donnée car nous nous intéressons aux liens entre les utilisateurs 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ées graphe et des algorithmes de recherche de similarité. Nous allons également utiliser les bases de données orientées 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 ses requêtes ce qui rend le langage visuel et facile à lire. Pour héberger les bases de données Neo4j , j'ai utilisé l’hébergeur Graphendb.
[[Fichier:Exemple_requete_ascii.png | frame | none | 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 importants pour pouvoir créer une base de données orientée graphe :
*Les Nœuds (Nodes) (Les éléments principaux)
*Les relations (Relationships) (Qui relient les nœuds entre eux)
*Les propriétés (Properties) (Les caractéristiques spécifiques des nœuds et relations)
*Les fonctions permettant de gérer ces objets

=== Créer des nœuds et des relations ===
Pour créer des nœuds (et des relations) il faut utiliser la fonction CREATE. 
Dans cypher un nœud est composé comme ceci : <code>(nomNoeudRacc:labelNoeud {propriétés})</code>
 
nomNoeudRacc est un nom du nœud raccourci pour le manipuler plus rapidement et facilement dans les requêtes. 
labelNoeud est le nom d'un "type" de nœud.
 
Les propriétés sont définies comme ceci : <code>{nomParametre:valeurParametre}</code>
 
Enfin les relations sont créées ainsi : <code>-[:NOMRELATION {propriétés}]-></code>
 
Voici un exemple de création de nœuds et d'une relation qui les relie ainsi que le résultat obtenu :
<nowiki>// 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</nowiki>
[[Fichier:Exemple_noeuds.png | center]]

=== Importer une base de données CSV et mise en place de la base de données ===
Nous voulons dans ce projet utiliser la base de données de MovieLens qui donne la notation des films par des utilisateurs. Le format de cette base de données est CSV et à un en-tête (header). 

Voici un lien qui vous mène vers la base de données sur les utilisateurs : [https://www.dropbox.com/s/piz58gre87s9miu/u.user.csv?] 
Pour importer cette base dans Neo4j j'ai utilisé les fonctions suivantes : 
<code>LOAD CSV WITH HEADERS FROM "lien de la base de données" AS line</code>
 
Puis vous pouvez utiliser "line" pour récupérer les données et les utiliser dans vos nœuds, relations ou propriétés.
 
J'ai créé ainsi des nœuds et des relations sous la forme : <code>(Film)-[DU_GENRE]->(Genre)</code>
 
Les nœuds films ont en paramètre le nom du film et la date de sortie du film. 
Les nœuds Genre ont en paramètre le genre du film (Action, Comédie, Horreur...). 
Voici le résultat pour le film Toy Story : 
[[Fichier:Exemple_genre.png | center]] 
Par la suite j'ai créé des nœuds Utilisateur en relation avec des nœuds Film sous la forme :<code>(Utilisateur)-[:A_VU {note}]->(Film)</code>
 
Les nœuds 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 mis au film. 
Voici le résultat pour Toy Story : 
[[Fichier:Exemple_utilisateur.png | 400px | thumb | none | Chaque relation A_VU possède la note de l'utilisateur sur le film relié]]
 
La base de données est prête on peut 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 ensembles 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 : 
[[Fichier:Formule_sim_jaccard.png | link=https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard | frame | center | Plus l'indice de Jaccard est proche de 1 plus les ensembles sont similaires.]] 

En appliquant cette formule aux films vus par les utilisateurs, je peux regarder les utilisateurs les plus similaires par rapport aux mêmes films qu'ils ont vus. 
Pour ceci, j'ai utilisé les commandes suivantes : 
<nowiki>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</nowiki>
 
Cependant ma base de données é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 ajouté qu'il fallait que les utilisateurs aient au moins vu 5 films en commun j'ai ajouté la requête suivante : <code>WHERE inter >= 5</code>
 
Et voici le résultat pour les 10 utilisateurs les plus similaires dans l'ordre décroissant : 

[[Fichier:Resultats_sim_jaccard.png | frame | none | 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 susceptibles 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 filtré 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 : 

[[Fichier:Resultat_recom_1.png | frame | center | Bridcage, Clerks et Rock sont donc susceptibles d’intéresser l'utilisateur 117.]]
 
Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png | frame | center | Toy Story, Usual Suspect, Mr. Holland's Opus, Sacré Grall et Aliens sont donc susceptibles d’intéresser l'utilisateur 162.]]

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

=== Importation de la base de données sur les patients contaminés et mise en place de la base de données ===
Pour étudier les données de la base j'ai importé la base de données sous la forme : <code>(Patient)-[:RESIDE]->(Ville)-[:LOCALISE]->(Pays)</code>
 
Les nœuds Pays et Villes possède l'unique paramètre "nom". 
Les nœuds 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 :
[[Fichier:Graphe_pays_ville.png | 700px | thumb | center| On remarque qu'il y a une erreur dans la base de données, ils ont mis France en tant que ville]]
 

=== Création de relations de contamination potentielle ===

J'ai par la suite ajouté des relations de contamination potentielle entre les individus de même ville et si un individu a une date d'apparition des symptômes antérieure à un autre individu.
 
Pour commencer je ne me suis intéressé qu'aux patients qui possèdent une date de symptôme (qui n'ont pas la date "NA"). 
Ensuite il fallait trouver un moyen de convertir les chaines de caractères "date", qui sont sous la forme "mois/jour/année", en 3 paramètres jour, mois, année en des entiers pour pouvoir comparer les dates. 
Pour ceci j'ai utilisé la fonction split pour supprimer les "/" et les mettre dans une liste. 
Puis j'ai utilisé la fonction SET pour créer les nouveaux paramètres. 
J'ai utilisé les requêtes suivantes : 
<nowiki>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])</nowiki>
 
Puis j'ai comparé les personnes venant des mêmes villes et qui ont eu des symptômes avant un autre patient pour créer les relations de contamination potentielle.

=== Exploitation de la base de données : ===

Dans les résultats qui suivent j'ai enlevé les nœuds qui n'avaient pas de date de symptôme car il ne fournissent pas d'information. 

Voici le résultat pour la ville de Gansu en Chine : 
[[Fichier:Exemple_Gansu.png | frame | center | Les individus 89 et 150 ont une date d’apparition des symptômes antérieure à l'individu 151. Ils ont également le même jour d’apparition des symptômes; pour cette raison il n'y a pas de lien entre eux.]]
 
Voici le résultat pour la Chine entière : 

[[Fichier:Graphe_contamination_potentiel_Chine.png | 700px | thumb | center| On remarque que des "Clusters" (regroupements de nœuds) se sont formés sur Wuhan (le foyer de l'épidémie) et sur les plus grosses métropoles chinoises comme Beijin (la capitale de la Chine), Shaanxi ou Tianjin. Bien que cette information soit évidente, cela montre que le virus se propage plus facilement dans les lieux avec une forte démographie.]]
 
Ensuite j'ai décidé de regarder le nombre de personnes ayant visité Wuhan et vivant a Wuhan parmi les infectés pour voir si il y avait une relation. 
J'ai calculé le nombre de personnes ayant 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 : 
[[Fichier:Resultat_nbr_Wuhan.png | center]]
 
On remarque que sur les 800 contaminés, 170 personnes ont visité Wuhan et 143 vivaient à 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 venaient les premiers infectés (de la base de données). 
Avec les résultats de requêtes j'ai trouvé que 27 infectés sur 30 ont été à Wuhan parmi ces premiers infectés, ce qui montre bien que l'épidémie a commencé là-bas.
 
Enfin j'ai voulu voir dans quel ordre de pays s'est propagé le virus. 
Voici la liste des Pays que j'ai trouvé par ordre chronologique de contamination à partir de la base de données : 
[[Fichier:Resultat_liste_pays.png | center]]

== 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 : 
[https://github.com/TheSummer1502/VISI201.git https://github.com/TheSummer1502/VISI201.git]

== Source ==

Documentation sur le langage Cypher 
[https://neo4j.com/docs/cypher-manual/4.0/ https://neo4j.com/docs/cypher-manual/4.0/]
 
Pages sur les bases de données : 
Pour les bases de données relationelles 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle]
 
Pour les bases de données orientées graphe 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe]
 
Fonctionnement de la similarité de Jaccard : 
[https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard]
 
Site de Neo4j : 
[https://neo4j.com/ https://neo4j.com/]
 
Site de Graphendb : 
[https://www.graphenedb.com/ https://www.graphenedb.com/]

== Conclusion ==
A travers ce projet j'ai pu découvrir en général l'univers des bases de données 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ées graphe. J'ai pu voir qu'elles offraient beaucoup plus d'avantages lors de la manipulation de relations par rapport aux bases de données relationnelles.

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

De plus 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.

Egalement j'ai appris différentes manières de calculer la similarité entre des éléments notamment avec l'indice de Jaccard mais j'ai également découvert d'autres moyens 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 parfaites et possèdent des données manquantes ou erronées. Pour ceci, il faut fournir un travail supplémentaire pour pouvoir quand même exploiter des résultats malgré les données lacunaires.

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

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

2020-05-17T15:55:29Z

Rpajean :

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 devenue primordiale. Aujourd'hui, les utilisateurs ne peuvent plus faire directement le choix d'un produit, d’un média...
Pour cela, la plupart des entreprises utilisent des systèmes de recommandations. Ces systèmes de recommandations utilisent des algorithmes qui identifient des utilisateurs similaires et leurs recommandent des éléments susceptibles de les intéresser. 

Dans ce projet nous n'allons pas utiliser des bases de données relationnelles (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ées graphe, qui reprennent la théorie des graphes en utilisant des nœuds et des arcs pour représenter et stocker les données, rendent ces bases de données très efficaces pour traiter les relations. Nous allons utiliser ce type de base de donnée car nous nous intéressons aux liens entre les utilisateurs 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ées graphe et des algorithmes de recherche de similarité. Nous allons également utiliser les bases de données orientées 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 ses requêtes ce qui rend le langage visuel et facile à lire. Pour héberger les bases de données Neo4j , j'ai utilisé l’hébergeur Graphendb.
[[Fichier:Exemple_requete_ascii.png | frame | none | 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 importants pour pouvoir créer une base de données orientée graphe :
*Les Nœuds (Nodes) (Les éléments principaux)
*Les relations (Relationships) (Qui relient les nœuds entre eux)
*Les propriétés (Properties) (Les caractéristiques spécifiques des nœuds et relations)
*Les fonctions permettant de gérer ces objets

=== Créer des nœuds et des relations ===
Pour créer des nœuds (et des relations) il faut utiliser la fonction CREATE. 
Dans cypher un nœud est composé comme ceci : <code>(nomNoeudRacc:labelNoeud {propriétés})</code>
 
nomNoeudRacc est un nom du nœud raccourci pour le manipuler plus rapidement et facilement dans les requêtes. 
labelNoeud est le nom d'un "type" de nœud.
 
Les propriétés sont définies comme ceci : <code>{nomParametre:valeurParametre}</code>
 
Enfin les relations sont créées ainsi : <code>-[:NOMRELATION {propriétés}]-></code>
 
Voici un exemple de création de nœuds et d'une relation qui les relie ainsi que le résultat obtenu :
<nowiki>// 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</nowiki>
[[Fichier:Exemple_noeuds.png | center]]

=== Importer une base de données CSV et mise en place de la base de données ===
Nous voulons dans ce projet utiliser la base de données de MovieLens qui donne la notation des films par des utilisateurs. Le format de cette base de données est CSV et à un en-tête (header). 

Voici un lien qui vous mène vers la base de données sur les utilisateurs : [https://www.dropbox.com/s/piz58gre87s9miu/u.user.csv?] 
Pour importer cette base dans Neo4j j'ai utilisé les fonctions suivantes : 
<code>LOAD CSV WITH HEADERS FROM "lien de la base de données" AS line</code>
 
Puis vous pouvez utiliser "line" pour récupérer les données et les utiliser dans vos nœuds, relations ou propriétés.
 
J'ai créé ainsi des nœuds et des relations sous la forme : <code>(Film)-[DU_GENRE]->(Genre)</code>
 
Les nœuds films ont en paramètre le nom du film et la date de sortie du film. 
Les nœuds Genre ont en paramètre le genre du film (Action, Comédie, Horreur...). 
Voici le résultat pour le film Toy Story : 
[[Fichier:Exemple_genre.png | center]] 
Par la suite j'ai créé des nœuds Utilisateur en relation avec des nœuds Film sous la forme :<code>(Utilisateur)-[:A_VU {note}]->(Film)</code>
 
Les nœuds 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 mis au film. 
Voici le résultat pour Toy Story : 
[[Fichier:Exemple_utilisateur.png | 400px | thumb | none | Chaque relation A_VU possède la note de l'utilisateur sur le film relié]]
 
La base de données est prête on peut 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 ensembles 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 : 
[[Fichier:Formule_sim_jaccard.png | link=https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard | frame | center | Plus l'indice de Jaccard est proche de 1 plus les ensembles sont similaires.]] 

En appliquant cette formule aux films vus par les utilisateurs, je peux regarder les utilisateurs les plus similaires par rapport aux mêmes films qu'ils ont vus. 
Pour ceci, j'ai utilisé les commandes suivantes : 
<nowiki>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</nowiki>
 
Cependant ma base de données é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 ajouté qu'il fallait que les utilisateurs aient au moins vu 5 films en commun j'ai ajouté la requête suivante : <code>WHERE inter >= 5</code>
 
Et voici le résultat pour les 10 utilisateurs les plus similaires dans l'ordre décroissant : 

[[Fichier:Resultats_sim_jaccard.png | frame | none | 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 susceptibles 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 filtré 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 : 

[[Fichier:Resultat_recom_1.png | frame | center | Bridcage, Clerks et Rock sont donc susceptibles d’intéresser l'utilisateur 117.]]
 
Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png | frame | center | Toy Story, Usual Suspect, Mr. Holland's Opus, Sacré Grall et Aliens sont donc susceptibles d’intéresser l'utilisateur 162.]]

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

=== Importation de la base de données sur les patients contaminés et mise en place de la base de données ===
Pour étudier les données de la base j'ai importé la base de données sous la forme : <code>(Patient)-[:RESIDE]->(Ville)-[:LOCALISE]->(Pays)</code>
 
Les nœuds Pays et Villes possède l'unique paramètre "nom". 
Les nœuds 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 :
[[Fichier:Graphe_pays_ville.png | 700px | thumb | center| On remarque qu'il y a une erreur dans la base de données, ils ont mis 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 : 
<nowiki>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])</nowiki>
 
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 : 
[[Fichier:Exemple_Gansu.png | frame | center | 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 : 

[[Fichier:Graphe_contamination_potentiel_Chine.png | 700px | thumb | center| 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 : 
[[Fichier:Resultat_nbr_Wuhan.png | center]]
 
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 : 
[[Fichier:Resultat_liste_pays.png | center]]

== 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 : 
[https://github.com/TheSummer1502/VISI201.git https://github.com/TheSummer1502/VISI201.git]

== Source ==

Documentation sur le langage Cypher 
[https://neo4j.com/docs/cypher-manual/4.0/ https://neo4j.com/docs/cypher-manual/4.0/]
 
Pages sur les bases de données : 
Pour les bases de données relationelles 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle]
 
Pour les bases de données orienté graphe 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe]
 
Fonctionement de la similarité de Jaccard : 
[https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard]
 
Site de Neo4j : 
[https://neo4j.com/ https://neo4j.com/]
 
Site de Graphendb : 
[https://www.graphenedb.com/ https://www.graphenedb.com/]

== 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.

De plus 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.

Egalement j'ai 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.

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

2020-05-17T11:44:42Z

Rpajean :

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.
[[Fichier:Exemple_requete_ascii.png | frame | none | 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 : <code>(nomNoeudRacc:labelNoeud {propriétés})</code>
 
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 : <code>{nomParametre:valeurParametre}</code>
 
Enfin les relations sont crées ainsi : <code>-[:NOMRELATION {propriétés}]-></code>
 
Voici un exemple de création de noeuds et d'une relation qui les relient ainsi que le résultat obtenu :
<nowiki>// 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</nowiki>
[[Fichier:Exemple_noeuds.png | center]]

=== 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 : [https://www.dropbox.com/s/piz58gre87s9miu/u.user.csv?] 
Pour importer cette base dans Neo4j j'ai utilisé les fonctions suivantes : 
<code>LOAD CSV WITH HEADERS FROM "lien de la base de donnée" AS line</code>
 
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 : <code>(Film)-[DU_GENRE]->(Genre)</code>
 
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 : 
[[Fichier:Exemple_genre.png | center]] 
Par la suite j'ai crée des noeuds Utilisateur en relation avec des noeuds Film sous la forme :<code>(Utilisateur)-[:A_VU {note}]->(Film)</code>
 
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 : 
[[Fichier:Exemple_utilisateur.png | 400px | thumb | none | 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 : 
[[Fichier:Formule_sim_jaccard.png | link=https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard | frame | center | 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 : 
<nowiki>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</nowiki>
 
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 : <code>WHERE inter >= 5</code>
 
Et voici le resultat pour les 10 utilisateur les plus similaires dans l'ordre décroissant : 

[[Fichier:Resultats_sim_jaccard.png | frame | none | 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 : 

[[Fichier:Resultat_recom_1.png | frame | center | Bridcage, Clerks et Rock sont donc susceptible d’intéresser l'utilisateur 117.]]
 
Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png | frame | center | 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 : <code>(Patient)-[:RESIDE]->(Ville)-[:LOCALISE]->(Pays)</code>
 
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 :
[[Fichier:Graphe_pays_ville.png | 700px | thumb | center| 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 : 
<nowiki>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])</nowiki>
 
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 : 
[[Fichier:Exemple_Gansu.png | frame | center | 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 : 

[[Fichier:Graphe_contamination_potentiel_Chine.png | 700px | thumb | center| 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 : 
[[Fichier:Resultat_nbr_Wuhan.png | center]]
 
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 : 
[[Fichier:Resultat_liste_pays.png | center]]

== 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 : 
[https://github.com/TheSummer1502/VISI201.git https://github.com/TheSummer1502/VISI201.git]

== Source ==

Documentation sur le langage Cypher 
[https://neo4j.com/docs/cypher-manual/4.0/ https://neo4j.com/docs/cypher-manual/4.0/]
 
Pages sur les bases de données : 
Pour les bases de données relationelles 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle]
 
Pour les bases de données orienté graphe 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe]
 
Fonctionement de la similarité de Jaccard : 
[https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard]
 
Site de Neo4j : 
[https://neo4j.com/ https://neo4j.com/]
 
Site de Graphendb : 
[https://www.graphenedb.com/ https://www.graphenedb.com/]

== 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.

De plus 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.

Egalement j'ai 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.

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

2020-05-17T11:40:13Z

Rpajean :

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.
[[Fichier:Exemple_requete_ascii.png | frame | none | 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 : <code>(nomNoeudRacc:labelNoeud {propriétés})</code>
 
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 : <code>{nomParametre:valeurParametre}</code>
 
Enfin les relations sont crées ainsi : <code>-[:NOMRELATION {propriétés}]-></code>
 
Voici un exemple de création de noeuds et d'une relation qui les relient ainsi que le résultat obtenu :
<nowiki>// 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</nowiki>
[[Fichier:Exemple_noeuds.png | center]]

=== 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 : [https://www.dropbox.com/s/piz58gre87s9miu/u.user.csv?] 
Pour importer cette base dans Neo4j j'ai utilisé les fonctions suivantes : 
<code>LOAD CSV WITH HEADERS FROM "lien de la base de donnée" AS line</code>
 
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 : <code>(Film)-[DU_GENRE]->(Genre)</code>
 
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 : 
[[Fichier:Exemple_genre.png | center]] 
Par la suite j'ai crée des noeuds Utilisateur en relation avec des noeuds Film sous la forme :<code>(Utilisateur)-[:A_VU {note}]->(Film)</code>
 
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 : 
[[Fichier:Exemple_utilisateur.png | 400px | thumb | none | 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 : 
[[Fichier:Formule_sim_jaccard.png | link=https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard | frame | center | 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 : 
<nowiki>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</nowiki>
 
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 : <code>WHERE inter >= 5</code>
 
Et voici le resultat pour les 10 utilisateur les plus similaires dans l'ordre décroissant : 

[[Fichier:Resultats_sim_jaccard.png | frame | none | 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 : 

[[Fichier:Resultat_recom_1.png | frame | center | Bridcage, Clerks et Rock sont donc susceptible d’intéresser l'utilisateur 117.]]
 
Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png | frame | center | 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 : <code>(Patient)-[:RESIDE]->(Ville)-[:LOCALISE]->(Pays)</code>
 
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 :
[[Fichier:Graphe_pays_ville.png | 700px | thumb | center| 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 : 
<nowiki>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])</nowiki>
 
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 : 
[[Fichier:Exemple_Gansu.png | frame | center | 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 : 

[[Fichier:Graphe_contamination_potentiel_Chine.png | 700px | thumb | center| 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 : 
[[Fichier:Resultat_nbr_Wuhan.png | center]]
 
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 : 
[[Fichier:Resultat_liste_pays.png | center]]

== 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 : 
[https://github.com/TheSummer1502/VISI201.git]

== Source ==

Documentation sur le langage Cypher 
[https://neo4j.com/docs/cypher-manual/4.0/ https://neo4j.com/docs/cypher-manual/4.0/]
 
Pages sur les bases de données : 
Pour les bases de données relationelles 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle]
 
Pour les bases de données orienté graphe 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe]
 
Fonctionement de la similarité de Jaccard : 
[https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard]
 
Site de Neo4j : 
[https://neo4j.com/ https://neo4j.com/]
 
Site de Graphendb : 
[https://www.graphenedb.com/ https://www.graphenedb.com/]

== 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.

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

2020-05-17T11:37:53Z

Rpajean :

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.
[[Fichier:Exemple_requete_ascii.png | frame | none | 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 : <code>(nomNoeudRacc:labelNoeud {propriétés})</code>
 
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 : <code>{nomParametre:valeurParametre}</code>
 
Enfin les relations sont crées ainsi : <code>-[:NOMRELATION {propriétés}]-></code>
 
Voici un exemple de création de noeuds et d'une relation qui les relient ainsi que le résultat obtenu :
<nowiki>// 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</nowiki>
[[Fichier:Exemple_noeuds.png | center]]

=== 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 : [https://www.dropbox.com/s/piz58gre87s9miu/u.user.csv?] 
Pour importer cette base dans Neo4j j'ai utilisé les fonctions suivantes : 
<code>LOAD CSV WITH HEADERS FROM "lien de la base de donnée" AS line</code>
 
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 : <code>(Film)-[DU_GENRE]->(Genre)</code>
 
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 : 
[[Fichier:Exemple_genre.png | center]] 
Par la suite j'ai crée des noeuds Utilisateur en relation avec des noeuds Film sous la forme :<code>(Utilisateur)-[:A_VU {note}]->(Film)</code>
 
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 : 
[[Fichier:Exemple_utilisateur.png | 400px | thumb | none | 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 : 
[[Fichier:Formule_sim_jaccard.png | link=https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard | frame | center | 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 : 
<nowiki>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</nowiki>
 
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 : <code>WHERE inter >= 5</code>
 
Et voici le resultat pour les 10 utilisateur les plus similaires dans l'ordre décroissant : 

[[Fichier:Resultats_sim_jaccard.png | frame | none | 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 : 

[[Fichier:Resultat_recom_1.png | frame | center | Bridcage, Clerks et Rock sont donc susceptible d’intéresser l'utilisateur 117.]]
 
Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png | frame | center | 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 : <code>(Patient)-[:RESIDE]->(Ville)-[:LOCALISE]->(Pays)</code>
 
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 :
[[Fichier:Graphe_pays_ville.png | 700px | thumb | center| 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 : 
<nowiki>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])</nowiki>
 
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 : 
[[Fichier:Exemple_Gansu.png | frame | center | 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 : 

[[Fichier:Graphe_contamination_potentiel_Chine.png | 700px | thumb | center| 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 : 
[[Fichier:Resultat_nbr_Wuhan.png | center]]
 
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 : 
[[Fichier:Resultat_liste_pays.png | center]]

== 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 : 
[https://github.com/TheSummer1502/VISI201.git]

== Source ==

Documentation sur le langage Cypher 
[https://neo4j.com/docs/cypher-manual/4.0/]
 
Pages sur les bases de données : 
Pour les bases de données relationelles 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_relationnelle]
 
Pour les bases de données orienté graphe 
[https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es_orient%C3%A9e_graphe]
 
Fonctionement de la similarité de Jaccard : 
[https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard]
 
Site de Neo4j : 
[https://neo4j.com/]
 
Site de Graphendb : 
[https://www.graphenedb.com/]

== 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.

Fichier:Resultat liste pays.png

2020-05-17T11:29:00Z

Rpajean : Rpajean a téléversé une nouvelle version de Fichier:Resultat liste pays.png

Fichier:Resultat liste pays.png

2020-05-17T11:28:01Z

Rpajean : Rpajean a téléversé une nouvelle version de Fichier:Resultat liste pays.png

Fichier:Exemple Gansu.png

2020-05-17T11:12:35Z

Rpajean :

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

2020-05-17T10:53:10Z

Rpajean :

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

2020-05-17T10:47:03Z

Rpajean :

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

2020-05-17T10:36:16Z

Rpajean :

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

2020-05-17T10:22:13Z

Rpajean :

Fichier:Exemple utilisateur.png

2020-05-17T10:13:53Z

Rpajean :

Fichier:Exemple genre.png

2020-05-17T10:07:37Z

Rpajean :

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

2020-05-17T09:54:46Z

Rpajean :

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

2020-05-16T19:45:47Z

Rpajean :

VISI201 CMI : visite de laboratoire

2020-05-16T19:17:31Z

Rpajean : /* Sujets réalisés (2019-2020) */

* Cours du semestre 2 du parcours CMI Informatique (licence INFO).

* Responsable pour 2019--2020: Jacques-Olivier Lachaud
* Responsable pour 2018--2019: Jacques-Olivier Lachaud
* Responsable pour 2017--2018: Jacques-Olivier Lachaud
* Responsable pour 2016--2017: Jacques-Olivier Lachaud

= Descriptif =

L'objectif du module est de faire découvrir les laboratoires, le monde de la recherche et les enseignants-chercheurs et chercheurs, ainsi que la réflexion scientifique. Cela se fait de deux manières.

D'abord, une partie de ce module consiste à assister à des séminaires dédiés aux étudiants CMI Informatique et Mathématique (1 fois par mois, les jeudi après-midi). [[http://www.lama.univ-savoie.fr/index.php?use=seminaires&&lang=fr&equipe=cmi&annee=1&lang=fr Planning des séminaires CMI]]

Ces séminaires "grand public" portent sur des sujets variées en informatique et mathématiques.

Les étudiants choisissent ensuite d'approfondir un sujet proposé par les enseignants, ou un sujet motivé de leur choix (en accord avec le responsable du module). Ce travail se fait en interaction avec un tuteur académique (5-6 contacts au moins). Ce travail personnel tuteuré donne lieu à la rédaction d'une synthèse sur le sujet sous forme d'une page wiki/web, ainsi que d'un mini-exposé.

= Sujets réalisés (2019-2020) =

* Compression et transformée de Burrow-Wheeler, Simon Léonard (Tuteur : Pierre Hyvernat)
* Backtracking, Simon Pichenot (Tuteur : Pierre Hyvernat)
* Transfert de couleur (version 2), Florian Dufaure (Tuteur : Jacques-Olivier Lachaud)
* [[Génération fractale de terrains]], Hugo Rey (Tuteur : Jacques-Olivier Lachaud)
* Architectures Orientées Micro-Services, Romain Negro (David Télisson)
* Apprentissage automatique, Evan L'Huissier (Tuteur : Tom Hirschowitz)
* Algorithmes probabilistes/déterministes pour tester la primalité d'un entier, Juliette Neyrat (Tuteur : Sébastien Tavenas)
* [[Base de données orientées Graphe et similarité]], Romain Pajean (Gérald Cavallini)
* Modèles d'évolution de populations, Théo Guesdon (Tuteur : Jimmy Garnier)

= Sujets proposés (2019-2020) =

* Compression et transformée de Burrow-Wheeler
* Backtracking
* Transfert de couleur (version 2)
* Génération fractale de terrains
* Architectures Orientées Micro-Services
* Apprentissage automatique
* Algorithmes probabilistes/déterministes pour tester la primalité d'un entier
* Base de données orientées Graphe, similarité et modèles prédictifs

== Compression et transformée de Burrow-Wheeler ==

* Tuteur : Pierre Hyvernat
* Résumé : La transformée de Burrow-Wheeler est l'étape clé de l'algorithme de compression bzip2. C'est une transformation de texte (suite d'octet) qui ne modifie pas la taille, mais ajoute suffisamment de motifs redondants pour améliorer un autre algorithme de compression (algorithme de Huffman dans le cas de bzip2)
* Objectif : L'objectif est de comprendre le fonctionnement de cette transformation (et de son inverse) et d'implémenter une version naïve de l'algorithme de compression / décompression et de tester sur quelques exemples. Les améliorations de l'algorithme seront ensuite abordées.
* Liens : Burrows, Michael; Wheeler, David J. (1994), A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation [[https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf PDF]]

== Backtracking ==

* Tuteur : Pierre Hyvernat
* Résumé et objectif : La notion de "backtracking" est fondamentale en algorithmique : il s'agit essentiellement de tester des solutions partielles à un problème, en revenant en arrière dès qu'une incohérence est découverte. Le point de départ sera le fascicule 4.5b de D. Knuth "Introduction to backtracking" et permettra de se familiariser avec les concepts, la terminology et des exemples, qu'il faudra implémenter. Une suite possible sera la notion de réduction de problèmes et l'algorithme-X qui permet de "factoriser" de nombreux problèmes de backtracking en un seul algorithme.
* Liens : D. Knuth, "the art of computer programming introduction to backtracking" [[https://www-cs-faculty.stanford.edu/~knuth/fasc5b.ps.gz PS]]

== Transfert de couleur (version 2) ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le transfert de couleurs de l'image Y vers l'image X consiste à repeindre "au mieux" l'image X avec la palette de couleurs de l'image Y. L'image repeinte X' a alors les mêmes couleurs que l'image Y (mais les pixels ne sont pas répartis pareils). Voir l'exemple de transfert ci-dessous. Il existe plusieurs techniques de transfert de couleurs, mais nous étudierons une technique basée sur le transport optimal. Comme c'est un problème assez difficile dans le cas général, nous étudierons une variante dite par coupe 1D, qui simplifiera considérablement le problème de transport.
{| class="wikitable alternance center"
|+ Transfert de couleur
|----
! scope="col" | Input !! scope="col" | Output
|----
| [[Fichier:horseshoe.jpg|200px]] || [[Fichier:horseshoe-fjord-n40.jpg|200px]]
|----
| [[Fichier:fjord.jpg|200px]] || [[Fichier:fjord-horseshoe-n40.jpg|200px]]
|}
* Objectifs:
*# Comprendre la version 1 fait par [[https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images Lucas Chardonnet]], comprendre les qualités et limites de l'approche (sur quelle type d'image ça marche assez bien par exemple)
*# Adapter l'algorithme pour qu'il puisse traiter des images de tailles différentes
*# Réécrire le code en utilisant la bibliothèque python NUMPY pour accélérer les calculs
*# Changer les espaces de couleurs utilisés: RGB ne convient pas très bien pour mesurer le coût du transport. Transformer le code pour qu'il puisse utiliser plutôt l'espace [[https://fr.wikipedia.org/wiki/L*a*b*_CIE_1976 L*a*b*]] mieux adapté pour calculer des distances entre couleurs.
* Liens:
** la page de [[https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images Lucas Chardonnet]]
** [[https://en.wikipedia.org/wiki/Color_mapping Transfert de couleur Wikipedia]]
** [[https://hal.archives-ouvertes.fr/tel-01246096/file/hdr_hal2.pdf Habilitation de N. Papadakis]] (regardez les images plutôt).

== Génération fractale de terrains ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: La génération procédurale de terrain est très utilisée en modélisation 3D et dans les jeux vidéos, afin de générer rapidement des paysages pseudo-réalistes que l'on étoffera ensuite de façon plus manuelle. On propose d'étudier et d'implémenter un algorithme classique, dit "algorithme Diamant-Carré". Cet algorithme récursif permet de générer une carte d'élévation. Selon les paramètres données, le résultat peut ressembler aux cartes d'altitude de haute montagne ou des collines plus douces.
{| class="wikitable alternance center"
|+ Génération fractale de terrain par algorithme diamand carré
|----
! scope="col" | Elévations générées !! scope="col" | Colorisation !! scope="col" | Visualisation 3D
|----
| [[Fichier:Diamond-Square_texture.png|200px]] || [[Fichier:Diamond-Square_heightmap.png|200px]] || [[Fichier:Terragen.jpg|200px]]
|}

* Objectifs:
*# Comprendre et implémenter l'algorithme Diamant-Carré
*# Comprendre comment paramétrer cet algorithme pour qu'il génère des montagnes bien abrupte à haute altitude ou des collines à basse altitude.
*# Fabriquer une image de couleur/texture qui va associer des couleurs aux altitudes générées (e.g. forcer du bleu sous l'altitude zero, ajouter de la neige, des lacs, de la forêt)
*# Générer un fichier 3D (par exemple OBJ) à partir de ces deux images (l'image des hauteurs et l'image des couleurs) pour pouvoir faire de beau rendu 3D (sous blender par exemple)
* Liens:
** La page [[https://fr.wikipedia.org/wiki/Algorithme_Diamant-Carr%C3%A9 Wikipedia]] de l'algorithme
** La page [[https://en.wikipedia.org/wiki/Wavefront_.obj_file Wikipedia]] du format OBJ

== Architectures Orientées Micro-Services ==

* Tuteur : David Télisson
* Résumé : Les architectures des applications logicielles distribuées de grandes envergures ont évolué à partir du début des années 2000, d’une application molithique déployée sur un serveur d’application (JEE, TomCat, etc.) vers des solutions fortement répartis déployées sous formes de services. On parle alors d’architectures orientées services qui se traduisent par le développement et le déploiement de services logiciels interrogeables via des protocoles dédiés (par exemple SOAP) et des API (REST). Cette tendance, corrélée aux nouvelles méthodes de management des projets informatiques (méthodes agiles, intégration continue, DevOps1), s’est accentué ces dernières années et a fait émergé un « nouveau » paradigme : le micro-service. Plusieurs aspects caractérisent un micro-service :
** fonctionnalité unique
** flexibilité technologie
** équipe de développement réduite
** déploiement ciblé
** support de la montée en charge (scalabilité)
** tests facilités et intégrés au processus de développement (TDD2)
* Objectifs du projet :
*# Etudier et comprendre les concepts liés aux micro-services (API, conteneurisation, framework, etc.)
*# Implémentez un PoC (proof of concept) qui démontre qu’une application peut se construire dynamiquement par agrégation de micro-services développés avec des langages différents (Python, JS et Java), déployés sur des plateformes différentes (Django, Node et Glassfish) et disponibles sous formes de conteneurs dans le cloud (Azure)
*# Livrable attendu : un tutoriel « à la OpenClassRooms »
* Liens pour démarrer :
** https://mbaron.developpez.com/cours/microservices/introduction-generalites
** https://openclassrooms.com/fr/courses/4668056-construisez-des-microservices

== Apprentissage automatique ==

* Tuteur : Tom Hirschowitz
* Résumé : L'apprentissage automatique est un ensemble de techniques algorithmiques visant à écrire des programmes qui améliorent leurs performances au cours du temps. Le sujet consiste en une initiation à cette idée par l'exemple, à base de ressources telles que https://colah.github.io/posts/2015-08-Backprop et http://neuralnetworksanddeeplearning.com .

== Algorithmes probabilistes/déterministes pour tester la primalité d'un entier ==

* Tuteur : Sébastien Tavenas
* Pouvoir tester si un entier est un nombre premier semble être une brique de base si l'on souhaite faire de l'arithmétique sur un ordinateur. Le crible d'Érathostène enseigné dans les petites classes se montre beaucoup trop lent en pratique. L'algorithme probabiliste utilisé le plus rapide est le test de Fermat. Or, si on regarde les algorithmes des librairies "génériques", on peut s'apercevoir que la fonction 'mpz_probab_prime_p' de la librairie 'gmp' sur c++ utilise un test probabiliste de Miller-Rabin, la fonction 'isPrime' de la classe 'Prime' dans java utilise aussi un test de Miller-Rabin mais qui est déterminisé, alors que la fonction 'isprime' de la librairie 'sympy' dans python effectue un test de Miller-Rabin si l'entier est plus petit que 2^64 et un test BPSW fort si l'entier est plus grand. Ainsi, une fonction déjà implémentée de test de primalité peut se tromper ou non, être instantanée ou moins. Que dire alors de l'algorithme polynomial déterministe et toujours correct proposé par AKS?
* Objectifs :
*# Comprendre quelques tests de primalité et comment l'aléatoire est utilisé dans ces algorithmes
*# Comprendre la notion de nombre pseudopremier qui explique, entre autre, quand il vaut mieux utiliser le test de Fermat ou celui de Miller-Rabin
*# Programmer quelques uns des ces tests et les comparer
*# Essayer de dérandomiser ces tests à l'aide de hitting-sets précalculés

* Liens pour commencer
** [[https://en.wikipedia.org/wiki/Primality_test Tests de primalité]]

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

* Tuteur : Gérald Cavallini
* Résumé : Avec l’avènement du BigDatas, dans bien des cas le choix d’un produit, d’un média, d’un voyage ... ne peut plus être direct. Il s’appuie sur des systèmes de recommandations. L’importance financière de ces systèmes est énorme Amazon estime à 30% les ventes supplémentaires dues à son système de recommandation. Ces systèmes s’appuient sur des calculs statistiques et des algorithmes de recherche de similarité. Ces algorithmes expriment la distance entre des objets, ce qui permet par exemple d’identifier des utilisateurs(consommateurs, électeur ...) similaire et de recommander leurs choix.
* Objectifs :
*# Mettre en œuvre différents algorithmes de recherche de similarité ( similarité de Jaquard, similarité cosinus...) dans une base de donnée orientées Graphe Neo4j.
*# Proposer un système de recommandation de film à partir de la base MovieLens (Notation de films par des utilisateurs).
*# Proposer un une validation du modèle prédictif.
* Liens pour commencer
** https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard
** https://www.machinelearningplus.com/nlp/cosine-similarity/
** https://neo4j.com/
** https://movielens.org/

[[Fichier:Neo4j.jpg|400px]]

= Sujets réalisés (2018-2019) =

* [[Transport optimal par coupe 1D et transfert de couleurs entre images]] (Lucas CHARDONNET)
* [[Génération et résolution de labyrinthes II]] (Romain THEODET)
* [[Rest & Pub-Sub : protocole hybride pour l'IoT]] (Ewan RAKOTOANOSY)
* [[La suite de Conway et la classification périodique des "éléments"]] (Yohann THEPAUT)
* [[Initiation à la démonstration sur ordinateur et certification de logiciel]] (Loïc DORNET)
* [[Dilemme du prisonnier]] (Christophe CARMAGNAC)

= Sujets proposés (2018-2019) =

* Transport optimal par coupe 1D et transfert de couleurs entre images
* Génération et résolution de labyrinthes II
* REST + Pub/Sub : protocole hybride pour l’IoT
* La suite de Conway et la classification périodique des "éléments"
* Initiation à la démonstration sur ordinateur et certification de logiciel
* Algorithmes probabilistes/déterministes pour tester la primalité d'un entier
* Dilemme du prisonnier

== Transport optimal par coupe 1D et transfert de couleurs entre images ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le transfert de couleurs de l'image Y vers l'image X consiste à repeindre "au mieux" l'image X avec la palette de couleurs de l'image Y. L'image repeinte X' a alors les mêmes couleurs que l'image Y (mais les pixels ne sont pas répartis pareils). Voir l'exemple de transfert ci-dessous. Il existe plusieurs techniques de transfert de couleurs, mais nous étudierons une technique basée sur le transport optimal. Comme c'est un problème assez difficile dans le cas général, nous verrons une variante dite par coupe 1D, qui simplifiera considérablement le problème de transport.

[[Fichier:Ex-transfert-couleur-OT.png]]

* Objectifs:
*# comprendre ce qu'est une image niveaux couleur, et ce qu'on appelle le transfert de couleurs.
*# comprendre le principe du transport optimal (discret).
*# comprendre et décrire le principe du transport optimal par coupe 1D, et comment se fait le calcul du meilleur transport dans ce cas.
*# Coder un programme de transfert de couleur, qui prend deux images couleurs et réalise le transfert de couleurs.
*# On pourra ensuite réfléchir à quelques améliorations simples (espace couleur YUV, grouper les pixels).
* Liens pour démarrer
** Le vrai "Transport Optimal" est vite très mathématique (ce sont des mesures qui sont transportées), mais on peut l'aborder beaucoup plus simplement dans le cas discret (un nombre fini de valeurs) comme une simple assignation entre deux ensembles.
** [[https://en.wikipedia.org/wiki/Color_mapping Transfert de couleur Wikipedia]]
** [[https://hal.archives-ouvertes.fr/tel-01246096/file/hdr_hal2.pdf Habilitation de N. Papadakis]] (regardez les images plutôt).

== Génération et résolution de labyrinthes II ==

* Tuteur: François Boussion
* Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
* Objectifs:
*# Comprendre comment représenter un labyrinthe avec une structure de données simple
*# Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
*# Comprendre l'algorithme d'arbre couvrant minimum
*# Comprendre le principe du parcours en profondeur et de la récursivité
* Pour aller plus loin
*# coder la génération d'un labyrinthe et sa visualisation
*# introduire des poids pour varier le labyrinthe
*# comment faire un labyrinthe sur grille hexagonale avec des tableaux.
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe Wikipedia]]
** [[https://en.wikipedia.org/wiki/Maze_generation_algorithm Version anglaise plus complète]]

== REST + Pub/Sub : protocole hybride pour l’IoT ==

* Tuteur: David Télisson
* Résumé: L’avènement de l’Internet des Objets (IoT) depuis une dizaine d’années a fait apparaitre des problématiques propres aux protocoles de communications liées à ces objets. En effet, l’échange de données dans ce contexte nécessite de tenir compte (au moins) des paramètres suivant :
*# Autonomie énergétique souvent limitée
*# Faible puissance des processeurs et taille réduite de la mémoire
*# Disponibilité « aléatoire » de l’accès aux réseaux de communication

De nombreux protocoles cohabitent et la littérature du domaine foisonne d’exemples autour des réseaux dédiées (LORA, Sigfox, etc.) et des protocoles applicatifs (OPC-UA, MQTT, CoaP, XMPP) mais force est de constater que dans la réalité, ces solutions ne répondent pas toujours aux besoins des concepteurs qui leurs préfèrent encore le protocole HTTP. Celui-ci offre l’avantage d’implémenter un protocole applicatif (REST) en même temps qu’un protocole de transport de haut niveau (TCP/IP) permettant de passer les pare-feu. Cependant, la version actuel d’HTTP ne répond pas vraiment aux critères énoncés précédemment.
Depuis quelques années émerge donc l’idée d’enrichir HTTP pour créer un protocole hybride qui mêlerait les avantages de REST avec ceux proposés par les mécanismes de type Publish/Subscribe (MQTT, AMQP, JMS, etc.). En attendant cette éventuelle évolution, peut-on envisager de mettre en place un mécanisme de type Pub/Sub avec le protocole Websocket au-dessus d’HTTP ?

* Objectifs:
*# Etudier et faire une synthèse des deux approches : REST et Pub/Sub
*# Implémentez un PoC (proof of concept) d’une solution hybride qui met en œuvre un mécanisme de Pub/Sub sur Websocket. .
*# Présenter un protocole de test pour valider ou invalider cette solution

* Liens pour démarrer :
** https://nsrc.org/workshops/2018/apricot/iot/presentations/mqttvsrest_v4.pdf
** http://www.tigli.fr/lib/exe/fetch.php?media=cours:tutorial_mqtt_mit_2015_2016.pdf
** https://openclassrooms.com/fr/courses/3449001-utilisez-des-api-rest-dans-vos-projets-web
** http://www.lirmm.fr/~tibermacin/ens/ws/expose.pdf

== La suite de Conway et la classification périodique des "éléments" ==

* Tuteur : Pierre Hyvernat
* La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
** "1" : un "1" -> 11
** "11" : deux "1" -> 21
** "21" : un "2", un "1" -> 1211
** "1211" : un "1", un "2", deux "1" -> 111221
** etc.
Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".
* Objectifs :
*# comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
*# programmer la suite de Conway pour retrouver la classification des "atomes"
*# écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
*# écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

* Liens pour commencer
** [[https://fr.wikipedia.org/wiki/Suite_de_Conway suite de Conway]]
** [[https://fr.wikipedia.org/wiki/Suite_de_Robinson suite de Robinson]]

== [[Initiation à la démonstration sur ordinateur et certification de logiciel]] ==

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

== Algorithmes probabilistes/déterministes pour tester la primalité d'un entier ==

* Tuteur : Sébastien Tavenas
* Pouvoir tester si un entier est un nombre premier semble être une brique de base si l'on souhaite faire de l'arithmétique sur un ordinateur. Le crible d'Érathostène enseigné dans les petites classes se montre beaucoup trop lent en pratique. L'algorithme probabiliste utilisé le plus rapide est le test de Fermat. Or, si on regarde les algorithmes des librairies "génériques", on peut s'apercevoir que la fonction 'mpz_probab_prime_p' de la librairie 'gmp' sur c++ utilise un test probabiliste de Miller-Rabin, la fonction 'isPrime' de la classe 'Prime' dans java utilise aussi un test de Miller-Rabin mais qui est déterminisé, alors que la fonction 'isprime' de la librairie 'sympy' dans python effectue un test de Miller-Rabin si l'entier est plus petit que 2^64 et un test BPSW fort si l'entier est plus grand. Ainsi, une fonction déjà implémentée de test de primalité peut se tromper ou non, être instantanée ou moins. Que dire alors de l'algorithme polynomial déterministe et toujours correct proposé par AKS?
* Objectifs :
*# Comprendre quelques tests de primalité et comment l'aléatoire est utilisé dans ces algorithmes
*# Comprendre la notion de nombre pseudopremier qui explique, entre autre, quand il vaut mieux utiliser le test de Fermat ou celui de Miller-Rabin
*# Programmer quelques uns des ces tests et les comparer
*# Essayer de dérandomiser ces tests à l'aide de hitting-sets précalculés

* Liens pour commencer
** [[https://en.wikipedia.org/wiki/Primality_test Tests de primalité]]

== Dilemme du prisonnier ==

* Tuteur: Gerald Cavallini
* Résumé: Le dilemme du prisonnier caractérise en théorie des jeux une situation où deux joueurs auraient
intérêt à coopérer, mais où, en l’absence de communication entre les deux joueurs, chacun choisira
de trahir l'autre si le jeu n'est joué qu'une fois.

On peut informatiquement modéliser ce dilemme à l’aide de matrices de gains et conserver la
mémoire des choix de l’adversaire. Ce modèle appliqué à un grand nombre d’individus peut être
utilisé pour comprendre l’émergence de stratégies stables dans l’économie, l’écologie, l’évolution
des espèces ...

On peut visualiser spatialement les interactions entre individus en les représentants par des pixels et
en leurs associant une couleur en fonction de leurs stratégies.

[[Fichier:Dilemme.png]]

* Objectifs
*# Comprendre le dilemme du prisonnier
*# Comprendre la notion de stratégie
*# Penser un modèle spatiale pour « opposer » des individus qui appliquent des stratégies différentes
*# Développer une interface pour visualiser dans le temps l’évolution d’une population d’individus adoptants des stratégies différentes.

* Lien :
*# [https://fr.wikipedia.org/wiki/Dilemme_du_prisonnier Dilemme du prisonnier Wikipedia]
*# [http://cormas.cirad.fr/fr/applica/dps.htm Site spécifique]

= Sujets réalisés (2017-2018) =

* [[VISI201 Analyse syntaxique (Tristan Porteries, 2018)]]
* [[Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"]] (Nils Ruet, 2018)
* [[Fouille de données textuelles à partir des "Exercices de style" de R. Queneau]] (Rémi Bouvier, 2018)
* [[Transformées en distance, diagramme de Voronoi et applications en geometry processing]] (Robin Wagner, 2018)
* [[Pavages de Penrose]] (Brunelle Cordier-Pierre-Bès, 2018)

= Sujets proposés (2017-2018) =

* Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"
* Initiation à la démonstration sur ordinateur et certification de logiciel
* Fouille de données textuelles à partir des "Exercices de style" de R. Queneau
* Transformées en distance, diagramme de Voronoi et applications en geometry processing
* Pavages de Penrose

== [[Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: La segmentation d'image vise à identifier les régions d'intérêt dans une image. Typiquement, une région d'intérêt est une zone de l'image plutôt homogène (les pixels ont des valeurs proches) et le contour entre deux régions d'intérêt est tracé là où les valeurs subissent de fortes variations. La méthode de segmentation proposée ici suit ce principe en enchaînant deux calculs: (1) un premier traitement calcule une image "gradient" et fabrique une image dont les valeurs élevées correspondent à des zones de fortes variations, (2) le deuxième algorithme voit cette image comme un relief 3D et identifie ses bassins hydrographiques. Cette identification des lignes de partage des eaux permet de découper l'image en ses zones d'intérêt.
* Objectifs:
*# comprendre ce qu'est une image niveaux de gris ou couleur, ce qu'est le gradient d'une image et ce qu'on appelle segmentation d'image.
*# décrire un algorithme de calcul du gradient d'une image, e.g. le filtre de Sobel, voire les convolutions par dérivées de Gaussienne.
*# décrire le principe de ligne de partage des eaux ("watershed" en anglais), ses différentes définitions équivalentes, et les différents types d'algorithmes pour la calculer.
*# Coder un programme de segmentation d'image, qui prend une image (niveaux de gris) en entrée, calcule son gradient, et extrait les bassins de sa ligne de partage des eaux.
* Liens pour démarrer
** [[https://en.wikipedia.org/wiki/Watershed_(image_processing) Watershed Wikipedia]]
** Luc Vincent and Pierre Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Num. 6 (1991), pages 583–598 [[https://pdfs.semanticscholar.org/a381/9dda9a5f00dbb8cd3413ca7422e37a0d5794.pdf PDF]]

== [[Initiation à la démonstration sur ordinateur et certification de logiciel]] ==

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

== [[Fouille de données textuelles à partir des "Exercices de style" de R. Queneau]] ==

* Tuteur: Laurent Vuillon
* Résumé: L'idée de ce projet est de se familiariser avec les techniques de fouille de données textuelles à partir des "Exercices de style" de R. Queneau (https://fr.wikipedia.org/wiki/Exercices_de_style). On cherchera à comprendre la structure du vocabulaire du corpus de textes, à utiliser les techniques de TF/IDF pour extraire les mots significatifs du corpus puis à tester les techniques de LDA (Allocation de Dirichlet latente) pour extraire automatiquement les thématiques du corpus afin de construire des regroupements par thème. On pourra également proposer des visualisations des résultats afin de rendre accessible visuellement l'analyse de données produite sur le corpus de documents.
* Objectifs: Introduction à la fouille de données au travers d'un cas pratique
* Pour aller plus loin
** http://blogperso.univ-rennes1.fr/stephane.tuffery/
** http://www.editionstechnip.com/en/catalogue-detail/1005/data-mining-et-statistique-decisionnelle.html
* Liens pour démarrer
** https://fr.wikipedia.org/wiki/Exploration_de_donn%C3%A9es
** https://fr.wikipedia.org/wiki/TF-IDF
** "Recherche d'information : applications, modèles et algorithmes; Data mining, décisionnel et big data" de Amini et Gaussier aux éditions Eyrolles.

== [[Transformées en distance, diagramme de Voronoi et applications en geometry processing]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Les nuages de points constituent une source de données géométriques importantes (cf LIDAR scanner, 3D scanner) et qui permet de construire des modèles géométriques 3D d'objets réels. La difficulté est de transformer ces nuages de points en des surfaces (souvent des surfaces triangulées, c'est-à-dire des triangles collés entre eux). Un outil essentiel dans ce processus est la transformée en distance, le diagramme de Voronoi (et son dual la triangulation de Delaunay). A partir de ces outils, des algorithmes existent pour reconstruire les surfaces, estimer la géométrie du nuage de point (sa normale par exemple), etc.
* Objectifs:
*# Comprendre ce qu'est une distance, une transformée en distance, et un diagramme de Voronoi. Comprendre ce qu'est la stabilité d'une fonction.
*# Identifier les propriétés des diagrammes de Voronoi, de leur dual la triangulation de Delaunay, et comprendre leurs variantes comme les diagrammes de puissance
*# Identifier le lien avec l'axe médian et les squelettes
*# Décrire les principaux algorithmes de calcul des transformées en distance et du diagramme de Voronoi, pour des nuages de point quelconques ou pour des nuages de points à coordonnées entières.
*# Présenter un algorithme de reconstruction de surface utilisant le diagramme de Voronoi
*# Coder un algorithme de calcul du diagramme de Voronoi et, si le temps le permet, un algorithme de reconstruction de surface.

* Liens pour démarrer
** [[https://en.wikipedia.org/wiki/Voronoi_diagram Diagramme de Voronoi Wikipedia]]
** [[https://en.wikipedia.org/wiki/Distance_transform Transformée en distance Wikipedia]]
** [[https://en.wikipedia.org/wiki/Topological_skeleton Squelette Wikipedia]]
** [[http://dgtal.org/doc/nightly/moduleVolumetric.html Transformées discrètes en distance DGtal]]

== [[Pavages de Penrose]] ==

* Tuteur : Pierre Hyvernat
* Résumé : le "cerf-volant" et la "fléchette" de Penrose sont deux tuiles qui permettent de recouvrir le plan, mais uniquement de manière non-périodique. Autrement dit, les pavages correspondants ne sont pas obtenus en répétant un même motif de manière régulière. A cause de ceci, il n'est pas évident de générer un tel pavage.

[[Fichier:P2.png]]

* Objectifs
*# comprendre les notion de pavage périodique, non périodique et apériodique,
*# comprendre la méthode "inflation / déflation" pour générer des pavages de Penrose des différents types,
*# comprendre le lien entre les 2 (ou 3) types de pavage de Penrose
*# écrire un programme permettant de générer de tels pavages : avec la méthode "inflation / déflation" et avec la méthode "grille de de Bruijn"
*# utiliser ces méthodes pour générer d'autres types de pavages apériodique.

* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Pavage_de_Penrose pavage de Penrose (wikipedia]]
** [[https://www.maa.org/sites/default/files/pdf/pubs/focus/Gardner_PenroseTilings1-1977.pdf Penrose Tiling (Marting Gardner, en anglais)]]

== [[Algorithmes d'analyse syntaxique]] ==

* Tuteur : Pierre Hyvernat

* Résumé : le code source d'un programme, d'un fichier de configuration d'un serveur de base de données ou le code d'une page web sont des données ''textuelles'' et ''structurées''. Il est possible de définir exactement quelles données sont correctes, et quelle est leur signification. (Cela est beaucoup plus difficile pour des textes en langue naturelle par exemple.) En ce sens, il est possible de lire, d'interpréter ces données à l'aide d'un programme. On parle ''d'analyseur syntaxique'' ou de ''parseur''. Il existe de nombreux outils pour faire ça automatiquement, mais il est parfois important (et toujours intéressant) de comprendre les mécanismes correspondant. C'est ce que ce stage propose de faire.

* Objectifs :
*# étudier la formalisation du problème à travers la notion de ''langage'' et les premiers étages de la hiérachie de Chomsky (langages réguliers et grammaires hors contexte).
*# comprendre le lien entre les langages et les automates (automates finis / automates à pile)
*# implémenter un parseur "from scratch" et le tester sur des petits exemples simples, "à la main", soit en calculant "à la volée" la sémantique d'un langage, soit en produisant des "arbres de syntaxe abstraits", qui pourront être analysés par la suite,
*# comprendre les restrictions souvent imposées sur les grammaires afin d'améliorer l'efficacité du parseur (''LL*(k)'', ''LR'', etc.)
*# à partir de là, de nombreuses pistes sont ouvertes :
*#* essayer d'écrire un petit outils qui puisse lire une grammaire, et générer un parseur pour cette grammaire,
*#* comparer l'approche "automate" avec l'approche "combinateurs" et "parseur récursifs"
*#* améliorer l'efficacité des parseurs produits
*#* ajouter des fonctionnalités,
*#* ...

* Liens pour démarrer :
** [[https://en.wikipedia.org/wiki/Parsing page wikipedia "parsing"]]
** [[https://en.wikipedia.org/wiki/Recursive_descent_parser page wikipedia "recursive descent parser"]]
** Le livre référence sur le parsing est probablement "Compilers: Principles, Techniques, and Tools" de Aho, Sethi et Ullman (le "dragon book")
** [[https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/ exemples de notes cours de compilation]]

= Sujets réalisés (2016-2017) =

* [[Algorithme de rendu de scène 3D par Z-buffer]]
* [[Traitement d'image]]
* [[Nim et la théorie des jeux impartiaux]]
* [[Calculabilité et modèles de calcul]]
* [[Génération et résolution de labyrinthes]]

= Sujets proposés (2016-2017) =

== [[Algorithme de rendu de scène 3D par Z-buffer]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le Z-buffer est un algorithme classique de rendu de scène 3D. C'est celui (avec quelques variantes) qui est implémenté dans nos cartes graphiques 3D et qui permet de visualiser des scènes extrêmement complexes en temps réel (typiquement 24 image/s).
* Objectifs:
*# décrire le principe de la projection 3D vers 2D
*# décrire la rastérisation des triangles sur une image en pixel
*# expliquer le principe du Z-buffer qui permet de gérer le fait que certains objets sont cachés par d'autres
*# expliquer comment les couleurs sont calculées par pixel
*# indiquer les qualités et limitations de l'algorithme
* Pour aller plus loin
*# mettre du code démo (WebGL) avec quelques explications sur le pipeline graphique OpenGL
*# expliquer comment on peut utiliser cet algorithme pour calculer des ombres (shadow map)
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Z-buffer Wikipedia]]
** [[https://www.scratchapixel.com/lessons/3d-basic-rendering/rasterization-practical-implementation/overview-rasterization-algorithm Scratch a pixel]]

== [[Traitement d'image]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le traitement d'image rassemble tous les algorithmes utilisés pour transformer les images, les améliorer, éliminer certaines perturbations, augmenter ou diminuer le contraste, changer les couleurs vers d'autres couleurs, éliminer le flou ou les yeux rouges, faire du cartooning pour un rendu moins photo-réaliste, etc.
* Objectifs:
*# identifier les grandes familles de traitement: restauration, égalisation, élimination du flou de déplacement, segmentation, etc
*# identifier les grandes familles de techniques: filtrage spatial, filtrage fréquentiel, optimisation, etc
*# comprendre les points communs et différences entre le traitement des images noir et blanc et le traitement des images couleurs.
*# choisir un ou deux algorithmes de traitement et les expliquer en détails
* Pour aller plus loin
*# Coder un algorithme de traitement d'image simple (e.g, un filtrage médian, ou un algo qui transporte les couleurs d'une photo vers une autre photo)

* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Traitement_d%27images Wikipedia]]
** [[http://www.ipol.im/ Image Processing on line]] (permet de tester en ligne des algorithmes sur vos images)

== [[Nim et la théorie des jeux impartiaux]] ==

* Tuteur: Pierre Hyvernat

* Étudiant : Luca Chapelle

* Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des premiers jeux ayant été analysé mathématiquement (par Charles Bouton en 1901). Les stratégies gagnantes peuvent être calculées en utilisant le développement en base 2 des nombres, et l'opération d'"addition de Nim" (XOR). La théorie de ce type de jeux (jeux "impartiaux") est assez simple, mais de nombreuses instances de jeux sont encore non résolues.
* Objectifs:
*# comprendre la théorie du jeu de Nim (et la programmer)
*# comprendre le théorème de Sprague Grundy qui montre que tout jeu impartial est équivalent à un jeu de nim
*# regarder quelques autres exemples de tels jeux : jeu de Nim déguisés, ou jeux véritablement différents
*# programmer une version naịve de recherche de stratégie basée sur le théorème de Sprague-Grundy pour quelques jeux

* Liens pour commencer
** [https://fr.wikipedia.org/wiki/Jeux_de_Nim jeu de Nim]
** [https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Sprague-Grundy théorème de Sprague Grundy]
** [https://fr.wikipedia.org/wiki/Jeu_de_Grundy jeu de Grundy]

== La suite de Conway et la classification périodique des "éléments" ==

* Tuteur : Pierre Hyvernat
* La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
** "1" : un "1" -> 11
** "11" : deux "1" -> 21
** "21" : un "2", un "1" -> 1211
** "1211" : un "1", un "2", deux "1" -> 111221
** etc.
Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".
* Objectifs :
*# comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
*# programmer la suite de Conway pour retrouver la classification des "atomes"
*# écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
*# écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

* Liens pour commencer
** [[https://fr.wikipedia.org/wiki/Suite_de_Conway suite de Conway]]
** [[https://fr.wikipedia.org/wiki/Suite_de_Robinson suite de Robinson]]

== Initiation à la démonstration sur ordinateur et certification de logiciel ==

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

== [[Calculabilité et modèles de calcul]] ==

* Tuteur: Rodolphe Lepigre
* Résumé: Une fonction f sur l'ensemble des entiers naturels est dite calculable s'il existe une procedure effective (ou un algorithme) qui permet, étant donné un entier n, de calculer f(n) en temps fini. Il existe divers modèles de calcul qui permettent de représenter toutes les fonctions calculables : machines de Turing, λ-calcul, automates cellulaires, ...
* Objectifs:
*# comprendre la notion de fonction calculable,
*# comparer l'ensemble des fonctions à l'ensemble des fonctions calculables,
*# regarder et comparer quelque modèles de calcul,
*# programmer un modèle de calcul et comprendre les limitations pratiques.

* Liens pour commencer:
** https://fr.wikipedia.org/wiki/Calculabilité
** https://fr.wikipedia.org/wiki/Machine_de_Turing
** https://fr.wikipedia.org/wiki/Lambda-calcul
** https://fr.wikipedia.org/wiki/Jeu_de_la_vie

== [[Génération et résolution de labyrinthes]] ==

* Tuteur: <strike>Jacques-Olivier Lachaud</strike> Xavier Provençal
* Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
* Objectifs:
*# Comprendre comment représenter avec une structure de données un labyrinthe
*# Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
*# Comprendre l'algorithme d'arbre couvrant minimum
*# Comprendre le principe du parcours en profondeur et de la récursivité
* Pour aller plus loin
*# coder la génération d'un labyrinthe et sa visualisation
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe Wikipedia]]
** [[https://en.wikipedia.org/wiki/Maze_generation_algorithm Version anglaise plus complète]]

== Pavages par polyomino ==

* Tuteur: Xavier Provençal
* Résumé : On s'intéresse aux pavages du plan par des tuiles formées de petits carrés collés les uns aux autres, appelé "polyominos". Étant donné une tuile, peut-on paver le plan ? Si oui, avec quelles opérations (translation et/ou rotations et/ou réflexions) Une fois un pavage réalisé, on observe ses propriétés. Quelles symétries ? Le pavage est-il identique du point de vue de chacune des tuiles ? Si ce n'est pas le cas, en combien de classes peut-on diviser ces tuiles ?
On s'intéressera aussi à des propriétés connexes. Au lieu de paver tout le plan, on peut essayer de paver une région finie donnée. Plus localement, peut-on encercler complètement une tuile avec des copies d'elle-même, sans former de trous ? Si oui, peut-on faire de même avec la proto-tuile formée par la tuile de départ et toutes ses copies ? Si oui, combien de fois peut-on répéter l'opération ?
* Objectifs :
*# Comprendre les différentes classes de pavages (isohédral, k-isohédral, anisohédral).
*# Pour chacun des sept types de pavages "isohédraux", comprendre le lien entre les symétries du pavages et la caractérisation des tuiles qui le réalisent.
*# Pour un pavage k-isohédral, identifier les "classes d'équivalences" et le "domaine fondamental".
* Pour aller plus loin :
*# Coder la génération de tuiles capables de paver le plan en fonction pour une classe de pavages donnée.
*# Étudier et implémenter certains algorithmes pour le pavages d'un domaine fini.
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Polyomino Polyomino]]
** [[https://en.wikipedia.org/wiki/Polyomino Polyomino (en)]]
** [[https://fr.wikipedia.org/wiki/Pavage_par_des_polygones_r%C3%A9guliers Pavages]]

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

2020-05-16T19:16:47Z

Rpajean :

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

2020-05-16T19:00:16Z

Rpajean : Page créée avec « 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 de... »

Fichier:Exemple requete ascii.png

2020-05-16T18:52:45Z

Rpajean :

VISI201 CMI : visite de laboratoire

2020-05-12T19:27:37Z

Rpajean : /* Sujets réalisés (2019-2020) */

* Cours du semestre 2 du parcours CMI Informatique (licence INFO).

* Responsable pour 2019--2020: Jacques-Olivier Lachaud
* Responsable pour 2018--2019: Jacques-Olivier Lachaud
* Responsable pour 2017--2018: Jacques-Olivier Lachaud
* Responsable pour 2016--2017: Jacques-Olivier Lachaud

= Descriptif =

L'objectif du module est de faire découvrir les laboratoires, le monde de la recherche et les enseignants-chercheurs et chercheurs, ainsi que la réflexion scientifique. Cela se fait de deux manières.

D'abord, une partie de ce module consiste à assister à des séminaires dédiés aux étudiants CMI Informatique et Mathématique (1 fois par mois, les jeudi après-midi). [[http://www.lama.univ-savoie.fr/index.php?use=seminaires&&lang=fr&equipe=cmi&annee=1&lang=fr Planning des séminaires CMI]]

Ces séminaires "grand public" portent sur des sujets variées en informatique et mathématiques.

Les étudiants choisissent ensuite d'approfondir un sujet proposé par les enseignants, ou un sujet motivé de leur choix (en accord avec le responsable du module). Ce travail se fait en interaction avec un tuteur académique (5-6 contacts au moins). Ce travail personnel tuteuré donne lieu à la rédaction d'une synthèse sur le sujet sous forme d'une page wiki/web, ainsi que d'un mini-exposé.

= Sujets réalisés (2019-2020) =

* Compression et transformée de Burrow-Wheeler, Simon Léonard (Tuteur : Pierre Hyvernat)
* Backtracking, Simon Pichenot (Tuteur : Pierre Hyvernat)
* Transfert de couleur (version 2), Florian Dufaure (Tuteur : Jacques-Olivier Lachaud)
* [[Génération fractale de terrains]], Hugo Rey (Tuteur : Jacques-Olivier Lachaud)
* Architectures Orientées Micro-Services, Romain Negro (David Télisson)
* Apprentissage automatique, Evan L'Huissier (Tuteur : Tom Hirschowitz)
* Algorithmes probabilistes/déterministes pour tester la primalité d'un entier, Juliette Neyrat (Tuteur : Sébastien Tavenas)
* [[Base de données orientées Graphe, similarité et modèles prédictifs]], Romain Pajean (Gérald Cavallini)
* Modèles d'évolution de populations, Théo Guesdon (Tuteur : Jimmy Garnier)

= Sujets proposés (2019-2020) =

* Compression et transformée de Burrow-Wheeler
* Backtracking
* Transfert de couleur (version 2)
* Génération fractale de terrains
* Architectures Orientées Micro-Services
* Apprentissage automatique
* Algorithmes probabilistes/déterministes pour tester la primalité d'un entier
* Base de données orientées Graphe, similarité et modèles prédictifs

== Compression et transformée de Burrow-Wheeler ==

* Tuteur : Pierre Hyvernat
* Résumé : La transformée de Burrow-Wheeler est l'étape clé de l'algorithme de compression bzip2. C'est une transformation de texte (suite d'octet) qui ne modifie pas la taille, mais ajoute suffisamment de motifs redondants pour améliorer un autre algorithme de compression (algorithme de Huffman dans le cas de bzip2)
* Objectif : L'objectif est de comprendre le fonctionnement de cette transformation (et de son inverse) et d'implémenter une version naïve de l'algorithme de compression / décompression et de tester sur quelques exemples. Les améliorations de l'algorithme seront ensuite abordées.
* Liens : Burrows, Michael; Wheeler, David J. (1994), A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation [[https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf PDF]]

== Backtracking ==

* Tuteur : Pierre Hyvernat
* Résumé et objectif : La notion de "backtracking" est fondamentale en algorithmique : il s'agit essentiellement de tester des solutions partielles à un problème, en revenant en arrière dès qu'une incohérence est découverte. Le point de départ sera le fascicule 4.5b de D. Knuth "Introduction to backtracking" et permettra de se familiariser avec les concepts, la terminology et des exemples, qu'il faudra implémenter. Une suite possible sera la notion de réduction de problèmes et l'algorithme-X qui permet de "factoriser" de nombreux problèmes de backtracking en un seul algorithme.
* Liens : D. Knuth, "the art of computer programming introduction to backtracking" [[https://www-cs-faculty.stanford.edu/~knuth/fasc5b.ps.gz PS]]

== Transfert de couleur (version 2) ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le transfert de couleurs de l'image Y vers l'image X consiste à repeindre "au mieux" l'image X avec la palette de couleurs de l'image Y. L'image repeinte X' a alors les mêmes couleurs que l'image Y (mais les pixels ne sont pas répartis pareils). Voir l'exemple de transfert ci-dessous. Il existe plusieurs techniques de transfert de couleurs, mais nous étudierons une technique basée sur le transport optimal. Comme c'est un problème assez difficile dans le cas général, nous étudierons une variante dite par coupe 1D, qui simplifiera considérablement le problème de transport.
{| class="wikitable alternance center"
|+ Transfert de couleur
|----
! scope="col" | Input !! scope="col" | Output
|----
| [[Fichier:horseshoe.jpg|200px]] || [[Fichier:horseshoe-fjord-n40.jpg|200px]]
|----
| [[Fichier:fjord.jpg|200px]] || [[Fichier:fjord-horseshoe-n40.jpg|200px]]
|}
* Objectifs:
*# Comprendre la version 1 fait par [[https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images Lucas Chardonnet]], comprendre les qualités et limites de l'approche (sur quelle type d'image ça marche assez bien par exemple)
*# Adapter l'algorithme pour qu'il puisse traiter des images de tailles différentes
*# Réécrire le code en utilisant la bibliothèque python NUMPY pour accélérer les calculs
*# Changer les espaces de couleurs utilisés: RGB ne convient pas très bien pour mesurer le coût du transport. Transformer le code pour qu'il puisse utiliser plutôt l'espace [[https://fr.wikipedia.org/wiki/L*a*b*_CIE_1976 L*a*b*]] mieux adapté pour calculer des distances entre couleurs.
* Liens:
** la page de [[https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images Lucas Chardonnet]]
** [[https://en.wikipedia.org/wiki/Color_mapping Transfert de couleur Wikipedia]]
** [[https://hal.archives-ouvertes.fr/tel-01246096/file/hdr_hal2.pdf Habilitation de N. Papadakis]] (regardez les images plutôt).

== Génération fractale de terrains ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: La génération procédurale de terrain est très utilisée en modélisation 3D et dans les jeux vidéos, afin de générer rapidement des paysages pseudo-réalistes que l'on étoffera ensuite de façon plus manuelle. On propose d'étudier et d'implémenter un algorithme classique, dit "algorithme Diamant-Carré". Cet algorithme récursif permet de générer une carte d'élévation. Selon les paramètres données, le résultat peut ressembler aux cartes d'altitude de haute montagne ou des collines plus douces.
{| class="wikitable alternance center"
|+ Génération fractale de terrain par algorithme diamand carré
|----
! scope="col" | Elévations générées !! scope="col" | Colorisation !! scope="col" | Visualisation 3D
|----
| [[Fichier:Diamond-Square_texture.png|200px]] || [[Fichier:Diamond-Square_heightmap.png|200px]] || [[Fichier:Terragen.jpg|200px]]
|}

* Objectifs:
*# Comprendre et implémenter l'algorithme Diamant-Carré
*# Comprendre comment paramétrer cet algorithme pour qu'il génère des montagnes bien abrupte à haute altitude ou des collines à basse altitude.
*# Fabriquer une image de couleur/texture qui va associer des couleurs aux altitudes générées (e.g. forcer du bleu sous l'altitude zero, ajouter de la neige, des lacs, de la forêt)
*# Générer un fichier 3D (par exemple OBJ) à partir de ces deux images (l'image des hauteurs et l'image des couleurs) pour pouvoir faire de beau rendu 3D (sous blender par exemple)
* Liens:
** La page [[https://fr.wikipedia.org/wiki/Algorithme_Diamant-Carr%C3%A9 Wikipedia]] de l'algorithme
** La page [[https://en.wikipedia.org/wiki/Wavefront_.obj_file Wikipedia]] du format OBJ

== Architectures Orientées Micro-Services ==

* Tuteur : David Télisson
* Résumé : Les architectures des applications logicielles distribuées de grandes envergures ont évolué à partir du début des années 2000, d’une application molithique déployée sur un serveur d’application (JEE, TomCat, etc.) vers des solutions fortement répartis déployées sous formes de services. On parle alors d’architectures orientées services qui se traduisent par le développement et le déploiement de services logiciels interrogeables via des protocoles dédiés (par exemple SOAP) et des API (REST). Cette tendance, corrélée aux nouvelles méthodes de management des projets informatiques (méthodes agiles, intégration continue, DevOps1), s’est accentué ces dernières années et a fait émergé un « nouveau » paradigme : le micro-service. Plusieurs aspects caractérisent un micro-service :
** fonctionnalité unique
** flexibilité technologie
** équipe de développement réduite
** déploiement ciblé
** support de la montée en charge (scalabilité)
** tests facilités et intégrés au processus de développement (TDD2)
* Objectifs du projet :
*# Etudier et comprendre les concepts liés aux micro-services (API, conteneurisation, framework, etc.)
*# Implémentez un PoC (proof of concept) qui démontre qu’une application peut se construire dynamiquement par agrégation de micro-services développés avec des langages différents (Python, JS et Java), déployés sur des plateformes différentes (Django, Node et Glassfish) et disponibles sous formes de conteneurs dans le cloud (Azure)
*# Livrable attendu : un tutoriel « à la OpenClassRooms »
* Liens pour démarrer :
** https://mbaron.developpez.com/cours/microservices/introduction-generalites
** https://openclassrooms.com/fr/courses/4668056-construisez-des-microservices

== Apprentissage automatique ==

* Tuteur : Tom Hirschowitz
* Résumé : L'apprentissage automatique est un ensemble de techniques algorithmiques visant à écrire des programmes qui améliorent leurs performances au cours du temps. Le sujet consiste en une initiation à cette idée par l'exemple, à base de ressources telles que https://colah.github.io/posts/2015-08-Backprop et http://neuralnetworksanddeeplearning.com .

== Algorithmes probabilistes/déterministes pour tester la primalité d'un entier ==

* Tuteur : Sébastien Tavenas
* Pouvoir tester si un entier est un nombre premier semble être une brique de base si l'on souhaite faire de l'arithmétique sur un ordinateur. Le crible d'Érathostène enseigné dans les petites classes se montre beaucoup trop lent en pratique. L'algorithme probabiliste utilisé le plus rapide est le test de Fermat. Or, si on regarde les algorithmes des librairies "génériques", on peut s'apercevoir que la fonction 'mpz_probab_prime_p' de la librairie 'gmp' sur c++ utilise un test probabiliste de Miller-Rabin, la fonction 'isPrime' de la classe 'Prime' dans java utilise aussi un test de Miller-Rabin mais qui est déterminisé, alors que la fonction 'isprime' de la librairie 'sympy' dans python effectue un test de Miller-Rabin si l'entier est plus petit que 2^64 et un test BPSW fort si l'entier est plus grand. Ainsi, une fonction déjà implémentée de test de primalité peut se tromper ou non, être instantanée ou moins. Que dire alors de l'algorithme polynomial déterministe et toujours correct proposé par AKS?
* Objectifs :
*# Comprendre quelques tests de primalité et comment l'aléatoire est utilisé dans ces algorithmes
*# Comprendre la notion de nombre pseudopremier qui explique, entre autre, quand il vaut mieux utiliser le test de Fermat ou celui de Miller-Rabin
*# Programmer quelques uns des ces tests et les comparer
*# Essayer de dérandomiser ces tests à l'aide de hitting-sets précalculés

* Liens pour commencer
** [[https://en.wikipedia.org/wiki/Primality_test Tests de primalité]]

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

* Tuteur : Gérald Cavallini
* Résumé : Avec l’avènement du BigDatas, dans bien des cas le choix d’un produit, d’un média, d’un voyage ... ne peut plus être direct. Il s’appuie sur des systèmes de recommandations. L’importance financière de ces systèmes est énorme Amazon estime à 30% les ventes supplémentaires dues à son système de recommandation. Ces systèmes s’appuient sur des calculs statistiques et des algorithmes de recherche de similarité. Ces algorithmes expriment la distance entre des objets, ce qui permet par exemple d’identifier des utilisateurs(consommateurs, électeur ...) similaire et de recommander leurs choix.
* Objectifs :
*# Mettre en œuvre différents algorithmes de recherche de similarité ( similarité de Jaquard, similarité cosinus...) dans une base de donnée orientées Graphe Neo4j.
*# Proposer un système de recommandation de film à partir de la base MovieLens (Notation de films par des utilisateurs).
*# Proposer un une validation du modèle prédictif.
* Liens pour commencer
** https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard
** https://www.machinelearningplus.com/nlp/cosine-similarity/
** https://neo4j.com/
** https://movielens.org/

[[Fichier:Neo4j.jpg|400px]]

= Sujets réalisés (2018-2019) =

* [[Transport optimal par coupe 1D et transfert de couleurs entre images]] (Lucas CHARDONNET)
* [[Génération et résolution de labyrinthes II]] (Romain THEODET)
* [[Rest & Pub-Sub : protocole hybride pour l'IoT]] (Ewan RAKOTOANOSY)
* [[La suite de Conway et la classification périodique des "éléments"]] (Yohann THEPAUT)
* [[Initiation à la démonstration sur ordinateur et certification de logiciel]] (Loïc DORNET)
* [[Dilemme du prisonnier]] (Christophe CARMAGNAC)

= Sujets proposés (2018-2019) =

* Transport optimal par coupe 1D et transfert de couleurs entre images
* Génération et résolution de labyrinthes II
* REST + Pub/Sub : protocole hybride pour l’IoT
* La suite de Conway et la classification périodique des "éléments"
* Initiation à la démonstration sur ordinateur et certification de logiciel
* Algorithmes probabilistes/déterministes pour tester la primalité d'un entier
* Dilemme du prisonnier

== Transport optimal par coupe 1D et transfert de couleurs entre images ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le transfert de couleurs de l'image Y vers l'image X consiste à repeindre "au mieux" l'image X avec la palette de couleurs de l'image Y. L'image repeinte X' a alors les mêmes couleurs que l'image Y (mais les pixels ne sont pas répartis pareils). Voir l'exemple de transfert ci-dessous. Il existe plusieurs techniques de transfert de couleurs, mais nous étudierons une technique basée sur le transport optimal. Comme c'est un problème assez difficile dans le cas général, nous verrons une variante dite par coupe 1D, qui simplifiera considérablement le problème de transport.

[[Fichier:Ex-transfert-couleur-OT.png]]

* Objectifs:
*# comprendre ce qu'est une image niveaux couleur, et ce qu'on appelle le transfert de couleurs.
*# comprendre le principe du transport optimal (discret).
*# comprendre et décrire le principe du transport optimal par coupe 1D, et comment se fait le calcul du meilleur transport dans ce cas.
*# Coder un programme de transfert de couleur, qui prend deux images couleurs et réalise le transfert de couleurs.
*# On pourra ensuite réfléchir à quelques améliorations simples (espace couleur YUV, grouper les pixels).
* Liens pour démarrer
** Le vrai "Transport Optimal" est vite très mathématique (ce sont des mesures qui sont transportées), mais on peut l'aborder beaucoup plus simplement dans le cas discret (un nombre fini de valeurs) comme une simple assignation entre deux ensembles.
** [[https://en.wikipedia.org/wiki/Color_mapping Transfert de couleur Wikipedia]]
** [[https://hal.archives-ouvertes.fr/tel-01246096/file/hdr_hal2.pdf Habilitation de N. Papadakis]] (regardez les images plutôt).

== Génération et résolution de labyrinthes II ==

* Tuteur: François Boussion
* Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
* Objectifs:
*# Comprendre comment représenter un labyrinthe avec une structure de données simple
*# Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
*# Comprendre l'algorithme d'arbre couvrant minimum
*# Comprendre le principe du parcours en profondeur et de la récursivité
* Pour aller plus loin
*# coder la génération d'un labyrinthe et sa visualisation
*# introduire des poids pour varier le labyrinthe
*# comment faire un labyrinthe sur grille hexagonale avec des tableaux.
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe Wikipedia]]
** [[https://en.wikipedia.org/wiki/Maze_generation_algorithm Version anglaise plus complète]]

== REST + Pub/Sub : protocole hybride pour l’IoT ==

* Tuteur: David Télisson
* Résumé: L’avènement de l’Internet des Objets (IoT) depuis une dizaine d’années a fait apparaitre des problématiques propres aux protocoles de communications liées à ces objets. En effet, l’échange de données dans ce contexte nécessite de tenir compte (au moins) des paramètres suivant :
*# Autonomie énergétique souvent limitée
*# Faible puissance des processeurs et taille réduite de la mémoire
*# Disponibilité « aléatoire » de l’accès aux réseaux de communication

De nombreux protocoles cohabitent et la littérature du domaine foisonne d’exemples autour des réseaux dédiées (LORA, Sigfox, etc.) et des protocoles applicatifs (OPC-UA, MQTT, CoaP, XMPP) mais force est de constater que dans la réalité, ces solutions ne répondent pas toujours aux besoins des concepteurs qui leurs préfèrent encore le protocole HTTP. Celui-ci offre l’avantage d’implémenter un protocole applicatif (REST) en même temps qu’un protocole de transport de haut niveau (TCP/IP) permettant de passer les pare-feu. Cependant, la version actuel d’HTTP ne répond pas vraiment aux critères énoncés précédemment.
Depuis quelques années émerge donc l’idée d’enrichir HTTP pour créer un protocole hybride qui mêlerait les avantages de REST avec ceux proposés par les mécanismes de type Publish/Subscribe (MQTT, AMQP, JMS, etc.). En attendant cette éventuelle évolution, peut-on envisager de mettre en place un mécanisme de type Pub/Sub avec le protocole Websocket au-dessus d’HTTP ?

* Objectifs:
*# Etudier et faire une synthèse des deux approches : REST et Pub/Sub
*# Implémentez un PoC (proof of concept) d’une solution hybride qui met en œuvre un mécanisme de Pub/Sub sur Websocket. .
*# Présenter un protocole de test pour valider ou invalider cette solution

* Liens pour démarrer :
** https://nsrc.org/workshops/2018/apricot/iot/presentations/mqttvsrest_v4.pdf
** http://www.tigli.fr/lib/exe/fetch.php?media=cours:tutorial_mqtt_mit_2015_2016.pdf
** https://openclassrooms.com/fr/courses/3449001-utilisez-des-api-rest-dans-vos-projets-web
** http://www.lirmm.fr/~tibermacin/ens/ws/expose.pdf

== La suite de Conway et la classification périodique des "éléments" ==

* Tuteur : Pierre Hyvernat
* La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
** "1" : un "1" -> 11
** "11" : deux "1" -> 21
** "21" : un "2", un "1" -> 1211
** "1211" : un "1", un "2", deux "1" -> 111221
** etc.
Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".
* Objectifs :
*# comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
*# programmer la suite de Conway pour retrouver la classification des "atomes"
*# écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
*# écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

* Liens pour commencer
** [[https://fr.wikipedia.org/wiki/Suite_de_Conway suite de Conway]]
** [[https://fr.wikipedia.org/wiki/Suite_de_Robinson suite de Robinson]]

== [[Initiation à la démonstration sur ordinateur et certification de logiciel]] ==

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

== Algorithmes probabilistes/déterministes pour tester la primalité d'un entier ==

* Tuteur : Sébastien Tavenas
* Pouvoir tester si un entier est un nombre premier semble être une brique de base si l'on souhaite faire de l'arithmétique sur un ordinateur. Le crible d'Érathostène enseigné dans les petites classes se montre beaucoup trop lent en pratique. L'algorithme probabiliste utilisé le plus rapide est le test de Fermat. Or, si on regarde les algorithmes des librairies "génériques", on peut s'apercevoir que la fonction 'mpz_probab_prime_p' de la librairie 'gmp' sur c++ utilise un test probabiliste de Miller-Rabin, la fonction 'isPrime' de la classe 'Prime' dans java utilise aussi un test de Miller-Rabin mais qui est déterminisé, alors que la fonction 'isprime' de la librairie 'sympy' dans python effectue un test de Miller-Rabin si l'entier est plus petit que 2^64 et un test BPSW fort si l'entier est plus grand. Ainsi, une fonction déjà implémentée de test de primalité peut se tromper ou non, être instantanée ou moins. Que dire alors de l'algorithme polynomial déterministe et toujours correct proposé par AKS?
* Objectifs :
*# Comprendre quelques tests de primalité et comment l'aléatoire est utilisé dans ces algorithmes
*# Comprendre la notion de nombre pseudopremier qui explique, entre autre, quand il vaut mieux utiliser le test de Fermat ou celui de Miller-Rabin
*# Programmer quelques uns des ces tests et les comparer
*# Essayer de dérandomiser ces tests à l'aide de hitting-sets précalculés

* Liens pour commencer
** [[https://en.wikipedia.org/wiki/Primality_test Tests de primalité]]

== Dilemme du prisonnier ==

* Tuteur: Gerald Cavallini
* Résumé: Le dilemme du prisonnier caractérise en théorie des jeux une situation où deux joueurs auraient
intérêt à coopérer, mais où, en l’absence de communication entre les deux joueurs, chacun choisira
de trahir l'autre si le jeu n'est joué qu'une fois.

On peut informatiquement modéliser ce dilemme à l’aide de matrices de gains et conserver la
mémoire des choix de l’adversaire. Ce modèle appliqué à un grand nombre d’individus peut être
utilisé pour comprendre l’émergence de stratégies stables dans l’économie, l’écologie, l’évolution
des espèces ...

On peut visualiser spatialement les interactions entre individus en les représentants par des pixels et
en leurs associant une couleur en fonction de leurs stratégies.

[[Fichier:Dilemme.png]]

* Objectifs
*# Comprendre le dilemme du prisonnier
*# Comprendre la notion de stratégie
*# Penser un modèle spatiale pour « opposer » des individus qui appliquent des stratégies différentes
*# Développer une interface pour visualiser dans le temps l’évolution d’une population d’individus adoptants des stratégies différentes.

* Lien :
*# [https://fr.wikipedia.org/wiki/Dilemme_du_prisonnier Dilemme du prisonnier Wikipedia]
*# [http://cormas.cirad.fr/fr/applica/dps.htm Site spécifique]

= Sujets réalisés (2017-2018) =

* [[VISI201 Analyse syntaxique (Tristan Porteries, 2018)]]
* [[Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"]] (Nils Ruet, 2018)
* [[Fouille de données textuelles à partir des "Exercices de style" de R. Queneau]] (Rémi Bouvier, 2018)
* [[Transformées en distance, diagramme de Voronoi et applications en geometry processing]] (Robin Wagner, 2018)
* [[Pavages de Penrose]] (Brunelle Cordier-Pierre-Bès, 2018)

= Sujets proposés (2017-2018) =

* Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"
* Initiation à la démonstration sur ordinateur et certification de logiciel
* Fouille de données textuelles à partir des "Exercices de style" de R. Queneau
* Transformées en distance, diagramme de Voronoi et applications en geometry processing
* Pavages de Penrose

== [[Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: La segmentation d'image vise à identifier les régions d'intérêt dans une image. Typiquement, une région d'intérêt est une zone de l'image plutôt homogène (les pixels ont des valeurs proches) et le contour entre deux régions d'intérêt est tracé là où les valeurs subissent de fortes variations. La méthode de segmentation proposée ici suit ce principe en enchaînant deux calculs: (1) un premier traitement calcule une image "gradient" et fabrique une image dont les valeurs élevées correspondent à des zones de fortes variations, (2) le deuxième algorithme voit cette image comme un relief 3D et identifie ses bassins hydrographiques. Cette identification des lignes de partage des eaux permet de découper l'image en ses zones d'intérêt.
* Objectifs:
*# comprendre ce qu'est une image niveaux de gris ou couleur, ce qu'est le gradient d'une image et ce qu'on appelle segmentation d'image.
*# décrire un algorithme de calcul du gradient d'une image, e.g. le filtre de Sobel, voire les convolutions par dérivées de Gaussienne.
*# décrire le principe de ligne de partage des eaux ("watershed" en anglais), ses différentes définitions équivalentes, et les différents types d'algorithmes pour la calculer.
*# Coder un programme de segmentation d'image, qui prend une image (niveaux de gris) en entrée, calcule son gradient, et extrait les bassins de sa ligne de partage des eaux.
* Liens pour démarrer
** [[https://en.wikipedia.org/wiki/Watershed_(image_processing) Watershed Wikipedia]]
** Luc Vincent and Pierre Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Num. 6 (1991), pages 583–598 [[https://pdfs.semanticscholar.org/a381/9dda9a5f00dbb8cd3413ca7422e37a0d5794.pdf PDF]]

== [[Initiation à la démonstration sur ordinateur et certification de logiciel]] ==

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

== [[Fouille de données textuelles à partir des "Exercices de style" de R. Queneau]] ==

* Tuteur: Laurent Vuillon
* Résumé: L'idée de ce projet est de se familiariser avec les techniques de fouille de données textuelles à partir des "Exercices de style" de R. Queneau (https://fr.wikipedia.org/wiki/Exercices_de_style). On cherchera à comprendre la structure du vocabulaire du corpus de textes, à utiliser les techniques de TF/IDF pour extraire les mots significatifs du corpus puis à tester les techniques de LDA (Allocation de Dirichlet latente) pour extraire automatiquement les thématiques du corpus afin de construire des regroupements par thème. On pourra également proposer des visualisations des résultats afin de rendre accessible visuellement l'analyse de données produite sur le corpus de documents.
* Objectifs: Introduction à la fouille de données au travers d'un cas pratique
* Pour aller plus loin
** http://blogperso.univ-rennes1.fr/stephane.tuffery/
** http://www.editionstechnip.com/en/catalogue-detail/1005/data-mining-et-statistique-decisionnelle.html
* Liens pour démarrer
** https://fr.wikipedia.org/wiki/Exploration_de_donn%C3%A9es
** https://fr.wikipedia.org/wiki/TF-IDF
** "Recherche d'information : applications, modèles et algorithmes; Data mining, décisionnel et big data" de Amini et Gaussier aux éditions Eyrolles.

== [[Transformées en distance, diagramme de Voronoi et applications en geometry processing]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Les nuages de points constituent une source de données géométriques importantes (cf LIDAR scanner, 3D scanner) et qui permet de construire des modèles géométriques 3D d'objets réels. La difficulté est de transformer ces nuages de points en des surfaces (souvent des surfaces triangulées, c'est-à-dire des triangles collés entre eux). Un outil essentiel dans ce processus est la transformée en distance, le diagramme de Voronoi (et son dual la triangulation de Delaunay). A partir de ces outils, des algorithmes existent pour reconstruire les surfaces, estimer la géométrie du nuage de point (sa normale par exemple), etc.
* Objectifs:
*# Comprendre ce qu'est une distance, une transformée en distance, et un diagramme de Voronoi. Comprendre ce qu'est la stabilité d'une fonction.
*# Identifier les propriétés des diagrammes de Voronoi, de leur dual la triangulation de Delaunay, et comprendre leurs variantes comme les diagrammes de puissance
*# Identifier le lien avec l'axe médian et les squelettes
*# Décrire les principaux algorithmes de calcul des transformées en distance et du diagramme de Voronoi, pour des nuages de point quelconques ou pour des nuages de points à coordonnées entières.
*# Présenter un algorithme de reconstruction de surface utilisant le diagramme de Voronoi
*# Coder un algorithme de calcul du diagramme de Voronoi et, si le temps le permet, un algorithme de reconstruction de surface.

* Liens pour démarrer
** [[https://en.wikipedia.org/wiki/Voronoi_diagram Diagramme de Voronoi Wikipedia]]
** [[https://en.wikipedia.org/wiki/Distance_transform Transformée en distance Wikipedia]]
** [[https://en.wikipedia.org/wiki/Topological_skeleton Squelette Wikipedia]]
** [[http://dgtal.org/doc/nightly/moduleVolumetric.html Transformées discrètes en distance DGtal]]

== [[Pavages de Penrose]] ==

* Tuteur : Pierre Hyvernat
* Résumé : le "cerf-volant" et la "fléchette" de Penrose sont deux tuiles qui permettent de recouvrir le plan, mais uniquement de manière non-périodique. Autrement dit, les pavages correspondants ne sont pas obtenus en répétant un même motif de manière régulière. A cause de ceci, il n'est pas évident de générer un tel pavage.

[[Fichier:P2.png]]

* Objectifs
*# comprendre les notion de pavage périodique, non périodique et apériodique,
*# comprendre la méthode "inflation / déflation" pour générer des pavages de Penrose des différents types,
*# comprendre le lien entre les 2 (ou 3) types de pavage de Penrose
*# écrire un programme permettant de générer de tels pavages : avec la méthode "inflation / déflation" et avec la méthode "grille de de Bruijn"
*# utiliser ces méthodes pour générer d'autres types de pavages apériodique.

* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Pavage_de_Penrose pavage de Penrose (wikipedia]]
** [[https://www.maa.org/sites/default/files/pdf/pubs/focus/Gardner_PenroseTilings1-1977.pdf Penrose Tiling (Marting Gardner, en anglais)]]

== [[Algorithmes d'analyse syntaxique]] ==

* Tuteur : Pierre Hyvernat

* Résumé : le code source d'un programme, d'un fichier de configuration d'un serveur de base de données ou le code d'une page web sont des données ''textuelles'' et ''structurées''. Il est possible de définir exactement quelles données sont correctes, et quelle est leur signification. (Cela est beaucoup plus difficile pour des textes en langue naturelle par exemple.) En ce sens, il est possible de lire, d'interpréter ces données à l'aide d'un programme. On parle ''d'analyseur syntaxique'' ou de ''parseur''. Il existe de nombreux outils pour faire ça automatiquement, mais il est parfois important (et toujours intéressant) de comprendre les mécanismes correspondant. C'est ce que ce stage propose de faire.

* Objectifs :
*# étudier la formalisation du problème à travers la notion de ''langage'' et les premiers étages de la hiérachie de Chomsky (langages réguliers et grammaires hors contexte).
*# comprendre le lien entre les langages et les automates (automates finis / automates à pile)
*# implémenter un parseur "from scratch" et le tester sur des petits exemples simples, "à la main", soit en calculant "à la volée" la sémantique d'un langage, soit en produisant des "arbres de syntaxe abstraits", qui pourront être analysés par la suite,
*# comprendre les restrictions souvent imposées sur les grammaires afin d'améliorer l'efficacité du parseur (''LL*(k)'', ''LR'', etc.)
*# à partir de là, de nombreuses pistes sont ouvertes :
*#* essayer d'écrire un petit outils qui puisse lire une grammaire, et générer un parseur pour cette grammaire,
*#* comparer l'approche "automate" avec l'approche "combinateurs" et "parseur récursifs"
*#* améliorer l'efficacité des parseurs produits
*#* ajouter des fonctionnalités,
*#* ...

* Liens pour démarrer :
** [[https://en.wikipedia.org/wiki/Parsing page wikipedia "parsing"]]
** [[https://en.wikipedia.org/wiki/Recursive_descent_parser page wikipedia "recursive descent parser"]]
** Le livre référence sur le parsing est probablement "Compilers: Principles, Techniques, and Tools" de Aho, Sethi et Ullman (le "dragon book")
** [[https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/ exemples de notes cours de compilation]]

= Sujets réalisés (2016-2017) =

* [[Algorithme de rendu de scène 3D par Z-buffer]]
* [[Traitement d'image]]
* [[Nim et la théorie des jeux impartiaux]]
* [[Calculabilité et modèles de calcul]]
* [[Génération et résolution de labyrinthes]]

= Sujets proposés (2016-2017) =

== [[Algorithme de rendu de scène 3D par Z-buffer]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le Z-buffer est un algorithme classique de rendu de scène 3D. C'est celui (avec quelques variantes) qui est implémenté dans nos cartes graphiques 3D et qui permet de visualiser des scènes extrêmement complexes en temps réel (typiquement 24 image/s).
* Objectifs:
*# décrire le principe de la projection 3D vers 2D
*# décrire la rastérisation des triangles sur une image en pixel
*# expliquer le principe du Z-buffer qui permet de gérer le fait que certains objets sont cachés par d'autres
*# expliquer comment les couleurs sont calculées par pixel
*# indiquer les qualités et limitations de l'algorithme
* Pour aller plus loin
*# mettre du code démo (WebGL) avec quelques explications sur le pipeline graphique OpenGL
*# expliquer comment on peut utiliser cet algorithme pour calculer des ombres (shadow map)
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Z-buffer Wikipedia]]
** [[https://www.scratchapixel.com/lessons/3d-basic-rendering/rasterization-practical-implementation/overview-rasterization-algorithm Scratch a pixel]]

== [[Traitement d'image]] ==

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le traitement d'image rassemble tous les algorithmes utilisés pour transformer les images, les améliorer, éliminer certaines perturbations, augmenter ou diminuer le contraste, changer les couleurs vers d'autres couleurs, éliminer le flou ou les yeux rouges, faire du cartooning pour un rendu moins photo-réaliste, etc.
* Objectifs:
*# identifier les grandes familles de traitement: restauration, égalisation, élimination du flou de déplacement, segmentation, etc
*# identifier les grandes familles de techniques: filtrage spatial, filtrage fréquentiel, optimisation, etc
*# comprendre les points communs et différences entre le traitement des images noir et blanc et le traitement des images couleurs.
*# choisir un ou deux algorithmes de traitement et les expliquer en détails
* Pour aller plus loin
*# Coder un algorithme de traitement d'image simple (e.g, un filtrage médian, ou un algo qui transporte les couleurs d'une photo vers une autre photo)

* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Traitement_d%27images Wikipedia]]
** [[http://www.ipol.im/ Image Processing on line]] (permet de tester en ligne des algorithmes sur vos images)

== [[Nim et la théorie des jeux impartiaux]] ==

* Tuteur: Pierre Hyvernat

* Étudiant : Luca Chapelle

* Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des premiers jeux ayant été analysé mathématiquement (par Charles Bouton en 1901). Les stratégies gagnantes peuvent être calculées en utilisant le développement en base 2 des nombres, et l'opération d'"addition de Nim" (XOR). La théorie de ce type de jeux (jeux "impartiaux") est assez simple, mais de nombreuses instances de jeux sont encore non résolues.
* Objectifs:
*# comprendre la théorie du jeu de Nim (et la programmer)
*# comprendre le théorème de Sprague Grundy qui montre que tout jeu impartial est équivalent à un jeu de nim
*# regarder quelques autres exemples de tels jeux : jeu de Nim déguisés, ou jeux véritablement différents
*# programmer une version naịve de recherche de stratégie basée sur le théorème de Sprague-Grundy pour quelques jeux

* Liens pour commencer
** [https://fr.wikipedia.org/wiki/Jeux_de_Nim jeu de Nim]
** [https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Sprague-Grundy théorème de Sprague Grundy]
** [https://fr.wikipedia.org/wiki/Jeu_de_Grundy jeu de Grundy]

== La suite de Conway et la classification périodique des "éléments" ==

* Tuteur : Pierre Hyvernat
* La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
** "1" : un "1" -> 11
** "11" : deux "1" -> 21
** "21" : un "2", un "1" -> 1211
** "1211" : un "1", un "2", deux "1" -> 111221
** etc.
Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".
* Objectifs :
*# comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
*# programmer la suite de Conway pour retrouver la classification des "atomes"
*# écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
*# écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

* Liens pour commencer
** [[https://fr.wikipedia.org/wiki/Suite_de_Conway suite de Conway]]
** [[https://fr.wikipedia.org/wiki/Suite_de_Robinson suite de Robinson]]

== Initiation à la démonstration sur ordinateur et certification de logiciel ==

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

== [[Calculabilité et modèles de calcul]] ==

* Tuteur: Rodolphe Lepigre
* Résumé: Une fonction f sur l'ensemble des entiers naturels est dite calculable s'il existe une procedure effective (ou un algorithme) qui permet, étant donné un entier n, de calculer f(n) en temps fini. Il existe divers modèles de calcul qui permettent de représenter toutes les fonctions calculables : machines de Turing, λ-calcul, automates cellulaires, ...
* Objectifs:
*# comprendre la notion de fonction calculable,
*# comparer l'ensemble des fonctions à l'ensemble des fonctions calculables,
*# regarder et comparer quelque modèles de calcul,
*# programmer un modèle de calcul et comprendre les limitations pratiques.

* Liens pour commencer:
** https://fr.wikipedia.org/wiki/Calculabilité
** https://fr.wikipedia.org/wiki/Machine_de_Turing
** https://fr.wikipedia.org/wiki/Lambda-calcul
** https://fr.wikipedia.org/wiki/Jeu_de_la_vie

== [[Génération et résolution de labyrinthes]] ==

* Tuteur: <strike>Jacques-Olivier Lachaud</strike> Xavier Provençal
* Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
* Objectifs:
*# Comprendre comment représenter avec une structure de données un labyrinthe
*# Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
*# Comprendre l'algorithme d'arbre couvrant minimum
*# Comprendre le principe du parcours en profondeur et de la récursivité
* Pour aller plus loin
*# coder la génération d'un labyrinthe et sa visualisation
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe Wikipedia]]
** [[https://en.wikipedia.org/wiki/Maze_generation_algorithm Version anglaise plus complète]]

== Pavages par polyomino ==

* Tuteur: Xavier Provençal
* Résumé : On s'intéresse aux pavages du plan par des tuiles formées de petits carrés collés les uns aux autres, appelé "polyominos". Étant donné une tuile, peut-on paver le plan ? Si oui, avec quelles opérations (translation et/ou rotations et/ou réflexions) Une fois un pavage réalisé, on observe ses propriétés. Quelles symétries ? Le pavage est-il identique du point de vue de chacune des tuiles ? Si ce n'est pas le cas, en combien de classes peut-on diviser ces tuiles ?
On s'intéressera aussi à des propriétés connexes. Au lieu de paver tout le plan, on peut essayer de paver une région finie donnée. Plus localement, peut-on encercler complètement une tuile avec des copies d'elle-même, sans former de trous ? Si oui, peut-on faire de même avec la proto-tuile formée par la tuile de départ et toutes ses copies ? Si oui, combien de fois peut-on répéter l'opération ?
* Objectifs :
*# Comprendre les différentes classes de pavages (isohédral, k-isohédral, anisohédral).
*# Pour chacun des sept types de pavages "isohédraux", comprendre le lien entre les symétries du pavages et la caractérisation des tuiles qui le réalisent.
*# Pour un pavage k-isohédral, identifier les "classes d'équivalences" et le "domaine fondamental".
* Pour aller plus loin :
*# Coder la génération de tuiles capables de paver le plan en fonction pour une classe de pavages donnée.
*# Étudier et implémenter certains algorithmes pour le pavages d'un domaine fini.
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Polyomino Polyomino]]
** [[https://en.wikipedia.org/wiki/Polyomino Polyomino (en)]]
** [[https://fr.wikipedia.org/wiki/Pavage_par_des_polygones_r%C3%A9guliers Pavages]]

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

2020-05-12T19:24:24Z

Rpajean :

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.

[[Fichier:Exemple_graphe.jpg]]

== 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}]->

<nowiki>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</nowiki>
[[Fichier:Exemple_noeuds.png]]

=== 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:

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

Puis on crée des noeuds Genre avec des paramètres:
<nowiki>
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)})</nowiki>

<nowiki>
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)})
...
...</nowiki>
On utilise cette requête pour chaque genre

On crée les relations entre les Films et les Genres :
<nowiki>
MATCH (f:Film)
MATCH (g:Genre)
WHERE f.idFilm = g.idGenre
CREATE (f)-[:DU_GENRE]->(g)</nowiki>

On peux observer le résultat avec la commande :
<nowiki>
MATCH (f:Film)-[r]->(g:Genre)
RETURN f,r,g LIMIT 50</nowiki>
[[Fichier:Graph_films_genres.png | 800x800px]]

On crée des noeuds Utilisateur avec des paramètres :
<nowiki>
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)</nowiki>

Pour finir, on ajoute les relations entre les utilisateurs et les films avec comme paramètre la note qu'ils ont donné au film :
<nowiki>
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)</nowiki>

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 :
[[Fichier:Formule_sim_jaccard.png]]

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 :

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

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 :
<nowiki>
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</nowiki>
Et voici le resultat :
[[Fichier:Resultats_sim_jaccard.png]] 
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 :
<nowiki>
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</nowiki>

J'obtient les films suivants : 
[[Fichier:Resultat_recom_1.png]] 
Donc Bridcage, Clerks et Rock sont susceptible d'intéresser l'utilisateur 117.

Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png]] 
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 :
<nowiki>
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)</nowiki>

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 : 
[[Fichier:Graphe_pays_ville.png | 1000x1000px]]

=== 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 :
<nowiki>
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])</nowiki>

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 :
<nowiki>
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)</nowiki>

=== Exploitation de la base de donnée : ===
Voici le résultat pour la ville de Sichuan en Chine :
[[Fichier:Graphe_contamination_potentiel.png]] 
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. 
[[Fichier:Graphe_contamination_potentiel_Chine.png]] 

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 :
<nowiki>
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</nowiki>
Le resultat est : 
[[Fichier:Resultat_nbr_Wuhan.png]] 

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 :
<nowiki>
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</nowiki>

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 :
<nowiki>
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</nowiki>
Et voici le resultat : 
[[Fichier:Resultat_liste_pays.png | center]]

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

2020-05-12T19:24:06Z

Rpajean :

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.

[[Fichier:Exemple_graphe.jpg]]

== 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}]->

<nowiki>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</nowiki>
[[Fichier:Exemple_noeuds.png]]

=== 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:

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

Puis on crée des noeuds Genre avec des paramètres:
<nowiki>
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)})</nowiki>

<nowiki>
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)})
...
...</nowiki>
On utilise cette requête pour chaque genre

On crée les relations entre les Films et les Genres :
<nowiki>
MATCH (f:Film)
MATCH (g:Genre)
WHERE f.idFilm = g.idGenre
CREATE (f)-[:DU_GENRE]->(g)</nowiki>

On peux observer le résultat avec la commande :
<nowiki>
MATCH (f:Film)-[r]->(g:Genre)
RETURN f,r,g LIMIT 50</nowiki>
[[Fichier:Graph_films_genres.png | 800x800px]]

On crée des noeuds Utilisateur avec des paramètres :
<nowiki>
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)</nowiki>

Pour finir, on ajoute les relations entre les utilisateurs et les films avec comme paramètre la note qu'ils ont donné au film :
<nowiki>
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)</nowiki>

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 :
[[Fichier:Formule_sim_jaccard.png]]

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 :

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

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 :
<nowiki>
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</nowiki>
Et voici le resultat :
[[Fichier:Resultats_sim_jaccard.png]] 
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 :
<nowiki>
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</nowiki>

J'obtient les films suivants : 
[[Fichier:Resultat_recom_1.png]] 
Donc Bridcage, Clerks et Rock sont susceptible d'intéresser l'utilisateur 117.

Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png]] 
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 :
<nowiki>
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)</nowiki>

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 : 
[[Fichier:Graphe_pays_ville.png | 1000x1000px]]

=== 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 :
<nowiki>
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])</nowiki>

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 :
<nowiki>
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)</nowiki>

=== Exploitation de la base de donnée : ===
Voici le résultat pour la ville de Sichuan en Chine :
[[Fichier:Graphe_contamination_potentiel.png]] 
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. 
[[Fichier:Graphe_contamination_potentiel_Chine.png]] 

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 :
<nowiki>
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</nowiki>
Le resultat est : 
[[Fichier:Resultat_nbr_Wuhan.png]] 

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 :
<nowiki>
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</nowiki>

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 :
<nowiki>
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</nowiki>
Et voici le resultat : 
[[Fichier:Resultat_liste_pays.png]]

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

2020-05-12T19:22:34Z

Rpajean :

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.

[[Fichier:Exemple_graphe.jpg]]

== 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}]->

<nowiki>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</nowiki>
[[Fichier:Exemple_noeuds.png]]

=== 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:

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

Puis on crée des noeuds Genre avec des paramètres:
<nowiki>
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)})</nowiki>

<nowiki>
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)})
...
...</nowiki>
On utilise cette requête pour chaque genre

On crée les relations entre les Films et les Genres :
<nowiki>
MATCH (f:Film)
MATCH (g:Genre)
WHERE f.idFilm = g.idGenre
CREATE (f)-[:DU_GENRE]->(g)</nowiki>

On peux observer le résultat avec la commande :
<nowiki>
MATCH (f:Film)-[r]->(g:Genre)
RETURN f,r,g LIMIT 50</nowiki>
[[Fichier:Graph_films_genres.png | 800x800px]]

On crée des noeuds Utilisateur avec des paramètres :
<nowiki>
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)</nowiki>

Pour finir, on ajoute les relations entre les utilisateurs et les films avec comme paramètre la note qu'ils ont donné au film :
<nowiki>
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)</nowiki>

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 :
[[Fichier:Formule_sim_jaccard.png]]

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 :

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

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 :
<nowiki>
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</nowiki>
Et voici le resultat :
[[Fichier:Resultats_sim_jaccard.png]] 
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 :
<nowiki>
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</nowiki>

J'obtient les films suivants : 
[[Fichier:Resultat_recom_1.png]] 
Donc Bridcage, Clerks et Rock sont susceptible d'intéresser l'utilisateur 117.

Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png]] 
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 :
<nowiki>
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)</nowiki>

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 : 
[[Fichier:Graphe_pays_ville.png | 1000x1000px]]

=== 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 :
<nowiki>
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])</nowiki>

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 :
<nowiki>
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)</nowiki>

Voici le résultat pour la ville de Sichuan en Chine :
[[Fichier:Graphe_contamination_potentiel.png]] 
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. 
[[Fichier:Graphe_contamination_potentiel_Chine.png]] 

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 :
<nowiki>
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</nowiki>
Le resultat est : 
[[Fichier:Resultat_nbr_Wuhan.png]] 

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 :
<nowiki>
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</nowiki>

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 :
<nowiki>
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</nowiki>
Et voici le resultat : 
[[Fichier:Resultat_liste_pays.png]]

Fichier:Resultat liste pays.png

2020-05-12T19:22:06Z

Rpajean :

Fichier:Resultat nbr Wuhan.png

2020-05-12T19:15:34Z

Rpajean :

Fichier:Graphe contamination potentiel Chine.png

2020-05-12T19:11:53Z

Rpajean :

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

2020-05-12T16:39:16Z

Rpajean :

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.

[[Fichier:Exemple_graphe.jpg]]

== 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}]->

<nowiki>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</nowiki>
[[Fichier:Exemple_noeuds.png]]

=== 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:

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

Puis on crée des noeuds Genre avec des paramètres:
<nowiki>
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)})</nowiki>

<nowiki>
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)})
...
...</nowiki>
On utilise cette requête pour chaque genre

On crée les relations entre les Films et les Genres :
<nowiki>
MATCH (f:Film)
MATCH (g:Genre)
WHERE f.idFilm = g.idGenre
CREATE (f)-[:DU_GENRE]->(g)</nowiki>

On peux observer le résultat avec la commande :
<nowiki>
MATCH (f:Film)-[r]->(g:Genre)
RETURN f,r,g LIMIT 50</nowiki>
[[Fichier:Graph_films_genres.png | 800x800px]]

On crée des noeuds Utilisateur avec des paramètres :
<nowiki>
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)</nowiki>

Pour finir, on ajoute les relations entre les utilisateurs et les films avec comme paramètre la note qu'ils ont donné au film :
<nowiki>
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)</nowiki>

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 :
[[Fichier:Formule_sim_jaccard.png]]

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 :

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

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 :
<nowiki>
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</nowiki>
Et voici le resultat :
[[Fichier:Resultats_sim_jaccard.png]] 
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 :
<nowiki>
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</nowiki>

J'obtient les films suivants : 
[[Fichier:Resultat_recom_1.png]] 
Donc Bridcage, Clerks et Rock sont susceptible d'intéresser l'utilisateur 117.

Dans l'autre sens je trouve : 
[[Fichier:Resultat_recom_2.png]] 
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 :
<nowiki>
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)</nowiki>

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 : 
[[Fichier:Graphe_pays_ville.png | 1000x1000px]]

=== 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 :
<nowiki>
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])</nowiki>

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 :
<nowiki>
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)</nowiki>

Voici le résultat pour la ville de Sichuan en Chine :
[[Fichier:Graphe_contamination_potentiel.png]]

Fichier:Graphe contamination potentiel.png

2020-05-12T16:37:25Z

Rpajean :

Fichier:Graphe pays ville.png

2020-05-12T16:32:23Z

Rpajean :

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

2020-05-12T15:59:34Z

Rpajean :

Fichier:Resultat recom 2.png

2020-05-12T15:58:52Z

Rpajean :

Fichier:Resultat recom 1.png

2020-05-12T15:57:08Z

Rpajean :

Fichier:Resultats sim jaccard.png

2020-05-12T15:54:29Z

Rpajean :

Fichier:Formule sim jaccard.png

2020-05-12T15:51:07Z

Rpajean :

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

2020-05-12T15:48:06Z

Rpajean :

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

2020-05-12T15:44:14Z

Rpajean : /* Importer une base de donnée CSV */

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

2020-05-12T15:42:04Z

Rpajean : /* Importer une base de donnée CSV */

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

2020-05-12T15:40:33Z

Rpajean :

Fichier:Graph films genres.png

2020-05-12T15:39:08Z

Rpajean : Résultat du graphe des films et leur genres

Résultat du graphe des films et leur genres

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

2020-05-12T15:37:23Z

Rpajean : /* Importer une base de donnée CSV */

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

2020-05-12T15:36:18Z

Rpajean : /* Importer une base de donnée CSV */

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

2020-05-12T15:33:54Z

Rpajean : /* Importer une base de donnée CSV */

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

2020-05-12T15:33:12Z

Rpajean :

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

2020-05-12T15:30:23Z

Rpajean : Cette page wiki est le résumé de mon travail pour le projet de VISI201 sur les bases de données orienté graphe

Fichier:Exemple noeuds.png

2020-05-12T15:23:06Z

Rpajean : Exemple d'un noeud et d'une relation

Exemple d'un noeud et d'une relation

Fichier:Exemple graphe.jpg

2020-05-12T15:08:18Z

Rpajean : Un exemple de graphe sous Neo4j

Un exemple de graphe sous Neo4j