Univerzita Hradec Králové Fakulta informatiky a managementu
Diplomová práce
2014
Bc. Pavel KINC, DiS. Univerzita Hradec Králové
Fakulta informatiky a managementu Katedra informatiky a kvantitativních metod
Analýza nestrukturovaných dat Diplomová práce
Autor: Bc. Pavel KINC, DiS. Studijní obor: Aplikovaná informatika
Vedoucí práce: doc. RNDr. Hana SKALSKÁ, CSc.
Hradec Králové
květen 2014
Prohlášení: Prohlašuji, že jsem diplomovou práci zpracoval samostatně. K získání znalostí o zpracovaném tématu jsem použil níže uvedené literatury a internetových zdrojů.
V Hradci Králové dne 15.5.2014
Bc. Pavel KINC, DiS.
Poděkování Považuji za svou milou povinnost poděkovat svému vedoucímu práce paní doc. RNDr. Haně SKALSKÉ, CSc. za odborné vedení a cenné rady v průběhu zpracovávání vybraného tématu. Poděkování patří také firmě StatSoft, která mi poskytla, pro účely diplomové práce, časově omezenou profesionální verzi své aplikace Statistica 12CZ. V poslední řadě bych chtěl poděkovat celé své rodině za psychickou podporu.
Anotace Analýza nestrukturovaných dat Tato diplomová práce má za cíl přiblížit problematiku analýzy nestrukturovaných dat. Práce je zaměřena na textovou interpretaci dat především z důvodu rozsahu zpracování této problematiky. Diplomová práce je rozdělena do dvou hlavních pasáží: nastínění problematiky nestrukturovaných dat, jejich příprava před samotnou analýzou a jednotlivé úlohy pro analýzu nestrukturovaných textových dat. První část má za úkol vysvětlit pojem nestrukturovatelná data, proč je náročné jejich hromadné zpracování, jaká jsou úskalí automatické analýzy a podobně. Dále je tato část zaměřena na přípravu dat před samotnou analýzou. Jsou zde nastíněny metody převedení textových dat do numerické podoby a výběr reprezentativních vzorků pomocí různých metod. Druhá část je zaměřena na jednotlivé úlohy analýzy nestrukturovaných textových dat, též nazývaných jako „Data-mining“. V této části jsou nastíněny úlohy, jako je sumarizace, klasifikace, určení míry podobnosti dokumentů, vyhledávání plagiátů a podobně. Závěrečná
pasáž
„Data-miningu“,
je
věnována
respektive
demonstraci
„Text-miningu“.
softwarových Shrnuje
aplikací
v úlohách
problematiku
analýzy
nestrukturovaných dat a poskytuje návrhy na možné využití popsaných analýz v praxi. Pomocí
vybraných
softwarových
aplikací
jsou
demonstrovány
konkrétní
úlohy
„Text-miningu“, jako jsou indexace, sumarizace, porovnání podobnosti dokumentů (plagiátorství) a podobně.
Anotation Unstructured data analysis This thesis aims to explain the issue of the analysis of unstructured data. The work is focused on textual interpretation of the data mainly because of the scale handling of these issues. The thesis is divided into two main passages: outlines the problems of unstructured data, their preparation before to analysis and individual tasks for analyzing unstructured text data. The first part is responsible for explanation the concept unstructured data, why is difficult their bulk processing, what are the pitfalls of automatic analysis and the like. Furthermore, this section focuses on data preparation before analysis. There are methods which convert text data into numeric form and collected representative samples using a variety of methods. The second part focuses on the individual task of analysis of unstructured text data, also known as "data-mining". This section outlines the tasks such as summarization, classification, determining the degree of similarity of documents, searching for plagiarism and the like. Final passage is devoted to demonstrating software applications in tasks "data-mining" or "text-mining". Summarizes the problems of analysis of unstructured data and provides suggestions for possible use of analysis in practice. By using of selected software applications there are demonstrated specific tasks "text-mining", such as indexing, summarizing, comparing the similarity of documents (plagiarism) and the like.
Obsah 1
Úvod .................................................................................................................................. 1
2
Rozdělení dat .................................................................................................................. 2
3
2.1
Strukturovaná data .................................................................................................. 2
2.2
Nestrukturovaná data .............................................................................................. 3
2.3
Semi-strukturovaná data......................................................................................... 3
Analýza nestrukturovaných dat ................................................................................. 4 3.1
Příprava dat .............................................................................................................. 4
3.2
Model vektorového prostoru (Vector space model)............................................ 6
3.2.1
Binární zápis vektoru ....................................................................................... 7
3.2.2
Frekvenční zápis vektoru (TF) ....................................................................... 9
3.2.3
Frekvenční zápis vektoru s vyjádřením důležitosti slova (TF-IDF) ........ 11
3.3
Redukce dimenze .................................................................................................. 13
3.3.1
Odstranění Stop-slov / Pos-tagging ............................................................ 14
3.3.2
Lemmatizace .................................................................................................. 15
3.3.2.1 Brute Force algoritmus .............................................................................. 15 3.3.2.2 Lovinsův algoritmus ................................................................................... 16 3.3.3
Stemming ........................................................................................................ 18
3.3.4
Očištění od synonym ..................................................................................... 18
3.3.5
Výběr příznaků - feature selection .............................................................. 19
3.3.6
Extrakce příznaků – feature extraction ....................................................... 20
3.3.7
Extrakce frází .................................................................................................. 21
3.3.7.1 Mi-score (mutual Information) .................................................................. 21 3.3.7.2 T-score ......................................................................................................... 23 3.3.7.3 Latentní sémantická analýza (LSA) ........................................................ 24 3.3.7.4 Singular value decomposition (SVD) ...................................................... 24 4
Úlohy pro analýzu textu – Data mining .................................................................. 28 4.1
Indexace textových dokumentů ........................................................................... 29
4.2
Shrnutí textu - sumarizace ................................................................................... 31
4.2.1
Luhnova metoda ............................................................................................ 31
4.2.2
Grafová analýza hyperstuktur ...................................................................... 33
4.2.2.1 LexRank ...................................................................................................... 34 4.3
Klasifikace textových dokumentů (klastrování) ................................................. 37
4.3.1
Lexikální frekvenční analýza ........................................................................ 37
4.3.2
Shluková analýza ........................................................................................... 39
4.3.2.1 Hierarchické shlukování ............................................................................ 41 4.3.2.1.1 Metoda nejbližšího souseda ...................................................... 41 4.3.2.2 Nehierarchické shlukování ....................................................................... 45 4.3.2.2.1 Metoda k-means ........................................................................ 45 4.4
Fraud management ............................................................................................... 47
4.5
Hledání plagiátů ..................................................................................................... 49
4.5.1 5
6
Hledání plagiátu pomocí LSA ...................................................................... 49
Systémy pro ukládání nestrukturovaných dat..................................................... 51 5.1
Document Management Systém ......................................................................... 51
5.2
Content Management System ............................................................................. 52
Sofwarové nástroje Data-miningu........................................................................... 52 6.1
KWords .................................................................................................................... 53
6.2
Online summarize tool .......................................................................................... 54
6.3
Statistica 12 ............................................................................................................ 55
6.4
Theses.cz ................................................................................................................ 57
7
Závěr ............................................................................................................................... 59
8
Terminologický slovník .............................................................................................. 61
9
Seznam použité literatury .......................................................................................... 63
10 Přílohy............................................................................................................................. 67 Seznam stop slov............................................................................................................... 67 Nový systém odhalí plagiátorství mezi vědci................................................................. 67
Seznam obrázků Obrázek 1 – Rozdělení dat [44] .................................................................................................. 2 Obrázek 2 – Příklad strukturovaných dat (tabulka událostí systému Windows) ........................ 3 Obrázek 3 – Doporučené velikosti korpusů dle témat a složení korpusu SYN2010 [21, 22] .... 5 Obrázek 4 – Možný postup přípravy dat .................................................................................... 6 Obrázek 5 – Vector space model – vyjádření tří dokumentů ABC ........................................... 12 Obrázek 6 – Ukázka zpracování článku přílohy č. 2 pomocí online služby LemmaGen [33] . 17 Obrázek 7 – Ukázka nadřazených termů (generalizace) .......................................................... 19 Obrázek 8 – Redukované matice [6] ........................................................................................ 25 Obrázek 9 – Závislost výskytu termů v korpusu na TF-IDF .................................................... 30 Obrázek 10 – Grafová analýza LexRank článku přílohy č.2 [32] ............................................ 36 Obrázek 11 – Příklad 2D cluster mapy a dendrogramu [41] .................................................... 39 Obrázek 12 – Příklad řádkového a sloupcového dendrogramu [41] ........................................ 41 Obrázek 13 – Zobrazení objektů v rovině [13]......................................................................... 42 Obrázek 14 – Dendrogram po prvním kroku rozkladu matice D ............................................. 43 Obrázek 15 – Dendrogram po druhém kroku rozkladu matice D ............................................ 44 Obrázek 16 – Dendrogram rozkladu na shluky ........................................................................ 45 Obrázek 17 – Příklad detekce podvodných objednávek pomocí shlukové analýzy ................. 47 Obrázek 18 – Příklad pravidel ohodnocení sledovaných příznaků [25]................................... 48 Obrázek 19 – Podobnost dokumentů [23] ................................................................................ 50 Obrázek 20 – Reprezentace výsledků indexace [20] ................................................................ 53 Obrázek 21 – Ukázka aplikace Online summarize tool [42] .................................................... 54 Obrázek 22 – Načtení textových dokumentů [Statistica CZ v.12] ........................................... 55 Obrázek 23 – Předzpracování dokumentů [Statistica CZ v.12]................................................ 56 Obrázek 24 – Kombinace podobných slov [Statistica CZ v.12]............................................... 56 Obrázek 25 – Ukázka funkcí programu [Statistica CZ v.12] ................................................... 57 Obrázek 26 – Ukázka funkce projektu Theses.cz [38] ............................................................. 58 Obrázek 27 – Zpráva o podobnosti ze systému Odevzdej........................................................ 58
Seznam tabulek Tabulka 1 – Vyjádření výskytu jednotlivých slov v dokumentech ............................................. 9 Tabulka 2 – Vyjádření důležitosti termů ................................................................................... 12 Tabulka 3 – Ukázka báze dat pro algoritmus Brute Force ....................................................... 15 Tabulka 4 – Příklad slovníku synonym (synonymických řad) ................................................. 19 Tabulka 5 – Vyjádření vah termů dokumentu B pro indexaci .................................................. 30 Tabulka 6 – Matice podobnosti 3 vět článku přílohy č.2 .......................................................... 35 Tabulka 7 – Frekvenční výskyt slov v dokumentu a napříč korpusem .................................... 38
1
Úvod Za data lze ve světě IT považovat veškeré informace v digitální podobě. Podle jejich
způsobu uložení se dělí na několik základních typů – strukturovaná (například databáze), semi-strukturovaná (soubory typu XML, XLS, …) a nestrukturovaná (například textové dokumenty). A právě nestrukturovaná data jsou, vzhledem k jejich formátu, pro počítačové zpracování nejsložitější. Obecným důvodem pro analýzu dat je potencionální možnost využití nevyčíslitelného kvanta dat, uloženého v různých systémech a různých formách. Největším uložištěm dat je v dnešní době Internetová síť, kde se data nacházejí v různých podobách. V elektronických systémech je dle studie firmy IBM – „The toxic terabytes“ - více než 80% dat v multimediálních souborech [19, 44]. Podle odborníka na zpracování dat Billa Jensena se množství informací zdvojnásobuje po každých 1100 dnech, tedy zhruba po třech letech. Nicméně čas, který je k dispozici ke zpracování tohoto narůstajícího objemu informací, je stále stejný: 1440 minut denně [9]. Tento výrok však dle přední mezinárodní analytické společnosti IDC platí již jen z poloviny. Množství dat se tedy dle IDC zdvojnásobuje přinejmenším za polovinu Jensenem uvedeného času. Odvážnější tvrzení přinesla společnost IBM, ve výše zmíněné studii, že se data zdvojnásobují každých 11 hodin. Z těchto jmenovaných materiálů jasně vyplývá, že dat přibývá závratnou rychlostí, což má za následek neustálé zvyšování požadavků na kapacitu datových uložišť a hlavně na správu těchto dat. S nárůstem objemu dat přichází problém v jejich následném využití – data jsou sice k dispozici, ale najít a využít relevantní informace, klade stále větší nároky na čas a výpočetní výkon. Z tohoto důvodu se rozvíjí obor analýzy dat a dolování v datech. Tyto dva pojmy neznamenají totéž, jak bude patrné z následujících kapitol. „Obrovský nárůst objemu dat je přímo úměrný snaze získání relevantních informací v nich uložených. Informace jsou uloženy v datech a ta jsou ztracena v databázích“ [2]. Cílem práce je přiblížit problematiku analýzy nestrukturovaných dat se zaměřeným na textové dokumenty. Na příkladech ukázat způsob reprezentace dokumentů a následně na nich aplikovat metody data-minigu.
-1-
2
Rozdělení dat Data můžeme dělit dle různých aspektů. Podle jejich tematického zaměření, formátu
(audio, video, text, www,...), objemu dat a podobně. K tomu abychom mohli data takto třídit či vyhledávat, musí být uložena v adekvátní podobě. Dle způsobu uložení dat dělíme data na strukturovaná, semi-strukturovaná a nestrukturovaná. Následující diagram znázorňuje rozdělení a strukturu jednotlivých typů dat [44]. Obrázek 1 – Rozdělení dat [44]
2.1
Strukturovaná data Jsou to data ukládaná do přesně specifikovaných struktur, jako jsou například databáze,
formuláře či jiné dokumenty s pevnou strukturou. Tento způsob uložení umožňuje provádět nad těmito daty velké množství operací, které usnadňují manipulaci. Oproti nestrukturovaným datům jsou však tato data převážně bez smyslu plného kontextu. Postrádají informační souvislosti a jazyková zabarvení.
-2-
Obrázek 2 – Příklad strukturovaných dat (tabulka událostí systému Windows)
Pro samotnou analýzu a následné dolovaní v datech jsou strukturovaná data nejlépe zpracovatelným zdrojem informací, neboť každý jeden datový sloupec obsahuje přesně definované hodnoty.
2.2
Nestrukturovaná data Naproti tomu nestrukturovaná data nejsou ukládána v přesně definovaných jednotných
strukturách. Jedná se především o textové dokumenty, audio a video dokumenty, www stránky, prezentace, elektronickou poštu a podobně. Na rozdíl od strukturovaných dat obsahují informace v souvislostech a velkou míru redundance. Vzhledem k výši redundance, nespecifikované struktuře a absenci klíčových slov, je velice složité v těchto datech vyhledávat, respektive vyhledávat relevantní informace ve velkém souboru dat. Vzhledem k objemu nestrukturovaných dat a jeho tempu nárůstu, je stále více kladen důraz na tvorbu algoritmů a systému pro jejich zpracování.
2.3
Semi-strukturovaná data Podle způsobu uložení můžeme data zařadit do skupiny semi-strukturovaná (částečně
strukturovaná) data. Ty částečně splňují kritéria pro začlenění do předchozích dvou typů. Jinými slovy vyplňují pomyslný prostor mezi předchozími dvěma typy dat. Netrukturovaná data jsou doplněna například o klíčová slova, metatagy a podobně. O těchto praktikách se stále častěji mluví především v souvislosti se sémantickým webem. Příkladem semistrukturovaných dat mohou být RSS kanály, XML soubory, informace uloženy v tabulkových procesorech (xls, ods a podobně).
-3-
3
Analýza nestrukturovaných dat Samotná analýza dat spočívá v několika fázích. V prvním kroku je nutné data připravit.
Pokud nejsou v digitální podobě, je nezbytné jejich převedení do počítačem zpracovatelné podoby. V případě textových dat, na která je zaměřena tato práce, lze například použít technologie OCR (Optical Character Recognition), ICR (Intelligent Character Recognition) či OMR (Optical Mark Recognition). Po digitalizaci následuje stanovení formy zpracování, zda je požadováno zařadit je dle jejich obsahu (klasifikace dokumentů), shrnout jejich podstatu (sumarizace / indexace), zjistit podobnost vybraných dokumentů, vyhledat v kolekci dle klíčových slov a podobně. Následuje výběr vhodné metody ke zpracování dat a finální fází je vyhodnocení poskytnutých výsledků – interpretace získaných informací a jejich aplikace v dalším procesu. Aby bylo možné data analyzovat a odvozovat nějaké závěry, je nutné nejprve vytvořit z podkladových dat jejich počítačem zpracovatelný model. Existuje mnoho technik vytvoření modelu s různými přístupy [5]. Dříve než se začne vytvářet pomyslný obraz nebo model textového dokumentu je nutné požadovaná data připravit.
3.1
Příprava dat Budeme-li uvažovat o analýze dokumentů, je nutné si uvědomit, co s dokumenty chceme
dělat. Mezi základními úlohy pro analýzu dat patří porovnání, indexace, sumarizace, klasifikace (kategorizace) dokumentů a další. Mezi pokročilé úlohy bychom mohli zařadit získávání nových znalostí z dokumentů tzv. „Data mining“ [27]. K tomu aby bylo možné s dokumenty pracovat, je nutné mít sestavenou jakousi kolekci dokumentů, nad kterou budou prováděny jednotlivé úlohy. Tato kolekce by měla obsahovat tematicky podobné dokumenty. Takový soubor dokumentů se nazývá korpus a slouží k učení klasifikátorů, odhalení podstatných informací v dokumentu, ke stanovení důležitosti slov (vysvětleno v následujících kapitolách) a podobně [28]. Velikost korpusu je vhodné stanovit jednak na základě počtu slov, ale také na základě počtu dokumentů v souboru. Použitelné tematické korpusy pro stanovení tématu dokumentu jsou podle Českého národního korpusu SYN2010 ve velikosti řádově několik milionů slov. Konkrétně zmíněný český národní korpus obsahuje cca 100 milionů slov. Následující obrázek znázorňuje doporučené objemy dat pro vybrané domény (témata) [22, 21]. -4-
Obrázek 3 – Doporučené velikosti korpusů dle témat a složení korpusu SYN2010 [21, 22]
Vzhledem k velkému objemu dokumentů, který přesahuje schopnost člověka je ručně zpracovávat, je nutné dokumenty převést do struktury, se kterou bude možné vykonávat matematické operace. Jednou z možných struktur, pro takové zpracování, je z hlediska matematického vyjádření Vektor. Segmentací textového dokumentu se rozumí rozdělení dokumentu na základní stavební kameny tzv. „Tokeny“. Tokeny jsou slova či sousloví, které tvoří jednotlivé složky vektoru. Tato část zpracování dokumentu se nazývá „tokenizace“ či „segmentace“ dokumentu [27]. V následujících kapitolách bude objasněna vhodnost využití sousloví jako jednotlivých složek vektoru, před rozdělením dokumentu na jednotlivá slova. Jedním z důvodu může být uchování správného významu. Především u flektivních jazyků, které díky vlastnostem jako jsou mnohoznačnost, synonyma a podobně, je nutné při zpracování dokumentů porozumět kontextu.
-5-
Obrázek 4 – Možný postup přípravy dat
V následujících kapitolách bude demonstrována reprezentace textových dokumentů pomocí počítačem zpracovatelných struktur.
3.2
Model vektorového prostoru (Vector space model) Jedním ze základních matematických způsobů pro vyjádření textového dokumentu je
model vektorového prostoru. Dokumenty jsou zde reprezentovány jako samostatné vektory, kde každá složka vektoru odpovídá jednomu termu z kolekce dokumentů [27]. Při procesu analýzy dokumentů je nutné vytvořit jeden společný vektor všech porovnávaných dokumentů, který bude obsahovat všechny termy (slova). Parametry (termy) tohoto vektoru je pro přehlednost vhodné seřadit dle abecedy. Na jeho základě jsou pak vytvořeny, dle zvolené metody, vektory jednotlivých porovnávaných dokumentů. Ty mají stejnou dimenzi jako společný vektor. Každý parametr takto vytvořených vektorů reprezentuje přítomnost termu vůči společnému vektoru.
Příklad: Pro jednoduchou demonstraci vytvoření společného vektoru dokumentů pomocí vektorového zápisu budeme uvažovat tři dokumenty, kde je pro jednoduchost každý tvořen -6-
jednou větou [39]: Dokument A: „The man walked the dog“ Dokument B: „The man took the dog to the park“ Dokument C: „The dog went to the park“ Z těchto tří dokumentů je sestrojen společný vektor vk, který obsahuje všechna navzájem různá slova, které se ve výčtu kolekce dokumentů vyskytují. vk = (The, man, walked, dog, took, to, park, went) Následně jsou sestaveny vektory všech ostatních dokumentů vzhledem ke společnému vektoru korpusu. K sestavení vektorů samotných dokumentů se používá několika různých technik. Vzájemná podobnost dokumentů je poté posuzována na základě vzájemné polohy vektorů dokumentů v prostoru. Respektive podle jejich vzdálenosti, velikosti svírajícího úhlu a jiných metrik.
3.2.1 Binární zápis vektoru V případě reprezentace dokumentů binárním vektorovým zápisem jde o vyjádření přítomnosti jednotlivých termů in ve společném vektoru dokumentů vk = (i1, i2, i3,…, in). Vektory dokumentů mají stejnou dimenzi jako společný vektor vk. Logickou hodnotou „1“ má parametr tn vektoru dokumentu vA = (t1, t2, t3, ..., tn) v případě, obsahuje-li výčet jeho termů slovo ze společného vektoru vk. V opačném případě nabývá logické hodnoty „0“. = 1 ⇔
∈
Z dokumentů uvedených v předchozí kapitole je tedy nejprve sestaven společný vektor, který obsahuje všechna slova dokumentů v kolekci: vk = (The, man, walked, dog, took, to, park, went) -7-
Binární zápis dokumentů (uvedených výše) pomocí vektorů bude vypadat vzhledem k vektoru korpusu vk takto: vA = ( 1 1 1 1 0 0 0 0 ) vB = ( 1 1 0 1 1 1 1 0 ) vC = ( 1 0 0 1 0 1 1 1 ) Z vektorů jednotlivých dokumentů je sestavena matice korpusu „A“, kde sloupce reprezentují vektory dokumentů.
1 1 1 1 0 0 0 0
=
1 1 0 1 1 1 1 0
1 0 0 1 0 1 1 1
Jak je z binárního zápisu vidět, čím více „1“ se objeví na pozicích vektoru vybraného dokumentu, tím je vektor dokumentu podobnější vektoru korpusu. Jde však o zkreslující informaci, jejíž podstata spočívá ve ztrátě informace o frekvenci výskytu termů v dokumentech. Pro uvedené nedostatky je vhodné použít tuto metodu do jednoduchých vyhledávačů. Mějme korpus dokumentů, ve kterých chceme vyhledávat, vyjádřen maticí A. Její sloupce reprezentují binární zápisy vektorů jednotlivých dokumentů korpusu (v1...vn). Zadaný dotaz D je převeden na nový vektor vd, který má stejnou dimenzi jako společný vektor korpusu vk. Podle metody binárního zápisu jsou stanoveny hodnoty parametrů vektoru dotazu vd a poté je přepočítána podobnost vektoru vd se všemi ostatními vektory v1...n v matici A. Používanou metrikou pro takový výpočet je například „cosinová vzdálenost“. =
∑
∑
(
×
) × ∑
(
)
.
Výsledky dotazu jsou pak seřazeny podle relevance, kde nejlepší (první zobrazený) je reprezentován největší hodnotou
Následující metody číselného vyjádření vektoru dokážou uchovat informaci o frekvenci jednotlivých termů. Jde o metody frekvenčních výskytů (TF), které lze dále upravit tak, aby -8-
zohlednily délku dokumentu a důležitost slov (TF-IDF). V takovém případě se číselnému vyjádření jednotlivých složek vektoru říká „váha“ termu.
3.2.2 Frekvenční zápis vektoru (TF) Metoda TF (Term Frekvency) oproti zápisu v binární podobě poskytuje cenou informaci v podobě skutečného počtu výskytů daného slova (termu) v dokumentu a tím zdokonaluje vyjádření jeho „váhy“. Postup metody spočívá opět v sestavení vektoru vk, na jehož základě se sestrojí jednotlivé vektory odpovídající zadaným dokumentům. Parametry jednotlivých vektorů jsou tvořeny číselným vyjádřením frekvence výskytu termu v dokumentu. Původní vektor kolekce: vk = (The, man, walked, dog, took, to, park, went) Pro přehlednost je vhodné opět sestrojit matici dokumentů A. Jednotlivé položky vyjadřují frekvenci výskytů termů obsažených ve vk. Tabulka 1 – Vyjádření výskytu jednotlivých slov v dokumentech
dokument A
dokument B
dokument C
the
2
3
2
man
1
1
0
walked
1
0
0
dog
1
1
1
took
0
1
0
to
0
1
1
park
0
1
1
went
0
0
1
Jednotlivé sloupce matice výskytů představují frekvenční vektory posuzovaných dokumentů. Vektory dokumentů tedy vypadají následovně: vA = ( 2 1 1 1 0 0 0 0 ) vB = ( 3 1 0 1 1 1 1 0 ) -9-
vC = ( 2 0 0 1 0 1 1 1 ) Jak je vidět, jsou zde exponována nepodstatná slova, ačkoli mají nevypovídající, často mizivou hodnotu – spojky, předložky a podobně. V případě vzorových 3 částí textů (dokumentů) je nejvíce zvýrazněné slovo „The“, které určitě není nositelem informací reprezentujících obsah dokumentu. V následujících kapitolách, které se věnují redukci dimenze vektorového prostoru, budou takové termy z výpočtů odstraněny. Metodu TF je vhodné normalizovat s ohledem na váhu jednotlivých termů, například použitím „Euklidovské normy“ a převodu na jednotkový vektor. " #" =
( #,
# ) %#
'
=&
#
" #"
Takovému vyjádření se říká „normovaný frekvenční zápis“ [36]. Tento způsob je vhodné využít pro případ významně rozdílných velikostí posuzovaných dokumentů. Výpočet euklidovské normy pro jednotlivé vektory dokumentů: ‖ ‖ ‖
‖ = )2 + 1 + 1 + 1 + 0 + 0 + 0 + 0 = √7
.‖ 1‖
= )3 + 1 + 0 + 1 + 1 + 1 + 1 + 0 = √14
= )2 + 0 + 0 + 1 + 0 + 1 + 1 + 1 = √8
Přepočet na jednotkové vektory:
2 1 1 1 % = 3 , , , , 0,0,0,04 = (0.76, 0.38, 0.38, 0.38, 0, 0, 0, 0) √7 √7 √7 √7 3 1 1 1 1 1 %. = 3 , , 0, , , , , 04 = (0.80, 0.27, 0, 0.27, 0.27, 0.27, 0.27, 0) √14 √14 √14 √14 √14 √14 2 1 1 1 1 %1 = 3 , 0,0, , 0, , , 4 = (0.71, 0, 0, 0.35, 0, 0.35, 0.35, 0.35) √8 √8 √8 √8 √8
Výsledná matice Â, s vyjádřením vah termů, je zkonstruována transponováním normovaných (jednotkových) vektorů.
- 10 -
=
2 1 1 1 0 0 0 0
3 1 0 1 1 1 1 0
2 0 0 1 7 = 0 1 1 1
0,76 0,38 0,38 0,38 0 0 0 0
0,80 0,27 0 0,27 0,27 0,27 0,27 0
0,71 0 0 0,35 0 0,35 0,35 0,35
Sloupce matice  představují normované vektory původních dokumentů, kde je zohledněna jak délka dokumentu, tak počet výskytu jednotlivých termů.
3.2.3 Frekvenční zápis vektoru s vyjádřením důležitosti slova (TF-IDF) Metoda TF-IDF (Term Frequency - Inverse Document Frequency) je modifikací frekvenční metody, která využívá ke stanovení důležitosti slova pokročilejší metodu inverzního vektoru. Základem je výpočet dvou vektorů tf a idf, které udávají výslednou polohu vektorů v prostoru. TF-IDF zajišťuje zohlednění nejen počtu výskytů daného termu v dokumentu, ale bere v úvahu také délky porovnávaných dokumentů a důležitost jednotlivých termů (slov). Vektor idf představuje již zmíněnou „důležitost slova“. Vychází z úvahy, že čím častěji se slovo v dokumentu vyskytuje, tím méně je důležité. Typickým příkladem jsou slovní druhy, které budou v následujících kapitolách popsány jako „Stop-slova“. Matematicky lze závislost mezi počtem výskytů slova a jeho důležitostí vyjádřit jako podíl logaritmu počtu porovnávaných dokumentů D a počtu dokumentů j, ve kterých je slovo obsaženo. Důležitost slova je tedy počítána dle následujícího vzorce:
= 89 = log ( ) >
Výpočet vektoru idf ze zadaných frekvenčních vektorů tf:
tfA = ( 2 1 1 1 0 0 0 0 )
tfB = ( 3 1 0 1 1 1 1 0 ) tfC = ( 2 0 0 1 0 1 1 1 )
3 3 3 3 3 3 3 3 89 = (D E , D E , D E , D E , D E , D E , D E , D E ) 2 1 3 1 2 2 1 3 - 11 -
idf = ( 0 0,18 0,18 0 0,48 0,18 0,18 0,48 )
Dalším krokem pro vyčíslení výsledného vektoru je součin idf s jednotlivými vektory tf.
Vypočtené hodnoty parametrů vektorů, vyjadřují význam slov v dokumentu. Tabulka 2 – Vyjádření důležitosti termů
the
man
walked
dog
took
to
park
went
tfA * idf
0
0,18
0,18
0
0
0
0
0
tfB * idf
0
0,18
0
0
0,48
0,18
0,18
0
tfC * idf
0
0
0
0
0
0,18
0,18
0,48
Z výsledného součinu je patrné, že termíny, které se vyskytují ve všech dokumentech, mají nízkou váhu (blížící se nule) a termíny, které se objevují pouze v některých dokumentech, mají váhu vyšší. Budeme-li pro jednoduchost uvažovat 3 dokumenty zobrazené ve dvou-rozměrném prostoru, pak lze graficky znázornit dokumenty následujícím způsobem. Obrázek 5 – Vector space model – vyjádření tří dokumentů ABC
Míru podobnosti dokumentů lze měřit pomocí úhlu Theta, který mezi sebou vektory svírají. Čím menší úhel mezi sebou vektory svírají, tím jsou si podobnější. Z předchozího obrázku je vidět, že dokument B je podobnější C nežli A. Často používanou metrikou, je cosinova míra podobnosti. Ta nabývá hodnot od „0“ do „1“. Čím vyšší je její hodnota, tím podobnější jsou
- 12 -
si vektory [39, 44]. H 8 IJ
= cos( ) =
∗N = ǁAǁ ǁBǁ )∑
∑
P ∗ I
(P ) ∗ )∑
(I )
Dříve se využívalo k porovnání podobnosti dokumentů vyjádření pomocí vzdálenosti vektorů (euklidovská vzdálenost). Tato metoda však není vhodná především z důvodu neschopnosti reagovat na velikost porovnávaných dokumentů. V případě duplikace všech slov v dokumentu B by mělo za následek dvojnásobné zvětšení jeho vektoru, čímž by se značně zmenšila podobnost s dokumentem C, ačkoliv by se obsahově dokument B nezměnil [44]. Aritmetické vyjádření vektorů je vcelku snadné, nicméně jako problém se jeví počet složek vektorů, který zároveň reprezentuje počet dimenzí prostoru. Tento problém byl popsán jako „Curse of dimensionality“ (dimenzionální prokletí). Výsledný model je tedy situován v n-dimenzionálním prostoru, kde n udává celkový počet unikátních slov všech dokumentů, které jsou porovnávány. Celková dimenze tedy exponenciálně roste v závislosti na počtu dokumentů potažmo jejich slov [18, 44]. Uvedené vektorové zápisy jsou však náročné nejen výpočetně, ale také časově. Při použití skutečných dokumentů a rozsáhlých korpusů, které mohou obsahovat více 108 termů (viz. SYN2010), by bylo jejich zpracování nesmírně náročné. Z tohoto důvodu je nutné dimenze vektorů snížit.
3.3
Redukce dimenze Následující kapitoly budou věnovány úkolu, jak snížit dimenzi při zachování podstatných
informací. Z hlediska porovnání vektorů v prostoru vyplývá, čím nižší je dimenze, tím snažší je matematické vyjádření závislostí. Totéž již nelze říci o zachování informačních hodnot dokumentů. Je nutné stanovit takovou velikost dimenze, která ještě zachová obsah a zároveň maximálně sníží počet parametrů vektoru. Redukce dimenze lze provádět několika způsoby. Mezi nejčastěji využívané patří „pos-tagging“
(odstranění
stop-slov),
sloučení
„stemmizace“, sloučení synonym a další.
- 13 -
termů
na
základě
„lemmatizace“,
3.3.1 Odstranění Stop-slov / Pos-tagging Jedná se o nejjednodušší metodu přístupu k redukci dimenze vektorového prostoru. Spočívá ve vynechání nepodstatných slovních druhů, které nejsou nositeli stěžejních informací. Jinými slovy jde o termy, které mají minimální nebo nulovou informační hodnotu. S trochou nadsázky by se tato slova dala nazvat jakousi formou informační redundance. Typickým příkladem „Stop-slov“ jsou převážně slovní druhy spojky, předložky, částice a citoslovce. Po jejich odstranění značně klesne dimenze vektoru, reprezentujícího textový dokument. Naopak mezi nositele informací se řadí slovní druhy jako podstatná jména, přídavná jména, slovesa a příslovce. Redukce vektorového prostou touto metodou nevyužívá znalostí o konstrukci jazyka. Nedokáže ani určit, zda informace vyjádřené v číslovkách jsou podstatné či nikoliv. Z toho důvodu některé přístupy převádějí číselnou informaci do textové podoby, jiné odstraňují řadové číslovky a zachovávají konkrétní číselné hodnoty a podobně. Jeden z možných průběhů metody: 1) převedení všech termů dokumentu do lemmatizované podoby; 2) porovnání termů se souborem stop-slov a odstranění nalezených shod. Původní dokument: „Softwarový strašák na studenty, kteří chtěli opsat závěrečnou práci z internetu, se stane noční můrou i pro akademiky. Informatici z brněnské Masarykovy univerzity totiž rozšířili svůj systém porovnávající texty a odhalující podobnosti i na odborné články, publikace a jiná díla.“ [45] Možný vzhled dokumentu po lemmatizaci a odstranění Stop-slov: Software strašák student chtít opsat závěr práce internet stát noc můra akademik. Informatik Brno Masaryk univerzita rozšířit systém porovnat text odhalit podobnost odborný článek publikace dílo. Velikost původního dokumentu je 40 termů a po úpravě jen 26 termů. Na výše uvedeném příkladu je vidět, účinnost metody vzhledem ke snížení velikosti dimenze vektorů dokumentů.
- 14 -
Seznam nejčastějších českých stop-slov je uveden v příloze č. 1 této práce.
3.3.2 Lemmatizace Při procesu lemmatizace je hledán základní neboli normalizovaný tvar daného slova tzv. „Lemma“. Za normalizovaný stav je považován u podstatných jmen první pád jednotného čísla, u přídavných jmen první pád jednotného čísla základního stupně mužského rodu, u sloves jde o tvar slova v infinitivu a podobně [10]. Algoritmů pro lemmatizaci je celá řada. Dají se rozdělit do dvou základních skupin a to vyhledávací nad bází dat nebo algoritmy využívající pravidla o znalosti jazyka. U strojového zpracování je vhodnější využít pro lemmatizaci algoritmů, které využívají větší znalosti o struktuře jazyka. Ty pak mají za úkol najít termy o stejném základu a v porovnání s ostatními identifikovanými termy odstranit přípony, předpony, či jiné možné koncovky slov, které jsou způsobeny jejich ohebností. Takové algoritmy se nazývají „Suffix Stripping“ [37].
3.3.2.1 Brute Force algoritmus Tento algoritmus patří mezi skupinu prohledávacích, přičemž není využito znalosti konstrukce jazyka. Tento algoritmus je založen na principu „hrubé síly“. Každý term dokumentu je porovnán s obsáhlou bází dat, ve které jsou uloženy základní tvary slov a jejich jazykové modifikace. Již z tohoto pohledu je tento algoritmus velice časově a výpočetně náročný. Zároveň vyžaduje dostupnost velice obsáhlé báze dat, která je vytvořena znalcem. Tabulka 3 – Ukázka báze dat pro algoritmus Brute Force
term dokumentu
lemma
byl
být
byla
být
bylo
být
byli
být
bude
být
....
....
- 15 -
U strojového zpracování pomocí takového lemmatizátoru existuje však problém zvaný víceznačnost (mnohoznačnost). Jednoduché lemmatizátory, které nezkoumají kontext, nemusí správně posoudit význam slova, které normalizují. Tím může dojít k nalezení špatného normalizovaného tvaru (lemma). Příkladem lze uvést slovo „tancích“, které může mít normalizovaný tvar „tanec“ nebo „tank“. Původní text: „Jeden z nejhodnotnějších zdrojů o maďarských tancích.“ Lemmatizovaný text: „Jedna/Jíst z hodnotný zdroj o maďarský tanec/tank.“ Tento příklad demonstruje nejčastější chyby lemmatizátorů, založených na principu Brute-force. Tyto chyby mohou být stěžejní pro následující zpracování a analýzu dokumentu například při jejich klasifikaci. Při vyšší koncentraci takovýchto chyb by mohlo dojít k nesprávnému zařazení dokumentu do třídy „obrněná vozidla“, místo do třídy „umění“.
3.3.2.2 Lovinsův algoritmus Jedná se o algoritmus pracující se znalostními pravidly – Suffix Stripping. Vyžaduje již podrobné znalosti o stavbě jazyka. Pomocí nich se snaží najít lemma pomocí odstranění přípon. Algoritmus vychází ze dvou principů Iteration a Longest-match. Princip Iterace pracuje s příponami postupně. Je stanoveno několik skupin neboli tříd přípon, které se odstraňují postupně. 1. třída přípon obsahuje dále již nerozšiřující přípony - koncovky. Například termy „silní x silná x silné“ mají koncovky první třídy: „í, á, é“, ale stejné lemma „siln“. Do této třídy patří také víceznakové koncovky, například u termů „vyšší, prudší“ - „ší“. 2. třídu tvoří přípony, které ve skladbě slova předcházejí 1.třídu přípon. Příkladem mohou být termy „silnější x rychlejší“. Lemma slov tvoří „siln“ a „rychl“, 2.třídu přípony „ěj, ej“ a 1.třídu přípony „ší“. V konečném důsledku tyto třídy dohromady tvoří různé tvary slov (například siln-ĚJ-ŠÍ). Princip iterace tedy postupně odstraňuje přípony podle priority tříd, nejprve 1. třídu, 2. třídu a tak dále. Tímto postupem je získáno Lemma.
- 16 -
Přístup Longest-match pracuje na principu nalezení nejdelší známé přípony a tu odstraní. Například tedy u termu „silnější“ odstraní rovnou celou příponu „ější“. Oba zmíněné přístupy vyžadují rozsáhlou bázi dat, která obsahuje známé přípony případně jejich kombinace. Uvedené algoritmy jsou využívány v automatických generátorech lemmatizovaných textů. Příkladem aplikace lemmatizátoru suffix-stripping je generátor „LemmaGen“ či „AIKA“. Obrázek 6 – Ukázka zpracování článku přílohy č. 2 pomocí online služby LemmaGen [33]
Lemmatizace je jedním ze základních způsobů snížení dimenze u vektorového vyjádření textového dokumentu. Využívá se také při fulltextovém vyhledávání, kategorizaci (klasifikaci), indexaci dokumentů a podobně. Následující příklad demonstruje rozdílné výsledky lemmatizace pomocí Brute force a Lovinsova algoritmu. Lemmatizována byla první věta z článku přílohy č. 2, této práce. Původní text: „Softwarový strašák na studenty, kteří by chtěli opsat svou závěrečnou práci z internetu, se stane noční můrou i pro akademiky.“ [45] Lemmatizovaný text pomocí Brute force algoritmu: Software strašák na student, který by chtít opsat své závěr práce z internet, se stát noc můra i pro akademik. Lemmatizovaný text pomocí sufix-stripping algoritmu: Softwar strašák na student, kte by cht sv závěrečn prác z internet, s stan nočn můr i pro akademik.
- 17 -
3.3.3 Stemming Stemming je podobný procesu lemmatizace až na skutečnost, že se v tomto případě nehledá normalizovaná forma, nýbrž kořen (stem) slova. Výhodou stemmingu oproti lemmatizaci je větší snížení dimenze vektoru reprezentujícího textový dokument, nevýhodou je nutnost existence široké databáze slov s jejich kořeny – Brute-force algoritmy. Příklad: termy vodárna, vodovod, vodník, zavodnit, odvodnit, voda, … společný kořen slova je „vod“. Stemming si snadno poradí s morfologickými koncovkami, předponami, odvozenými slovy a podobně. Jak je vidět, je mnohem efektivnější nežli lemmatizace při redukci dimenzí, ale nese sebou závažný problém. Tím jsou slova, která nemají společný význam, ale mají stejný kořen slova. Příkladem může být slovo „lední“ jehož kořenem slova je „led“, avšak pro slovo „leda“ je taktéž kořen slova „led“. Toto je problém zejména flektivních jazyků, jako je čeština. Stemming se proto s výhodou používá například pro anglický jazyk, ale pro flektivní (ohebné) jazyky je vhodné použít spíše Lemmatizaci. Ani jedna varianta ať už lemmatizace či stemming si však neumí poradit se slovy, která mají více významů. Pro ilustraci slovo „pánev“ má význam v oblasti geografického útvaru, části těla či nádobí. V takovém případě by se dimenze tedy snížila o slova, která nemají významově nic společného. Tyto popsané problémy umí řešit až vyšší metody sémantických analýz, kterou je například LSA (Latent Semantic Analysis).
3.3.4 Očištění od synonym Předchozí metody redukce dimenze vektorového prostoru již dokázaly vynechat Stop-slova či sloučit termy, které byli v různých jazykových tvarech (ohebnost slov). Tato metoda přináší další možnost redukce vektorového prostoru postavenou především na bázi identifikovaných synonym. Pro takovéto procesy existují lexikální databáze například WordNet [10]. Jde o databázi seskupující jednotlivá slova v synonymických řadách tzv. synsetech. Českou variantu WordNetu je „Český WordNet“, který vyvíjí Centrum zpracování přirozeného jazyka na Fakultě informatiky Masarykovy univerzity v Brně.
- 18 -
Tabulka 4 – Příklad slovníku synonym (synonymických řad)
Slovo
synonymum 1
synonymum 2
...
počítač
PC
computer
...
řeka
potok
bystřina
...
automobil
vozidlo
auto
...
labyrint
bludiště
babylon
...
...
...
...
...
Na základě takového slovníku jsou termy identifikované jako synonyma nahrazeny jedním prvotním výrazem. V případě potřeby, co největší redukce dimenze je možné využít variantu zobecnění významu termů. Jde o nahrazení slova jejím nadřazeným slovem. Jde o zpětnou generalizaci slov. Obrázek 7 – Ukázka nadřazených termů (generalizace)
Při použití této metody však dochází k velkému zobecnění samotného dokumentu. Proto tento způsob omezení dimenze vektorů je vhodný spíše pro klasifikaci dokumentů.
3.3.5 Výběr příznaků - feature selection Výše zmíněný problém „Curse of dimensionality“ je možné řešit metodou výběru příznaků. Tato metoda vychází z poznatku, že k popsání dokumentu není třeba všech složek vektoru, ale postačí pouze klíčové termy. Metoda výběru příznaků se zabývá vyhledáváním takových termů, které mají dostatečnou vypovídající hodnotu pro daný textový dokument [8]. Před samotným výběrem příznaků je vhodné použít předchozí metody redukce dimenze. - 19 -
Zvláště důležité je odstranění stop-slov či lemmatizace. Stemmingu či nahrazení nadřazenými termy není vhodný především z důvodu, následné absence původních termů ve výsledném vektoru. Selekce příznaků je tedy výběr vhodných parametrů původního vektoru. V žádném případě neplatí, že čím více příznaků bude vybráno, tím lépe. Při zvolené velké dimenzi tzv. „vektoru příznaků“, se zvyšuje pravděpodobnost špatné klasifikace dokumentu (začlenění do nevhodných tematických okruhů). Zároveň, se vzrůstajícím počtem parametrů vektoru příznaků, se zvyšuje výpočetní a časová náročnost dalšího zpracování dokumentů. Nízká dimenze naopak nemusí mít vypovídající hodnotu o daném souboru. Po prvotní redukci dimenze pomocí vypuštění stop-slov, lemmatizace a podobně, se pro další zpracování používají sofistikovanější metody statistických funkcí, jako je například relativní četnost (normovaný frekvenční výskyt). U selekce příznaků platí, že vytvořená množina parametrů vektoru, je podmnožinou základního vektoru. Jinými slovy žádný term není nahrazen jiným, což by bylo v případě stemmingu porušeno. Dochází tak k zachování podobnosti s původním dokumentem, což může být nezbytné například v případě analýzy dokumentů při hledání duplikátů, plagiátů a podobně [8, 4]. Pro výběr příznaků je vhodné použít metodu uvedenou v předchozích kapitolách, například frekvenční výskyt s posouzením důležitosti slov, neboli TF-IDF.
3.3.6 Extrakce příznaků – feature extraction Metoda extrakce příznaků je založená na jazykové znalosti, kdy jsou jednotlivé termy nahrazovány nadřazenými výrazy a to buď pomocí stemmingu, nebo na základě generalizace slov. Jejím cílem je ještě větší snížení dimenze vektoru oproti metodám „Výběru příznaků“. Metody extrakce příznaků si navíc dokážou poradit se slovy souzvučnými (synonymy). Jako příklad lze uvést synonymickou řadu „statečný“, „smělý“, „udatný“, „heroický“, kde jsou tato slova nahrazena prvním termem z řady. V mnoha případech se v dokumentech mohou vyskytovat nedělitelné sousloví, tzv. „ngramy“, kde n značí počet termů. Ty je vhodné zpracovávat jako celek, neboť tak udávají komplexní informaci. Příkladem mohou být víceslovné názvy měst, organizací a podobně (Univerzita Hradec Králové, Autorský zákon, atd.). - 20 -
3.3.7 Extrakce frází Jak již bylo výše řečeno, vektorový zápis textového dokumentu je složen z termů. Ty mohou být tvořeny 1 až n slovy (n-gramy) v závislosti na následujícím účelu zpracování dokumentu. Jednotlivé N-gramy se extrahují po předzpracování textového dokumentu vynecháním stop-slov, provedené lemmatizaci či stemmingu. Dvouslovné fráze se nazývají „bigramy“, trojslovné „trigramy“ a víceslovné „N-gramy“. Čím víceslovné jsou termy vybírány, tím menší je pravděpodobnost nalezení takového Ngramu v jiném dokumentů. Tato vlastnost lze s výhodou uplatnit u detekce plagiátů, kde platí, čím více je nalezeno stejných n-gramů, tím větší je pravděpodobnost plagiátorství [35].
3.3.7.1 Mi-score (mutual Information) Mi-score je metoda extrakce parametrů založená na statistických funkcích. Z názvu je patrné, že se jedná o posouzení vzájemné informace, která je definována pro jevy x a y následujícím matematickým vyjádřením [4, 33]. Q (R, S) = D E
T(R, S) T(R) ∗ T(S)
Kde P(x) je pravděpodobnost výskytu slova x, P(y) je pravděpodobnost výskytu slova y a P(x,y) je potom pravděpodobnost výskytu slova y v kontextu x. Kontext x značí zadaný počet pozic od posuzovaného slova na obě strany. T(R) =
9(R) 9(S) 9(R, S) T(S) = T(R, S) = U U U
Kde f(x) a f(y) jsou počty samostatných výskytů posuzovaných slov a f(x,y) je počet společných výskytů těchto slov. Z hlediska pravděpodobnosti výskytu jednotlivých slov je N celkový počet slov v korpusu dokumentů. Nevýhodou této metody je vysoká závislost na frekvenci slov v dokumentu. Nejvyšších hodnot totiž dosahují dvojice slov s nízkou frekvencí. Z tohoto důvodu je vhodné vypustit slova s absolutní frekvencí nižší než je předem zvolená hranice. Ta je závislá na počtu požadovaných příznaků [3, 33].
- 21 -
Příklad: Pro názornou demonstraci a jednoduchost výpočtu byl vybrán upravený výňatek článku z přílohy č. 2 – „Nový systém odhalí plagiátorství mezi vědci“. Kontext budeme uvažovat 1, čili nejbližší soused slova. Výpočet Mi-score bude demonstrován pro term „Open“ a jeho nejbližší sousedy („hnutí“ a „Access“). Původní text: „Repozitar.cz umožní také zpřístupnit výsledky vědy širší veřejnosti při zachování vůle autorů. K tzv. Open Access k vědeckým informacím, který prosazuje hnutí Open Access, se MU přihlásila loni v říjnu podpisem Berlínské deklarace. Informatici MU již proto také vytvořili vlastní univerzitní repozitář, který rozšiřuje stávající systém evidence publikací“ Lemmatizovaný text s vypuštěnými stop-slovy: „Repozitar.cz umožnit zpřístupnit výsledek věda široká veřejnost zachovat vůle autor Open Access vědecký informace prosazovat hnutí Open Access MU hlásit loni říjen podpis Berlín deklarace Informatik MU tvořit univerzita repozitář rozšiřovat systém evidence publikace.“ Pro každé slovo je spočítána pravděpodobnost jeho výskytu:
T( HVJ) =
pravděpodobnost výskytu slova Open:
W(XYZ )
T(P V ) =
pravděpodobnost výskytu slova Access:
T(ℎJc í) =
pravděpodobnost výskytu slova Access:
[
= \] = 0,059
W(_``Zaa) [
W(e fgí) [
= \] = 0,059
= \] = 0,029
pravděpodobnost společného výskytu slov hutí, open a access v kontextu 1: T( HVJ, P V ) = T( HVJ, ℎJc í) =
W(XYZ , _``Zaa) [
W(XYZ , e fgí) [
= \] = 0,059
= \] = 0,029
Výsledné mi-score termů je vyjádřeno takto: Q ( HVJ, P V ) = D E
T( HVJ, P V ) 0,059 =D E = 4,079 T( HVJ) ∗ T(P V ) 0,059 ∗ 0,059 - 22 -
T( HVJ, ℎJc í) 0,029 =D E = 4,138 T( HVJ) ∗ T(P V ) 0,059 ∗ 0,029
Q ( HVJ, ℎJc í) = D E
Mi-score lze vypočítat také pomocí vzorce, který využívá na místo pravděpodobnosti výskytu frekvenční výskyt slov: Q (R, S) = D E
T( HVJ, P V ) = D E
U ∗ 9(R, S) 9(R) ∗ 9(S)
U ∗ 9( HVJ, P V ) 34 ∗ 2 =D E = 4,087 9( HVJ) ∗ 9(P V ) 2∗2
Nevýhodou této metody je značná závislost na samotné frekvenci jednotlivých slov (bez společného výskytu). Z tohoto důvodu dosahují nejvyššího mi-score slova s nízkou frekvencí. Některé algoritmy umožňují z tohoto důvodu nastavit spodní prahovou hodnotu frekvenčního výskytu slov. Pro termy, které nesplní toto kriterium, není mi-score počítáno [34].
3.3.7.2 T-score Jedná se o metodu, která na rozdíl od předchozího mi-score, zkoumá náhodnost jevů. Jinými slovy testuje, zda frekvence termů a jejich společného výskytu odpovídá náhodnému rozložení termů v korpusu. Čím vyšší je hodnota t-score, tím pravděpodobnější je správná identifikace sousloví. Takové lze označit za kolokaci (kombinace slov) [34]. h=
9(R) ∗ 9(S) U )9(R, S)
9(R, S) −
Kde f(x) a f(y) jsou frekvence výskytů jednotlivých slov, f(x,y) frekvence společného výskytu a N je celkový počet termů v dokumentu. Příklad: Pro výpočet t-score vezmeme příklad z předchozí kapitoly. h( HVJ, P V ) =
9(R) ∗ 9(S) 2∗2 2 − 34 1,88 U = = = 1,33 1,41 √2 )9 (R, S)
9(R, S) −
- 23 -
h( HVJ, ℎJc í) =
9(R) ∗ 9(S) 2∗1 1− 34 = 1,88 = 0,94 U = 1,41 √1 )9 (R, S)
9(R, S) −
3.3.7.3 Latentní sémantická analýza (LSA) Tato metoda, jak již název naznačuje, dokáže pracovat s významovou složkou slov. Pro stanovení dimenzí již nejsou důležitá slova ani jejich lingvistický základ, nýbrž jejich tematické zaměření. LSA v tomto smyslu zavádí nový pojem a tím je koncept (draft). Koncept představuje doménu neboli nadřazený termín slov [12, 39]. Koncepty jsou stanoveny na základě kolokací. Jako příklad lze uvést termy z kapitoly č. 3.2. Dokument A: „The man walked the dog.“ Dokument B: „The man took the dog to the park.“ Kde je slovo „man“ spojeno v dokumentu A se slovem „walked“. V dokumentu B se slovem „took“. Stejná vazba platí, pokud vezmeme místo slova „man“ slovo „dog“. Z tohoto vyplývá, že slova „walked“ a „took“ mohou nést stejný informační význam. Ve výsledku budou tedy slova „walked“ a „took“ tvořit jeden „koncept“ (draft). Vazby mezi takovými termy se nazývají „kolokace“. Před samotným rozkladem je vhodné provést redukci dimenze vektorového prostoru pomocí lemmatizace a odstranění stop-slov, především z důvodu časové a výpočet náročnosti následných výpočtů. Věty dokumentů jsou reprezentovány normalizovanými vektory. Z nich je sestavena matice A o velikosti m x n, kde sloupce (n) reprezentují vektory jednotlivých vět a řádky (m) pak samotná slova. Po sestavení matice A je třeba nalézt výše zmíněné kolokace a z nich vyplývající koncepty. Tím se opět sníží dimenze vektorového prostoru. Samotná redukce probíhá pomocí metody Singular value decomposition (SVD).
3.3.7.4 Singular value decomposition (SVD) Singular value decomposition je metoda redukce dimenze prostoru, vyhledávající kolokace mezi jednotlivými termy. Při jejich nalezení sjednotí termy do jednoho konceptu
- 24 -
a tím sníží dimenzi prostoru. Pro většinu případů posuzovaných dokumentů je 1000 postačující hodnota počtu konceptů [12]. Stanovení počtu konceptů však závisí na účelu využití LSA. Pro indexaci dokumentu bude požadován vyšší počet nežli při využití pro vyhledávání plagiátů a podobně. SVD vychází z dekompozice matice dokumentu. Matici A rozkládá SVD na tři další matice ortogonální U, diagonální Σ a transponovanou ortogonální VT. Matice U je velikosti mxm. Její sloupce jsou nazývány levé singulární vektory. Termy jsou zde reprezentovány řádkovými vektory, které tvoří lineárně nezávislé komponenty. Společný výskyt termů je vyjádřen pomocí znaménka +/-. Σ je matice velikosti m x n, kde prvky hlavní diagonály reprezentují singulární hodnoty. Ty vyjadřují závislost jednotlivých termů. Matice VT je řádkově ortonormální o velikosti k x k, kde k je počet nenulových prvků hlavní diagonály matice Σ . Sloupce matice VT reprezentují singulární vektory vět. Z těchto matic je pomocí počtu nenulových prvků hlavní diagonály matice Σ stanovena redukovaná dimenze prostoru k. Tímto se značně sníží časová náročnost dalších výpočtů, jak je vidět na následujícím obrázku. Dimenzi je možné ještě snížit, pokud je požadovaný počet hledaných termů nižší než počet nenulových prvků hlavní diagonály. Obrázek 8 – Redukované matice [6]
Příklad: Pro sestrojení matice A bude z důvodu přehlednosti použit příklad z kapitoly 3.2. v1: „The man walked the dog“ v2: „The man took the dog to the park“
- 25 -
v3: „The dog went to the park“ Sestavení společného vektoru vk (abecedně seřazený bez stop-slov): vk = (The, man, walked, dog, took, to, park, went) Vyjádření matice dokumentu A a normované matice Â:
=
2 1 1 1 0 0 0 0
3 1 0 1 1 1 1 0
2 0 0 1 7 = 0 1 1 1
0,76 0,38 0,38 0,38 0 0 0 0
0,80 0,27 0 0,27 0,27 0,27 0,27 0
0,71 0 0 0,35 0 0,35 0,35 0,35
Matice A (Â) je zpravidla řídká matice, jelikož se slova (reprezentující řádky) v každé větě neopakují. V případě analýzy skutečného dokumentu by bylo zastoupení nulových hodnot v jednotlivých sloupcích, které reprezentují věty dokumentu, mnohem vyšší. Samotný postup rozkladu matice pomocí SVD není předmětem této práce, proto bylo pro výpočet ukázkového rozkladu matice A na matice U, Σ a VT využito aplikace Maple. Použité příkazy programu Maple: -
zadání normované matice Â:
-
pro výpočet singulárního rozkladu matic SVD je nutné využít balíček MTM, který obsahuje funkce pro jeho výpočet, volá se následujícím příkazem:
-
výpočet rozkladu na jednotlivé matice:
- 26 -
Výsledky SVD rozkladu:
Řádky matice U reprezentují vektory jednotlivých termů a vyjadřují jejich lineární nezávislost. Společné výskyty slov ve větách jsou vyjádřeny zápornými hodnotami. První sloupec, kde jsou samé záporné hodnoty, vyjadřuje základní společný výskyt termů v dokumentu. Ve druhém sloupci jsou vidět dvě skupiny slov. Společně se vyskytující jsou „took“, „to“, park“ a „went“. V další dimenzi se spolu vyskytují termy „walked“, „dog“,„went“, a tak dále. Slova, která jsou si blízká významem, nebo jde o synonyma, budou v m-dimenzionálním prostoru mapována blízko sebe – vytvoří shluk. Kombinace slov, která se vyskytuje v dokumentu často, je reprezentována jedním singulárním vektorem z VT.
Singulární hodnota z Σ, indikuje významnost kombinace slov v dokumentu. Věta, která obsahuje tuto kombinaci termů, bude promítnuta blízko k odpovídajícímu singulárnímu vektoru z matice VT. Singulární vektory tedy reprezentují koncepty dokumentu a singulární čísla jejich významnost [6]. Pro demonstraci redukce dimenze upravíme matice dle singulárních hodnot v Σ. Odstraní se odpovídající vektory z U a získáme následující redukované matice:
- 27 -
Odstraněním prvků reprezentujících dimenze, které nevykazují významnou změnu, je efektivně eliminován šum z vektorů slov. Nyní jsou dimenze 3 na rozdíl od původních 8. Vektory slov nyní obsahují ty nejvýznamnější závislosti mezi slovy. Zjednoduší se tím výpočty podobnosti vektorů, vět či dokumentů při další analýze. LSA lze využít například při sumarizaci dokumentu, kdy se vypočítá matice B. Její sloupce reprezentují věty, respektive vektory vět. Velikost vektoru vyjadřuje jeho váhu (ohodnocení). Do sumarizace se začlení ty věty, které dosáhnou největší váhy. N = j ∗ kl
= )(N ) + (N ) + ⋯ + (N' )
4 Úlohy pro analýzu textu – Data mining Tato kapitola má za úkol přiblížit, k jakému účelu lze metody analýzy textových dokumentů v praktických úlohách využít. Tuto otázku řeší soubor metod nazývaný Data-minig. Definice: „Data-mining lze charakterizovat jako proces extrakce relevantních, předem neznámých nebo nedefinovaných informací z velmi rozsáhlých databází. Nicméně data mining lze aplikovat i na malé soubory. Důležitou vlastností data miningu, je že se jedná o analýzy odvozované z obsahu dat, nikoliv předem specifikované uživatelem nebo implementátorem. Jedná se především o odvozování prediktivních (předpovídaných) informací, nikoliv deskriptivních (popisných). To znamená, že proces data miningu lze definovat jako netriviální získávání implicitních, dříve neznámých a potenciálně užitečných informací.“ [15]. - 28 -
Jak je z předchozí definice patrné, jde především o zjištění skutečností, závislostí či relevantních informací, které nejsou na první pohled uživateli (manažerům) známy. S nasazením metodik automatických analýz lze prohledat obrovské množství uložených dat. Velké uplatnění přináší data-mining také ve světě obchodu, v marketingových kampaních, strategických rozhodovacích procesech a podobně. V případě, že by závěrem data-miningu byly již známé skutečnosti, nebo jednoduše odvoditelné skutečnosti, byla využitelnost a efektivnost dolování v datech nulová [11, 43]. V následujících kapitolách je popsáno několik základních úloh, kterými se data-mining zabývá. Vzhledem k rozsahu a množství algoritmů u jednotlivých úloh, není možné obsáhnout v této práci veškeré přístupy. U každé úlohy jsou tedy popsány vybrané algoritmy.
4.1
Indexace textových dokumentů Základním úkolem Indexace textových dokumentů je vytvořit takovou množinu termů,
která co nejlepším způsobem popisuje obsah a zaměření zkoumaného dokumentu. Indexaci lze rozdělit dle způsobu zpracování na dva základní typy: ruční a automatická. Ruční indexace je prováděna expertem. Ten stanoví potřebné množství termů a vybere hledanou množinu nejlépe popisujících zkoumaný dokument. Největší nevýhodou tohoto přístupu je doba potřebná pro sestavení takového indexového souboru a také nezbytná přítomnost experta na danou problematiku, což se projeví kromě jiného také ve finanční náročnosti. Navíc při nezávislé indexaci jednoho dokumentu dvěma různými experty je velmi pravděpodobné sestavení odlišných indexových souborů (počet termů či rozdílné termy). To je dáno jistou mírou subjektivity každého z expertů [1]. Automatická indexace má za úkol nedostatky ruční indexace odstranit. Počet termů je předem dán. Při pokročilé indexaci lze předem mít skupinu termů, ze které je následně indexový vektor sestavován. Takové indexaci se říká řízená. Samotný výběr termů spočívá v sestavení vektorového modelu, popsaného v předchozích kapitolách. Následnou aplikací metod na snížení dimenze a seřazení termů vektorového souboru dle jejich významu (například metoda TF-IDF) je sestaven vektor. Ten slouží k vytvoření indexového souboru na základě požadovaného množství termů. Do indexového souboru jsou vybírány termy na základě jejich významu. Termy, které se vyskytují v příliš mnoha dokumentech a tedy jejich TF-IDF se blíží k 0, nejsou vhodné, jelikož se s velkou pravděpodobností nejedená o nositele podstatných informací. Stejně tak nejsou vhodné termy, u kterých se TF-IDF blíží 1, to jsou - 29 -
termy, které jsou naopak svým výskytem v korpusu ojedinělé. V případě vysokého numerického vyčíslení TF-IDF jde převážně o příliš odborné názvy, které nejsou podstatou dokumentů [14]. Obrázek č. 9, znázorňuje závislost výskytu termů v dokumentech na analýze TF-IDF. Jako zdrojové dokumenty jsou pro jednoduchost použity dokumenty z předchozích kapitol. Příklad: Dokument A: „The man walked the dog.“ Dokument B: „The man took the dog to the park.“ Dokument C: „The dog went to the park.“ Společný vektor dokumentů, jehož vytvoření je demonstrováno v kapitole „3.2 Vector space model“, je tedy vk = (The, man, walked, dog, took, to, park, went). Za předpokladu, že dokument B má být indexován a zbylé dva dokumenty tvoří korpus, pak frekvenční zápis vektoru s vyjádřením důležitosti slova vypadá takto: Tabulka 5 – Vyjádření vah termů dokumentu B pro indexaci
the
man
walked
dog
took
to
park
went
počet souborů
3
2
1
3
1
2
2
1
tfB * idf
0
0,18
0
0
0,48
0,18
0,18
0
Obrázek 9 – Závislost výskytu termů v korpusu na TF-IDF
- 30 -
Termy se vybírají od středu intervalu, tedy TF-IDF = 0,5, v závislosti na požadovaném počtu termů, respektive na velikosti indexového souboru. Čím menší bude dimenze indexového souboru, tím více informací bude skryto, naopak čím větší dimenze tím obecnější bude popis, což není vhodné například u internetových vyhledávačů.
4.2
Shrnutí textu - sumarizace Definice: „Text that is produced from one or more texts, that contains a signifiant partion of the
information in the original text(s), and that is no longer then half of the original text(s).” [26] Sumarizace textu je tedy shrnutí dokumentů do kratší podoby, při zachování důležitých informací. Zároveň její délka nepřekračuje polovinu velikosti původního dokumentu. Sumarizaci lze nazvat také jako abstrakt, který je zcela diametrálně odlišný od předchozí úlohy indexace a to především ve skutečnosti, že sumarizace poskytuje ucelené informace. Nejde tedy pouze o termy, nýbrž o stručné větné vyjádření obsahu textových dokumentů. Existuje několik různých přístupů, jak tento abstrakt vytvořit. Podle způsobu přístupu k sumarizaci, lze tyto úlohy rozdělit na heuristické, statistické, grafové a další [26, 4].
4.2.1 Luhnova metoda Jednou z metod, jak z textového dokumentu vytvořit sumarizaci, je Luhnova metoda. Jde o statistickou metodu založenou na posuzování významu nikoliv elementárních částí dokumentů, jako jsou slova, nýbrž celých vět. Postup Luhnovy metody je následující. Pro každou větu Vi zpracovávaného dokumentu D je vytvořen vektor frekvencí výskytu jednotlivých termů tf. Dále je vytvořen inverzní vektor idf. Pomocí těchto dvou vektorů, respektive jejich skalárním součinem, je vypočtena významnost každé věty w [31].
no = 9op × 89op
Věta, která dosáhne nejvyššího významu je zahrnuta do výsledku sumarizace S [31]. q = maxunop v + q - 31 -
Jedna věta však nemusí mít dostačující vypovídající hodnotu o celém dokumentu, proto tímto celý postup nekončí. Všechny termy, které obsahuje věta s nejvyšším významem, jsou z dokumentu odstraněny.
= = (= − k )
Kde Vi je množina termů (slov), které obsahuje již vybraná věta začleněná do shrnutí dokumentu D. Opět se vytvoří vektory tf a idf, kde jejich skalární součin identifikuje další větu. Tímto způsobem se pokračuje tak dlouho, dokud nemá sumarizace potřebnou délku. Příklad: Pro názornost byl vybrán výňatek z článku přílohy č. 2 - „Nový systém odhalí plagiátorství mezi vědci“. Červeně jsou zvýrazněna stop-slova, která nejsou nositelem informací a nejsou tedy zahrnuta do společného vektoru. Dimenze vektorového souboru tak klesne ze 43 na 34. V1: „Repozitar.cz umožní také zpřístupnit výsledky vědy širší veřejnosti při zachování vůle autorů.“ V2: „K tzv. otevřenému přístupu k vědeckým informacím, který prosazuje hnutí Open Access, se MU přihlásila loni v říjnu podpisem Berlínské deklarace.“ V3: „Informatici MU již proto také vytvořili vlastní univerzitní repozitář, který rozšiřuje stávající systém evidence publikací.“ Sestavení společného vektoru vk (abecedně seřazený): vk = (autorů, Berlínské, deklarace, evidence, hnutí, informacím, Informatici, loni, MU ,Open Access, otevřenému, podpisem, prosazuje, přihlásila, přístupu, publikací, repozitář, rozšiřuje, Repozitar.cz, říjnu, stávající, systém, širší, univerzitní, veřejnosti, vědeckým, vědy, vlastní, vůle, vytvořili, výsledky, umožní, zachování, zpřístupnit) v1 = (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1) v2 = (0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0) v3 = (0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0) Idf = (0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.18, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, - 32 -
0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48) Následuje vypočet skalárního součinu vektorů tfi a idf a vyčíslení významu věty, ten je vyjádřen jako součet všech parametrů vektoru získaného skalárním součinem (hodnoty při skutečných výpočtech budou v závislosti na délce dokumentu mnohem nižší). tfv1*idf = (0.48, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.48, 0, 0, 0, 0.48, 0, 0.48, 0, 0.48, 0, 0.48, 0, 0.48, 0.48, 0.48, 0.48) významnost věty = 4,8 tfv2*idf = (0, 0.48, 0.48, 0, 0.48, 0.48, 0, 0.48, 0.18, 0.48, 0.48, 0.48, 0.48, 0.48, 0.48, 0, 0, 0, 0, 0.48, 0, 0, 0, 0, 0, 0.48, 0, 0, 0, 0, 0, 0, 0, 0) významnost věty = 6,42 tfv3*idf = (0, 0, 0, 0.48, 0, 0, 0.48, 0, 0.18, 0, 0, 0, 0, 0, 0, 0.48, 0.48, 0.48, 0, 0, 0.48, 0.48, 0, 0.48, 0, 0, 0, 0.48, 0, 0.48, 0, 0, 0, 0) významnost věty = 4,98
Nejvýznamnější větou ze tří posuzovaných je tedy: „K tzv. otevřenému přístupu k vědeckým informacím, který prosazuje hnutí Open Access, se MU přihlásila loni v říjnu podpisem Berlínské deklarace.“ V dalším kroku by následovalo vyřazení všech termů, které obsahuje tato věta z dokumentu a proces by se opakoval až do požadovaného rozsahu sumarizace.
4.2.2 Grafová analýza hyperstuktur Grafové metody byly původně navrženy pro hodnocení a následné řazení webových stránek. Jsou postaveny na teorii grafu, kde G je graf s množinou vrcholů V a množinou hran E, kde E je podmnožinou VxV. Pro každý vrchol Vi existuje množina vrcholů In(Vi), ze kterých vede větev do Vi a množina vrcholů Out(Vi), do kterých vede větev z Vi. Vrcholy reprezentují jednotlivé věty a větve reprezentují vazby mezi větami. Příkladem takového algoritmu může být PageRank. Ten využívá pro ohodnocení výsledků řada internetových
- 33 -
vyhledávačů (například Google) [31, 24]. Tw(k ) =
1−8 ∗ U+8
&
oz ∈{ (op )
Tw(k# )
xyc (k# )x
Kde N je počet vrcholů a d je parametr (faktor tlumení) s hodnotou intervalu 0 až 1. Parametr (1-d) vyjadřuje pravděpodobnost provedení přechodu z jednoho vrcholu na libovolný další vrchol a parametr d vyjadřuje pravděpodobnost přechodu podle větve vedoucí z aktuálního vrcholu. Hodnota d je doporučena ve výši 0,8. Počáteční hodnoty vrcholů nejsou podstatné, proto se volí pro všechny stejné se součtem 1 [31]. Z hlediska použití při analýze textových dokumentů, je však vhodnější použít algoritmus, který umožňuje určit nejen důležitost jednotlivých vrcholů (vět), ale také váhu větví (podobnost vět), které je spojují. Takovým algoritmem je například LexRank.
4.2.2.1 LexRank Jedná se o pokročilý grafový algoritmus, který podobnost vět zachycuje do matice. Ta je velikosti nxn, kde n vyjadřuje počet vět dokumentu. Každá hodnota se počítá pomocí kosinové podobnosti [31]. H 8 IJ
= cos( ) =
∗N = ǁAǁ ǁBǁ )∑
∑
P ∗ I
(P ) ∗ )∑
(I )
Podle metod uvedených v předchozích kapitolách, jsou postupně sestrojeny pro dokument D vektory vk a idf. Pro každou větu i pak normovaný tfi, a tfi*idf. Výsledná matice podobnosti je složena z výpočtů dle uvedeného vzorce pro jednotlivé páry vět. K výpočtu se používá parametru t, což je práh podobnosti. Ten určuje minimální hranici stupně vrcholu, který bude zařazen do výsledného souhrnu. Větve (hodnoty míry podobnosti), které nesplňují kritérium parametru t, jsou z grafu vymazány a tím je snížen také stupeň vrcholu (věty). Práh podobnosti se volí na základě požadovaného rozsahu sumarizace. Čím je nastavena větší hodnota t, tím méně vazeb ve výsledném souhrnu [24]. Algoritmus využívá také hodnot významnosti vět wi. Pakliže vrchol dosáhne potřebného stupně dle t, nemusí být přesto zařazen z důvodu nízkého významu.
- 34 -
Příklad: Považujme, pro zjednodušení, za dokument první tři věty článku z přílohy č. 2 – „Nový systém odhalí plagiátorství mezi vědci“. Práh podobnosti t = 0,03. Dle předchozích kapitol jsou vypočítány následující hodnoty: idf = (0.48, 0.48, 0.18 ....... 0.48) tf1.věty * idf =
(
0.48
0.48
0.18
...
0
)
tf2.věty * idf =
(
0
0
0.18
...
0
)
tf3.věty * idf =
(
0
0
0
...
0.48
)
Dosazením do vzorce podobnosti jsou získány hodnoty pro výslednou matici vrcholů (vět), které vyjadřují podobnost jednotlivých vět. H 8 IJ
(1. P 2. ě S) =
H 8 IJ
(2. P 3. ě S) =
H 8 IJ
)∑
(1. P 3. ě S) =
∑
P ∗ I
(P ) ∗ )∑
0,062 = 0,039 4,011
(I )
=
0,062 = 0,017 3,642
0 =0 4,331
Váhy jednotlivých vět jsou stanoveny Luhnovou metodou: w1.věty = 7,736, w2.věty = 8,463 a w3.věty = 10,423 Tabulka 6 – Matice podobnosti 3 vět článku přílohy č.2
1.věta
2.věta
3.věta 3
1.věta
1
0,017
0,039
2.věta
0,017
1
0
3.věta
0,039
0
1
Věty, které jsou identické, mají podobnost rovnu 1 a věty, které se dle míry podobnosti nijak nepřekrývají (nemají žádná společná slova), mají podobnost 0. Z uvažovaného dokumentu,
- 35 -
respektive jeho prvních tří vět, by byla nejprve vybrána do sumarizace 3. věta, protože má nejvyšší stupeň vrcholu, který splňuje prahovou hodnotu t a zároveň nejvyšší váhu w. Následující obrázek reprezentuje již grafické zobrazení celého článku, při nastavení hodnot prahu podobnosti na 0,25. Červeně obarvené vrcholy nevyhovují zadané hodnotě významnosti w a vrcholy, které nemají žádnou společnou vazbu, nesplnily kriterium prahu podobnosti t. Obrázek 10 – Grafová analýza LexRank článku přílohy č.2 [32]
Výsledná sumarizace celého článku metodou LexRank zahrnuje následujících 5 vět: „Nový systém odhalí plagiátorství mezi vědci. Spolu se studentskými pracemi se stanou v elektronické podobě součástí takzvaného Repozitáře, který do budoucna umožní také jejich zpřístupnění širší veřejnosti při dodržení autorských práv. „Projekt, na jehož realizaci získaly vysoké školy přes třináct miliónů korun, řeší široké spektrum problémů spojených s plagiátorstvím v terciárním vzdělávání,“ říká mluvčí Masarykovy univerzity Tereza Fojtová. Deset z patnácti vysokých škol, které se do projektu řízeného MU zapojily, se chystá také pořizovat, upravovat a následně napojit své lokální systémy pro sběr zaměstnaneckých děl na systém Repozitar.cz. Aby vyhledávání podobných souborů (možných plagiátů) bylo co nejúčinnější, bude databáze propojena s dalšími již existujícími systémy pro vyhledávání plagiátů – například Theses.cz (vysokoškolskými kvalifikačními pracemi) a Odevzdej.cz (studentskými pracemi) aj.“
- 36 -
4.3
Klasifikace textových dokumentů (klastrování) Klasifikace textových dokumentů je souhrn metod, které mají za úkol stanovit téma
neboli doménu, na kterou je posuzovaný dokument zaměřen. Základním kamenem je předpoklad, že tematicky podobné dokumenty mají také podobnou strukturu a složení termů. Cílem klasifikace může být také zařazení dokumentů podle předem zvoleného atributu – autora, domény, jazyka či žánru. Metody
pro
klasifikaci
dokumentů,
stejně
jako
předchozí,
nepracují
přímo
s nestrukturovaným dokumentem. Pro analýzu používají buď výstupní data z indexace, nebo selekce či extrakce příznaků. Mezi nejznámější metody klasifikace dokumentů patří lexikální frekvenční analýza, shluková analýza, naivní bayesovská klasifikace a další [16, 7].
4.3.1 Lexikální frekvenční analýza Jedná se o metodu, která posuzuje téma (doménu) dokumentu na základě počtu výskytů důležitých (reprezentativních) slov. Před samotnou kategorizací je nutné textové dokumenty předzpracovat pomocí výše uvedených metod ke snížení dimenze vektorového souboru. Metody pro kategorizaci potom pracují již se souhrnem termů, které vhodným způsobem reprezentují posuzovaný dokument. Dokument je redukován pomocí výše popsaných metod a jednotlivé termy jsou zaznamenány do přehledné tabulky frekvenční analýzy. Pro názornost byla zpracována tabulka frekvenčních výskytu termů článku z přílohy č. 2 – „Nový systém odhalí plagiátorství mezi vědci“, respektive jeho 3 vět. Největší roli pro klasifikaci podle tématu hrají podstatná jména. V následující tabulce jsou již v upraveném tvaru po lemmatizaci. Ve dvou případech bylo zachováno důležité sousloví. Jedná se o spojení tvořící důležité názvy, proto je vhodné je zachovat. Příklad: „Repozitar.cz umožní také zpřístupnit výsledky vědy širší veřejnosti při zachování vůle autorů. K tzv. otevřenému přístupu k vědeckým informacím, který prosazuje hnutí Open Access, se MU přihlásila loni v říjnu podpisem Berlínské deklarace. Informatici MU již proto také vytvořili vlastní univerzitní repozitář, který rozšiřuje stávající systém evidence publikací.“
- 37 -
Tabulka 7 – Frekvenční výskyt slov v dokumentu a napříč korpusem
Celkový součet Term počet výskytů
počet dokumentů
Repozitář
2
1
Možnost
1
1
Přístup
2
1
Výsledek
1
1
Věda
2
1
Veřejnost
1
1
Vůle
1
1
Autor
1
1
Informace
2
1
Hnutí
1
1
Open Access
1
1
Loni
1
1
Berlínská deklarace
1
1
Univerzita
1
1
Systém
1
1
Evidence
1
1
Publikace
1
1
Nejčetnější termy jsou tedy: informace, věda, přístup a repozitář. Z takto definovaných klíčových slov je sestaven vektor. Ten je porovnán s již existujícími vektory různých domén. Dokument je zařazen do domény s největší podobností vektorů klíčových slov [7]. Velkou nevýhodou této metody je absence porovnání důležitosti termů, závislost na velikosti dokumentu a podobně.
- 38 -
4.3.2 Shluková analýza Shluková (clusterová) analýza je vícerozměrná statistická metoda vycházející ze seskupování objektů (termů nebo dokumentů) do shluků na základě jejich podobnosti. Jednotlivé termy jsou přidávány do shluků tak, aby rozptyl shluku by minimální a vzdálenosti mezi jednotlivými shluky byly maximální. Jinými slovy řečeno, shluková analýza má za úkol rozdělit soubor dat na několik shluků tak, aby si objekty uvnitř shluku byly co nejvíce podobné. V úloze data-miningu, která se zabývá stanovením tématu, je za objekt považován jeden textový dokument. Pomocí metod shlukové analýzy lze roztřídit velké množství dokumentů do tematicky podobných skupin (shluků). Další možností využití je roztřídění dokumentů do již známých domén (kategorií). V takovém případě je nutné již mít předem vytvořené domény obsahující výčet klíčových termů. Shluková analýza funguje na principu vnitřní podobnosti dokumentů (objektů). Výsledkem analýzy může být diagram zobrazující nalezené množiny podobných dokumentů, kde jednotlivé množiny reprezentují různé domény. Výsledky shlukové analýzy mohou být reprezentovány pomocí různých typů grafů jako je 2D cluster map či dendrogram. Obrázek 11 – Příklad 2D cluster mapy a dendrogramu [41]
Obrázek č.11 (vlevo) zobrazuje 2D mapu, na které jsou zobrazeny 2-dimenzionální objekty. Jak je z grafu vidět, objekty tvoří 4 shluky. Na obrázku č.11 (vpravo), jsou na dendrogramu shluky reprezentovány uzly jednotlivých větví grafu. Na vertikální ose jsou zachyceny jednotlivé objekty (jejich číselné označení). V prvním kroku obsahující pouze jeden objekt. Horizontální osa vyjadřuje vzdálenost, na níž došlo ke spojení shluku. Zároveň zachycuje - 39 -
podobnost jednotlivých shluků. Porovnávané objekty lze zapsat do matice X typu m*n, kde X reprezentuje dokumentový korpus, m je počet objektů a n vyjadřuje počet proměnných. Cílem shlukové analýzy je rozklad matice X do k skupin (domén) [13]. Cílem rozkladu je nalezení takového počtu shluků S, aby objekty uvnitř shluku vykazovaly co největší míru podobnosti. S(k) = {C1, C2, C3, …, Ck} Míra podobnosti je měřena pomocí metrik k určení vzdálenosti mezi objekty. Příkladem metrik mohou být euklidovská vzdálenost či Canberra a další.
ρZ uR , R# v = }&(R ~ − R#~ ) ~
ρ1 uR , R# v = & ~
xR ~ − R#~ x
|R ~ | + xR#~ x
Uvedené metriky však nedokážou reagovat na silně korelované proměnné, či na hodnoty použitých různých jednotek (hmotnost, váha, vzdálenost apod.). Jednou z metrik, která řeší vzájemnou korelaci parametrů je tzv. Mahalanobisova metrika k určení vzdálenosti objektů.
ρ€ uR , R# v = (R − R# )l ∗ k • ∗ (R − R# ) Kde V-1 je inverzní kovarianční matice. Shluková analýza má několik možností přístupů dělení matice vzdáleností objektů do jednotlivých shluků. Ty lze rozdělit na hierarchické a nehierarchické. Mezi hierarchické metody patří například strategie nalezení nejbližšího či nejvzdálenějšího souseda, zatímco pro nehierarchické metody jsou využívány například metody k-means, fuzzy C-means, RELOC a podobně.
- 40 -
4.3.2.1 Hierarchické shlukování Základem metod pro hierarchické shlukování je matice vzdáleností D, kterou je nutné rozložit do k shluků. Na začátku rozkladu je předpoklad, že existuje pouze jeden shluk, do kterého patří všechny objekty. V každém i-tém kroku je shluk rozdělen na další dva shluky. Grafickou
reprezentací
hierarchického shlukování je stromový diagram nazývaný
dendrogram. Podle výše uvedených metrik posuzování vzdálenosti mezi objekty se budou lišit také jejich grafy. Obrázek 12 – Příklad řádkového a sloupcového dendrogramu [41]
Jednotlivé řádky reprezentující všechny objekty jsou zobrazeny nejvíce vpravo (viz. Obrázek č. 12 – řádkový dendrogram). Každý uzel znázorňuje shluk všech objektů, které leží napravo od uzlu. Vertikální čára znázorňuje řez grafem s uvedenými hodnotami počtu aktuálních shluků a vzdáleností mezi nimi.
4.3.2.1.1 Metoda nejbližšího souseda Metoda nejbližšího souseda prohledává matici vzdáleností D k nalezení nejmenší hodnoty min(ρ), respektive shluků h a h´, které jsou si nejblíže. Tyto dva shluky jsou spojeny do nového společného shluku g. Matici vzdáleností D je nyní potřeba upravit nahrazením h-tého a h´-tého řádku a sloupce nově spočítanou vzdáleností g-tého shluku od ostatních shluků. Matice vzdáleností je konstruována z jednotlivých vzdáleností vyjádřených například pomocí euklidovského vztahu. Kde se na hlavní diagonále vyskytují 0 (vzdálenost vx od vx). Pro lepší názornost uvedeného postupu je uveden následující příklad. K reprezentaci - 41 -
dokumentů byly zvoleny dvousložkové vektory. Ve skutečnosti by objekty byly vyjádřeny například vektorovým zápisem pomocí tf * idf. V demonstračním příkladě by však víceparametrické vektory neměly vypovídající informační hodnotu, proto byly nahrazeny níže popsanými objekty. Příklad: Pro jednoduchost je dáno několik objektů A1, A2, A3, A4 a A5, které jsou reprezentovanými vektory va1=[2,2], va2=[3,3], va3=[4,6], va4=[6,3] a va5=[8,4]. Na následujícím obrázku jsou zobrazeny ve 2-rozměrném prostoru (viz. obrázek č. 13) [13]. Obrázek 13 – Zobrazení objektů v rovině [13]
Jak bylo výše zmíněno, v prvním kroku je nutné spočítat matici vzdáleností D všech objektů A. Matice D se bude lišit v závislosti na použité metrice výpočtu vzdáleností. Za použití euklidovského vyjádření vzdáleností mezi objekty získáme matici v následujícím tvaru. Vzhledem ke skutečnosti, že jsou posuzovány vzdálenosti mezi všemi body, jde o symetrickou matici. Hlavní diagonála je nulová jelikož vzdálenost mezi objekty A1 a A1 je rovna 0.
ρZ uP , P# v = }&(P ~ − P#~ ) ~
ρZ (P , P ) = )(2 − 3) + (2 − 3) = √2 ρZ (P , P\ ) = )(2 − 4) + (2 − 6) = √20
ρZ (P , P] ) = )(2 − 6) + (2 − 3) = √17 ρZ (P , P‚ ) = )(2 − 8) + (2 − 4) = √40 - 42 -
…. Výsledky euklidovských vzdáleností jednotlivých objektů jsou reprezentovány v následující matici: A1 A1 A2 A3 A4 A5
A2
A3
A4
A5
√2
√20
√17
√40
√20
√10
0
√13
√20
√40
√26
0
√2
√17
0
√9
√10 √13 √20
√9 0
√5
0 ƒ = = 20 17 40
√26 √5
ƒ 0 10 9 26
20 10 0 13 20
17 9 13 0 5
40 26 20 5 0
0
Dalším krokem je nalezení prvních dvou nejbližších objektů, které jsou reprezentovány prvkem matice d12 s hodnotou 2. Jde o vzdálenost mezi objekty A1 a A2, které budou v tomto kroku nahrazeny novým společným shlukem. 1. a 2. řádek a stejně tak 1. a 2. sloupec, které reprezentovaly vzdálenosti objektů A1 a A2 jsou nahrazeny jedním společným řádkem a sloupcem nového shluku [13]. Obrázek 14 – Dendrogram po prvním kroku rozkladu matice D
- 43 -
Nové hodnoty jsou stanoveny z minimálních hodnot následujícím způsobem: 8(
)\
= min(8 \ ; 8 \ ) = 10
8(
)‚
= min(8 ‚ ; 8 ‚ ) = 26
8(
)]
0 10 = = † 9 26
= min(8 ] ; 8 ] ) = 9
10 0 13 20
9 13 0 ‡
26 20 ˆ ‡ 0
Další krok je analogický, opět je vyhledán první nejmenší prvek - d34 s hodnotou 5. Jde o vzdálenost mezi původními objekty A4 a A5. Tyto objekty opět vytvoří společný shluk a stejně jako v předchozím bodě jsou nahrazeny novým shlukem. 8(
8(
)\
= min(8 \ ; 8 \ ) = 10
)(]‚)
= minu8(
)] ; 8(
)‚ v
8\(]‚) = min(8\] ; 8\‚ ) = 13
=9
0 10 =\ = ‰10 0 9 13
9 13Š 0
Obrázek 15 – Dendrogram po druhém kroku rozkladu matice D
Dalším nejmenším prvkem rozložené matice je 9, pomocí kterého je matice rozložena do konečné podoby. 8((
)(]‚))\
= minu8(
=] = ‹
)\ ; 8(]‚)\ v = 10
0 10
10 Π0
Konečný dendrogram rozkladu matice D do jednotlivých shluků je znázorněn na následujícím obrázku.
- 44 -
Obrázek 16 – Dendrogram rozkladu na shluky
Alternativou pro metodu nejbližšího souseda je metoda nejvzdálenějšího souseda, která se liší pouze ve výběru maximálního prvku na rozdíl od znázorněného postupu. Efektivnější a častěji používanější metodou rozkladu matice je počítání nových středů posuzovaných objektů (shluků), dochází tak k menším chybám v kategorizaci, vzhledem ke skutečnosti malého posunu „težiště“ shluku, oproti krajním hodnotám vzdáleností stanovených u nových shluků. Jedním z takových postupů je nehierarchická metoda K-means.
4.3.2.2 Nehierarchické shlukování Na rozdíl od hierarchického shlukování rozkládají matici do předem daných podmnožin (shluků). Tyto shluky jsou dány vzorovými hodnotami (tématy). Na počátku metody je nutné všechny hodnoty přiřadit do některého vzorového tématu (shluku). Postupně je každý objekt přiřazen do všech předem definovaných témat, kde je spočítána hodnota podobnosti (vzdálenosti) s tímto shlukem. Kde je hodnota vzdálenosti nejlepší, tam bude objekt přiřazen. Nehierarchické metody jsou někdy též nazývány optimalizačními metodami, které hledají nejlepší kategorizaci objektů postupným přeřazováním mezi vzorovými tématy. Jednou z optimalizačních metod je metoda K-means.
4.3.2.2.1 Metoda k-means Metoda k-means se vyznačuje předem definovaným počtem hledaných shluků k. Přičemž - 45 -
k je zpravidla menší než počet původních objektů. Nejprve je nutné vybrat k počátečních vzorových objektů (bodů), které jsou buď prvky původní množiny objektů, nebo hledané tematicky zaměřené objekty (domény). Všechny objekty jsou náhodně přiděleny do vybraných k shluků. Stanoví se těžiště shluků zvětšené/zmenšené o jeden právě přidaný/odebraný objekt. Postupně jsou porovnány všechny objekty, respektive jejich polohy vzhledem k těžišti shluku. Pokud má právě přidaný objekt polohu nejblíže k těžišti shluku, zůstane v tomto shluku, v opačném případě je odebrán a přiřazen do jiného. Algoritmus končí ve chvíli, kdy nejde k žádnému přesunu objektu mezi shluky. Pro názornost budeme uvažovat opět případ z předchozí kapitoly a objekty A1 … A5. Nehierarchické metody vyžadují předem stanovený počet hledaných shluků. Pro jednoduchost zvolíme k=2 [13]. Náhodně jsou přiřazeny objekty do jednotlivých shluků. Shluk S1 obsahuje objekty A1, A3 a A5 a shluk S2 obsahuje objekty A2 a A4. Po přiřazení je nutné přepočítat těžiště shluků dle následujícího vzorce: h~ = (
•
+
• +. . . +
J
•
;
Ž
+
Těžiště vybraných dvou shluků budou mít tedy polohu: h =3
2+4+8 2+6+4 ; 4 = (4,7; 4) 3 3
Ž +. . . +
J
Ž
)
3+6 3+3 h =3 ; 4 = (4,5; 3) 2 2
Po výpočtu těžišť jednotlivých shluků následuje výpočet vzdáleností všech bodů A1..A5 vzhledem k vypočítaným těžištím (euklidovská metrika).
ρ(h ,
) = (4,7 − 2) + (4 − 2) = 11,29
ρ(h ,
) = (4,5 − 2) + (3 − 2) = 7,25
A1 je blíže těžišti T2 … změna shluku
) = (4,7 − 3) + (4 − 3) = 3,89
) = (4,5 − 3) + (3 − 3) = 2,25
A2 je blíže těžišti T2 shluku S2, ve
ρ(h ,
ρ(h ,
…
na S2
kterém se nachází …
- 46 -
ρ(h ,
ρ(h ,
‚)
‚)
= (4,7 − 8) + (4 − 4) = 10,89
= (4,5 − 8) + (3 − 4) = 13,25
A5 je blíže těžišti T1 shluku S1, ve kterém se nachází
Vzhledem ke skutečnosti, že shluky změnily svou velikost, je nutné přepočítat jejich těžiště T1 a T2. Přepočty vzdáleností objektů od těžišť se opakují tak dlouho, dokud nejsou všechny vzdálenosti objektů od těžišť shluku, do kterých jsou právě přiřazeny, menší než vzdálenosti od jiných těžišť shluků.
4.4
Fraud management Další úlohou data-miningu je Fraud management. Ten se též někdy nazývá detekcí
podvodů. Jak již název napovídá, jedná se o metodu k odhalení „podvodného“ jednání či jeho náznaků. Je postaven na expertních znalostech, které jsou formulovány do pravidel, která slouží pro klasifikaci zkoumaných dat. Pravidla jsou následně implementována do různých skryptů, expertních systémů a podobně. Významným úkolem Fraud managementu je posuzování internetových objednávek, odhalování nevyžádané pošty, různých žádostí, formulářů, pojistných událostí a podobně. Pro tyto účely je možné využít některou z analýz z předchozích kapitol, jako je například shluková analýza, frekvenční analýza, indexace dokumentů a podobně. Shlukovou analýzu je možno s úspěchem využít při odhalování podvodných objednávek, které demonstruje obrázek č.17. Vlevo je graf objednávek v závislosti na čase, vpravo pak ilustrace shlukové analýzy sestavená z dvousložkových vektorů vi=(množství, cena), které reprezentují jednotlivé objednávky. Obrázek 17 – Příklad detekce podvodných objednávek pomocí shlukové analýzy
- 47 -
Obrázek zachycuje dva případy podezřelého jednání. Červenou barvou je znázorněn prvek, který se významným způsobem odlišuje od ostatních a je detekován jako podezřelý. Oranžovou barvou je zvýrazněn prvek, který může být způsoben chybou systému (duplicitní objednávka), ale tímto způsobem by nebyl označen. Z tohoto důvodu je vhodné metody kombinovat s dalšími pravidly. Fraud managementu lze využít také k detekci podvodných emailů. Zde je možné využít frekvenční analýzu výskytu podezřelých termů a při překročení prahové hodnoty takový dokument označit. V sofistikovanějších metodách lze využít porovnání podobnosti vektorů. V takovém případě je nutné mít sestavený vektor klíčových slov pro nežádoucí dokumenty. Zredukovat dimenzi porovnávaného dokumentu na hodnotu dimenze filtru a provést porovnání. Fraud managementu je možné dále využít při analýze strukturovaných dokumentů – formulářů, databází a podobně. Klíčovou informací pro identifikaci můžou být krátká doba od uzavření pojistné smlouvy, dvě navzájem si odporující položky formuláře (nezaměstnaný x výše platu) a další. Pro názornost lze uvést běžný způsob pojišťoven při likvidaci pojistných událostí, kdy využívají formulářů k ohodnocení míry rizik při jejich vyhodnocení – „Expertní bodový systém“ [25]. Obrázek 18 – Příklad pravidel ohodnocení sledovaných příznaků [25]
U všech výše zmíněných případů se nemusí vždy jednat o podvod, ale určitě je vhodné je označit a následně ověřit s ohledem na možné dopady (například finanční náklady). Tato úloha má za úkol pouze identifikovat možná rizika
- 48 -
4.5
Hledání plagiátů Za jednu z nejdůležitějších úloh pro analýzu nestrukturovaných dat považuji hledání
plagiátů. Jedná se o velice závažný problém v oblasti lidské tvůrčí práce, především v oblasti vědy a školství. Cílem této metod pro hledání plagiátů je vyhledat dokumenty s takovou mírou vzájemné podobnosti, u kterých je možné porušení zákona o autorském právu. Z důvodu rozsáhlosti této problematiky se tato práce bude zabývat metodou využívající výše popsanou Latentní sémantickou analýzu (LSA) pouze v oblasti textových dokumentů. Metody pro hledání plagiátů lze dle T. Lancastera [11] dělit dle několika kritérií. Dle složitosti: povrchní - metody se nezabývají znalostí jazyka a jeho struktury; strukturní - jsou zde použity znalosti o struktuře jazyka, ohebnosti a podobně. Dle počtu zpracovávaných dokumentů: jednotlivé - zpracováván pouze jeden dokument, kde výsledky mohou být použity v následném párovém porovnání; párové - současné zpracování dvou dokumentů; multidimenzionální - současné zpracování m dokumentů; korpální - současné zpracování celého korpusu.
4.5.1 Hledání plagiátu pomocí LSA Dle výše zmíněného rozdělení se tato metoda vyznačuje strukturním přístupem k textovým dokumentům. Podle druhého rozdělení dle tabulky č. 9, závisí jen na počtu porovnávaných dokumentů. Jako u každé metody analýzy nestrukturovaných dat je i zde nutné, z důvodu snížení výpočetní náročnosti, ale také přesnosti, provést předzpracování dat. Z porovnávaných dokumentů je nejprve nutné vytvořit vektory, kde jsou termy reprezentovány n-gramy. N-gramy mohou být tvořeny i celými větami. Ty, které se vyskytují v obou porovnávaných dokumentech, signalizují známky plagiátorství. Naopak ty které se vyskytují pouze v jednom dokumentu, nejsou pro tuto úlohu důležité, neboť je zřejmé, že nejsou plagiovány [39]. - 49 -
Metodou SVD je dále provedena redukce dimenze na základě konceptů korpusu. Podobnost dokumentů se stanovuje pomocí matice VT, kterou je nutné z důvodu získání správného rozměru matice reprezentující porovnávané dokumenty, vynásobit maticí singulárních hodnot Σ dle následujícího vztahu:
N = kl ∗ Σ
Zda se jedná o dokumenty, které jsou plagiovány, vyjadřuje opět matice podobností. Jedná se o symetrickou matici, která udává procentuální podobnost pro všechny porovnávané dokumenty. Matice podobností se vypočítá dle následujícího vztahu: H 8 IJ
•o•
= (‖N‖l ∗ ‖N‖)
Původní vektory dokumentů byly však redukovány na základě významnosti n-gramů, které znázorňuje obrázek č. 19. Tato redukce negativním způsobem ovlivňuje míru podobnosti dokumentů. Obrázek 19 – Podobnost dokumentů [23]
Ačkoli jde pouze o podobnost nevýznamných termů, je vhodné minimalizovat chybu výpočtu podobnosti s ohledem na rozdíl mezi počtem původních termů před redukcí a počtem termů po redukci. Následující vztah tuto chybu odstraňuje: xphš›œ• (A)x xphš›œ• (B)x podobnost (“,”) = podobnost •–— (A, N) ∗ ˜ ∗ |ph›žŸ ( )| |ph›žŸ (B)| Kde phorig je počet původních n-gramů před redukcí dimenze vektoru a phred reprezentuje počet termů po redukci dimenze vektorů.
- 50 -
5 Systémy pro ukládání nestrukturovaných dat Vzhledem k obrovskému množství dat je nutné zavést do ukládaných dat předem definovaný systém. Pro lepší a jednodušší správu dat existují sofistikované systémy, které jsou určeny k ukládání, začleňování, třídění a následně k vyhledávání v datech. Právě vyhledávání a následné zpracování dříve uložených dat je zejména v podnikové struktuře stěžejní problém. Podnik má obrovské množství dat, které je potřeba zpracovat k získání například důležitých strategických či marketingových údajů. Systémy pro zpracování nestrukturovaných dat se na základní úrovni dělí na: systémy pro správu dokumentů (Document Management System) systémy pro správu obsahu (Content Management System)
5.1
Document Management Systém Základním úkolem document management systému (dále jen DMS) je řízení životního
cyklu dokumentu po jeho vytvoření. Principem DMS je umožnit efektivně spravovat a sdílet firemní know-how ve formě strukturovaných i nestrukturovaných dokumentů. DMS systémy využívají centralizovaného uložiště, které zabezpečuje dostupnost informací na základě principu autorizace a poskytuje uživatelské rozhraní, které nabízí velké množství operací s takto uloženými daty. Primární fuknce: přehledná organizace dat; automatická tvorba, řízení verzí a revizí dokumentů; multi-uživatelský přístup; vyhledávací procedury; řízení životního cyklu dokumentu a podobně. Na trhu je mnoho systémů typu DMS, které poskytují výše uvedené funkcionality. Příkladem může být například Bussiness objects od společnosti SAP.
- 51 -
5.2
Content Management System Základním úkolem content management systému (dále jen CMS) je řízení tvorby
dokumentů neboli zajištění správné struktury dokumentu. CMS systémy se používají především ke tvorbě a správě webových aplikací. Jedná se o takzvaný redakční či publikační software. Primární funkce: vytvoření dokumentu dle stanovené struktury; administrace přístupu dle autentizace a autorizace; modifikace; správa dokumentů; statistické funkce. V závislosti na hloubce propracování systému mohou být implementovány funkce workflow a groupware. Workflow má za úkol řídit jednotlivé fáze tvorby dokumentu a předávat jejich řízení jednotlivým skupinám. Příkladem systému CMS může být produkt WordExpress, Drupal či Joomla!. Tyto jmenované redakční systémy jsou navíc šířeny zcela zdarma.
6 Sofwarové nástroje Data-miningu Softwarové nástroje tvoří velice důležitou část správy dat zejména v podnikových strukturách. Jak již bylo výše popsáno, je velice důležité mít množství dat, ale mnohem důležitější je skutečnost efektivně s těmi daty nakládat. Softwarové nástroje umožňují integraci výše popsaných metod a postupů a omezit vliv lidského faktoru. Automatizují celý proces a uživateli poskytují relevantní vizualizované informace. Existuje celá řada produktů zabývajících se data-miningem, které jsou více či méně propracované. V této kapitole budou reprezentovány zejména aplikace, které jsou volně dostupné pro jednotlivé úlohy data-miningu. Příkladem volně šiřitelných aplikací jsou KWords, Online summarize tool, Open NLP, ElasticSearch či Weka. Z portfolia komerčních - 52 -
systémů je možné jmenovat například aplikace Oracle Data Minig, Statsoft Statistica či IBM SPSS Data Modeler. Většina open-source aplikací pro data-mining pracuje se strukturovanými daty (Weka – formát ARFF) nebo vyžadují znalosti ve zpracování a využití Java skriptu (ElasticSearch). V případě jmenované Weky je navíc práce ztížena ne příliš přehledným prostředím. Pro účely této práce byly proto vybrány aplikace, které tyto požadavky nemají.
6.1
KWords Online aplikace KWords je zaměřená na indexaci textových dokumentů. Pro svou práci
využívá referenčního korpusu SYN2010 na jehož základě vybírá klíčová slova dokumentu. „Výstupem KWords je
seznam
slov,
jejichž
frekvence
je
signifikantně
vyšší
v analyzovaném textu než v referenčním korpusu (např. v SYN2010, což je vyvážený referenční korpus současné psané češtiny. Pokud je rozdíl ve frekvencích (po zohlednění odlišné velikosti textu a referenčního korpusu) statisticky významný (např. na základě testů chi2 nebo log-likelihood), je následně vypočtena relevance rozdílu (tzv. effect size).“ [20] Na následujícím obrázku jsou reprezentovány výsledky indexace článku z přílohy č. 2 „Nový systém odhalí plagiátorství mezi vědci“ pomocí aplikace KWords. Obrázek 20 – Reprezentace výsledků indexace [20]
Pro indexaci uvedeného článku byly identifikovány následující klíčové termy: „repozitář“, „sběr“, „pracemi“, „masarykovy“, „textů“, „univerzity“ a „sytém“. Tabulka zároveň zobrazuje jejich váhu či frekvenci. - 53 -
6.2
Online summarize tool Jedním z užitečných nástrojů pro automatickou sumarizaci textového dokumentů je
„Online summarize tool“ (http://www.tools4noobs.com/summarize/). Tento nástroj jsem vybral především pro jeho širší možnost nastavení nežli je tomu u jiných dostupných online nástrojů. Pro své výpočty využívá algebraických metod založených na frekvenčním výskytu a výpočtu vah jednotlivých vět [42]. Stejně jako u většiny dostupných nástrojů však chybí implementace odstranění stop-slov, která vnáší do výpočtu nepřesnosti. Pro praktickou ukázku jeho funkcí byl vybrán článek přílohy č. 2 - „Nový systém odhalí plagiátorství mezi vědci“. Obrázek 21 – Ukázka aplikace Online summarize tool [42]
Tento nástroj umožňuje redukci dokumentu na základě nastavené prahové hodnoty „Threshold“ nebo počtu požadovaných vět „Number of lines“. Čím vyšší je prahová hodnota nastavena, tím větší je redukce dokumentu. Při použití sumarizačního nástroje na zmíněný dokument, při na stavení „Threshold“ na hodnotu 70, byl výsledkem sumarizace tento výstup: „Deset z patnácti vysokých škol, které se do projektu řízeného MU zapojily, se chystá také pořizovat, upravovat a následně napojit své lokální systémy pro sběr zaměstnaneckých děl na systém Repozitar.cz. Aby vyhledávání podobných souborů (možných plagiátů) bylo co nejúčinnější, bude databáze propojena s dalšími již existujícími systémy pro vyhledávání plagiátů – například Theses.cz (vysokoškolskými kvalifikačními pracemi) a Odevzdej.cz (studentskými pracemi) aj. Hlavním úkolem odborníků z Fakulty informatiky Masarykovy univerzity bude vyvinout nový systém pro sběr, řízenou prezentaci a kontrolu odborných - 54 -
článků, publikací a jiných děl vytvořených zaměstnanci nebo doktorskými studenty – tzv. Repozitar.cz.“ Což je redukce dokumentu na přibližně 20% původní velikosti. Z původních 13 vět byly sumarizací vybrány 3 nejvýstižnější věty.
6.3
Statistica 12 Jedním z komplexnějších nástrojů je komerční produkt Statistica Data miner 12 CZ od
firmy StatSoft. V testovací verzi nabízí však uvedená společnost aplikaci bez modulu „Text Mining“, který je stěžejní pro zpracování nestrukturovaných dokumentů. Pro účely této práce se mi po konzultaci se zástupci uvedené společnosti podařilo získat tento modul v časově omezené zkušební verzi. Ačkoli se v názvu objevuje česká verze, jedná se pouze o částečnou lokalizaci aplikace. Velkou výhodou této aplikace je možnost načtení dokumentů z různých zdrojů (lokální složky, url, ...) a formátů (txt, doc, xls, ...). Obrázek 22 – Načtení textových dokumentů [Statistica CZ v.12]
Navzdory skutečnosti, že aplikace zatím nepodporuje český jazyk, umožňuje přidat znaky, seznam stop-slov a synsety jiného jazyka (viz. záložky „Words“ a „Filters“).
- 55 -
Obrázek 23 – Předzpracování dokumentů [Statistica CZ v.12]
Velkým problémem však zůstává redukce dimenzí dokumentů. Aplikace neobsahuje funkci lemmatizace pro český jazyk. Proto je nutné využít externího lemmatizátoru (např. LemmaGen). I po této úpravě je však nutné ručně upravit soubor termů funkcí „Combine Words“,. Obrázek 24 – Kombinace podobných slov [Statistica CZ v.12]
Především z tohoto důvodu zatím není tato aplikace příliš vhodná pro automatické zpracování českých textů. Vyžaduje velký a časově náročný zásah zpracovatele.
- 56 -
Obrázek 25 – Ukázka funkcí programu [Statistica CZ v.12]
Na obrázku č.25 (vlevo) je vidět reprezentace souborů vektory tf-idf a v pravé části pak identifikace konceptů, respektive singulárních hodnot. Jak bylo zmíněno v kapitole o SVD, díky nim je možné redukovat dimenzionální prostor na hodnotu počtu singulárních hodnot. V tomto případě byla dimenze vektorů souborů redukována pomocí LSA-SVD na 10-dimenzionální prostor, zatímco původní dimenze vektorů byla cca 1000.
6.4
Theses.cz Dalším projektem analýzy textových dokumentů, který již delší dobu funguje za účelem
registrování závěrečných prací a odhalování plagiátů. Theses.cz je financován Ministerstvem školství mládeže a tělovýchovy (dále jen MŠMT) a zpravuje ho Masarykova univerzita v Brně [29]. Projekt porovnává nové práce s ostatními, které jsou již v systému uloženy. Slabinou projektu je tzv. parafrázování, kdy autor vlastními slovy přepíše cizí myšlenky. Nicméně parafrázování je dle normy ČSN ISO 5127-2003, která definuje pojem plagiát, povolená forma využití cizích zdrojů. I v tomto případě však musí být řádně uveden zdroj informací, odkud autor práce čerpal [30]. Kontrola samotné závěrečné práce probíhá tak, že jsou pomocí funkce „Vejce vejci“ vyhledány podobné dokumenty s procentuální mírou jejich překrytí. Při následném použití funkce „Podobnosti“ jsou vypsány a zvýrazněny červenou barvou shodné pasáže. Samotné rozhodnutí, zda se jedná o plagiátorství, závisí již na posuzovateli.
- 57 -
Obrázek 26 – Ukázka funkce projektu Theses.cz [38]
Pomocí projektu Theses mohou práce kontrolovat pouze registrovaní uživatelé. Je to především z důvodu vytíženosti a oprávněnosti využití systému. Příkladem systému, kde registrace není nutná a je tedy využitelný pro širší veřejnost, je projekt „Odevzdej.cz“. Ten je propojen se systémy „Theses.cz“ a „Repozitar.cz“. Zásadní rozdíl je ve skutečnosti, že po načtení dokumentu do systému a jeho kontrole, je následně po 5 dnech ze systému opět vymazán. O výsledku je zadavatel informován prostřednictvím emailové zprávy s velice stručnými údaji o podobnosti s jinými dokumenty. Pomocí projektu „Odevzdej.cz“ byla prověřena také tato diplomová práce (viz. obrázek č.27). Obrázek 27 – Zpráva o podobnosti ze systému Odevzdej
- 58 -
7 Závěr Tato diplomová práce měla za úkol vysvětlit problematiku analýzy nestrukturovaných dat, zejména pak textových dokumentů. Analýza zahrnuje velké množství operací, které je možné nad dokumenty vykonávat od samotného převodu do elektronické podoby, přes jejich matematickou interpretaci, až po zisk požadovaných informací. Jednotlivé postupy zpracování textových dokumentů jsou v této práci vysvětleny od samotné digitalizace až po zisk výsledků. První část práce je věnována interpretaci dokumentů do podoby, která bude snadno počítačově zpracovatelná. V této fázi předzpracování dat byly uvedeny metody reprezentace textových souborů za pomocí vektorů. Nejčastěji využívanou formou pro reprezentaci dokumentů je vektorový zápis pomocí metody „tf-idf“ či normovaný frekvenční zápis [43]. Obě tyto metody zachycují důležitost jednotlivých slov a navíc zohledňují rozdílné délky posuzovaných dokumentů. Důležitým krokem analýzy, kterému se věnuje tato práce, je redukce dimenze vektorů. Ta je nutná především z důvodu výpočetní náročnosti dalšího postupu zpracování. Různé metody text-miningu upřednostňují rozdílné postupy či jejich kombinace. Pro většinu úloh však platí maximální možná redukce dimenze, která ještě bude reprezentovat obsah dokumentu. Odstranění stop-slov a normalizace termů (lemma/stem) je však společná pro většinu případů. Odstraněním stop-slov a normalizací termů se při testování aplikací redukce dimenze pohybovala okolo 40%. Část diplomové práce popisuje také využití aplikací pro jednotlivé kroky analýzy. Není příliš komplexních nástrojů, které by umožňovaly načíst české textové dokumenty různých formátů (doc, pdf, txt, apod...). Většina aplikací umožňuje provádět data-miningové úlohy z databázových zdrojů, nebo nejprve vyžaduje úpravu dat do pevně daných struktur (například ARFF pro aplikaci Weka). Jednou z testovaných aplikací, která umí pracovat s různými formáty je Statsoft Statistica. Pro úlohy data-miningu implementuje velké množství algoritmů a funkcí. Nevýhodou však zůstává nepřímá podpora českého jazyka, která se projevuje především ve fázi předzpracování – lemmatizace. V práci jsou demonstrovány také aplikace pro indexaci a sumarizaci textových dokumentů. Oba tyto nástroje lze využít k zestručnění obsahu. Indexace nachází velké uplatnění například ve vyhledávačích, kterým poskytuje klíčová slova dokumentů. Sumarizace vytváří abstrakty, které pak umožňují rozhodnutí, zda se jedná o požadovaný dokument. Většina vyhledávačů ji nabízí k relevantním odkazům - 59 -
v délce cca 10% originálu. Pro informativní abstrakty se používají délky cca 20-30%, ty mají za úkol zběžné seznámení s tématem [31]. Poslední úlohou text-miningu, která je v této práci zmíněna je detekce plagiátů. Tato problematika má velké opodstatnění především u vědeckých článků, závěrečných prací a podobně. Jak se poslední dobou ukazuje, opisování zmíněných prací je stále častějším jevem. Vzhledem k obrovskému množství dokumentů, které již byly sepsány, je nezbytně nutné využít k posouzení autorství (originality) některou z metod automatické detekce podobnosti dokumentů. Pokročilejší metody vyhledávání plagiátů se zaměřují také na parafrázované dokumenty, kde autor přebere cizí myšlenky a přepíše je, za použití synonym aniž by uvedl původní zdroj. V takových případech je využito metod extrakce příznaků (například pomocí LSA). Je nutné si uvědomit, že algoritmy pouze upozorňují na příznaky takového jednání. Závěr, zda se skutečně jedná o plagiát a tím i o porušení zákona, by měl být výsledkem lidského rozhodnutí.
- 60 -
8 Terminologický slovník Bigram – je posloupnost dvou sousedících prvků dokumentu, typicky e jedná o slova. Bigramy se používají pro jednoduché statistické metody v úlohách analýzy textových dokumentů. (obdobou bigramu je trigram) Business intelligence (BI) - k pochopení hlavního důvodu snahy analyzovat data je nutné pochopit pojem Business Intelligence. Jedná se o veškeré informace, znalosti, dovednosti, aplikace, technologie, politiky a postupy používané v podniku či v jiné organizační struktuře. Data - mají za úkol popisovat nějaký děj, skutečnost nebo objekt. Data se získávají pozorováním reality a následným ukládáním do různých struktur. Datový sklad (Data Warehouse) - je jednoduše řečeno místem pro uložení velkého objemu dat v definované struktuře, která umožňuje efektivní práci s těmito daty – analýzu, vyhledávání a podobně. Datový sklad uchovává data, která byla vytvořena pomocí různých informačních systémů, databází a podobně. Datový sklad obsahuje velkou část již výše popsané Business Intelligence. Z tohoto důvodu je nutné zajistit, aby uložená data byla co nejkvalitnější a měla potřebnou váhu. Naproti databázím neobsahuje datový sklad pouze „klíčová“ slova či termíny, nýbrž obsahuje informace v celém kontextu – ucelené informace. ICR – (Intelligent Character Recognition) jde o rozšíření OCR o možnost rozpoznání a převedení do elektronické podoby ručně psaný text. Korpus - je soubor nebo kolekce textových dokumentů uložených v elektronické podobě. Pro potřeby analýzy textů, zejména pro jejich klasifikaci byly vytvořeny tzv. doménové korpusy, které sdružují dokumenty dle jejich tematických zaměření. Pro tyto účely byly vytvořeny reprezentativní korpusy spisovné češtiny, z nichž každý obsahuje 100 milionů textových slov (SYN2010) [22]. NLP techniky
(Natural Language Procesisng) – jedná se o metody předzpracování
textových dokumentů například odstranění stop-slov, stemmingem či lemmatizací. N-gram – jsou používané sekvence základních n po sobě jdoucích prvků dokumentu. Jsou široce využívány v pravděpodobnostních úlohách analýzy textových dokumentů. OCR – (Optical Character Recognition) jde o metodu digatalizace tištěných textů do elektronické podoby za pomocí zařízení jako je scanner. OMR – (Optical Mark Recognition) je metoda, která se využívá k zpracování například - 61 -
dotazníků, kde jsou sledovány zaškrtávací pole. Ortonormální matice – je reálná čtvercová matice, jejíž transponovaná matice je současně maticí inverzní. Řádky (sloupce) matice tvoří soustavu ortonormálních vektorů. Sémantický web – je způsob organizace webu do dokumentů pevných standardizovaných struktur, umožňujících snadné automatické zpracování. Klíčovým nástrojem jsou ontologie neboli formalizovaná doména znalostí.
- 62 -
9 Seznam použité literatury TIŠTĚNÉ ZDROJE: [1]
Bella, Martin. Metody indexace dokumentů: diplomová práce. Brno: Masarykova univerzita, Fakulta informatiky, 2010. Vedoucí práce RNDr. Matěj Štefaník.
[2]
Berka, Petr. Dobývání znalostí z databází. 1. vydání. Praha: Academia, nakladatelství Akademie věd České republiky, 2005. 368 s., ISBN 80-200-1062-9.
[3]
Berry M., Dumais S., O’Brein G.. Using Linear Algebra for Intelligent Information Retrieval; SIAM Review, vol. 37 issue 4, pp. 573-595, Philadelphia, USA, 1995. ISSN 0036-1445.
[4]
Berry M., Linoff G.. Data Mining Techniques, Second Edition. USA: Wiley Publishing, Inc. 2004. ISBN: 0-471-47064-3.
[5]
Cabena P., Hadjinian P., Stadler R., Verhees J., Zanasi A.. Discovering Data Mining - From Concept to Implementation. New Jersey: Prentice Hall PTR, 1998. 224 s., ISBN 978-0137439805.
[6]
Faber, Petr. Sumarizátor textů založen na latentní sémantické analýze: diplomová práce. Plzeň: Fakulta aplikovaných věd, Katedra informatiky a výpočetní techniky, 2007. Vedoucí práce Doc. Ing. Karel Ježek, CSs..
[7]
Fejfar, Kamil. Metody kategorizace textu: diplomová práce. Plzeň: Fakulta aplikovaných věd, Katedra informatiky a výpočetní techniky, 2007. Vedoucí práce Doc. Ing. Karel Ježek, CSs..
[8]
Holubec, Bohumil. Použití PSO metody pro selekci příznaků: diplomová práce. Praha: ČVUT, Fakulta elektrotechnická, Katedra informatiky a výpočetní techniky, 2008. Vedoucí práce Doc. Ing. Lenka Lhotská, CSc..
[9]
Jensen, Bill. Simplicity: The New Competitive Advantage in a World of More, Better, Faster. London: Perseus Publishing, 2001. 240 s., ISBN 9780738204307.
[10] Karásek J., Šanda P., Burget R., Morský O.. Strojové učení základen pro hybridní lematizační algoritmus. Elektrorevue: Časopis pro elektroniku, vol.57. Brno: Fakulta elektrotechniky a komunikačních technologií VUT v Brně, 2012. ISSN 1213-1539. [11] Lancaster T., Culwin F.. Classification of plagiarism detection engines: E-journal ITALICS, vol. 4 issue 2, 2005. ISSN 1473-7507. - 63 -
[12] Landauer T., Foltz P., Laham D.. An introduction to Latent Semantic Analysis, Discourse Processes. Official Journal of the Society for Text & Discourse, vol. 25. pp. 259-284, 1998. ISSN 1532-6950. [13] Leixner, Petr. Shlukování textových dat: diplomová práce. Brno: VUT, Fakulta informačních technologií, Ústav informačních systémů, 2010. Vedoucí práce Ing. Vladimír Bartík, Ph.D.. [14] Maimon O., Rokach L.. Data mining and knowledge discovery handbook. USA: Springer, 2005. e-ISBN-13: 9-780-387-25465-4. [15] Petr, Pavel. Data mining – díl 1. Univerzita Pardubice, 2010. 139 s., ISBN 978-807395-325-6. [16] Suchomel, Vít. Klasifikace dokumentů v textových korpusech: diplomová práce. Brno: Masarykova univerzita, Fakulta informatiky, 2010. Vedoucí práce RNDr. Jan Pomikálek.
INTERNETOVÉ ZDROJE: [17] Boguraev, B., Kennedy, C.. Salience-based content characterization of text documents, Advances in Automatic Text Summarization. [Online: 23. červenec 1997]. [Citace: 10. Srpen 2013]. URL:< http://home.uchicago.edu/>. [18] Brin, S., Page, L.. The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems. [Online 10. srpen 2013]. [Citace: 10. srpen 2013]. URL: < http://infolab.stanford.edu/>. [19] Coles, Paul. The Toxic Terabytes – How Data-dumping threatens business efficiency, IBM Global Technology Services. [Online: červenec 2006]. [Citace: 6. srpen 2013]. URL:
. [20] Cvček, Václav. KWords. Ústav Českého národního korpusu FF UK. [Online: 13. březen 20014]. [Citace: 13. březen 2014]. URL:< https://kwords.korpus.cz/>. [21] Cvrček, Václav a kol.. Český národní korpus. [Online: 2. únor 2013]. [Citace: 2. únor 2013]. URL: . [22] Český národní korpus – SYN2010. Ústav Českého národního korpusu FF UK, Praha 2010.
[Online:
9.
únor
2014]. - 64 -
[Citace:
9.
únor
2014].
URL:
. [23] Češka, Zdeněk. Využití moderních přístupů pro detekci plagiátů. [Online: 22. říjen 2009]. [Citace: 2. únor 2013]. URL: . [24] Erkan, G., Radev, D., G.. LexRank: Graph-based Lexical Centrality as Salience in Text Summarization. [Online: 2. únor 2013]. [Citace: 2. únor 2013]. URL: . [25] Háva, Ondřej. Fraud management aneb data mining v praxi. [Online 13. březen 2007]. [Citace: 16. říjen 2013]. URL:< http://www.systemonline.cz/>. [26] Hovy, E. H. Automated Text Summarization. [Online: 7. březen 2014]. [Citace: 7. březen 2014]. URL: < http://www.isi.edu/natural-language/>. [27] Hrabak, Petr. Dataminig. [Online: 13. leden 2012]. [Citace: 13. leden 2013]. URL: . [28] Húsek D., Pokorný J., Snášel V., Řezanková H.. Metody vyhledávání v rozsáhlých kolekcích dat. [Online: 18. Říjen 2003]. [Citace: 13. leden 2013]. URL: . [29] Infogram. Plagiátorství – projekty. [Online: 16. říjen 2013]. [Citace: 16. říjen 2013]. URL:< http://www.infogram.cz>. [30] Infogram. Úvod do problematiky plagiátorství. [Online: 16. říjen 2013]. [Citace: 16. říjen 2013]. URL:< http://www.infogram.cz>. [31] Ježek K., Steinberger J.. Sumarizace textů. [Online: 16. říjen 2013]. [Citace: 16. říjen 2013]. URL:. [32] Jordan, Patrick. LexRank demo. [Online 13. březen 2014]. [Citace: 13. březen 2014]. URL:< http://clair.si.umich.edu/demos/lexrank/>. [33] Jursic M., Lavrac N., et al. LemmaGen Multilingual Open Source Lemmatisation. [Online 15. únor 2014]. [Citace: 15. únor 2014]. URL:. [34] Kocek, Jan. Mi-score – vzájemná informace (mutual information). [Online: 3. květen 2013]. [Citace: 3. květen 2013]. URL: < http://ucnk.ff.cuni.cz/bonito >. [35] Koukal, Jaromír. Metody dolování dat a jejich užitečnost. [Online: leden 2008]. [Citace: 22. únor 2012]. URL: . - 65 -
[36] Krátký, Michal. Využití SVD pro indexování latentní sémantiky. [Online: únor 2002]. [Citace: 12. Července 2013]. URL:. [37] Lovins, Julie Beth. Development of a Stemming Algorithm. [Online 19. únor 2012]. [Citace: 19. únor 2012]. URL: . [38] Masarykova univerzita. Theses.cz. [Online: 15. duben 2014]. [Citace: 15. duben 2014]. URL:< http://www.theses.cz>. [39] Materna, Jiří. Sémantická analýza textů. [Online: 30. srpna 2011]. [Citace: 15. leden 2012]. URL: . [40] Seo servis. Seznam nejčastějších českých stop. [Online: 3.3.2014]. [Citace: 3.3.2014]. URL: <.http://seo-servis.cz/libs/stopwords.txt.cz>. [41] Spotfire. Overview of Hierarhical Clustering Theory. [Online 10. červen 2013. [Citace: 10.červen 2013]. URL: . [42] Tools 4 noobs. Online summarize tool (free summarizing). [Online 9. únor 2014]. [Citace: 9. únor 2014]. URL:. [43] Ulrich, Miloš. Text mining aneb kladivo na nestrukturovaná data. [Online: 15. leden 2012]. Citace: [15. leden 2012]. URL: . [44] Zavoral, Petr. Nestrukturovaná data: kolik jich je?. [Online 28. prosince 2010]. [Citace: 2. únor 2013]. URL: . [45] Ulrich, Miloš. Nový systém odhalí plagiátorství mezi vědci. [Online: 11. únor 2011]. [Citace: 23. prosinec 2013]. URL: .
- 66 -
10 Přílohy Příloha č. 1 Seznam stop slov a, a sice, a to, aby, aj, ale, ani, aniž, ano, asi, až, bez, bude, budeme, budeš, by, byl, byla, byli, byly, bylo, být, co, což, cz, či, článek, článku, články, další, dnes, do, ho, i, já, jak, jako, je, jeho, jej, její, jejich, jen, jenž, ještě, ji, jiné, již, jsem, jsi, jsme, jsou, jste, k, kam, každý, kde, kdo, když, ke, která, které, kterou, který, kteří, ku, má, máte, mezi, mi, mé, mě, mně, mnou, mít, můj, může, my, na, nad, nám, napiš, náš, naši, ne, nebo, nechť, nejsou, není, než, nic, ní, nové, nový, o, od, ode, on, pak, po, pod, podle, pokud, pouze, právě, pro, proč, proto, protože, první, před, přede, přes, při, ptá, re, s, se, si, strana, své, svůj, svých, svým, svými, ta, tak, také, takže, tato, tedy, těma, té, tě, ten, tento, této, tím, tímto, tipy, to, tohle, toho, tohoto, tom, tomto, tomuto, toto, tu, tuto, tvůj, ty, tyto, u, už, v, vám, váš, vaše, ve, více, však, všechen, vy, z, za, zda, zde, ze, zpět, zprávy, že [40].
Příloha č. 2 Nový systém odhalí plagiátorství mezi vědci Softwarový strašák na studenty, kteří by chtěli opsat svou závěrečnou práci z internetu, se stane noční můrou i pro akademiky. Informatici z brněnské Masarykovy univerzity totiž rozšířili svůj systém porovnávající texty a odhalující podobnosti i na odborné články, publikace a jiná díla. Spolu se studentskými pracemi se stanou v elektronické podobě součástí takzvaného Repozitáře, který do budoucna umožní také jejich zpřístupnění širší veřejnosti při dodržení autorských práv. „Projekt, na jehož realizaci získaly vysoké školy přes třináct miliónů korun, řeší široké spektrum problémů spojených s plagiátorstvím v terciárním vzdělávání,“ říká mluvčí Masarykovy univerzity Tereza Fojtová. „Nejde jen o vytvoření technických podmínek nebo systémů pro sběr prací a kontrolu textů, ale například i o vytvoření pravidel, jak postupovat při nalezení podobných textů,“ dodává Fojtová. „Hlavním úkolem odborníků z Fakulty informatiky Masarykovy univerzity bude vyvinout nový systém pro sběr, řízenou prezentaci a kontrolu odborných článků, publikací a jiných děl vytvořených zaměstnanci nebo doktorskými studenty – tzv. Repozitar.cz,“ informoval vedoucí projektu Michal Brandejs z Fakulty informatiky MU. „Řešení pro - 67 -
centralizovaný sběr celých textů s řízeným zveřejňováním a kontrolou proti plagiátorství dosud neexistuje. I ve světě se podle dostupných informací sbírají jen metadata, tj. nikoli celé texty,“ upřesnil Brandejs. Deset z patnácti vysokých škol, které se do projektu řízeného MU zapojily, se chystá také pořizovat, upravovat a následně napojit své lokální systémy pro sběr zaměstnaneckých děl na systém Repozitar.cz. Aby vyhledávání podobných souborů (možných plagiátů) bylo co nejúčinnější, bude databáze propojena s dalšími již existujícími systémy pro vyhledávání plagiátů – například Theses.cz (vysokoškolskými kvalifikačními pracemi) a Odevzdej.cz (studentskými pracemi) aj. Repozitar.cz umožní také zpřístupnit výsledky vědy širší veřejnosti při zachování vůle autorů. K tzv. otevřenému přístupu k vědeckým informacím, který prosazuje hnutí Open Access, se MU přihlásila loni v říjnu podpisem Berlínské deklarace. Informatici MU již proto také vytvořili vlastní univerzitní repozitář, který rozšiřuje stávající systém evidence publikací [45].
- 68 -
