Razprave Gradnja hierarhične strukture konceptov iz nestrukturiranih tekstovnih dokumentov Robert t Leskovar, J6zsef Gyorkos, Ivan Rozman Univerza v Mariboru, Fakulteta ?a elektrotehniko, računalništvo in informatiko. Inštitut za informatiko. Smetanova ulica 17. Maribor RLeskovar@uni-mb.si Povzetek Metode za iskanje po obsežnih bazah dokumentov in za klasificiranje dokumentov pogosto uporabljajo za učinkovitejše delovanje vnaprej pripravljene opise področnih kategorij. V prispevku je predstavljena izvirna metoda za samodejno gradnjo hierarhične strukture vsebinskih konceptov, ki jih določi z analizo množice dokumentov. Struktura omogoča učinkovito brskanje in iskanje po vsebinskih konceptih ter zelo poenostavi oblikovanje opisa področnih kategorij za poljubno množico dokumentov. Metoda je zasnovana neodvisno od jezika, v katerem je zapisana vsebina dokumentov. Predstavljeni sla tudi razširitvi za semantično povezovanje konceptov in za pospešitev delovanja metode. Abstract CONSTRUCTION OF A HIERARCHICAL CONCEPT STRUCTURE FROM UNSTRUCTURED TEXT DOCUMENTS Document retrieval methods, implemented for large document collections and document classification methods often use predefined descriptions of subject categories to improve their efficiency. In the article the original method for automated construction of a hierarchical concept structure is presented. The structure is built through an analysis of the documents in a collection. Such a stmcture makes efficient concept browsing and searching feasible and simplifies defining of subject category descriptions for arbitrary document collections. The method is independent of language used in documents. Two improvements are introduced as well, aiming a£ connecting the concepts semantically and improving a processing capacity of the method. ■ ■ ■ 1. Uvod 1.1 Pridobivanje informacij Količina informacij, zapisanih v nestrukturirani ali delno strukturirani tekstovni elektronski obliki (nadalje: informacij), s katerimi se kot Informacijska družba srečujemo v okoljih delovnih organizacij in v spletu, je vse manj obvladljiva in zahteva nove metode iskanja in predstavitve želenih informacij. Znanje, zapisano s temi informacijami, ima visoko vrednost in njegovo učinkovito upravljanje je ključnega pomena za kakovost delovnih procesov ter posledično konkurenčnost organizacij, tako gospodarskih kot negospodarskih. Metodo pridobivanja informacij (ang. 'Information retrieval') so se v zadnjih dvajsetih letih razvile od preprostega iskanja dokumentov do zahtevnejšega iskanja, klasificiranja, filtriranja in grupiranja dokumentov. Področje pridobivanja informacij ne zajema le sintaktičnega vidika dokumentov, ki je predmet preprostega iskanja, ampak tudi na semantični in pragmatični vidik dokumentov. Preprosto isknnje (v literaturi je običajno omenjeno kot 'prosto iskanje po tekstu') na podlagi uporabnikovega povpraševanja vrne seznam dokumentov, ki vsebujejo natančno takšne izraze, kot so bili zapisani v povpraševanju. Pomanj- kljivosti, ki jih vsebuje ta postopek, so neprepozna^ vanje večpomenskih besed, sinonimov, izvorov besed, sklanjatev in spregate v. Učinkovitost iskanja je temu primerno ni/.ka. Osnovne veje področja pridobivanja informacij so danes: ■ Iskanje dokumentov (najpogosteje ga imenujemo kar 'pridobivanje informacij') temelji predvsem na enem od štirih modelov ter njihovih variantah -verjetnostnem, Hoolovem modelu na podlagi mehke logike in vektorskem. Kot rezultat procesa dobimo iz baze dokumentov seznam dokumentov, ki so urejeni po stopnji ustreznosti glede na povpraševanje. Več o posameznih modelih je na voljo v [Yates, 99I. « Klasificiranje dokumentov (v literaturi tudi kategorizira nje, ang. 'classification' oz, 'categorization') izvaja razporejanje dokumentov, ki se nahajajo v skupni bazi, v vnaprej določeno množico področnih kategorij. Razporejanje temelji na vsebini dokumentov in ne na melainformacijah, ki jih lahko dokumenti vsebujejo. Zato je razporejanje nede term mističen proces. „/„„»WIN FORM ATI KA 2002 Številka 2 - letnik X ft o tiei t T. l.eskovar, J6?s&f Gyčrkas, Ivan Rozman: Gradnja hierarhično strukture konceptov iz nftStfUKturlianlh tekstovni It dokumentov ■ Filtriranje dokumentov je oblika klasificiranja, ki razporeja dinamični tok dokumentov v vnaprej določene kategorije, najpogosteje glede na profil uporabnika, v katerem so v obliki pravil zapisani njegovi izbori. Primeri so sistemi za filtriranje novic, reklamnih sporočit ali Usenet novic. ■ Gntfiinuijc dokumentov (v literaturi tudi grozdenje ali združevanje, ang. 'clustering') združuje dokumente v grupe na podlagi določenih skupnih značilnosti. Rezultati naše raziskave predstavljajo doprinos iskanju in klasificiranju dokumentov. V nadaljevanju bomo dodatno utemeljili potrebo po tovrstnih raziskavah. 1.2 Ovire za učinkovito pridobivanje želenih informacij in motivacija za raziskavo Pri interakciji med človekom in informacijskim sistemom prihaja do več ovir, ki otežujejo učinkovito pridobivanje želenih informacij. Ena od ovir je nezmožnost uporabnikov, da bi oblikovali ustrezno povpraševanje. Pri iskanju v spletu je posledica tega Ogromna množica vrnjenih dokumentov, med katerimi uporabniki ne najdejo želenih. Študija rabe spletnega iskalnika Excite je pokazala, da so povpraševanja v povprečju krajša od treh besed IJansen, 981. Osnovna razloga za to sta, da obstajajo med različnimi avtorji dokumentov razlike v rabi jezika, ki so pogojene med drugim z njihovo izobrazbo, kulturo, razgledanostjo in namenom pisanja, in da uporabniki, ki niso strokovnjaki računalniške stroke, ne poznajo principov, po katerih delujejo metode za iskanje informacij, K reševanju tega problema so se usmerite tehnike za samodejno razširjanje povpraševanj z ustreznejšimi izrazi in za usmerjanje povpraševanj na podlagi vnaprej zgrajenih seznamov izrazov, ki jih uporablja določeno vsebinsko področje (imenujemo jih vertikalni tezavri), vendar povzroči večje število izrazov pogosto tudi večji obseg pridobljenih dokumentov, tako ustreznih kot neustreznih. Druga ovira za uspešno iskanje informacij se pojavi, če naša informacijska potreba ni jasno definirana. V takšnih primerih se raje lotimo brskanja po katalogih informacij (če so na voljo), kjer so dokumenti razvrščeni v področne kategorije. To nam omogoča, tla pridemo prek kategorij do želenih informacij, ali da odkrijemo informacije, ki bi nas utegnile zanimati. Za klasificiranje dokumentov v kategorije skrbi klasilikator - sistem, ki skuša s pomočjo različnih metod ugotoviti, v katero kategorijo (ali več kategorij) je potrebno dokument uvrstiti glede na njegovo vsebino. Najpogosteje so v rabi metode strojnega učenja, s katerimi klasifikator z 'opazovanjem' značilnosti množico dokumentov, ki jih je poprej klasificiral v vnaprej določeno množico kategorij strokovnjak, določajo uvrstitev v te kategorije tudi za ostale doku- mente. Na mnogih področjih so se zato oblikovale taksonomije kategorij. V spletu so to splošnonamen-ski katalogi, kot sta Vahool-jeV in Infoseek-ov, ki so osnova veČini iskalnikov, ameriška Kongresna knjižnica ima sistem oznak Library of Congress Subject Headings (LCSH), v mnogih knjižnicah se uporablja Deweyeva decimalna klasifikacija (DDC), v medicinski domeni uporabljajo množico medicinskih oznak Medical Subject Headings (MeSH) itn.. Nnjnatančneje lahko klasificiramo dokumente, če so v njih navedeni metapodatki - klasifikacijske oznake ali ključne besede. Kadar niso, jih lahko doda urednik ali katalogizator, ki pozna oziroma preuči vsebino, vendar je to drag in dolgotrajen proces. Na človeško izbiro oznak in ključnih besed vpliva tudi več dejavnikov -predvsem izkušnje, razgledanost, izobrazba in konsistentnost pri uporabi oznak. Raziskave konsistentnosti pri izbiri oznak za opis vsebine določenega dokumenta so pokazale, da se oznake, ki jih izbereta dva različna profesionalna katalogizatorja, razlikujejo v povprečju za 20 odstotkov | Ha rman, 95]. Našo raziskavo smo usmerili v razvoj metode, ki omogoča, da lahko dobi uporabnik - iskalec informacij - hiter, strukturiran pregled vsebine množice dokumentov, ko ni na voljo vnaprej pripravljena taksono-mija kategorij, v katere bi jih lahko klasificirali, in ko dokumenti niso opremljeni z metapodatki. V ta namen pretvori metoda vsebino dokumentov v hierarhično strukturo, V kateri se nahajajo med seboj povezani vsebinski koncepti, kar omogoča učinkovito brskanje in iskanje želenih informacij in predstavlja osnovo za gradnjo taksonomije kategorij. Metodo smo zasnovali neodvisno od jezika, v katerem so dokumenti. Z razširitvami, prilagojenimi določenemu jeziku, lahko še dodatno povečamo njeno učinkovitost. 1.3 Definicije Najprej bomo natančneje definirali osnovne termine, ki jih uporabljamo v prispevku. Termina 'dokument' in 'izraz' sta privzeta termina iz področja pridobivanja informacij. Dokument pomeni določeno tekstovno enoto, npr. naslov, povzetek, odstavek, prispevek, poglavje. Množica dokumentov je množica tekstovnih enot. Izraz je ključna beseda (lahko besedna zveza), ki sodeluje pri opisu vsebine dokumentov. Za ključne besede izberemo predvsem tiste, ki nosijo večji pomen (predvsem samostalniške besedne oblike). Koncept imenujemo množico izrazov, ki soodvisno nastopajo pri opisu določenih vsebinskih delov. Samodejno prepoznavanje konceptov temelji na dejstvu, da pri opisovanju podobnih stvari uporabljamo podobne besede. Koncepte lahko natančneje določimo ob primerjavi več vsebinsko sorodnih dokumentov. 2002 ■ številka 2 - letnik X i i/xMnln /nI NFOR M AT IKA Robert F, Lesfcovar, Jozsef Gyijrftos, Ivan Rozman: Gradnja hierarhične strukture konceptov iz nesrru k turi ranih tekstovnih dokumentov 2. Sorodna dela Forsyth in Rada sta v svojem delu določala splošnost in specifičnost izrazov na podlagi števila dokumentov, v katerih se pojavljajo [Forsyth, 86]. Uporabila sta predpostavko, da je izraz bolj splošen, če se pojavi v več dokumentih. Na podlagi tega sta zgradila manjši veenivojski graf, ki je predstavljal relacije med izrazi. Woods je v svojem delu uporabil analizo angleških fraz v povezavi z veliko bazo znanja, na podlagi Česar je organiziral izraze v hierarhije konceptov [Woods, 97\. Uspeh tehnike je temeljil na bogati bazi morfološkega znanja, s katerim je identificiral komponente fraz. Hierarhijo konceptov je uporabil za samodejno razširjanji* povpraševanj pri iskanju dokumentov. Sanderson in Croft sta se lotila gradnje hierarhije konceptov iz dokumentov, ki so bili pridobljeni na podlagi povpraševanja, s primerjanjem medsebojne vsebovanosti izrazov [Sanderson, 99]. Iz množice dokumentov sta najprej s pomočjo določenega povpraševanja pridobila tiste dokumente, ki so vsebinsko vezani na povpraševanje. Množico dokumentov so zato že sestavljali dokumenti, ki uporabljajo izraze na podoben način. Množico izrazov, ki bodo vsebovani v hierarhiji, sta pridobila iz izrazov razširjenega povpraševanja in izrazov, ki se pojavljajo v več kot 10% v pridobljenih dokumentih glede na celotno bazo. Izraze sta nato primerjala glede na relacijo 'vsebovan-je' (angi 'subsumption'): izraz A vsebuje izraz B, če nastopa v več kot 8(1% dokumentov, v katerih nastopa izraz 1J, Glede na medsebojno vsebovanje sta izraze uredila v hierarhijo, pri čemer sta izločila izraze z nizko frekvenco pojavljanja. Izrazi v njuni hierarhiji lahko imajo več staršev. Yang in Lee pristopata h gradnji hierarhije z metodo nenadzorovanega učenja nevronskih mrež, ki se imenuje snnun>rgcitiizirnioče mape [Yang, 001, Avtorja sta z učnimi primerki dokumentov vzpostavila dve mapi, mapo grup dokumentov in mapo grup izrazov. Dominantne nevrone v mapi grup dokumentov (ki predstavljajo določeno grupo dokumentov) sta vzela kot centroide nadgrup, ki predstavljajo bolj splošno kategorijo. Izraze, ki so povezani z istoležečim nevronom v mapi grup izrazov, sta nato uporabila kot izraze, ki opisujejo kategorijo. I lierarhijo kategorij sta zatem gradila z iskanjem korelacij med nevroni v obeh mapah. Rezultati so žal predstavljeni s kitajskimi pismen-kami (avtorji so testirali pristop na množici dokumentov v kitajščini), zato jih ne moremo ovrednotiti. Avtorja omenjata nujnost zmanjšanja dimenzij vhodnih podatkov, vendar tega postopka nista opisala. Iz prispevka tudi niso razvidni načini za določanje začetne velikosti samoorganizirajoče mreže, topologije mreže (kar lahko naredimo le empirično) in faktorja učenja, ki so pomembni parametri za uspešno delovanje samoorganizacije. Pričujoče delo se od omenjenih razlikuje v bolj univerzalnem načinu za določanje splošnosti izrazov, ki upošteva za vsak izraz število in moč njegovih korelacij, in v načinu gradnje hierarhične strukture konceptov, ki omogoča natančnejše določanje konceptov. Za gradnjo strukture ne potrebujemo pripravljenih učnih primerkov. Struktura konceptov, ki jo zgradi v nadaljevanju predstavljena metoda, je sestavljena iz več hierarhij, znotraj katerih so koncepti jasno izraženi glede na dokumente, v katerih se pojavljajo, med hierarhijami pa so šibko povezani, kar omogoča hiter pregled različnih delov vsebine celotne množice dokumentov. Vsebina množice dokumentov je lahko raznovrstna. 3. Metoda za gradnjo hierahične strukture konceptov Med opisom metode bomo predstavljali njeno delovanje na majhnem, preglednem primeru - tekstu desetih naslovov prispevkov, od katerih jih šest opisuje pridobivanje informacij in štirje aplikacije teorije grafov. Delovanje metode smo testirali na bazah dokumentov velikosti od 10 do 300 dokumentov, ki smo jih tvorili i/, standardnih baz dokumentov TIME (novice iz vsega sveti), objavljene v reviji TIME leta 1963), C RAN (povzetki člankov s področja aerodinamike) in na bazi 110 dokumentov, ki govorijo o terorističnih napadih in njihovem ozadju. Z;i predstavitev konceptov v zgoščeni obliki smo izbrali hierarhično drevesno strukturo - neusmerjen, neciklieen graf, v katerem lahko ima vsak otrok le enega starša. Struktura konceptov je sestavljena iz več dreves (hierarhij), ki vsebujejo koncepte* Koncepti znotraj hierarhij so močno, med hierarhijami pa šibko povezani. Koreni hierarhij so izrazi, ki so v konceptih hierarhij najmočneje zastopani. Kot model za predstavitev vsebovanosti izrazov v dokumentih smo izbrali model vektorskega prostora |Sal-ton, 711, ki je v praksi najbolj uporabljan model, saj omogoča učinkovito obdelavo s statističnimi algoritmi in algoritmi strojnega učenja, ki izvajajo združevanje, klasificiranje, analizo glavnih komponent in druge vrste obdelav, V tem modelu so izrazi predstavljeni z vrsticami in dokumenti s stolpci matrike. Elementi matrike so uteži, ki jih priredimo posameznemu izrazu za določen dokument. Metoda za samodejno gradnjo hierarhične strukture konceptov zajema Štiri osnovne korake, ki jih bomo podrobneje predstavili v nadaljevanju: 1. Gradnja matrike izrazov ter dokumentov. 2. Računanje matrike koreiativnosti izrazov. 3. Računanje globalnih ko relacijski h stopenj in iskanje korenov hierarhij. 4. Gradnja hierarhične strukture. r rfxmi/>7 ml NFO RM ATI KA 2002 - Številka 2 ■ latnik X Robert F, Lesfcovar, Jozsef Gyijrftos, Ivan Rozman: Gradnja hierarhične strukture konceptov iz nesrru k turi ranih tekstovnih dokumentov 1. Gradnja matrike izrazov ter dokumentov Ta korak je običajen začetni korak v pridobivanju informacij in zajema večino naslednjih aktivnosti; (a) izbor izrazov iz baze dokumentov, (b) krojenje izrazov, (c) uteževanje in normaliziranje izbranih izrazov ter (d) združevanje izrazov, predstavljenih z enakimi vektorji. V prvi aktivnosti iz množice vseh izrazov, ki nastopajo v bazi dokumentov, izločimo blokirane izraze. V splošnem lahko izločimo pomensko šibke besede, ki se zelo pogosto pojavljajo v dokumentih in jih določimo s seznamom blokiranih besed (npr. vezniki in števniki) in pomensko šibke besede, ki jih določimo s pomočjo slovarja jezika (obdržimo npr. samo samostalnike besedne oblike). V sklopu te aktivnosti izločimo samodejno tudi izraze z zelo nizko frekvenco pojavljanja v bazi dokumentov, saj njihov delež pri preglednem opisu vsebine dokumentov ni pomemben (imajo nizko funkcionalno vrednost), obenem pa s tem precej zmanjšamo dimenzije matrike izrazov in dokumentov. Frekvenčni prag je odvisen tudi od tega, koliko dokumentov je v bazi in koliko specifičnih izrazov želimo vstaviti v hierarhično strukturo. Obdržati i m izrazom nato priredimo frekvence, s katerimi nastopajo v določenem dokumentu. Po predhodni aktivnosti lahko izraze tudi krnimo, torej izluščimo korene izrazov z odstranjevanjem predpon in predvsem pripon. Študija uporabe krnje-nja v angleščini (kjer se večinoma uporablja Porterjev algoritem [Porter, 80; Porler, 01]) ni pokazala, da bi leto pri pridobivanju informacij prispevalo k natančnosti [Frakes, 92). Nedvomno ima krnjenje večji pomen za morfološko kompleksne jezike, kol je slovenščina. Temu primerno so kompleksni tudi algoritmi, ki se lotevajo krnjenja v teh jezikih [Popovič, 91; Dimec, 99]. V naši raziskavi krnjenja nismo uporabili, menimo pa, da velja pri aplikaciji metode za določen jezik razmisliti o njegovi uporabi. Uteževanje izrazov priredi elementu n{) v matriki izrazov in dokumentov A določeno vrednost. Vrednost je odvisna od pomena izraza i za dokument j (temu faktorju pravimo lokalna utež) in pomena izraza i za celotno bazo dokumentov (faktor imenujemo globalna utež). Obstaja več načinov za računanje lokalnih in globalnih uteži, ki so bili razviti empirično Dokumenti (naslovi prispevkov) Dl: CAFE: A Conceptual Model for Managing Information in Electronic Mail D2: Agent-based approach for information gathering D3: Dunhuang Frescoes retrieval based on si mi tari ty calculation D4: Information Retrieval on the Web D5: The Retrieval of Document Images: A Brief Survey D6: Survey: Introduction to Content-Based Image Retrieval 07: Graph Visualization and Navigation in Information Visualization: A Survey D8: Flo or p Ian generation and area optimization using AND-ÛR graph search D9: Visual programming with graph rewriting systems D10: A graph grammar approach to graphical parsing Dl D2 D3 D4 DS D6 D7 D8 D9 D10 1. cafe.conceptual .model. managing.electronie, mail 1 0 0 0 0 0 0 0 0 0 2. information 0,5 0,5 0 0,5 0 0 0,5 0 0 0 3. agent-based .gathering 0 1 0 0 0 0 0 0 0 0 4, approach 0 0,7 a 0 0 0 0 0 0 0,7 5. dunhuang, frescoes, based.simiiarity.calculat ion 0 0 l 0 0 0 0 0 0 0 6. retrieval 0 0 0,5 0,5 0,5 0.5 0 0 0 0 7, web 0 0 0 1 0 0 0 0 0 0 8. document, i mages 0 0 0 0 1 0 0 0 0 0 9. survey 0 0 0 0 0.6 0.6 0,6 0 0 0 10, Introduction, content-based,image 0 0 0 0 0 1 0 0 0 0 11. graph 0 0 0 0 0 0 0,5 0,5 0,5 0.5 12. visualization, navigation 0 0 0 0 0 0 1 0 0 0 13. floorplan,generation,area,optimization.and-or,search 0 0 0 0 0 0 0 1 0 0 14. visual, p rogra m m ¡ ng, row ri t i ng. syste m s 0 0 0 0 0 0 0 0 1 0 15. gram mar,graphical, parsing 0 0 0 0 0 0 0 0 0 1 Tabela 1: Demonstracijski primer ■ matrika izrazov in dokumentov po prvem koraku 2002 ■ šlevilka 2 - letnik X i IJ«hjím«H N FO R M AT IKA Roheft r. Leskovar, Jözse/ Györftös, Ivan Rozman; Gradnja liicrarhiinc strukture konceptov \i nestrukturi ranih tekstovnih dokumentov in na podlagi teorije informacij [Kowalski, 971. V praksi izkazujeta večjo učinkovitost uporaba logaritemske uteži za lokalno utež in entropijske uteži za globalno utež IDumais, 91]. V našem primeru globalne uteži nismo uporabili, saj se vektorji izrazov v drugem koraku pri računanju matrike korelacij normalizirajo in se globalna utež, ki sorazmerno uteži komponente vektorjev izrazov, s tem izniči. Globalna utež, ki vključuje inverzno frekvenco izrazov za določen dokument [Yates, 99| in zato ne uteži vseh komponent vektorja izraza sorazmerno, pa je dajala na testih slabše rezultate, kot če globalne uteži nismo uporabili. Kot lokalno utež smo uporabili logaritemsko, torej za vse elemente v matriki A je a^logCtfy + J), pri čemer je tfy frekvenca pojavljanja izraza i v dokumentu j. S tem smo zmanjšali učinek večjih razlik pojavljanja izrazov v frekvencah, ker je za tvorjenje konceptov bolj pomembno, da neki izraz sodeluje v konceptu, kot to, kolikokrat sodeluje. Vektorje izrazov na koncu normaliziramo in združim» izraze, ki so predstavljeni z enakimi vektorji (imenujemo jih bratje, saj nastopajo v istih dokumentih z istimi frekvencami in za tovrstno samodejno obdelavo med njimi ni razlik). Rezultat prvega koraka na demonstracijskem primeru prikazuje tabela I. !z naslovov nad tabelo smo s pregledovalnikom izločili blokirane izraze s pomočjo seznama angleških blokiranih izrazov SMARI* ISMART], ki je nastal v okviru dolgoletnega projekta na univerzi Cornwell. Dimenzije začetne matrike A so bile 39 (izrazov) x 10 (dokumentov). Elemente matrike smo utežili z lokalno logaritemsko utežjo, vektorje izrazov normalizirali in združili brate. Tabela l prikazuje končno matriko A, ki je osnova za nadaljnje korake metode. 2. Računanje matrike korelativnosti izrazov V drugem koraku metode izračunamo korelacije (podobnost, soodvisnost) poljubnih dveh izrazov. Vse korelacije predstavimo v matriki korelacij C Korelacije dobimo z računanjem kosinusa kota wlf med vektorji vseh izrazov i in j, i o j. Kosinus kota nam pove, kako blizu so vektorji izrazov oziroma koliko sodelujejo pri opisu vsebine dokumentov. Ker so vektorji normalizirani, je računanje kosinusa enako množenju vektorjev: čokat,, =(«/A)(i4r«y), (I) za i,j= \,..,,in, ej je enotski vektor dimenzije /t; m predstavlja št. izrazov, tt predstavlja št. dokumentov. Če je vrednost produkta blizu 1, pomeni, da sta vektorja izrazov skoraj vzporedna oziroma da sta izraza na podoben način zastopana v vsebini množice dokumentov. Matrika C je simetrična, na diagonalo postavimo ničle. Algoritem za računanje matrike C je v splošnem reda 0(m n/2), vendar ga lahko v našem primeru pospešimo, ker so vektorji izrazov v matrikah izrazov in dokumentov /1 redki. Pri običajnih dimenzijah matrike A, to je nad nekaj tisoč izrazov in nad nekaj sto ali tisoč dokumentov, je v povprečju 99 odstotkov elementov enakih 0 [Berry, 92). Redkost ne nastopa v obliki pravilnih vzorcev, lahko pa jo izkoristimo za pospešitev algoritmov za računanje z matrikami ]Ber-ry, 991. Prvi korak metode za gradnjo hierarhične strukture konceptov je običajen korak pri metodah pridobivanja informacij. Drugi je običajen v primerih, ko želimo grupirati izraze po podobnosti. Naslednji koraki so izvirni in specifični za metodo, ki je predmet tega prispevka. 3. Računanje globalnih korelacijskih stopenj in iskanju korenov hierarhij Elementi Cg matrike korelacij C izražajo podobnost parov izrazov i in j. Da bi 1 ali ko ugotovili, kako so posamezni izrazi korelativni z vsemi izrazi v množici dokumentov, smo uvedli tudi globalno korelacijsko stopnjo Gkst za vsak izraz i: I "' m predstavlja število izrazov; A", predstavlja Število izrazov, s katerimi je korelativen izraz i. Globalna koretacijska stopnja,izračunana po enačbi 2, je dajala najustreznejše empirične rezultate, kar je potrdilo intuitivno pričakovanje, daje najustrezneje upoštevati enakomeren vpliv razmerja med številom korelacij izraza i in št. vseh izrazov ter povprečne višine korelacij za izraz i. Izvedli smo tudi teste, pri katerih smo prišteli h Ghj globalno entropijsko utež izraza i, ki smo jo omenili v prvem koraku, saj se v prejšnjih korakih metode ni mogla postati opazna. Vendar se je pokazalo, da njen vpliv ni dovolj velik (ali dovolj različen od že Upoštevanih sumandov), da bi spremenil izbor korenov hierarhij ali izboljšal njihovo gradnjo. Po izračunu vseh Gks, ki jih uredimo po velikosti od najvišje do najnižje, lahko določimo korene hierarhij po naslednjem postopku: ■ prvi koren postane izraz z najvišjo Gks, m vsak naslednji koren postane izraz z nižjo Gks, ki je /. dosedaj izbranimi koreni korelativen nižje ud korenskega praga Kp (ali z drugimi besedami; kosinus kola med kandidatom za koren in dosedanjimi koreni mora biti nižji od K/i). Za določitev korenskega praga K p so se pokazale kot najbolj uporabne vrednosti med 0,2 in 0,5, za večino upomb, INFORMATIKA 2002 številka2-letnikX Robert F, Lesfcovar, Jozsef Gyijrftos, Ivan Rozman: Gradnja hierarhične strukture konceptov iz nesrru k turi ranih tekstovnih dokumentov primerov lahko vzamemo Vrednost 0,3. Višja vrednost vodi k več korenom, ki so večinoma močneje zastopani v konceptih hierarhij, nižja vrednost pa k manj korenom, od katerih so nekateri šibkeje zastopani (zaradi nizke Giis). Če želimo minimizirati število hierarhij, lahko določimo prag samodejno, z računanjem korenov na določenem intervalu in izborom praga, pri katerem je njihovo število minimalno. Na opisani način izberemo za korene izraze, ki nastopajo večinoma v različnih konceptih in so najbolj zastopani v ustrezni hierarhiji. Korene lahko določi tudi uporabnik, npr. na podlagi seznama izrazov, ki so urejeni po višini Gfcs. Ko jih izbere, se lahko določijo po zgornjem postopku samodejno Se drugi koreni, da bodo v hierarhični strukturi zajeti vsi koncepti v dokumentih, Rezultate drugega in tretjega koraka metode, uporabljene na demonstracijskem primeru, prikazuje tabela 2. V prvem stolpcu so globalne korelacijske stopnje (Gfcs) izrazov 1 do 15 (indeksi izrazov iz tabele ]}, v drugem stolpen so izrazi, ki so bili izbrani kot koreni pri pragu 0,3. Gks Koreni 1. 0,1 9. 0,592 2. information (0,743) 2. 0,743 10. 0,205 11. graph (0,659) 3. 0,214 11. 0,659 9. survey (0,592) 4. 0,408 12. 0.305 5. dunhuang, fnescocs, based, similarity, calculation (0,1) 5. 0.1 13. 0,1 6. 0,588 14. 0,1 7. 0,2 15. 0,214 8. 0.205 Tabela 2: Demonstracijski primer - globalne korelacijske stopnje in izbrani koreni Štirje koreni določajo štiri ločene hierarhije, znotraj katerih bodo umeščeni koncepti iz dokumentov. Četrti koren z nizko Gka, je bil izbran kot koren zato, ker je z vsemi prejšnjimi korelativen nižje od praga Kp in bi lahko manjkal v celotni hierarhični strukturi koncept, v katerem se nahaja, če bi ga izpustili. 4. Gradnja hierarhične strukture Hierarhična struktura konceptov, ki jo zgradi metoda iz vsebine baze dokumentov, je sestavljena iz več drevesnih hierarhij, katerih korene smo določili v prejšnjem koraku. Gradnja vsake hierarhije poteka ločeno in po nivojih. Preden začnemo z gradnjo, pripravimo za vsak izraz; korelacijske sezname /Cs.-, to je sezname izrazov, ki so z njim korelativni. Sezname uredimo v padajočem redu po njihovi globalni korelacijski stopnji. S tem pospešimo gradnjo konceptov v hierarhiji, sicer bi ob iskanju otrok določenega izraza (prvi korak algoritma, ki je opisan v tem razdelku) iskali vsakič kandidata z maksimalno Gks. Začnemo z uvrstitvijo korenskega izraza v hierarhijo. Ta je skupen vsem konceptom znotraj te hierarhije. Gradnja konceptov se nato nadaljuje po nivojih do listov - izrazov, ki nimajo otrok, kar pomeni, da ni več v okviru določenega koncepta korelativen z njimi noben drug izraz. Vsak otrok v hierarhiji ima le enega starša. Otroci določenega starša se uvrščajo v hierarhijo po višini Gks, najprej tisti z višjo stopnjo. Koncepti so tako predstavljeni v drevesni hierarhiji kot vr> ncciklične poti od korena do lista. Sledi postopek gradnje konceptov po nivojih: Najprej vstavimo na prvi nivo vsake hierarhije indeks izraza, ki je njen koren, in mu dodamo množico indeksov dokumentov, v katerih nastopa {to so indeksi neničelnih elementov v njegovi vrstici matrike A). Množico indeksov dokumentov, ki so prirejeni indeksu izraza j v okviru določenega koncepta, imenujemo v nadaljevanju 'dokumenti izraza j'. Dokumenti se prenašajo navzdol do listov, s čimer zagotavljamo, da so izrazi (otroci) na nižjih nivojih vsebovani v istih konceptih kot njihovi starši. Koncepte nato gradimo po nivojih. Izrazu /, ki se že nahaja v hierarhiji na nivoju I, dodamo otroke, ki nastopajo v okviru istega koncepta ali več konceptov, iterativno po naslednjih fazah: I. Preverimo, ali obstaja v korelacijskem seznamu Ks: kandidat za njegovega otroka. Če ne obstaja, preverimo, ali je izraz j list, kar pomeni, da v okviru tega koncepta noben izraz iz K?, ni mogel postali otrok Če ni list, odstranimo iz njegovih doku me n-tov tiste, v katerih so vsebovani tudi njegovi otroci, da niso vsem izrazom v konceptu prirejeni dokumenti, ampak le listom. V obeh primerih označimo, da je izraz j v okviru tega koncepta zadnji - komponente vrstice j, ki ustrezajo njegovim dokumentom, v matriki A postavimo na 0 in končamo z gradnjo koncepta, Z ažuriranjem matrike A preprečimo, da bi se koncepti ali deli konceptov v hierarhiji po nepotrebnem ponavljali. II. Vzamemo naslednjega kandidata za otroka iz seznama Ksr Pri njem preverimo: a. ali nastopa v okviru koncepta, ki ga gradimo -torej ali se pojavlja v dokumentih izraza j. Če se ne, začnemo ponovno s fazo I. b. ali se nahaja med predniki tega izraza. Če se nahaja, začnemo ponovno s fazo 1. c. ali nastopa v enakem konceptu, kot kateri od že dodanih otrok svojega starša - torej ali je korelativen s katerim od njih. Če je, je smiselno, da ga 2002- Številka 2-letnik X apuTjibtifA NFORM&TIKA Rohert r. Lestovar, Jnzsef Ciy6rk6$, Ivan Rozman: Gradnja hierarhične strukture konceptov iz neslrukturi ranih tekstovnih dokumentov uvrstimo pod njega, zato ga ne dodamo pod izraz/ S tem zagotovimo celovitost konceptov. Če je iz korelacijskih seznamov takšnega otroka in izraza, ki ga dodajamo, bila izbrisana njuna relacija v katerem od prejšnjih konceptov, jo povrnemo, da ga bomo lahko kasneje res uvrstili pod njega, m. Izraz, ki je postal otrok, postavimo na nivo /+1 in ga povežemo z iKrazom j. Dodamo mu pod-množico dokumentov izraza /, v katerih nastopa v okviru tega koncepta, in zbrišemo otroka iz kore-lacijskega seznama izraza j ter izraz j iz kore-ladjskega seznama otroka, da se ne ponovi njuna relacija (lahko jo povrnemo v fazi II). Slika 1 prikazuje diagram opisanega algoritma za gradnjo konceptov. Na sliki 2 je predstavljen rezultat tega koraka metode, uporabljene na demonstracijskem primeru. Hierarhije so zgrajene in oštevilčene pri korenskih izrazih. Pri izrazih na nižjem nivoju so navedene v okroglih oklepajih njihove globalne ko relacijske stopnje. Pri listih se nahajajo v koničastih oklepajih seznami indeksov dokumentov. Koncept, ki ga tvorijo izrazi od lista do korena, nastopa v vseh teh dokumentih. 4. Razširitve metode v smeri večje učinkovitosti, neodvisne od jezika 4.1 Uporaba analize glavnih komponent Pri pridobivanju informacij na osnovi vektorskega prostora se pogosto uporablja metoda za analizo glavnih Slika 1: Algoritem gradnje konceptov «^»«(jihi INFORMATIKA - vstavljanje otrok izraza j, ki se nahaja na nivoju I določene hierarhije 2002 - številka 2 - letnik X Rohea T. Leskovar, Jdtsef Gyork6s, Ivan Rozman: Gradnja hierarhične strukture konceptov iz nestruktunranih tekstovnih dokumentov Š 1. Iriforniation H _Jaraph(659) r-i survey<592) ♦ visuallzallon.navigation(305)«D7> - „J raljieval(588) « web(20fli*D4 ■ Si j approach(408) • aDent-tiassd.3atMering(213)'D2» » t ate, c o n c a plual ,m od e t,m a p a g Ing, e leurc n It. m al l(i 00)■ Ltj _J 2. graph S approacri{4C8tS ■ • gramrriar.(jr3phical.par$lng(2) 3)*D10> « iloarplan.genGratlon.area^pBmiiation.and-or.searefiitOOJ^DB^ * visual.progfsmfnipg, re/iTi !i n j ,system s (10 0) «D9» S „13. sutvev 3 ..j relrieval(i38) • documenl,lrnages(205)*D5» • IMro du cHcn, c o nterrt- bos ed,lm agi) na A - UZVT, lahko sedaj preoblikujemo, saj ni potrebno po razcepu izračunati aproksimirane matrike Ak, da dobimo vektorje izrazov, ampak je dovolj, da izračunamo 2^1// (dimenzij k x m). Ce definiramo uj^ZJI^ej (j= 1,..,,«), lahko enačbo 2 zapišemo kot: Wtwj IHN' Če se pojavijo po razcepu matrike A zaradi aproksimacije novi bratje {izrazi, katerih korekcija je 1), jih združimo, tako kol smo lo naredili že v prvem koraku. Razvite so bile hitre iterativne metode za izračun RSV, ki so prilagojene tudi redkim matrikam, kot sta Arnoldi-jeva (I,ehouctj, 96] in Lanczos-eva [Parlett, 80], s katerimi se osnovna časovna in prostorska zahtevnost razcepa (0{/»>72) za polno matriko) precej zmanjša (manj kot 0{»ur)). Testi so pokazali, da z večjo aproksimacijo matrike A izgubljamo poleg Šuma tudi natančnost korelacij, zaradi česar se vzpostavlja med izrazi vse več bratov in postajajo koncepti vse bolj sploščeni. Prednost uporabe RSV v gradnji hierarhične strukture konceptov je, da se združujejo koncepti, ki vsebujejo veliko skupnih izrazov, s čimer dosežemo manjšo občutljivost za variacije v rabi besed in za sinonime, kar je tudi sicer splošna značilnost RSV, znana iz pridobivanja informacij. Težava pri uporabi te metode je, da se ne da vnaprej določiti optimalnega ran ga aproksimirane matrike, ampak se to počne empirično. V pomoč so nam lahko raziskave, ki so v praksi [Berry, 951 in s statistično analizo [Ding, 99] pokazale, da je optimalni rang, v katerem se ohrani večina pomembne vsebinske strukture dokumentov, okrog 100 do največ 300. kjer je II ortogorialna matrika dimenzij m \ m, katere stolpci so levi singularni vektorji A, V je ortogo-nalna matrika dimenzij ji x h, katere stolpci so desni singularni vektorji A in £je matrika dimenzij nt x /r, katere diagonalni elementi so singularne vrednosti A, urejene od najvišje do najnižje. Po razcepu lahko odrežemo k najnižjih singularnih vrednosti, s čimer aproksimiramo matriko A z matriko Ak {rečemo tudi, da zmanjšamo rang matrike na k). Ak, izračunana z RSV, velja za optimalno aproksimacijo ranga k matrike A [Eckarl, 36; Stevvart, 00], Zaradi lastnosti metode RSV smo želeli ovrednotiti njen vpliv tudi v okviru naše metode, torej ugotoviti, kako bi RSV vplival na strukturo in povezavo konceptov. Razcep uporabimo v našem kontekstu na matriki A takoj po prvem koraku metode za gradnjo hierarhične strukture. Enačbo 1, po kateri smo v drugem koraku računali korelacije med vektorji izrazov, Eil „j H J 1 inforniaiion 9 JgrapH(707) i S sutvev(6DS) • vituai isatlon, n avig ali o r (S 8 /) * D 7 > S „j mineva 1(625) ......♦ web(434) -! approach(424) • agent-based.gHlheringHI 2)*D2* • caf9lccnceptuai,mo(i0l>mana3tng,elsctronir.,mail(417>vD1» e; _J2 uraph • Yi$ual,programmirg.rewriiing,sys1amstS03)«D9' - J approach(4?4) • grammar,graphical,patsing(J11)*[>!{l» * floorptar.gBneraliur,area,opt[mization.and-or,search{318)*P8» Š . j 3 rehlevat B . 1 survey(808) » inlroduction.corileril-basi'{j,imaga(D90)