Unstructured data pre-processing using Snowball language

Unstructured data pre-processing using Snowball language Předzpracování nestrukturovaných dat pomocí jazyka Snowball Bc. Pavel Řezníček, doc. Ing. František Dařena, PhD., Ústav informatiky, Provozně ekonomická fakulta, Mendelova univerzita v Brně, [email protected], [email protected] Abstrakt Práce se zabývá problémem předzpracování nestrukturovaných dat a jejich další modifikací. Po krátkém nastínění zkoumané problematiky popisuje její současný stav spolu s různými algoritmy pro stemming dat. Popisuje jazyk Snowball jako vhodný nástroj pro definici transformace a modifikace zdrojových dat, který je následně využit. V poslední části se práce zabývá vytvořeným programem, který automatizovaně řeší problém stemmingu, po jehož popisu následuje stručné zhodnocení výsledků.

Klíčová slova Nestrukturovaná data, stemming, Snowball, Perl

Abstract The work deals with the problem of pre-processing of unstructured data and further modifications. After a brief outline of examined issues describes the current state along with various algorithms used for stemming data. The work describes a language Snowball as a suitable tool for the definition of transformation and modification of source data, which is subsequently used. The last part of work deals with creating a program that automatically solves the problem of stemming and after description of a program follows a brief evaluation of results.

Key Words Unstructured data, stemming, Snowball, Perl

Úvod a cíl Při každodenní činnosti uživatelů na internetu a jejich interakci s webovým prohlížečem, vzniká obrovské množství dat, která v sobě ukrývají skryté a někdy velice zajímavé informace. Data jsou ukládána v nestrukturované podobě a pro jejich další zpracování a následné získání skrytých informací vzniká potřeba je nejdříve převést do reprezentace

vhodné pro určitý učící algoritmus a klasifikační úlohu, popřípadě data určitým způsobem předzpracovat. (Silva, Ribero, 2010). Jednou z nejjednodušších a nejčastěji používaných reprezentací znalostí, jež zároveň umožňuje snadno provádět algebraické operace, jsou vektory (Howland, Park, 2004). Vektorová reprezentace je také nejrozšířenější metodou pro modelování obsahu textových dokumentů. S dokumenty se pracuje v rámci vektorového prostoru, kde je každý dokument reprezentován jedním příznakovým vektorem. Dokument je obecně reprezentován frekvencí výskytu termů, jimž mohou být přiřazeny statistické váhy představující důležitost termů (Wang, Zhang, Vassileva, 2010; Zhang, Zhu, 2005). Tzv. bag-of-words reprezentace, kdy příznaky vektorů tvoří pouze originální slova z dokumentu, je nejprimitivnější reprezentací textového dokumentu. I když její použití vede k uspokojivým výsledkům, řada výzkumů se zaměřuje na hledání reprezentace poskytující výsledků lepších. Aby mohly být z dat pomocí algoritmů strojového učení získány určité znalosti, je potřeba provést jejich předzpracování. Tento článek v krátkosti popisuje možné metody předzpracování nestrukturovaných dat a představuje implementovaný program řešící jednu konkrétní metodu předzpracování dat. Cílem práce je vyvinout spustitelný program, který na zpracovávaná zdrojová data nejvhodnějším způsobem aplikuje stemmovací algoritmy a následně vytvoří kopie zdrojových dat, které po transformaci obsahují pouze kořeny původních slov. Tyto modifikované soubory budou v následující fázi dále zpracovávány a budou z nich získávány další informace.

Současný stav problematiky Pro potřeby předzpracování dokumentů je možné využít metodu extrakce termů nazývanou stemming. Za použití stemmingu vzniká z původního nový term tak, že dochází k odstranění částí slov, které vznikají jeho skloňováním nebo časováním. Například slova viewed, viewer či preview jsou tak transformována na stejný kořen view. Existuje několik typů algoritmů pro stemming, které se liší v přesnosti a schopnosti překonávat překážky vyskytující se v nestrukturovaných datech (Lovins, 1968):  Porterův algoritmus ‒ nejznámějším stemmovací algoritmus původně vyvinutým pro angličtinu, jenž se postupem času stal určitým standardem v oblasti stemmingu.  Vyhledávací algoritmy ‒ používají vyhledávání skloňovaných tvarů termů ve vyhledávací tabulce. Výhodou těchto algoritmů je jednoduchost a rychlost.

Nevýhodou je nutný výčet všech skloňovaných forem uvedený v tabulce, což způsobuje nepřesnosti při zpracování neznámých slov.  Produkční techniky ‒ vyhledávací tabulky jsou zde vytvářeny poloautomaticky a dokáží si lépe poradit s neznámými slovy.  Algoritmy pro odstraňování přípony (suffix-stripping) ‒ jejich součástí není vyhledávací tabulka, ale list pravidel, podle kterých algoritmus postupuje. Tento algoritmus je založen zejména na oddělování přípon termů a pro jeho použití nejsou nutné příliš veliké znalosti lingvistiky. Problémy s tímto algoritmem nastávají v případě, že kořen slova nelze získat pouze odstraněním přípony popřípadě předpony (např. nepravidelná anglická slovesa).  Stochastické

algoritmy

‒

využívají

k identifikaci

kořenového

tvaru

termu

pravděpodobnost a jsou trénovány pomocí tabulky kořenových tvarů, která je v průběhu zpracování ovlivňována a jejich pravděpodobnostní model je postupem času vyvíjen.  Hybridní přístupy ‒ k dosažení výsledků kombinují dva nebo více přístupů popsaných výše. Příkladem je kombinace vyhledávacích tabulek a odstraňování přípon, kde pokud není slovo ve vyhledávací tabulce, uplatní se algoritmus pro odstranění přípony.  Porovnávací algoritmy ‒ používají databázi stem slov, které nemusí být nutně validními slovy, ale spíše určitými běžnými podřetězci slov (např. „brows“ ve slově „browse“ a ve slově „browsing“). Většina algoritmů byla vytvořena pro zpracování anglického jazyka, a proto byl z důvodu potřeby zpracovávat nejen anglické texty, ale i texty dalších jazyků vyvinut, jako nadstavba Porterova algoritmu, jazyk Snowball umožňující vytvářet vlastní algoritmy pro stemming a pomocí těchto algoritmů předzpracovávat zdrojová data a získávat z nich další informace (TARTARUS, 2012). Na ÚI PEF MENDELU je již delší dobu ve vývoji aplikace s grafickým uživatelským rozhraním sloužící k předzpracování textových dat. Tato aplikace je vytvořena s využitím jazyka Perl a modulu Perl/Tk pro její GUI. Umožňuje uživateli vložit zdrojový soubor, zvolit název a umístění výstupního souboru, využívat funkce potřebné pro generování slovníku, transformaci dat do požadovaného tvaru, filtrování slov podle požadované délky, frekvence výskytu atd. Podoba aplikace a množství způsobů jak připravit textová data zatím nejsou konečné a stále se pracuje na jejím rozšiřování (Novák, Dařena, 2012).

Metodika Dosáhnout potřebné podoby dat lze různými způsoby a zejména z technologického hlediska se stal vhodným nástrojem pro předzpracování dat Lingua::Stem::Snowball jako jeden z modulů programovacího jazyka Perl určených ke zpracování a transformaci textových dat. Tento modul je XS modulem1 pro Snowball stemmery napsané v jazyce C. Umožňuje definovat vstupní kódování a jazyk, ve kterém jsou zpracovávaná data zapsána ‒ v současné době podporuje modul Snowball 15 světových jazyků. Pomocí již optimalizovaných metod ořezává ve velice krátkém čase (45 tisíc slov zpracuje za 0,6s)2 jednotlivá slova zdrojového textu na jejich kořenový tvar (CPAN, 2013).

Předzpracování dat Zdrojové texty obsahují v podstatě libovolné znaky. Tyto texty je tedy nejdříve potřeba vyčistit tak, aby v nich zbyla pouze slova, to znamená, je třeba z nich nejdříve odstranit veškeré html tagy a entity, interpunkci (tečky, čárky, vykřičníky atd.), a cokoliv, co nemůže být znakem slova.

Specifikace základního souboru dat Základním souborem dat je kolekce textových dokumentů ‒ recenzí zákazníků hotelů. Tyto recenze jsou rozděleny do adresářů podle jazyka, ve kterém jsou napsány. Data ve všech souborech recenzí jsou uspořádána způsobem, kde jeden řádek odpovídá předpisu “CTEXT“, kde C je třída dokumentu označující dokument např. jako pozitivní nebo negativní, je znak tabelátoru a TEXT je vlastní text recenze v kódování UTF‒8 jako posloupnost znaků zakončená znakem konce řádku.

Výsledky Výsledkem práce je program v jazyce Perl spustitelný z příkazové řádky, který umožňuje zpracovat obsah předaného souboru, transformovat jej a tento modifikovaný obsah uložit do nového souboru opatřeného příznakem o proběhlé transformaci jako součást jména nového souboru. V programu je zabudována kontrola podpory jazyků, které nabízí modul Lingua::Stem::Snowball a v případě, že dojde k pokusu o zpracování souborů v jazyce, který tento modul nepodporuje, se žádná transformace či modifikace na datech neprovádí.

1 2

Rozhraní, skrze které lze v jazyce Perl vyvolávat příkazy jazyka C Testováno s 3.2GHz Pentium 4, Perl 5.8.7, Lingua::Stem::Snowball 0.94

Pro větší uživatelskou přívětivost jsem do zpracovávajícího skriptu implementoval algoritmus, který prochází adresář zadaný jako vstupní parametr a podle názvů jednotlivých podadresářů, vytváří instance třídy Snowball s potřebnými parametry (zejména jazyk recenzí), na základě který probíhá následné ořezávání slov. Je však zároveň nutné dodržovat určitou hierarchii podadresářů znázorněnou na Obrázku 1.

Obrázek 1: vzorová struktura zpracovávaného adresáře Celkový čas potřebný ke zpracování všech souborů ve zvoleném adresáři je závislý jednak na výkonu stroje, na kterém je program spouštěn a také na velikosti zpracovávaných dat. V průběhu zpracování dat je na standartní výstup zobrazován průběh činnosti v podobě aktuálního procházeného adresáře a zpracovávaného souboru spolu s informativními hláškami o úspěšnosti zpracování (Obrázek 2).

Obrázek 2: výstup spuštěného programu

Závěr Výsledný program plní všechny požadavky, které na něj byly kladeny, a po důkladném otestování lze říci, že poskytuje požadované výsledky v akceptovatelných časových intervalech. Nutnost zařazovat zpracovávané soubory do definované hierarchické struktury je vykoupena ušetřeným časem při zpracování veškerých dat použitím pouze jediného příkazu.

Výsledná modifikovaná data jsou přehledně roztřízena a ihned připravena k dalšímu zpracování. Tento článek vznikl v rámci řešení projektu IGA 4/2013 Analýza vlivu předzpracování textových dokumentů na výsledky úloh text mining.

Zdroje CPAN.

Lingua-Stem-Snowball

[online].

2008

[cit.

2013-10-14].

Dostupné

z:

http://search.cpan.org/dist/Lingua-Stem-Snowball/lib/Lingua/Stem/Snowball.pm

Lovins, J. Development of a Stemming Algorithm. Mechanical Translation and Computational Linguistics 11. 1968, s. 22–31. Novák, Z., Dařena, F. Aplikace pro přípravu textových dat. [CD-ROM]. In PEFnet 2012. ISBN 978-80-7375-669-7.

Silva, C., Ribeiro, B. Inductive Inference for Large Scale Text Classification: Kernel Approaches and Techniques. Springer, 2010. ISBN 978-3-642-04533-2. TARTARUS. Snowball – Quick introduction [online]. 2012 [cit. 2013-10-15]. Dostupné z: http://snowball.tartarus.org/texts/quickintro.html

Wang, Y., Zhang, J., Vassileva, J. Towards Effective Recommendation of Social Data across Social Networking Sites. In: Dicheva, D., Dochev, D. (eds.) Artificial Intelligence: Methodology, Systems, and Applications. Springer, 2010, s. 61--70.

Zhang, X., Zhu, X. Extended Bi-gram Features in Text Categorization. In: Proceedings of IbPRIA (2)'2005, 2005, s. 379--386.