Univerza v Ljubljani
Fakulteta za raˇ cunalniˇ stvo in informatiko
Mitja Brezovnik
Samodejno prepoznavanje vsebinskih blokov znotraj spletiˇ sˇ c
DIPLOMSKO DELO
UNIVERZITETNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE
RA ˇCUNALNIˇSTVO IN INFORMATIKA
Mentor : doc. dr. Slavko ˇ Zitnik
Ljubljana, 2021
tatov diplomske naloge je potrebno pisno privoljenje avtorja, fakultete ter mentorja.
Besedilo je oblikovano z urejevalnikom besedil LATEX.
Kandidat: Mitja Brezovnik
Naslov: Samodejno prepoznavanje vsebinskih blokov znotraj spletiˇsˇc Vrsta naloge: Diplomska naloga na univerzitetnem programu prve stopnje Raˇcunalniˇstvo in informatika
Mentor: doc. dr. Slavko ˇZitnik
Opis:
Prepoznavanje vsebinskih blokov na spletnih straneh sluˇzi k boljˇsemu zajema- nju vsebin in omogoˇca natanˇcnejˇso nadaljno obdelavo podatkov. Kandidat naj pregleda moˇznosti za identifikacijo razliˇcnih tipov vsebinskih blokov na spletnih straneh. Pregleda naj tehnologije in odprtokodne knjiˇznice, ki so na voljo v ta namen. Na podlagi pregleda naj prilagodi obstojeˇce pristope, jih uporabi nad izbranimi slovenskimi spletiˇsˇci in ovrednoti njihovo uspeˇsnost.
Na tem mestu bi se rad zahvalil mentorju doc. dr. Slavku ˇZitniku za pomoˇc in strokovno usmerjanje tekom izdelave diplomske naloge. Zahvala gre tudi moji druˇzini, ki mi je stala ob strani skozi celoten ˇstudij, ter prijateljem za nepozabne trenutke.
Kazalo
Povzetek Abstract
1 Uvod 1
2 Pregled tehnologij 5
2.1 Pristopi luˇsˇcenja podatkov . . . 5
2.1.1 Vizualni pristop . . . 5
2.1.2 N-grami . . . 7
2.1.3 Reˇsitve specifiˇcne za doloˇcene spletne strani . . . 8
2.1.4 Znaˇcilnosti plitkih besedil . . . 8
2.2 Obstojeˇce reˇsitve . . . 11
2.2.1 Goose . . . 11
2.2.2 Readability . . . 12
2.2.3 jusText . . . 13
2.2.4 Trafilatura . . . 14
2.2.5 Boilerpipe . . . 14
3 Implementacija lastne reˇsitve 19 3.1 Problematika . . . 19
3.2 Korpus in zajem spletnih strani . . . 20
3.3 Slovenski jezikovni model . . . 21
3.4 Prikaz delovanja . . . 25
4.2 Nadzorovano uˇcenje . . . 32
4.3 K-kratno preˇcno preverjanje . . . 33
4.4 Meritve vrednotenja modelov strojnega uˇcenja . . . 34
4.5 Primerjava reˇsitev . . . 37
5 Zakljuˇcek 43
Literatura 45
Seznam uporabljenih kratic
kratica angleˇsko slovensko
CSV Comma Separated Values Vrednosti, loˇcene z vejico JSON JavaScript Object Notation Notacija Objektov JavaScript WEKA Waikato Environment for
Knowledge Analysis
Waikato okolje za analizo zna- nja
XML eXtensible Markup Language Razˇsirljiv oznaˇcevalni jezik MCC Matthews correlation coeffici-
ent
Korelacijski koeficient Mat- thewa
HTML Hyper Text Markup Language Hipertekstovni oznaˇcevalni je- zik
URL Uniform Resource Locator Enoliˇcno kazalo virov
DOM Document Object Model Dokumentni objektni model ARFF Attribute Relation File For-
mat
Relacije atributov kot oblika dokumenta
SVM Support vector machine Metoda podpornih vektorjev VIPS VIsion-based Page Segmenta-
tion
Segmentacija strani na osnovi vida
Povzetek
Naslov: Samodejno prepoznavanje vsebinskih blokov znotraj spletiˇsˇc Avtor: Mitja Brezovnik
Informacije so dandanes enostavno dostopne, informiranost pa kljuˇcnega po- mena. S to mislijo smo se lotili izdelave reˇsitve, ki bo omogoˇcala luˇsˇcenje vse- bine ˇclankov iz slovenskih noviˇcarskih portalov. Glavni problem s katerim se pri tovrstnih reˇsitvah sooˇcimo je loˇcitev vsebine od nepotrebnih informacij, kot so oglasi, komentarji in ostali postavitveni elementi spletnih strani. Za reˇsitev tega problema smo ubrali pristop, ki temelji na znaˇcilnostih plitkih besedil. Na njegovi osnovi smo zasnovali jezikovni model, ki smo ga zgra- dili s pomoˇcjo slovenskega korpusa 10000 slovenskih ˇclankov iz 5 razliˇcnih noviˇcarskih portalov. Konˇcni izdelek predstavlja ekstraktor, ki omogoˇca pri- dobitev vsebine slovenskih ˇclankov in jih predstavi v strukturirani obliki.
Kljuˇcne besede: ekstrakcija, ˇclanki, znaˇcilnosti plitkih besedil.
Abstract
Title: Automatic identification of content blocks from Web sites Author: Mitja Brezovnik
Nowadays information is easily accessible and even more so valuable. With this in mind, we set about creating a solution that will enable content extrac- tion of articles found in Slovenian news portals. The main problem we face with such solutions is separating the content from unnecessary information, such as ads, comments and other layout elements of web pages. To solve this problem, we implemented a solution based on shallow text features. On its basis, we designed a language model, which was built with the help of Slove- nian news corpus that contains 10000 articles from 5 different news portals.
The final product is an extractor that allows content extraction of Slovenian articles and presents them in a structured form.
Keywords: extraction, articles, shallow text features.
Poglavje 1 Uvod
Za veliko ljudi glavni vir informacij predstavljajo razliˇcni portali novic do- stopni preko interneta. Ti so zasnovani tako, da ciljnega bralca ˇcimbolj pritegnejo. Poleg vsebine ˇclankov so takˇsne strani zasute z raznoraznimi informacijami, ki niso nujno povezane s ˇclankom. Tu pridejo v upoˇstev in- formacije v glavi in nogi spletne strani, oglasi, komentarji, tudi ankete pa ˇse kaj bi se naˇslo.
Tu se pojavi potreba po ˇcistosti informacij. Bodisi ˇzelimo ˇcisto vsebino ˇclanka za nemoteno branje brez distrakcij, bodisi za namene arhiviranja ali pa za obdelovanje podatkov in njihovo analizo. V te namene so bile imple- mentirane razliˇcne knjiˇznice in orodja za luˇsˇcenje vsebine. A kot se zdi, se te reˇsitve nekoliko slabˇse obnesejo na slovenskih noviˇcarskih portalih. Razlog tiˇci v mogoˇce nekoliko drugaˇcni strukturi portalov ali pa v samem jeziku, saj je velika veˇcina reˇsitev zgrajena na osnovi angleˇskih ˇclankov in angleˇskega je- zika. Zaradi tega smo se odloˇcili implementirati namensko reˇsitev za luˇsˇcenje slovenskih ˇclankov. Cilj te diplomske naloge je torej narediti ekstraktor, ki bo znal loˇcevati med vsebino ˇclanka in ˇsumnimi podatki ter vsebino uspeˇsno izvozil. Za ˇsumni podatek smatramo vso neˇzeleno informacijo, ki za vsebino ˇclanka ni pomembna (sem spadajo oglasi, navigacija spletne strani, komen- tarji, postavitveni elementi ipd.). Glej sliko 1.1. Za vhod bo lahko sprejel preneˇseno HTML datoteko spletne strani ali pa kar njen URL. Izhod pa bo
1
predstavljal vsebino ˇclanka prikazano v tekstovni datoteki ali pa v struktu- rirani obliki JSON datoteke.
Slika 1.1: Primer postavitve spletne strani [16]
Diplomska naloga 3 V naslednjih poglavjih si bomo na zaˇcetku pogledali razliˇcne tehnike luˇsˇcenja podatkov, ki se dandanes uporabljajo. Sledil bo pregled obstojeˇcih reˇsitev luˇsˇcenja ˇclankov. Tu si bomo podrobneje ogledali eno izmed njih, saj nam bo sluˇzila kot osnova za naˇso implementacijo. Nato vam bomo pred- stavili postopek implementacije naˇse reˇsitve in njeno delovanje. V poglavju evalvacije nas ˇcaka analiza podatkov s katerimi smo delali, ogledali si bomo tehnike strojnega uˇcenja, ki smo jih uporabili, na koncu pa bomo uspeˇsnost naˇse reˇsitve ˇse potestirali. Nenazadnje pa bomo opravljeno delo zavili v celoto in povzeli ugotovitve.
Poglavje 2
Pregled tehnologij
V prvem delu tega poglavja si bomo ogledali razliˇcne pristope, ki jih lahko uporabimo da pridobimo podatke s spletiˇsˇc. Povzeli bomo samo osnovne principe posameznih pristopov, na koncu pa nekoliko podrobneje opisali pri- stop, ki smo ga uporabili mi za izdelavo reˇsitve. Med sabo se razlikuejo po izbranih znaˇcilnosti na osnovi katerih luˇsˇcijo podatke in uporabljenih algorit- mih. Ker pa teh ni malo, se bomo osredotoˇcili na tiste ki so najbolj poznani in jih na grobo opisali. V naslednjem delu tega poglavja pa si bomo ogledali nekaj ˇze obstojeˇcih reˇsitev, ki so lahko v obliki aplikacij, knjiˇznic ali celo vmesnikov na brskalniku.
2.1 Pristopi luˇ sˇ cenja podatkov
2.1.1 Vizualni pristop
Temeljni koncept vizualnega pristopa je v upoˇstevanju vizualnih lastnosti spletnih strani za namen pridobivanja podatkov. Glavna prednost uporabe vizualnih znaˇcilnosti spletnih strani za pridobivanje podatkov je v tem, da se ne zanaˇsajo direktno na HTML strukturo spletne strani kot veˇcina ostalih pristopov. Pri odloˇcanju ali element predstavlja vsebino ali ne se v gro- bem zanaˇsajo na dve lastnosti. Prva lastnost je postavitev spletne strani, pri ˇcemer si pomagajo s koordinatnim sistemom. Druga uporabna lastnost
5
pa je stil pisave. Tu pride v upoˇstev velikost pisave, barva, obroba pisave, ali so ˇcrke preˇcrtane, podˇcrtane, leˇzeˇce, krepke ipd. Za pridobitev vizualnih podatkov se uporabljajo razliˇcne tehnike, ena izmed njih je uporaba VIPS al- goritma. Delovanje in uporabo VIPS algoritma smo nato preuˇcili [13] in [18].
VIPS pretvori spletno stran v drevo vizualnih blokov. Koren drevesa pred- stavlja celotno spletno stran, vsa nadalnja vozliˇsˇca pa pravokotne segmente strani. Listi drevesa pa so bloki, ki jih ne moremo segmentirati dalje, kot so na primer zvezen tekst in slike. Pretvorbo spletne strani na vizualne bloke predstavlja slika 2.2 sestavo drevesa pa slika 2.1. Te blokovne elemente dre- vesa nato ocenimo z vizualnimi znaˇcilkami, na podlagi katerih se odloˇcimo ali predstavljajo vsebino ali ne. Vizualne znaˇcilke so lahko:
poloˇzaj elementov - ta lastnost nam pove lokacijo podatkovnega obmoˇcja na spletni strani,
postavitev elementov - opredelijo, kako so podatkovni zapisi porazde- ljeni znotraj podatkovnega obmoˇcja,
vizualne karakteristike - povzamejo vizualne lastnosti ki jih nosijo po- datkovni zapisi znotraj podatkovnega obmoˇcja,
vsebina - s tem ocenimo pravilnost vsebine v podatkovnih zapisih.
Slika 2.1: Sestava drevesa vizualnih blokov [13]
Diplomska naloga 7
Slika 2.2: Spletna stran segmentirana na vizualne bloke [13]
2.1.2 N-grami
Pregledali smo podroˇcje n-gramov [9]. Po definiciji je n-gram katerikoli niz sestavljen iz n tokenov (besed). Za primer, besedna zveza ”ˇcista de- setka”predstavlja 2-gram oz. bi-gram, ”noro vroˇce poletje”pa 3-gram. Pro- blema se lotimo na zadostno veliki mnoˇzici uˇcnih podatkov, kjer se klasificira vse moˇzne n-grame. Seveda to pomeni, da bolj obˇsirna uˇcna mnoˇzica pomeni veˇcjo uspeˇsnost. Ko se lotimo luˇsˇcnja podatkov, ciljno spletno stran razbi- jemo na n-grame. Nato pa se te n-grame na podlagi izraˇcunane verjetnosti klasificira kot ˇsumni podatek ali vsebino. Za raˇcunanje uporabimo verjetno- sti kot so, pogostost izrazov (angl. term frequency), pogostost dokumentov (angl. document frequency), inverzna pogostost dokumentov, informacijski prispevek, entropija ali pa uporabimo razliˇcne kombinacije med njimi. Iz- med bolj dovrˇsenih metod pa poznamo pristope, ki si pomagajo z uporabo
Rocchiovega modela, BM25 modela, SVM modela ali pa z razliˇcnimi pristopi vzorˇcnega rudarjenja (angl. pattern mining). Vredno je tudi omeniti, da po- navadi delamo z n-grami dolˇzine 2 ali 3, saj se izkaˇzejo za najbolj uˇcinkovite.
2.1.3 Reˇ sitve specifiˇ cne za doloˇ cene spletne strani
Ce se z luˇsˇˇ cenjem podatkov omejimo samo na doloˇcene strani, lahko naˇsa pravila njim bolje prilagodimo. Takˇsne reˇsitve so ponavadi manj robustne a v veˇcini primerov bolj natanˇcne za izbrane strani. Prvi primer je pristop luˇsˇcenja podatkov na podlagi pravil. Tukaj klasifikacijski model predsta- vlja mnoˇzico pravil, ta pravila pa so v obliki IF-THEN stavkov, ki jih lahko predstavimo tudi z odloˇcitvenim drevesom. ˇCe toˇcno vemo kako so podatki predstavljeni na strani, potem je sestava pravil dokaj trivialna. Ciljno sple- tno stran lahko pretvorimo v DOM drevo. S pomoˇcjo ogleda vira strani ugotovimo, kateri deli spletne strani so nam zanimivi in tako ugotovimo na katerem delu DOM drevesa se nahajajo. Vse kar nam ostane je, da podatke izluˇsˇcimo.
2.1.4 Znaˇ cilnosti plitkih besedil
Znaˇcilnosti plitkih besedil (angl. shallow text features) je pristop, ki so ga v ˇstudiji definirali Christian Kohlsch¨utter in dr.[12]. Avtorji te publikacije so napisali tudi Boilerpipe knjiˇznico, ki sluˇzi kot osnova za naˇso implementacijo reˇsitve. Preden si ogledamo glavne znaˇcilnosti tega pristopa pa na hitro omenimo ˇze znane znaˇcilnosti spletnih strani, ki pripomorejo k uspeˇsnosti te reˇsitve.
Pomagamo si z globalno informacijo imenovano referenˇcna znaˇcilnost, ki nam pove pogostost besedila v celotnem korpusu. S to znaˇcilnostjo lahko identificiramo pogosto uporabljene fraze ˇsumnih podatkov. Najbolj oˇciten primer je gradnja nabora ustavitvenih besed (angl. stop words), ki nam pove da vse informacije dalje ne predstavljajo pomembne vsebine.
Medtem ko veliko metod klasifikacije besedila ali pa segmentacije spletnih
Diplomska naloga 9 strani uporablja ˇsirok nabor strukturnih znaˇcilnosti spletnih strani, se tukaj temu ˇzelimo v veliki meri izogniti. Med strukturne znaˇcilnosti spletnih strani spadajo HTML oznake (naslov, slika, odstavek, oblikovne karakteristike be- sed, hiperpovezave, ipd.), DOM drevesa pa tudi razredi in stili znotraj CSS dokumentov. Izognemo se jim, ker ne ˇzelimo dobiti znaˇcilnosti specifiˇcne za doloˇcena spletna mesta, ki bi nam pokvarile podatke. Prav tako pa se s tem izognemo dragim obdelavam nad spletnimi stranmi. Edine strukturne znaˇcilnosti ki se uporabijo, so oznake naslovov (H1, H2, H3, H4, H5, H6), ozanka odstavka (P), loˇcitvena oznaka (DIV) in oznaka hiperpovezave (A).
Uporabimo jih kot HTML elemente ki zapirajo tekstovne bloke v celoto.
Konˇcno pridemo do ˇze omenjenih znaˇcilnosti plitkih besedil. Tu se do- taknemo znaˇcilnosti, ki se uporabljajo na podroˇcju kvantitativne lingvisitke (angl. quantitative linguistic). V upoˇstev pridejo lastnosti: povpreˇcna dolˇzina besed, povpreˇcna dolˇzina stavka (tukaj je stavek definiran z enostavno hevri- stiko na podlagi vzorca, kot sklop besed zakljuˇcen s piko, klicajem, vpraˇsajem ali podpiˇcjem) in absolutno ˇstevilo besed. Pri klasifikaciji si pomagamo tudi z intra-dokumentnimi znaˇcilnostmi. Tukaj upoˇstevamo absolutni in rela- tivni poloˇzaj tekstovnega bloka v dokumentu. Razdrobljenost segmentacije je tukaj velika, kar pomeni da zelo verjetno vsebini sledi vsebina in da po ˇsumnemu podatku sledi nov ˇsumni podatek. V primerih kjer imamo velike koliˇcine ˇsumnih podatkov, je vsebina ponavadi z njimi obdana z vseh strani (glava, noga, navigacije na levi in desni strani, oglasni okvirji, ipd.) in tako nam poloˇzaj blokov doda veliko informacijske vrednosti. Poleg znaˇcilnosti trenutnega bloka pa zajamemo tudi znaˇcilnosti blokov njegovih neposre- dnih sosedov. Nenazdanje pa v ta sklop spadajo tudi slednje hevristiˇcne znaˇcilnosti:
Absolutno ˇstevilo besed, ki se zaˇcnejo z veliko zaˇcetnico, ali pa so v celoti napisane z veliko zaˇcetnico.
Razmerje besed iz zgornje toˇcke v primerjavi s skupnim ˇstevilom besed.
Razmerje pik (loˇcilo na koncu stavka) v primerjavi s skupnim ˇstevilom
besed.
ˇStevilo tokenov, ki se nanaˇsajo na datum in ˇcas.
ˇStevilo navpiˇcnih ˇcrt ”|”(ti znaki se pogosteje nahajajo v ˇsumnih po- datkih).
gostota linkov (angl. link density ali anchor percentage), ki pred- stavlja ˇstevilo tokenov (znakov) znotraj HTML oznake A, deljeno s skupnim ˇstevilom tokenov v bloku.
Zadnji sklop uporabljenih znaˇcilnosti pa so tako imenovane denzitome- triˇcne znaˇcilnosti (angl. densinometric features). Glavna lastnost na ka- tero se tu osredotoˇcimo je tekstovna gostota (angl. text density), ki jo izraˇcunamo za vsak blok posebaj. Tekstovna gostota ρ(b) se ˇze uporablja za segmentacijo spletnih strani in pri zdruˇzevalni strategiji spajanja blokov (angl. Block Fusion). Tukaj so sosednji tekstovni bloki podobnih teksovnih gostot (beri kot ”podobnih razredov”) iterativno spojeni, dokler ni gostota sosednjih blokov dovolj razliˇcna da jih lahko nedvoumno loˇcimo. Izkaˇze se da je takˇsna strategija zelo podobna roˇcni segmentaciji.
Znaˇcilnost tekstovne gostote izhaja iz raˇcunalniˇskega vizualnega pristopa doloˇcanja tekstovne gostote na osnovi pikslov in je bila nato preneˇsena ˇse na podoben problem na ravni znakov. Za njen izraˇcun, preˇstejemo ˇstevilo tokenov |T(b)| znotraj doloˇcenega tekstovnega bloka b, ki jih nato delimo s ˇstevilom vrsticL(b), po tem ko besedilo v bloku ovijemo/razdelimo glede na fiksno ˇsirino stolpca wmax. Ker pa lahko ima zadnja vrstica v bloku manjˇso dolˇzino kot wmax, to vrstico pri izraˇcunu izpustimo, razen ˇce gre za edino vrstico v segmentu.
T0(b) ={t|t ∈T(l), lf irst(b)≤l < llast(b)}
ρ(b) =
|T0(b)|
|L(b)|−1, |L(b)|>1
|T(b)|, drugaˇce
Diplomska naloga 11
2.2 Obstojeˇ ce reˇ sitve
2.2.1 Goose
Goose [4] je odprtokodna knjiˇznica za programski jezik Java, ki je bila ka- sneje v okviru projekta pretvorjena v Scala programski jezik. Leta 2012 je bil projekt ukinjen a je ˇcez nekaj let pridobil na zanimanju, kar je privedlo da je bila knjiˇznica v celoti prepisana ˇse v drug programski jezik, Python. V takˇsni obliki se uporablja ˇse zdaj, obstaja pa tudi kot samostojna aplikacija.
Za vhodni parameter sprejema samo url naslov ˇzelene spletne strani, ne pa tudi html datoteke. Pri ekstrakciji podatkov poizkuˇsa izluˇsˇciti glavno vsebino spletne strani, najpomembnejˇso sliko ˇclanka, YouTube ali Vimeo vsebine, ˇce se le te nahajajo na strani, meta opise in meta znaˇcke. Gre za jezikovno neodvisno knjiˇznico, kar pomeni da izluˇsˇci tudi vse jezikovno odvisne meta znaˇcke. Prav tako pa omogoˇca luˇsˇcenje ˇclankov zapisanih v nekoliko zahtev- nejˇsih jezikih, kot so kitajˇsˇcina, arabˇsˇcina, korejˇsˇcina ipd. pri tem pa moramo samo uporabiti ustrezen razred z ustavitvenimi besedami (npr. StopWord- sChinese za kitajski jezik). Za slovenske portale ta podpora ˇse ne obstaja.
Primer uporabe iz ukaznega pozivnika vidimo na sliki 2.3.
C :\ U s e r s \ Mitja > p y t h o n
P y t h o n 3 . 8 . 3 ( t a g s / v3 . 8 . 3 : 6 f8c832 , May 13 2020 , 2 2 : 3 7 : 0 2 ) [ MSC v . 1 9 2 4 64 bit ( A M D 6 4 ) ] on w i n 3 2 T y p e " h e l p " , " c o p y r i g h t " , " c r e d i t s " or " l i c e n s e " for m o r e i n f o r m a t i o n .
> > > f r o m g o o s e 3 i m p o r t G o o s e
> > > url = 'h t t p s :// www . d n e v n i k . si / 1 0 4 2 9 4 6 7 4 3'
> > > g = G o o s e ()
> > > a r t i c l e = g . e x t r a c t ( url = url )
> > > a r t i c l e . t i t l e
'V UKC L j u b l j a n a se p r i p r a v l j a j o na t r e t j i val'
> > > a r t i c l e . m e t a _ d e s c r i p t i o n
'UKC L j u b l j a n a te dni p e s t i ve ˇc kot 50 - o d s t o t n i p o r a s t p r i h o d o v v u r g e n t n o i n t e r n i s t i ˇc no a m b u l a n t o , z a r a d i ˇc e s a r so m o r a l i bolniki , ve ˇc i n o m a s t a r e j ˇs i , na p r e g l e d e ˇc a k a t i c e l o po o s e m ur .'
> > > a r t i c l e . c l e a n e d _ t e x t [ : 1 0 0 0 ]
'Ob tem se v UKC p r i p r a v l j a j o na t r e t j i val e p i d e m i j e . G e n e r a l n i d i r e k t o r z a v o d a J a n e z P o k l u k a r meni , da bi m o r a l i z a r a d i p o m a n j k a n j a o s e b j a k a d r e s p o d r o ˇc ja z d r a v s t v e n e n e g e r a c i o n a l i z i r a t i o z i r o m a p r e r a z p o r e d i t i . " Ta t r e n u t e k i m a m o po S l o v e n i j i p r i b l i ˇz no 850 m e d i c i n s k i h s e s t e r v r e f e r e n ˇc nih a m b u l a n t a h , c e n t r i h za k r e p i t e v zdravja , v z d r a v s t v e n o v z g o j n e m d e l u in n e k a t e r i h d r u g i h d e l o v i ˇs ˇc ih , ki ta t r e n u t e k , ko je k l j u ˇc no re ˇs e v a n j e ˇz ivljenj , m o r d a n i s o n a j b o l j p o t r e b n a ," je d e j a l v i z j a v i za
j a v n o s t . Kot so ˇs e p o j a s n i l i v UKC , je v e l i k p o r a s t p r i h o d o v v u r g e n t n o i n t e r n i s t i ˇc no a m b u l a n t o obi ˇ
c a j n a p o s l e d i c a n o v o l e t n i h p r a z n i k o v , t o d a l e t o s je b i l o p r e c e j h u j e kot obi ˇc a j n o . K ve ˇc j e m u p r i l i v u so p o l e g z i m s k e g a ˇc asa in r e s p i r a t o r n i h oku ˇz b p r i s p e v a l i z l a s t i z a p l e t i pri b o l n i k i h , ki so c o v i d ˇz e p r e b o l e l i , in ve ˇc n a p o t i t e v iz d o m o v za s t a r e j ˇs e .'
Slika 2.3: Primer ekstrakcije ˇclanka s knjiˇznico Goose
2.2.2 Readability
Originalno je bil Readability [6] odprtokodni Javascript bookmarklet. Zaradi svoje uspeˇsnosti je bil prepisan v raznorazne programske jezike, obstajajo pa tudi verzije razˇsiritev v brskalnikih Mozzila in Google Chrome. Originalni algoritem je bil pretvorjen v samostojen Readability produkt, ki se sedaj uporablja v produktih kot so Safari Reader, Flipboard pa tudi Treesaver. Za vhod lahko algoritmu podamo samo url naslov ali pa kar html kodo strani, nato pa imamo na voljo nastavitve kako in katere podatke ˇzelimo izluˇsˇciti.
Podatki se nahajajo v Article objektu, znotraj katerega lahko dostopamo do podatkov kot so content, title, textBody, html, document in meta object.
Ne omogoˇca pa ekstrakcijo slik iz spletnih strani, za kar obstaja reˇsitev v obliki modula Newspaper3k ki to funkcionalnost nato omogoˇca. Slika 2.4 predstavlja primer uporabe v programsekm jeziku Javascript.
var read = require('node-readability');
read('https://www.24ur.com/novice/fokus/madzarska-orbanov-rezim.html', function(err, article, meta) {
// Title
console.log(article.title);
// Main Article
console.log(article.content);
// HTML Source Code console.log(article.html);
// DOM
console.log(article.document);
article.close();
});
Slika 2.4: Primer ekstrakcije ˇclanka iz portala 24ur s knjiˇznico Readability
Diplomska naloga 13
2.2.3 jusText
JusText [5] je orodje napisano v Pythonu uporabljeno za ekstrakcijo vse- bine iz spletnih strani. Trenutno nima veˇc podpore originalnih avtorjev te knjiˇznice, je pa bilo to orodje implementirano v raznorazne ostale program- ske jezike. Gre za precej bolj preprosto razliˇcico v primerjavi z ostalimi opisanimi. Deluje po principu hard-coded hevristike, zato tudi rezultati niso najbolj nataˇcni. Na primer, do napak pride ˇce strani/ˇclanki vsebujejo veliko koliˇcino ˇsumnih podatkov kot so oglasi sredi glavnega besedila ali komentarji pod ˇclanki. Kot nam ˇze samo ime orodja pove, ne omogoˇca ekstrakcijo slik in drugih multimedijskih vsebin. Knjiˇznice, kot so: Chirp, Lazynlp, Pears, Re- adability Calculator, Sky, uporabljajo jusText kot pomoˇc pri delu s podatki.
Pri svojem delovanju je na momente dokaj omejen, na primer s portala 24ur nam ni uspelo preneti nobene vsebine ˇclanka, zato kot primer prikazan na sliki 2.5 prilagamo izluˇsˇceno vsebino ˇclanka s portala Dnevnik.
Slika 2.5: Primer ekstrakcije ˇclanka z orodjem justText preko spletne demo verzije [2]
2.2.4 Trafilatura
Trafilatura [7] je ˇse eno izmed orodij s katerim si lahko pomagamo pri luˇsˇcenju podatkov s spleta. Lahko ga uporabljamo v obliki knjiˇznice v programskem jeziku Python ali R ali pa kar direktno preko orodja ukaznega pozivnika.
Deluje na osnovi knjiˇznice LXML, za zagotavljanje varnosti pa si v primeru nepravilne ekstakcije pomaga s knjiˇznicama Readability in jusText. Omogoˇca ekstrakcijo razliˇcnih oblik podatkov, med njimi se lahko osredotoˇcimo samo na ekstrakcijo slik ali tabel. Rezultat lahko predstavi v obliki navadnega besedilnega dokumenta ali pa kot JSON, XML ali CSV dokument. Med naˇstetimi reˇsitvami je najbrˇz pod najbolj aktivnim razvojem. Primer upo- rabe vidimo na sliki 2.6
C :\ U s e r s \ Mitja > p y t h o n
P y t h o n 3 . 8 . 3 ( t a g s / v3 . 8 . 3 : 6 f8c832 , May 13 2020 , 2 2 : 3 7 : 0 2 ) [ MSC v . 1 9 2 4 64 bit ( A M D 6 4 ) ] on w i n 3 2 T y p e " h e l p " , " c o p y r i g h t " , " c r e d i t s " or " l i c e n s e " for m o r e i n f o r m a t i o n .
> > > i m p o r t t r a f i l a t u r a
> > > d o w n l o a d e d = t r a f i l a t u r a . f e t c h _ u r l ('h t t p s :// www .24 ur . com / p o p i n / f i l m _ t v / po - koncu - serije - b i r m i n g h a m s k e - tolpe - prihaja - se - f i l m . html')
> > > t r a f i l a t u r a . e x t r a c t ( d o w n l o a d e d )
'T e l e v i z i j s k a s e r i j a B i r m i n g h a m s k e t o l p e ( P e a k y B l i n d e r s ) s l e d i k r i m i n a l n i dru ˇz ini Shelby , g l a v n o v l o g o T o m m y j a S h e l b y j a pa i g r a C i l l i a n M u r p h y . D o g a j a n j e se za ˇc ne t a k o j po p r v i s v e t o v n i vojni , ko se T o m m y S h e l b y v r n e s f r o n t e v d o m a ˇc i B i r m i n g h a m , k j e r p r e v z a m e v o d e n j e t o l p e z i m e n o m P e a k y B l i n d e r s .\ nV p o n e d e l j e k je s i c e r K n i g h t obo ˇz e v a l c e s e r i j e o p o z o r i l , da se b o d o n j e n i j u n a k i v ˇs e s t i s e z o n i soo ˇc ili z e k s t r e m n o n e v a r n o s t j o . Re ˇz ijo bo p o n o v n o p r e v z e l A n t h o n y B y r n e .\ n K n i g h t je s i c e r v p r e t e k l o s t i n a p o v e d a l , da bo s e r i j a i m e l a s e d e m d e l o v . BBC je spomnil , da je l e t a 2 0 1 8 p r e d p e t o s e z o n o dejal , da je v s e r i j i ˇz e l e l p r e d s t a v i t i ˇz i v l j e n j e dru ˇz ine med v e l i k i m a v o j n a m a in jo s k l e n i t i
z z v o k o m sirene , ki je v B i r m i n g h a m u n a z n a n i l a za ˇc e t e k d r u g e s v e t o v n e v o j n e l e t a 1 9 3 9 . A t e d a j se mu je zdelo , da bo za to p o t r e b o v a l v s a j ˇs e tri sezone , kot ka ˇz e zdaj , pa bo n a m e s t o s e d m e s e z o n e u s t v a r i l f i l m .'
Slika 2.6: Primer ekstrakcije ˇclanka z orodjem Trafilatura
2.2.5 Boilerpipe
Tej knjiˇznici bomo namenili nekoliko veˇc pozornosti in o njej povedali kakˇsno stvar veˇc, saj nam sluˇzi kot osnova za implementacijo naˇse reˇsitve.
Boilerpipe [3] je odprtokodna knjiˇznica za programski jezik Java, pri- marno napisana pod okriljem L3S raziskovalnega centra, ˇcigar glavni avtor je Christian Kohlsch¨utter. Ekstrakcije se loti z uporabo znaˇcilnosti plitkih besedil, opisanih v pododstavku 2.1.4. Znotraj knjiˇznice najdemo kar nekaj
Diplomska naloga 15 razliˇcnih ekstraktorjev, vsak s svojimi znaˇcilnostmi. Od vseh sta najpomemb- nejˇsa in najbolj perspektivna ArticleExtractor in DefaultExtractor, ostali pa so bolj vzorˇcne narave. Spodaj so opisani vsi glavni ekstraktorji in njihova groba primerjava med sabo:
ArticleExtractor Kot ˇze samo ime pove je namenjen ekstrakciji podatkov spletnih ˇclankov. Zaradi svoje namenskosti se pri luˇsˇcenju novic ve- liko bolje odreˇze kot DefaultExtractor. Nam najbolj zanimiva verzija ekstraktorja, saj bomo zasnovali podoben model za slovenske ˇclanke.
DefaultExtractor Generiˇcen ekstraktor katerega prednost je veˇcnamenskost.
V veˇcini situacijah se odreˇze vredu a nikjer nima nadpovpreˇcne na- tanˇcnosti.
ArticleSentencesExtractor V tem primeru gre za ArticleExtractor zno- traj ArticleSentecesExtractorja, s to razliko, da se na koncu besedilo znotraj blokov razdeli po odstavkih za lepˇsi prikaz podatkov.
LargestContentExtractor Ekstraktor, ki vrne samo najveˇcjo tekstovno komponento na strani. Po spajanju sosednih blokov, obdrˇzi samo najveˇcji blok (najveˇcji po ˇstevilu besed). Ce ima veˇˇ c blokov enako dolˇzino, vzame prvega. Na spletnih ˇclankih se odreˇze bolje kot Defau- tExtractor in v veˇcini primerov slabˇse kot ArticleExtractor.
NumWordRulesExtractor Ekstraktor, ki temelji izkljuˇcno na klasifika- torju ˇstevila besed trenutnega in sosednjih blokov.
KeepEverythingExtractor Izluˇsˇci popolnoma vse informacije na strani, ne diskriminira med vsebino in nepotrebnimi informacijami.
Uporabili so 2 nabora podatkov. Prvi nabor so naredili sami in se imenuje L3S-GN1 dataset. Ta vsebuje 621 roˇcno ocenjenih ˇclankov iz 408 razliˇcnih spletnih strani. Te novice pa so bile nakljuˇcno pridobljene iz ˇse veˇcjega nabora 25,400 novic. Pridobili pa so jih s pajki, ki so se sprehodili skozi okoli 7,854 razliˇcnih spletnih straneh ki so jih dobili s spremljanjem Google
Novic. Spremljali so novice ˇsestih razliˇcnih angleˇsko govoreˇcih Google News portalov (ZDA, Kanada, Velika Britanija, Juˇzna Afrika, Indija, Avstralija) v ˇstirih razliˇcnih kategorijah (svet, tehnologija, ˇsport, zabava). Vsem 621 ˇclankom so roˇcno oznaˇcili v kater razred spada posamezen gradnik spletne strani (vsebina ali ˇsumni podatek).
Drugi nabor podatkov pa so vzeli iz CleanEval korpusa. Ta se upo- rablja za tako imenovane ”boilerplate removal”tekmovanja v ACL Web-as- Corpus skupnosti. Zbirka predstavlja 798 HTML strani ˇclankov, izvzetih iz nakljuˇcnega vzorca pridobljenega preko spletnih brskalnikov. Od teh je bilo 733 ˇze roˇcno pregledanih in oznaˇcenih, od tega 58 dokumentov predstavlja testno mnoˇzico.
Slika 2.7: Prikaz uspeˇsnosti 67 znaˇcilnosti, kjer viˇsji informacijski prispevek pomeni veˇcjo vrednost
Svoje rezultate so testirali s C4.8 drevesi, katere so uporabili tudi v fazi iz- biranja uporabnih znaˇcilnosti (angl. feature selection). Testirali so uspeˇsnost 67 znaˇcilnosti pri ˇcemer je bila enota uspeˇsnosti predstavljena z informacij- skim prispevkom (angl. information gain). Uspeˇsnost posameznih znaˇcilnosti lahko vidimo na sliki 2.7. Pri testiranju uspeˇsnosti so vkljuˇcili znaˇcilnosti
Diplomska naloga 17 prejˇsnjega (P) in naslednjega bloka (N), ter seveda trenutnega bloka (C).
Na podlagi teh ugotovitev so zasnovali klasifikatorje, ki jih uporabljajo zgo- raj omenjeni ekstraktorji. Ta informacija pa bo tudi nam osnova za izbiro znaˇcilnosti pri izdelavi slovenskega jezikovnega modela.
Uporaba knjiˇznice je zelo preprosta. Repozitorij si prenesemo na ciljno lokacijo na svojem raˇcunalniku, najbolje kar s programom za verzioniranje.
Poˇzenemo projekt, nato pa v svojem razredu samo kliˇcemo ekstraktor, ki ga ˇzelimo uporabiti, pri tem pa navedemo ˇse URL spletne strani katere vsebino ˇzelimo izluˇsˇciti. Na sliki 2.8 je zelo enostaven primer klica ArticleExtractor- ja, ki velja za najbolj univerzalnega in najboljˇsega v tej knjiˇznici. Rezultat je ˇcisto besedilo novice izpisano v ukaznem pozivniku 2.9.
public class Oneliner {
public static void main(final String[] args) throws Exception {
final URL url = new URL("https://www.24ur.com/novice/tujina/droni.html");
System.out.println(ArticleExtractor.INSTANCE.getText(url));
} }
Slika 2.8: Uporaba ArticleExtractorja
Opazimo lahko da so implementacijo in testiranje svoje reˇsitve zasnovali izkljuˇcno okoli ˇclankov angleˇsko govoreˇcih portalov. ˇZe iz tega razloga lahko sklepamo da kljub odliˇcni sploˇsni pokritosti ne morejo optimalno delovati na vseh noviˇcarskih portalih, ˇse posebej ne ˇce gre za drugojeziˇcne portale. Tu pridejo najbrˇz v upoˇstev tudi lingvistiˇcne karakteristike posameznega jezika, ki ne morejo biti sploˇsno zajete z znaˇcilnosmi predstavljenimi na sliki 2.7.
S tem imamo v mislih razliˇcne mejne vrednosti znaˇcilnosti glede na jezik ekstrakcije. To razmiˇsljanje naj nam sluˇzi kot povod za nadgradnjo reˇsitve na slovenski problem.
Nad n e z a k o n i t e m i g r a n t e in t i h o t a p c e z droni , p r o j e k t z a n i m a t u d i S l o v e n i j o Dunaj , 0 2 . 0 8 . 2 0 2 0 , 1 4 : 0 1 | P o s o d o b l j e n o p r e d 5 m e s e c i
icon - content - book -3 P R E D V I D E N ˇC AS B R A N J A : 1 min icon - u s e r
icon - l i n k
D o k l e r z u n a n j a m e j a EU ni n e p r o d u ˇs no zaprta , bo A v s t r i j a n a d z o r o v a l a s v o j o mejo , pri tem pa bo o k r e p i l a t e h n i ˇc na s r e d s t v a , pi ˇs e v v l a d n e m p r o g r a m u , ki ga r a z k r i v a k r o n e . at . A v s t r i j s k a p o l i t i k a je
n a m r e ˇc o d l o ˇc ena , da bo v a r n o s t s v o j e m e j e z a g o t o v i l a z d o d a t n i m i k o r a k i v s m e r i b o l j ˇs ega v a r o v a n j a . icon - e x p a n d
N e z a k o n i t e m i g r a c i j e so ˇs e n a p r e j v e l i k a te ˇz ava , t i h o t a p c i pa so z e l o i z n a j d l j i v i . F O T O : POP TV T r e n u t n o o k o l i c o m e j e n a d z o r u j e j o p r e d v s e m s p o m o ˇc jo t e r m o k a m e r , z d a j pa n a m e r a v a j o o k r e p i t i p r e d v s e m " v a r o v a n j e iz z r a k a " , p r a v i a v s t r i j s k i n o t r a n j i m i n i s t e r K a r l N e h a m m e r . C i l j je p r e d v s e m b o l j u s p e ˇs no s t o p i t i na p r s t e t i h o t a p c e m .
V z r a k u z d a j n a l o g e v a r o v a n j a a v s t r i j s k e m e j e o p r a v l j a h e l i k o p t e r , a to je drago , p r a v i j o pri s o s e d i h . V s a j del t e g a naj bi z d a j n a d o m e s t i l i s p r e c e j u ˇc i n k o v i t e j ˇs imi in c e n o v n o u g o d n e j ˇs imi d r o n i .
S k u p a j s p o d a t k i o l o k a c i j i naj bi d r o n i v r e a l n e m ˇc asu s l i k o p r e n a ˇs ali v n a d z o r n i center , n e z a k o n i t i p r e h o d i m e j e pa bi b i l i t a k o h i t r o z a z n a n i in o b r a v n a v a n i .
" V a r o v a n j e m e j e m o r a m o p o p e l j a t i v 21. s t o l e t j e ," je o d l o ˇc en m i n i s t e r .
Pri s o s e d i h n a m e r a v a j o n a j p r e j p o g n a t i p i l o t n i projekt , s k a t e r i m bi p r e v e r j a l i u ˇc i n k o v i t o s t n o v i h m e t o d in n j i h o v e p o m a n j k l j i v o s t i .
S l o v e n i j o in Mad ˇz a r s k o so o p i l o t n e m p r o g r a m u ˇz e o b v e s t i l i , p r a v i j o pri sosedih , in obe dr ˇz avi sta po m n e n j u m i n i s t r a za p r o j e k t " z e l o z a i n t e r e s i r a n i ". S l o v e n i j a je p o n u d i l a s o d e l o v a n j e pri p r o j e k t u ,
pravi , na ˇs e o b l a s t i naj bi z a n i m a l o t e s t i r a n j e d r o n o v na s l o v e n s k o - h r v a ˇs ki m e j i .
Slika 2.9: Rezultat luˇsˇcenja
Poglavje 3
Implementacija lastne reˇ sitve
3.1 Problematika
Cilj, ki smo si ga zadali na zaˇcetku izdelave naˇse reˇsitve je bil razˇsiriti Boiler- pipe knjiˇznico s slovenskim jezikovnim modelom. Z njim pa se bi osredotoˇcili na zajemanje ˇclankov iz slovenskih noviˇcarskih portalov. Glavni problem takˇsnega zajemanja podatkov je loˇciti vsebino od ˇsumnih podatkov, kar bomo skuˇsali v nadaljevanju doseˇci. V naˇsem primeru so ˇsumni podatki vse, kar ne predstavlja vsebine ˇclanka, kot so: komentarji, oglasi, razliˇcni gradniki spletne strani, skratka vse kar ni vsebina. Za Boilerpipe knjiˇznico pa smo se odloˇcili, ker predstavlja eno izmed najbolj natanˇcnih implementacij za tovrsten problem, v primerjavi s svojo konkurenco.
Problema smo se lotili, ker se obstojeˇce reˇsitve slabo odreˇzejo na sloven- skih noviˇcarskih portalih in je ekstrakcija slovenskih ˇclankov iz spleta slabˇse podprta. Del teˇzave je bil tudi v tem, da slovenski noviˇcarski portali ne sle- dijo istim HTML standardom kot reˇsitve, ki so svoje obnaˇsanje v veˇcji meri prilagodile angleˇskim portalom spletnih novic. Rezultat bo izdelek, ki bo iz dobljene vhodne spletne strani izluˇsˇcil vsebino ter slike in podatke pred- stavil v strukturirani JSON obliki. V naslednjih delih poglavja pa si bomo pogledali postopke, preko katerih smo priˇsli do konˇcnega izdelka.
19
3.2 Korpus in zajem spletnih strani
Za klasifikacijo elementov znotraj strani smo si pomagali s slovenskim korpu- som SentiNews 1.0 [11]. Sestavljen je iz 10427 ˇclankov, ki so bili objavljeni v razponu med 1. septembrom 2007 in 31. januarjem 2016. Izmed teh ˇclankov so roˇcno oznaˇcili 2103 ˇclanke iz portala 24ur, 2048 iz portala Dnevnik, 2000 ˇclankov je bilo oznaˇcenih iz Financ, iz portala RTV Slo so vzeli 2064 ˇclankov, ter 2212 ˇclankov je bilo oznaˇcenih za portal ˇZurnal24. Za vsak ˇclanek se je zapisalo njegov url naslov, naslov ˇclanka, kljuˇcne besede, vsebino, datum pu- blikacije in avtorja. Ti parametri nam bodo sluˇzili za klasifikacijo elementov v vsebino ali ˇsumni podatek.
V naslednjem koraku pa smo morali spletne strani iz zgoraj omenjenega korpusa prenesti na lokalen raˇcunalnik. Ker pa bi bilo takˇsno delo zamudno in redundantno smo napisali enostavno .bat skripto, ki se sprehodi ˇcez vse url naslove v korpusu in jih prenese. Pri tem pa smo si pomagali s programom Wget [1], ki omogoˇca enostavno pridobivanje spletnih virov. Primer ukaza, s katerim prenesemo eno spletno stran:
wget --no-parent --convert-links --page-requisites --no-directories --adjust-extension -w 2 --random-wait
--no-check-certificate -e robots=off --user-agent= "Mozilla/5.0
(X11; U; Linux i686; en-US; rv:1.8.1.6) Gecko/20070802 SeaMonkey/1.1.4"
--directory-prefix=1 http://www.dnevnik.si/posel/novice/266125
Uporabljene znaˇcke:
–no-parent: prenesemo samo to datoteko in ne tudi ostale viˇsje v hie- rarhiji
–convert-links: spremeni da vse povezane datoteke (kot so CSS, HTML, slike) kaˇzejo na lokalno datoteko
–page-requisites: pridobi vse podatke, potrebne za prikaz spletne strani (slike ipd.)
Diplomska naloga 21
–no-directories: ˇzelimo da so vse datoteke shranjene v eno mapo
–adjust-extension: shrani HTML/CSS datoteke s pravilno konˇcnico
-w 2 –random-wait: med poizvedbami se poˇcaka nakljuˇcen interval sekund v rangu [0.5·2, 1.5·2], s tem se izognemo preobremenjenosti ciljnega streˇznika
–no-check-certificate: ne validiraj streˇznikovega SSL certifikata
-e robots=off: ignoriramo robots.txt datoteko, ki ponavadi prepreˇcuje da bi s pajkom prenesli spletno stran
–user-agent: identificiramo se kot Firefox brskalnik namesto Wget, da se izognemo blokiranju s strani streˇznika
–directory-prefix=1: vse datoteke shranimo v mapo, v naˇsem primeru z imenom “1”
3.3 Slovenski jezikovni model
Ko smo naloˇzili vse potrebne spletne strani iz korpusa SentiNews 1.0, je bil naslednji korak priprava slovenskega jezikovnega modela. Ta nam bo sluˇzil kot glavni odloˇcitveni model pri klasifikaciji ˇse ne videnih podatkov slovenskih noviˇcarskih portalov. Prikaz korakov potrebnih za izdelavo le tega je prikazan na sliki 3.1 Posamezne zakljuˇcene celote dela so med sabo loˇcene z zaprtimi rumenimi okvirji.
V prvem delu je sledila izdelava uˇcne mnoˇzice (angl. learning set). Pri strojnem uˇcenju se podatke razdeli na uˇcno in testno mnoˇzico (angl. training set) pri ˇcemer mora biti uˇcna mnoˇzica izrazito veˇcja, da zajamemo ˇcim ˇsirˇsi nabor podatkov. S testno mnoˇzico pa se bomo sreˇcali v 4. poglavju, kjer bomo preizkusili uspeˇsnost naˇsega modela.
Mnoˇzico HTML spletnih strani poˇsljemo v Boilerpipe knjiˇznico preko katere vsako posamezno stran pretvorimo v TextDocument objekt. Ta pa je
Slika 3.1: Prikaz postopka izdelave slovenskega jezikovnega modela sestavljen iz mnoˇzice tekstovnih blokov TextBlock, ki predstavljajo najbolj osnoven gradnik spletne strani. Vsakemu tekstovnemu bloku izraˇcunamo lastnosti plitkih besedil opisanih v odstavku 2. Za laˇzjo predstavo glej sliko 3.2, kjer so zraven ˇse naˇstete glavne lastnosti objekta TextBlock. Te bodo igrale vlogo pri gradnji modela, nekatere pa bomo uporabili v prihodnje za izboljˇsanje hevristike.
Sledi delno avtomatska klasifikacija tekstovnih blokov, pri ˇcemer si po- magamo z omenjenim korpusom SentiNews 1.0. Naˇs razred [0, 1] bo oznaˇcil tekstovne bloke kot vsebino, ki jo bomo oznaˇcili z 1 ali ˇsumni podatek oznaˇcen z 0. Torej ˇce se besedilo bloka spletne strani popolnoma ujema z besedilom iz prileˇzne oznaˇcene datoteke iz korpusa, jo oznaˇcimo z 1, drugaˇce z 0. Ta postopek ponovimo za vse spletne strani v korpusu nato pa dobljene po- datke izvozimo v eno veliko CSV datoteko. V to datoteko shranimo samo
Diplomska naloga 23
Slika 3.2: Vsebina objekta TextDocument
klasificiran razred in mnoˇzico lastnosti (angl. feature set) vsakega bloka, ki nam bodo pripomogle pri uˇcenju naˇsega jezikovnega modela. Lastnosti so prikazane v tabeli 3.1.
ID Ime
1 prev num words
2 prev num words in anchor text 3 prev text density
4 prev link density
5 curr num words
6 curr num words in anchor text 7 curr text density
8 curr link density
9 next num words
10 next num words in anchor text 11 next text density
12 next link density
Tabela 3.1: Tabela lastnosti uˇcnih podatkov
Kot je razvidno nas za vsak blok zanimajo znaˇcilnosti plitkih besedil tre- nutnega bloka ter njegovih sosedov. V upoˇstev pridejo 4 glavne lastnosti, to so: ˇstevilo besed, ˇstevilo besed v hiperpovezavi (gre za besedilo v hiperpove- zavi ki ga lahko kliknemo, po spletnem standardu je prikazan kot podˇcrtano besedilo modre barve), gostota besedila in gostota linkov. Datoteka torej predstavlja mnoˇzico vrstic, pri ˇcimer vsaka vrstica vsebuje zgoraj naˇstete lastnosti in klasificiran razred bloka v obliki urejenih 13-teric.
Sledila je pretvorba dokumenta iz tipa CSV v ARFF, katero lahko sprejme WEKA [8] za nadaljnje delo s podatki. V datoteki se oznaˇci relacijo, v naˇsem primeru smo jo poimenovali kar SloPortali, sledi poimenovanje atributov in oznaˇcitev podatkov. Konˇcno obliko datoteke in prvih 10 vrstic podatkov lahko vidimo na sliki 3.3.
@ R E L A T I O N S l o P o r t a l i
@ A T T R I B U T E p r e v _ n u m _ w o r d s R E A L
@ A T T R I B U T E p r e v _ n u m _ w o r d s _ i n _ a n c h o r _ t e x t R E A L
@ A T T R I B U T E p r e v _ t e x t _ d e n s i t y R E A L
@ A T T R I B U T E p r e v _ l i n k _ d e n s i t R E A L
@ A T T R I B U T E c u r r _ n u m _ w o r d s R E A L
@ A T T R I B U T E c u r r _ n u m _ w o r d s _ i n _ a n c h o r _ t e x t R E A L
@ A T T R I B U T E c u r r _ t e x t _ d e n s i t y R E A L
@ A T T R I B U T E c u r r _ l i n k _ d e n s i t y R E A L
@ A T T R I B U T E n e x t _ n u m _ w o r d s R E A L
@ A T T R I B U T E n e x t _ n u m _ w o r d s _ i n _ a n c h o r _ t e x t R E A L
@ A T T R I B U T E n e x t _ t e x t _ d e n s i t y R E A L
@ A T T R I B U T E n e x t _ l i n k _ d e n s i t y R E A L
@ A T T R I B U T E c l a s s {0 ,1}
@ D A T A
0 ,0 ,0 ,0 ,10 ,10 ,10.0 ,1.0 ,0 ,0 ,0.0 ,0.0 ,0 10 ,10 ,10.0 ,1.0 ,0 ,0 ,0.0 ,0.0 ,2 ,0 ,2.0 ,0.0 ,0 0 ,0 ,0.0 ,0.0 ,2 ,0 ,2.0 ,0.0 ,1 ,0 ,1.0 ,0.0 ,0 2 ,0 ,2.0 ,0.0 ,1 ,0 ,1.0 ,0.0 ,2 ,2 ,2.0 ,1.0 ,0 1 ,0 ,1.0 ,0.0 ,2 ,2 ,2.0 ,1.0 ,2 ,2 ,2.0 ,1.0 ,0 2 ,2 ,2.0 ,1.0 ,2 ,2 ,2.0 ,1.0 ,1 ,0 ,1.0 ,0.0 ,0 2 ,2 ,2.0 ,1.0 ,1 ,0 ,1.0 ,0.0 ,1 ,1 ,1.0 ,1.0 ,0 1 ,0 ,1.0 ,0.0 ,1 ,1 ,1.0 ,1.0 ,1 ,1 ,1.0 ,1.0 ,0 1 ,1 ,1.0 ,1.0 ,1 ,1 ,1.0 ,1.0 ,1 ,1 ,1.0 ,1.0 ,0 1 ,1 ,1.0 ,1.0 ,1 ,1 ,1.0 ,1.0 ,1 ,1 ,1.0 ,1.0 ,0
Slika 3.3: ARFF datoteka
Diplomska naloga 25 V zadnjem koraku pa smo z uporabo WEKA orodja in pridobljenih po- datkov ustvarili odloˇcitveni model. Za to smo nad podatki izvedli tehniko 10-kratnega preˇcnega preverjanja in za metodo strojnega uˇcenja izbrali J48 odloˇcitvena drevesa. O tem bomo veˇc povedali v poglavju 4 kjer bomo po- datke tudi podrobneje analizirali. Odloˇcitveni model smo dobili v obliki odloˇcitvenega drevesa, katerega smo nato nekoliko porezali (angl. pruning) da smo izboljˇsali izvajanje na raˇcun skoraj zanemarljive izgube natanˇcnosti.
Nenazadnje pa smo to odloˇcitveno drevo implementirali v kodo, ki nam sedaj sluˇzi kot slovenski jezikovni model.
3.4 Prikaz delovanja
Za vhodni parameter v naˇso nadgrajeno knjiˇznico lahko sprejmemo url ciljne spletne strani ali pa pot do HTML datoteke spletne strani, ki je shranjena lokalno na naˇsem raˇcunalniku. Ta spletna stran se nato pretvori v objekt TextDocument in poˇslje v razred SloPortaliExtractor v obdelavo. Razred je viden na sliki 3.4.
V razredu se nad TextDocument objektom kliˇce SloPortaliModelClassi- fier, ki sluˇzi kot slovenski jezikovni model. V njem se zgodi klasifikacija spletne strani s katero pridobimo samo vsebino ki nas zanima. Ostali ra- zredi hevristike in filtrov pa nam sluˇzijo za izboljˇsanje natanˇcnosti klasifika- cije. Z njimi oznaˇcimo za ˇsumni podatek vse tiste TextBlocke, ki zagotovo ne predstavljajo vsebine. Na primer, ko najdemo blok s tekstom “sorodni ˇclanki:”, “komentarji:”, “preberite tudi” ipd., ta najverjetneje predstavlja konec ˇclanka in lahko njega in vse naslednje TextBlocke oznaˇcimo za ˇsumni podatek.
Na koncu pa dobljene podatke shranimo v navaden tekstovni dokument ali pa v JSON obliko za nadaljnjo obdelavo. V primeru da se odloˇcimo za izhod v obliki JSON datoteke, se SloPortaliExtractor izvede v kombinaciji z ˇze obstojeˇcim ImageExtractorjem, ki poskrbi da pridobimo tudi podatke o relevantnih slikah ˇclanka. Dobljene rezultate zapakiramo v bolj pregle-
dno strukturirano obliko. Slika 3.5 prikazuje izvorno spletno stran ˇclanka na portalu 24ur, slika 3.6 pa izluˇsˇceno vsebino predstavljeno v tekstovnem dokumentu. Za nemen prikaza rezultatov smo dokument roˇcno formatirali, da so na njem vidni vsi rezultati. Normalen izpis pa bi vsak odstavek ˇclanka prikazal v svoji vrstici. Na sliki 3.7 pa lahko vidimo iste izluˇsˇcene podatke predstavljene ˇse v JSON obliki.
public final class SloPortaliExtractor extends ExtractorBase {
public static final SloPortaliExtractor INSTANCE = new SloPortaliExtractor();
public static SloPortaliExtractor getInstance() { return INSTANCE;
}
public boolean process(TextDocument doc) throws BoilerpipeProcessingException { return
SloTerminatingBlocksFinder.INSTANCE.process(doc)
| new DocumentTitleMatchClassifier(doc.getTitle()).process(doc)
| SloPortaliModelClassifier.INSTANCE.process(doc)
| HeadingToContentFilter.INSTANCE.process(doc)
| IgnoreBlocksAfterContentFilter.DEFAULT_INSTANCE.process(doc)
| TrailingHeadlineToBoilerplateFilter.INSTANCE.process(doc)
| ExpandTitleToContentFilter.INSTANCE.process(doc)
; } }
Slika 3.4: SloPortaliExtractor razred
Diplomska naloga 27
Slika 3.5: ˇClanek iz portala 24ur [17]
Nov re ˇz im na m e j i : h i t r o t e s t i r a n j e na p e t i h p r e h o d i h in b r n i ˇs kem l e t a l i ˇs ˇc u
Od d a n e s bo na p e t i h m e j n i h p r e h o d i h s H r v a ˇs ko in b r n i ˇs kem l e t a l i ˇs ˇc u p o t e k a l o t e s t i r a n j e na n o v i k o r o n a v i r u s
s h i t r i m i a n t i g e n s k i m i t e s t i . P o l e g t e g a je od d a n e s na s e z n a m u i z j e m za v s t o p b r e z k a r a n t e n e ali n e g a t i v n e g a
t e s t a PCR pet novih , med n j i m i so ˇs p o r t n i k i , o t r o c i in p r i p a d n i k i n u j n i h slu ˇz b .
Dr ˇz a v l j a n o m t r e t j i h dr ˇz av na n e n u j n e m p o t o v a n j u , ki t e s t i r a n j a s h i t r i m t e s t o m ne b o d o ˇz e l e l i o p r a v i t i
ali b o d o p o z i t i v n i , b o d o v s t o p v dr ˇz avo z a v r n i l i . F O T O : A l j o ˇs a K r a v a n j a Od d a n e s l a h k o tisti , ki ˇz e l i j o ob p r i h o d u iz rde ˇc e dr ˇz ave v S l o v e n i j o v s t o p i t i na z u n a n j i s c h e n g e n s k i meji ,
pri ˇc e m e r ne b o d o p r e d l o ˇz ili n e g a t i v n e g a t e s t a PCR ali pa ˇc e ne s o d i j o med 12 izjem , v dr ˇz avo v s t o p i j o s a m o
na m e j n i h p r e h o d i h , k j e r so z a g o t o v l j e n i p o g o j i za t e s t i r a n j e s h i t r i m i t e s t i .
To so l e t a l i ˇs ˇc e Jo ˇz eta Pu ˇc n i k a ter m e j n i p r e h o d i s H r v a ˇs ko O b r e ˇz je , Gru ˇs kovje , Metlika , S r e d i ˇs ˇc e ob D r a v i in Jel ˇs ane .
Osebe , ki b o d o na t e s t i r a n j u na n o v i k o r o n a v i r u s n e g a t i v n e , b o d o l a h k o v s t o p i l e b r e z n a p o t i t v e v k a r a n t e n o na d o m u .
Dr ˇz a v l j a n o m t r e t j i h dr ˇz av na n e n u j n e m p o t o v a n j u , ki t e s t i r a n j a s h i t r i m t e s t o m ne b o d o ˇz e l e l i o p r a v i t i
ali b o d o p o z i t i v n i , b o d o v s t o p v dr ˇz avo z a v r n i l i . D r u g e osebe , ki se ne b o d o ˇz e l e l e t e s t i r a t i ali b o d o
p o z i t i v n e na n o v i k o r o n a v i r u s , pa b o d o m o r a l e v k a r a n t e n o na d o m u . V l a d a je ob tem raz ˇs i r i l a s e z n a m i z j e m za
v s t o p b r e z k a r a n t e n e ali n e g a t i v n e g a t e s t a PCR iz dr ˇz av na rde ˇc em s e z n a m u . Od d a n e s je d o v o l j e n i h 12 izjem , od t e g a pet n o v i h .
Med t e m i so otroci , ki ˇs e n i s o d o p o l n i l i 13 let in p o t u j e j o s k u p a j z o ˇz jim dru ˇz i n s k i m ˇc lanom , ki ni n a p o t e n v k a r a n t e n o
o z i r o m a mu ni z a v r n j e n v s t o p . I z j e m a so po n o v e m t u d i d o l o ˇc eni ˇs p o r t n i k i in ˇs p o r t n i d e l a v c i .
N o v a i z j e m a so ˇs e p r i p a d n i k i n u j n i h slu ˇz b , ki i z v a j a j o h u m a n i t a r n e p r e v o z e ali n u d i j o p o m o ˇc pri re ˇs e v a n j u in o d p r a v i p o s l e d i c n e s r e ˇc .
Slika 3.6: Izluˇsˇcena vsebina ˇclanka 24 ur, prikazana v TXT dokumentu
Diplomska naloga 29
{
"url": "https://www.24ur.com/novice/korona/meja.html",
"date_accessed": "2.1.2021",
"extracted_data": {
"title": "Nov reˇzim na meji: hitro testiranje na petih prehodih in brniˇskem ...",
"subtitle": "Od danes bo na petih mejnih prehodih s Hrvaˇsko in brniˇskem ...",
"content": "Od danes lahko tisti, ki ˇzelijo ob prihodu iz rdeˇce drˇzave v ...",
"images": [ {
"url": "https://images.24ur.com/media/images/1000xX/Feb2020/ ... .jpg?v=3556",
"alt": "Drˇzavljanom tretjih drˇzav na nenujnem potovanju, ki testiranja s ...", }
] } }
Slika 3.7: Izluˇsˇcena vsebina ˇclanka 24 ur, prikazana v JSON obliki
Poglavje 4 Evalvacija
V tem poglavju si bomo podrobneje pogledali uporabljene podatke za uˇcenje in testiranje jezikovnega modela. Sledil bo pregled uporabljenih tehnik nad- zorovanega uˇcenja in opis meritev za preverjanje uspeˇsnosti naˇse reˇsitve. Ne- nazadnje pa bomo naˇso reˇsitev, namenjeno slovenskim noviˇcarskim portalom primerjali z obstojeˇco reˇsitvijo znotraj Boilerpipe knjiˇznice.
4.1 Osnovna analiza podatkov
Podatke s katerimi smo delali, smo razdelili na dva dela in sicer na uˇcno in testno mnoˇzico. Uˇcno mnoˇzico smo opisali ˇze v podpoglavju 3.2 za katero smo si pri oznaˇcitvi podatkov pomagali s korpusom SentiNews 1.0. Te podatke smo uporabili za pripravo naˇsega slovenskega jezikovnega modela. Testno mnoˇzico pa smo sami roˇcno oznaˇcili. Sestavljena je iz 50 spletnih strani, po 5 ˇclankov iz 10 razliˇcnih slovenskih noviˇcarskih portalov. Uporabili smo ˇclanke iz portalov Slovenske Novice, Megafon, Dnevnik, 24ur, RTVSlo, Delo, Veˇcer, Zurnal24, Siol.net in Svet24. Testno mnoˇˇ zico smo uporabili pri preverjanju uspeˇsnosti naˇse reˇsitve in njeno primerjavo z ˇze obstojeˇcno reˇsitvijo.
Spletne strani smo razbili na tekstovne bloke in uporabili obetavne atri- bute. Naˇs problem je 2-razreden, kjer je vsebina oznaˇcena z razredom 1 in ˇsumni podatek z razredom 0. Porazdelitev razreda v uˇcni mnoˇzici lahko
31
vidimo v tabeli 4.1, porazdelitev v testni mnoˇzici pa v tabeli 4.2.
Stevilo zapisovˇ Odstotek Razred 0 (ˇsumni podatek) 1984160 96.79%
Razred 1 (vsebina) 65879 3.21%
Skupaj 2050039 100%
Tabela 4.1: Porazdelitev razreda v uˇcni mnoˇzici Stevilo zapisovˇ Odstotek Razred 0 (ˇsumni podatek) 14306 95.89%
Razred 1 (vsebina) 613 4.11%
Skupaj 14919 100%
Tabela 4.2: Porazdelitev razreda v testni mnoˇzici
4.2 Nadzorovano uˇ cenje
Nadzorovano uˇcenje je tehnika strojnega uˇcenja, kjer funkcijo uˇcimo z vna- prej pripravljenimi pari vhodov in izhodov. Ker imamo podane izhode, lahko bi rekli tudi reˇsitve, mora funkcija samo poiskati korake potrebne da iz vho- dnih podatkov pridemo do izhodnih. Rezultat uˇcenja nad uˇcno mnoˇzico je izpeljana funkcija oz. algoritem, ki lahko pravilno napove izhod na ˇse nevi- denih podatkih. Metod nadzorovanega uˇcenja je veliko, kar nas privede do naslednje toˇcke.
Za doloˇcitev naˇsega modela smo uporabili pristop odloˇcitvenih dreves.
Pristop uvrˇsˇcamo v tehniko simboliˇcnega induktivnega uˇcenja, katerega re- zultat je odloˇcitveno drevo. Drevo je sestavljeno iz notranjih vozliˇsˇc oz.
atributov, vej, ki predstavljajo vrednosti atributov v nekem odloˇcitvenem koraku in listov ki predstavljajo klasificiran razred [10]. Delimo jih na re- gresijska drevesa, kjer ima konˇcen razred zvezen atribut in na klasifikacijska drevesa, kjer je konˇcen razred diskreten atribut. V naˇsem primeru gre za bi- narno klasifikacijo, torej smo imeli opravka s klasifikacijskimi drevesi. Vsako
Diplomska naloga 33 drevo lahko pretvorimo v mnoˇzico odloˇcitvenih pravil, zaradi ˇcesar smo naˇso reˇsitev enostavno pretvorili v klasifikator znotraj kode.
Obstaja veliko razliˇcnih odloˇcitvenih dreves. Potrebovali smo takˇsnega, ki se dobro odreˇze z diskretnimi in kvantitativnimi atributi [15] zaradi ˇcesar smo za pomoˇc pri izdelavi naˇsega modela uporabili J48 odloˇcitveno drevo (tudi C4.5), ki je ˇze implementiran znotraj WEKE.
4.3 K-kratno preˇ cno preverjanje
V tej sekciji bomo na kratko opisali uporabljeno tehniko k-kratnega preˇcnega preverjanja (angl. k-fold cross-validation). Preden pa to storimo, je smiselno da razjasnemo porazdelitev naˇsega nabora podatkov, da se izognemo more- bitni dvoumnosti. Za laˇzjo predstavo si pomagajmo s priloˇzeno sliko 4.1.
Slika 4.1: Vizualizirana uˇcna, validacijska in testna mnoˇzica
Znotraj panoge strojnega uˇcenja se velikokrat zgodi da avtorji besedil obr- nejo pomen validacijske in uˇcne mnoˇzice ali pa se izraz testne mnoˇzice upo- rablja tako za testno kot za validacijsko mnoˇzico. Na tem mestu bi vkljuˇcili citat, ki se lepo odraˇza v tem kontekstu.
”The literature on machine learning often reverses the me- aning of “validation” and “test” sets. This is the most blatant example of the terminological confusion that pervades artificial intelligence research.” [14]
V naˇsem primeru uˇcno mnoˇzico predstavlja oznaˇcen nabor podatkov, ki smo jih dobili s spletnih strani vkljuˇcenih v SentiNews 1.0 korpus. Drugi nabor podatkov pri nas predstavlja testna mnoˇzica podatkov 50 strani slovenskih ˇclankov, ki smo jih roˇcno klasificirali. Validacijska mnoˇzica pa tu predstavlja del uˇcne mnoˇzice v doloˇceni iteraciji preˇcnega preverjanja.
Torej, preˇcno preverjanje je statistiˇcna metoda, ki se uporablja za oceno uspeˇsnosti in izgradnjo modela strojnega uˇcenja. Je manj pristranska oz.
manj optimistiˇcna metoda ocenjevanja modela, kot nekatere druge metode (npr. enostavna delitev na uˇcno/validacijsko mnoˇzico). Gre za tehniko veˇckratnega ponovnega vzorˇcenja (angl. resampling) z namenom oceniti in testirati model, ki se bo dobro odnesel v danem okolju ˇse nevidenih primerov.
Procedura ima samo en parameterk, ki predstavlja ˇstevilo na katerega se raz- deli uˇcna mnoˇzica, temu ustreza tudi ime. Torej prik = 2 imamo enostavno primer razdelitve na uˇcno in validacijsko mnoˇzico. Izvajanje poteka tako, da uˇcno mnoˇzico nakljuˇcno razdelimo nak podmnoˇzic. Pri ˇcemer v vsaki itera- ciji ena izmed podmnoˇzic predstavlja validacijsko mnoˇzico, uˇcna mnoˇzica pa se sestavi iz preostalihk−1 podmnoˇzic. Nad validacijsko mnoˇzico se v vsaki iteraciji oceni model sestavljen iz uˇcne mnoˇzice. Konˇcni rezultat je sestavljen model na podlagi povpreˇcne uspeˇsnosti izdelanih k modelov.
Izbira parametra k vpliva na uspeˇsnost konˇcnega modela. Z veˇcanjem k parametra se pristranskost veˇca, z manjˇsanjem pa izgubljamo varianco podatkov. V praksi se vrednost k ponavadi nastavi na 5 ali 10, pri gradnji naˇsega modela smo uporabili 10-kratno preˇcno preverjanje.
4.4 Meritve vrednotenja modelov strojnega uˇ cenja
Preden se lotimo predstavitve rezultatov naˇse reˇsitve, opiˇsimo mere s kate- rimi bomo preverili njeno uspeˇsnost. Glavno predstavitev porazdelitve kla- sificiranih razredov nam prikaˇze matrika zamenjav (angl. confusion matrix) prikazana s tabelo 4.3.
Diplomska naloga 35 Dejanski razred
Pozitiven Negativen Napovedan razred Pozitiven T P F P
Negativen F N T N
Tabela 4.3: Tabela matrike zamenjav
Matrika ima velikostn x n, pri ˇcimern predstavlja ˇstevilo razredov. Ker imamo opravka z binarno klasifikacijo bomo vse nadalnje meritve izpeljali iz matrike zamenjav velikosti 2 x 2. Matrika odraˇza ˇstevilo pravilno/nepravilno klasificiranih razredov relativno z dejansko porazdelitvijo razredov. Njen namen je, da lahko ˇze na daleˇc vidimo kako se obnaˇsa naˇs model.
Znotraj matrike najdemo 4 vrednosti, na podlagi katerih lahko izraˇcunamo ostale meritve za ocenjevanje toˇcnosti:
True Positive (TP) predstavlja izid kjer model pravilno napove pozitiven razred.
True Negative (TN) predstavlja izid kjer model pravilno napove negativen razred.
False Positive (FP) predstavlja izid kjer model nepravilno napove pozitiven razred.
False Negative (FN) predstavlja izid kjer model nepravilno napove negativen razred.
Prvi naˇcin ocenjevanja uspeˇsnosti je klasifikacijska toˇcnost (angl. accuracy).
Predstavlja vrednost med 0 in 1, kot ulomek napovedi ki jih je naˇs model pravilno klasificiral. Pri binarnem problemu ga izraˇcunamo s slednjo formulo:
Accuracy= T P +T N T P +T N+F P +F N
Natanˇcnost (angl. precision) je v klasifikacijskih problemih definirana s ˇstevilom pravilno napovedanih pozitivnih razredov, ki ga delimo s ˇstevilom
vseh pozitivnih napovedi razreda. Visoka natanˇcnost pomeni, da nam je model podal veliko veˇc relevantnih rezultatov, kot pa nerelevantnih.
P recision= T P T P +F P
Obˇcutljivost (angl. sensitivity ali recall) je definirana kot ulomek pridoblje- nih relevantnih primerov, deljen s skupnim ˇstevilom vseh relevantnih prime- rov. Visoka obˇcutljivost pomeni da nam je model vrnil veˇcinoma relevantne rezultate.
Recall = T P T P +F N
Kot vidimo tako natanˇcnost kot obˇcutljivost delujeta na osnovi relevantnosti rezultatov. Pogosto sta ti vrednosti v konfliktu, saj z izboljˇsanjem ene vre- dnosti poslabˇsamo drugo in obratno. Tu pride v upoˇstev ocena F1 (angl. F1 Score), ki predstavlja harmoniˇcno sredino natanˇcnosti in obˇcutljivosti. Vre- dnost ocene F1 se giblje med 1 (pomeni popolna natanˇcnost in obˇcutljivost) in 0 (pomeni da je vsaj eden izmed njiju 0).
F1 Score= 2∗ P recision∗Recall P recision+Recall
Zgoraj omenjena ocena F1 ne predstavlja realne ocene toˇcnosti v primeru ko je razred zelo neenakomerno porazdeljen. Na tem mestu predstavimo Matthews korelacijski koeficient, primarno definiran za dvorazredni klasifi- kacijski problem. Ta predstavlja dobro oceno toˇcnosti tudi v neenakomerno porazdeljenih razredih. Mnogi trdijo da je to najbolj informativna ocena za ugotavljanje kakovosti napovedovanja v binarni klasifikaciji, ki jo lahko izpe- ljemo iz matrike zamenjav. MCC nam vrne vrednost v rangu od -1 do 1, pri ˇcimer koeficient 1 predstavlja popolno klasifikacijsko toˇcnost, 0 predstavlja napovedovanje, ki bi ga lahko enaˇcili z nakljuˇcnim ugibanjem in -1 oznaˇcuje ˇcisto nestrinjanje opazovanja in napovedi.
M CC = T P ∗T N−F P ∗F N
p(T P +F P)∗(T P +F N)∗(T N+F P)∗(T N +F N)
Diplomska naloga 37
4.5 Primerjava reˇ sitev
Uspeˇsnost naˇse reˇsitve smo primerjali z obstojeˇco sploˇsno reˇsitvijo v Boiler- pipe knjiˇznici. Primerjava je torej potekala med ekstraktorjema SloPortaliE- xtractor in ArticleExtractor. Testiranje smo izvajali nad naˇso testno mnoˇzico 50 spletnih strani.
V prvem delu smo ˇzeleli samo preveriti, kolikˇsno je procentualno uje- manje izluˇsˇcene vsebine ˇclanka ekstraktorjev in dejanske vsebine ˇclanka. V ta namen smo zgenerirali 150 tekstovnih datotek. 50 datotek je vsebovalo ˇclanke slovenskih portalov izluˇsˇcene s pomoˇcjo SloPortaliExtractorja, 50 da- totek je vsebovalo izluˇsˇcene ˇclanke ArticleExtractorja, zadnjih 50 datotek pa je vsebovalo pravilno vsebino ˇclankov. Nato smo dobljene vsebine ˇclankov ekstraktorjev primerjali z istoleˇznimi roˇcno izluˇsˇcenimi ˇclanki. Ujemanje smo raˇcunali s pomoˇcjo Levenshteinove razdalje, ki pravi da je razdalja med dvema nizoma definirana kot minimalno ˇstevilo sprememb, ki jih je potrebno storiti da en niz spremenimo v drugega. Pri tem so dovoljene operacije nad nizom: dodajanje, brisanje ali sprememba enega znaka. S spodnjo formulo smo nato dobili odstotek ujemanja z izvornim besedilom ˇclanka.
p= 1− Levenshtein distance
M ath.max(niz1.length, niz2.length)∗100
Dobljene rezultate lahko vidimo v tabeli 4.4. Pri ekstrakciji ˇclankov z upo- rabo SloPortaliExtractorja smo zabeleˇzili minimalno ujemanje pri 77,24%
in maksimalno ujemanje pri 100%, medtem ko je pri ekstrakciji ˇclankov z ArticleExtractorjem minimalno ujemanje znaˇsalo 24,35%, maksimalno pa 97,68%. Opazimo da ima ArticleExtractor bolj razprˇsene rezultate, po- slediˇcno tudi manj zanesljive. Kot vidimo povpreˇcno ujemanje SloPortali- Extractorja znaˇsa kar 93,95%, pri ArticleExtractorju pa je povpreˇcno ujema- nje z izvornim ˇclankom znaˇsalo 84,56%.
ArticleExtractor SloPortaliExtractor
Min 24,35% 77,24%
Max 97,68% 100%
Avg 84,56% 93,95%
Tabela 4.4: Statistika ujemanja izluˇsˇcenih ˇclankov
V naslednjem delu pa smo analizirali klasifikacijo teh dveh reˇsitev na ni- vojev blokov. ˇSe enkrat si oglejmo porazdelitev naˇsih testnih podatkov 4.2, z njimi bomo v nadaljevanju izvajali naˇse testiranje. Za izhodiˇsˇce (angl.
baseline) vzemimo klasifikacijsko metodo ZeroR, poznana tudi kot metoda za veˇcinski razred (angl. majority classifier). Gre za najpreprostejˇso obliko klasifikacije, kjer pristop vedno napove veˇcinski razred. Ker nima moˇci napo- vedovanja je uporabna kot mera za uspeˇsnost ostalih klasifikacijskih metod.
Po principu napovedovanja s pristopom ZeroR vse elemente klasificiramo kot ˇsumni podatek (razred 0), porazdelitev je prikazana z matriko zamenjav 4.5.
Dejanski razred Vsebina ˇSum
ZeroR Vsebina 0 0
Sumˇ 613 14306
Tabela 4.5: Porazdelitev razreda s pristopom ZeroR
Pri taki porazdelitvi izraˇcunamo natanˇcnostAcc= 0.9589 oz. 95,89%. Hitro vidimo da natanˇcnost ne poda realne ocene, saj ne upoˇsteva cen napaˇcne klasifikacije. Za referenco bomo primerjali tudi uspeˇsnost ocene F1. V naˇsem primeru natanˇcnost in ocena F1 ne odraˇzata pravilno oceno toˇcnosti, saj imamo dva razreda zelo razliˇcnih velikosti. Zato si bomo tu pomagali z ˇze zgoraj omenjenim Matthews korelacijskim koeficientom, ki se dobro obnese tudi v zelo neuravnoteˇzeni porazdelitvi razredov.
Spet primerjamo ekstraktorja SloPortaliExtractor in ArticleExtractor, ki vkljuˇcujeta nauˇcene klasifikacijske modele in dodane filtre in hevristiˇcne funk- cije. Vzporedna primerjava rezultatov je vidna v tabeli 4.6. Opazili smo da
