Natural Language Processing for Fuzzy String Matching with Python

Tietotekniikassa sumea merkkijonojen täsmäytys on tekniikka, jonka avulla etsitään merkkijonoja, jotka täsmäävät kuvioon suunnilleen samansuuntaisesti (pikemminkin kuin täsmälleen). Toisinsanoen, sumea merkkijonojen täsmäytys on hakutyyppi, joka löytää osumia, vaikka käyttäjät kirjoittaisivat sanoja väärin tai syöttäisivät hakuun vain osittaisia sanoja. Se tunnetaan myös nimellä likimääräinen merkkijonojen täsmäytys.

Sumeaa merkkijonohakua voidaan käyttää erilaisissa sovelluksissa, kuten:

• Oikeinkirjoituksen tarkistusohjelma ja oikeinkirjoitusvirheiden, kirjoitusvirheiden korjausohjelma. Jos käyttäjä esimerkiksi kirjoittaa Googleen ”Missisaga”, palautetaan osumaluettelo sekä ”Showing results for mississauga”. Eli hakukysely palauttaa tuloksia, vaikka käyttäjän syötteessä olisi ylimääräisiä tai puuttuvia merkkejä tai muunlaisia kirjoitusvirheitä.
• Ohjelmistoa voidaan käyttää päällekkäisten tietueiden tarkistamiseen. Esimerkiksi jos asiakas on merkitty tietokantaan useaan kertaan eri ostoksilla, koska hänen nimensä on kirjoitettu eri tavoin (esim. Abigail Martin vs. Abigail Martinez), hänellä on uusi osoite tai hänen puhelinnumeronsa on syötetty virheellisesti.

Dedupeerauksesta puheen ollen, se ei välttämättä ole niin helppoa kuin miltä se kuulostaa, erityisesti jos tietueita on satoja tuhansia. Edes Expedia ei tee sitä sataprosenttisesti oikein:

Tässä postauksessa selitetään, mitä sumea merkkijonojen täsmäytys on yhdessä sen käyttötapausten kanssa, ja annetaan esimerkkejä Pythonin Fuzzywuzzy-kirjastoa käyttäen.

Kullakin hotellilla on oma nimikkeistö, jolla se nimeää huoneitaan, ja sama skenaario pätee myös online-matkailutoimistoihin (Online Travel Agency, OTA). Esimerkiksi yhtä huonetta samassa hotellissa Expedia kutsuu nimellä ”Studio, 1 King Bed with Sofa bed, Corner”, Booking.com voi pitää turvallisena näyttää huoneen yksinkertaisesti nimellä ”Corner King Studio”.

Tässä ei ole mitään väärää, mutta se voi johtaa sekaannukseen, kun haluamme vertailla huoneen hintaa OTA:iden välillä, tai kun yksi OTA haluaa varmistaa, että toinen OTA noudattaa hinnanpariteettisopimusta. Toisin sanoen, jotta voimme vertailla hintaa, meidän on varmistettava, että vertaamme omenoita omenoihin.

Yksi hintavertailusivustojen ja -sovellusten jatkuvasti turhauttavimmista ongelmista on yrittää selvittää, ovatko kaksi kohdetta (tai hotellihuonetta) samaa asiaa, automaattisesti.

Fuzzywuzzy on Python-kirjasto, joka käyttää Levenshteinin etäisyyttä laskeakseen sekvenssien väliset erot helppokäyttöisessä paketissa.

Luotuani demonstraation, luon oman aineistoni, eli otan samasta hotellikiinteistöstä huonetyypin Expedian sivuilta, sanotaan vaikka ”Sviitti, 1 kuninkaallinen sänky (salonki)”, ja vertaan sitä Booking.comin huonetyyppiin, joka on ”King Parlor Suite”. Pienellä kokemuksella useimmat ihmiset tietäisivät, että ne ovat sama asia. Tätä menetelmää noudattaen luon pienen tietokokonaisuuden, jossa on yli 100 huonetyyppiparia ja joka löytyy Githubista.

Testaamme tämän tietokokonaisuuden avulla, miten Fuzzywuzzy ajattelee. Toisin sanoen, käytämme Fuzzywuzzya sovittamaan tietueita kahden tietolähteen välillä.

import pandas as pddf = pd.read_csv('room_type.csv')
df.head(10)

Data-aineisto on luotu itse, joten se on hyvin puhdas.

Fuzzywuzzyssä on useita tapoja verrata kahta merkkijonoa, kokeillaan niitä yksi kerrallaan.

• ratio , vertaa koko merkkijonon samankaltaisuutta, järjestyksessä.

from fuzzywuzzy import fuzz
fuzz.ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')

Tämä kertoo, että parit ”Deluxe Room, 1 King Bed” ja ”Deluxe King Room” ovat noin 62 % samanlaisia.

fuzz.ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')

Parit ”Traditional Double Room, 2 Double Beds” ja ”Double Room with Two Double Beds” ovat noin 69 % samanlaisia.

fuzz.ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')

Pari ”Huone, 2 parisänkyä (19.-25. kerros)” ja ”Kahden parisängyn huone – Sijaintihuone (19.-25. kerros)” ovat noin 74% samoja.

Olen pettynyt näihin. Kävi ilmi, että naiivi lähestymistapa on aivan liian herkkä pienille eroille sanajärjestyksessä, puuttuville tai ylimääräisille sanoille ja muille vastaaville seikoille.

• partial_ratio , vertaa osittaista merkkijonojen samankaltaisuutta.

Käytämme edelleen samoja aineistopareja.

fuzz.partial_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')

fuzz.partial_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')

fuzz.partial_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')

Minun aineistossani osittaisten merkkijonojen vertailu ei tuota kokonaisuutena katsottuna parempia tuloksia. Jatketaan.

• token_sort_ratio , ei huomioi sanajärjestystä.

fuzz.token_sort_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')

fuzz.token_sort_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')

fuzz.token_sort_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')

Best toistaiseksi.

• token_set_ratio , ei huomioi päällekkäisiä sanoja. Se on samanlainen kuin token sort ratio, mutta hieman joustavampi.

fuzz.token_set_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')

fuzz.token_set_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')

fuzz.token_set_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')

Näyttää siltä, että token_set_ratio sopii parhaiten aineistooni. Tämän löydön perusteella päätin soveltaa token_set_ratio koko aineistooni.