| Popis: |
U svetu u kome živimo, internet i digitalni zapis učinili su da ogromne količine sirovih podataka postanu dostupne širokoj javnosti. Jedan američki menadžer je još davno izjavio: "Računari su nam obećali fontanu mudrosti, a ovo što smo dobili je poplava podataka" [20]. Sirovi podaci, neadekvatno strukturirani i različitih formata, sadržaja i kvaliteta su retko od koristi. Neophodno ih je pripremiti, analizirati i na osnovu toga doći do informacija i znanja koja na taj način stiču neprocenjivu vrednost. Istraživanje podataka (eng. data mining) je interdisciplinarno polje infor- matike koje se bavi automatskim ili polu-automatskim otkrivanjem znanja u podacima. Njegov osnovni zadatak je netrivijalna ekstrakcija informa- cija iz podataka, i to informacija koje su implicitne, prethodno nepoznate i potencijalno korisne. Koriste se metode koje su u preseku veštačke in- teligencije, mašinskog učenja, statistike i sistema baza podataka [97]. Zadaci koji se rešavaju u okviru Istraživanja podataka mogu biti prediktivni (klasi- fikacija, regresija, analiza vremenskih serija) ili deskriptivni (klasterovanje, sumarizacija, pravila pridruživanja, analiza redosleda, otkrivanje anomalija). U okviru ove doktorske disertacije bavimo se problemom klasifikacije tek- stova na osnovu njihovog sadržaja. Smatra se da je preko 80% dostupnih informacija sačuvano u tekstualnom obliku. Većina informacija je zapisana prirodnim jezikom, odnosno jezikom koji koriste ljudi za svakodnevnu ko- munikaciju. Za očekivati je da će tehnologije automatske obrade podataka zapisanih prirodnim jezikom postati vodeće u svetu. Glavni doprinos di- sertacije ogleda se u predstavljanju novih metoda za klasifikaciju tekstual- nih dokumenata. Prva metoda predstavlja unapredenje metode razvijene u cilju otkrivanja autorstva teksta [38]. Metoda je zasnovana na predstavlja- nju dokumenta kao profila koji sadrži fiksiran broj n-grama bajtova koji se pojavljuju u dokumentu, i meri različitosti pomoću koje se određuje klasa kojoj dokument pripada. Ova metoda je jezički nezavisna i ne zahteva nikakvu prethodnu obradu teksta niti predznanje o sadržaju teksta ili jeziku na kome je tekst napisan. Druga metoda se zasniva na odabranim koncep- tima kao predstavnicima klasa koji se dobijaju iz srpskog wordnet-a, leksičko semantičke mreže za srpski jezik. Deo rezultata iz ove disertacije je sadržan u radovima [23, 27, 22, 21, 56, 26, 25, 24] koji su objavljeni, predati za ob- javljivanje ili su u fazi pripreme. Disertacija je organizovana na sledeći način. U glavi 1 je prikazan uvod u oblast klasifikacije podataka, u okviru koga su prikazane vrste klasifikacije, procena kvaliteta klasifikacije i primeri primene. Poseban osvrt dat je na klasifikaciju tekstualnih dokumenata. Prikazani su različiti načini predstavljanja dokumenata kao jednog od najvažnijiih koraka u procesu klasifikacije. Predočeni su i mnogi problemi i izazovi koji se javlja- ju. Prikazani su korpusi klasifikovanih tekstova na srpskom, engleskom, ki- neskom i arapskom jeziku koji će biti korišćeni u daljem istraživanju. Uvodna glava završava se jednim filozofskim pogledom na proces klasifikacije. Glava 2 daje pregled postojećih leksičkih resursa za srpski jezik [17] koji se razvijaju u okviru Grupe za jezičke tehnologije na Matematičkom fakul- tetu Univeziteta u Beogradu. Ideja je da se uključivanjem morfoloških, sin- taksičkih i semantičkih informacija sadržanih u resursima unapredi proces klasifikacije tekstova na srpkom jeziku, kao jednom od morfološki bogatijih jezika. Predstavljeni su korpusi srpskog jezika, elektronski rečnik i srpski wordnet kao i raznovrsne tehnologije koje se koriste za njihovu obradu a koje se razvijaju u okviru Grupe. U glavi 3 su prikazane postojeće metode mašinskog učenja koje su do sada imale veoma uspešnu primenu u procesu klasifikacije. Prikazane su metode zasnovane na drvetima odlučivanja, metode zasnovane na pravilima i rastojanju, statistički zasnovane metode, metode zasnovane na neuronskim mrežama i metode zasnovane na podržavajućim vektorima. Nove metode za klasifikaciju teksta prikazane su u glavi 4. U okviru prve metode zasnovane na n-gramima bajtova, uvedeni su nova mera različitosti i novi težinski faktori u odnosu na osnovnu varijantu metode. Težinski faktori su dodeljeni n-gramima u okviru profila klasa, reflektujući značaj koji n-grami imaju za pripadajuću klasu. Smatra se da n-grami koji imaju veću frekvenciju a pripadaju manjem broju klasa imaju veći znaˇcaj za klasu kojoj pripadaju. Uvodenje ovih težinskih faktora rezultovalo je modifikacijom metode na dva načina: modifikacija na nivou mere različitosti i modifikacija na nivou profila klase. Druga metoda se odnosi na korišćenje informacija sadržanih u srpskom wordnetu i srpskom elektronskom rečniku u cilju klasifikacije teksta na srp- skom jeziku. Ova metoda zasniva se na pridruživanju odabranih koncepata iz srpskog wordnet-a klasama, na osnovu kojih se izračunava mera pripadnosti klasi i vrši pridruživanje dokumenta nekoj od klasa. Rezultati prikazanih novih metoda sumirani su u okviru glave 5. Na srp- skom korpusu je prikazano poredenje prve metode i njenih modifikacija zas- novanih na n-gramima bajtova, karaktera i reči. Osnovna varijanta metode i njene modifikacije za n-grame bajtova, testirani su na korpusima na srpskom, engleskom, kineskom i arapskom jeziku, čime je demonstrirana jezička neza- visnost metode. U okviru Priloga 1 dodatno su predstavljeni svi rezultati dobijeni testiranjem metode za različite vrednosti parametara, za sve pred- stavljene mere različitosti, na svim pomenutim korpusima. Druga metoda testirana je samo na korpusu na srpskom jeziku. Poredenje prikazanih rezultata sa drugim rezultataima iz ove oblasti dato je u glavi 6 a glava 7 prikazuje zaključke i pravce daljeg rada. We live in a world where the Internet and digital recording have made available huge amounts of raw data to the public. A frustrated manage- ment information systems executive a long time ago said: "Computers have promised us a fountain of wisdom but delivered a flood of data" [20]. Docu- ments in their textual semi-structured data formats (or raw data), with dif- ferent content and quality are rarely useful. It is necessary to prepare these raw data for analysis, to transform them into information and to transform information into invaluable knowledge. Data mining, also known as knowledge-discovery in databases, is an in- terdisciplinary subfield of computer science which task is the automatic or semi-automatic analysis of large quantities of data to extract previously un- known interesting patterns. It can be defined as nontrivial extraction of implicit, previously unknown, and potentially useful information from data. The methods used are at the juncture of artificial intelligence, machine learn- ing, statistics, database systems and business intelligence [97]. In general, data mining tasks can be classified into two categories: predictive (classifica- tion, regression, and times series) and descriptive (clustering, summarization, association rules, sequence analysis, anomaly detection). This dissertation deals with the problem of automatic and semi-automatic content-based classification of natural language text documents. The main contribution of this thesis is development of new methods for text categoriza- tion. The first method is an improvement of Keˇselj’s method [38] to solving authorship attribution problem. The approach relies on a profile representa- tion of restricted size of both document and a category, and a simple algo- rithm for comparing profiles. It is language independent and does not require any morphological analysis of texts, any preprocessing steps, or any prior in- formation about document content or language. The second method is based on well-chosen concepts from lexical-semantic network Serbian wordnet, as- signed to the corresponding categories. Parts from this dissertation have been described in papers [23, 27, 22, 21, 56, 26, 25, 24], that are published or submitted for publication in several journals and conference proceedings, or they are in preparation phase. The dissertation is organized as follows: Section 1 presents an overview of some basic concepts related to classifi- cation in general. The different types of classification of data, performance measures for assessing the quality of classification models and some exam- ples of application are presented. The choice of document representation has a profound impact on the quality of the classifier so different types of the text document representation are described as well as many problems and challenges that arise. The different document collections in English (Reuters- 21578 and 20-Newsgroups), Chinese (Tancorp-12), Arabic (Mesleh-10) and Serbian (Ebart-3) that will be used for text classification are also presented. This section ends with a philosophical view of the classification process. Lexical resources for Serbian [17] that have been developed within the Hu- man Language Technologies Group at the Faculty of Mathematics, University of Belgrade are described in Section 2. They contain integrated morphologi- cal, syntactic and semantic information that can be used to improve classifi- cation accuracy of text documents in Serbian, one of the morphologically rich languages. This section describes the Serbian language corpora, system of electronic morphological dictionaries of Serbian and the lexical-semantic net- work, the Serbian wordnet, as well as the various natural language processing tools. Section 3 provides a comprehensive coverage of the most important ma- chine learning techniques used for classification task, and their application in this domain. Decision Tree methods, Distance- and Rule-based methods, Statistical methods, Neural Networks and Support Vector Machine methods are described. New classification methods are presented in Section 4. In the case of the n-gram based method, a new n-gram weighting factors scheme is introduced. Weighting factors, which are associated with n-grams in category profiles, reflect importance of n-grams for the corresponding category with respect to other categories. In this way, n-gram with higher frequency that belongs to a smaller number of categories has a greater significance for the corresponding category. This was resulting in a two new variants of basic method: first based on modification of dissimilarity measures and second based on modifi- cation of category profiles. The second method is based on sets of well-chosen concepts from the Serbian wordnet, assigned to the corresponding categories. Each set includes literals from chosen concepts, and literals from all other concepts that are in syntactic or semantic relationship with chosen concepts. Category assignment function is defined for an test document as the maxi- mum number of occurrences of all literals associated to the set of the chosen concepts assigned to the category, maybe filtered by domains. Section 5 reports on experimental results of presented new classification methods. On Serbian corpus, comparison of the new variants of n-gram based method with the basic method using byte-, character-, and word-level n-grams, is presented. Only for byte-level n-grams, basic method and its modifications are tested on English, Chinese, and Arabic document collec- tions, thus demonstrating, at the same time, language-independence of the technique. Appendix 1 additionally presents experimental results obtain by basic n-gram method and its modifications, for all datasets and all dissim- ilarity measures. Method based on the Serbian wordnet is tested only on Serbian corpus. A comparison of the results obtained by the methods presented in this dissertation with results of other classification methods is given in Section 6. Section 7 concludes the dissertation with some discussion of the potential significance of obtained results and some directions for future work. |
