Martin Dostal
Analýza nestrukturovaných dat s využitím Linked Data Katedra informatiky a výpočetní techniky Fakulta aplikovaných věd Západočeská univerzita v Plzni
Obsah 1) Linked Data • •
Problém s různou úrovní popisu Řešení disambiguace
2) Volba vlastností s využitím Linked Data • •
PageRank Pojmenování shluků s LD
3) Analýza sw specifikací – ukázka komplexní úlohy 4) Možnosti využití v praxi
LINKED DATA (PROPOJENÁ DATA)
3
Data ve strojově čitelné podobě: např. RDF, RDFa, SPARQL
1) Linked Data - teorie The Beatles
John_Lennon formerBandMembers
http://dbpedia.org/page/The_Beatles
Paul McCartney
organisation
band Liverpool
Help! (album)
songs
Help! (song)
http://dbpedia.org/page/Help!_(album) England
4
1) Linked Data – problém s různou úrovní popisu
Co je to? Počítač
Notebook Dell
Notebook Dell Latitude e6400
LD: http://www.czc.cz/dell-latitude-e6400-n10-e6400-0002-cerna/ 5
1) Linked Data – disambiguace
bank (anglicky) banka
břeh
Řešení
LD: http://dbpedia.org/ontology/Bank rdfs:comment > company … banking or financial services
6
1) Linked Data – disambiguace Disambiguaci lze realizovat s využitím:
1)Vlastností entity z LD • Otevírací hodiny • Kontakt: adresa, email, telefon
většinou dostatečné
2)Popisu entity • a company which main services are banking or financial services. • + případnou analýzou „banking services“ 7
VOLBA VLASTNOSTÍ (FEATURE SELECTION)
8
2) Volba vlastností (feature selection)
• Cíl – Redukce dimenze, snížení počtu vlastností – Odstranění rušivých vlastností, které zvýší přesnost a úplnost algoritmu
• Metoda – Výběr existujících vlastností – Generování nových vlastností na základě existujících
9
2) Volba vlastností s LD
Postup: • Najdeme klíčová slova dokumentu a namapujeme je na uzly v Linked Data • Provedeme expanzi uzlů – viz. další slide • Uzly ohodnotíme s využitím PageRanku • Vybereme uzly dle počtu výskytů, PageRanku apod. a použijeme je jako vlastnosti pro další algoritmy.
10
2) Volba vlastností - princip expanze uzlů
Článek: … pro uložení dat použijeme MySql nebo v případě většího objemu dat Oracle … Postup: 1. Určíme klíčová slova – např. statisticky 2. Z LD určíme společného „rodiče“, kterým je databáze 3. Vstupní množina vlastností pro článek: MySql, Oracle, databáze 11
2) Princip PageRanku
2 2 1
2
4 2
9
5 5
3
3
3
5
3
12
2) Volba vlastností - LD + PR článek
MAX PR
MAX PR článek
článek 13
2) PageRank – inicializace (omezení expanze)
a) Všechny hrany mají stejnou váhu. b) Základní uzly mají přidané samocitace. c) Hodnota hran klesá se vzdáleností od počátečních uzlů (obsažených v textu).
14
2) Volba vlastností – LD + PageRank
• Vstup: • Data: 20 News groups – 18 000 článků, • Features (keywords): 2,3 mil. k celé kolekci 20 News groups + vazby mezi vlastnostmi z Linked Data
• Výstup: • Feature selection (LD + PR) ke každému článku: » 1 nejlepší, » max. 20 nejlepších, optimální řešení » všechny nejvýznamnější uzly z komponent.
Jak zvolit počet vlastností (uzlů z LD)? 15
2) Vliv na klasifikaci - Rocchio class. (F1)
Problém s přetrénováním, dobré pro menší trénovací sady
16
2) Shlukování s využitím LD
Můžeme použít 2 základní přístupy: • Využít existující algoritmus – vstupem budou získané vlastnosti. • Vlastní algoritmus pro shlukování nad vytvořeným grafem využívající např. počet hran mezi uzly nebo délku cesty.
17
2) Pojmenování shluků (cluster labeling) – existuje: • Cluster differential labeling – Jméno = 1 nebo více klíčových slov. – Maximální odlišení od ostatních shluků. Dobré rozlišení, ale špatně čitelné pro člověka.
• Cluster internal labeling – Jméno = název dokumentu. – Výběr dokumentu, který je nejblíže centroidu. Dobře čitelné pro člověka, ale špatné rozlišení. Riziko nevhodně pojmenovaného článku.
18
Cluster differential labeling Shopping, clothes
Technology, computer
Existuje
Firefox, browsers, IE
19
Cluster internal labeling 18 Breathable, Simple Summer T-Shirts
Which of the big five Web Browsers is the Best?
What's the difference between an Intel Core i3, i5 and i7?
Existuje
20
Cluster labeling with Linked Data Clothing fashions Fashion is a popular style or practice, especially in clothing …
Technologie Technologie je odvětví techniky, které se zabývá tvorbou …
Nové
cz, en
Mozilla Firefox Mozilla Firefox je svobodný multiplatformní webový prohlížeč, který …
21
ANALÝZA SW SPECIFIKACÍ (APLIKACE METOD)
22
3) Analýza sw specifikací - postup • Named Entity Recognition (NER) s LD – Detekce aktérů a normalizace: OS -> operační systém • Funkční požadavky – lze vytipovat s využitím LD • Mimo-funkční požadavky – LD + ontologie • Detekce a normalizace případů použití (use-case) s využitím regulérních výrazů – Vyhledat „use-case“: \b([Uu]se\-?[Cc]ase) – Vyhledání odrážek: [\-|\*|\#|A-Za-z|1-9*]+[\.|\)]*
23
3) Ukázka analýzy sw specifikace • • • • 1. 2. 3. 4. 5.
UseCase: Buyer searches for an offer Scope: Marketplace Component: Marketplace Information System NER Primary actor: Buyer Buyer enters basic search criteria System responds within few seconds with the list of matches Buyr requests the complete listing of a selected offer System responds with the requested information Buyer pays via credit card / wire transfer.
24
3) Výsledek analýzy sw specifikace • Aktéři: nakupující (buyer) • Požadavky na systém: – Hledání (search) – Odpověď do několika sekund (few seconds)
1. iterace
• Požadavky na platby: – credit cart – wire transfer
• Požadavky na systém: – Odpověď do 2 sekund – upřesnění od zákazníka
2. iterace
25
3) Analýza sw specifikací - význam • Hrubou analýzu požadavků provede stroj a omezí možnost lidské chyby. Chybějící požadavky označí člověk. • Je možné kombinovat s nástrojem pro správu verzí jako např. GIT. – Iterace 1: několika sekund – „popis_eshopu.doc“ – Iterace 2: 2 sekund – „popis_eshopu.doc“
• Velký význam pro: – Obchodníka – např. z důvodu případné reklamace – Programátora – jasně vidí, že došlo ke změně požadavků a kdy ke změně došlo
26
MOŽNOSTI VYUŽITÍ V PRAXI
27
Praktické využití Většina metod byla experimentálně implementována v prostředí s omezenou RAM a dobou běhu skriptu. Je možné využití: • V prostředí webu – JavaScriptová aplikace (AngularJS + NodeJS) • Mobilní aplikace – Většina výpočtů jde realizovat přímo v zařízení. – Rychlost procesorů je více než dostatečná. – Uložení dat o velikosti několika GB opět není problém.
28
Oblasti využití Linked Data je možné využít k odhalení synonym, nadřazených i podřazených pojmů v libovolném textu. V kombinaci s dalšími metodami je možná detekce překlepů nebo identifikace klíčových frází (2 a více slov). Hlavní význam Linked Data spočívá v podobě přidání sémantického významu do existujících webových stránek např. s využitím RDFa. Viz. následující slide.
29
BBC music
Coldplay
http:// …
1996-09
30
Závěr • Navržené metody lze využít k extrakci témat obsažených v textu. Dle toho lze rychle určit, zda jsou např. dva dokumenty tématicky shodné i když neobsahují stejná slova. • Tyto metody jsou zajímavým alternativním řešením k čistě statistickému přístupu. • Algoritmy a ani LD nevyžadují žádnou licenci a je možné jejich plné využití.
Děkuji za pozornost Dotazy?
