Què és Fuzzy Matching? – TechNative

La concordança difusa (FM), també coneguda com a lògica difusa, concordança aproximada de cadenes, concordança de noms difusos o concordança de cadenes difuses és una tecnologia d’intel·ligència artificial i d’aprenentatge automàtic que identifica elements similars, però no idèntics, en conjunts de taules de dades.

FM utilitza un algorisme per navegar entre regles absolutes per trobar cadenes duplicades, paraules/entrades, que no comparteixen immediatament les mateixes característiques. Quan la lògica de cerca típica funciona en un patró binari, (és a dir: 0:1, sí/no, veritable/fals, etc.), la concordança de cadenes difuses, en lloc d’això, troba cadenes, entrades i/o text en conjunts de dades que es troben entremig. d’aquests paràmetres definitius i navega per graus intermedis de veritat.

La concordança aproximada de cadenes ajuda a trobar coincidències aproximades, fins i tot quan certes paraules s’escriuen malament, s’abreugen o s’ometen, una funció molt utilitzada als motors de cerca. Al final, la concordança aproximada de cadenes proporciona una puntuació de coincidència i, com que s’utilitza per identificar paraules, frases i cadenes que no són una concordança perfecta, la puntuació de la coincidència no serà del 100%.

Com funciona la concordança difusa?

És important aterrar a l’algoritme de concordança difusa adequat per ajudar a determinar la similitud entre una cadena i una altra. En un cas, podríeu tenir una distància d’un sol caràcter de “prova” a “ruta” o cercar “passaport” quan la cadena existent diu “passaport”, una errada d’ortografia. Per descomptat, no tots els casos de lògica difusa seran una qüestió de distància d’un sol caràcter. “Martin Luther Junior” és bastant semblant a “Martin Luther King, Jr”. Les distàncies varien i hi ha diversos algorismes de concordança de noms difusos per ajudar a superar aquestes llacunes.

Hi ha alguns inconvenients per executar una cerca de lògica difusa amb regles poc definides per fer coincidir cadenes. L’ús d’un sistema feble augmenta la possibilitat de falsos positius. Per tal de mantenir aquests falsos positius al mínim o, idealment, inexistents, el vostre sistema aproximat de concordança de cadenes hauria de ser més aviat holístic. Ha de tenir en compte les faltes d’ortografia, les abreviatures, les variacions de noms, les grafies geogràfiques de determinats noms, els sobrenoms escurçats, les sigles i moltes altres variables.

Algoritmes de concordança de noms difusos

Tot i que hi ha molts algorismes de concordança de cadenes per triar quan es reconcilien conjunts de dades, no hi ha una solució única per a tots els casos d’ús. A continuació, es mostren algunes de les tècniques de concordança de cadenes més fiables i utilitzades sovint en ciència de dades per trobar coincidències aproximades.

Distància de Levenshtein

La distància de Levenshtein (LD) és una de les tècniques de concordança difusa que mesuren entre dues cordes, amb el nombre donat que representa fins a quin punt estan les dues cordes de ser una coincidència exacta. Com més gran sigui el nombre de la distància d’edició de Levenshtein, més lluny estaran els dos termes de ser idèntics.

Per exemple, si esteu mesurant la distància entre “Cristian” i “Christian”, tindríeu una distància d’1, ja que estaríeu a una “h” de distància d’una coincidència exacta. Aquest terme sovint és intercanviable amb el terme “distància d’edició”.

Levenshtein edita exemples de distància

  1. Potència -> Pols (inserció de “w”) – Distància: 1
  2. Lovin -> Loving (inserció de “g”) – Distància: 1
  3. Marsopa -> Propòsit (substitució “o” per “u”, inserció de “i”) – Distància: 2

Distància de Hamming

Anomenada pel matemàtic nord-americà Richard Hamming, la distància de Hamming (HD) és força semblant a la de Levenshtein, excepte que s’utilitza principalment en el processament de senyals, mentre que la primera s’utilitza sovint per calcular la distància en cadenes de text. Aquest algorisme utilitza la taula ASCII (American Standard Code for Information Interchange) per determinar el codi binari assignat a cada lletra de cada cadena per calcular la puntuació de distància.

Exemples de distància de Hamming

Agafeu les cadenes textuals “blat de moro” i “suro”. Si intenteu trobar el HD entre aquests dos, la vostra resposta seria una distància de 2, no 1, com obtindreu amb l’algorisme de Levenshtein. Per obtenir aquesta puntuació, heu de mirar l’assignació binària de cada lletra, una per una. Com que la taula de caràcters binaris ASCII assigna el codi (01101110) per a N i (01101011) per a K, notareu que la diferència entre el codi de cada lletra es produeix en dues ubicacions, per tant, un HD de 2.

Damerau-Levenshtein

Aquesta variant LD també troba el nombre mínim d’operacions necessàries per fer que dues cadenes siguin una coincidència directa, utilitzant operacions de distància d’un sol caràcter com la inserció, la supressió i la substitució, però, Damerau-Levenshtein fa un pas més enllà integrant una quarta operació possible: la transposició de dos caràcters per trobar una coincidència aproximada.

Exemple de Damerau-Levenshtein

Corda 1: Michael

Tanga 2: Michaela

Operació 1: transposició: intercanviar els caràcters “a” i “e”

Operació 2: inseriu “a” (final de la cadena 2)

Interval = 2

Cada operació té un recompte d'”1″, de manera que cada inserció, supressió, transposició, etc. es pondera per igual.

Casos d’ús de concordança difusa

Els casos d’ús de FM són amplis, amb moltes aplicacions del món real, la deduplicació és una de les més populars entre elles. Imagineu que publiqueu contínuament el mateix anunci digital a un usuari que ja hagi reaccionat negativament a aquest anunci i favorablement a un altre. Com es veuria afectada l’experiència de l’usuari si una institució financera imposa la detecció de frau en una transacció que l’usuari repeteix setmanalment? És l’ús de la concordança aproximada de cadenes el que ha permès la desduplicació per racionalitzar els registres dins de molts dels nostres sistemes de dades moderns.

Quan vam llançar RediSearch el 2016, una de les seves característiques clau era un motor de suggeriments automàtics amb FM. Qualsevol persona que hagi navegat mai per la web ha vist el suggeriment automàtic en acció en un motor de cerca. Parlant de motors de cerca, heu escrit alguna vegada malament una paraula mentre feu una cerca a Google, però encara heu obtingut els resultats que cerqueu? De fet, Google mostrarà el que creu que volíeu escriure com a consulta principal alhora que ofereix una opció per cercar les paraules tal com les vau escriure just a sota. D’aquesta manera, la concordança difusa ha ajudat a donar forma a com AI/ML ha ajudat a millorar els nostres motors de cerca més fiables.

Beneficis de concordança difusa

La investigació ha descobert que l’error humà representa una quantitat considerable de la duplicació que es produeix en el manteniment de registres i la gestió de dades. Un estudi de la revista de recerca en línia sobre Perspectives en la gestió de la informació sanitària va trobar que els registres mèdics duplicats no només són comuns, sinó també perillosos i costosos. L’estudi, dirigit per Beth Haenke Just, MBA, RHIA, FAHIMA, va utilitzar un conjunt de dades multisite de 398.939 registres de pacients i va trobar que la majoria de les discrepàncies dels camps del nom eren el resultat de faltes d’ortografia (54,14% en camps de noms, 33,62% en cognoms). camps, i un 58,3% per als noms secundaris). L’error humà és sovint el major obstacle en la gestió de dades i la vinculació de registres. La FM s’ha convertit en una eina indispensable per unir conjunts de dades imprecís en l’àmbit mèdic, els serveis financers, la identificació del frau a la seguretat social i molt més. Al final, FM ha ajudat a estalviar a les empreses modernes innombrables hores de treball en la feina sovint onerosa i minuciosa de la deduplicació manual.

Altres avantatges de FM inclouen:

Precisió: FM és molt més granular que la concordança determinista, amb la capacitat de cercar coincidències amb dades imprecises, penetrant més profundament que les cadenes binàries clàssiques

flexibilitat: Els diferents algorismes de lògica difusa disponibles permeten resoldre problemes més complexos

Fàcil de construir: La implementació de la lògica difusa al vostre sistema és un procés senzill

Configurable: És fàcil modificar la lògica per adaptar-se a les vostres necessitats específiques

Implementació de la concordança difusa en diferents llenguatges de programació

Els algorismes de Fuzzy Matching es poden implementar en diversos llenguatges de programació com:

Python – Molts opten per utilitzar la biblioteca Fuzzywuzzy Python quan intenten fer una concordança aproximada de cadenes. Aquesta biblioteca utilitza per defecte l’algorisme LD

R – S’utilitza principalment per a la computació estadística i els gràfics

Java – Una mica més complicat implementar FM a Java, encara que no impossible! Aquest dipòsit de GitHub allotja una implementació Java d’aquesta mateixa biblioteca Fuzzywuzzy

sobresortir – Mitjançant complements com ara Fuzzy Lookup, Exis Echo i fins i tot utilitzant la funció VLOOKUP

Les implementacions són similars, amb tots els idiomes comparant conjunts, emparejant patrons i determinant la distància estadística de la concordança perfecta.

Com minimitzar els errors en la cerca difusa

Amb FM, la fiabilitat no és una garantia infal·lible. De vegades apareixen falsos positius, que requereixen comprovar manualment si hi ha errors. És important preguntar-se: uns quants falsos positius superaran el benefici de fer coincidir correctament més dades de manera exponencial? Si és insignificant, potser dedicar temps a comprovar manualment si hi ha errors no seria temps ben dedicat. Fer coincidir l’algorisme i el llenguatge de programació adequats amb el cas d’ús correcte és la millor manera d’evitar errors en aplicar la lògica difusa a la concordança de dades.


Sobre l’autor

Eric Silva és líder de màrqueting de productes SaaS a Redis. Redis fa que les aplicacions siguin més ràpides, creant una base de dades per a un món en temps real. És la força impulsora de Open-Source Redis, la base de dades en memòria més estimada del món, i proveïdor comercial de Redis Enterprise, una plataforma de dades en temps real. Redis Enterprise ofereix serveis en temps real per a més de 8.000 organitzacions a tot el món. Es basa en la simplicitat i la velocitat inigualables de Open-Source Redis juntament amb una plataforma de dades de grau empresarial que ofereix robustesa dels models de dades moderns, gestió, automatització, rendiment i resiliència per desplegar i executar aplicacions modernes a qualsevol escala des de qualsevol lloc del planeta.

Imatge destacada: Adobe Stock


Leave a Comment

Your email address will not be published. Required fields are marked *