Fuzzy matching. Analiza podobieństwa tekstu

Jak ocenić stopień podobieństwa dwóch zmiennych tekstowych? W jaki sposób zakodować spontanicznie udzielane odpowiedzi w pytaniach bez czytania każdej z nich, interpretowania, a następnie ręcznego przypisywania jej do właściwej kategorii?

Pomocny w rozwiązaniu powyższych problemów jest fuzzy maching. Technika ta, pozwala na porównanie dwóch ciągów znaków i określenie na ile są podobne za pomocą miar podobieństwa. W następnej kolejności najbardziej zbieżne ciągi tekstowe mogą zostać dopasowane lub połączone.

Wszędzie tam, gdzie dopuszczamy możliwość ręcznego wpisania wartości bez wcześniej zdefiniowanego słownika (np. nazwy klientów, produktów, marek) mogą pojawiać się błędy, takie jak różnorodna interpretacja pisowni, literówki czy „zwykłe” błędy ortograficzne. Ręczne przygotowanie takich danych z jednej strony związane jest nierzadko z niewspółmiernym nakładem czasu, z drugiej strony obarczone jest ryzykiem zbytniej uznaniowości w ocenie. W tych przypadkach fuzzy maching pozwala skrócić czas pracy z danymi tekstowymi.

Problem kodowania na podstawie dokładnego dopasowania

Na potrzeby zaprezentowania fuzzy machingu wyobraźmy sobie taką sytuację: firma zajmująca się sprzedażą burgerów poprosiła klientów o opinie na temat spożywanych produktów. Respondenci wpisywali nazwy kanapek w otwartym polu, bez kafeterii odpowiedzi, ponieważ burgerownia chciała poznać również zasięg i rozpoznawalność poszczególnych marek. Niestety wymyślne nazwy ze zamerykanizowaną pisownią przyniosły efekt w postaci dość dowolnej interpretacji nazw produktów.

Respondenci mogli spożywać i oceniać 5 burgerów: VEGETA (wegetariański), GLUTENFREE (bezglutenowy), SPICYBEEF (pikantna wołowina), MAXIBURGER (duża bułka z dużą ilością mięsa), BOOLADRWALA (zapewne jeszcze większa bułka, z jeszcze większą ilością mięsa).

Próba przypisania nazw burgerów do odpowiedzi respondentów na podstawie wyszukiwania wystąpienia dokładnych nazw przyniosła umiarkowane rezultaty. Efekty kodowania opartego o dokładne dopasowanie nazw zostały zamieszczone powyżej. Nazwy zostały wcześniej ujednolicone pod kątem wielkości liter. Usunięte zostały również ewentualne polskie znaki, znaki przestankowe czy spacje. Mimo to udało się wyłapać tylko niewielką część odpowiedzi.

Przyjrzyjmy się burgerowi wegetariańskiemu. Respondenci wpisali tę nazwę na 4 różne sposoby. Mamy więc następujące odmiany: VEGETTA, WEGETA, wreszcie VEGEBURGER. O ile ten ostatni wpis może być problematyczny, o tyle w przypadku dwóch poprzednich mamy do czynienia raczej z pomyłką w nazwie. Z podobną sytuacją spotkamy się w również w przypadku pozostałych bułek.

Lepszym rozwiązaniem wydaje się zakodowanie odpowiedzi respondentów na podstawie stopnia podobieństwa odpowiedzi do rzeczywistych nazw produktów, czyli zastosowanie dopasowania rozproszonego (fuzzy maching). Należałoby więc obliczyć podobieństwo podanej nazwy do każdej z nazw burgerów, przeanalizować uzyskane wartości i na tej podstawie przyjąć wartość progową, powyżej której uznamy, że nazwy pasują do siebie a rozbieżności są jedynie efektem pomyłek.

Przygotowanie danych do fuzzy matchingu

Zanim jednak wykorzystamy do tego celu fuzzy maching, musimy odpowiednio przygotować dane. W naszym przypadku konieczne jest wykonanie restrukturyzacji zbioru danych do postaci, w której odpowiedzi respondentów mogą zostać porównane z każdą poprawną nazwą produktu. Potrzebujemy więc przekształcić zbiór w taki sposób, aby uzyskać dwie zmienne – jedną z nazwą rzeczywistą i drugą z nazwą do której porównujemy odpowiedzi. Przekształcenie danych jak i fuzzy maching przeprowadzimy wykorzystując do tego oprogramowanie PS IMAGO PRO. W programie wybieramy menu [Dane -> Restrukturyzuj Dane -> Wybrane zmienne przekształcić w obserwacje].

W rezultacie powstanie zbiór, w którym każdy przypadek zostanie zmultiplikowany tyle razy, ile występuje zmiennych zamienianych w obserwacje. Przypadek zostanie utworzony dla każdej odpowiedzi skrzyżowanej z każdą z możliwych do porównania nazw burgerów.

Powyżej zamieściłem fragment nowoutworzonego zbioru danych. Odpowiedzią pierwszego respondenta był BEEFBURGER. Przypadek ten został sztucznie rozmnożony tak, aby móc ocenić stopień podobieństwa odpowiedzi (wartość zmiennej burger) z prawidłowymi nazwami (wartość zmiennej produkt).

Dopasowanie rozszerzone w praktyce

Jak obliczyć podobieństwo pomiędzy dwoma tekstami? Wszystko zależy od przyjętej miary odległości. Może to być liczba działań edycyjnych, które należy wykonać, aby dwa teksty stały się identyczne (wstawienia, usunięcia, zamiany znaków), możemy też porównywać tekst znak po znaku i obliczyć liczbę znaków, które nie są takie same.

W PS IMAGO PRO znajduje się procedura pozwalająca na obliczenie miar podobieństwa pomiędzy zmiennymi tekstowymi. Dostępna jest ona w zakładce [Predictive Solutions -> Analiza -> Porównaj tekst]. Okno kreatora procedury zostało zamieszczone poniżej. Omówmy pokrótce możliwości, które ona oferuje.

Procedura [Porównaj tekst] pozwala na obliczenie specjalnych miar dystansu pomiędzy zmiennymi tekstowymi oraz zapis wyników w postaci oceny albo podobieństwa. Dostępne jest 7 miar dedykowanych zmiennym tekstowym:

• Dystans Jaro: liczba zgodnych znaków
• Dystans Jaro z poprawką Winklera: liczba zgodnych znaków z bonusem przyznawany za zgodny prefiks. Kreator procedury pozwala na zdefiniowanie długości prefiksu (max 4 znaki) oraz stopnia korekty (max 0,25)
• Dystans Hamminga: liczba znaków niezgodnych, ale znaki porównujemy na poszczególnych pozycjach w tekście (od początku znak po znaku)
• Dystans Levenshteina: liczba poprawek edycyjnych, jakich należy dokonać, aby dwa teksty stały się identyczne (wstawienie, usunięcie, zamiana)
• Dystans Levenshteina z poprawką na transpozycje znaków (Optimal String Alignment – OSA-Levenshtein): dystans Levenshteina, ale przestawienie kolejności dwóch znaków liczone jest za 1 działanie
• Dystans Needlemana-Wunscha: różnica pomiędzy sumą nagród za zgodne znaki a karami za niezgodności lub luki. Wagi dla nagród oraz kar definiujemy w opcjach procedury.
• Najdłuższy wspólny ciąg znaków (Longest Common Substring): długość najdłuższego wspólnego ciągu znaków w porównywanych tekstach

Procedura pozwala na zapisanie oceny dla każdej z wybranych miar oraz podobieństwa, które jest unormowaną wartością od 0 (teksty zupełnie niezgodne) do 1 (teksty identyczne). Sposób obliczania podobieństwa zależy od sposobu obliczania oceny. Interpretacja wartości poszczególnych miar, które możemy wykorzystać w fuzzy machingu została opisana w punktach powyżej.

W tym przykładzie najlepszym sposobem porównania będzie obliczenie dystansu oraz podobieństwa na podstawie miary OSA-Levenshtein. Do zbioru danych zostały dodane 2 nowe zmienne: osa_scr (ocena) oraz osa_sim (podobieństwo). Przeanalizujmy poniższy przykład.

Pierwszy przypadek to prawidłowo wpisana nazwa: dystans wynosi 0 a podobieństwo 1. Tylko w tym przypadku reguła oparta na dokładnym dopasowaniu zidentyfikowała wystąpienia nazwy produktu w odpowiedzi. W drugim wierszu mamy do czynienia z błędem polegającym na przestawieniu liter W oraz R. Dystans wynosi więc 1 (jedna zamiana), a podobieństwo to 0,909. Przypadek trzeci różni się od nazwy produktu dwiema literami (U zamiast OO), stąd też dystans wynosi 2, a podobieństwo 0,818. W czwartym przypadku powinniśmy zmienić 4 litery oraz wstawić 1 – więc należy podjąć 5 działań edycyjnych, a podobieństwo jest już dużo niższe (0,583). Piąty przypadek – BEEFBURGER jest już bardzo daleki od porównywanej nazwy.

W tym momencie stajemy przed najważniejszą decyzją – jak określić próg podobieństwa, powyżej którego odpowiedzi zostaną uznane za odmiany tej samej nazwy, a poniżej którego stwierdzamy, że odpowiedzi respondentów dotyczą innych produktów. Wartości podobieństwa powyżej tego progu kodujemy następnie jako 1 (czyli uznajemy, że mamy do czynienia z odmianą tej samej nazwy) lub 0 (inne nazwy). Warto pamiętać, że przyjęcie zbyt wysokiego progu może spowodować nieprawidłowe odrzucanie teoretycznie prawidłowych nazw, natomiast przyjęcie zbyt niskiego spowoduje obecność dużej ilości szumu i nieprawidłowości wśród zakodowanych wartości. Warto przetestować różne wartości progowe i ocenić efekty – na dużej próbie można skorzystać z losowania.

Po analizie zdecydowałem się przyjąć próg podobieństwa na poziomie 0,8.

Porównajmy teraz uzyskane wyniki z tymi, które zostały zaprezentowane na początku niniejszego tekstu. W tym celu musimy przekształcić nasz roboczy zbiór za pomocą wykorzystywanej już procedury restrukturyzacji zbioru danych, ale tym razem w odwrotnym kierunku – przekształcić zmultiplikowane obserwacje w pojedyncze przypadki.

W celu zwiększenia czytelności usunąłem ze zbioru zerowe wartości.

Kodowanie oparte o podobieństwo tekstu, a nie o dokładne dopasowanie zdecydowanie zwiększyło liczbę poprawnie zidentyfikowanych odpowiedzi. Udało się poprawnie wychwycić po 2 lub 3 nazwy produktów. Wartość 1 dla danej nazwy w danym wierszu oznacza, że na podstawie przyjętej wartości progowej (0,8) nazwa podana przez respondenta została uznana za odmianę poprawnej nazwy produktu (różnice są efektem nieintencjonalnych pomyłek). Zazwyczaj różnica dotyczyła jednej, opcjonalnie dwóch liter w nazwie. Jak widać, dopasowanie rozproszone okazało się pomocne przy opracowaniu wyników badania.

Oczywiście, analizując mechanicznie tego rodzaju dane, nie unikniemy pewnych rozbieżności. Przykładowo odpowiedź SPAJSIBIF (wiersz 14), choć można ją potraktować jako fonetyczną wersję burgera SPICYBEEF, nie została sklasyfikowana jako odmiana nazwy produktu. W takich przypadkach konieczne byłoby zastosowanie zaawansowanych algorytmów opartych o fonetyczne dopasowanie tekstu, lub po prostu zakodowanie tej wartość ręcznie.

PS IMAGO PRO pozwala użytkownikowi na pogłębioną analizę porównawczą zmiennych tekstowych. Możliwość oceny stopnia zbieżności dwóch ciągów tekstowych otwiera przed analitykami dużo nowych możliwości w zakresie analizy pytań otwartych, czy komentarzy zamieszczonych w kwestionariuszach lub bazach danych. Fuzzy maching pozwala skrócić czas potrzebny na wyszukiwanie odmian nazw klientów lub produktów, wyszukiwać poprawki w tekście i ocenić liczbę ewentualnych różnic i zmian.