Vysoká škola ekonomická v Praze Fakulta informatiky a statistiky

Vysoká škola ekonomická v Praze Fakulta informatiky a statistiky

DIPLOMOVÁ PRÁCE

2012

Bc. Aleš Pouzar

Vysoká škola ekonomická v Praze Fakulta informatiky a statistiky

DIPLOMOVÁ PRÁCE

Extrakce strukturovaných dat z českého webu s využitím extrakčních ontologií

Autor: Bc. Aleš Pouzar Katedra: Katedra informačního a znalostního inženýrství Obor: Znalostní technologie Vedoucí práce: Doc. Ing. Vojtěch Svátek, Dr.

Praha 2012

Prohlášení Prohlašuji, že jsem diplomovou práci na téma Extrakce strukturovaných dat z českého webu s využitím extrakčních ontologií vypracoval samostatně. Použitou literaturu a další podkladové materiály uvádím v přiloženém seznamu literatury. V Praze dne 27. června 2012

................................... Bc. Aleš Pouzar

iv

Poděkování Rád bych poděkoval vedoucímu mé práce Vojtěchu Svátkovi za rady a čas, po který se mi věnoval, ale i za možnost zapojit se do dalších, pro mě zajímavých projektů. Velký dík patří Martinu Labskému za jeho trpělivé zodpovídání dotazů ohledně extrakčního systému Ex i za obecné rady ohledně extrakce informací. Dále bych rád poděkoval firmě Dain s.r.o. za poskytnutí dat k pracovním nabídkám a vůbec za inspiraci věnovat se této oblasti. Největší poděkování pak patří mým rodičům za jejich nekonečnou podporu po celou dobu mého studia a Simoně za její obdivuhodnou trpělivost.

v

a

Abstrakt Předkládaná práce se zabývá úlohou automatické extrakce informací z HTML dokumentů ve dvou vybraných doménách. Ze stránek e-shopů jsou extrahovány nabídky notebooků a z webových prezentací firem volně publikované pracovní nabídky. Výsledkem extrakčního procesu jsou strukturovaná data uspořádaná do záznamů, ve kterých je každému údaji přiřazena odpovídající sémantická značka. Pro realizaci úlohy byl vybrán extrakční systém Ex, který kombinuje dva typy extrakčních znalostí: ručně zadaná pravidla a supervizované algoritmy strojového učení. Díky expertní znalosti v podobě extrakčních pravidel lze účinně kompenzovat nedostatek trénovacích dat. Pravidla jsou přitom nezávislá na konkrétní formátovací struktuře a jeden extrakční model je tak možné využít pro heterogenní množinu dokumentů. Dosažená úspěšnost v extrakci nabídek notebooků ukázala, že by extrakční ontologie, popisující jeden nebo několik málo typů produktů, mohla být úspěšně využita v kombinaci s metodami pro indukci wrapperů a tím automaticky extrahovat nabídky všech typů produktů na úrovni webu.

Klíčová slova: extrakce informací, automatická sémantická anotace, extrakční ontologie, strojové učení, rozpoznávání pojmenovaných entit, dolování dat z webu

Abstract The presented thesis deals with the task of automatic information extraction from HTML documents for two selected domains. Laptop offers are extracted from e-shops and free-published job offerings are extracted from company sites. The extraction process outputs structured data of high granularity grouped into data records, in which corresponding semantic label is assigned to each data item. The task was performed using the extraction system Ex, which combines two approaches: manually written rules and supervised machine learning algorithms. Due to the expert knowledge in the form of extraction rules the lack of training data could be overcome. The rules are independent of the specific formatting structure so that one extraction model could be used for heterogeneous set of documents. The achieved success of the extraction process in the case of laptop offers showed that extraction ontology describing one or a few product types could be combined with wrapper induction methods to automatically extract all product type offers on a web scale with minimum human effort.

Keywords: information extraction, automatic semantic annotation, extraction ontologies, machine learning, named entity recognition, web content mining

vi

Obsah Seznam obrázků

ix

Seznam tabulek

xi

1. Úvod 1.1. Motivace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Cíle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Struktura práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 3 4

2. Extrakce informací z webu 2.1. Typy dokumentů . . . . . . . . . . . . . . . . . 2.2. Typy úloh a využití . . . . . . . . . . . . . . . 2.3. Přehled přístupů . . . . . . . . . . . . . . . . . 2.3.1. Přístup využívající lingvistické techniky 2.3.2. Přístup založený na ontologiích . . . . . 2.3.3. Wrapperový přístup . . . . . . . . . . . 2.4. Přehled metod . . . . . . . . . . . . . . . . . . 2.4.1. Skryté Markovovy modely . . . . . . . . 2.4.2. Podmíněná náhodná pole . . . . . . . . 2.4.3. Porovnávací techniky . . . . . . . . . . . 2.5. Extrakční systémy . . . . . . . . . . . . . . . . 2.6. Metody vyhodnocení . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

5 6 7 9 10 12 12 13 13 16 18 20 22

3. Systém Ex 3.1. Popis systému . . . . . . . 3.2. Anotace a vyhodnocení . 3.3. Nástroj CRF++ . . . . . 3.3.1. Příznaky . . . . . 3.3.2. Možnosti nastavení

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

25 25 27 27 28 30

. . . . . . . . .

31 32 34 36 37 38 40 41 42 43

. . . . . . . . . . . . . . . . . . . . . . . . algoritmu

4. Extrakce produktových nabídek 4.1. Popis domény . . . . . . . . . . 4.2. Dataset . . . . . . . . . . . . . 4.3. Klíčové otázky . . . . . . . . . 4.4. Vytváření extrakční ontologie . 4.4.1. Specifikace atributů . . 4.4.2. Koreferenční rozhodnutí 4.4.3. Seskupování atributů do 4.5. Trénování CRF modelu . . . . 4.6. Vyhodnocení . . . . . . . . . .

. . . . .

. . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . instancí . . . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

vii

Obsah 4.6.1. Extrakce hodnot atributů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6.2. Extrakce instancí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. Extrakce pracovních nabídek 5.1. Popis domény . . . . . . . . . . 5.2. Dataset a ruční anotace . . . . 5.3. Klíčové otázky . . . . . . . . . 5.4. Vytváření extrakční ontologie . 5.4.1. Slovníky . . . . . . . . . 5.4.2. Název pracovní pozice . 5.4.3. Seskupování atributů do 5.5. Trénování CRF modelu . . . . 5.6. Vyhodnocení . . . . . . . . . .

43 44

. . . . . . . . .

47 47 49 50 51 52 54 55 56 57

6. Závěr 6.1. Shrnutí provedených experimentů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Využití extrakčních ontologií v doméně produktových nabídek . . . . . . . . . . . . . . 6.3. Zhodnocení cílů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61 61 62 63

Literatura

66

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . instancí . . . . . . . . . .

. . . . . . . . .

A. Výsledkové tabulky

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

I

B. Ukázky výstupu

V

viii

Seznam obrázků 2.1. Příklad instance šablony Pracovní nabídka. . . . . . . . . . . . . . . . . . . .

8

2.2. Topologie konkrétního HMM modelu. . . . . . . . . . . . . . . . . . . . . . .

14

2.3. HMM model v čase. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.4. Grafická struktura CRF modelu. X odpovídá pozorováním (slovům v dokumentu) a veličina Y stavům (značkám). . . . . . . . . . . . . . . . . . . . . .

17

2.5. Algoritmus MDR a porovnávání stromů. . . . . . . . . . . . . . . . . . . . . .

20

2.6. Vilainovy metriky. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.1. Ukázka části extrakční ontologie. . . . . . . . . . . . . . . . . . . . . . . . . .

27

4.1. Produktový katalog. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

4.2. Výčet parametrů notebooku bez kontextu. . . . . . . . . . . . . . . . . . . . .

34

4.3. Schéma třídy Nabídka notebooku. . . . . . . . . . . . . . . . . . . . . . . . .

38

5.1. Částečně strukturovaná pracovní nabídka. . . . . . . . . . . . . . . . . . . . .

48

5.2. Schéma třídy Pracovní nabídka. . . . . . . . . . . . . . . . . . . . . . . . . . .

52

5.3. Příklad pracovní nabídky s vizuálně odděleným názvem pracovní pozice. . . .

55

B.1. Extrakční ontologie pro pracovní nabídky byla aplikována na dataset čítající více než 9 600 dokumentů, na výstupu bylo přes 12 600 extrahovaných pracovních nabídek. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

IX

ix

Seznam tabulek 2.1. Výstup morfologické analýzy. . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

3.1. Trénovací data pro algoritmus CRF++. . . . . . . . . . . . . . . . . . . . . .

28

4.1. Základní údaje o datasetu e-shopů. . . . . . . . . . . . . . . . . . . . . . . . .

35

4.2. Nabídka notebooků – extrahované typy informací. . . . . . . . . . . . . . . .

35

4.3. Míra úspěšnosti extrakce atributů pro nabídky notebooků (trénovací data). .

44

4.4. Nabídky notebooků: úspěšnost seskupování atributů do instancí. . . . . . . .

45

5.1. Pracovní nabídky – extrahované typy informací. . . . . . . . . . . . . . . . . .

49

5.2. Základní údaje o datasetu firemních stránek. . . . . . . . . . . . . . . . . . .

50

5.3. Vyhodnocení atributů pro pracovní nabídky (trénovací data). . . . . . . . . .

58

5.4. Vyhodnocení atributů pro pracovní nabídky (testovací data). . . . . . . . . .

58

5.5. Pracovní nabídky: úspěšnost seskupování atributů do instancí. . . . . . . . .

59

A.1. Míra úspěšnosti extrakce atributů pro nabídky notebooků (trénovací data). .

II

A.2. Míra úspěšnosti extrakce atributů pro nabídky notebooků (trénovací data). .

III

xi

1

Kapitola 1.

Úvod

Ačkoliv množství volně dostupných a užitečných informací na Internetu neustále roste, jejich nalezení se stává paradoxně obtížnější a nákladnější. Současný způsob vyhledávání informací pomocí klíčových slov, kterými uživatel definuje svou informační potřebu, umožňuje zjistit přítomnost určitého termínu v dokumentu. To ale ještě nezaručuje, že se v něm nalézá požadovaná informace. Příčin je většinou více, ať už mnohoznačnost (dvě různé entity reálného světa jsou v daném jazyce často popsány stejným výrazem) nebo prostě fakt, že každá entita (objekt, informace) se může vyskytovat v nejrůznějších souvislostech a vztazích s jinými entitami1 . Možnosti dnešního vyhledávání jsou dostačující v případě, kdy uživatel hledá libovolné články (dokumenty) na určité téma, o kterém si chce něco přečíst (jinak řečeno, jeho informační potřeba je široce vymezená). Pokud naopak uživatel hledá velmi specifickou (konkrétní) informaci, je nucen každý nalezený dokument, který je systémem označen za relevantní, pročíst a požadovanou informaci v něm vyhledat (pokud se tam nachází). Tento způsob náročného (a ne vždy úspěšného) vyhledávání je v rozporu s obecným požadavkem na rychlé a včasné informace, který je v dnešním světě příznačný. Sofistikovanější a pohodlnější vyhledávání informací naráží na stávající reprezentaci dat na webu (nejčastěji v podobě HTML dokumentů), která definuje pouze uspořádání a vzhled jednotlivých částí textu. Struktura těchto dokumentů je tak orientována výhradně na prezentaci informací pro koncového uživatele. Co je lidmi vnímáno jako smysluplný text (či obrázek), jsou pro stroje nicneříkající řetězce znaků. Vynořila se přirozená snaha explicitně přiřadit k jednotlivým fragmentům textu uvnitř dokumentu odpovídající význam (samovysvětlující popis) 2 a to ve standardizované formě, která by byla strojově zpracovatelná3 . Prosazení tohoto konceptu, známého pod pojmem sémantický web, ale závisí rovněž na tom, jak rychle, úspěšně a s jakými náklady lze využít existující nestrukturovaná data, která obsahují množství užitečných informací. Metody extrakce informací, které umožňují v dokumentech identifikovat (a následně sémanticky anotovat) předem specifikované typy událostí, entit či relací (resp. 1

Pořadí výsledků vyhledávání je rovněž ovlivněno hojně používanými optimalizačními SEO technikami. Nebo-li metadata, která definují význam („sémantiku“) dat. 3 Tj. ve strojově srozumitelném jazyce. 2

1

Úvod

údaje popisující určité události nebo entity), provádí zmíněné kroky „čtení dokumentů“ a „výběru relevantních informací“ za uživatele. Takto extrahovaná data mají velký význam již nyní, přestože jsou využívána pouze v koncových aplikacích bez jejich vzájemného propojení, které by umožnilo zodpovídat specifické dotazy napříč doménami (na „globální“ úrovni). V současné době jsou vedle univerzálních vyhledávacích systémů jako Google populární i další vyhledávací služby, které se zaměřují na data určitého typu – ve více či méně strukturované podobě – které získavají od uživatelů (klientů). Narozdíl od výše uvedených vyhledávačů umožňují zodpovídat specifické dotazy, nepokrývají ale zdaleka všechen relevantní obsah, který se na webu nachází. Příklady takových služeb jsou portály zaměřené na komparativní nakupování nebo pracovní portály pro hledání volných pracovních míst. Možnosti vyhledávání pak záleží na samotné kvalitě (strukturovanosti) dat a počtu typů údajů. Objevují se i tzv. agregátory zdrojů, které získávají data určitého typu automaticky z několika primárních zdrojů. Podle povahy dat je pak uživateli předložen konečný obsah (výsledek) nebo výsledky vyhledávání na odpovídajících stránkách (tj. formou odkazů na primární zdroje). Dobrovolné poskytování dat veřejné povahy ve strukturované podobě je zde rozhodně největší překážkou – ne každý je ochotný potřebná data poskytovat, příp. neví jak nebo k tomu nemá prostředky. Předkládaná práce řeší konkrétní úlohy ve dvou vybraných doménách, jejichž cílem je extrahovat a sémanticky označkovat informace nalezené v HTML dokumentech. Obě úlohy jsou primárně zaměřeny na využití dat ve zmíněných specializovaných vyhledávačích, použité metody extrakce informací lze ale využít i v mnoha dalších scénářích, které jsou relevantní k výše definovanému problému. První úloha se zabývá extrakcí strukturovaných dat o nabídkách notebooků ze stránek e-shopů. Extrahovány jsou jednotlivé parametry výrobku včetně informací o nabídce jako je cena nebo dostupnost. Druhá úloha se zaměřuje na získání informací z volně publikovaných pracovních nabídek na stránkách firem. Obě úlohy jsou omezeny pouze na český web a tedy i na český jazyk.

1.1. Motivace Extrakce informací je prostřední a zároveň nejkritičtější článek celého procesu – prvním krokem je získání dostatečně obsáhlé množiny webových dokumentů, úkolem finální fáze je spárovat nabídky týkající se identických produktů (resp. odstranit duplicitní záznamy pracovních nabídek). Ve výsledku tak musí být extrakční model dostatečně robustní i pro nerelevantní dokumenty a zároveň popsat co nejvíce důležitých informací, které by usnadnily finální proces párování produktů (tj. rozlišení mezi různými variantami produktu se stejným názvem). Hlavní motivací této práce je skutečnost, že automatickým zpracováním velkého množství dokumentů lze s pomocí metod extrakce informací získat podstatně více relevantních informací, než jakými disponují databáze současných portálů4 . E-shopová data o produktových nabídkách jsou zpravidla poskytována portálům kompa4

Množství dat pochopitelně přímo úměrně roste s počtem nalezených relevantních dokumentů ve fázi crawlingu. Web crawler viz 2 na straně 5.

2

Cíle

rativního nakupování (např. heureka.cz) prostřednictvím tzv. XML feedů 5 , které musí odpovídat požadovanému schématu. To pro dané firmy nese i určité náklady, neboť schéma databáze a způsob uložení dat může být i značně odlišný od požadované specifikace. Využití těchto služeb může odrazovat potenciální obchodníky (především menší e-shopy) navíc i tím, že jsou většinou zpoplatněny. Na webových prezentacích firem se pak nachází mnoho pracovních nabídek, které jsou v rámci Internetu unikátní (tj. nejsou zveřejněny na žádném pracovním portálu). Některé nabídky firmy na portály nevkládají z důvodu, že mohou mít nadčasovou povahu (tj. firma má obecně zájem o šikovné pracovníky, ale nejde o bezprostřední potřebu a tedy ani žádné aktivně nehledá). Na pracovní nabídky lze narazit i na stránkách menších personálních agentur. Příkladem portálu, který agreguje pracovní nabídky z několika pracovních portálů, je jooble.cz.

1.2. Cíle Cílem této práce je vytvořit extrakční modely, které umožní automaticky získávat užitečné informace v dostatečně vysoké kvalitě z dostatečně rozsáhlé množiny dokumentů. Kvalitou je přitom myšleno nejenom konkrétní číslo, vyjadřující míru úspěšnosti6 extrahovaných dat, ale rovněž co nejširší využitelnost pro reálné aplikace. Mezi dílčí cíle, které tento základní cíl naplňují, patří: • vytvoření jediného extrakčního modelu pro každou doménu, který umožní extrahovat informace z množiny heterogenních dokumentů s různou formátovací strukturou • využitelnost vytvořených modelů i pro extrakci z nestrukturovaného dokumentu/textu • získání dat o vysoké granularitě (tj. např. rozlišit jednotlivé parametry výrobku) • extrahovat o každé nabídce maximum užitečných informací Některé cíle jsou společné oběma úlohám, jiné se týkají spíše jen produktových nabídek (druhý a čtvrtý bod). Druhý cíl vychází z faktu, že popis vlastností produktu je často uveden v podobě neformátovaného (volného) textu jak v nestrukturovaných webových stránkách, tak v některých existujících označkovaných metadatech. Pro úlohu pracovních nabídek byla navázána spolupráce s firmou Dain, která mi poskytla výchozí data ke zpracování a se kterou byly konzultovány průběžné výstupy tak, aby jejich výsledná forma byla aplikovatelná do praxe. Zcela zásadní je v daných dokumentech identifikovat celý název pracovní pozice a místo pracoviště. V databázi mohou být tyto údaje ukládány spolu s odkazem na původní zdroj (tj. stránku obsahující pracovní nabídku). Pro firmu Dain bylo dostačující získat celý popis pracovní nabídky. V této práci (v souladu s 5

XML feed je pojem, který se vžil pro XML soubor obsahující určitá data (nejčastěji automaticky vygenerovaná z databáze) podle předem určeného schématu, aby mohla být zpracována dalšími aplikacemi. 6 Pod pojmem úspěšnost je zde zamýšlena jednak přesnost (správnost) výsledků extrakce, jednak jejich úplnost, pojem je tedy ekvivalentní F -míře, jejíž definice je uvedena v kapitole 2.6.

3

Úvod

obecným požadavkem na vysokou granularitu údajů) byly namísto celých popisů extrahovány jen některé základní typy údajů, které se v pracovních nabídkách nejčastěji objevují 7 . Dalším důležitým údajem jsou kontaktní informace firem, kterým se v této práci nevěnuji. Úloha extrakce kontaktních údajů byla v minulosti řešena rovněž s pomocí nástroje Ex [7]).

1.3. Struktura práce Práce je dále členěna do pěti kapitol. Druhá kapitola podává přehled o metodách a přístupech, které se používají pro úlohy extrakce informací. Uveden je rovněž krátký přehled extrakčních systémů. Třetí kapitola představuje extrakční systém Ex, který byl vybrán pro realizaci obou úloh. Kromě obecných informací je v kapitole popsáno, jakým způsobem jsou využity zahrnuté algoritmy strojového učení. Čtvrtá a pátá kapitola popisují realizaci vybraných úloh. V obou případech kapitoly začínají analýzou dané domény a shrnutím klíčových otázek. Následuje popis vytváření samotné extrakční ontologie, tj. jakým způsobem byly řešeny vybrané problémy. Další část obou kapitol pojednává o vytvořených modelech pomocí algoritmu CRF++ a v poslední části jsou vytvořené extrakční ontologie vyhodnoceny. V závěrečné kapitole jsou pak diskutovány dosažené výsledky, které jsou konfrontovány se zvolenými cíly.

7

Nutno poznamenat, že získání celého popisu není vždy triviální úlohou. Identifikace jednotlivých údajů v popisu obsažených je jeden z možných přístupů (zdola nahoru), jak identifikovat hranice popisu nabídky.

4

2

Kapitola 2.

Extrakce informací z webu

Extrakce informací je technika umožňující identifikovat v textu údaje předem specifikovaného typu a extrahovat je v podobě strukturovaných a strojově srozumitelných dat. Výsledná data tak mohou být snadno využita pro potřeby dalších aplikací. Extrakce informací je zaměřena pouze na extrakci izolovaných fragmentů textu, nikoliv na jeho komplexním porozumění (přestože je někdy určitá úroveň porozumění částí textu nezbytná). Z tohoto pohledu je extrakce informací disciplínou, která se nachází na půli cesty mezi tradičním vyhledáváním informací podle klíčových slov (IR – information retrieval) a porozuměním přirozeného jazyka strojem (NLU – natural language understanding). Extrakce informací (IE – information extraction) bývá někdy uváděna jako specifická úloha z oblasti dolování dat z textu (text mining), potažmo z webu (web mining) – pokud se omezíme pouze na webové dokumenty1 . V první a dosud nejznámější monografii o web miningu [9] je věnována jedna kapitola technikám, které vznikly právě pro úlohu extrakce informací z webu (a které jsou krátce zmíněny v 2.4.3). Z tradičního pohledu data miningu, který se zabývá objevováním nových, netriviálních a potenciálně zajímavých informací z rozsáhlé množiny dat, je extrakce informací spíše samostatnou a svébytnou disciplínou. Objevování vzorů, které umožňují v textu identifikovat požadované informace, totiž nelze považovat za novou znalost v tom smyslu, že vzory jako takové nemají pro člověka vypovídací hodnotu. Nalezené vzory mají povahu extrakčních znalostí, s jejichž pomocí extrakční systém ve výsledku nalezne a extrahuje pouze známou, v dokumentu obsaženou informaci (ta může být uvedena explicitně nebo lze vyčíst z kontextu). V praktických aplikacích je ale zřejmé prolínání obou disciplín – samotné výsledky extrakčního procesu mohou být mj. dále využity v text (web) miningových aplikacích a naopak web (text) miningové techniky jako crawling 2 nebo klasifikace stránek jsou často využívány před samotným extrakčním procesem. Extrakce informací je od svých prvopočátků naopak pevně spjata s oblastí zpracování přirozeného jazyka (NLP – natural 1

Web (data) mining jako takový se dělí na 3 základní podoblasti: web content mining (dolování z obsahu webu), web structure mining (dolování ze struktury webu) a web usage mining (dolování z dat o uživatelském chování na webu). Extrakce informací pak může být chápána jako součást web content miningu. 2 Web crawler je druh počítačového programu, který na internetu prochází stránky propojené odkazy, stahuje dokumenty (metainformace, obsah) a ukládá části dokumentů v různých formátech k dalšímu použití. Využíván je především pro indexaci stránek na internetu.

5


language processing). Tato kapitola shrnuje současné poznání v oblasti extrakce informací a ač je primárně zaměřena na prostředí webu, opomíjeny nejsou ani tradiční metody, které jsou úžeji spjaty se zpracováním přirozeného jazyka. Ty neztratily nic ze své důležitosti, neboť velké množství informací na webu je stále obsaženo ve formě vět psaných přirozeným jazykem.

2.1. Typy dokumentů Textové dokumenty, které jsou vstupem každé extrakční úlohy, lze rozlišovat podle míry jejich strukturovanosti. Dokumenty mohou být strukturované, polostrukturované či nestrukturované. Pohled na to, co lze považovat za strukturované nebo kde leží hranice mezi jednotlivými typy dokumentů, se liší napříč oblastmi výzkumu. Soderland považuje volný (neformátovaný) text psaný v přirozeném jazyce (např. novinové články) za nestrukturovaný, komentáře v diskusním fóru nebo medicínské záznamy za polostrukturované a HTML stránky za strukturované [12]. Z tradičního databázového pohledu jsou za strukturované naopak považovány databázové tabulky (příp. tabulky vytvořené v tabulkovém procesoru nebo neformátované tabulky, kde jsou hodnoty oddělené středníkem). Z tohoto úhlu pohledu jsou XML dokumenty spíše polostrukturované (datové hodnoty se prolínají se schématem), zatímco HTML dokumenty nestrukturované. V [3] považují naopak XML za strukturovaná, HTML stránky za polostrukturovaná a volný text za nestrukturovaná data. Z výše uvedených pohledů jsou jednotlivé typy dokumentů popisovány spíše podle jejich struktury. Pro extrakci informací je ale rovněž podstatná povaha samotného textu, která může být proměnlivá v rámci všech uvedených typů dokumentů. Dlouhé odstavce textu psané v přirozeném jazyce jsou v nestrukturované podobě (ty nalezneme např. v novinových článcích, recenzích nebo blozích uživatelů), informace zapsané v tabulkové formě jsou většinou strukturované a „útržky“ textu polostrukturované. „Útržky“ jsou navzájem izolované jednotky, netvoří tedy plnohodnotné věty a v dokumentech se nacházejí většinou na samostatných řádcích (ve formě položek seznamu). Poslední definici tak rovněž vyhovuje obyčejný neformátovaný text, pokud jsou jednotlivé informace psány pod sebou na řádcích a netvoří souvislé věty (v podstatě jde tedy o tabulku s jedním sloupcem). V praxi je ale spíše rozhodující, jaká je granularita originálních dat s ohledem na požadavky. Podle (ne)souladu stavu a cíle lze pak vybrat odpovídající nástroj či metody. V [4] klasifikují HTML dokumenty podle míry granularity obsažených dat od „málo kvalitních“ po „velmi kvalitní“. Pokud je naším cílem extrahovat položky odpovídající n atributům, pak „velmi kvalitní“ stránky jsou takové, kde každá položka odpovídající právě jednomu atributu je obklopena párem HTML značek. Naopak „málo kvalitní“ stránky jsou ty, kde každý řetězec znaků mezi párem HTML tagů odpovídá více než jednomu atributu (jednotlivé hodnoty atributů mohou být příp. odděleny interpunkčními znaménky jako „.“, „,“ nebo „;“). V takovém případě mohou být „nekvalitní“ rovněž XML dokumenty nebo data generovaná z databází (i databázové tabulky a XML soubory mohou obsahovat delší souvislý text jako např. popis nějakého výrobku).

6

Typy úloh a využití

2.2. Typy úloh a využití Podle povahy extrakčního cíle se rozlišuje několik základních typů úloh, které se v praktických aplikacích zpravidla kombinují. Níže uvádím jejich výčet, pro úplnost je uveden i jejich anglický ekvivalent. • rozpoznávání/extrakce pojmenovaných entit (named entity recognition/extraction) • extrakce termínů (term extraction) • plnění šablon (template filling) • extrakce relací (relation extraction) • koreferenční rozhodnutí (coreference resolution) Pojmenované entity jsou slova či slovní spojení, která v textu vystupují jako jména osob, geografická místa, názvy organizací, jména produktů, časové či peněžní výrazy. Pojmenované entity jsou tedy vlastní jména rozšířená o některé další výrazy. Pojem vznikl v souvislosti se zpracováním přirozeného jazyka (resp. extrakcí informací), nejde tedy o klasický lingvistický termín. V encyklopedii Wikipedia je pojmenovaná entita mj. definována jako taková entita, která má jeden nebo více rigidních designátorů3 , jež ji označují. Například výraz „automobilová společnost založená Henry Fordem v roce 1903“ odkazuje k designátorům „Ford“ nebo „Ford Motor Company“. Naopak výraz „současný americký prezident“ je non-rigidní designátor, protože vztah mezi ním a individuem, které označuje, je nahodilý. Podobně je to i u časových nebo číselných výrazů. Rok „2012“ je pojmenovaná entita, neboť odkazuje k 2012. roku v gregoriánském kalendáři, naopak měsíc „červen“ odkazuje k měsíci červnu v libovolném roce a pojmenovanou entitou tedy není. Byly rovněž vytvořeny taxonomie pojmenovaných entit4 . Například v názvu notebooku „Lenovo ThinkPad Edge E520“ odpovídá výrobce „Lenovo“ entitě „Organizace“, zatímco „ThinkPad Edge E520“ je „Produkt“. Tento typ úlohy nalézá využití mj. pro automatické zodpovídání dotazů nebo ve strojovém překladu, kde je žádoucí zachovat vlastní jména v původním jazyce (tj. nepřekládat např. „John Smith“ na „Jan Kovář“). O rozpoznávání pojmenovaných entit v češtině pojednává [13]. Úlohou extrakce termínů je nalézt v textu všechny termíny, které jsou relevantní k určité doméně. Tato úloha je užitečná např. při konceptualizaci doménové znalosti, resp. jako podpora při vytváření doménové ontologie. V úloze plnění (populace) šablon je extrakčním cílem šablona tvořená relací k-tice, do které se mají vyplnit údaje předem specifikovaného typu, jež se vztahují k nějakému objektu či události. Obecně řečeno jde o určitý scénář – příkladem je sbírání údajů o teroristických útocích (z novinových článků) nebo o pracovních místech. Příklad takové vyplněné šablony je na obr. 2.1. 3

Pojem, který zavedl americký filosof a logik Saul Kripke. Podle něj rigidní designátor referuje právě k jednomu a témuž individuu ve všech možných (sémantických) světech. Rigidní designátory zahrnují jak vlastní jména, tak např. biologické druhy nebo látky. 4 www.ldc.upenn.edu nebo nlp.cs.nyu.edu

7


Pracovní pozice název pozice Obchodní zástupce vzdělání SŠ řidičský průkaz B jazyk AJ jazyk NJ pracovní poměr živnostenský list Obrázek 2.1.: Příklad instance šablony Pracovní nabídka. Extrahované hodnoty jsou zvýrazněny barvou, každá barva odpovídá jednomu atributu (slotu). V souvislosti s extrakcí datových záznamů z webových stránek generovaných podle určité formátovací šablony se v literatuře často vyskytuje rovněž pojem extrakce šablon (template extraction). Jedná se fakticky o konkrétní realizaci úlohy plnění šablon (pokud údaje v nalezeném záznamu odpovídají slotům v definované šabloně). Princip uvedené metody je popsán v sekci 2.4.3. Cílem extrakce relací (relation extraction) je nalézt mezi extrahovanými údaji (mohou jimi být jak pojmenované entity tak celé instance šablon) jeden z předem daných vztahů, např. „osoba se narodila ve městě.“ Konkrétním příkladem této relace je narozen_v(Ernest Hemingway, Oak Park-Illinois) pro větu „Ernest Hemingway was born in Oak Park-Illinois.“ Výstupem tohoto typu úlohy je tedy binární relace5 , která explicitně popisuje vztah mězi nějakými dvěma objekty (entitami). Plnění šablon naproti tomu vyjadřuje příslušnost určité položky (entity) k danému scénáři, jejím předmětem ale není identifikovat typy vztahů mezi jednotlivými entitami (položkami) uvnitř této n-ární relace. V závislosti na definici úlohy může jít ale ve výsledku téměř o totéž. Pokud by bylo cílem vyplnit šablonu o českých prezidentech, pak jednotlivými sloty6 by mohly být např. místo narození, knihy, které napsal a vysoké školy, které absolvoval. Ačkoliv neexistuje zjevný vztah mezi sloty navzájem, za předpokladu přítomnosti všech uvedených typů informací by vznikly následující smysluplné binární relace: narozen_v(<prezident>,<místo>), napsal_knihu(<prezident>,), ab5

Výsledkem mohou být pochopitelně relace vyšší arity, k jejich konstrukci je ale zapotřebí nejprve detekovat binární relace. 6 Pojmem slot je v úloze plnění šablon obecně označován typ informace o dané entitě (jde tedy o ekvivalentní výraz k atributu). V ontologickém inženýrství je slot chápan jako binární relace.

8

Přehled přístupů

solvent_školy(<prezident>,). Úkolem koreferenčního rozhodnutí (analýzy koreferencí) je rozpoznat, zda dvě extrahované hodnoty neodkazují ke stejnému referentu (entitě reálného světa). V kladném případě jsou tyto hodnoty v koreferenčním vztahu. Koreference může být jmenná (např. „HP“ a „HewlettPackard“) nebo zájmenná (tj. jedna z hodnot je zájmeno, které může zastupovat např. v textu již zmíněné vlastní jméno). V závislosti na typu úlohy se hledají koreferenční vztahy buď na úrovni dokumentu nebo datového záznamu (instance šablony), kterých se na stránce nalézá více. V této diplomové práci jsou pro obě domény primárně řešeny úlohy plnění šablon (konkrétní instance šablony je v dalším textu práce označována jako instance ontologické třídy, jde ale o totéž) a koreferenční rozhodnutí, částečně pak rozpoznávání pojmenovaných entit. Cílem je totiž extrahovat pouze ty pojmenované entity, které se vztahují k danému scénáři.

Příklady aplikací Extrakce informací nachází uplatnění pro vědecké, komerční i osobní účely. Příklady užitečných aplikací jsou systémy pro automatické zodpovídání na faktografické otázky nebo strukturované vyhledávání. Zatímco současné fulltextové vyhledávání dokáže vrátit dokumenty v podstatě jen na jednoduchý dotaz, pomocí strukturovaného vyhledávání lze klást složitější dotazy. Tak lze snadno hledat informace nejen o entitách, ale i o vztazích mezi nimi. Strukturované vyhledávání lze využít ve specifických doménách jako např. vyhledávání produktů, služeb (ubytování, hotely aj.) nebo pracovních míst. MEzi další aplikace patří například sledování specifických událostí v tisku (např. teroristické útoky nebo kriminální činy), vyhodnocování uživatelských nálad z transkripcí hovorů na zákaznických linkách, automatický sběr bibliografických údajů o vědeckých i jiných publikacích nebo pro analýzu sentimentu, kdy jsou nejrůznějších diskusních fór nebo blogů „extrahovány“ myšlenky a názory lidí (třeba o produktech).

2.3. Přehled přístupů Pro extrakci informací jsou nejčastěji využívána pravidla, jejichž úkolem je identifikovat v textu požadované údaje. Extrakční pravidla7 mohou popisovat přímo hodnotu, jež má být extrahována, její kontext nebo separátory (v podobě HTML značek) oddělující jednotlivé položky textu. Extrakční pravidla mohou být obecně vyjádřena pomocí formálních gramatik nebo logických pravidel (založených na predikátové logice prvního řádu). Patrně nejpoužívanějším prostředkem jsou regulární výrazy, v prostředí webu se ale uplatňují rovněž výrazy popisující cestu (např. XPath). Složitější struktury slov lze popsat pomocí bezkontextových gramatik. Pro zápis extrakčních pravidel je možné použít běžné programovací jazyky (Perl, PHP, Java, Prolog), existují ale rovněž jazyky navržené speciálně pro extrakci informací (např. JAPE v systému GATE nebo EOL v systému Ex). K odvozování (učení) vzorů z 7

Pojmy extrakční pravidla, resp. extrakční vzory se v literatuře prolínají a zaměňují, budu je tedy v této práci používat jako synonyma.

9


množiny trénovacích příkladů se využívají buď supervizované metody (učení s učitelem) nebo nesupervizované metody (učení bez učitele) strojového učení. Dle míry automatizace vytváření extrakčních pravidel lze mluvit o manuálních, poloautomatických nebo automatických metodách. Poloautomatické a automatické metody jsou založeny na induktivním učení. Nepravidlový přístup představují pravděpodobnostní grafické modely, které se nezaměřují na vnitřní strukturu slov, ale na jejich vztahy v posloupnosti slov, kterou dokument přirozeně vytváří. Snahou je modelovat závislost výskytu atributů (typů informací) mezi sebou. K tomu jim obvykle stačí samotná identita (podoba) slov a několik málo příznaků, jež popisují jejich obecné vlastnosti (slovní druh, velké písmeno na začátku apod.). Hledání ideálních parametrů modelu, které by dokázaly dostatečně obecně a přesně vystihnout danou závislost, se provádí opět na množině trénovací dat pomocí algoritmů strojového učení. Nejpoužívanější statistické modely jsou podrobněji popsány v 2.4.1 a 2.4.2. Pro potřeby extrakce informací z webu byly vyvinuty plně automatické techniky, které narozdíl od výše uvedených nevyžadují žádná trénovací data a minimální či žádný zásah od uživatele. Jedná se o metody, které v rámci jednoho nebo více HTML dokumentů hledají jednotnou formátovací šablonu, podle které jsou data na stránce generována z databáze. Jejím nalezením lze tak snadno získat obsažená data v podobě datových záznamů8 . Zbývající část této podkapitoly popisuje základní „směry“ v extrakci informací, které se vyvinuly na základě různých potřeb. V praxi se často využívá kombinace více přístupů najednou, jen velmi obtížně by se ale hledal extrakční systém, který využívá výhod všech přístupů.

2.3.1. Přístup využívající lingvistické techniky První extrakční systémy byly zaměřeny na texty psané v přirozeném jazyce, pro které bylo nutné použití metod pro zpracování přirozeného jazyka. Pro tento přístup jsou typické metody jako lexikální analýza, indetifikace konců vět, lemmatizace, značkování slovních druhů (partof-speech tagger) nebo mělká syntaktická analýza vět (shallow parsing nebo také chunking). Každý extrakční systém musí provést nejprve tokenizaci, tj. vstupní text segmentovat na menší jednotky, které mají z hlediska dalšího zpracování význam. Obecně může být výsledným tokenem znak, ale i věta. Pro potřeby extrakce informací (a zpracování přirozeného jazyka) je žádoucí, aby token byl samostatné slovo, číslo, interpunkční znaménko, matematický operátor aj. U HTML dokumentů se kromě slov přirozeného jazyka vyskytují rovněž tagy (každý tag je zpravidla jeden token). Pro potřeby morfologické a syntaktické analýzy je nutné provést rovněž lexikální analýzu textu. Ta spočívá v identifikaci jednotlivých lexémů9 v textu. Určité obtíže mohou nastat u zkratek nebo s interpretací slov oddělených spojovníkem/pomlčkou (obě znaménka jsou často zaměnována). Ty mohou být chápána jako dvě samostatná slova nebo jako jediné slovo. Stemming odstraňuje zakončení slov a ponechává jen jeho kořen. Ve většině případů je ale tato technika pro extrakci informací nepoužitelná, neboť redukuje identitu slov na obecnější 8

Datový záznam je tvořen položkami, které se vztahují k jednomu objektu. Např. produktová nabídka v produktovém katalogu, komentář ve fóru atd. 9 Základní (lexikální) jednotka slovní zásoby jazyka.

10

Přehled přístupů

výrazy, které vedou k nejednoznačnosti. Pro syntaktickou analýzu vět je klíčová identifikace konců vět, neboť tečka plní v textu i další funkce. Lemmatizace je proces, ve kterém je lexém převeden na jeho základní tvar – lemma10 . Určování slovních druhů a lemmat je součástí morfologické analýzy slov. Ta má za úkol pro každé vstupní slovo najít nejen možná lemmata, ale určit rovněž jeho gramatické kategorie. Výstup morfologického analyzátoru pro slova „funkci“ a „technika“ je uveden v tabulce 2.1. vstupní slovo

lemma

funkci

funkce

technika

technik technika

značka11 NNFS3 NNFS4 NNFS6 NNMS2 NNMS4 NNFS1

Tabulka 2.1.: Výstup morfologické analýzy. V prvním případě je jediné nalezené lemma (tedy základní slovníkový tvar) slovo „funkce“. Protože slovní tvar „funkci“ odpovídá slovu „funkce“ ve 3., 4. a 6. pádě, jsou na výstupu celkem 3 značky. Např. značka NNFS3 odpovídá podstatnému jménu (substantivu) rodu ženského v jednotném čísle a 3. pádě. Slovu „technika“ pak odpovídá lemma „technik“ (jako povolání) a lemma „technika“. Prvnímu slovníkovému tvaru odpovídají dvě značky (NNMS2 a NNMS4 ), zatímco druhému jen jedna (podstatné jméno, rod ženský, číslo jednotné, 1. pád – NNFS1 ). Pro odstranění morfologické víceznačnosti je nutné vybrat pouze jediný slovníkový tvar (který je jediný správný vzhledem k okolnímu kontextu). Tento proces zjednoznačňování (desambiguace) je založen na pravidlových nebo statistických přístupech. Morfologická desambiguace je klíčová rovněž pro syntaktickou analýzu vět. V mnoha úlohách IE může být dostačující samotná lemmatizace bez určování příslušných gramatických kategorií. Mělká syntaktická analýza vět probíhá zdola nahoru. Nejprve jsou identifikována jednotlivá slova a jejich vlastnosti (tj. výstup morfologické analýzy), které slouží pro odvození frází ve větě (např. jmenné nebo slovesné fráze) k sestavení derivačního stromu (strom, který reprezentuje syntaktickou strukturu věty podle formální gramatiky). Tím se liší od plné syntaktické analýzy, která se zabývá rovněž závislostními vztahy mezi výrazy ve větě (pak je výstupem tzv. závislostní strom). Vhodným jazykovým zdrojem využitelným v aplikacích extrakce informací (nebo obecně zpracování přirozeného jazyka) je tezaurus WordNet, který seskupuje slova do synonymických řad zvaných synsety. Kromě krátkých obecných definicí jejich významu zachycuje různé sémantické nebo lexikální vztahy, které mezi synsety existují. Příklady sémantických vztahů jsou hyponymie–hyperonymie (vztah nadřazeného a podřazeného pojmu), holonymie–meronymie (vztah celku a části) nebo vyplývání. Slova jsou rovněž zařazena do různých sémantických tříd (tj. množina konceptů, které patří do určité sémantické kategorie). 10

Lemma označuje v lingvistice základní podobu lexému (tedy slova nebo fráze), která se uvádí jako reprezentativní ve slovnících (slovníkový tvar).

11


Výstup výše uvedených metod může být využit jak při vytváření extrakčních pravidel (adresující buď hodnoty nebo i kontext), tak při klasifikaci sekvencí slov (kde jsou lingvistické údaje součástí množiny příznaků daného slova). Význam jednotlivých metod se liší v závislosti na povaze textu, ale i na obtížnosti jazyka. V jazycích jako čeština, kde je velmi časté ohýbání slov, je morfologická analýza u některých typů úloh nezbytná. Příkladem extrakčních systémů, které využívají metody pro zpracování přirozeného jazyka, jsou WHISK, RAPIER (viz 2.5) a SRV.

2.3.2. Přístup založený na ontologiích Extrakční systémy založené na extrakčních ontologiích vznikly ze dvou důvodů. Aby vznikla ontologie jako popis nějaké domény, musí ji někdo nejprve vytvořit. Extrakční systémy na druhou stranu umožňují automaticky získávat informace obsažené v textu, aniž by přesně věděly, co extrahují. Vznikla tedy myšlenka oba přístupy spojit. Řešením prvního problému je automatické populování ontologií instancemi konceptů. Řešení druhého problému pak spočívá v tom, že extrakční systémy mohou využít již jednou vytvořenou znalost. Ve třetí kapitole je blíže popsán extrakční systém Ex, který je představitelem přístupu založeného na tzv. extrakčních ontologiích.

2.3.3. Wrapperový přístup Pojmem wrapper se v původním smyslu označovala komponenta v systémech pro integraci informací, jejímž cílem bylo poskytnout jediné a zároveň jednotné rozhraní pro dotazování se nad několika informačními zdroji. V současné době se tak rovněž označují extrakční systémy, které umožňují efektivně získávat data z webu. Pojem wrapper může označovat jak systém pro extrakci informací, tak konkrétní extrakční pravidla. Wrapper může být komplexní systém, který zahrnuje proces shromažďování dat z webu (crawling), proces extrakce a výše uvedenou „integrační“ komponentu. Může jít ale také o jednoduchý skript o několika řádcích, který extrahuje např. informace z tabulek na určité webové stránce. Wrapper využívá formátovací struktury HTML stránky a skutečnosti, že mnohé údaje na webu jsou pevně strukturované (mají vysokou kvalitu HTML kódu). Extrakční pravidla wrapperů primárně adresují tzv. oddělovače položek, které jsou si v rámci stránky velmi podobné či stejné a oddělují požadované hodnoty. Ve značné většině případů plní funkci oddělovače formátovací značky (HTML tagy), v některých případech mohou být využity i literály (příkladem takového oddělovače je slovo „jméno:“ ve větě „Jméno: Aleš Pouzar“, pokud extrahujeme vlastní jména). V případě „méně“ kvalitního HTML kódu lze tímto způsobem získat jen veškerý obsah, který se mezi danými tagy nachází. Pak je nutné použít i nějaká jednoduchá pravidla adresující konkrétní hodnoty v nalezených položkách (nejčastěji regulární výrazy). Kushmerick rozlišuje několik tříd wrapperů (pravidel) podle jejich vyjadřovací síly: LR, HLRT, OCLR, HOCLR. Nejjednodušší z nich je LR (Left-Right) wrapper, který obklopuje požadovanou hodnotu z obou stran: $5.00

12

Přehled metod

Musíme zde každý prvek n-tice vyjádřit zvlášť (v tomto případě cena produktu). Složitější wrapper je pak např. OCLR (Opening-Close-Left-Right), kde parametry O a C definují začátek a konec nezávislých n-tic. Např: Blue: $5.00 Yellow: $6.50

Každá n-tice je jeden produkt, který má přiřazenu barvu a cenu. Parametr O zde odpovídá tagu , zatímco parametr C odpovídá tagu . Pomocí toho wrapperu je tak možné extrahovat celou n-tici. Extrakční pravidla pro wrapper mohou být vytvářena manuálně nebo odvozována z trénovacích příkladů prostřednictvím učících metod (v této souvislosti se používá pojem indukce wrapperů – wrapper induction). Pro indukci wrapperů se využívají metody strojového učení, ve většině případů jde o metody učení s učitelem, které vyžadují ručné označkované příklady. Mezi wrappery se rovněž řadí systémy umožňující nalézt datové záznamy na stránce automaticky bez zásahu uživatele, které byly zmíněny na začátku kapitoly. Tyto systémy nevyžadují pravidla, místo toho analyzují strukturu a hledají v ní opakující se vzory, které by mohly představovat datové záznamy s požadovaným obsahem. Výhodou wrapperů je možnost získat rychle a efektivně velké množství dat. Nevýhodou je naopak přílišná závislost na formátovací struktuře, neboť pro každou třídu dokumentů12 jsou zapotřebí nová pravidla. Metody pro indukci wrapperů sice proces vytváření pravidel zrychlují, přesto je tento přístup využitelný nanejvýš pro extrakci dat z menšího počtu webových sídel. Další nevýhodou je nutnost udržovat wrappery aktuální. Layout webů se s časem mění a pravidla tak přestávají fungovat. Některé systémy umí změnu formátování na webu detekovat automaticky a vygenerovat nová pravidla na základě znalosti dříve extrahovaných dat (pokud zůstala stejná). Ve většině případů je ale nutné provést učící proces odznova (tj. včetně značkování dat), u mánuálně konstruovaných wrapperů nezbývá než všechna pravidla přepsat.

2.4. Přehled metod V následující podkapitole jsou popsány dva pravděpodobnostní modely, které se mj. používají pro značkování textu a jsou tedy vhodné pro úlohu extrakce informací. Dokument je reprezentován typicky jako sekvence slov. Dále jsou popsány některé z automatických metod, kde dokument odpovídá DOM stromu (hierarchii HTML značek).

2.4.1. Skryté Markovovy modely Skrytý Markovův model (HMM – hidden Markov model) patří do skupiny grafických pravděpodobnostních modelů. Jeho využití je široké, nachází uplatnění jak v oblastech rozpoznávání 12

Třída dokumentu je množina dokumentů na určitém webovém sídle, které sdílejí formátovací strukturu (ve smyslu, že je identická nebo velmi podobná). Např. stránky vse.cz, fis.vse.cz a kizi.vse.cz tvoří jednu třídu dokumentu.

13


řeči, zpracování přirozeného jazyka (strojový překlad, značkování slovních druhů aj.), tak i v bioinformatice (predikce genů) nebo v kryptoanalýze. V úloze extrakce informací se HMM používá pro značkování slov v dokumentu. Cílem je objevit co nejoptimálnější „skrytou“ posloupnost značek (tj. značky pro daná slova nejsou přímo pozorovatelná), která je pozorovatelná pomocí množiny náhodných procesů13 , jež generují pozorovací posloupnost (slova dokumentu). Výraz „co nejoptimálnější“ se přitom vztahuje k takové posloupnosti značek, která by minimalizovala počet chyb při značkování dokumentu. Skrytý Markovův model je formálně definován jako pětice (Y, X, A, B, π): • Y – počet stavů (značek) • X – počet pozorování (slov) • A – přechodové pravděpodobnosti mezi jednotlivými stavy (značkami) • B – výstupní pravděpodobnosti pozorovaných slov • π – počáteční rozdělení pravděpodobností

Obrázek 2.2.: Topologie konkrétního HMM modelu. Náhodná veličina X představuje konkrétní pozorování, veličina Y představuje konkrétní stavy. Černé hrany odpovídají přechodovým pravděpodobnostem mezi stavy, barevně označené hrany pak výstupním (emisním) pravděpodobnostem. Skrytý Markovův model je konečný automat, který přechází z jednoho stavu do druhého, přičemž v každém stavu vygeneruje jedno slovo. Tento proces je znázorněn na obrázku 2.3. Přechody mezi jednotlivými stavy odpovídají Markovovu procesu prvního řádu, neboť budoucí stav závisí pouze na současném stavu a nikoliv už na stavech předcházejících (paměť je omezena na jeden předchozí stav). Tato skutečnost se označuje jako Markovova vlastnost. 13

Tyto náhodné procesy jsou determinovány konkrétní strukturou modelu, která se získá z trénovacích dat ve fázi učení.

14

Přehled metod

Obrázek 2.3.: HMM model v čase. Yi reprezentují posloupnost skrytých stavů (Markovův proces). Xi jsou jednotlivá pozorování. Šipky znázorňují směr závislosti. Přechod z předchozího stavu na současný stav (přechodová pravděpodobnost) v čase t je určen pravděpodobností P (yt | yt−1 ) a generování slova xt v současném stavu yt (výstupní nebo také emisní pravděpodobnost) v čase t je určeno pravděpodobností P (xt | yt ). Pro přechody vycházející z libovolného stavu platí, že množina odpovídajících přechodových pravděpodobností musí sčítat do 1. HMM je generativní model, který pro celou sekvenci slov délky N modeluje sdružené rozdělení pravděpodobnosti P (X, Y ), které lze rozložit na součin distribuce přechodových a výstupních pravděpodobností:

P (X, Y ) = P (Y ) · P (X | Y )

(2.1)

kde

P (Y ) = P (y1 | y0 )P (y2 | y1 ) . . . P (yn−1 | yn ) =

N Y

P (yt | yt−1 )

(2.2)

t=1

P (X | Y ) = P (x1 | y1 )P (x2 | y2 ) . . . P (xn | yn ) =

N Y

P (xt | yt )

(2.3)

t=1

Pro úlohu extrakce informací jsou pak stěžejní tyto dvě otázky: • fáze učení – jak odhadnout parametry modelu vzhledem k pozorované posloupnosti, aby pravděpodobnost P (X) byla maximální • fáze dekódování – jak najít odpovídající posloupnost stavů (značek) Y k danému modelu a při pozorované posloupnosti slov X

15


Fáze učení Natrénovaný HMM model označíme µ = (A, B, π). Výstupní a přechodové pravděpodobnosti modelu lze přibližně aproximovat podle relativních četností v trénovacích datech, většinou se ale využívá učení pomocí nesupervizovaného Baum-Welchova algoritmu. To probíhá v iterativním procesu, kde v každém kroku je natrénován model s novými parametry, které zvyšují maximálně věrohodný odhad modelu (tj. pravděpodobnost pozorované sekvence v trénovacích datech P (X | µ)). Učící fáze končí dosažením maximálního počtu iterací nebo pokud přírůstek zlepšení modelu nepřekročil daný práh. Protože by takto natrénovaný model neuměl rozpoznávat nová slova, která nebyla zahrnuta v trénovacích datech, je ve fázi učení rovněž nutné přerozdělit část pravděpodobnosti přiřazené pozorovaným slovům ve prospěch slov nepozorovaných, nebo-li aby každá emisní distribuce zahrnovala rovněž neznámé slovo.

Fáze dekódování Problém dekódování spočívá v nalezení takové posloupnosti stavů (značek) Y 0 , která pro pozorovanou sekvenci slov délky n maximalizuje sdružené rozdělení pravděpodobnosti: Y = arg max P (Y 0 | X, µ) = arg max Y0

Y0

P (Y 0 , X, µ) = arg max P (Y 0 , X, µ) P (X, µ) Y0

P (Y 0 , X, µ) = P (y1 | yπ )P (x1 | y1 )P (y2 | y1 )P (x2 | y2 ) . . . P (yn−1 | yn )P (xn | yn )

(2.4)

(2.5)

kde je počáteční stav označen yπ . Protože se posloupnost n slov v daném dokumentu nemění, je marginální pravděpodobnost P (X) konstantní a tudíž pro výpočet maxima zbytečná. Výstupní sekvence značek Y pro daný dokument je tedy determinována nejlepší stavovou cestou vzhledem k pozorované sekvenci slov. Problém hledání maxima lze efektivně řešit pomocí Viterbiho algoritmu (technika dynamického programování). Ten vychází z principu, že pro výpočet pravděpodobnosti určité cesty s1 . . . sn lze využít již dříve spočítanou pravděpodobnost pro kratší cestu s1 . . . sn−1 ., která tvoří prefix počítané cesty.

2.4.2. Podmíněná náhodná pole Podmíněná náhodná pole (CRF – conditional random fields) je pravděpodobnostní model určený pro značkování a segmentaci senkvenčních dat. Jeho využití je stejné jako u HMM, v současné době ale dosahuje mezi pravděpodobnostními modely nejlepších výsledků ve všech zmíněných oblastech. Potvrzují to výsledky mnoha výzkumných prací, kde byl na stejných datech srovnáván CRF model s klasickým HMM modelem, příp. s jeho (v některých ohledech vylepšenou) variantou MEMM (maximum-entropy Markov model – Markovský model s maximální entropií).

16

Přehled metod

Obrázek 2.4.: Grafická struktura CRF modelu. X odpovídá pozorováním (slovům v dokumentu) a veličina Y stavům (značkám). Podmíněná náhodná pole jsou narozdíl od HMM diskriminativní model, který namísto sdruženého rozdělení pravděpodobnosti P (X, Y ) modeluje přímo podmíněnou pravděpodobnostní distribuci P (Y | X), která je z pohledu úloh jako extrakce informací nebo zpracování přirozeného jazyka nejpodstatnější. Dalším důvodem popularity CRF oproti HMM je možnost využít velkého počtu vzájemně závislých příznaků, pomocí nichž lze lépe modelovat některé reálné jevy (v případě extrakce informací a NLP je to závislost mezi slovy ve větě, lze přitom uvažovat i delší kontext). Příznakem může být samotné slovo, jeho vlastnosti (např. ortografické nebo morfologické jako lemma či slovní druh), členství slova v nějakém seznamu slov nebo slova v okolí aktuálního slova. U skrytého Markovova modelu je sice rovněž možné použít namísto slova množinu příznaků, ve většině situací to ale povede k „prořídnutí“ trénovacích dat (data sparseness). Úkolem CRF v úloze extrakce informací je tedy označkovat sekvenci slov dokumentu pomocí odpovídajících sémantických značek. Značka yt pro aktuální slovo xt závisí na předchozím stavu yt−1 a pozorované množině příznaků F (xt ) pro toto slovo. Podmíněná pravděpodobnost je tedy určena jako P (yt | yt−1 , F (xt )) Zde je důležité zdůraznit, že tyto lokální podmíněné pravděpodobnosti neslouží pro výpočet celé podmíněné distribuce, ale jsou převedeny na tzv. potenciálové funkce. Ty nejsou normalizované (nemusí sčítat do 1) a namísto pravděpodobnosti vracejí číselné váhy. Tím se zabraňuje jevu „label bias“, který je popsán níže. Tyto potenciálové funkce jsou přitom definovány pouze pro ty vrcholy v grafu, které jsou navzájem propojeny, tj. tvoří maximální kliku v grafu. V případě sktruktury CRF modelu v podobě řetězce je potenciálová funkce definována na dvojici sousedních stavů Yi a Yi+1 a odpovídajícího pozorování Xt (viz obrázek 2.4). Potenciálová funkce se vypočítá jako exponenciální součet vah pozorovaných příznaků: ψ(yi−1 , yi , F (X)) = exp

X

λf,si ,si−1 f (yi−1 , yi , X, i)

(2.6)

f F

Parametr λf,yi ,yi−1 představuje váhu konkrétního příznaku f odhadnutou z trénovacích dat ve fázi učení. Příznaková funkce14 F se vztahuje zároveň ke slovům a k předchozímu a 14

Rozdíl mezi příznakem a příznakovou funkcí je objasněn v další kapitole na konkrétních ukázkách pro

17


současnému stavu. Izolované potenciálové funkce nemají přímou pravděpodobnostní interpretaci, jejich význam spočívá v lokálních omezeních náhodných veličin, pro které je funkce definována. To ve výsledku ovlivňuje i globální konfiguraci modelu. Hledání nejpravděpodobnějšího označkování Y vstupní sekvence slov v dokumentu pro daný model µ spočívá v maximalizaci podmíněné pravděpodobnostní distribuce: Y = arg max P (Y 0 | X, µ)

(2.7)

Y0

Tu dostaneme vynásobením n potenciálových funkcí daných klik: P (Y 0 | X, µ) =

n X X 1 exp λf,yi ,yi−1 f (yi−1 , yi , X, i) Z(λ, X) i=1 f F

(2.8)

Z označuje normalizační faktor: Z(λ, X) =

X s

exp

n X X

λf,si ,si−1 f (yi−1 , yi , X, i)

(2.9)

i=1 f F

Normalizace je tedy provedena až u celé výstupní distribuce. Pro hledání nejlepší cesty je opět využíván Viterbiho algoritmus. Ve fázi učení je cílem dosáhnout maximální věrohodnosti podmíněné pravděpodobnosti sekvence značek v celých trénovacích datech (viz 2.8). Optimalizace přitom probíhá na celé výstupní distribuci (nikoliv na lokálních pravděpodobnostech), trénink CRF modelu je proto podstatně pomalejší než u HMM nebo MEMM. Pro tuto úlohu se využívají gradientní algoritmy jako např. L-BFGS (Low-Memory BFGS). Problém označovaný „label bias“ se vztahuje k preferenci stavů s nižším počtem následných přechodů před stavy s vyšším počtem přechodů. To je dáno podmínkou, aby přechodové pravděpodobnosti z jednoho stavu do dalších sčítaly do 1 – s rostoucím počtem možných přechodů tak klesá i průměrná přechodová pravděpodobnost. Label bias patří k hlavní nevýhodě MEMM oproti CRF. Nespornou výhodou CRF (a MEMM) oproti HMM je naopak využití velkého množství vzájemně závislých příznaků.

2.4.3. Porovnávací techniky Cílem porovnávacích technik je detekovat opakující se vzory ve formátovací struktuře stránky. Mnohé webové stránky jsou generovány automaticky z databáze podle určitých šablon a tedy lze obnovit (resp. objevit) původní strukturu informací (která byla v určité míře ztracena při publikování dat ve formátu HTML) nalezením této formátovací šablony. Úloha se v literatuře někdy označuje jako template extraction nebo pattern mining (to je ale relativně obecný výraz, pod kterým se skrývají i další významy). Objekt generovaný podle nějaké šablony (např. nabídka produktu) budeme označovat jako datový záznam (v návaznosti na původní strukturu dat ve formě databázové tabulky). Jedná se o plně automatické metody, k jejichž provedení nejsou nutná žádná trénovací data ani zásah uživatele. Výhodou je dále skutečnost, že jeden datový záznam odpovídá algoritmus CRF++ (3.3).

18

Přehled metod

právě jedné instanci. To je užitečné v případě plnění šablon, resp. seskupování hodnot do instancí ontologické třídy. Hranice mezi jednotlivými záznamy totiž od sebe zároveň oddělují nalezené k-tice hodnot atributů a není zapotřebí seskupovat hodnoty na základě pravidel. Na druhou stranu se tyto techniky uplatní jen u pevně strukturovaných HTML stránek a přímá využitelnost získaných dat je přímo úměrná kvalitě vstupního HTML dokumentu (viz typy dokumentů na straně 6). Formátovací šablonu lze nalézt za těchto situací: • hledání probíhá v rámci jediného dokumentu, ve kterém se nachází alespoň dva záznamy generované podle stejné (či velmi podobné) šablony • hledání probíhá v rámci webového sídla pro alespoň dva dokumenty stejné třídy, které obsahují po jednom záznamu Příkladem první situace jsou nejrůznější produktové katalogy, komentáře na diskusním fóru nebo třeba výsledky vyhledávání na Google.com. Za (relativně) nejjednodušší příklad takové šablony (struktury) si lze představit tabulku, kde každý řádek tabulky odpovídá jednomu datovému záznamu a každý sloupec specifikuje typ informace (tato struktura se nejvíce přibližuje původní podobě). Příkladem druhého typu jsou např. šablony pro zpravodajské články nebo blogy. Pro realizaci úlohy se používají tzv. porovnávací techniky založené na míře podobnosti. Možné je porovnávat řetězce (string alignment nebo také string matching), stromy (tree alignment nebo tree matching) nebo obojí zároveň. V konkrétních úlohách je nutné porovnávat společně i desítky řetězců (stromů), v takovém případě se jedná o vícenásobné porovnávání (multiple alignment). Nejpoužívanější technikou pro měření vzdálenosti („podobnosti“) mezi řetězci je Levenhsteinova editační vzdálenost. Je definována jako minimální počet operací (vkládání, mazání a substituce) vyžadovaných pro změnu řetězce s1 na řetězec s2 . Vzdálenost mezi stromy A a B je definována jako minimální počet operací nutných pro transformaci stromu A do stromu B (vložení uzlu, odstranění uzlu nebo nahrazení uzlu). Pro porovnávání stromů se používá DOM strom. Nejjednodušší možností, jak porovnat dva stromy, je najít maximum shodných uzlů. Algoritmus MDR Algoritmus MDR (Mining Data Records) [14] je určen pro hledání datových záznamů, které jsou tvořeny HTML značkami, jež se používají pro tvorbu tabulek či formulářů. Navržený algoritmus umožňuje najít rovněž vnořené záznamy. Metoda vychází z předpokladu, že jestliže datové záznamy jedné datové oblasti jsou vedle sebe a mají podobný formát, pak se v DOM stromu musí nacházet na stejné úrovni a mít společného předka (viz obrázek na následující straně). Oblast datových záznamů (zkráceně datová oblast) je vymezena jako taková skupina datových záznamů, které spolu sousedí, jsou podobně (stejně) formátované a popisují podobné objekty. Příkladem datové oblasti je např. produktový katalog tvořený záznamy o mobilních telefonech. Algoritmus se skládá celkem ze 3 kroků:

19


Obrázek 2.5.: Algoritmus MDR a porovnávání stromů. Zdroj: [14] 1. zkonstruování DOM stromu pro danou stránku 2. nalezení a vydolování datových oblastí 3. identifikace datových záznamů Najít na stránce datové záznamy a jejich skryté schéma znamená najít opakující se vzory a zarovnat je. Datový záznam může na stránce začínat odkudkoliv a může být libovolně dlouhý. Varianta vyzkoušet všechny možnosti je stěží možná a především neefektivní. Obecný problém výše uvedených technik a metod je skutečnost, jak zjistit, zda nalezené položky tvoří k-tici nebo množinu k-tic. Obtížnější je to v případě, kdy jsou všechny k-tice v rámci jedné množiny tvořeny stejným počtem atributů. Ukázka níže odpovídá množině 3 dvojic (jedná se o 3 variace stejného produktu lišící se barvou a cenou): Blue: $5.00 Yellow: $6.50 Pink: $10.99

HTML kód níže naopak zobrazuje atributy jedné dvojice (jedná se o parametry jednoho produktu): weight: 30 kg height: 5 m

Ne vždy lze předpokládat, že každý HMTL tag je generovaný šablonou a vše ostatní (tj. slova obsažená mezi značkami) jsou datové položky (na tomto předpokladu jsou postaveny wrapperové systémy DeLa a DEPTA). Proto některé systémy (IEPAD nebo OLERA) nechávají na samotném uživateli, aby označil co je šablona a co data. V tomto případě je nutný minimální zásah uživatele.

2.5. Extrakční systémy V [3] klasifikují extrakční systémy z několika úhlů pohledu.

20

Extrakční systémy

Vezmeme-li v úvahu úlohu plnění šablon (extrakce instancí nějaké třídy) na webové stránce, kde je extrakční cíl definován jako relace k-tice (k odpovídá počtu atributů), pak může dojít k následujícím variacím datového objektu: • chybějící atribut • atribut má více hodnot • různá pořadí atributů • různá formátování – 1 atribut má více různých formátování/jednotné formátování pro více atributů • datový objekt je ploché nebo vnořené struktury (obsahuje další objekty) Některé extrakční systémy provádějí tokenizaci vstupního dokumentu na úrovni slov, jiné na úrovni tagu (tj. token odpovídá buď HTML tagu nebo celému řetězci znaků mezi dvěma HTML tagy). Jak bylo uvedeno již výše, systémy se liší i stupněm automatizace, podporou komplexních objektů s vnořenou strukturou, typem dokumentů, dostupností grafického uživatelského rozhraní nebo formátem výstupních dat (XML), robustností vůči různým variacím extrakčního cíle nebo adaptivitou. Sarawagi15 rozlišuje wrapper systémy podle typu extrakční úlohy. Extrakce jednoho typu údaje (field-level extraction), extrakce na úrovni záznamu (record-level extraction), extrakce na úrovni stránky (page-level extraction) a extrakce na úrovni webového sídla (site-level extraction). První uvedená úloha extrahuje hodnoty jediného atributu (slotu), nezabývá se vztahy mezi atributy v datovém objektu. Druhý typ odpovídá již definované relaci k-tice, cílem je ale pouze jediný typ objektu. Naproti tomu wrappery umožňující extrakci na úrovni stránky mohou definovat více typů objektů. Poslední uvedený typ definuje takové úlohy, kde jsou cílové atributy „rozházené“ po celém webovém sídlu.

Rapier Rapier je zástupcem semisupervizovaných extrakčních systémů založených na analýze přirozeného jazyka. Indukce extrakčních pravidel probíhá zdola nahoru pomocí technik inspirovaných induktivním logickým programováním. Každé extrakční pravidlo je definováno pomocí 3 vzorů, z nichž první a poslední specifikují okolí hodnoty, která má být extrahována: (1) prefixový vzor (pre-filler pattern), který popisuje levý kontext požadované hodnoty, (2) vzor popisující hodnotu (filler pattern), jež má být extrahována a (3) suffixový vzor (post-filler pattern), který popisuje pravý kontext požadované hodnoty. Jednotlivé vzory mohou být vymezeny pomocí slov, slovních druhů nebo sémantických tříd. Rapier využívá při generalizaci pravidel slovník WordNet. Pokud je jedno z pravidel omezeno třídou „žena“ a druhé třídou „muž“, generalizací vznikne mj. pravidlo omezené třídou „osoba“. Nejlepší generalizace dvou 15

Sarawagi, S.: Automation in information extraction and integration. Tutorial of The 28th International Conference on Very Large Data Bases (VLDB), 2002.

21


pravidel je hledána pomocí paprskového prohledávání, k výslednému pravidlu mohou být dodatečně přidány další omezení, dokud pravidlo nefunguje bezchybně. Rapier umožňuje ze stránek extrahovat pouze jediný objekt (instanci šablony). Níže je ukázka indukovaného pravidla na základě předložených trénovacích příkladů. “nn” a “nnp” odkazují ke slovním druhům „podstatné jméno“, resp. „vlastní jméno“, „jj“ označuje přídavné jméno. Cílem je extrahovat oznámení o akvizici firem.

Pre-filler Pattern:

Filler Pattern:

Post-filler Pattern:

1) syntactic: {nn,nnp}

1) word: undisclosed

1) semantic: price

2) list: length 2

syntactic: jj

2.6. Metody vyhodnocení Pro vyhodnocení úspěšnosti extrakčních metod se používají tradiční metriky využívané v oblasti vyhledávání informací. Měření úspěšnosti extrakce hodnot Přesnost (P – precision) vyjadřuje podíl správně extrahovaných položek mezi všemi extrahovanými položkami. Jestliže ručně označkovaná data označíme GOLD (odpovědi učitele – ručního anotátora) a automaticky extrahovaná data AUTO (předpovědi extrakčního systému), přesnost se bude rovnat průniku ručně označkovaných a automaticky extrahovaných dat ku počtu všech předpovědí systému: P =

P =

AU T O ∩ GOLD AU T O

(2.10)

# spr´ avn´ e odpovˇ edi # odpovˇ edi syst´ emu

Úplnost (R – recall) vyjadřuje podíl správně extrahovaných položek ku počtu všech položek označených anotátorem. Jinak řečeno, úplnost je počet správných odpovědí systému ku počtu všech odpovědí učitele (které jsou implicitně považovány za správné): R=

R=

AU T O ∩ GOLD GOLD

(2.11)

# spr´ avn´ e odpovˇ edi # odpovˇ edi uˇ citele

Obě míry leží v intervalu < 0; 1 >, přičemž 1 (100 %) je nejvyšší možná dosažená přesnost (úplnost). Mezi přesností a úplností existuje inverzní vztah. Čím obecnější extrakční pravidla specifikujeme (nebo čím obecnější dotaz položíme vyhledávači), tím více výsledků dostaneme, zároveň ale bude mezi nimi dost i těch, které neodpovídají našemu dotazu (cíli). Čím jsou extrakční pravidla nebo dotaz na vyhledávač specifičtější, tím přesnější dostaneme výsledky –

22

Metody vyhodnocení

ale zdaleka ne všechny. Pro potřebu srovnání jednotlivých metod (či systémů) pomocí jedné metriky byla definována rovněž F -míra, která je harmonickým průměrem přesnosti a úplnosti: F =

(β 2 + 1) · P · R β2P + R

(2.12)

Parametr β umožňuje preferovat jednu z měr před druhou. Nejčastěji se používá nastavení β = 1, tedy obě míry mají stejnou váhu. Meření úspěšnosti seskupování hodnot Lze rovněž měřit správnost seskupování hodnot atributů do instancí (objektů). Pro potřeby této práce jsem si vybral Vilainovy metriky [10], která je odvozena z výše uvedených měr. Namísto hodnot porovnává pomyslné hrany, které propojují sekvenci označkovaných hodnot atributů v rámci instance. Každá instance má tedy přesně N − 1 hran, kde N je počet vrcholů (hodnot atributů) v dané instanci. Pro názornost je doplněn obrázek 2.6. Vilainova přesnost (VP – Vilain precision) se počítá jako poměr počtu hran nutných k propojení extrahovaných hodnot patřících do instance k počtu všech „extrahovaných“ hran v instanci. VP =

# spr´ avn´ e hrany # hrany syst´ emu

Vilainova úplnost (VR – Vilain recall) je poměr počtu správně extrahovaných hran ku počtu všech ručně označkovaných hran. VR=

# spr´ avn´ e hrany # hrany uˇ citele

Vilainovo skóre (VS – Vilain score) je podobně jako u F -míry harmonický průměr obou měr: VS =

Mikroprůměrování a makroprůměrování

2·VP ·VR VP +VR

(2.13)

Pokud probíhá vyhodnocení na velkém datasetu,

je vhodné předem určit, jakým způsobem se budou počítat průměrné hodnoty statistik pro celý soubor dat. Při mikroprůměrování jsou počítány statistiky zvlášť pro každý dokument a ve výsledku se zprůměrují (nebere se tedy ohled na počet příkladů v dokumentech). Makroprůměrování bere celý soubor dat jako jeden dokument – statistiky jsou tedy vypočítány z kumulativních počtů AU T O ∩ GOLD, AU T O a GOLD.

23


Obrázek 2.6.: Vilainovy metriky. Levá strana označuje ručně označkované údaje (3 hrany), pravá strana výsledek extrakčního procesu (2 hrany). Vilainova přesnost je rovna 1/2=0.5 a Vilainova úplnost 1/3=0.33.

24

3

Kapitola 3.

Systém Ex

3.1. Popis systému Extrakční nástroj Ex1 , vyvíjený na VŠE Praha, slouží k extrakci pojmenovaných entit (hodnot atributů) a k jejich seskupování do relací (instancí tříd). Zpracovávat lze dokumenty s různým množstvím formátovací struktury jako jsou webové stránky, ale také čistě textové nebo tabulární dokumenty. Definice tříd a (k ní náležejících) atributů se zapisují do tzv. extrakční ontologie [1]. Snahou je zde využít pro extrakci doménové ontologie doplněné o znalosti umožňující automatickou extrakci z textu. Mezi doménové ontologie využitelné pro odvození struktury extrakčních ontologií [5] v oblasti nabídek produktů patří např. CEO2 nebo nově vznikající PTO3 . Odvozením z vhodné doménové ontologie se současně minimalizuje úsilí nutné pro zpětnou konverzi extrahovaných výsledků při populaci zdrojové ontologie. Nástroj Ex kombinuje celkem tři typy extrakční znalosti: pravidla ručně zadaná expertem, znalosti indukované z trénovacích dat pomocí algoritmů strojového učení a částečně jsou využity znalosti nesupervizovaně indukované na základě opakující se formátovací struktury (především pro tabulky). Tímto způsobem je možné z textu extrahovat i takové hodnoty, které předchozí typy extrakční znalosti nepokrývají (nebo-li je chybně považují za negativní příklady). Extrakční ontologie definuje jednu nebo více tříd (např. produktová nabídka) sestávajících z atributů, u kterých lze definovat kardinalitní a datotypová omezení a využít dědičnosti (např. cena a cena s DPH). Definice atributů i tříd obsahují extrakční indicie (evidence), které jsou reprezentovány zejména regulárními vzory a axiomy. Regulární vzory na úrovni třídy specifikují pravděpodobná pořadí atributů uvnitř instance nebo kontext jejího výskytu, zatímco na úrovni atributů modelují předpovídanou hodnotu atributu (obsahové vzory) nebo okolí jeho výskytu (kontextové vzory). Vzory lze definovat na úrovni slov (včetně rozsáhlých seznamů), vlastností slov, na úrovni znaků a na úrovni formátovacích značek (HTML tagů). Vzory mohou odkazovat na jiné vzory (patřící i k jiné třídě), možné je tak jejich opakované 1

http://eso.vse.cz/~labsky/ex/ http://www.ebusiness-unibw.org/ontologies/consumerelectronics/v1 3 http://www.productontology.org 2

25

Systém Ex

použití, včetně vnoření jednoho vzoru do druhého. Třídní axiomy představují tvrzení o obsahu třídy (typicky o vztazích mezi hodnotami jejích atributů, např. „emailová adresa je podobná jménu majitele“), zatímco axiomy definované na atributech se vyjadřují o hodnotě daného atributu. Axiomy je možné definovat jako funkce jazyka JavaScript vracející binární výsledek. U každé evidence je možno nastavit dva pravděpodobnostní odhady. Přesnost evidence P (A | E) stanovuje pravděpodobnost výskytu atributu v případě, že daná evidence platí. Pokrytí evidence P (E | A) stanovuje, do jaké míry je přítomnost vzoru pro extrakci hodnoty daného atributu nutná. Dále je každý typ atributu spojen s určitou nízkou apriori pravděpodobností výskytu v textu. Na základě vyhodnocení všech evidencí a předpokladu jejich podmíněné nezávislosti systém odhadne pravděpodobnost každé potenciální hodnoty atributu PAC ve zkoumaném dokumentu: PAC = P (A | E ∈ ΦA )

(3.1)

Pro extrakci atributů lze navíc přímo z extrakční ontologie trénovat a používat externí algoritmy strojového učení: značkovač sekvencí CRF[8] a některé klasifikátory implementované v systému Weka [2]. Rozhodnutí těchto algoritmů je obvykle využito jako další obsahový vzor klasifikovaného atributu [6]. Práce s nástrojem CRF++ je blíže popsána v sekci 3.3. Atribut na obrázku 3.1 je definován pomocí dvou obsahových a dvou kontextových vzorů. První vzor říká, že výskyt jednoho z uvedených písmen v textu s 25 % pravděpodobností představuje skupinu řidičského oprávnění, tj. pro řetězec „A“ jde o pravděpodobnost P (A | driving license) = 0.25 100 % pokrytí zamezí extrakci hodnot tento vzor nesplňujících. První kontextový vzor svým vysokým pokrytím 75 % omezuje pravděpodobná levá okolí předpovídané hodnoty atributu (označené symbolem $). Pokrytí vzoru má na výsledek extrakce vliv vždy, i když neodpovídá žádnému řetězci, naopak parametr přesnost vstupuje do výsledné míry spolehlivosti4 pouze v případě, že daný vzor platí. Největší vliv na (ne)extrakci má první kontextový vzor s pokrytím 75 %, který vymezuje levé okolí předpovídané hodnoty atributu (označené zástupným symbolem $). Ve vzoru jsou celkem 2 regulární vzory (řádky), stačí splnit pouze jeden z nich (znak nového řádku, potažmo oddělovač ’|’ představuje logický operátor OR). Kardinalita vztahu je vymezena pomocí parametru card, tedy jedna instance třídy může mít až 4 odpovídající hodnoty (skupiny ŘP). Poslední obsahový vzor přijímá rozhodnutí externího klasifikátoru CRF. Extrakční vzory se pro každý atribut specifikují ve dvou částech (sekcích). První je určena pro definici obsahových vzorů, zatímco druhá pro definici kontextových vzorů. Obě části jsou oddělené a na sobě nezávislé v tom smyslu, že nelze provázat určitá pravidla z jedné sekce s pravidly z druhé sekce (tj. mezi obsahovými a kontextovými vzory nelze vytvářet vztahy). Tímto způsobem se Ex liší např. od Rapieru. Tam každé pravidlo obsahuje vzor pro levý 4

Míra spolehlivosti je předpověď extrakčního systému o dané hodnotě spočítaná z pravděpodobnostních odhadů extrakčních indicií.

26

Anotace a vyhodnocení

Obrázek 3.1.: Ukázka části extrakční ontologie – atribut driving_license pro extrahování skupin řidičského oprávnění. kontext (pre-filler), obsahový vzor (filler) a vzor pro pravý kontext (post-filler). Oba způsoby mají v praxi své výhody a nevýhody, patrně nejlepší variantou by byla možnost využívat výhod obou.

3.2. Anotace a vyhodnocení Systém Ex podporuje anotace ve formátu Ellogon. Ty je možné vytvořit se stejnojmennou aplikací Ellogon5 (víceúčelová a vícejazyčná platforma pro zpracování textů). Ellogon umožňuje jak označkování hodnot atributů, tak výsledné anotace pospojovat do skupin (instancí). V systému Ex je možné měřit úspěšnost extrakce atributů a rovněž úspěšnost seskupování hodnot atributů do instancí. K tomu slouží Vilainova míra uvedená v 2.6. Měření je možné ve dvou módech. Tzv. „striktní“ mód (dále strict mode) počítá za správně extrahovanou hodnotu jen takovou, která je identická s ručně označkovanou hodnotou. Naopak ve „volném“ módu (dále loose mode) jsou k výslednému skóre připočteny i částečně správně extrahované hodnoty. Skóre pro danou hodnotu pak odpovídá poměru počtu správně extrahovaných slov (tokenů) k počtu ručně označkovaných slov. Dále jsou zde přítomny módy „occurrence“ a „presence“. První uvedený mód počítá všechny výskyty atributů, zatímco ve druhém případě postačuje extrahovat pro každý atribut v dokumentu jediný výskyt.

3.3. Nástroj CRF++ Nástroj CRF++6 je open source implementace algoritmu CRF. Systém Ex umožňuje tento algoritmus zahrnout do extrakční úlohy. V extrakční ontologii postačuje definovat, které atributy z ontologie mají být součástí CRF modelu, a vytvořit tzv. příznakové šablony. Spuštěním trénovacího módu systém Ex automaticky vygeneruje z označkovaných dat trénovací soubor, který posléze předloží nástroji CRF++. Výsledkem je natrénovaný model, který stačí přidat 5 6

http://www.ellogon.org/ http://code.google.com/p/crfpp/

27

Systém Ex

do extrakční ontologie (uvedením cesty k modelu a jeho název). V nástroji Ex lze použít celkem dvě reprezentace dokumentu: sekvence slov a sekvence sousloví určité délky. Pro algoritmus CRF je vhodnější první uvedený. HTML značky nejsou do trénovacích dat zahrnuty. Každý atribut v extrakční ontologii, který je vybrán pro CRF model, je automaticky modelován jako „začátek atributu“ (tj. první slovo hodnoty) a „pokračování atributu“ (zbývající slova hodnoty). Předpověď CRF klasifikátoru má pak stejnou povahu jako jakékoliv jiné extrakční pravidlo. K atributu stačí přidat odkaz na definovaný CRF model se jménem konkrétní značky. Tento „odkaz“ je vnořen v obsahovém vzoru a proto je ještě potřeba zadat pravděpodobnostní odhady jako u ostatních vzorů. Při extrakčním procesu pak systém Ex předkládá nástroji CRF++ jednotlivá testovací data (odpovídající aktuálnímu dokumentu) a přijímá zpět nejlepší rozhodnutí klasifikátoru. Pokud značka (třída) vrácená klasifikátorem odpovídá atributu (značce) předpovídané hodnoty, pak extrakční vzor platí (a naopak).

3.3.1. Příznaky Velkou výhodou CRF oproti HMM je možnost využít velké množství vzájemně závislých příznaků. Protože na vhodně definovaných příznacích závisí výsledná úspěšnost modelu, měla by být tomuto kroku věnována dostatečná pozornost. Způsob vytváření příznaků je demonstrován na jednoduchém příkladě. Mějme v označkovaném dokumentu následující posloupnost slov: Notebook Sony VAIO SB3S9E/B Slovo „Sony“ je označkováno jako „Manufacturer“, slovo „VAIO“ jako „Serie“ a slovo „SBS3S9E/B“ jako „Model“. Pro každé slovo (příklad) máme definovány 2 vlastnosti: • velikost písma („CA“ – první velké, „UC“ – všechna velká, „LC“ – všechna malá) • ortografický typ slova („ALPHA“ – jen písmena abecedy, „ALPHANUM“ – alfanumerické slovo, „P“ – interpunkční znaménko, „INT“ – číslo) Každou sémantickou značku pak modelujeme jako „začátek značky“ (B-značka) a „pokračování značky“ (I-značka). V tabulce 3.1 je zachycen odpovídající výstup určený pro algoritmus CRF++. Slovo [0]

Velikost písma [1]

Typ slova [2]

Třída

Notebook Sony VAIO SB3S9E / B

CA CA UC UC NA UC

ALPHA ALPHA ALPHA ALPHANUM P ALPHA

bg B-Manufacturer B-Serie B-Model I-Model I-Model

Tabulka 3.1.: Trénovací data pro algoritmus CRF++. Číslo v hranaté závorce označuje číslo sloupce. Třída „bg“ odkazuje k neoznačkovanému slovu (nezajímavé slovo na pozadí).

28

Nástroj CRF++

Před vytvářením CRF modelu je nejprve nutné vytvořit šablony, které pomocí maker definují, z jakých typů údajů v trénovacím souboru (viz tabulka) se má vytvořit příznak. Tyto příznaky jsou posléze pomocí příznakových funkcích převedeny do binární podoby. Příznaková šablona je tedy např.: U05:%x[-1,0]/%x[0,0] Makro %x[-1,0] odkazuje k předchozímu příkladu (tj. o řádek výše) v nultém sloupci a makro %x[0,0] odkazuje k atuálnímu příkladu v nultém sloupci. Tata šablona tedy dává do vztahu předchozí a aktuální slovo v dokumentu. Příznak je konkrétní realizace dané šablony. Pokud se nyní nacházíme na druhé pozici v trénovacích datech (2. řádek), pak je výsledkem: U05:Notebook/Sony Současně je vytvořena příznaková funkce, která váže vygenerovaný příznak ke konkrétní třídě: func1 = if (output = B-Manufacturer and feature="U05:Notebook/Sony") return 1 else return 0 Šabloně „U06:%x[-1,2]/%x[0,2]“ by pak odpovídal příznak „typ předchozího slova/typ aktuálního slova“. Počínaje druhým řádkem tabulky by byly postupně vygenerovány příznaky „ALPHA/ALPHA“, „ALPHA/ALPHA“, „ALPHANUM/ALPHA“, „P/ALPHANUM“ a „ALPHA/P“. Počet příznakových funkcí f vygenerovaných jednou šablonou (tj. počet binárních příznaků) je roven L ∗ N , kde L je počet tříd (značek) a N je počet jedinečných konkrétních příznaků, které byly pomocí šablony vygenerovány. Po vygenerování všech příznakových funkcí pro všechny definované šablony je pak každému slovu x v trénovacích datech podle těchto vytvořených funkcí přiřazena odpovídající množina binárních hodnot Fx , které definují, zda dané slovo má nebo nemá konkrétní příznak (tyto binární hodnoty jsou v podstatě binární příznaky): Fx = {f unc1 , f unc2 , . . . , f uncf } Součástí distribuce systému Ex jsou již předdefinované šablony, které byly v minulosti využity v úlohách jako extrakce kontaktních informací nebo oznámení o seminářích [7]. Těchto šablon využívám rovněž pro extrakci produktových a pracovních nabídek. Trénovací soubor pro nástroj CRF++, který systém Ex automaticky vytváří z trénovací sady dokumentů, obsahuje informace jako základní identita slova, slovo převedené na malá písmena, lemma (funguje pouze pro angličtinu) nebo ortografické vlastnosti slova. V šablonách příznaků jsou pak kombinovány tyto informace do bigramů, trigramů atd. Využívají se rovněž „okénka slov“ pro obsáhnutí identity/vlastností okolních slov (okénka jsou velikosti 5 slov, tj. kontext je 2 slova vlevo a 2 vpravo). Zbývající údaje v trénovacím souboru se týkají toho, zda dané slovo odpovídá extrakčním vzorům definovaných v extrakční ontologii či nikoliv. Výsledné příznaky pak pro každé slovo určují, zda odpovídá „začátku vzoru“, „pokračování vzoru“ nebo „neodpovídá vzoru“.

29

Systém Ex

3.3.2. Možnosti nastavení algoritmu Kvalitu výsledného modelu lze ovlivnit pomocí 3 parametrů: • výběr regularizačního algoritmu (L1/L2) • parametr ovlivňující míru generalizace (hyper-parametr) • určení prahu pro minimální frekvenci příznaku Regularizace je používána ve statistice a strojovém učení k zamezení přeučení (overfitting). Podle autorů první typ regularizace (L1) výrazně redukuje absolutní počet příznaků v modelu, mírně lepších výsledků dosahuje druhá uvedená varianta regularizace (L2). Pomocí druhého parametru lze vyvažovat rovnováhu mezi přeučením a „podučením“ modelu. Pro fázi učení jde o klíčový parametr. Čím vyšší číslo, tím větší tendence k přeučení. Třetí parametr umožňuje prořezat příznaky o ty, které se vyskytují v datech v počtu menším než je nastavený práh. To je užitečné při velkém množství dat a velkém množství příznaků.

30

4

Kapitola 4.

Extrakce produktových nabídek

Předmětem této úlohy je extrahovat nabídky notebooků. Extrakčním cílem jsou vybrané parametry notebooků a údaje specifikující konkrétní nabídku, které jsou jedinečné pro každý eshop (tj. cena a dostupnost zboží na skladě). Jednotlivé typy extrahovaných informací jsou zmíněny v sekci 4.2. Extrakční cíl byl zvolen se záměrem, aby získaná data mohla být použita v aplikacích jako strukturované vyhledávání na základě parametrů a komparativní nakupování. Cílem je vytvořit jedinou extrakční ontologii pro všechny typy stránek (produktové katalogy, detailní popisy produktů). Pro doménu produktových nabídek byly vytvořeny 2 extrakční ontologie, které se od sebe liší použitými extrakčními znalostmi. První extrakční ontologie (EO#1) využívá pouze ručně zadaná pravidla, zatímco druhá ontologie (EO#2) kombinuje expertní znalost v podobě pravidel se znalostmi indukovanými pomocí algoritmu CRF++. Úloha byla realizována v následujících krocích:

1. analyzovat webové stránky e-shopů 2. vybrat dataset a rozdělit ho na trénovací a testovací část 3. navrhnout extrakční ontologii a pro každý atribut ručně napsat extrakční vzory (EO#1) 4. ručně označkovat trénovací data 5. vylepšovat extrakční ontologii do té doby, dokud dochází ke zvyšování úspěšnosti na trénovacích datech 6. natrénovat CRF model se všemi atributy 7. vytvořit ontologii #EO2: k ručně napsaným vzorům z #EO1 přiřadit dodatečné vzory, které přijímají rozhodnutí klasifikátoru CRF 8. ručně označkovat testovací data

9. na testovacích datech ověřit kvalitu modelu EO#2

31


10. natrénovat další CRF model s jinými parametry učení či jinými atributy, příp. jiným počtem příznakových šablon 11. vybrat CRF model dosahující na testovacích datech nejvyšší F-míry

12. provést vyhodnocení na trénovacích i testovacích datech pro obě extrakční ontologie (#EO2 s CRF modelem vybraným v předcházejícím kroku) Kromě parametrů samotného CRF modelu je především klíčové jeho zapojení do extrakční ontologie #EO2 tak, aby na výsledek extrakce měly vliv pouze správná rozhodnutí CRF klasifikátoru a naopak špatná rozhodnutí byla potlačena. Je proto nutné u každého atributu v ontologii dosáhnout optimálního vyvážení pravděpodobnostních odhadů všech extrakčních indicií a zároveň brát v potaz, že jsou některé atributy ve vzájemné interakci a proto zhoršení úspěšnosti u jednoho může vést ke zhoršení úspěšnosti několika dalších atributů. Nejvíce času zabraly kroky 3 až 5. Z bodu 5 bylo často nutné vracet se k předchozím dvěma bodům. Proces ručního anotování celého datasetu trval přibližně jeden člověkotýden (5 člověkodní). Seskupování hodnot do instancí probíhalo automaticky pomocí vytvořeného PHP skriptu. Při anotování bylo seskupení hodnot patřící do jedné instance z obou stran „ohraničeno“ označením okolních neutrálních slov (k tomu sloužila speciální značka). Skript pak podle těchto „oddělovačů“ zařadil označkované hodnoty do odpovídajících instancí. Hlavním důvodem automatizace byla skutečnost, že Ex vyžaduje anotace instancí v trochu jiné podobě, než v jaké je vytváří Ellogon. Ellogon odkazuje k prvkům instance pomocí pozice hodnoty v textu (např. {5600 5615}), zatímco Ex odkazuje na již označkované prvky pomocí jejich identifikátorů (např. {1}). Vytváření ručních pravidel zabralo přibližně 2 člověkotýdny. Určení přesnějšího časového údaje stěžuje fakt, že jsem se systémem Ex předtím nikdy nepracoval a tudíž bylo nejprve potřeba pochopit, jak funguje a jakým způsobem zapisovat potřebná extrakční pravidla. „Tento proces učení“ jsem zahájil tvorbou extrakčních ontologií, které jsou předmětem této práce. Proces vytváření extrakční ontologie probíhal tedy současně s procesem učení.

4.1. Popis domény Z hlediska počtu nabídek produktů a množství informací o produktech lze stránky eshopů rozdělit na dva základní typy: • stránka obsahující produktový katalog s více produkty • stránka, která detailně popisuje jeden vybraný produkt Produktový katalog si lze představit jako tabulku obsahující m×n (nabídek) produktů, kde m je počet řádků a n počet sloupců dané tabulky (obrázek 4.1). Každá buňka pomyslné tabulky tedy odpovídá jedné nabídce1 . Jediné údaje, které se v produktových nabídkách objevují bez 1

Tato představa se liší od tabulkové struktury zapsané v HTML kódu, kde je pro popis jednoho produktu nutné využít více buněk.

32

Popis domény

Obrázek 4.1.: Produktový katalog. Stránka generovaná z databáze podle formátovací šablony. výjimky u všech eshopů, jsou název notebooku a cena. Velmi často bývá uváděna dostupnost a množství na skladě. Počet parametrů popisujících notebook se u jednotlivých obchodů liší. Parametry bývají nejčastěji uvedeny ve zkrácené formě bez jakéhokoliv kontextu2 (viz obrázek 4.2), výjimkou nejsou ani slovní popisy tvořené větami přirozeného jazyka. Dokumenty obsahující produktový katalog budu v dalším textu označovat jako katalogová stránka eshopu. Druhý typ stránek je naopak charakteristický detailním popisem jednoho vybraného produktu. Ten je většinou tvořen kombinací slovního popisu (větami přirozeného jazyka) a výčtem parametrů ve formě tabulky či seznamu. Narozdíl od katalogové stránky je u všech parametrů uveden kontext, podle kterého lze daný údaj identifikovat. Tento typ stránky budu nadále označovat jako detailová stránka eshopu. Kromě produktových katalogů a detailních popisů se na stránkách eshopů vyskytují často i další oblasti datových záznamů, které obsahují nabídky produktů – např. seznam nejlépe prodávaných notebooků v postranní liště. Proto i detailová stránka může obsahovat více produktů. Obecně u produktových nabídek platí, že se vlastnosti (parametry) produktů nacházejí nejčastěji v základním tvaru i v českém jazyce (tj. ohýbání slov se nepoužívá typicky u názvů produktů, řad/modelů nebo číselných či technických parametrů). Pro identifikaci těchto hodnot není nutná morfologická analýza (resp. lemmatizace). Každý notebook lze popsat velkým množstvím parametrů, převážně technické povahy. Číselné parametry následované příslušnými jednotkami míry se snadno rozlišují od okolního textu, víceznačnost hrozí u hodnot se stejnou jednotkou míry: např. „8 GB“ jako operační paměť a „500 GB“ jako kapacita pevného disku. Důležitý je zde kontext, přestože ve většině 2

Cyhbějícím kontextem je zamýšlena nepřítomnost údajů, které indikují (vysvětlují) daný parametr.

33


Obrázek 4.2.: Výčet parametrů notebooku bez kontextu. případů lze dané atributy odlišit vymezením oboru hodnot (intervalem). Problémy mohou způsobovat výskyty atributů, které se nevztahují přímo k popisovanému notebooku, ale jsou zde uvedeny např. z důvodu srovnání nebo doplnění informace. Příkladem je popis: „Operační paměť: 6 GB (1×4 GB) DDR3 1333 rozšířitelná až na 8 GB“. Pro odlišení takových hodnot je zapotřebí již poměrně dobře porozumět kontextu, nebo využít informací z příslušného produktového katalogu, ve kterém je daný notebook popsán (parametr tam může i nemusí být uveden). V praxi je součástí extrakčního procesu rovněž navigace po stránkách, aby mohly být využity rovněž informace z dalších stránek, které popisují objekt zájmu. Toto je ale spíše úloha integrace informací a v této práci se jí nezabývám. Dodatečná informace, která mohla být získána z produktového katalogu, proto není k dispozici.

4.2. Dataset Dataset produktových nabídek je tvořen celkem 56 stránkami získanými ze 17 různých eshopů. Dataset byl pořízen manuálně, nachází se v něm tedy pouze relevantní dokumenty. Každý e-shop je zastoupen dvěma detailovými stránkami a minimálně jednou katalogovou stránkou (některé e-shopy umožňují zobrazit produktový katalog v odlišném vizuálním stylu3 ). Poměr těchto typů dokumentů je 22 katalogových stránek ku 34 detailovým stránkám. V trénovací množině je zastoupeno 11 eshopů, v testovací zbývajících 6. Stránky stejného e-shopu jsou vždy přiřazeny k právě jedné množině, bez ohledu na typ dokumentu. Trénovací data pocházejí z e-shopů: Alza.cz, Czechcomputer.cz, Cybex.cz, Digiboss.cz, Digiprofi.cz, ITLevne.cz, Kasa.cz, Mall.cz, Mironet.cz, Okay.cz, TSBohemia.cz. Testovací data pocházejí z eshopů: Datart.cz, Electrohall.cz, Korunka.cz, Nakupuj.cz, OKComputer.cz, Onlineshop.cz. 3

Tj. např. tabulková struktura a obrázkový katalog. V datasetu jsou zahrnuty jen taková zobrazení katalogů, která se liší buď počtem údajů nebo formátovací strukturou. Pomocí speciálních knihoven jQuery lze totiž dosáhnout změny vizuálního vzhledu beze změny formátovací struktury.

34

Dataset

Hodnoty atributů (#)

Instance (#)

Trénovací data

Testovací data

Trénovací data

Testovací data

Katalogové stránky

3432

1098

249

79

Detailové stránky

1810

1398

22

26

P

5242

2496

271

105

Tabulka 4.1.: Základní údaje o datasetu e-shopů. Počet ručně označkovaných příkladů (hodnot atributů) a instancí. Vyšší počet instancí a příkladů u testovací množiny detailových stránek je způsoben přítomností datových oblastí obsahující další nabídky produktů. Základním kritériem pro rozdělení e-shopů na trénovací a testovací množinu bylo to, zda jsem e-shop již znal z minulosti. „Důvěrně“ známé e-shopy tak byly vybrány do trénovací množiny, aby testovací množina představovala pokud možno co nejvíce „neznámá“ data. Značka

#

Značka

#

Výrobce notebooku

730

Název grafické karty

363

Řada notebooku

501

Grafická paměť

281

Model notebooku

730

Název IGP4

125

Produktový kód

212

Operační paměť

530

EAN kód

6

Kapacita HDD

520

Cena (bez označení)

405

Kapacita SSD

29

Cena s daní

203

Operační systém

519

Cena bez daně

37

Úhlopříčka displeje

667

Množství na skladě

104

Rozlišení displeje

211

Dostupnost zboží

333

Typ disleje

47

Název procesoru

578

Barva

342

Frekvence CPU

207

Hmotnost

58

Tabulka 4.2.: Nabídka notebooků – extrahované typy informací. Ručně označkované hodnoty pro celý dataset. Atribut cena byl anotován pomocí 3 značek, přičemž značka „cena“ je použita pro takové hodnoty, v jejichž okolí není explicitně uveden typ ceny (s daní nebo bez daně).

35


4.3. Klíčové otázky Klíčové otázky před samotným návrhem extrakční ontologie by šly shrnout do následujících bodů: • jestliže existují dva typy dokumentů, kolik extrakčních ontologií vytvořit • jakým způsobem modelovat názvy výrobků (→notebook, grafická karta, procesor) • jak postihnout často se měnící údaje, aby nemusel být extrakční model často aktualizovaný • jak extrahovat hodnoty s chybějícím kontextem, aniž by došlo ke snížení přesnosti Pokud je dopředu znám typ zpracovávaného dokumentu, pak lze použít pro každý typ jinou extrakční ontologii, která bude lépe vystihovat charakteristiky dané stránky. V detailových stránkách je používán delší kontext, u katalogových často úplně chybí. Na druhou stranu, delší věty a tím kontext lze nalézt i v produktových katalozích. Vybrána byla jedna ontologie pro oba typy dokumentu, aby mohly být lépe demonstrovány možnosti zvoléného přístupu. Extrakční ontologie může být ale kdykoliv rozdělena na dvě samostatné a příslušná extrakční pravidla mohou být upravena, aby lépe vyhovovaly danému typu stránky. Klíčovou otázkou při návrhu extrakční ontologie je, kolik atributů zvolit pro komplexní typy údajů, které se skládají z více sémanticky dělitelných jednotek (sémantických komponent). V této úloze jsou takové údaje celkem 3: název notebooku, název grafické karty, název procesoru. Jednotlivé názvy obsahují jméno výrobce a označení modelu, v některých případech i označení řady. Jde tedy o tři údaje s různým významem. Je možné zvolit jeden atribut pro každou komponentu nebo jeden vzor pro každou komponentu a ty posléze pomocí referencí poskládat do celku v rámci jediného atributu. Volba záleží mj. na složitosti převedení různých značení výrobců na jednotné značení (tj. zjednoznačnění), ale i na délce (počtu slov) jednotlivých částí názvu. Mezi dalšími aspekty lze zmínit odlišnou specifikaci koreferenčního rozhodnutí (v prvním případě lze přímo porovnávat údaje stejné sémantiky) nebo typ vybraného klasifikátoru. K tomu se dále váže otázka, co přesně považovat za název produktu a jaké z uvedených částí musí tento název tvořit. V popisech notebooků se často používají blíže nespecifikovaná označení jako např. „grafická karta AMD Radeon 6xxx“ nebo „procesor AMD řady E“. Stejně tak se lze setkat s velmi zkrácenými názvy jako např. „310M“ nebo „HD 6590M“ (obě hodnoty označují modely grafických karet). Často se měnící údaje (modelová označení, produktové kódy apod.) lze v zásadě identifikovat třemi způsoby. Označkováním velkého množství dat a využitím nějakého klasifikátoru. První a nejméně vhodná varianta, která vyžaduje pravidelné přetrénování modelu. Vytvořením seznamů slov a naplněním je pokud možno všemi existujícími názvy modelů, řad, výrobců či výrobních kódů. Pokud existuje spolehlivý zdroj pokrývající všechny potřebné informace (či rozhodující většinu), ze kterých lze údaje získávat automaticky a bez rizika zanesení chyb, je to patrně nejvhodnější volba. Třetí možností je vymezit názvy produktů pomocí regulárních

36

Vytváření extrakční ontologie

výrazů. Za určitého předpokladu jde o stejně účinný a efektivní způsob, jak najít potřebné údaje.

Předpoklad, který jsem zmínil o odstavec výše, se týká posledního, čtvrtého bodu. Obecně vymezené vzory jsou snadno zaměnitelné s jinými údaji, zapotřebí je proto přesný, úzce vymezený kontext. To se zároveň týká i mnohých dalších parametrů, které bývají v produktovém katalogu vypsány bez explicitního uvedení, o jaký typ údaje se jedná.

Rozhodl jsem se pro vytvoření 3 samostatných atributů, které specifikují název notebooku. Naopak jeden atribut popisuje celý název grafické karty a jeden atribut celý název procesoru. Kvůli jednoznačnosti extrahovaných údajů je stanovena podmínka, že název musí být tvořen alespoň modelovým označením, které označuje jeden konkrétní produkt. Extrakční pravidla popisující název procesoru a grafické karty by měla být zároveň schopna extrahovat i samostatné výskyty modelových označení, které jsou v popisech notebooků velmi časté. K extrakci atributů výrobce notebooku a série notebooku byly vytvořeny seznamy slov – jde o malý konečný počet hodnot, které jsou z krátkodobého časového hlediska relativně neměnné. Naopak modelové označení notebooku, grafické karty i procesoru je specifikováno obecně, aby daný regulární vzor odpovídal i novým údajům a odpadla tím nutnost časté aktualizace extrakčního modelu. Obecně je specifikován rovněž produktový kód.

4.4. Vytváření extrakční ontologie

Extrakční ontologie je tvořena jedinou ontologickou třídou. Obsahuje celkem 108 ručně vytvořených vzorů (z toho 2 vzory pro seskupování atributů) a 8 axiomů. Jedinými povinnými atributy jsou výrobce notebooku, modelové označení notebooku a cena. Schéma třídy je zachyceno na obrázku 4.3. Povinné atributy jsou vyznačené tučně. Uzly vycházející z kořenu představují atributy, uzly vycházející z těchto atributů jsou specializované atributy. Kardinalita vztahu je vyjádřena dvojicí čísel.

37


Obrázek 4.3.: Schéma třídy Nabídka notebooku.

4.4.1. Specifikace atributů Extrakční vzory pro název notebooku byly rozděleny do 3 atributů, které postupně odpovídají výrobci notebooku, označení série (nepovinné) a označení modelu. Naopak pro název grafické karty a název procesoru byl vytvořen vždy jen jeden atribut. Bylo to mj. z důvodu, že na stránkách e-shopů se prolínají stará označení s novými, které lze velmi obtížně převést na jednotný systém značení, podle kterého by bylo možné vytvořit odpovídající extrakční pravidla. Název notebooku Dekompozice názvu produktu na údaje výrobce, řada (série) a model byla provedena subjektivně se záměrem vytvořit jediný a jednoznačný systém značení, který by vyhovoval produktovým značením všech výrobců v trénovacích datech. Sémantika systémů značení se napříč výrobci různí. Dobrým příkladem je firma Apple, která notebooky označuje pouze názvem řady a úhlopříčkou displeje. V tomto případě bylo tedy s ohledem na schéma provedeno zjednodušení, že název řady je považován za označení modelu. Odlišit od sebe jednotlivé modely je přesto stále možné, protože je zachován údaj o velikosti úhlopříčky displeje (pouze se nevyskytuje v názvu produktu). Atribut Model notebooku je specifikován podle několika regulárních výrazů, z nichž některé se částečně překrývají (systém Ex preferuje vždy co nejdelší hodnotu, která odpovídá vzoru).

38


Každý výraz je definován pomocí ortografického typu slova a přípustného počtu znaků. V modelu notebooku se prolínají především alfanumerická slova, která jsou od sebe zpravidla oddělena pomlčkou nebo lomítkem. Jednotlivé vzory byly odvozeny z trénovacích dat. V těch se nacházely nejčastěji kombinace „alfanumerické slovo“ (41%) a „alfanumerické slovointerpunkční znaménko-alfanumerické slovo“ (30%). Níže uvedených 10 vzorů pokrývá celkem 94% všech modelových označeních v trénovacích datech. Z celkového počtu 505 hodnot bylo vytvořeno 23 regulárních výrazů, do modelu nebyly zahrnuty ty nejméně frekventované. Jednoduchá generalizace spočívala v přizpůsobení intervalů hodnot. [ALPHANUM]{4,5}[P][ALPHA]{2}[P][ALPHANUM]{5} [ALPHANUM]{5}[P][ALPHANUM]{3}[P][ALPHANUM]{6} [ALPHANUM]{2,4}[INT]{4}[P][ALPHANUM]{3} [ALPHANUM]{2,7}[P][ALPHANUM]{5,12} [ALPHANUM]{4,5}[ALPHA]{5,7}[ALPHANUM]{3,4} [ALPHANUM]{5,9}[P][ALPHA] [INT]{3,4}[P][ALPHANUM]{10,12} [INT]{4}[ALPHA]{3} [ALPHANUM]{3,6} [INT]{3,4} Regulární výrazy jsou převedeny do čtivější podoby. [P] zastupuje 3 interpunkční znaménka: tečku, čárku a pomlčku. Např. první vzor stanovuje, že označení modelu má následující přípustnou strukturu: 1. token typu „alfanumerické slovo“ o délce 4 až 5 znaků, 2. token typu „interpunkční znaménko“, 3. token typu „slovo“ o délce 2 znaky, 4. token „interpunkční znaménko“ a 5. token typu „alfanumerické slovo“ o délce 5 znaků. Protože se jednotlivé údaje nachází v samostatných atributech, bylo zapotřebí je ještě pospojovat. U každého atributu je uveden nutný vzor, který definuje přípustný kontext. Řada notebooku je extrahována jen a pouze tehdy, pokud je zleva uveden výrobce a zprava model. Výrobce je extrahován jen a pouze tehdy, pokud se zprava nachází alespoň model, nebo série následovaná modelem. Model notebooku je extrahován jen a pouze tehdy, pokud je zleva výrobce, nebo výrobce následovaný řadou. Při extrakci názvu notebooku se lze dále omezit pouze na ty HTML tagy, jež název notebooku obklopují a zároveň ho od zbytku textu „vizuálně oddělují“. Jinak řečeno, snahou je úplně zabránit extrakci výskytů ve volném textu (popisu notebooku). To je důležité především z hlediska seskupování atributů do instancí. Přestože není prováděna analýza CSS stylů, lze využít např. nadpisy (tagy H1 – H6) a hyperlink (tag A), které se v obou případech používají jen pro zobrazování kratších (řekněme důležitějších) informací. Ve výsledku je tak možné buď úplně potlačit všechny duplicitní názvy nebo jejich počet alespoň omezit – pokud se na stránce nachází vícero názvů v podobě nadpisů/odkazů (např. u stránek s detaily produktu). Jde zároveň o dostačující podmínku pro to, aby se v okolí názvu notebooku nevyskytovala běžná slova jazyka, často přítomná ve slovních popisech, která by mohla být chybně přiřazena k modelovému označení.

39


Název procesoru a grafické karty Poměrně obecně jsou specifikovány rovněž extrakční vzory pro název procesoru a grafické karty, ve kterých jsou kombinovány názvy výrobců a řad (výčtem slov) a regulárními výrazy popisujícími konkrétní modelová označení. Aby bylo možné extrahovat názvy procesorů a grafických karet pouze v podobě modelového označení (tj. bez uvedení výrobce, příp. řady), je nutné vymezit velmi specifický a povinný kontext. Samotné výskyty modelového označení jsou totiž snadno zaměnitelná s jinými údaji. Příkladem je označení modelu procesoru jako „2430M“ nebo označení modelu grafické karty „GT520“. V systému Ex nebylo jiné řešení, než pro každý údaj vytvořit dva atributy. První vymezuje „užší“ obor hodnot (specifičtější hodnoty) a zároveň ponechává volný kontext, který nemusí být splněn. Druhý atribut pak definuje obecné hodnoty pomocí regulárních výrazů, ale vynucuje je pomocí specifického kontextu. Dodatečný atribut pro grafickou kartu je uveden níže. <pattern p="0.5" cover="0.5" ignore="case"> ( HD [0-9]{4}[M]? | HD[0-9]{4}[M]? ) [0-9]{3}[A-Z] <pattern p="-1" cover="1"> , $ | $ - ( [0-9] GB )

4.4.2. Koreferenční rozhodnutí V systému Ex jsou za koreferenci automaticky považovány takové hodnoty atributu, které jsou identické jako již jiné extrahované hodnoty v této instanci. Pomocí JavaScriptových funkcí lze pak účinně hledat koreference i mezi dvěma různými řetězci. Nalezení koreferencí je podstatné z hlediska seskupování atributů, chybné koreferenční rozhodnutí může vést k porušení kardinality vztahu mezi atributem a třídou a ve výsledku i k zamítnutí instance. U extrahovaných hodnot je obecně je zapotřebí vypořádat se s • chybějícími slovy, • permutací slov, • rozdílnou podobou slov, • používáním zkratek, • kombinací výše uvedeného.

40


V rámci produktových nabídek není potřeba řešit tzv. zájmennou koreferenci, vyjadřovací síla JavaScriptu je v tomto případě vesměs dostačující. Bez ohledu na atribut se nejprve zjišťuje, zda není jeden z řetězců podřetězcem druhého. V opačném případě jsou řetězce normalizovány na jednotný zkrácený tvar, který lze lépe porovnávat. Takovým příkladem jsou např. následující dvě hodnoty, které odkazují ke stejnému objektu (referentu): Windows 7 Professional 64-bit CZ W7 Pro CZ (x64).

V tomto případě je název Windows převeden na jediný znak (odpovídající počátečnímu písmenu v názvu), totéž je provedeno s označením verze (Professional, Home, Premium apod.), odstraněny jsou rovněž veškeré mezery, interpunkční znaménka a slova, která jsou z hlediska porovnávání nepodstatná (bit nebo jazyková označení jako CZ, EN apod.). Výsledkem sekvence těchto konverzí řetězců je u výše uvedeného příkladu v obou případech tvar „W7PRO64“, druhou z hodnot tak lze prohlásit za koreferenci k té první. U číselných hodnot je pak pomocí axiomů docíleno, že dvě různá čísla vyjadřující stejné množství jsou považovány za jednu hodnotu. Např. „4“ GB operační paměťi je koreferencí k „4096“ MB operační paměťi nebo „2.1“ GHz je koreferencí k „2100“ MHz.

4.4.3. Seskupování atributů do instancí Přípustná pořadí hodnot atributů v instanci lze definovat pomocí vzorů na úrovni třídy. S rostoucím počtem vzorů, které popisují různé permutace atributů, se úměrně zvyšuje počet možností, jak dané atributy seskupit a tím klesá rozlišovací schopnost. Produktové nabídky na stránkách e-shopů typicky začínají názvem produktu. V extrakční ontologii je proto seskupování atributů vynuceno pomocí jediného přípustného pořadí na začátku instance: „Výrobce (Série) Model“, přičemž přítomnost atributu Série není povinná. Zbývající atributy se mohou v instanci vyskytovat v libovolném pořadí. Název notebooku tak v podstatě slouží jako hranice (oddělovač) mezi nabídkami. Zároveň je negativně vymezeno (tj. nulovým pokrytím vzoru), kterými atributy nesmí instance začínat (tj. všechny kromě výše zmíněných, které tvoří název výrobce). Ač se jedná o ekvivalentní pravidla, algoritmus bez této dodatečné podmínky v některých situacích selhával. Striktně definovaná pravidla jsou orientována na co největší přesnost seskupování (na úkor úplnosti). U e-shopů obecně platí, že produktové nabídky začínají právě názvem výrobku 5 . Pouhým zvolením pořadí atributů na začátku instance ještě není zajištěno jejich správné seskupení. V textu se většinou vyskytují několikanásobné výskyty názvu produktu vztahující se k jedinému produktu, mezi nimiž se mohou vyskytovat hodnoty ostatních atributů. V závislosti na hodnotách těchto atributů „mezi“ a jejich kardinalitních omezeních může i nemusí dojít 5

V určitých případech nemusí vizuální pořadí atributů korespondovat s pořadím atributů ve zdrojovém kódu dokumentu.

41


k rozdělení instance do více objektů. I proto je v extrakční ontologii vymezeno, že název notebooku musí být obklopen příslušnými formátovacími značkami (viz výše).

4.5. Trénování CRF modelu Nejprve byla k vytvoření modelu použita celá množina atributů. Algoritmus CRF++ si ovšem s tak velkým počtem atributů neporadil a program po načtení dat přestal reagovat. Nepomohla ani změna regularizačního algoritmu ani prořezání méně frekventovaných příznaků, ani zredukování datového souboru o nevýznamná slova (viz dále). Ve výsledku tak bylo z trénovacího souboru odstraněno 8 nejméně frekventovaných značek (atributů). Společně se zredukováním souboru z původních 72 596 příkladů na třetinu se podařilo uvést algoritmus do chodu. V datovém souboru se totiž vyskytovaly příliš dlouhé sekvence nevýznamných slov, které pochází z detailových stránek e-shopů. S pomocí PHP skriptu byl proto soubor zredukován o nevýznamná slova, která nejsou zařazená do žádné třídy, tj. v původním dokumentu neměla přiřazenou žádnou značku. Byly odstraněny všechny sekvence nevýznamných slov mezi příklady zařazenými do cílových tříd tak, aby rozestup mezi těmito označkovanými slovy byl právě 20 nevýznamných slov. Majoritní třída neoznačkovaných slov tak byla mírně znevýhodněna oproti ostatním (cílovým) třídám, která jsou předmětěm extrakční úlohy. Změnou parametrů učení se nepodařilo dosáhnout významnějších změn, všechny modely na testovacích datech dosahovaly téměř identických výsledků. Co mělo na výsledek větší vliv, bylo přenastavení pravděpodobnostních odhadů u extrakčních indicií odpovídajících atributů. Většinou nestačilo pouze přidat vzor odkazující na CRF klasifikátor, zohledněny musely být všechny vzory a jejich pravděpodobnostní odhady. Jen „optimálním“ vyvážením expertní znalosti a předpovědi CRF klasifikátoru bylo možné dosáhnout lepších výsledků. Vybraný CRF model obsahuje celkem 22 tříd odpovídající 11 atributům (každý atribut je modelován jako „začátek atributu“ a „pokračování atributu“). V modelu jsou zahrnuty atributy výrobce, řada a model notebooku, produktový kód, název procesoru, název grafické karty, úhlopříčka displeje, operační a grafická paměť, cena, cena s daní, barva a operační systém. Příznaky byly vygenerovány podle 90 příznakových šablon, z toho 52 šablon se týkalo obsahových a kontextových vzorů v extrakční ontologii. Velikost trénovacích dat: 26 695 příkladů Počet příkladů odpovídající značkám: 7 590 Celkový počet vygenerovaných příznaků: 1 677 208 (bez prořezání) Hyper-parameter: 0.756 Error rate: 0.00259 Počet iterací: 207 Celkový čas: 14 minut7 6

Parametr, pomocí kterého lze korigovat přeučení/podučení. Výchozí nastavení je 1, čim vyšší hodnota, tím větší sklon k přeučení. 7 PC sestava: Intel Core i5-2430M @ 2.40 GHz, 4 GB RAM, Windows 7 Pro x64.

42

Vyhodnocení

4.6. Vyhodnocení V této části jsou prezentovány dosažené výsledky. Byla měřena obecná schopnost extrahovat požadované hodnoty atributů bez ohledu na to, zda patří k nějaké instanci, a dále úspěšnost seskupování atributů do instancí. Z důvodu velkého množství extrahovaných údajů jsou uváděny pouze některé důležité atributy a to jen pro testovací data. Kompletní statistiky včetně vyhodnocení trénovacích dat lze nalézt v příloze. Agregované míry přesnosti, úplnosti a Fmíra jsou počítány pomocí makroprůměrování. K vyhodnocení byl využit mód „occurrence“, kde se počítají všechny výskyty atributů. Obecná specifikace některých atributů s použitím regulárních výrazů je nejpravděpodobnější příčinou toho, že výsledky na trénovací a testovací množině jsou téměř shodné. Svůj podíl má na tom pochopitelně i skutečnost, že koncept notebook je snadno popsatelný – většina parametrů má pouze několik málo jedinečných hodnot, které se opakují stále dokola. Člověk navíc postupuje na rozdíl od stroje intuitivně a do pravidel se tedy promítá i to, co není explicitně uvedeno v označkovaných dokumentech. U dobře popsatelného konceptu tedy snadno dojde k pokrytí většiny reálných jevů. V případech „jednoduchých“ atributů klasifikátor CRF nepřinesl žádná (nebo jen minimální) zlepšení. Neextrahované nebo špatně extrahované položky jsou příčinou již zmíněného chybějícího kontextu (tj. není explicitně uvedeno, o jaký údaj se jedná).

4.6.1. Extrakce hodnot atributů S pomocí kombinovaného modelu (#EO2) se podařilo především zvýšit počet extrahovaných údajů – o 7 % (to představuje 177 hodnot). Nepatrně se však zvýšila i přesnost (počet falešně pozitivních příkladů klesl o 30). Zlepšení je vidět především u problémových údajů, které se v datech vyskytují často bez kontextu a jejichž podobu bylo nutné vyjádřit obecně. Pomocí manuálně vytvářených pravidel šlo takové atributy popsat jen obtížně, zvýšení úplnosti bylo pouze za cenu velké nepřesnosti. To je příklad atributů pro název procesoru a grafické jednotky. Pokud není každý údaj specifikován pomocí dodatečných atributů, úspěšnost je v případě ručně psaných pravidel výrazně nižší – 55 % v případě procesoru a 72 % v případě grafické karty. Přítomnost dodatečných atributů nehraje významnou roli pouze u kombinovaného modelu, tam jsou F-míry v obou případech srovnatelné. Tyto atributy jsou přitom důležité i pro pozdější párování produktů (v aplikacích komparativního nakupování), protože v českých obchodech se neuvádí mezinárodní identifikátory zboží jako např. kód EAN (v celém datasetu bylo pouze 6 takových hodnot). Nepoměrně důležitý je při jednoznačné identifikaci produktu samotný kód výrobce (produktový kód). Relativně malý přínos kombinovaného modelu lze vyčíst u modelového označení notebooku. To je dáno skutečností, že se atribut nemůže díky definovaným restrikcím na okolní formátování vyskytovat ve volném textu a zároveň je výskyt atributu vázán na dva zbývající atributy, které tvoří název notebooku – kontext vymezený zleva připouští pouze název výrobce nebo název řady notebooku. Vyloučen je tedy jeho samostatný výskyt v textu. Proto se i přes obecnou specifikaci identity atributu podařilo dosáhnout uspokojivých výsledků i bez po-

43


Nabídky notebooků (testovací data) Atribut

Výrobce (S) Řada (S) Model (S) Model (L) Produktový kód (S) Produktový kód (L) Cena (S) Cena (L) Název CPU (S) Název CPU (L) Název GPU (S) Název GPU (L) Název IGP Grafická paměť Operační paměť Průměr (S) Průměr (L)

#

P (%)

EO#1 R (%)

225 139 225 225 54 54 147 147 182 182 108 108 53 91 158

98,06 94,78 75,45 88,28 93,33 96,92 89,41 96,47 86,59 87,15 92,96 97,18 100 97,92 71,43

89,78 91,37 74,11 85,45 25,93 27,78 82,99 84,27 85,16 85,35 61,11 62,43 52,83 51,65 79,11

93,74 93,04 74,77 86,84 40,58 43,18 86,08 89,96 85,87 86,24 73,74 76,02 69,14 67,63 75,08

98,54 95,49 80,75 93,01 80,00 88,46 89,25 95,70 95,86 97,66 93,46 94,04 90,91 92,47 85,00

89,78 91,37 76,79 85,90 44,44 48,93 92,52 93,79 89,01 91,25 92,59 93,52 94,34 94,51 86,08

93,95 93,38 78,72 89,31 57,14 63,01 90,85 94,74 92,31 94,35 93,02 93,78 92,59 93,48 85,53

+0,21 +0,34 +3,95 +2,47 +16,56 +19,83 +4,77 +4,78 +6,44 +8,11 +19,28 +17,76 +23,45 +25,85 +10,45

2496 2496

90,47 92,70

79,56 81,12

84,66 86,52

92,35 94,41

86,65 88,25

89,41 91,23

+4,75 +4,71

F (%)

P (%)

EO#2 R (%)

F (%)

4F (%)

Tabulka 4.3.: Míra úspěšnosti extrakce atributů pro nabídky notebooků (trénovací data). Pouze ruční pravidla (EO#1) a kombinovaný model (EO#2). 4F = rozdíl mezi F-mírou třetího a prvního modelu. (L) mód loose, (S) mód strict. moci CRF. Klasifikátor pak zvýšil především přesnost – o 13 správných hodnot. Absence kontextu má i další důsledek. V extrakčních pravidlech bylo často nutné vymezovat kontext nikoliv pomocí slov indikujících přítomnost údaje, ale pomocí okolních hodnot atributů. Proto některé atributy jsou klíčové v tom smyslu, že se na jejich výskyt vážou další atributy, a neextrahování hodnoty klíčového atributu vede ke zhoršení úspěšnosti i u dalších atributů. Příkladem je trojice atributů výrobce-řada-model. Na modelové označení notebooku se přitom v kontextových vzorech odkazují další 3 atributy.

4.6.2. Extrakce instancí Díky restrikcím na formátovací strukturu v okolí názvu notebooku je seskupování atributů do instancí relativně snadné u katalogových stránek. Potíže činilo pouze velké množství atributů. Algoritmus pro seskupování hodnot je občas citlivý na sebemenší změny, např. přidání jednoho atributu způsobilo „rozbití“ všech instancí na stránce, přestože splňoval kardinalitní omezení. Pořadí atributů, které je stanoveno pravidly, nevyhovovala jediná katalogová stránka (z testovací sady). Na té nekorespondovalo vizuální pořadí prvků s formátovací strukturou. Detailové stránky naopak obsahují velmi mnoho (často se opakujících) hodnot atributů roztroušených po celé stránce a je proto velmi obtížné je seskupit všechny do jediné instance.

44

Vyhodnocení

Příčinou „rozbití“ instance je většinou porušení kardinalitního omezení. Roli zde hraje kvalita koreferenčních rozhodnutí pro dané atributy, leckdy se ale pro jeden atribut objeví různé hodnoty odkazující k různým referentům (entitám). Možností je „zvolnit“ kardinalitní omezení, to ale může vést ke sloučení dvou nabídek, pokud se vedle sebe nachází dva produkty se stejným názvem. Nízká úplnost je ale částečně způsobena faktem, že se neměří unikátnost informací (které jsou pro praktické využití dat zásadní), ale všechny výskyty, tedy včetně častých koreferencí (resp. duplicit). Z hlediska využitelnosti dat by bylo zajímavé počítat pouze poměr správně extrahovaných unikátních hodnot (referentů) k počtu všech ručně označkovaných unikátních referentů. Měření všech výskytů hodnot naopak odráží výkonnost extraktoru. Uvážíme-li, že pravidla pro seskupování atributů mají původ spíše v obecné zkušenosti, pak jsou vytvořené extrakční vzory nezávislé na pozorovaných datech a tudíž celý dataset lze považovat za „testovací“ data. Ve výsledkové tabulce jsou tedy uvedeny rovněž výsledky pro trénovací data. Seskupování atributů do instancí (kombinovaný model #EO2) Množina dokumentů

Trénovací data VP (%) VR (%) VS (%)

Testovací data VP (%) VR (%) VS (%)

Katalogové stránky Detailové stránky

97,61 85,87

86,20 30,35

91,60 45,80

92,13 93,18

61,04 39,21

73,32 55,20

Celkem

93,55

66,90

78,01

92,75

48,81

63,96

Tabulka 4.4.: Nabídky notebooků: úspěšnost seskupování atributů do instancí. Pro měření byly využity Vilainovy metriky.

45

5

Kapitola 5.

Extrakce pracovních nabídek

Předmětem této úlohy je extrahovat pracovní nabídky z firemních stránek. Extrakčním cílem jsou název pracovní pozice, lokalita a několik málo dalších údajů, které se v nabídkách nejčastěji vyskytují. Stejně jako u produktových nabídek byly vytvořeny 2 extrakční ontologie, které se navzájem liší použitými extrakčními znalostmi. První extrakční ontologie (EO#1) využívá pouze ručně zadaná pravidla, zatímco druhá ontologie (EO#2) kombinuje expertní znalost se znalostmi indukovanými pomocí značkovače sekvencí CRF. Realizace úlohy byla provedena ve stejných krocích jako u produktových nabídek. Ruční anotace dokumentů zabrala podobně jako u produktových nabídek přibližně jeden člověkotýden. Ačkoliv bylo označkováno mnohem méně příkladů, bylo pro to nutné použít mnohem více dokumentů. Přibližně každý třetí dokument byl buď nerelevantní nebo se jednalo sice o kariérní stránku, ale nenacházela se na ní žádná pracovní nabídka. Rovněž bylo zapotřebí více pozornosti, pracovní nabídky se často ztrácely v nepřehledném textu. Přestože předmětem extrakce je jen několik málo atributů, vytváření extrakčních pravidel bylo časově náročné a zabralo přibližně 8 člověkodní. V tom je započítána i tvorba slovníku profesí, který byl nezbytný pro nalezení názvů pracovních pozic. Stejně jako v prvním případě, vynaložený čas nelze z výše popsaného důvodu jednoznačně určit.

5.1. Popis domény Firemní stránky (resp. kariérní stránky firem, na kterých jsou pracovní nabídky nejčastěji uvedeny) jsou minimálně strukturované a text se na nich většinou nachází ve formě odstavců souvislých vět. V ideálním případě je popis nabídky strukturován bodově pomocí hesel (či krátkých vět) a je rozčleněn do více logických částí, přičemž každá logická část má svůj nadpis (např. „pracovní náplň“, „požadavky na zaměstnance“ a „nabídka zaměstnavatele“). Příklad takové stránky je na obrázku 5.1. Tento typ nabídek je ale v menšině.

47


Obrázek 5.1.: Částečně strukturovaná pracovní nabídka. Nabídka je členěna do tří logických částí, každá obsahuje nadpis. Pro firemní stránky pak narozdíl od e-shopů platí, že namísto profesionálních webových prezentací se často jedná o (polo)amatérské počiny – mohou je snadno vytvářet sami zaměstnanci firmy v nějakém WYSIWYG editoru nebo lidé, kteří se vytvářením amatérských stránek pro menší firmy živí „ve volném čase“. Nedostatečné znalosti nebo zkušenosti pak mohou vést k nevalidnímu kódu stránek, špatné strukturovanosti či prostě jen nepřehlednosti obsahu. Oproti e-shopům se zde tak vyskytuje mnohem větší množství typografických chyb. Komerční web je pomocí automatických metod mnohem lépe zpracovatelný, v případě produktových nabídek je ale spíše zapotřebí analyzovat přirozený jazyk – formátovací struktura je zde využitelná minimálně. V některých případech jsou dvě nabídky pracovních míst sloučeny do jediné nebo se vzájemně „kříží“. Kupříkladu mohou mít společný popis pracovní náplně – třeba ve formě jednoho odstavce – ale požadavky na zaměstnance jsou rozepsány zvlášť pro každou pozici. Správné seskupení atributů do instance je komplikováno množstvím přípustných permutací atributů. Příznačné je to především pro méně strukturované či nestrukturované nabídky ve formě volného textu. Na stránce se může nalézat méně, stejně i více lokalit než kolik je nabízených pracovních míst. Ve všech případech platí, že každá pracovní nabídka může mít libovolný počet lokalit a zároveň jedna lokalita se může vztahovat k více nabídkám (vztah typu M:N). Možný je souvýskyt obou atributů, aniž by k sobě patřily. Zjištění lokality, která se k dané nabídce vztahuje, je v některých případech obtížné (či nemožné) i pro člověka – zvlášť pokud není

48

Dataset a ruční anotace

přímo zmíněna v rámci dané nabídky, ale někde dále v textu se nachází jen kontakt na danou firmu (to může být správná lokalita i nemusí). V další části této kapitoly budu souběžně používat tři pojmy: povolání, profese a (název) pracovní pozice. Povoláním nebo profesí je v této práci myšlen primárně jednoslovný název (ve formě podstatného jména), který označuje nějaký druh pracovní činnosti. Například architekt, grafik, ekonom, inženýr nebo právník. Pojem pracovní pozice se více vztahuje ke konkrétním pracovním nabídkám a zpravidla se jedná o konkrétnější (speciálnější) varianty názvů povolání (resp. profesí). První dva pojmy tedy používám v obecnějším smyslu.

5.2. Dataset a ruční anotace Dataset kariérních stránek firem byl poskytnut firmou Dain s.r.o. Více než 9 tisíc stránek bylo získáno pomocí crawleru z množiny předem známých internetových domén firem a společností. Dataset obsahuje jak relevantní, tak nerelevantní dokumenty. Trénovací i testovací množina byla z celého datasetu vybrána náhodně (pomocí funkce random v databázovém systému MySQL). Součástí trénovací i testovací sady jsou rovněž dokumenty, které neobsahují žádnou pracovní nabídku (pro vyhodnocení robustnosti ontologie).

Značka

#

Značka

#

Název pozice

373

Vzdělání

175

Lokalita

207

Jazykové znalosti

92

Pracovní poměr

58

Řidičské oprávnění

51

Platové podmínky

10

Délka praxe

42

Termín nástupu

52

Tabulka 5.1.: Pracovní nabídky – extrahované typy informací. Ručně označkované hodnoty pro celý dataset.

Narozdíl od produktových nabídek bylo mnohem obtížnější rozhodnout, jaké hodnoty atributů ještě anotovat a které už ne. Samotný výskyt některých hodnot atributů neznamená, že jde vždy o pozitivní příklady. Např. výskyt hodnoty „němčina“ ve výrazu “znalost němčiny výhodou” neznamená, že je němčina po uchazeči vyžadována. Pro rozlišování těchto nuancí by bylo zapotřebí definovat další atribut a především taková pravidla, která by uměla extrahované hodnoty dát do správné relace (viz věta „povinná znalost anglického jazyka, němčina výhodou“). Jedná se tedy spíše o úlohu extrakce relací. V tomto případě by šlo ale rovněž použít jeden atribut pro každý cizí jazyk a oborem hodnot by byly „míry nutnosti“. Všechny názvy pracovních pozic byly anotovány tak, aby jedno označení odpovídalo jednomu pracovnímu místu (pozici), bez ohledu na interpunkční znaménka.

49


Pracovní nabídky

Hodnoty atributů (#)

Instance (#)

Trénovací data

Testovací data

Trénovací data

Testovací data

701

359

189

116

Tabulka 5.2.: Základní údaje o datasetu firemních stránek.

5.3. Klíčové otázky V této úloze je klíčovým atributem název pracovní pozice. Ten obvykle tvoří jedna či více profesí a případně další podpůrná slova, která rozvíjejí profesi. V ojedinělých případech je pozice popsána pouze pomocí konkrétní činnosti (např. úklidové práce). Množina přípustných názvů pracovních pozic je přitom v podstatě nekonečná, kromě názvů povolání mohou obsahovat v podstatě libovolná slova. Názvy profesí (a další údaje) se na kariérních stránkách přirozeně vyskytují v libovolných slovních tvarech. Je tedy nutné respektovat tvarosloví. Pro oblast pracovních nabídek jsou stěžejní následující otázky: • jak rozpoznat relevantní dokument a jeho relevantní část • jakým způsobem popsat celý název pracovní pozice – jak interpretovat čárku/lomítko, které v textu oddělují profese – koreferenční rozhodnutí • jak přiřadit správnou lokalitu k názvu pracovní pozice • jak seskupit nalezené hodnoty do nabídek, jestliže je pořadí atributů různé První bod se týká opět klasifikace stránek. Mnohem více než u notebooků zde hrozí záměna názvů pracovních pozic s názvy povolání/profesí, které se netýkají pracovní nabídky. Základním problémem je skutečnost, že pro vytvoření instance pracovní nabídky postačuje název pozice bez jakýchkoliv dalších údajů. Vynucení kontextového vzoru, který by vymezoval některá typická slova v okolí pozice, je nepoužitelný, protože pozice se nacházejí v podstatě v libovolném kontextu. Vhodnější by tedy bylo pro klasifikaci stránek využít typických slov, jež se nacházejí v pracovních nabídkách. Bylo ověřeno, že relevantní stránka lze poměrně snadno detekovat pomocí nadpisů, které obsahují slova jako „Kariéra“, „Zaměstnání“ nebo „Volná místa“. V dalším kroku by bylo vhodné najít začátek a konec tzv. obsahové oblasti dokumentu, ve které se nachází hlavní text dané stránky. Zbavit se postranních menu a jiných lišt může být žádoucí kvůli snadnější desambiguaci hodnot atributů jako název povolání. V rámci této práce není klasifikace stránek řešena, stejně jako nejsou využívány odkazy na detailní popisy pozic (jsou-li k dispozici). V případě oddělení více profesí pomocí lomítka (eventuálně pomlčky) je pravděpodobněji zamýšleno jediné pracovní místo (více použitých profesí může sloužit pro přesnější specifikaci

50


pozice). Např. „asistentka vedení společnosti/asistentka jednatele“. Čárka mezi profesemi zase naopak spíše odděluje různé pracovní pozice, ale nejde o pravidlo. U rozpoznávání sémantiky interpunkčního znaménka je mj. důležitý kontext:

“na pozici skladník, řidič” (1 pracovní místo) “na pozice skladník, řidič” (2 pracovní místa)

V systému Ex nelze používat jako oddělovač hodnot nějaké slovo (literál). Problém by byl částečně řešitelný vymezením kontextu se 100 % pokrytím, který by vynucoval přítomnost oddělovače (třeba čárky) zleva nebo zprava a zároveň by příslušný obsahový vzor nesměl tento znak (oddělovač) definovat. Pak by ale nebylo pravidlo aplikovatelné na všechny ostatní hodnoty bez přítomnosti těchto oddělovačů. Pokud tedy nejsou pracovní pozice odděleny podle interpunkčních znamének, pak v některých případech dojde k chybnému sloučení dvou různých pozic, v opačném případě zase k možnému rozdělení jedné pozice. Rozhodování, která varianta z obou uvedených je akceptovatelnější, je volbou preference mezi přesností a úplností. Definovat pomocí JavaScriptových funkcí koreferenční rozhodnutí pro názvy pracovních pozic je velmi obtížný až neřešitelný úkol. I částečná shoda dvou řetězců může znamenat dvě různá pracovní místa. Více jsem se tedy této úloze nevěnoval. K tomu je mj. zapotřebí lépe porozumět textu. V neposlední řadě je důležité rozpoznat, která z nalezených lokalit se vztahuje k uvedenému pracovnímu místu (v případě extrahování kontaktních informací bychom měli rovněž doplňující informaci o tom, kde daná firma sídlí a případně by šla tato hodnota prohlásit za lokalitu dané pozice). Na stránce se mohou vyskytovat rovněž další lokality, které se nemusí vztahovat ani k pracovní nabídce, ani k sídlu firmy.

5.4. Vytváření extrakční ontologie Ontologická třída definující pracovní nabídky je tvořena 10 atributy (z toho jeden odvozený), které v součtu obsahují 82 ručních vzorů a 4 axiomy. Jediným povinným atributem je název pracovní pozice. Důvodem je rozmanitost údajů obsažených v jednotlivých pracovních nabídkách – od nabídek obsažených v jediné větě („Hledáme nové pracovníky na pozici kuchař nebo číšník“) až po nabídky strukturované do několika částí (obrázek 5.1).

51


Obrázek 5.2.: Schéma třídy Pracovní nabídka. Jediný povinný atribut (název pozice) je vyznačen tučně. Uzly vycházející z kořenu představují atributy, uzly vycházející z těchto atributů jsou specializované atributy. Kardinalita vztahu je vyjádřena dvojicí čísel. Lokalita může být libovolná obec nebo region (okres či kraj). Atribut pracovní poměr popisuje typ smluvního vztahu mezi zaměstnancem a zaměstnavatelem, resp. typ úvazku. Požadovaný počet let praxe uchazeče v daném oboru je vyjádřen pomocí atributu délka praxe. Jazykové znalosti se vztahují k několika málo cizím jazykům. Oborem hodnot atributu dosažené vzdělání je pak stupeň vzdělání, resp. typ školy – ZŠ/SŠ/VŠ/SOU/ÚSO apod. Atribut řidičské oprávnění popisuje skupiny řidičského průkazu. Atributy název pozice a lokalita nejsou podmíněny okolním kontextem. To znamená, že dané kontextové vzory jsou nastaveny na takové odhady, že i při jejich nesplnění a za současného splnění obsahového vzoru jsou hodnoty extrahovány. Ve výsledku jsou tak v podobě vyšší míry spolehlivosti zvýhodněny ty hodnoty, které rovněž odpovídají kontextovému vzoru. Ve fázi postprocessingu je tuto hodnotu možné zužitkovat a méně spolehlivé předpovědi např. předkládat anotátorovi ke kontrole. Některé atributy jsou naopak podmíněny výskytem obsahového (obsahových) i kontextového (kontextových) vzorů. Dále jsou atributy, které nemusí splnit pozitivní kontext, ale mají vymezený negativní kontext – v případě jeho splnění není hodnota extrahována.

5.4.1. Slovníky Jedinou pojmenovanou entitou je v této úloze lokalita. Pro pokrytí většiny obcí České republiky byl použit volně dostupný slovník1 na internetu, který obsahuje více než 6000 názvů českých obcí. Obor hodnot atributu Název pozice je v podstatě nekonečný, stěží lze tedy vytvořit seznam slov, který by pokrýval všechny názvy povolání a pozic. Jako jediný použitelný slovník jsem shledal katalog Národní soustavy povolání 2 , který obsahuje více než 2600 pracovních pozic včetně nejrůznějších údajů. Katalog vytváří rovněž určitou hierarchii povolání (nachází se 1 2

http://blok.net-vor.cz/kompletni-seznam-mest-a-obci-cr/ http://katalog.nsp.cz/

52


v něm vztahy nadřazenosti-podřízenosti). Bohužel ani tento slovník nebyl přímo použitelný pro extrakci názvů pozic z textu, protože uvedená povolání byla z většiny příliš specifická – ve smyslu velmi dlouhých názvů (některé měly i více než 10 slov). Jedná se tak spíše o standardizovanou terminologii, ve které je důležitá výstižnost a jednoznačnost. Na kariérních stránkách se přitom názvy vyskytují v jednodušších tvarech anebo pak v nejrůznějších „novotvarech“ (výjimkou nejsou anglické ekvivalenty), které nejsou pro změnu zahrnuty v katalogu NSP. Jako jediné přijatelné řešení se tedy zdálo „vytáhnout“ z tohoto slovníku všechny možné výskyty povolání (tj. podstatná jména) a posléze vymyslet způsob, jak pomocí základních (tj. jednoslovných) povolání nalézt v textu celé názvy pracovních pozic. Stránky Národní soustavy povolání umožňovaly přímý export katalogových dat do formátu XML včetně vlastního výběru údajů. Exportovány byly pouze takové položky, které se týkaly názvů pozic. Pro identifikaci podstatných jmen byl použit morfologický nástroj FMorph3 , který umožňuje provádět morfologickou analýzu a derivovat slovní tvary. V dodaném slovníku nebyla ovšem většina povolání obsažena, proto bylo zapotřebí vymyslet jiný způsob. Kromě manuálního čtení a značkování se nabízel alespoň zčásti automatický způsob: sepsat typická zakončení povolání a použít je na daný dataset. K tomu byly využity standardní funkce pro práci s řetězci a regulární výrazy ve skriptovacím jazyce PHP. Předpokladem byla skutečnost, že vygenerovaný XML soubor obsahující pouze názvy povolání bude obsahovat minimum běžných slov přirozeného jazyka. S pomocí 27 koncovek (o délce jednoho až tří znaků) byl získán seznam 450 povolání. Ve druhém kroce byla sepsána pravidla pro přechylování získaných slov z mužského rodu na ženský. Výsledný slovník byl nadále porovnán s datasetem získaným ze stránek Jobs.cz4 pomocí jednoduchého wrapperu typu LR napsaného rovněž v PHP. Dataset obsahoval celkem 13 tisíc názvů pracovních pozic. Porovnání probíhalo v několika krocích: nejprve byla provedena tokenizace jednotlivých záznamů (názvů) ze stránek Jobs.cz včetně odstranění nepotřebných znaků (interpunkčních znamének) a stopslov5 . Ve druhém kroce byly odstraněny všechny záznamy, ve kterých byla nalezena alespoň jedna známá profese (z vytvořeného slovníku). Slova ze zbývajících záznamů byla seřazena dle frekvence a vybrány (ručně) byly pouze ty, které odpovídaly nějakým profesím. Většinou šlo o anglické ekvivalenty. Tímto způsobem byl původní slovník rozšířen rovněž o slova používaná „v praxi“ – celkem se jednalo o 120 slov. Finální verze slovníku (resp. seznamu slov) tedy obsahuje celkem 1001 jednoslovných názvů povolání. Provedením morfologické analýzy vytvořeného slovníku pomocí nástroje FMorph bylo zjištěno, že FMorph „zná“ pouze 276 získaných názvů profesí. Vytvořený slovník je tak velmi komplexní, ale je nutno poznamenat, že se v něm nacházejí rovněž velmi specifické profese (ve smyslu ojedinělé, málo známé či již pomalu neexistující povolání) a mnoho názvů profesí v ženském rodě se jen stěží kdy objeví v pracovní nabídce (resp. se tyto tvary nepoužívají). Existují rovněž povolání, která jsou složená z více obecných slov (např. „zdravotní 3

http://ufal.mff.cuni.cz/pdt/Morphology_and_Tagging/Morphology/index.html http://www.jobs.cz 5 Jako stopslova se při počítačovém zpracování přirozeného jazyka označují slova, které se v daném jazyce vyskytují často, ale nenesou žádnou významovou informaci, mají zpravidla pouze syntaktický význam. Typicky se jedná o spojky, předložky atp. 4

53


sestra“) a odebráním těch slov, které rozvíjejí podstatné jméno, se vytrácí význam („sestra“ již neodkazuje k povolání). Podobně obecná jsou slova jako „pracovník“ nebo „spolupracovník“, která se používají velmi často, ovšem většinou ne v kontextu pracovní nabídky. Několik málo takových obecných slov bylo během experimentů se slovníkem odstraněno (vedly k falešně pozitivním příkladům).

5.4.2. Název pracovní pozice

Extrakce názvů pozic využívá formátovací strukturu stránky a vytvořený slovník profesí. V případě strukturovanosti textu na stránce jsou jednotlivé informace odděleny formátovacími prvky jazyka HTML. Se slovníkem pozic jsou tedy porovnávána jednotlivá slova mezi dvěma libovolnými HTML tagy (bez ohledu na to, zda jsou počáteční nebo ukončovací) a v případě shody některé dvojice porovnávaných slov lze extrahovat celý obsah tagu a označit jej za pracovní pozici. Za hranice názvu pracovní pozice jsou tedy považovány HTML značky – ať už jde o blokový element (DIV, P), odkaz (A) nebo odsazení na nový řádek (BR). Jedná se tak v podstatě o jednoduchý „wrapper“, který provádí extrakci na úrovni tagů. Extrakční pravidlo je omezeno pouze délkou okolí nalezené profese (5 tokenů na levé a 10 tokenů na pravé straně). Pokud není v jednom ze směrů v rámci povolené vzdálenosti nalezen žádný formátovací tag, k extrakci obsahu mezi dvěma tagy nedojde. V takovém případě se jedná pravděpodobně o volný text (delší větu). Protože dopředu nemáme jinou informaci než název pozice, nelze přesně určit začátek ani konec pracovní pozice. Tento přístup tedy není možné aplikovat na volný text. Základním předpokladem tohoto pravidla je skutečnost, že některé formátovací prvky jsou z hlediska významnosti obsaženého textu relevantnější než jiné. Jedná se především o tagy, které přiřazují textu nějaký vizuální efekt bez ohledu na použití kaskádových stylů – tj. nadpisy (H1 až H6), titulek stránky, zvýraznění textu (tučné písmo, kurzíva) či hyperlink. Spoléháno je tedy na „kvalitní“ HTML strukturu, kde se mezi každými dvěma tagy nachází pouze jeden typ informace. Obecně lze předpokládat, že pokud jsou použity HTML značky v okolí nějakého textu, je to kvůli jeho vizuálnímu oddělení od zbytku textu. Přestože vizuální podoba dokumentu je již definována převážně pomocí kaskádových stylů (CSS), stále je nutné v HTML dokumentu nejprve vytvořit formátovací značku a na daný styl se odkázat (resp. je na něj odkázáno pouze uvedením této značky). Podstatné zde přitom není, jak daný text uvnitř tagu vypadá, ale že je oddělen. Názorná ukázka pracovních nabídek, ze kterých je možné pouze s pomocí slovníku profesí extrahovat celé názvy pozic se 100 % úplností a 100 % přesností, je uvedena na obrázku 5.3. Níže je uveden rovněž odpovídající HTML kód stránky.

54


Obrázek 5.3.: Příklad pracovní nabídky s vizuálně odděleným názvem pracovní pozice (tučné písmo). Níže je uveden odpovídající HTML kód.

Specialista stavebního spoření (nutná praxe v oboru alespoň dva roky)
zpracovává poptávky všech našich klientů na stavební spoření a úvěry ze stavebního spoření. ...

Hypoteční makléř ...

Finanční / Pojišťovací specialista ...

Výhodou tohoto „naivního“ přístupu je skutečnost, že nejsou zapotřebí trénovací data, ale jen slovník profesí. Pokud bychom chtěli využít statistické metody strojového učení pro značkování sekvencí, bylo by zapotřebí obrovské množství dat a stále by nebyla množina možných pracovních pozic zcela pokryta. Další alternativou je využití transformačních pravidel (např. algoritmus LP 2 ), stále jsou ale zapotřebí ručně označkovaná data. Výše uvedená strategie by mohla být dále vylepšena o slovníky obsahující typické začátky a konce pracovních pozic6 . Případně pak také o seznamy slov, které se nacházejí bezprostředně před názvem pozice (resp. po názvu pozice) – k tomu už jsou ale zapotřebí trénovací data (nebo mít ke zmíněným údajům vyparsovaných z agenturních stránek odkaz na původní zdroj a tím získat kontext automaticky).

5.4.3. Seskupování atributů do instancí V případě pracovních nabídek lze pomocí pravidel jen obtížně reagovat na proměnlivé pořadí atributů v rámci instancí. Je tak použito jedno základní pravidlo stanovující jako začátek instance název pracovní pozice, pár dalších pravidel pak negativně vymezuje, jakými atributy 6

Takové údaje lze získat i nesupervizovaně, např. již zmíněným parsingem agenturních stránek jako Jobs.cz, které obsahují tisíce názvů pracovních pozic, byť s určitým šumem.

55


(či posloupností atributů) instance nesmí začínat. Jde o relativně volná pravidla, pracovní nabídka nemusí nutně začínat pracovní pozicí (byť je této možnosti přiřazena nejvyšší pravděpodobnost). V případě, že je nabídka strukturovaná a rozdělena do více částí, které začínají příslušným nadpisem (viz obrázek 5.1), lze se řídit podle těchto nadpisů, které se v celé doméně příliš nemění. Nejčastější jsou části popisující pracovní náplň, požadavky na uchazeče a nabídku zaměstnavatele. Pořadí těchto částí je libovolné, ne vždy jsou uvedeny všechny. Přesto je tento případ o to jednodušší, že název pracovní pozice je uveden jako první a pomocí nadpisů jako „Popis práce“, „Požadujeme“ či „Nabízíme“ lze lépe „kontrolovat“ obsah popisu nabídky. Je tak možné zabránit případům, kdy se promíchají hodnoty atributů různých instancí, které spolu sousedí. Jak bylo řečeno výše, název pracovní pozice není vynucován jako začátek pracovní nabídky (narozdíl od notebooku) a tedy instance může začínat i jiným atributem. Je tedy přinejmenším vhodné pomocí nějakého pravidla omezit počet takto zpřeházených hodnot. Zde popisované pravidlo, které tento problém zčásti řeší, vymezuje začátek a konec instance pomocí výše uvedených nadpisů: <pattern p="1" cover="0.5" type="pattern" ignore="case" cond="all"> ^ $job_title * $tmp_word * $tmp_word * $tmp_word?

Pomocí parametru cond lze zajistit, že dané pravidlo bude aktivní pouze v případě nálezu nadpisů (atribut tmp_word popisuje 10 různých nadpisů). Znak stříšky označuje začátek instance. Opět je možné omezit obor tohoto atributu pomocí formátovacích značek, aby nedocházelo k detekci definovaných slov uprostřed volného textu.

5.5. Trénování CRF modelu Název pracovní pozice je modelován jako „začátek názvu pozice“ a „pokračování názvu pozice“ (jde o výchozí nastavení Exu, které nelze v konfiguračním souboru přenastavit). V tomto případě by ale patrně bylo vhodnější modelovat pracovní pozici s pomocí více tříd – přidána by mohla mohla být ještě třída pro „konec pozice“: B-JOB_TITLE – I-JOB_TITLE – E-JOB_TITLE V případě CRF a dalších statistických metod ovšem platí, že je pro vytvoření kvalitního modelu nutný dostatek označkovaných dat. V případě atributu s téměř neomezeným oborem hodnot by patrně dobrých výsledků nebylo dosaženo ani s velkým množstvím trénovacích dat. Pro vyjádření vnitřní stuktury názvů pracovních pozic by tak bylo vhodnější použít transformační pravidla. Pro potřeby této práce tedy bylo lepší ponechat extrakci pracovních pozic „naivnímu“ přístupu pomocí okolních HTML značek. Bylo vytvořeno několik CRF modelů, všechny ale z hlediska hodnocení na testovací množinš lišily o desetiny procent. Nejlépe dopadl model, ke kterému byl použit zredukovaný trénovací soubor, tedy opět mítným znevýhodněním majoritní třídy (nezajímavá slova na pozadí). Z

56

Vyhodnocení

původního počtu více než 25 tisíc řádků zůstala přibližne třetina. Atributy byly využity všechny, celkem 20 tříd tak odpovídá 1 362 příkladům.

Velikost trénovacích dat: 8 587 příkladů Počet příkladů odpovídající značkám: 1 362 Celkový počet vygenerovaných příznaků: 846 770 (bez prořezání) Hyper-parameter: 1.00 Error rate: 0.00023 Počet iterací: 145 Celkový čas: 1,5 minuty

5.6. Vyhodnocení

Při vyhodnocování úspěšnosti pracovních nabídek je vhodné zaměřit se spíše na problémové atributy. Celková F-míra je zčásti zkreslená atributy, jejichž obor hodnot je malý a údaje jsou tedy snadno dohledatelné a v čase neměnné. Mezi tyto atributy patří především řidičský průkaz (ve více jak 95% případů jediná hodnota „B“ a v kontextu se střídají 3-4 varianty), ale i atributy jako vzdělání, jazykové znalosti nebo pracovní poměr. Pro jednoznačnou identifikaci identity těchto hodnot vystačí vymezit v kontextu několik málo slov. Pracovní nabídky jsou na celém českém webu psány vesměs stejným „jazykem“. Pro správnou interpretaci výsledků je opět dobré uvědomit si skutečnost, že názvy pozic i lokalit jsou popsány pomocí seznamů slov, nikoliv pomocí pravidel, která by byla závislá na trénovacích datech. I proto je zajímavější uvést výsledky pro obě množiny dokumentů. To platí i pro seskupování atributů, kde je možné počítat trénovací a testovací data jako jediný dataset. Pravidla vytvořená pro seskupování vychází z osobní zkušenosti, nikoliv z pozorovaných dat. Byly použity stejné metody vyhodnocení jako u produktových nabídek.

57


Pracovní nabídky (trénovací data) Atribut

#

P (%)

EO#1 R (%)

Název pozice (S) Název pozice (L) Lokalita (S) Lokalita (L) Pracovní poměr Platové podmínky Termín nástupu Vzdělání (S) Vzdělání (L) Jazykové znalosti Řidičské oprávnění Délka praxe

230 230 150 150 39 10 31 118 118 57 35 31

71,35 84,38 66,17 83,46 100 87,5 100 97,65 100 98,28 100 100

59,57 76,96 58,67 68,57 66,67 70,00 93,55 77,97 81,29 100 94,29 80,65

64,93 80,5 62,19 75,29 80,00 77,78 96,67 86,7 89,68 99,13 97,06 89,29

73,49 85,12 66,17 83,46 100 75,00 100 96,3 99,41 98,28 100 96,77

68,7 86,09 58,67 68,57 69,23 90,00 93,55 88,14 93,64 100 94,29 96,77

71,01 85,60 62,19 75,29 81,82 81,82 96,67 92,04 96,44 99,13 97,06 96,77

+6,08 +5,1 +1,82 +4,04 +5,34 +6,76 +7,48

Průměr (S) Průměr (L)

701 701

81,79 90,73

70,47 78,86

75,71 84,38

82,82 90,77

76,32 85,07

79,44 87,83

+3,73 +3,45

F (%)

P (%)

EO#2 R (%)

F (%)

4F (%)

Tabulka 5.3.: Vyhodnocení atributů pro pracovní nabídky (trénovací data).

Pracovní nabídky (testovací data) Atribut

#

P (%)

EO#1 R (%)

Název pozice (S) Název pozice (L) Lokalita (S) Lokalita (L) Pracovní poměr Termín nástupu (S) Termín nástupu (L) Vzdělání (S) Vzdělání (L) Jazykové znalosti Řidičské oprávnění Délka praxe

143 143 57 57 19 21 21 57 57 35 16 11

74,11 86,63 35,79 43,68 91,67 93,75 100 96,15 96,15 97,22 100 100

58,04 73,76 59,65 67,38 57,89 71,43 74,83 87,72 87,72 100 87,50 72,73

65,10 79,68 44,74 53,00 70,97 81,08 85,60 91,74 91,74 98,59 93,33 84,21

74,34 86,75 35,79 43,68 100 93,75 100 94,23 95,73 97,22 100 100

58,74 74,46 59,65 67,38 57,89 71,43 74,83 85,96 88,54 100 87,50 100

65,63 80,14 44,74 53,00 73,33 81,08 85,60 89,91 91,99 98,59 93,33 100

+0,53 +0,46 +2,36 -1,83 +0,25 +15,79


359 359

72,25 78,77

68,87 76,47

70,52 77,60

72,49 79,17

69,70 77,70

71,07 78,43

+0,55 +0,83

F (%)

P (%)

EO#2 R (%)

F (%)

4F (%)

Tabulka 5.4.: Vyhodnocení atributů pro pracovní nabídky (testovací data). CRF model pomohl pouze u trénovacích dat, naučené znalosti ale nebyly úspěšně aplikovány na neznámá data. To je dáno kombinací atributů, které jsou snadno specifikovatelné extrakčnimi pravidly a zároveň atributů, které obsahují obrovské množství přípustných hodnot. Výsledky extrakce názvu pozice potvrzují, že statistické metody strojového učení nejsou

58

Vyhodnocení

v případě velké proměnlivosti vnitřní struktury hodnot příliš vhodné, resp. nejsou vhodné (při nízkém počtu označkovaných příkladů). Na trénovacích datech CRF model pomohl extrahovat o 21 více pracovních pozic. U testovacích dat to pak už byla jediná vylepšená hodnota (ze 143)7 . Celkem bylo ručně označkováno 373 pracovních pozic. Pomocí kombinovaného modelu bylo úspěšně extrahováno celkem 67,05 % hodnot (ve striktním módu), s přesností 73,1 % a úplností 61,93 %. Tento způsob extrakce názvů pozic pomocí HTML značek byl aplikován rovněž na celý dataset od firmy Dain s.r.o. Z více než 9600 dokumentů bylo extrahováno přes 12600 názvů pracovních pozic. V příloze je ukázka výstupních dat. Druhý stěžejní atribut dosáhl na testovacích datech podstatně horších výsledků. Slovník obcí doplněný o seznam českých okresů a krajů nepokryl všechny výskyty lokalit pravděpodobně z důvodu tvarosloví a výskytu zkratek („Ústí nad Labem“ vs. „Ústí n. L.“ apod.). Průměrná úspěšnost extrakce instancí je pro trénovací data téměř 75%. Na testovacích datech je to méně, ačkoliv v průběhu vytváření extrakční ontologie bylo rovněž dosaženo F-míry 74%. Postupným přidáváním nových pravidel a úpravou stávajících se za současné rostoucí úspěšnosti extrakce atributů současně snižovala úspěšnost extrakce instancí. Seskupování atributů do instancí Model

Trénovací data VP (%) VR (%) VS (%)

Testovací data VP (%) VR (%) VS (%)

#EO1 #EO2

65,44 70,03

83,56 82,55

73,40 75,77

67,71 68,53

69,73 62,84

68,71 65,56

Celkem

67,63

83,54

74,75

68,10

66,28

67,18

Tabulka 5.5.: Pracovní nabídky: úspěšnost seskupování atributů do instancí. Pro měření byly využity Vilainovy metriky.

7

V trénovací a testovací množině dokumentů se nachází 10 zcela identických názvů pracovních pozic.

59

6

Kapitola 6.

Závěr

6.1. Shrnutí provedených experimentů Množství existujících a různorodých přístupů poukazuje na fakt, nakolik je extrakce informací komplexní úlohou, při níž je zpravidla využití jediného přístupu nedostačující. V doméně produktových nabídek by podstatně pomohla automatické detekce datových záznamů, neboť seskupování hodnot do objektů podle pravidel je poměrně komplikované. V oblasti pracovních nabídek by pak pomohlo využití lingvistických metod, což bylo nad rámec této diplomové práce. Vizuální informace by se pak dala využít k nalezení obsahové části na stránce. Jak lze vidět, pro vyšší úspěšnost by byla vhodná kombinace všech uvedených přístupů (lingvistické metody, extrakční ontologie, formátovací struktura, vizuální informace) a stejně tak kombinace ručně vytvořených pravidel s metodami supervizovaného učení. Přístup založený na extrakčních ontologiích se ukázal jako velmi všestranný. To s sebou nese i určité požadavky. Na straně jedné je zapotřebí porozumět problematice metod strojového učení, na straně druhé vyžaduje tento přístup důkladnou analýzu dané domény a zkonstruování odpovídajících pravidel. Časově nákladné je nejen vytváření těchto pravidel, ale i jejich údržba. Systém Ex se pak ukázal jako vhodný nástroj především pro extrakci produktových nabídek. Výhodou kombinace pravidel (v podobě regulárních výrazů) a statistického přístupu je ten, že není nutné často přetrénovávat CRF model. Díky obecným vzorům pro tyto atributy by měl extrakční model být robustní i bez častějších změn. Pochopitelně čím vyšší závislost atributů na daném CRF modelu, tím častěji je nutné ho aktualizovat. S rostoucím počtem atributů v ontologické třídě se stává problematičtější jejich seskupování do objektů a tedy klesá celková úspěšnost. Pro dynamicky generované záznamy z databází podle určité šablony (např. produktové katalogy) se jeví vhodnější využití nějaké automatické metody, která umožňuje detekovat datové záznamy na základě podobnosti (opakující se formátovací struktury). Zajímavé by bylo rovněž porovnání algoritmu CRF++ s algoritmem SMO ze systému Weka. Generování trénovacího souboru z množiny dokumentů bylo bohužel v případě druhého jmenovaného algoritmu nefunkční, zaměřil jsem se tedy pouze na algoritmus CRF++. Stejně

61

Závěr

tak jsem v systému Ex nevyužil indukci formátovací struktury. Nejde o klasickou indukci wrapperů, systém pouze zvyšuje pravděpodobnost extrakce hodnot v tabulce, pokud byly ve stejném sloupci v okolních řádcích extrahovány jiné hodnoty. V obou úlohách by se přitom velmi hodila indukce formátovací struktury v okolí nadpisů, ve kterých se nalézaly názvy notebooku, resp. názvy pracovních pozic. Z hlediska metod strojového učení je pro doménu produktových nabídek vhodný značkovač sekvencí, CRF pomohl zvýšit úspěšnost nejobtížněji specifikovatelných hodnot – model notebooku, název GPU a procesoru. V případě pracovních nabídek by byly vhodnější metody pro indukci gramatik. Extrakční pravidla popisující vnitřní strukturu pracovní pozice se zde hodí více než segmentační (sekvenční) přístup.

6.2. Využití extrakčních ontologií v doméně produktových nabídek U domény produktových nabídek je důležité uvědomit si, jakou úlohu může hrát v reálných aplikacích jediný extrakční model popisující jediný koncept. Protože je extrakční ontologie nezávislá na konkrétní formátovací struktuře, umožňuje extrahovat nabídky konkrétního produktu z heterogenních webových dokumentů s relativně vysokou úspěšností, jak bylo ukázáno v části 4.6. Tímto způsobem je pak ale možné snadno odhalit formátovací strukturu daného e-shopu a využít jí pro indukci wrapperů. Wrappery pak mohou být aplikovány na zbývající kategorie produktů. Třídy dokumentů v rámci e-shopu se většinou nemění a jsou pro všechny kategorie stejné. Automatické značkování produktových nabídek tak vlastně nahrazuje ruční anotaci, nutnou pro indukci wrapperů. Extrakční ontologie by tedy zde plnila úlohu „vstupní brány“ do daného e-shopu. Tímto způsobem lze pro všechny produktové nabídky v e-shopu snadno získat strukturované údaje jako název produktu, cenu, dostupnost a množství na skladě nebo produktový kód. Rovněž lze získat popisy produktů, ač jen ve formě nestrukturovaného textu. S danou extrakční ontologií je možné extrahovat všechny produktové nabídky z těch e-shopů, které prodávají produkt popsaný v ontologii. S ontologií popisující několik málo základních produktů by tak šlo zřejmě pokrýt rozhodující většinu e-shopů. Nebylo by obtížné detekovat ani případnou změnu formátování a automaticky vytvořit nové wrappery. Konkrétní parametry již jednou získaného produktu by bylo možné získat dodatečně, jak by přibývaly jednoduché extrakční ontologie popisující jednotlivé produkty (ať už ve formě pravidel a/nebo s pomocí statistického modelu CRF). Proces tvorby takových ontologií by bylo možné částečně automatizovat, pokud by existovaly odpovídající produktové ontologie (jako již zmíněná PTO). Granularitu údajů je možné zjemňovat již nyní u existujících strukturovaných dat (některé e-shopy používají např. zmíněnou ontologii GoodRelations). Výhodou obou zmíněných úloh je fakt, že by nebylo v této fázi nutné řešit seskupování hodnot do objektů (instancí tříd), neboť každý popis by odpovídal právě jednomu produktu. Tato úloha je klíčová jen při extrakci produktů z nového e-shopu. Ačkoliv výsledky prokázaly relativně vysokou úspěšnost seskupování hodnot do atributů v produktových katalozích pomocí přístupu „zdola nahoru“, vhodnější a obecně spolehlivější by bylo využití metod pro automatickou

62

Zhodnocení cílů

detekci datových záznamů, které navíc nevyžadují zásah uživatele. Bylo by proto velmi zajímavé využít již hotové ontologie a k tomu vyzkoušet nějaký systém pro indukci wrapperů. Tolik tedy k další motivaci, se kterou by bylo možné navázat na tuto práci.

6.3. Zhodnocení cílů Jestliže se na první pohled zdá, že vyhledat učité typy informací v textu je snadné, pokud dopředu známe jejich podobu, pak je to pravda jen do té chvíle, než chceme tyto data využít v reálných aplikacích. Obtížnost této úlohy roste s klesajícím množstvím informací o tom, jak požadované údaje „vypadají“ a v jakých souvislostech se v textu nacházejí, resp. s nemožností tyto „metainformace“ získat v rozumném čase a s rozumnými náklady. Cílem této práce přitom nebylo pouze vyzkoušet extrakční systém, ale získat kvalitní data, jež by byla dále strojově zpracovatelná a ve výsledku i užitečná. Vybraný extrakční systém byl pouze prostředek, jak tohoto cíle dosáhnout, a vše ostatní bylo nutné tomu podřídit. V průběhu nejrůznějších experimentů s datasetem jsem narazil na spoustu reálných problémů a vymýšlel občas „nekonečné“ varianty řešení i s pomocí jiných volně dostupných nástrojů. V této práci se bylo možné z hlediska omezeného místa věnovat pouze některým z nich. Definovaný cíl byl, myslím, u produktových nabídek splněn bez výhrad. Určité problémy se seskupováním hodnot do nabídek byly dány algoritmem, který patří ke slabším článkům jinak velmi komplexního systému. U pracovních nabídek byl cíl splněn pouze částečně, protože se nepodařilo úspěšně extrahovat místa pracoviště, které se k nabídkám vztahovaly. Napak dobrý základ byl položen v případě názvů pracovních pozic, které se dařilo navzdory jednoduchým a zjednodušujícím předpokladům extrahovat v dobré kvalitě.

63

Literatura [1] EMBLEY, David W., TAO, Cui, LIDDLE, Stephen W.: Automatically Extracting Ontologically Specified Data from HTML Tables With Unknown Structure. In Proceedings of the 21st International Conference on Conceptual Modeling, 2002, s. 322–337. ISBN 3-540-44277-4. [2] HALL, Mark, FRANK, Eibe, HOLMES, Geoffrey, PFAHRINGER, Bernhard, REUTEMANN, Peter, WITTEN, Ian H.: The WEKA Data Mining Software: An Update. SIGKDD Explorations, Volume 11, Issue 1, 2009. [3] CHANG, Chia-Hui, KAYED, Mohammed, GIRGIS, Moheb Ramzy, SHAALAN, Khaled: A Survey of Web Information Extraction Systems. In IEEE Transactions on Knowledge and Data Engineering, Vol. 18, Issue 10, 2006, s. 1411–1428. ISSN: 1041-4347. [4] KAISER, Katharina, MIKSCH, Silvia: Information Extraction. A Survey. Technical Report, Vienna University of Technology, Institute of Software Technology and Interactive Systems, 2005. [5] LABSKÝ, Martin, SVÁTEK, Vojtěch: On the design and Exploitation of Presentation Ontologies for Information Extraction. In: ESWC’06 -Workhshop 4: Mastering the Gap: From Information Extraction to Semantic Representation. Budva: KMI, The Open University, 2006. [6] LABSKÝ, Martin, NEKVASIL, Marek, SVÁTEK, Vojtěch, RAK, Dušan: The Ex Project: Web Information Extraction using Extraction Ontologies. In: Knowledge Discovery Enhanced with Semantic and Social Information. Springer, Studies in Computational Intelligence, Vol. 220, 2009. [7] LABSKÝ, Martin, SVÁTEK, Vojtěch, NEKVASIL, Marek: Information Extraction Based on Extraction Ontologies: Design, Deployment and Evaluation. In: Workshop on Ontology-Based Information Extraction Systems (OBIES-08), Kaiserslautern, 2008. [8] LAFFERTY, John, McCALLUM, Andrew, PEREIRA, Fernando: Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In Proceedings of the 18th International Conference on Machine Learning, 2001, s. 282-289. [9] LIU, Bing: Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data. 2nd edition. New York : Springer-Verlag, 2011. 622 s. ISBN 978-3-642-19459-7.

65

Literatura [10] MOENS, Marie-Francine: Information Extraction: Algorithms and Prospects in a Retrieval Context. New York : Springer, 2006. ISBN 1-4020-4987-0. [11] SHEN, Wei, WANG, Jianyong, LUO, Ping, WANG, Min: APOLLO: A General Framework for Populating Ontology With Named Entities via Random Walks on Graphs. In Proceedings of the 21st international conference companion on World Wide Web. New York : ACM, 2012, s. 595–596. ISBN 978-1-4503-1230-1. [12] SODERLAND, Stephen: Learning to Extract Text-Based Information from the World Wide Web. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining (KDD), 1997, s. 251–254. [13] ŠEVČÍKOVÁ, Magda, ŽABOKRTSKÝ, Zdeněk, KRŮZA, Oldřich: Zpracování pojmenovaných entit v češtině. Technická zpráva ÚFAL/CKL TR-2007-36. Praha : Univerzita Karlova v Praze, Matematicko-fyzikální fakulta, únor 2007, 60 s. Dostupné z WWW: [14] ZHAI, Yanhong, LIU, Bing: Web Data Extraction Based on Partial Tree Alignment. In Proceedings of the 14th international conference on World Wide Web. New York : ACM, 2005, s. 76–85.

66

A

Příloha A.

Výsledkové tabulky

I

Výsledkové tabulky

Nabídky notebooků (trénovací data)

#

P (%)

EO#1 R (%)

F (%)

P (%)

EO#2 R (%)

F (%)

4F (%)

Výrobce Řada (S) Řada (L) Model (S) Model (L) Produktový kód (S) Produktový kód (L) EAN kód Cena (S) Cena (L) Cena s daní (S) Cena s daní (L) Cena bez daně Dostupnost (S) Dostupnost (L) Množství na skladě Název CPU (S) Název CPU (L) Frekvence CPU (S) Frekvence CPU (L) Název GPU (S) Název GPU (L) Název IGP Grafická paměť Operační systém (S) Operační systém (L) Kapacita HDD Kapacita SSD Operační paměť Úhlopříčka displeje Rozlišení displeje Typ displeje Barva (S) Barva (L) Váha

505 362 362 505 505 158 158 4 258 258 164 164 31 161 161 79 396 396 133 133 255 255 72 190 343 343 343 22 372 425 144 33 258 258 29

93,54 93,00 95,61 79,37 91,11 89,33 90,46 0 91,69 92,13 98,47 100 100 78,33 79,31 98,70 85,43 89,29 80,28 80,99 73,06 82,69 81,93 90,62 80,12 86,35 87,60 100 88,96 80,58 98,47 64,10 92,59 92,59 70,27

94,65 91,71 94,11 79,06 89,08 42,41 43,04 0 99,61 100 97,56 98,95 96,77 98,76 99,54 96,20 75,51 77,77 85,71 86,02 55,29 59,50 94,44 76,32 79,01 84,09 95,04 36,36 75,81 79,06 89,58 75,76 87,60 87,60 89,66

94,09 92,35 94,86 79,22 90,08 57,51 58,33 0 95,49 95,9 98,02 99,47 98,36 87,36 88,28 97,44 80,16 83,13 82,91 83,42 62,95 69,20 87,74 82,86 79,56 85,20 91,17 53,33 81,86 79,81 93,82 69,44 90,03 90,03 78,79

93,54 94,68 95,61 86,08 94,03 92,24 92,97 0 91,69 92,13 98,47 100 100 78,33 79,31 98,70 86,39 88,55 80,28 80,99 87,05 88,34 81,93 90,73 82,98 86,17 87,60 100 85,06 81,06 98,47 64,10 91,63 92,40 70,27

94,65 93,37 94,75 85,91 89,40 67,72 68,35 0 99,61 100 97,56 98,95 96,77 98,76 99,54 96,20 96,21 99,22 85,71 90,53 94,90 96,27 94,44 97,89 91,25 94,42 95,04 36,36 94,89 93,41 89,58 78,79 93,80 94,06 89,66

94,09 94,02 95,18 85,99 91,66 78,10 78,78 0 95,49 95,90 98,02 99,47 98,36 87,36 88,28 97,44 91,04 93,58 82,91 85,49 90,81 92,13 87,74 94,18 86,92 90,11 91,17 53,33 89,71 86,80 93,82 70,69 92,70 93,22 78,79

+1,67 +0,32 +6,77 +1,58 +20,59 +20,45 +10,88 +10,45 +2,07 +27,86 +22,93 +11,32 +7,36 +4,91 +7,85 +6,99 +1,25 +2,67 +3,19 -


5242 5242

86,50 89,13

83,06 85,06

84,74 87,04

87,74 89,21

92,51 93,72

90,06 91,41

+5,32 +4,37

Atribut

Tabulka A.1.: Míra úspěšnosti extrakce atributů pro nabídky notebooků (trénovací data). Pouze ruční pravidla (EO#1) a kombinovaný model (EO#2). 4F = rozdíl mezi F-mírou třetího a prvního modelu. (L) mód loose, (S) mód strict.

II

Nabídky notebooků (testovací data)

#

P (%)

EO#1 R (%)

F (%)

P (%)

EO#2 R (%)

F (%)

4F (%)

Výrobce (S) Řada (S) Model (S) Model (L) Produktový kód (S) Produktový kód (L) EAN kód Cena (S) Cena (L) Cena s daní (S) Cena s daní (L) Cena bez daně (S) Cena bez daně (L) Dostupnost (S) Dostupnost (L) Množství na skladě Název CPU (S) Název CPU (L) Frekvence CPU (S) Frekvence CPU (L) Název GPU (S) Název GPU (L) Název IGP Grafická paměť Operační systém (S) Operační systém (L) Kapacita HDD Kapacita SSD Operační paměť Úhlopříčka displeje Rozlišení displeje Typ displeje Barva Váha

225 139 225 225 54 54 2 147 147 39 39 6 6 172 172 25 182 182 74 74 108 108 53 91 176 176 177 7 158 242 67 14 84 29

98,06 94,78 75,45 88,28 93,33 96,92 0 89,41 96,47 100 100 100 100 89,57 90,80 100 86,59 87,15 89,71 89,71 92,96 97,18 100 97,92 97,63 98,82 96,36 100 71,43 96,13 100 100 100 87,10

89,78 91,37 74,11 85,45 25,93 27,78 0 82,99 84,27 82,05 93,73 66,67 88,99 84,88 85,61 100 85,16 85,35 82,43 82,43 61,11 62,43 52,83 51,65 93,75 94,74 89,83 28,57 79,11 71,90 79,10 57,14 91,67 93,10

93,74 93,04 74,77 86,84 40,58 43,18 0 86,08 89,96 90,14 96,76 80,00 94,17 87,16 88,13 100 85,87 86,24 85,92 85,92 73,74 76,02 69,14 67,63 95,65 96,73 92,98 44,44 75,08 82,27 88,33 72,73 95,65 90,0

98,54 95,49 80,75 93,01 80 88,46 0 89,25 95,70 100 100 100 100 89,57 90,80 100 95,86 97,66 89,71 89,71 93,46 94,04 90,91 92,47 97,08 98,19 96,36 100 85 94,06 100 100 98,73 87,10

89,78 91,37 76,79 85,90 44,44 48,93 0 92,52 93,79 82,05 93,73 66,67 88,99 84,88 85,61 100 89,01 91,25 82,43 83,78 92,59 93,52 94,34 94,51 94,32 95,41 89,83 28,57 86,08 85,12 79,10 57,14 92,86 93,10

93,95 93,38 78,72 89,31 57,14 63,01 0 90,85 94,74 90,14 96,76 80,00 94,17 87,16 88,13 100 92,31 94,35 85,92 86,64 93,02 93,78 92,59 93,48 95,68 96,78 92,98 44,44 85,53 89,37 88,33 72,73 95,71 90,00

+0,21 +0,34 +3,95 +2,47 +16,56 +19,83 +4,77 +4,78 +6,44 +8,11 +0,72 +19,28 +17,76 +23,45 +25,85 +0,03 +0,05 +10,45 +7,1 +0,06 -


2496 2496

90,47 92,70

79,56 81,12

84,66 86,52

92,35 94,41

86,65 88,25

89,41 91,23

+4,75 +4,71

Atribut

Tabulka A.2.: Míra úspěšnosti extrakce atributů pro nabídky notebooků (trénovací data). Pouze ruční pravidla (EO#1) a kombinovaný model (EO#2). 4F = rozdíl mezi F-mírou třetího a prvního modelu. (L) mód loose, (S) mód strict.

III

B

Příloha B.

Ukázky výstupu

V

Ukázky výstupu

VI

VII

Ukázky výstupu

VIII

IX

Obrázek B.1.: Extrakční ontologie pro pracovní nabídky byla aplikována na dataset čítající více než 9 600 dokumentů, na výstupu bylo přes 12 600 extrahovaných pracovních nabídek.

Vysoká škola ekonomická v Praze Fakulta informatiky a statistiky

Recommend Documents