Jak párujeme nabídky k hotelům, aneb není Kleopatra jako Kleopatra

Ve Skrzu pracujeme s velkým množstvím nabídek — dnes jde většinou o pobyty a zájezdy, ale máme také vouchery do aquaparků, restaurací apod. Většina nabídek patří k nějakému hotelu, penzionu, kempu apod.
Databázi hotelů máme vlastní — plníme ji v základu z dat, která dostáváme o nabídkách.

Zajímají nás jak základní informace (název, poloha, fotografie), tak i další parametry (bezbariérový přístup, parkoviště, ale také to, jestli je ubytování vhodné pro rodiny s dětmi). Data u nabídek ale nejsou vždy stejná ani stejně kvalitní — pocházejí z různých zdrojů (na Skrzu se nachází nabídky od desítek cestovních kanceláří, slevových serverů i bookingových platforem), část dat může chybět nebo být nepřesná. Např. GPS souřadnice jsou často stovky metrů i kilometry vedle. Údaje se také mohou lišit napříč zdroji — jedna cestovní kancelář může hotel nazývat “Royal Hotel Grand and Spa” a druhá “Grand Hotel Royal”, i když se jedná o to samé místo. Na druhou stranu existují místa, kde stojí hned několik hotelů s podobným názvem vedle sebe.

Je pro nás (a hlavně pro naše uživatele) zásadní mít údaje o hotelech co nepřesnější a nabídky přiřazené k hotelům správně — když uživatel hledá dovolenou v hotelu s bazénem a saunou a my mu ukážeme pobyt, který je ve skutečnosti v kempu se společnou sprchou, asi už příště dovolenou přes naše stránky hledat nebude.
Jak k hotelům přiřazujeme nabídky?
O to se stará program, který se jmenuje — dost nudně, víme — MerchantTask (protože interně hotely/apartmány/kempy… označujeme termínem “merchant”). Z každé nové nabídky si vytáhne data potřebná pro porovnání s existujícími hotely (tzv. prototyp) a pak hledá ten “nejpodobnější” existující hotel.
Celková podobnost mezi prototypem a konkrétním hotelem je vyjádřena jedním číslem (říkejme mu P), které vznikne součtem dílčích skóre za podobnosti jednotlivých atributů (adresy, názvu, …), zjednodušeně:

Hotel s nejvyšším P vyhrává. Aby se k němu nabídka přiřadila, tak ale zároveň musí podobnost dosáhnout nějaké minimální hodnoty —hotel musí být nejen “nejpodobnější”, ale taky “dostatečně podobný”, což není to samé.

Dílčí podobnosti se samozřejmě počítají každá trochu jinak, v tomhle článku popíšeme jen dvě nejdůležitější.
Podobnost názvů
Data o nabídce obsahují mimo jiné název hotelu, restaurace apod. Stejný název hotelu je jeden z nejlepších indikátorů shody, ale jak už jsme zmínili v úvodu, stejný hotel se v datech z různých zdrojů může jmenovat odlišně. Prosté porovnání názvů proto nestačí. Nepomůže ani např. editační vzdálenost, protože slova jsou v názvech často prohozená (např. pro řetězce “Kleopatra Golden Sun” a “Golden Sun Kleopatra” je editační vzdálenost 18, přitom jde pravděpodobně o ten samý hotel).
Řešením, které jsme zvolili, je tokenizace názvů — zjednodušeně rozdělení názvů na jednotlivá slova (tokeny) a hledání shody pomocí nich. Před tokenizací se název také normalizuje — převede se na malá písmena, odstraní se některé znaky apod.

Další věc, kterou je třeba řešit, jsou stop slova, tzn. slova, která nemají pro zjištění podobnosti žádný význam — např. pro porovnání názvů “Nova Beach Hotel”, “Hotel Kleopatra Beach” a “Nova Beach” je slovo “hotel” prakticky zbytečné. Takže máme interní seznam stop slov (který průběžně aktualizujeme) a pokud token odpovídá stop slovu, tak ho MerchantTask zahazuje.

Kromě vyloženě bezvýznamových slov je také důležité, jak často se daný token vyskytuje napříč všemi existujícími hotely — slova jako “royal”, “sun” nebo “beach” jsou v názvech hotelů velmi častá a skóre za shodu na těchto slovech by tomu mělo odpovídat — mělo by být nižší. My jsme zvolili takové řešení, že skóre každého tokenu odpovídá 1 / N, kde N je počet hotelů s daným tokenem v názvu, tzn. čím častější je daný token, tím menší má hodnotu.

Někdy se také stane, že název hotelu je v různých zdrojích (v datech od různých cestovek) výrazně jiný, ale my víme, že jde o ten samý hotel. Třeba “Oz-Can Hotel” a “Özcan”. Jak tohle řešíme? To si necháme pro sebe, nemůžeme prozradit úplně všechno :)
Celý základní algoritmus vypadá nějak takhle:
- Normalizace + tokenizace názvu
- Odstranění stop slov
- Výpočet skóre za každý token
- Výpočet celkového skóre (jednoduše suma všech dílčích skóre)
Reálný algoritmus je trochu složitější, např. ještě řešíme zvlášť přesnou shodu názvu, skóre za každý token neodpovídá úplně přesně 1/N, bereme v potaz i částečnou shodu tokenu… Ale princip je stejný.
Podobnost na základě GPS souřadnic
Nabídky mají (často, ne vždy) u sebe i GPS souřadnice, které by měly odpovídat souřadnicím hotelu. Takže máme dvoje GPS souřadnice (nabídky a existujícího hotelu) a potřebujeme zjistit, jak jsou si “podobné”, tzn. jak blízko jsou u sebe — jednoduché, že? Ne tak docela.
Zaprvé je potřeba převést vzdálenost (čím větší, tím horší) na skóre (čím větší, tím lepší). Tady stačí zvolit vhodnou funkci — někdy se jí říká decay funkce — která má v nějakém bodě maximum a definuje, jak klesá hodnota se vzdáleností od tohoto bodu.

A zadruhé je třeba vzít v potaz přesnost GPS souřadnic. Když ve zdrojových datech chybí GPS souřadnice, ale je tam adresa, můžeme (pomocí Geocoding API od Googlu) odpovídající GPS polohu zjistit. Pokud je ale adresa např. “Spojené arabské emiráty, Abú Dhabí”, tak bude i vrácená poloha velmi nepřesná (bude nejspíš odpovídat středu Abú Dhabí). Google naštěstí vrací s polohou i přesnost. My to pak v naší decay funkci zohledňujeme — pro nižší přesnost je maximální skóre nižší, ale zase se vzdáleností klesá pomaleji (pokud je přesnost GPS na úrovni konkrétního domu, je vzdálenost 100 m hodně, pokud je ale na úrovni města, je to prakticky zanedbatelné).

Je toho víc
O MerchantTasku by se toho dalo napsat mnohem víc — přiřazovat se dá i podle jiných věcí, než je název a poloha, merchanti se nejen přiřazují, ale musí se i nějak vytvářet, některá data o merchantech u nabídek prostě nejsou a musíme je získávat odjinud… ale to si necháme na někdy příště.
Stroj nezvládne všechno
Bylo by hezké, kdyby MerchantTask pracoval vždycky správně, ale samozřejmě to tak není (a asi to tak nikdy nebude). Jeho práci pravidelně kontroluje a opravuje člověk. Až když se některé chyby objevují opakovaně a často, začneme řešit úpravu algoritmu. Je to totiž většinou něco za něco — úprava někde pomůže, ale jinde může zase uškodit. Takže taky každou změnu pečlivě testujeme na reprezentativním vzorku dat. Může se stát, že změna nepřinese významnější celkové zlepšení, takže ji do ostrého provozu nenasadíme a zahodíme.
Co nás čeká dál?
MerchantTask prošel v posledním roce několika iteracemi vylepšování a podařilo se nám snížit chybovost přiřazování z 20 % na 4 %, ale to neznamená, že by nebylo co zlepšovat. Za chvíli budeme mít např. problém s výkonem — počet merchantů pořád roste a kvůli rychlosti přiřazování se vždycky všichni natáhnou do paměti, což není dlouhodobě udržitelné. Přiřazení nabídek podle názvu taky pořád nefunguje tak dobře, jak bychom si představovali (už máme nápady na zlepšení).
Řešíte podobný problém? Děláte to úplně jinak? Máme všechno zahodit a používat machine learning? Napište nám to do komentářů nebo na twitter.
A pokud by někoho takové věci bavily vymýšlet a zlepšovat, tak neustále hledáme nové parťáky do týmu.
