Прилог методама класификације текста : математички модели и примене
Contribution to text categorization methods : mathematical models and applications
Doktorand
Graovac, Jelena B.Mentor
Pavlović-Lažetić, GordanaČlanovi komisije
Vitas, DuškoObradović, Ivan
Metapodaci
Prikaz svih podataka o disertacijiSažetak
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 podata...ka 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.