• Home
  • Chimie
  • Astronomie
  • Énergie
  • La nature
  • Biologie
  • Physique
  • Électronique
  •  science >> Science >  >> Autres
    Le hachage des données améliore l'estimation du nombre de victimes dans les bases de données

    Chars détruits devant une mosquée à Azaz, Syrie, en 2012. Crédit :Christiaan Triebert via Wikimedia Commons

    Des chercheurs de l'Université Rice et de l'Université Duke utilisent les outils de la statistique et de la science des données en collaboration avec Human Rights Data Analysis Group (HRDAG) pour estimer avec précision et efficacité le nombre de victimes identifiées tuées dans la guerre civile syrienne.

    Dans un article disponible en ligne et dont la publication est prévue dans le numéro de juin du Annales de statistiques appliquées , les scientifiques font état d'un effort de quatre ans pour combiner une méthode d'indexation des données appelée "hachage avec estimation statistique". La nouvelle méthode produit des estimations en temps réel des données documentées, ont identifié les victimes avec une marge d'erreur beaucoup plus faible que les méthodes statistiques existantes pour trouver les enregistrements en double dans les bases de données.

    « La suppression des enregistrements en double est facile si toutes les données sont propres :les noms sont complets, l'orthographe est correcte, les dates sont exactes, etc., " a déclaré Beidi Chen, co-auteur de l'étude, un étudiant diplômé de Rice en informatique. "Les données sur les victimes de guerre ne sont pas comme ça. Les gens utilisent des surnoms. Les dates sont parfois incluses dans une base de données mais absentes d'une autre. C'est un exemple classique de ce que nous appelons un ensemble de données" bruyant ". Le défi est de trouver un moyen de estimer avec précision le nombre d'enregistrements uniques malgré ce bruit."

    En utilisant les enregistrements de quatre bases de données de personnes tuées pendant la guerre en Syrie, Chen, Rebecca Steorts, statisticienne de Duke et experte en apprentissage automatique, et Anshumali Shrivastava, informaticien de Rice, ont estimé qu'il y en avait 191, 874 individus uniques documentés de mars 2011 à avril 2014. C'est très proche de l'estimation de 191, 369 compilés en 2014 par HRDAG, une organisation à but non lucratif qui aide à construire scientifiquement défendable, arguments fondés sur des preuves de violations des droits de l'homme.

    Mais alors que l'estimation de HRDAG reposait sur les efforts acharnés des travailleurs humains pour éliminer soigneusement les enregistrements en double potentiels, le hachage avec estimation statistique s'est avéré plus rapide, plus facile et moins cher. Les chercheurs ont déclaré que le hachage avait également l'avantage important d'un intervalle de confiance précis :la plage d'erreur est de plus ou moins 1, 772, ou moins de 1 pour cent du nombre total de victimes.

    "Le grand avantage de cette méthode est que nous pouvons calculer rapidement le nombre probable d'éléments uniques dans un ensemble de données avec de nombreux doublons, " a déclaré Patrick Ball, Directeur de recherche du HRDAG. "Nous pouvons faire beaucoup avec cette estimation."

    Shrivastava a déclaré que la netteté de l'estimation de hachage est due à la technique utilisée pour indexer les dossiers des victimes. Le hachage implique la conversion d'un enregistrement de données complet :un nom, Date, lieu de décès et sexe dans le cas de chaque victime de guerre syrienne, en un nombre appelé hachage. Les hachages sont produits par un algorithme qui considère les informations alphanumériques dans un enregistrement, et ils sont stockés dans une table de hachage qui fonctionne un peu comme l'index d'un livre. Plus il y a de similarité textuelle entre deux enregistrements, plus leurs hachages sont rapprochés dans la table.

    "Notre méthode d'estimation d'entité unique pourrait s'avérer utile au-delà du conflit syrien, " dit Steorts, professeur adjoint de science statistique à Duke.

    Elle a dit que l'algorithme et la méthodologie pourraient être utilisés pour les dossiers médicaux, statistiques officielles et applications industrielles.

    "Comme nous collectons de plus en plus de données, la duplication devient un problème plus actuel et plus important sur le plan social, " a déclaré Steorts. " Les problèmes de résolution d'entités doivent s'étendre à des millions et des milliards d'enregistrements. Bien sûr, le moyen le plus précis de trouver des enregistrements en double est de faire vérifier chaque enregistrement par un expert. Mais cela est impossible pour les grands ensembles de données, car le nombre de paires à comparer augmente considérablement à mesure que le nombre d'enregistrements augmente."

    Par exemple, une analyse enregistrement par enregistrement des quatre bases de données sur la guerre syrienne entraînerait quelque 63 milliards de comparaisons par paires, elle a dit.

    Shrivastava, professeur assistant d'informatique à Rice, mentionné, "Si vous faites des suppositions, comme les dates proches peuvent être des doublons, vous pouvez réduire le nombre de comparaisons nécessaires, mais chaque hypothèse vient avec un biais, et finalement vous voulez une estimation impartiale. Une approche statistique qui évite les biais est l'échantillonnage aléatoire. Alors peut-être choisissez 1 million de paires aléatoires sur les 63 milliards, voyez combien sont des doublons, puis appliquez ce taux à l'ensemble de données. Cela produit une estimation non biaisée, ce qui est bon, mais la probabilité de trouver des doublons purement par hasard est assez faible, et cela donne une grande variance.

    "Dans ce cas, par exemple, l'échantillonnage aléatoire pourrait également estimer les dénombrements documentés à environ 191, 000, " dit-il. " Mais il ne pouvait pas nous dire avec certitude si le compte était de 176, 000 ou 216, 000 ou un nombre entre les deux.

    « Dans des travaux récents, mon laboratoire a montré que les algorithmes de hachage conçus à l'origine pour effectuer des recherches peuvent également être utilisés comme échantillonneurs adaptatifs qui atténuent précisément la variance élevée associée à l'échantillonnage aléatoire, " dit Shrivastava.

    "Résoudre chaque doublon semble très attrayant, " il a dit, "mais c'est le moyen le plus difficile d'estimer le nombre d'entités uniques. La nouvelle théorie de l'échantillonnage adaptatif avec hachage nous permet d'estimer directement le nombre d'entités uniques de manière efficace, avec une grande confiance, sans résoudre les doublons."

    "À la fin de la journée, ça a été phénoménal de faire des progrès méthodologiques et algorithmiques motivés par un problème aussi important, " Steorts a déclaré. "HRDAG a ouvert la voie. Notre objectif et notre espoir est que nos efforts se révéleront utiles à leur travail. »

    Shrivastava et Steorts ont déclaré qu'ils prévoyaient de futures recherches pour appliquer la technique de hachage pour une approximation d'entité unique à d'autres types d'ensembles de données.


    © Science https://fr.scienceaq.com