Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka Ústav informatiky & SoNet RC PEF, Mendelova universita Brno
(Text Mining)
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Data, informace, znalost
●
Elektronická textová data
●
Induktivní strojové učení
●
Příprava dat, jejich representace
●
Metody vyhledávání, podobnost
●
Aplikační oblasti
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Data, informace, znalost - data jsou zde všechny údaje, které se nějak získaly (údaje relevantní, nerelevantní, se šumem i bez šumu, přesné i nepřesné, apod.) - informace je část dat, která je zajímavá z hlediska řešení zvoleného problému - znalost je zobecněná informace - metaznalost je znalost o znalosti (např. vědět, která znalost je aplikovatelná na konkrétní problém)
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Elektronická textová data Text v elektronické formě (ASCII/ANSI, Unicode, apod.). Typická textová data jsou např. součástí Internetu. Elektronický text je využíván v mnoha odvětvích. Elektronická textová data jsou velmi často tvořena běžným přirozeným libovolným jazykem (natural language). Strojové zpracování takových typicky lidských dat je mimořádně složité a většinou závisí na konkrétním jazyku.
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Induktivní strojové učení - učení pomocí konečné množiny konkrétních příkladů - příklady obecně pokrývají jen určitou část reality - chybějí dostatečné údaje o vlastnostech dat (např. rozložení) - nelze vytvořit matematický model pro spolehlivou predikci - znalost se získá zobecněním trénovacích příkladů
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Induktivní strojové učení Jakou barvu má vrána? Černou? A proč? Viděl někdy někdo jinou než černou vránu? Viděl někdo úplně všechny vrány, které kdy existovaly a existují kdekoliv na Zemi? Do jaké míry je generalizace správná a přijatelná?
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Induktivní strojové učení Kolik konkrétních vran je nutno vidět pro generalizaci vrána je černá?
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Induktivní strojové učení Vrána šedivka:
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Induktivní strojové učení Zobecnění konkrétních disponibilních příkladů je jedna z možných metod učení. Stroje (počítače) vyžadují (na rozdíl od lidí) obvykle podstatně větší množství příkladů ke zobecnění a tím k získání znalosti. Velkou roli hraje využívání nějaké metody na určování stupně podobnosti – např. zařazení neznámého příkladu k určité skupině příkladů známých.
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Induktivní strojové učení Algoritmy strojového učení stanovují své příslušné parametry automatizovaně ve fázi trénování. Vlastnosti natrénovaného algoritmu se ověří ve fázi testování. 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ředloženy během učení.
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Příprava dat, jejich representace Typická cesta získávání znalostí z elektronických nestrukturovaný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
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Příprava dat, jejich representace 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 jejich vzájemnou závislostí. Proto se pořadí slov v dokumentu považuje v principu za “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.
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Příprava dat, jejich representace 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).
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Příprava dat, jejich representace Příklad representace textu, 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 symbolů) používaný pro trénink nějakého zvoleného algoritmu:
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Příprava dat, jejich representace Příklad representace textu, 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 symbolů) 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
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Příprava dat, jejich representace 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 existuje zjednodušený systém Porter stemming, kde se prostě odřezávají koncovky, což není dokonalé, ale z praktického hlediska velmi účinné.
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Příprava dat, jejich representace Výskyt slov – existuje více možností, jak ho 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)
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Metody vyhledávání, podobnost Obecná úloha spočívá v nalezení podobnosti dokumentu vůči nějakému jinému nebo nějaké skupině (např. zajímavé a nezajímavé, spadající do určitého tématu, apod.). Podobné dokumenty tvoří shluky nebo třídy. Shlukování: učení bez učitele. Rozdělení směsi dokumentů na skupiny obsahující dokumenty s nějakou vzájemnou podobností. Podobnost je nutno nějak definovat. Shlukování se aplikuje tehdy, když nejsou k dispozici známé příklady z jednotlivých skupin. Klasifikace: učení s učitelem. Příklady členů jednotlivých tříd jsou k dispozici. Stroj se učí zatřiďovat pomocí příkladů.
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Metody vyhledávání, podobnost Učení s částečným dohledem učitele: k dispozici je málo příkladů, ale mohou být typické. Pomocí omezeného množství příkladů jsou neznámé případy postupně začleňovány do příslušných tříd (či shluků), a tak může být posilována rozhodovací schopnost vznikajících tříd pro zařazování dalších neznámých dokumentů. Postupuje se tak např. tehdy, když je k dispozici jen několik známých příkladů (např. článků) a je nutno roztřídit velmi velké množství neznámých případů – typický případ pro současná textová data.
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Metody vyhledávání, podobnost Metody klasifikace textových dokumentů (např.): - k-NN (k-nearest neighbors), nejbližší soused(é) (Eukleidova vzdálenost udává podobnost dokumentů); - generování rozhodovacích stromů mimalizací entropie (uzly testují jen ta relevantní “slova”, která přispívají k zařazení dokumentu do správné kategorie); - disjunktní normální forma (vytvořená pravidla); - 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); aj.
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Metody vyhledávání, podobnost 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:
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Metody vyhledávání, podobnost
p D ∣ h p h p h ∣ D = p D 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. 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.
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Metody vyhledávání, podobnost 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.
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Metody vyhledávání, podobnost Výpočetní složitost lze výrazně snížit zavedením úmyslné nekorektnosti, aby bylo možno Bayesovu metodu v praxi použít: Hodnoty atributů (slova na jednotlivých pozicích) jsou navzájem podmíněně nezávislé, tj. dokument je vlastně jen pozorovanou konjunkcí hodnot atributů. Celková pravděpodobnost náležení textu do každé z možných tříd cj se počítá zjednodušeně jako součin pravděpodobností výskytů individuálních slov wi v dokumentu:
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Metody vyhledávání, podobnost
p w 1 , w 2 , , w m ∣ c j
[
n
p w i ∣ c j ∏ i
]
c NB = argmax p c j ∏ p w i ∣ c j cj
i=1
n … počet slovních pozic v dokumentu třídy cj j … index jedné z uvažovaných klasifikačních tříd p(cj ) … apriorní pravděpodobnost výskytu dokumentu v cj p(wi | cj ) … aposteriorní pravděpodobnost výskytu slova wi v cj
Automatické vyhledávání informace a znalosti v elektronických textových datech
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
zdroj textových dokumentů
positivní trénovací příklady
předzpracování
+ extrakce unikátních slov a abeceda albatros . . . žížala
celkový slovník
-
četnosti slov v positivních p( wi | c+ ) dokumentech
četnosti slov v negativních p( wi | c– ) dokumentech
negativní trénovací příklady
Obecný přístup k vytváření pravděpodobností pro klasifikaci
Automatické vyhledávání informace a znalosti v elektronických textových datech
w1
Trénovací texty:
w2
je je není není velmi chladno
w3
pěkné počasí chladno velmi chladno pěkné chladno
. . .
+ texty : celkem 6 slov - texty : celkem 7 slov
. . .
. . .
cj + + -
. . .
počet unikátních slov : 6
Klasifikovaný dokument “to není pěkné chladno”: + nebo - ?
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: setříděný slovník : četnost slova wi v + četnost slova wi v p (wi | +) p (wi | -)
w1
w2
chladno je 1 3 1/6 3/7
1 1
w3
w4
w5
w6
není pěkné počasí velmi 1 1
1/6 1/6 1/7 1/7
1 1
1 0
1 1
1/6 1/7
1/6 0/7
1/6 1/7
p = p ( 'není', 'pěkné', 'chladno' | +/–) = = pNBK ('není' | +/–) × p('pěkné' | +/–) × p('chladno' | +/–)
“w3 w4 w1” = “není pěkné chladno” P+ = p(+) p(w3 = 'není' | +) p(w4 = 'pěkné' | +) p(w1 = 'chladno' | +) = 2 1 1 1 = × × × ≈ 0.00154 6 6 6 6
P- = p(–) p(w3 = 'není' | –) p(w4 = 'pěkné' | –) p(w1 = 'chladno' | –) = 4 1 1 3 = × × × ≈ 0.00583 6 7 7 7 0.00154 ≈ 0.21 P = 0.00154 0.00583
+ n
0.00583 ≈ 0.79 Pn = 0.00154 0.00583 -
Pn- > Pn+ ⇒ negativní
Jan Žižka, Ústav informatiky/SoNet RC, PEF, Mendelova universita, Brno
●
Aplikační oblasti Existuje velké množství aplikací v různých oborech, a to všude tam, kde existuje elektronický text. Typickým příkladem je např. vyhledávání na Internetu nebo filtrace spamu z elektronické pošty. Mezi nejmodernější aplikační oblasti nyní patří např.: - seskupování příspěvků v “blogosféře”; - stanovení subjektivity v textu; - názory/pocity/nálada/postoje/mínění v textu; - odhalovaní textových plagiátů; - analýza názorů; - business intelligence (legální komerční “špionáž”); atd.
Automatické vyhledávání informace a znalosti v elektronických textových datech