Sujet du projet

La percolation (mathématique) est une étude qui permet d'étudier la propagation d'une information ou d'une maladie. Si on considère les points d'un graphe aléatoire qui sont reliés (ou pas) avec une certaine probabilité p, on considère que la percolation a eu lieu si il y a un passage entre 2 extrémités du graphe ou s'il existe des composantes connexes infinies (dans le cas des graphes infinis).

Il est intéressant de simuler ce type de graphes de manière à mesurer certaines valeurs comme la taille moyenne des clusters ou la probabilité de percolation effective en fonction de p. Pour être utilisables, les algorithmes de génération de graphe doivent être efficaces, il est par exemple trop coûteux de générer un grand nombre de graphes aléatoires et de calculer à chaque fois leur composantes connexes pour chaque valeur de p. Dans « A Fast Monte Carlo Algorithm for Site or Bond Percolation » Newman et Ziff propose un algorithme itératif que nous vous proposons d'implémenter.

Implémenter l'algorithme basé sur les arbre de l'article et faire une interface graphique permettant de le piloter.

• Classification automatique

• Ensembles de cours datamining (cf *Arbre de décision* et *Random Forest*)
• Un fichier de donner pour commencer

La classification automatique est un domaine où on cherche à apprendre à reconnaitre la classe d'individus à partir d'exemples. Une technique parmis les plus efficaces est basée sur la construction d'un grand nombre d'arbres de décision (ce qu'on appelle forêt aléatoire). En effet, l'expérience montre que si on construire suffisamment de classifieurs différents entre eux mais efficaces, le fait de decider en fonction de la majorité des classifieurs appporte un grand gain.

Le but de votre projet est d'implémenter un algorithme classique de construction d'une forêt.

Pour cela il faut :

1. implémenter la construction d'un arbre de décision à partir d'un jeu de donnnées d'exemples;
2. implémenter un système permettant de générer un grand nombre d'arbres de décision;
3. mettre en place un système de test permettant de mesurer la qualité de vos algorithmes.

Votre logiciel devra être capable à partir d'un fichier d'exemple dans un format simple (CSV) de construire un modèle. Puis à partir d'un modèle et d'un fichier de test dans le même format de trouver les classes des objets.

Les améliorations possibles de votre travail pouront porter sur les différentes optimisations ou adaptations de l'algorithme à des cas spécifiques, sur l'amélioration du temps temps de calcul et du coût mémoire de votre programme. Vous pourrez aussi ajouter des prétraitements pour résoudre les cas ou les données sont lacunaires ou ajouter une interface graphique au programme.

• Classification automatique

• Ensembles de cours datamining (cf *SVM*)
• Un fichier de données pour commencer

Les Machines à vecteurs de support (Support Vector Machines) sont des outils de classification automatique efficaces. Ils permettent de trouver un séparateur qui permet de discriminer les classe dans un jeu d'exemple. Ce séparateur tente de maximiser la marge c'est à dire la distance avec les exemples connus.

Pour cela, on utilise un noyaux, c'est à dire une matrice des distances entre les points du jeu d'exemple. Votre logiciel devra implémenter l'algorithme de calcul de ce séparateur pour en utilisant une fonction noyau quelconque (symétrique définie positive). Il devra fonctionner pour le cas des problème à 2 classes.

Pour améliorer l'algorithme vous pouvez :

• améliorer le temps de calcul;
• généraliser l'algorithme à un nombre de classe non limité;
• ajouter des prétraitement pour supporter les données manquante ou éliminer les données abérantes.

• calcul de valeur propres,
• visualisation de données

• Alain Baccini et Philippe Besse, Exploration Statistique, chapitre 7

Le multi-dimensionnal scalling (ou positionnement multi-dimensionnel MDS) est une technique qu'on utilise souvent pour visualiser des données. Cela permet de calculer des coordonnées de points dont on ne connaît que les distances 2 à deux. On peut ainsi retrouver les coordonnées de points existants, mais aussi créer des cartes utilisant d'autres informations que la distance euclidienne (à vol d'oiseau). Par exemple, repositionner les villes d'un pays en fonction du temps nécessaire pour les joindre en transport en commun, positionner les députés en fonction de leurs votes …

Votre programme devra implémenter la construction MDS de donnée utilisant l'algorithme classique qui se résume à calculer des valeurs propres d'une matrice obtenue à partir de la matrice de distances. Il devra a partir d'un fichier contenant la liste des points et leur distance, fournir un fichier contenant les coordonnées calculées ce ces points.

Pour améliorer le programme, vous pourrez faire:

• une interface graphique pour manipuler les fichiers et visualiser le résultat;
• implémenter d'autres méthodes de calcul plus robustes;
• améliorer le temps de calcul et l'utilisation mémoire de votre programme
• …

• analyse de text,
• manipulation de grandes matrices

• Global Vectors for Word Representation
• Article expliquant l'algorithme

Le word embedding est une méthode à la base de nombreux travaux d'analyse du langage naturel. Il consiste à vouloir transformer les mots de la langue en un ensemble de vecteur mathématiques. Le but est de le faire en concervant une certaine notion du sens des mot.

Le moyen de faire cela est de travailler à partir d'une matrice de co-occurences des mots dans les phrases trouvées dans un grand corpus de texte (par exemple wikipedia). Cette matrice contient une partie du sens des mots car le sens dépend du context. Mais cette matrice est trop grande pour être utilisée. Il faut alors appliquer une technique de réduction de dimension de la matrice pour obtenir les vecteurs souhaités.

Ce projet demande de manipuler des données de grande taille. L'une des difficulté sera par exemple de créer la matrice de co-occurence alors que sa taille est de l'ordre du million.

• Part Of Speech
• Maximisation d'entropie

• Un article expliquant la méthode
• Un exemple de déroulement de l'algorithme présenté dans l'article

Reconnaitre la nature grammaticale d'un mot, ou Part Of Speech (POS), est un point de départ dans beaucoup de tâches de traitement du langage naturel. Il s'agit de reconnaitre automatiquement la nature d'un mot dans une phrase. Par exemple :

• Dans “des avions ont décollé ce matin”, “avions” est un nom
• Dans “Nous avions déjeuné”, “avions est un verbe

Le but de l'algorithme est d'être capable d'affecter un label (la nature) à chaque mot d'une phrase en considérant le contexte (c'est à dire la phrase). Une des technique utilisée pour faire cela est basé sur de l'apprentissage automatique. Elle apprend à partir d'exemples un modèle statistique qui est capable de donner une probabilité d'affecter un label en fonction du contexte. Pour mettre au point ce modèle, on utilise un série d'exemples et un algorithme de maximisation d'entropie.

Votre projet doit être capable de créer ce modèle à partir d'exemples de la litérature et de les tester pour mesurer leurs performances.

Pour améliorer le travail vous pouvez aussi :

• travailler les prétraitements permettant d'augmenter la performance (traitement des mots inconnus, correction de l'orthographe, …)
• ajouter des post traitements comme retrouver la forme canonique des mots (verbe à l'infinitif, nom au singulier, …)
• …