# Nettoyage de données

Le nettoyage de données est l'opération de détection et de correction (ou suppression) d'erreurs présentes sur des données stockées dans des bases de données ou dans des fichiers.
Le nettoyage de données est un des problèmes majeurs des entrepôts de données.
Les données présentes dans les bases de données peuvent avoir plusieurs types d'erreurs comme des erreurs de frappe, des informations manquantes, des imprécisions etc. La partie impropre de la donnée traitée peut être remplacée, modifiée ou supprimée. Le processus de nettoyage identifie les données erronées et les corrige automatiquement avec un programme informatique ou les propose à un humain pour qu'il effectue les modifications.
Le nettoyage de données est différent de la validation de données. La validation de données est l'étape qui consiste à vérifier et rejeter les données qui ne respectent pas certaines règles avant l'ajout en base de données, alors que le nettoyage intervient après (sur des données déjà présentes en base de données).
Les approches classiques de nettoyage utilisent les contraintes d'intégrité, les statistiques ou l'apprentissage automatique pour nettoyer les données.

## Problématique

Les problèmes liés au nettoyage de données sont apparus au début des années 2000 avec l'explosion d'Internet et des entrepôts de données.
Les entrepôts de données sont utilisés pour la prise de décision. Ceci implique que les données doivent être fiables. Des données incorrectes ou incohérentes peuvent conduire à de fausses conclusions et à de mauvaises prises de décision.
Par exemple, le gouvernement peut vouloir analyser les chiffres du recensement de la population pour décider quelles régions exigent davantage de dépenses et d'investissements en infrastructures et services. Dans ce cas, il est important d'avoir accès à des données fiables pour éviter des décisions budgétaires erronées.
Les erreurs dans les données coûtent aux entreprises l'équivalent de 30 à 50 % de leur budget d’implémentation. De plus, on estime que 40 à 50 % du budget temps d'un projet est dépensé dans la correction d'erreurs dans les données.

## Types d'erreurs

Les erreurs sur les données peuvent être de toutes sortes. Par exemple, une erreur peut apparaître lors d'une saisie (donnée manquante, données dupliquées, erreur de saisie, mauvais format, etc.)
Exemple d'erreurs multiples :
| Prénom | Âge | Reproduction sexuée | Taille |
| Alice | 150 | F | 1,70 |
| Bob Joe | 34 | M | |
| Charlie | 19 | 1,67 | |

### Erreurs de syntaxe
#### Erreurs lexicales

Une erreur lexicale est une divergence entre le nom de la donnée attendu et le format spécifié.
Exemple d'erreur lexicale :
| Prénom | Âge |
| Alice | F |
| Bob | M |
| Charlie | 21 |

#### Erreurs de formatage

Une erreur de formatage est une entrée qui ne correspond pas à un modèle donné.
Exemple d'erreur de formatage :
* Nom
* Doe, John
* John Smith

#### Erreurs d'irrégularité

Une erreur d'irrégularité se produit lorsqu'une donnée n'est pas représentée de façon régulière, en suivant le même schéma, la même suite logique d'écriture. Cela peut intervenir pour la représentation de distance par exemple en utilisant différents systèmes métriques.
Exemple d'irrégularité :
* Distance
* 25 km
* 23 km
* 20 mi

### Erreurs sémantiques
#### Violation des contraintes d'intégrité

Ce sont les erreurs qui ne respectent pas les règles d'intégrité du schéma de données.
Ce sont souvent des règles de bon sens comme la vérification d'une valeur supérieure à 0 pour l'âge d'une personne ou encore la vérification de l'unicité d'une clé primaire dans une base de données.

#### Erreurs de contradiction

Les erreurs de contradiction sont des contradictions dans les données.
Par exemple une erreur de contradiction peut intervenir lorsque l'âge spécifié ne correspond pas à la date de naissance.

#### Erreurs de duplication

Les erreurs de duplication surviennent lorsque plusieurs occurrences de la même donnée sont stockées.
Ces erreurs peuvent être vues comme un cas spécifique des erreurs de contradiction.

#### Erreurs de donnée invalide

Ce sont des entrées qui sont dites invalides mais qui ne sont pas détectables par la mise en place de contraintes. Ce sont des erreurs qui sont spécifiques au domaine.

### Erreurs de couverture
#### Valeur manquante

Ce type d'erreur provient d'une omission d'un champ de la donnée, lorsque la valeur attendue est manquante.
Exemple de valeur manquante :
| Prénom | Âge | Sexe | Taille |
| Alice | 23 | F | 1,70 |
| Bob | 34 | M | 1,82 |
| Charlie | 19 | M | |

#### Donnée manquante

Ce type d'erreur provient lorsqu'une donnée est vide ou manquante.
Exemple de donnée manquante :
| Prénom | Sexe | Taille |
| Alice | F | 1,70 |
| Bob | M | 1,86 |
| Charlie | M | 1,68 |

## Méthodes existantes

On distingue deux types d'approches :
* Celles des entreprises, qui utilisent généralement des nettoyeurs de type ETL. Ce type d'approche a été le premier à avoir vu le jour.
* Celles des scientifiques, qui explorent de nouvelles approches qui se basent sur les contraintes d'intégrité$^,$$^,$$^,$$^,$, les statistiques, l'apprentissage automatique ou encore le crowdsourcing.
Le nettoyage de données se décompose en 3 phases :
* Analyser les données afin de détecter les potentiels problèmes
* Choisir le type de transformations à effectuer
* Appliquer ces informations aux données

### Parsing

La méthode de parsing est utilisée pour la détection d'erreurs de syntaxe. Un parseur décide de l'acceptabilité de la donnée représentée par une chaîne de caractères. Il s'assure que la donnée suit la spécification.
Ce type d'approche requiert un ensemble de données qui peut être converti en distance pour pouvoir être comparé.
Cette approche a ses limites. En effet, celle-ci se base généralement sur des expressions régulières pour déterminer la validité d'une entrée. Ce processus de vérification peut être amélioré avec des techniques d'apprentissage automatique.

### Transformation de donnée

La transformation de donnée est une opération qui regroupe plusieurs champs en un seul.
Par exemple, la décomposition d'une date en plusieurs champs (année, mois et jour) ou encore la transformation d'une entrée de type booléen en entier (true = 1).

### Renforcement des contraintes d'intégrité

Les contraintes d'intégrité sont au départ utilisées pour prévenir des erreurs sur les données, cependant il se peut qu'elles ne suffisent pas et que des erreurs sur les données se manifestent au fil du temps. Dans certains cas, le meilleur moyen d'améliorer la qualité des données n'est pas de corriger les données corrompues, mais plutôt de modifier les contraintes d'intégrité car la sémantique des données ou de l'application peut avoir évolué.
Le but de cette méthode n'est pas de modifier les données de manière directe mais de trouver et modifier les contraintes d'intégrité douteuses afin qu'elles s'accordent mieux avec les données.

### Méthode statistique

Malgré les recherches faites sur les contraintes d'intégrité ainsi que sur d'autres méthodes visant à améliorer la qualité des données, les bases de données peuvent encore contenir un certain nombre d'erreurs subtiles, syntaxiques ou sémantiques, qu'il est difficile voire impossible d'exprimer (et détecter) en utilisant les contraintes générales offertes dans les SGBD actuels.
L'utilisation des statistiques permet d'obtenir des corrections d'erreurs plus fiables. En identifiant de potentielles dépendances statistiques entre les paires de données similaires et en développant des algorithmes que l'on peut greffer simplement dans les SGBD standards, on peut estimer automatiquement ces dépendances. Cette méthode permet par exemple de déduire des valeurs correctes même en présence de valeurs manquantes ou corrompues.
Les méthodes statistiques peuvent être utilisées pour l'analyse des données et/ou leur correction.

### Crowdsourcing

Il peut arriver que les méthodes précédentes n'aient pas assez d'éléments de preuve pour pouvoir identifier et corriger les erreurs.
Une approche basée sur le crowdsourcing permet d'utiliser des bases de connaissance externes qui permettent d'identifier plus d'erreurs automatiquement.
Les erreurs détectées qui ne peuvent être réparées automatiquement sont proposées à un humain qui les corrige manuellement.

## Solutions existantes

La recherche permet d'apporter de nouvelles solutions qui utilisent les approches citées précédemment. En voici quelques-unes :

### Potter's wheel

Potter's wheel est une méthode de nettoyage de données interactive qui permet la détection et la transformation de données.
Cette solution permet à l'utilisateur de construire des transformations lorsque celles-ci se présentent et d'ainsi améliorer itérativement la détection et la transformation. Ceci sans écrire de programmes complexes ou de perdre du temps de développement.
Potter's wheel fournit des transformations les plus générales possibles et assez puissantes pour faire la plupart des tâches de transformation sans programmation. Les utilisateurs saisissent des expressions régulières ou des expressions grammaticales pour spécifier les transformations à effectuer.
Avec Potter's wheel, c'est à l'utilisateur de choisir le résultat qu'il désire en sortie.
Le problème de l'approche de Potter's Wheel est de trouver une expression régulière qui ressemble le plus à la valeur à modifier sans pour autant lui être trop spécifique. Il faut garder à l'esprit que celle-ci peut avoir des variantes.

### AJAX

AJAX est un framework qui tente de séparer la partie logique (design et spécification du workflow) de la partie physique (implémentation). AJAX modélise la logique de nettoyage de données par un graphe orienté de transformations. Il prend comme entrée des données contenant des erreurs et renvoie des données propres.
Le but majeur est de transformer des données existantes venant d'une ou plusieurs collections en un schéma cible tout en éliminant les doublons pendant le processus. Le processus se décompose en 5 transformations : mapping, view, matching, clustering et merging. Le matching operator est notamment important dans la détection des doublons.
AJAX possède :
* des opérateurs logiques (extension d'algèbre relationnelle)
* des algorithmes d’exécution physique
* un langage déclaratif pour les opérateurs logiques
Ce langage consiste en des requêtes SQL enrichies par des primitives spécifiques. Son aspect déclaratif est hérité du SQL et garantit un déploiement ainsi qu'une maintenance facile des programmes de nettoyage de données. Il n'est cependant pas complètement déclaratif de par la présence de code impératif servant à la customisation pour un programme particulier si besoin.

### IntelliClean

IntelliClean est une approche fondée sur des règles essentiellement centrées sur l'élimination des doublons.
Cette solution consiste en 3 étapes :
* Pré-processing : élimination des erreurs syntaxiques, standardisation des formats et abréviations utilisées.
* Processing : évaluation des règles de nettoyage sur les données qui spécifie une action à effectuer sous certaine condition.
* Human Verification/Validation : les deux premières étapes produisent des logs de leur exécution qui permettent lors de la troisième étape à des humains de les étudier afin de vérifier et/ou corriger les précédentes actions effectuées.
Il y a 4 types de règles pour l'étape Processing :
* Duplicate identification : ces règles spécifient les conditions qui permettent d'affirmer quels tuples sont des doublons.
* Merge/Purge : ces règles indiquent comment les doublons doivent être gérés.
* Update Rules : ces règles indiquent comment les données doivent être gérées dans certaines conditions, elles permettent notamment la spécification de règles de renforcement des contraintes d'intégrité en indiquant la manière dont les valeurs manquantes doivent être remplies.
* Alert rules : ces règles spécifient les conditions pour lesquelles l'utilisateur est notifié.

### FraQL

FraQL est un autre langage déclaratif permettant la spécification d'un processus de nettoyage de données. Il est similaire à AJAX par le fait que c'est également une extension du SQL. FraQL permet de spécifier transformations de schémas et de données, standardisations/normalisations de valeurs grâce à des fonctions créées par l'utilisateur.
Grâce à la combinaison de ces fonctions utilisateurs avec les opérateurs de jointure et d'union, FraQL permet l'identification et l'élimination des doublons. Enfin cette solution permet le remplissage de valeurs manquantes ainsi que l'élimination de tuples invalides par la détection du bruit dans les données.

### ARKTOS

ARKTOS est un framework capable d’exécuter de l'ETL pour la création d'entrepôts de données. En effet, les auteurs de cette solution considèrent le nettoyage de données comme une part de l'ETL. Les étapes individuelles du processus sont appelées activités. Chaque activité est liée à une entrée et une sortie. La logique d'une activité est décrite par une requête SQL. Chaque requête est associée à un type d'erreur et une règle qui indique le comportement en cas de rencontre d'une telle erreur.
Il y a 6 types d'erreurs possibles dans un processus ETL, PRIMARY KEY VIOLATION, UNIQUENESS VIOLATION et REFERENCE VIOLATION sont des cas particuliers de violation de contraintes d'intégrité. Le type d'erreur NULL EXISTENCE est lié à l’élimination des valeurs manquantes. Les types d'erreurs restantes sont DOMAIN MISMATCH et FORMAT MISMATCH qui font référence au lexique et aux erreurs de formatage.
Les comportements qu'il est possible d'associer à une erreur sont IGNORE, qui ne va pas marquer le tuple comme erroné, DELETE, WRITE TO FILE et INSERT TO TABLE avec la sémantique attendue. Seuls les deux derniers permettent une interaction avec l'utilisateur.
La qualité du nettoyage peut être mesurée pour chaque activité en exécutant une requête SQL similaire qui va compter le ratio matching/violating des tuples.
ARKTOS définit deux langages déclaratifs servant à spécifier le processus ETL. Il est également muni d'un constructeur de scénarios graphiques.

### KATARA

KATARA est un système qui fait le pont entre les bases de connaissance et le crowdsourcing pour un nettoyage des données de bonne qualité.
Contrairement à d'autres approches, KATARA utilise un algorithme pour retrouver les types des données et les relations entre celles-ci. Grâce à ces informations, KATARA utilise une approche probabiliste pour déterminer la correction la plus cohérente à faire. Ces probabilités sont déterminées grâce aux bases de connaissances.
La recherche des données corrompues est un problème difficile. Pour améliorer cette recherche, la qualité des nettoyages ainsi que la précision des réparations, KATARA améliore les bases de connaissances avec les nouvelles entrées nettoyées et vérifiées par des humains.
KATARA permet aux entreprises de faire des économies. En effet, faire appel au crowdsourcing implique qu'il n'est pas nécessaire d'avoir un expert du domaine pour réparer une donnée corrompue.