Získávání znalostí z nestrukturovaných textových dokumentŮ Získávání znalostí z textu pomocí klasifikace algoritmy strojového učení Jan Žižka Centrum biostatistiky a analýz CBA Masarykova universita zizka@cba.muni.cz Získávání znalostí z nestrukturovaných textových dokumentŮ Co se rozumí pojmem znalost Jaká je obecně forma textovch dokumentů V jaké formě předložit text algoritmu v počítači Jak lze text před zpracováním vhodně připravit V čem je princip strojového učení Jak se dá strojové učení pro získání znalosti použít Které algoritmy strojového učení přicházejí do úvahy Jaký je konkrétní postup při učení Jaké výsledky lze očekávat Obecná zásada při řešení uvedených problémů je: EXPERIMENTOVAT Následující informace se věnuje stručnému přehledu problematiky z těchto hledisek: Získávání znalostí z nestrukturovaných textových dokumentŮ Velmi vysoké objemy elektronických textových dokumentů obsahují obecně různou znalost danou specifickým hlediskem, tj. konkrétní aplikací, která texty využívá. Potíž tvoří jak množství dat, tak i jejich forma ­ přirozený jazyk, který nemá vhodný formální popis pro vytvoření příslušné teorie umožňující automatizované zpracování. Typická cesta získávání znalostí z elektronických nestrukturo- vaných textů spočívá v těchto krocích: zdroj patřičný objem (obecně zašuměných) dat odstranění šumu čistá data výběr aplikačně zajímavé části dat informace zobecnění informace znalost Získávání znalostí z nestrukturovaných textových dokumentŮ Vzhledem k nedostatku formální teorie, která by na základě za- dání hodnot určitých parametrů byla schopna např. požadované předpovědi, je nutno použít alternativních metod. Poměrně velmi úspěšné výsledky poskytují algoritmy strojového učení, kdy příslušné parametry zvoleného algoritmu se stanovují automatizovaně ve fázi trénování. Vlastnosti natrénovaného algo- ritmu se ověří ve fázi testování, a pokud výsledky testování jsou přijatelné, lze naučený algoritmus použít pro danou aplikaci. Trénovací fáze vyžaduje vhodné učící příklady, neboť vlastnosti algoritmu (parametry) jsou nakonec stanoveny použitými daty. Testovací fáze používá příklady, které nebyly algoritmu před- loženy během učení. Správná generalizace umožní správné zpracování informace, která se teprve objeví v budoucnu. Získávání znalostí z nestrukturovaných textových dokumentŮ Representace textových dokumentů ­ bag of words (BOW) Metody strojového učení převážně vidí textové dokumenty jako soubory obsahující symbolické hodnoty ("termíny", "slova"), aniž by se zabývaly jejich významem (nanejvýš velmi mělce, např. při předzpracování dat) nebo vzájemnou závislostí. Proto je pořadí slov v dokumentu zcela bezvýznamné, což sice eliminuje určitý informační obsah, ale výrazně zjednodušuje zpracování přirozeného jazyka z hlediska např. klasifikace. Uvedená zjednodušení umožňují se vyhnout nevyřešeným problémům se strojovým porozuměním dokumentům v přirozeném jazyce (včetně odstranění potíží s mnohojazyčností), ale mohou vést ke snížení efektivity (nerozeznávání významu synonym, ignorování gramatiky, ...). Přesto jsou výsledky překvapivě dobré v mnoha aplikacích, i když je nutno počítat s chybovostí. Získávání znalostí z nestrukturovaných textových dokumentŮ Předzpracování ­ ovlivňuje výrazně kvalitu výsledku, např.: vyřazení obecných slov, která nemají specifický význam z hlediska aplikace (např. předložky, zkratky) vyřazení slov s velmi nízkou nebo vysokou frekvencí ve všech dokumentech vyřazení interpunkce, mezer, apod. převod všech písmen na malá (slovo na začátku věty a uvnitř věty je totéž při representaci typu bag-of-words) Eliminace nevýznamných znaků a slov výrazně snižuje dimensionalitu problému (např. řádově z 104 na 103 , protože každé unikátní slovo představuje jednu dimensi). Získávání znalostí z nestrukturovaných textových dokumentŮ Příklad representace textu pomocí metody bag-of-words (BOW), kde se ignoruje interpunkce, členění textu do řádků, velká a malá písmena, dvojjazyčnost (anglické termíny v české větě), pořadí slov, které může mít velký význam (např. machine learning ­ strojové učení a learning machine ­ učící stroj má zcela odlišný význam), a vynechají se obecná slova. Vznikne tedy slovník (seznam sym- bolů) používaný pro trénink nějakého zvoleného algoritmu: anglické bag bow české členění dvojjazyčnost ignoruje interpunkce learning machine má malá metody mít může obecná odlišný písmena pomocí pořadí příklad representace řádků slov stroj strojové termíny textu učení učící velká velký větě vynechání význam words zcela Získávání znalostí z nestrukturovaných textových dokumentŮ Representace BOW v předchozím příkladu vynechala např. spojku 'a', zvratné 'se', a některé další symboly nemající pro konkrétní aplikaci význam (včetně interpunkce). Další redukci dimensionality lze docílit např. převodem slov na zá- kladní tvar (kmen, lemma). V předchozím příkladu by bylo možné redukovat vzniklý slovník (infinitiv, 1. pád, jednotné číslo, jediný rod, apod.), takže dimensionalita klesne o 4: mít má stroj strojové učení učící velká velký mít stroj učit velký Tzv. lemmatizace je ovšem jazykově závislá. Pro angličtinu existu- je zjednodušený systém Porter stemming, kde se prostě odřezávají koncovky, což není dokonalé, ale z praktického hlediska účinné. Získávání znalostí z nestrukturovaných textových dokumentŮ Výskyt slov ­ existuje více možností, jak je vyjádřit, např.: binární ­ '1' slovo se v dokumentu vyskytuje, '0' slovo se nevyskytuje (váha slova = 1 nebo 0) frekvenční ­ váha slova je dána četností jeho výskytu tf-idf ­ term frequency-inverted document frequency: četnost slova v dokumentu (representace dokumentu daným slovem) vůči počtu dokumentů, v nichž se dané slovo vyskytuje (v čím více dokumentech se dané slovo vyskytuje, tím nižší je jeho diskriminační hodnota) Optimální representaci výskytu slov je obvykle nutno zjistit experimentálně, protože dosavadní zkušenosti ukazují, že je aplikačně závislá a navíc pro různé algoritmy může být různá. Získávání znalostí z nestrukturovaných textových dokumentŮ Další obrázek ilustruje representaci jednotlivých textových dokumentů jako vektory (pro jednoduchost jsou zde koncové body vektorů dány souřadnicemi v prostoru s binárním vyjádřením výskytu slov ­ pokud by např. bylo použito frekvenčního vyjá- dření, pak jednotlivé osy jsou číselné reálné). Vektorová representace umožňuje porovnávat podobnost či různost dokumentů jako podobnost vektorů: délka vektorů a úhel , který navzájem svírají. To umožňuje snadno porovnávat neznámé texty se známými např. výpočtem hodnoty 0.0 cos() 1.0, tj. hodnoty z reálného jednotkového intervalu. Získávání znalostí z nestrukturovaných textových dokumentŮ W1 = je doc4 = je pěkné teplo W2 = pěkné W3 = počasí 0 1 1 1 (1,1,1) (0,1,1) (1,1,0) (1,0,1) doc3 = je pěkné počasí doc1 = není pěkné počasí doc2 = je škaredé počasí cos(34 ) podobnost34 Slovník "+" má tři slova: je pěkné počasí 34 (0,0,1) doc5 = není škaredé počasí doc6 = není pěkné teplo (0,1,0) (1,0,0) Celkový slovník má 6 slov: je není pěkné počasí škaredé teplo (0,0,0) doc8 = není škaredé teplo 8 dokumentů: doc3 ... 100% doc8 ... 0% doc7 = je škaredé teplo Získávání znalostí z nestrukturovaných textových dokumentŮ Metody klasifikace/kategorizace textových dokumentů Existuje více možností strojového učení, například: metoda k-NN (k-nearest neighbors), nejbližší soused(é) (Eukleidova vzdálenost udává podobnost dokumentů) metoda generování rozhodovacích stromů mimalizací entro- pie (uzly testují jen ta relevantní "slova", která přispívají k za- řazení dokumentu do správné kategorie) metoda disjunktní normální formy (vytvořená pravidla) metoda support vector machines (SVM, nalezení pouze těch textů, které tvoří oddělovací hranici mezi dvěma třídami) Bayesův naivní klasifikátor (stanovení pravděpodobnosti náležení do jedné ze tříd pomocí kombinace podmíněných pravděpodobností vypočítaných z tréninkových dat) a řada dalších, včetně možnosti kombinací metod Získávání znalostí z nestrukturovaných textových dokumentŮ Jako demonstraci klasifikační metody lze použít např. jeden z nejčastěji aplikovaných algoritmů, tzv. metodu naivního bayesovského klasifikátoru (BNK). BNK je založen na Bayesově teorému pro pravděpodobnostní inferenci ­ předpokladem je, že míra náležení kombinovaných jevů (zde výskytů slov v dokumentu) do patřičných kategorií je řízena rozloženími pravděpodobností a že optimální rozhodnutí lze najít pomocí těchto pravděpodobností a údajů z disponibilních dat z reálného světa: ph D = pDh ph pD Počítá se pravděpodobnost hypotézy h (např. příslušnost do určité třídy) přičemž jsou dána nějaká trénovací data D. Získávání znalostí z nestrukturovaných textových dokumentŮ Bayesův teorém z předchozího vztahu využívá hodnoty pravdě- podobností p(D | h), což jsou pravděpodobnosti výskytu dat D za předpokladu platnosti uvažované hypotézy h. p(D) je pravděpodobnost výskytu dat D bez jakéhokoli vztahu k jakékoli hypotéze (apriorní pravděpodobnost). p(h) je pravděpodobnost platnosti hypotézy h (apriorní pravdě- podobnost), aniž jsou dosud známa nějaká data D, která svým výskytem mohou zvýšit či snížit p(h). p(h | D) je tedy hledaná aposteriorní pravděpodobnost, že pro daná data D bude platit hypotéza h. Získávání znalostí z nestrukturovaných textových dokumentŮ Naivní Bayesův klasifikátor Výpočetní složitost lze výrazně snížit zavedením úmyslné neko- rektnosti, aby bylo možno Bayesovu metodu v praxi použít: Hodnoty atributů (slova na jednotlivých pozicích v dokumentu) jsou navzájem podmíněně nezávislé, tj. dokument je vlastně pozorovanou konjunkcí hodnot atributů. V takovém případě se celková pravděpodobnost náležení textu do každé z možných tříd cj počítá zjednodušeně jako součin pravděpodobností jednotlivých nezávislých jevů, tj. výskytů individuálních slov wi v dokumentu: pw1 , w2 ,,wm cj i pwi cj Získávání znalostí z nestrukturovaných textových dokumentŮ cNB = argmax c j [pcj i=1 n pwi cj ] n ... počet slovních pozic v dokumentu klasifikovaném do třídy cj j ... index jedné z uvažovaných klasifikačních tříd (alespoň dvě) p(cj ) ... apriorní pravděpodobnost výskytu dokumentu v cj p(wi | cj ) ... aposteriorní pravděpodobnost výskytu slova wi v cj Např. konkrétní dokument dk může být representován n = 143 různými slovy w1 , w2 , w3 , ... , w143 a klasifikován do j = 3 různých tříd, např. cj {zajímavý, nezajímavý, neutrální}. Pro každé cj se spočítá pravděpodobnost, s níž tam dokument patří, a výsledek cNB (cNave Bayes ) je dán maximální hodnotou argmax. Získávání znalostí z nestrukturovaných textových dokumentŮ zdroj textových dokumentů a abeceda albatros . . . žížala předzpracování extrakce unikátních slov celkový slovník negativní trénovací příklady positivní trénovací příklady - + četnosti slov v positivních dokumentech četnosti slov v positivních dokumentech četnosti slov v negativních dokumentech p( wi | c+ ) p( wi | c­ ) Obecný přístup k vytváření prav- děpodobností pro klasifikaci Získávání znalostí z nestrukturovaných textových dokumentŮ je pěkné počasí + je chladno - není velmi chladno + není pěkné - velmi chladno - chladno - w1 w2 w3 cj . . . . . . . . . . . . Klasifikovaný dokument "to není pěkné chladno": + nebo - ? Trénovací texty: + texty : celkem 6 slov - texty : celkem 7 slov počet unikátních slov : 6 Získávání znalostí z nestrukturovaných textových dokumentŮ chladno je není pěkné počasí velmi četnost slova wi v + 1 1 1 1 1 1 četnost slova wi v - 3 1 1 1 0 1 p (wi | +) 1/6 1/6 1/6 1/6 1/6 1/6 w1 w2 w3 w4 w5 w6 setříděný slovník : p (wi | -) 3/7 1/7 1/7 1/7 0/7 1/7 Po vytvoření celkového slovníku z unikátních slov (je jich zde 6), výpočtu apriorních pravděpodobností (2 texty + a 4 texty ­ v celkem 6 textech), výpočtu aposteriorních pravděpodobností výskytu slov v + a ­, a následné normalizaci lze určit výsledek: p = p ( 'není', 'pěkné', 'chladno' | +/­) = = pNBK ('není' | +/­) × p('pěkné' | +/­) × p('chladno' | +/­) Získávání znalostí z nestrukturovaných textových dokumentŮ P+ = p(+) p(w3 = 'není' | +) p(w4 = 'pěkné' | +) p(w1 = 'chladno' | +) = P- = p(­) p(w3 = 'není' | ­) p(w4 = 'pěkné' | ­) p(w1 = 'chladno' | ­) = "w3 w4 w1 " = "není pěkné chladno" = 2 6 × 1 6 × 1 6 × 1 6 = 4 6 × 1 7 × 1 7 × 3 7 0.00154 0.00583 0.00154 0.00154 0.00583 Pn + = 0.21 Pn - = 0.00583 0.00154 0.00583 0.79 Pn - > Pn + negativní