Szövegbányászat és dokumentum kezelés

Szövegbányászat és dokumentum kezelés

1. Szöveg bányászat alapfogalmai

Dr. Kovács László ME GEIAL

Szövegbányászat Szövegbányászat = szöveg + bányászat Rövid történeti áttekintés: 1958 (Luhn): lényeges szavak kiemelése a szövegből 1961 (Doyle): a szavak gyakoriság alapú elemzése 1980: információ kinyerés (IR) explicit megjelenése 1988 (Swanson): szövegbányászat megjelenése 1995: módszerek kiszélesedése 2000: ipari alkalmazások elterjedése, előkészítési módszerek finomodása 2005: szemantika alapú megközelítés erősödése 2010: hatékonyság javulás Felhasználása: - titkosszolgálat - kutatás - törvénykezés - marketing Dr. Kovács László ME GEIAL

1

Szövegbányászat

Dokumentum kezelés Természetes nyelvi feldolgozás

Szerkesztés

Szövegbányászati módszerek

Megjelenítés

Publikálás

Adatbányászat Ontológia Statisztika

Metaadatok

Mesterséges intelligencia


Szövegbányászat Szövegbányászat fogalma Módszerek gyűjteménye a nagy mennyiségű szöveges formátumú Információkból a szabályszerűségek, minták feltárására. - cél a releváns, újszerű szabályok feltárása - nagy tanító halmazt igényel - rendszerint statisztikai alapú módszert alkalmaz - fontos a tanító halmaz megfelelő előkészítése - feldolgozási lépések: - megfelelő minta felépítése - dokumentum előfeldolgozás (transzformáció) - elemzések elvégzése

„it tries to discover or derive new information from the data (text) which was previously unknown „ (Hearst) Dr. Kovács László ME GEIAL

2

Szövegbányászat

Szöveg értelmezése

Szűkebb értelemben: természetes nyelvi dokumentum (regény, jelentés, levél,..) Tágabb értelemben: karakter sorozat (DNS, jelsorozat,..)

A szöveg lehet strukturálatlan és szemi-strukturált A számítógépen tárolt információk döntő többsége (≈80%) strukturálatlan vagy szemi-strukturált dokumentumokban tárolódik PubMed dokumentum-bázis: - orvosi cikkek gyüjteménye - kb. 16 millió cikk - havonta 40000 új dokumentum Az elemzéshez jól kell ismerni a terület fogalmait (domain knowledge) Dr. Kovács László ME GEIAL

Dokumentumok ábrázolása

Cél a tartalmi elemzés A formátum is hordozhat tartalmi elemeket Dokumentum felépítési szintjei: - karakter (kódolás,..) unigram, bigram, n-gram - szó szóalak, alapszó, ragozás - kifejezés szó vagy szólánc - fogalom áttételes, absztrakt Az alapszint statisztikai alapú, a felső ontológia alapú Dr. Kovács László ME GEIAL

3

Dokumentumok ábrázolása

Dokumentum modellek halmaz

Lista

Vektor

Betű

BOL

LOL

VOL

Szó

BOW

LOW

VOW

Kifejezés

BOT

LOT

VOT

Fogalom

BOC

LOC

VOC

CDM: concept document model VS: vector-space model B: bag of … L: list of … Dr. Kovács László ME GEIAL

Szövegbányászat A dokumentum feldolgozás tipikus műveleti: - fogalmak csatolt előfordulásainak megkeresése - fogalmak előfordulási gyakoriságai - fogalmak relevanciái - mintakeresés - kapott szabályok megjelenítése - trend elemezés - véleményelemzés - kivonatolás - eltérés kiemelés - hasonlóság mérése - fogalmak társítása - szótár készítés


4

Szövegfeldolgozó rendszerek architektúrája

Modulok: - Előfeldolgozó - Alapműveletek - Megjelenítés - Visszacsatolás

Adatstruktúrák: - dokumentum forráskészlet - transzformált dokumentumok - indexek - szótárak - metaadatok (nyelv,..,)

Előfeldolgozó: - konvertálás - tisztítás - redukálás

Megjelenítés: - GUI - 3D - lényegkiemelés

Alapműveletek: - klaszterezés - osztályozás - mintakeresés

Visszacsatolás: - módszer értékelése - paraméter korrekció - iteráció


Szövegfeldolgozó rendszerek architektúrája

séma adatbázisok dokumentum

e-mail

Dokumentumok begyűjtése

Dokumentumok előfeldolgozása

Dokumentumok archiválása

szöveg Iteratív dialógus kezelés

Dokumentumok lekérdezése

Feldolgozó alap algoritmusok

felhasználó


Külső adatbázisok

5

Feldolgozási eljárások A szöveg feldolgozási eljárások célja: hatékony információ lekérdezés, keresés Különböző szintű lekérdezések: Kérdés1: Keressük azon dokumentumokat, amelyben szerepel a labda szó, de nem szerepel a gól szó Kérdés2: Keressük azon dokumentumokat, amelyben szerepel a labda szó valamely alakja Kérdés3: Keressük azon dokumentumokat, amelyben együtt szerepel a labda és a gyártás szó Kérdés4: Keressük azon dokumentumokat, amely a fociról szól Kérdés5: Keressük azon dokumentumokat, amelyek hasznosak lehetnek a futbalistáknak


Szövegbányászat Egység karakter

Lekérdezés egzakt

statisztika

pozíció alapú

n-gram

közelítő

szó

fogalmi

kifejezés fogalom

szemantika Módszer mintakeresés klaszterezés osztályozás


értelmezés

kivonatolás

6

Feldolgozási eljárások Term – dokument mátrix (BOW) Hatékony indexelésre van szükség Hamlet

Othello

Macbeth

Antony

Antony and Cleopatra

1

Julius Caesar The Tempest

1

0

0

0

1

Brutus

1

1

0

1

0

0

Caesar

1

1

0

1

1

1

Calpurnia

0

1

0

0

0

0

Cleopatra

1

0

0

0

0

0

mercy

1

0

1

1

1

1

worser

1

0

1

1

1

0

Megfelel egy bitmap indexnek Nagy tanító mintáknál kezelhetetlenné válhat


Feldolgozási eljárások Invertált Term – dokument index

- Csak az értékes adatok maradnak meg - Láncolt listás megoldás - pointerek tárolása extra helyigény

Brutus

2

4

8

16

Calpurnia

1

2

3

5

Caesar

13

Dictionary

32 8

64 13

21

128 34

16

Postings


7

Feldolgozási eljárások Invertált Term – dokument index

Dokumentum készlet

Friends, Romans, countrymen. Tokenizer

Szöveg tokenizálás

Tokenek normalizálása.

Invertált index Dr. Kovács László ME GEIAL

Friends Romans

Countrymen

Linguistic modules friend

roman

countryman

Indexer friend

2

4

roman

1

2

countryman

13

16

Feldolgozási eljárások Invertált Term – dokument index Szövegből a kifejezések kigyűjtése : (term:document)

Az kapott lista rendezése kifejezés szerint

A kifejezések gyakoriság meghatározása


8

Feldolgozási eljárások Invertált Term – dokument index Term Doc # ambitious be brutus brutus capitol caesar caesar did enact hath I i' it julius killed let me noble so the the told you was was with

Freq 2 2 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 2 2 1 2 2 2 1 2 2

Doc #

1 1 1 1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1

Freq 2 2 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 2 2 1 2 2 2 1 2 2

Term N docs Tot Freq ambitious 1 1 be 1 1 brutus 2 2 capitol 1 1 caesar 2 3 did 1 1 enact 1 1 hath 1 1 I 1 2 i' 1 1 it 1 1 julius 1 1 killed 1 2 let 1 1 me 1 1 noble 1 1 so 1 1 the 2 2 told 1 1 you 1 1 was 2 2 with 1 1

1 1 1 1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1


Feldolgozási eljárások Invertált Term – dokument index Az invertált lista alkalmazható összetett keresések meggyorsítására Kérdés: Keressük azon dokumentumokat, amelyben szerepel a labda szó és szerepel a gól szó

2

8

2

4

8

16

1

2

3

5

32 8

64 13

128 21

34

labda gól

A két lista metszetét vesszük Műveletek megfeleltetése: A AND B ⇒ List (A) metszet List(B) A OR B ⇒ List (A) union List(B) NOT A ⇒ komplemens List (A) Dr. Kovács László ME GEIAL

9

Feldolgozási eljárások Invertált Term – dokument index Összetett feltételek hatékonysági kérdései A AND B AND C AND D … A megadott listák metszetét kell képezni. A sorrend meghatározza a költséget A legkisebb hosszúságú listával kell kezdeni

Brutus

2

Calpurnia

1

4 2

8

16 32 64 128

3

5

8

13 21 34

13 16

Caesar

A javasolt sorrend: (Ceasar AND Brutus) AND Calpurnia Dr. Kovács László ME GEIAL

Feldolgozási eljárások Invertált Term – dokument index Összetett feltételek hatékonysági kérdései Az OR művelet költsége - minden tagra a méret meghatározása (gyakoriság) - OR műveletnél a méretek összegét vesszük

(tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)


Term eyes kaleidoscope marmalade skies tangerine trees

Freq 213312 87009 107913 271658 46653 316812

10

Feldolgozási eljárások Invertált Term – dokument index Költség jellemzők: N: dokumentum db, M: szó db, L: dokumentum hossz, w: szóhossz, (M > L) Hely: dokumentumok: N*L*w index: M * (N* (L/ M))*w’ = N*L*w’ (25%) Idő: Keresés: N*L / M Metszet : 2 * N*L / M


Feldolgozási eljárások Amit nem támogat az alap invertált index: - kifejezések (szóláncok) keresése - pozíció alapú keresés - közelítő keresés - találatok rangsorolása

A AND B*C


11

Feldolgozási eljárások Invertált Term – dokument index Hatékonyság javítása A szomszédokra lépés helyett nagyobb ugrás a keresénél

128

16

2

4

8

16

32

64

128

31

8

1

2

3

5

8

17

21

31

Skip-lista alkalmazása


Feldolgozási eljárások Invertált Term – dokument index Skip lista előnye: Ha a szomszéd értéke nagyobb mint a távoli ugráshely értéke, akkor lehet ugorni. Hátránya: plussz vizsgálat + plussz helyköltség (pointer)

128

16

2

4

8

16

32


128

31

8

1

64

2

3

5

8

17

21

31

K listahossz esetén sqrt(K) hosszú ugrés

12

Feldolgozási eljárások Invertált Term – dokument index Kifejezésekre történő indexelés: az indexbe szópárok is kerülnek (szomszédos szavak) Tetszőleges szólánc felbontható szópárokra A kifejezés tangerine trees and marmalade skies felbontható az alábbi részekre tangerine trees AND trees and marmalade AND marmalade skies

Nem elég rugalmas, költséges L L2


Feldolgozási eljárások Invertált Term – dokument index Pozíciót is tároló indexelés A dokumentumhoz az előfordulási pozíciók is megadásra kerülnek

Megnövekedett költség (55%-az alap dokumentumnak) Alkalmas közelség alapú keresésre, sorrend alapú keresésre


13

Gyakorlati feladatok

F1 : Készítsen gyakoriság számláló algoritmusokat: a: karakter gyakoriság b: 2-gram gyakoriság c: szó gyakoriság (j2am.zip) (00598doc.zip) F2: rajzolja fel a gyakoriság hisztogramot hasonlítsa össze az egyes nyelveket F3 : készítsen invertált index struktúrát a: index felépítése b: AND, OR alapú keresés F4 : készítsen invertált pozíció tároló index struktúrát a: index felépítése b: közelség alapú keresés Dr. Kovács László ME GEIAL

Tokenizálás Értelmezési problémák: Finland’s capital → Finland? Finlands? Finland’s? Hewlett-Packard → Hewlett és Packard két token? San Francisco: egy vagy két token? Hogy lehet eldönteni? Japán, kínai nyelvekben nincs szóköz Az értékek alakjai, formátumai nemzet-függőek (12.11) Egy szó jelentése nyelvfüggő Hangzás alapú hibák kezelése Célszerű a szótövekre bontani a szöveget


14

Szótőkeresés

Nyelvfüggő Angol: egyszerűbb szabályok Porter algoritmusa: fix átalakítások rendszere sses → ss ies → i ational → ate tional → tion

http://facweb.cs.depaul.edu/mobasher/classes/csc575/porter.html Porter_stemer.txt


15

Szövegbányászat és dokumentum kezelés

Recommend Documents