Exploration de données et identification des zones conflictuelles
Stage dans un laboratoire de recherche en informatiques
·
Du 26/06/2020 au 26/08/2020
Lors de mon stage au sein du laboratoire de recherche LIRIS, j'ai été chargé de trouver des méthodes de calcul pour analyser un jeu de données avant l'entrainement d'un algorithme de Machine Learning. J'ai fini par créer des modules python capables d'analyser et de mettre en évidence d'éventuelles données incorrectes ou des valeurs problématiques pour l'entrainement d'un algorithme de Machine Learning. Au tout début de mon stage, j'ai appris les théories sur les méthodes et technologies de Machine Learning, appliquées à Python. Je me suis familiarisé avec les concepts d'intéligence artificiels et de Machine Learning tels que l'apprentissage supervisé/non supervisé ou l'underfiting/overfiting. Suivant une thèse, l'idée du projet était de construire des scripts capables d'identifier des données incorrectes dans un grand ensemble de données. L'idée générale était la suivante : Visant un algorithme de classification, le jeu de données a plusieurs attributs d'entrée qui sont utilisés pour deviner un attribut cible. L'objectif était alors d'évaluer la possibilité de deviner l'attribut cible en partant de l'idée que, s'il existe plusieurs instances dans l'ensemble de données avec les mêmes attributs d'entrée mais une cible différente, alors tout algorithme (quelle que soit sa complexité) sera incapable de réussir à 100 %. Illustrons cela avec un jeu de données courant dans l'apprentissage automatique : l'ensemble de données Iris. Il est constitué de données sur les fleurs d'iris et contient 5 attributs : la largeur et la longueur des sépales, la largeur et la longueur des pétales et l'espèce. Un algorithme de classification doit alors deviner l'espèce en fonction de la largeur et de la longueur des sépales et des pétales. Appliquée à cet ensemble de données, l'idée du projet était de vérifier si deux fleurs ont la même longueur/largeur des sépales et des pétales tout en étant de deux espèces différentes. En considérant l'égalité parfaite comme la fonction de comparaison entre les attributs d'entrée, l'algorithme a une complexité de O(n.log(n)) (en utilisant une Map comme structure de données). Cependant, en considérant une tolérance dans la fonction de comparaison, l'algorithme naïf a une complexité de O(n²), ce qui n'est pas acceptable pour les grands ensembles de données. Mon objectif était donc de trouver des moyens d'effectuer cette recherche dans un temps de calcul acceptable. J'ai effectué une recherche bibliographique pour résoudre le problème de la comparaison de chaque élément de l'ensemble de données à tous les autres éléments dans un temps de calcul raisonnable. Ensuite, j'ai mis en œuvre une méthode appelée Blocking. L'idée sous-jacente est la suivante :
Mapping - Tout d'abord, les valeurs sont mappées en blocs de valeurs similaires.
L'objectif est d'éviter les comparaisons entre des valeurs manifestement différentes.
Reducing - La deuxième étape consiste à comparer les valeurs, à l'aide d'un algorithme naïf,
bloc par bloc. Cette étape peut être parallélisée, car chaque bloc est indépendant.
J'ai ajouté une étape au processus, afin de m'assurer d'être exhaustif, en profitant du fait que nous connaissons la tolérance dans la fonction de comparaison. Cette étape consiste à dupliquer les valeurs aux bords des blocs au sein des blocs environnants, de sorte que chaque valeur soit comparée à toutes ses voisines, quelle que soit sa position absolue dans l'ensemble de données. L'algorithme qui en résulte renvoie des paires de valeurs contradictoires, c'est-à-dire des valeurs dont les attributs d'entrée sont similaires alors que les attributs cibles sont différents. Ces valeurs peuvent être introduites dans des visualisations de zones problématiques/conflictuelles, c'est-à-dire des zones du jeu de données qui contiennent un grand nombre de valeurs contradictoires. Ce type de visualisation peut être utile aux experts de la source de données pour expliquer pourquoi des valeurs contradictoires sont apparues à ces "endroits" ou pour remettre en question la manière dont les données ont été collectées. Enfin, les paires contradictoires peuvent faire l'objet d'un post-traitement afin de rechercher l'ensemble minimal de valeurs à supprimer de l'ensemble de données pour qu'il n'y ait plus de paires contradictoires. Cette recherche est similaire à la recherche d'une couverture minimale de sommets, en ayant comme sommets les valeurs et comme arêtes le fait d'être contradictoires. En effet, si une seule valeur est contradictoire avec 10 autres, on peut facilement conclure à la suppression de cette valeur, mais dans le cas de réseaux plus complexes, la décision est plus difficile à prendre. La recherche de la couverture minimale des sommets est prouvée comme étant NP-complet. Au final, les scripts python développés ont été capables d'identifier en 30 minutes les paires de valeurs contradictoires sur un jeu de données pour lequel l'algorithme naïf aurait pris environ 1 an de calcul. Ce projet m'a permis d'apprendre les concepts et les problèmes liés au Machine Learning, ainsi que d'approfondir mes compétences en algorithmies et en calcul parallèle.
python
algorithm
machine learning
artificial intelligence
parallel computing
research
sphinx