{"id":13259,"date":"2020-11-05T13:34:00","date_gmt":"2020-11-05T13:34:00","guid":{"rendered":"https:\/\/timi.eu\/?p=13259"},"modified":"2021-06-07T13:52:37","modified_gmt":"2021-06-07T13:52:37","slug":"fuzzy-matching-4-methodes-pour-realiser-une-jointure-dans-anatella","status":"publish","type":"post","link":"https:\/\/timi.eu\/fr\/blog-fr\/fuzzy-matching-4-methodes-pour-realiser-une-jointure-dans-anatella\/","title":{"rendered":"Fuzzy matching : 4 m\u00e9thodes pour r\u00e9aliser une jointure dans Anatella"},"content":{"rendered":"\n<div\n\t class=\"wpml-ls-statics-shortcode_actions wpml-ls wpml-ls-legacy-dropdown js-wpml-ls-legacy-dropdown\">\n\t<ul>\n\n\t\t<li tabindex=\"0\" class=\"wpml-ls-slot-shortcode_actions wpml-ls-item wpml-ls-item-fr wpml-ls-current-language wpml-ls-item-legacy-dropdown\">\n\t\t\t<a href=\"#\" class=\"js-wpml-ls-item-toggle wpml-ls-item-toggle\">\n                                                    <img\n            class=\"wpml-ls-flag\"\n            src=\"https:\/\/timi.eu\/wp-content\/plugins\/sitepress-multilingual-cms\/res\/flags\/fr.png\"\n            alt=\"\"\n            width=18\n            height=12\n    \/><span class=\"wpml-ls-native\">Fran\u00e7ais<\/span><\/a>\n\n\t\t\t<ul class=\"wpml-ls-sub-menu\">\n\t\t\t\t\n\t\t\t\t\t<li class=\"wpml-ls-slot-shortcode_actions wpml-ls-item wpml-ls-item-en wpml-ls-first-item\">\n\t\t\t\t\t\t<a href=\"https:\/\/timi.eu\" class=\"wpml-ls-link\">\n                                                                <img\n            class=\"wpml-ls-flag\"\n            src=\"https:\/\/timi.eu\/wp-content\/plugins\/sitepress-multilingual-cms\/res\/flags\/en.png\"\n            alt=\"\"\n            width=18\n            height=12\n    \/><span class=\"wpml-ls-display\">Anglais<\/span><\/a>\n\t\t\t\t\t<\/li>\n\n\t\t\t\t\n\t\t\t\t\t<li class=\"wpml-ls-slot-shortcode_actions wpml-ls-item wpml-ls-item-es\">\n\t\t\t\t\t\t<a href=\"https:\/\/timi.eu\/es\/\" class=\"wpml-ls-link\">\n                                                                <img\n            class=\"wpml-ls-flag\"\n            src=\"https:\/\/timi.eu\/wp-content\/plugins\/sitepress-multilingual-cms\/res\/flags\/es.png\"\n            alt=\"\"\n            width=18\n            height=12\n    \/><span class=\"wpml-ls-display\">Espagnol<\/span><\/a>\n\t\t\t\t\t<\/li>\n\n\t\t\t\t\n\t\t\t\t\t<li class=\"wpml-ls-slot-shortcode_actions wpml-ls-item wpml-ls-item-nl\">\n\t\t\t\t\t\t<a href=\"https:\/\/timi.eu\/nl\/\" class=\"wpml-ls-link\">\n                                                                <img\n            class=\"wpml-ls-flag\"\n            src=\"https:\/\/timi.eu\/wp-content\/plugins\/sitepress-multilingual-cms\/res\/flags\/nl.png\"\n            alt=\"\"\n            width=18\n            height=12\n    \/><span class=\"wpml-ls-display\">N\u00e9erlandais<\/span><\/a>\n\t\t\t\t\t<\/li>\n\n\t\t\t\t\n\t\t\t\t\t<li class=\"wpml-ls-slot-shortcode_actions wpml-ls-item wpml-ls-item-ru wpml-ls-last-item\">\n\t\t\t\t\t\t<a href=\"https:\/\/timi.eu\/ru\/\" class=\"wpml-ls-link\">\n                                                                <img\n            class=\"wpml-ls-flag\"\n            src=\"https:\/\/timi.eu\/wp-content\/plugins\/sitepress-multilingual-cms\/res\/flags\/ru.png\"\n            alt=\"\"\n            width=18\n            height=12\n    \/><span class=\"wpml-ls-display\">Russe<\/span><\/a>\n\t\t\t\t\t<\/li>\n\n\t\t\t\t\t\t\t<\/ul>\n\n\t\t<\/li>\n\n\t<\/ul>\n<\/div>\n\n<h1>Fuzzy matching : 4 m\u00e9thodes pour r\u00e9aliser une jointure<\/h1>\n<p>Dans un&nbsp;pr\u00e9c\u00e9dent article&nbsp;j\u2019ai partag\u00e9 avec vous une solution pour r\u00e9aliser un fuzzy matching entre 2 tables diff\u00e9rentes. J\u2019avais alors compar\u00e9 2 solutions d\u2019ETL (Extract Transform Load). Tableau Prep Builder n\u2019avait pas permis d\u2019aboutir au r\u00e9sultat d\u00e9sir\u00e9. Je m\u2019\u00e9tais donc tourn\u00e9 vers Anatella. Dans l\u2019article d\u2019aujourd\u2019hui j\u2019explore les&nbsp;<strong>diff\u00e9rents algorithmes de Fuzzy Matching disponibles<\/strong>&nbsp;dans cet outil et leurs r\u00e9sultats. Comme vous le verrez, un algorithme ressort grand gagnant de la confrontation.<\/p>\n<h2><img decoding=\"async\" class=\"aligncenter size-large wp-image-13405\" src=\"https:\/\/timi.eu\/wp-content\/uploads\/2021\/04\/introduction-banner-1024x341.jpg\" alt=\"\" width=\"600\" srcset=\"https:\/\/timi.eu\/wp-content\/uploads\/2021\/04\/introduction-banner-1024x341.jpg 1024w, https:\/\/timi.eu\/wp-content\/uploads\/2021\/04\/introduction-banner-600x200.jpg 600w, https:\/\/timi.eu\/wp-content\/uploads\/2021\/04\/introduction-banner-300x100.jpg 300w, https:\/\/timi.eu\/wp-content\/uploads\/2021\/04\/introduction-banner-768x256.jpg 768w, https:\/\/timi.eu\/wp-content\/uploads\/2021\/04\/introduction-banner.jpg 1200w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/>Introduction<\/h2>\n<p>Quand vous souhaitez faire une jointure entre plusieurs tables, vous avez 2 solutions. Soit votre cl\u00e9 de jointure suit exactement la m\u00eame nomenclature dans l\u2019une et l\u2019autre table; soit ce n\u2019est pas le cas. Si vous \u00eates dans le cas b\u00e9ni de la 1\u00e8re situation, passez votre chemin. Cet article ne vous apprendra rien. Si par contre vous \u00eates dans le 2\u00e8me cas (ou simplement curieux), je vous souhaite une bonne lecture.<\/p>\n<hr class=\"clearfix\">\n<h2><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter size-full wp-image-14497\" src=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/algorithme-banner-470x157-1.jpg\" alt=\"\" width=\"470\" height=\"157\" srcset=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/algorithme-banner-470x157-1.jpg 470w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/algorithme-banner-470x157-1-300x100.jpg 300w\" sizes=\"(max-width: 470px) 100vw, 470px\" \/>Algorithmes de fuzzy matching<\/h2>\n<p>Dans le cas d\u2019\u00e9tude que je vous propose, le fuzzy matching est r\u00e9alis\u00e9 sur une cl\u00e9 de jointure qui contient des noms de pays.<br \/>\nIl existe de nombreuses m\u00e9thodes de calcul de similarit\u00e9 entre 2 entit\u00e9s. Ce que j\u2019aime bien dans Anatella, c\u2019est que contrairement \u00e0 d\u2019autres ETL, il vous propose de choisir entre 4 m\u00e9thodes :<\/p>\n<ul>\n<li><a href=\"https:\/\/fr.wikipedia.org\/wiki\/Distance_de_Damerau-Levenshtein\" target=\"_blank\" rel=\"noopener noreferrer\">Distance de Damereau Levenshtein<\/a><\/li>\n<li>Similarit\u00e9 de Damereau Levenshtein (la m\u00eame chose que la distance m\u00eame born\u00e9e entre 0 et 1)<\/li>\n<li><a href=\"https:\/\/fr.wikipedia.org\/wiki\/Distance_de_Jaro-Winkler\" target=\"_blank\" rel=\"noopener noreferrer\">Similarit\u00e9 de Jaro Winkler<\/a><\/li>\n<li><a href=\"https:\/\/fr.wikipedia.org\/wiki\/Indice_de_S%C3%B8rensen-Dice\" target=\"_blank\" rel=\"noopener noreferrer\">Similarit\u00e9 de Dice<\/a><\/li>\n<\/ul>\n<p>Il existe bien entendu d\u2019autres m\u00e9thodes de calcul de similarit\u00e9.&nbsp;<a href=\"https:\/\/www.joyofdata.de\/blog\/comparison-of-string-distance-algorithms\/\" target=\"_blank\" rel=\"noopener noreferrer\">Raffael Vogler<\/a>&nbsp;donne un bon aper\u00e7u des diff\u00e9rentes techniques disponibles dans le package \u201cstringdist\u201d pour R.<\/p>\n<h3 style=\"padding-left: 40px;\">Similarit\u00e9 de Jaro-Winkler<\/h3>\n<p style=\"padding-left: 40px;\">La m\u00e9thode date de 1999 et est une \u00e9volution de la m\u00e9thode de Jaro (1989). Le score obtenu varie entre 0 et 1. Il est calcul\u00e9 en comparant les caract\u00e8res correspondants dans une cha\u00eene de caract\u00e8res puis dans l\u2019autre, et en tenant compte des transpositions de caract\u00e8res.<\/p>\n<h3 style=\"padding-left: 40px;\">Distance de&nbsp;Damereau Levenshtein<\/h3>\n<p style=\"padding-left: 40px;\">La m\u00e9thode est ancienne (1964) et permet de calculer le nombre d\u2019\u00e9tapes n\u00e9cessaires pour transformer une cha\u00eene de caract\u00e8res&nbsp;<em>a<\/em>&nbsp;en une cha\u00eene&nbsp;<em>b<\/em>. Les op\u00e9rations permises sont la suppression, l\u2019insertion, la substitution d\u2019un seul caract\u00e8re, la transposition de 2 caract\u00e8res adjacents. La distance calcul\u00e9e est donc un nombre entier qui correspond aux nombres d\u2019\u00e9tapes n\u00e9cessaires \u00e0 la transformation (0 quand les cha\u00eenes a et b sont identiques).<\/p>\n<h3 style=\"padding-left: 40px;\">Similarit\u00e9 de DICE<\/h3>\n<p style=\"padding-left: 40px;\">La m\u00e9thode est \u00e9galement ancienne (1948) et consiste en une simple comparaison des digrammes. Le coefficient est proche de l\u2019indice de Jaccard. Je vous renvoie \u00e0 Wikip\u00e9dia pour quelques exemples parlants.<\/p>\n<hr class=\"clearfix\">\n<h2><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter size-full wp-image-14509\" src=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/results-banner-470x157-1.jpg\" alt=\"\" width=\"470\" height=\"157\" srcset=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/results-banner-470x157-1.jpg 470w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/results-banner-470x157-1-300x100.jpg 300w\" sizes=\"(max-width: 470px) 100vw, 470px\" \/>Les r\u00e9sultats<\/h2>\n<p>Voici les r\u00e9sultats. Je rappelle que ces derniers ne sont pas transposables \u00e0 n\u2019importe quel cas de figure. Chaque cas doit \u00eatre \u00e9tudi\u00e9 pr\u00e9alablement pour trouver la m\u00e9thode qui convient le mieux. Dans le cas pr\u00e9sent nous parlons de fuzzy matching entre des noms de pays r\u00e9pondant \u00e0 diff\u00e9rentes nomenclatures. Je vous renvoie \u00e0 mon article de la semaine derni\u00e8re pour la liste des cas de figure.<\/p>\n<p>Pour comparer les r\u00e9sultats produits par les diff\u00e9rents algorithmes, j\u2019ai simplement modifi\u00e9 un petit peu le flux dans l\u2019ETL (Anatella) pour mettre en parall\u00e8le les 4 types de \u201cfuzzy joints\u201d propos\u00e9s. Le process est en bleu sur le diagramme ci-dessous (cliquez dessus pour l\u2019agrandir).<\/p>\n<p><a class=\"single-popup-image\" href=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-1.jpg\"><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter size-full wp-image-14503\" src=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-1.jpg\" alt=\"\" width=\"2041\" height=\"762\" srcset=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-1.jpg 2041w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-1-600x224.jpg 600w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-1-300x112.jpg 300w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-1-1024x382.jpg 1024w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-1-768x287.jpg 768w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-1-1536x573.jpg 1536w\" sizes=\"(max-width: 2041px) 100vw, 2041px\" \/><\/a><br \/>\nPour faciliter la lecture j\u2019ai export\u00e9 les r\u00e9sultats dans un fichier Excel (\u00e0 t\u00e9l\u00e9charger&nbsp;<a href=\"https:\/\/www.intotheminds.com\/blog\/app\/uploads\/comparison-agorithms-fuzzy-matching.xlsx\" target=\"_blank\" rel=\"noopener noreferrer\">ici<\/a>).<\/p>\n<p>Les r\u00e9sultats sont parfois \u00e9tonnants.<\/p>\n<p><a class=\"single-popup-image\" href=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-results.jpg\"><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter size-full wp-image-14506\" src=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-results.jpg\" alt=\"\" width=\"1180\" height=\"609\" srcset=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-results.jpg 1180w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-results-600x310.jpg 600w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-results-300x155.jpg 300w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-results-1024x528.jpg 1024w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/fuzzy-matching-comparison-anatella-results-768x396.jpg 768w\" sizes=\"(max-width: 1180px) 100vw, 1180px\" \/><\/a><\/p>\n<p>La m\u00e9thode 2 semble avoir une pr\u00e9dilection pour le Zimbabwe et diff\u00e8re d\u2019ailleurs de la m\u00e9thode 1 (\u00e0 priori proche). On voit que les erreurs de classification sont parfois grossi\u00e8res (South Sudan \/ South Korea).<\/p>\n<p>La m\u00e9thode 3 (Jaro Winkler) est l\u00e9g\u00e8rement meilleure, mais les erreurs de classification sont au final encore trop nombreuses.Toutefois elle pr\u00e9sente un gros avantage (voir prochain paragraphe).<\/p>\n<p>La m\u00e9thode 4 (similarit\u00e9 de Dice) donne les meilleurs r\u00e9sultats. La mauvaise classification de Hong-Kong peut \u00eatre attribu\u00e9e \u00e0 des raisons \u00e9videntes (voir l\u2019entr\u00e9e dans la table de r\u00e9f\u00e9rence). L\u2019erreur sur \u201cGambia\u201d s\u2019explique facilement par l\u2019approche par digrammes propre \u00e0 la m\u00e9thode de Dice-Sorensen.<\/p>\n<hr class=\"clearfix\">\n<h2>D\u00e9finition d\u2019un coefficient de seuil<\/h2>\n<p>Afin d\u2019<strong>\u00e9viter de se retrouver avec des faux positifs ou des faux n\u00e9gatifs, il est utile de d\u00e9finir un coefficient de seuil<\/strong>&nbsp;pour rejeter les r\u00e9sultats qui n\u00e9cessitent un traitement manuel.<\/p>\n<p>Pour la m\u00e9thode de Damereau Levenshtein (m\u00e9thodes 1 et 2) on voit que cette approche n\u2019est pas tr\u00e8s efficace car l\u2019algorithme donne des faux positifs avec des distances calcul\u00e9es peu \u00e9lev\u00e9es (voir Bahamas, Gambia, North Macedonia, South Sudan).<\/p>\n<p>Pour Dice, la d\u00e9finition d\u2019un seuil aux alentours de 0,5 n\u2019aurait pas permis de d\u00e9tecter les 2 faux positifs et aurait livr\u00e9 \u00e9galement un faux n\u00e9gatif (Congo).<\/p>\n<p>Pour la m\u00e9thode 3, la d\u00e9finition d\u2019un seuil \u00e0 0,8 aurait permis d\u2019\u00e9liminer tous les concordances rat\u00e9es mais aurait \u00e9galement g\u00e9n\u00e9r\u00e9 un faux n\u00e9gatif (Trinidad et Tobago).<\/p>\n<hr class=\"clearfix\">\n<h2><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter size-full wp-image-14500\" src=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/conclusion-banner-470x116-1.jpg\" alt=\"\" width=\"470\" height=\"116\" srcset=\"https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/conclusion-banner-470x116-1.jpg 470w, https:\/\/timi.eu\/wp-content\/uploads\/2020\/11\/conclusion-banner-470x116-1-300x74.jpg 300w\" sizes=\"(max-width: 470px) 100vw, 470px\" \/>Conclusion<\/h2>\n<p>La m\u00e9thode de Dice (\u00e9galement appel\u00e9e m\u00e9thode de Sorensen) livre dans cet exercice les meilleurs r\u00e9sultats pour r\u00e9aliser une jointure par fuzzy matching entre des noms de pays. La m\u00e9thode de Jaro-Winkler permet quant \u00e0 elle de d\u00e9finir un seuil \u00e0 0,8 qui \u00e9vacue avec pr\u00e9cis\u00e9ment les r\u00e9sultats non concordants.<\/p>\n<p style=\"margin-top: 30px;\">Source: <a href=\"https:\/\/www.intotheminds.com\/blog\/fuzzy-matching-comparaison-methodes-jointure\/\" target=\"_blank\" rel=\"noopener\">IntoTheMind<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"Explorez les diff\u00e9rents algorithmes de Fuzzy Matching disponibles dans Anatella et leurs performances.","protected":false},"author":1,"featured_media":13261,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[248,184],"tags":[320,318,321,307],"_links":{"self":[{"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/posts\/13259"}],"collection":[{"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/comments?post=13259"}],"version-history":[{"count":14,"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/posts\/13259\/revisions"}],"predecessor-version":[{"id":15438,"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/posts\/13259\/revisions\/15438"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/media\/13261"}],"wp:attachment":[{"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/media?parent=13259"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/categories?post=13259"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/timi.eu\/fr\/wp-json\/wp\/v2\/tags?post=13259"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}