ˇ ´ UCEN ´I TECHNICKE ´ V BRNE ˇ VYSOKE BRNO UNIVERSITY OF TECHNOLOGY
ˇ ´ICH TECHNOLOGI´I FAKULTA INFORMACN ˇ ´ICH SYSTEM ´ ´ U ˚ USTAV INFORMACN FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INFORMATION SYSTEMS
´ EXTRAKCE HLAVN´IHO TEXTU Z WEBOVYCH ˚ DOKUMENTU
´ RSK ˇ ´ PRACE ´ BAKALA A BACHELOR’S THESIS
´ AUTOR PRACE AUTHOR
BRNO 2014
´ DANIEL MROZEK
ˇ ´I TECHNICKE ´ V BRNE ˇ VYSOKE´ UCEN BRNO UNIVERSITY OF TECHNOLOGY
ˇ ´ICH TECHNOLOGI´I FAKULTA INFORMACN ˇ ´ICH SYSTEM ´ ´ U ˚ USTAV INFORMACN FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INFORMATION SYSTEMS
´ EXTRAKCE HLAVN´IHO TEXTU Z WEBOVYCH ˚ DOKUMENTU MAIN TEXT EXTRACTION FROM WEB DOCUMENTS
´ RSK ˇ ´ PRACE ´ BAKALA A BACHELOR’S THESIS
´ AUTOR PRACE
´ DANIEL MROZEK
AUTHOR
´ VEDOUC´I PRACE SUPERVISOR
BRNO 2014
Ing. VLADIM´IR BART´IK, Ph.D.,
Abstrakt Tato pr´ ace se zab´ yv´ a extrakc´ı hlavn´ıho textu z webov´ ych dokument˚ u ve form´atu HTML. Jsou zde pops´ any jiˇz pouˇzit´e metody a jejich rozdˇelen´ı. Praktick´a ˇc´ast se pak zab´ yv´ a n´avrhem algoritmu pro detekci hlavn´ıho textu v HTML str´ank´ach zaloˇzen´em na anal´ yze pˇredevˇs´ım textov´ ych rys˚ u str´ anky v kombinaci s vlastnostmi zaloˇzen´ ych na pozici v dokumentu. V´ ysledn´ a klasifikace je ˇreˇsena pomoc´ı v´ıcevrstv´e perceptonov´e s´ıtˇe. Je zde rovnˇeˇz pops´ana implementace navrhnut´eho algoritmu, postup pˇri testov´an´ı a prezentace zjiˇstˇen´ ych v´ ysledk˚ u.
Abstract This thesis deals with the main text extraction from the web documents in HTML format. It describes some methods that are already used and their separation. The goal of the practical part is to propose an algorithm for main text detection in HTML pages using primarily text features in combination with position features. Block classification is solved by multilayer perceptron. It also describes implementation of the proposed algorithm, the testing procedure and presentation of the obtained results.
Kl´ıˇ cov´ a slova extrakce, dolov´ an´ı, hlavn´ı obsah, textov´e rysy, HTML, MLP, umˇel´a neuronov´a s´ıt’
Keywords extraction, mining, main text, text features, HTML, MLP, artificial neural network
Citace Daniel Mr´ ozek: Extrakce hlavn´ıho textu z webov´ ych dokument˚ u, bakal´ aˇrsk´ a pr´ ace, Brno, FIT VUT v Brnˇe, 2014
Extrakce hlavn´ıho textu z webov´ ych dokument˚ u Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem tuto bakal´ aˇrskou pr´aci vypracoval samostatnˇe pod veden´ım pana . . . ....................... Daniel Mr´ozek 31. ˇcervence 2014
Podˇ ekov´ an´ı Dˇekuji vedouc´ımu pr´ ace Ing. Vladim´ırovi Bart´ıkovi, Ph.D. za trpˇelivost a vstˇr´ıcnost. Dˇekuji tak´e sv´ ym bl´ızk´ ym a pˇr´ atel˚ um za podporu.
c Daniel Mr´
ozek, 2014. Tato pr´ ace vznikla jako ˇskoln´ı d´ılo na Vysok´em uˇcen´ı technick´em v Brnˇe, Fakultˇe informaˇcn´ıch technologi´ı. Pr´ ace je chr´ anˇena autorsk´ym z´ akonem a jej´ı uˇzit´ı bez udˇelen´ı opr´ avnˇen´ı autorem je nez´ akonn´e, s v´yjimkou z´ akonem definovan´ych pˇr´ıpad˚ u.
Obsah ´ 1 Uvod
3
2 Existuj´ıc´ı n´ astroje, pˇ r´ıstupy a neuronov´ e s´ıtˇ e 2.1 Dolov´ an´ı textu . . . . . . . . . . . . . . . . . . . . . . . 2.2 Rozdˇelen´ı metod . . . . . . . . . . . . . . . . . . . . . . 2.3 Metody zaloˇzen´e na vizu´aln´ıch vlastnostech dokumentu 2.4 Metody pracuj´ıc´ı na u ´rovn´ı DOM . . . . . . . . . . . . . 2.5 Umˇel´ a neuronov´ a s´ıt’ . . . . . . . . . . . . . . . . . . . . 3 N´ avrh algoritmu 3.1 Pˇredzpracov´ an´ı dokumentu 3.2 Anal´ yza dokumentu . . . . 3.3 Klasifikace blok˚ u . . . . . . 3.4 N´ asledn´ a anal´ yza . . . . . . 3.5 Rozhran´ı programu . . . . .
´ Uvod Na internetu se nach´ az´ı nepˇrebern´e mnoˇzstv´ı informac´ı, vˇetˇsinou ve formˇe HTML str´anek. Ty vˇsak neobsahuj´ı pouze uˇziteˇcn´ y obsah, ale rovnˇeˇz r˚ uzn´e navigaˇcn´ı prvky, odkazy, reklamy apod. Pro efektivn´ı anal´ yzu takov´ ychto dokument˚ u je potˇreba zn´at hlavn´ı obsah. ˇ ek jej od neuˇziteˇcn´ Clovˇ ych informac´ı jednoduˇse rozliˇs´ı, poˇc´ıtaˇc ne. Proto je potˇreba m´ıt k dispozici n´ astroj, program, kter´ y je schopen plnˇe samostatnˇe rozliˇsit co je hlavn´ı obsah a co je generick´ y obsah. Z´ısk´ an´ı pouze hlavn´ıho obsahu m´a pak nesporn´e v´ yhody pˇri anal´ yze dokument˚ u, hled´ an´ı duplicit a pˇrin´aˇs´ı menˇs´ı datovou n´aroˇcnost. C´ılem t´eto pr´ ace je navrhnout program pro extrakci hlavn´ıho textu z webov´ ych dokument˚ u a implementovat jej. Souˇcasn´a ˇreˇsen´ı nejsou ˇcasto plnˇe vyhovuj´ıc´ı, zejm´ena z d˚ uvodu jejich zamˇeˇren´ı na konkr´etn´ı obor nebo jazyk. Proto se v t´eto pr´aci budeme snaˇzit navrhnout program, kter´ y bude univerz´aln´ı a nebude jazykovˇe ani oborovˇe specifick´ y. Program bude vyuˇz´ıvat pˇr´ıstupy z jiˇz zn´ am´ ych ˇreˇsen´ı a vz´ajemnˇe je kombinovat, d´ıky ˇcemuˇz by mˇel dosahovat podobn´ ych, v ide´ aln´ım pˇr´ıpadˇe lepˇs´ıch v´ ysledk˚ u a nemˇel by b´ yt v d˚ usledku zamˇeˇren pouze na jednu oblast. Program m˚ uˇze b´ yt pak pouˇzit jako souˇc´ast vˇetˇs´ıch syst´emu pˇredevˇs´ım v oblasti dolov´ an´ı dat a anal´ yzy dokument˚ u. Pr´ace je rozdˇelena n´ asleduj´ıc´ım zp˚ usobem. V kapitole 2 budou probr´any r˚ uzn´e postupy vyuˇz´ıvan´e pˇri detekci hlavn´ıho obsahu, pˇriˇcemˇz bude kladen d˚ uraz na metody zaloˇzen´e na DOM (objektov´ y model dokumentu). Rovnˇeˇz zde bude uvedena nezbytn´a teorie pro pochopen´ı n´ asledn´e implementace. Kapitola 3 obsahuje n´avrh syst´emu pro extrakci hlavn´ıho obsahu a porovn´ av´ a jej s dalˇs´ımi, jiˇz implementovan´ ymi syst´emy. V 4. kapitole bude pops´ana jiˇz samotn´ a implementace syst´emu v jazyce Ruby. Kapitola 5 popisuje pr˚ ubˇeh testov´ an´ı a porovn´ an´ı s nˇekter´ ymi jiˇz existuj´ıc´ımi ˇreˇsen´ımi. V 6. kapitole, tedy z´avˇeru, se nal´ez´ a ohl´ednut´ı za v´ ysledky a jsou pops´any dalˇs´ı moˇznosti rozˇs´ıˇren´ı.
3
Kapitola 2
Existuj´ıc´ı n´ astroje, pˇ r´ıstupy a neuronov´ e s´ıtˇ e Tato kapitola pojedn´ av´ a o studi´ıch souvisej´ıc´ıch s touto prac´ı. Zahrnuje rovnˇeˇz rozdˇelen´ı metod na z´ akladˇe toho na jak´e u ´rovn´ı pˇristupuj´ı k dokumentu.
2.1
Dolov´ an´ı textu
Extrakce hlavn´ıho textu spad´ a do oblasti tak zvan´eho dolov´an´ı textu. Dolov´ an´ı textu lze definovat jako intenzivn´ı proces s vyuˇzit´ım znalost´ı kdy uˇzivatel interaguje s kolekc´ı dokument˚ u za pouˇzit´ı sady n´astroj˚ u pro anal´ yzu. Analogicky k dolov´ an´ı dat, pˇri dolov´ an´ı textu se snaˇz´ıme z´ıskat uˇziteˇcn´e informace z datov´ ych zdroj˚ u pomoc´ı zkoum´ an´ı a identifikace zn´ am´ ych vzor˚ u v nestrukturovan´ ych datech.[5]
2.2
Rozdˇ elen´ı metod
Metody pro rozpozn´ av´ an´ı hlavn´ıho textu lze rozdˇelit nˇekolika zp˚ usoby. Kohlsch¨ utter et al. [6] dˇel´ı metody na ty, kter´e analyzuj´ı dokument na z´akladˇe vizu´aln´ıch vlastnost´ı dokumentu a metody, kter´e prov´ adˇej´ı anal´ yzu na u ´rovni DOM. D´ale je moˇzno rozdˇelit metody podle toho, jak´ ym zp˚ usobem funguje dan´ y algoritmus, a to bud’ algoritmy funguj´ıc´ı na principu heuristik bez strojov´eho uˇcen´ı a algoritmy, kter´e vyuˇz´ıvaj´ı strojov´e uˇcen´ı.
2.2.1
Principy bez strojov´ eho uˇ cen´ı
Tyto algoritmy pracuj´ı na z´ akladˇe vˇetˇsinou jednoduch´e heuristiky, popˇr´ıpadˇe nˇekolika heuristik. Pro spr´ avnou funkci nevyˇzaduj´ı ˇz´adn´e vstupn´ı znalosti ani tr´enovac´ı mnoˇzinu. Z valn´e vˇetˇsiny je v´ ysledek zpracov´ an´ı pomoc´ı heuristiky porovn´an v˚ uˇci urˇcit´emu prahu a na z´akladˇe v´ ysledku je rozhodnuto o tom, do kter´e mnoˇziny dan´ y blok n´aleˇz´ı. Aˇckoliv tyto metody patˇr´ı k jednoduˇsˇs´ım metod´am, pˇri spr´avn´em nastaven´ı a po ˇr´adn´em otestov´ an´ı m˚ uˇzou dosahovat velmi dobr´ ych v´ ysledk˚ u. D´ıky jednoduchosti je lze ˇradit vˇetˇsinou tak´e mezi velmi efektivn´ı ˇreˇsen´ı a ˇcasovˇe nen´aroˇcn´e. Jejich hlavn´ı nev´ yhodou je zamˇeˇren´ı na urˇcitou oblast, nepˇresn´e v´ ysledky v pˇr´ıpadˇe nestandardn´ıch dokument˚ u a sloˇzit´e, ˇcasto nemoˇzn´e zmˇeny v pˇr´ıpadˇe, ˇze se chceme zamˇeˇrit na jinou oblast. Metody, patˇr´ıc´ı do t´eto skupiny budou pops´ any n´ıˇze.
4
2.2.2
Principy vyuˇ z´ıvaj´ıc´ı strojov´ e uˇ cen´ı
Metody spadaj´ıc´ı do t´eto kategorie vyˇzaduj´ı urˇcit´e vstupn´ı znalosti resp. tr´enovac´ı mnoˇzinu pro spr´ avnou funkcionalitu. Na rozd´ıl od metod z pˇredchoz´ı kapitoly, kter´e nevyˇzaduj´ı pˇred pouˇzit´ım ˇz´ adn´e dalˇs´ı nastaven´ı ani testov´an´ı, u tˇechto metod je to nezbytn´e. Pro hlavn´ı anal´ yzu je v tomto pˇr´ıpadˇe vyuˇzito r˚ uzn´ ych klasifik´ator˚ u. Takov´ ymto klasifik´atorem m˚ uˇze b´ yt Bayesovsk´ y klasifik´ator, neuronov´a s´ıt’ a dalˇs´ı. Pˇred pouˇzit´ım mus´ı b´ yt klasifik´ ator spr´ avnˇe nastaven, ˇcehoˇz je doc´ıleno d˚ ukladn´ ym testov´an´ım a experimentov´an´ım s jednotliv´ ymi nastaven´ımi. Tento postup je ˇcasto velmi zdlouhav´ y a n´aroˇcn´ y na zdroje, coˇz tyto metody ˇrad´ı k metod´ am sloˇzitˇejˇs´ım. Aby mohly b´ yt provedeny experimenty, je potˇreba m´ıt k dispozici relevantn´ı a dostateˇcnˇe obs´ahlou mnoˇzinu vstupn´ıch resp. tr´enovac´ıch dat. V´ yhodou tˇechto algoritm˚ u je, ˇze pouhou zmˇenou nastaven´ı klasifik´atoru, popˇr. zmˇenou tr´enovac´ı mnoˇziny, m˚ uˇzeme pokr´ yt jinou oblast. Tyto metody si ˇcasto dok´aˇz´ı velmi dobˇre poradit i s nestandardn´ımi a ˇspatnˇe strukturovan´ ymi dokumenty. Hlavn´ı nev´ yhodou je jejich sloˇzitost a nutnost z´ıskan´ı tr´enovac´ı mnoˇziny dat a n´asledn´e tr´enov´an´ı klasifik´atoru. Na obr´ azku n´ıˇze (2.1) je zobrazen princip fungov´an´ı metod zaloˇzen´ ych na strojov´em uˇcen´ı. Pˇreruˇsovan´e ˇc´ ary charakterizuj´ı ˇc´ast, kdy je prov´adˇeno strojov´e uˇcen´ı, pln´e ˇc´ary pak zobrazuj´ı pr˚ ubˇeh, kdy je klasifik´ ator pouˇz´ıv´an jiˇz v praxi pro anal´ yzu dokumentu.
Obr´ azek 2.1: Metody se strojov´ ym uˇcen´ım
2.3
Metody zaloˇ zen´ e na vizu´ aln´ıch vlastnostech dokumentu
Metody zaloˇzen´e na vizu´ aln´ıch vlastnostech dokumentu vˇetˇsinou dˇel´ı dokument do menˇs´ıch logick´ ych celk˚ u na z´ akladˇe r˚ uzn´ ych mezer a oddˇelovaˇc˚ u a jednotliv´e celky pot´e analyzuj´ı. V´ yhodou tˇechto metod je, ˇze pˇri pouˇzit´ı relativnˇe jednoduch´eho algoritmu je moˇzno z´ıskat kvalitn´ı a dostateˇcnˇe pˇresn´e v´ ysledky. Hlavn´ı nev´ yhoda spoˇc´ıv´a v mnoˇzstv´ı informac´ı, kter´e je potˇreba zn´ at. Kromˇe HTML mus´ı b´ yt k dispozici rovnˇeˇz informace definuj´ıc´ı vzhled str´ anek, napˇr´ıklad CSS (kask´adov´e styly). Tyto informace znaˇcnˇe navyˇsuj´ı objem dat nutn´ y k anal´ yze. Aby str´ anka mohla b´ yt analyzov´ana na z´akladˇe vzhledu, je vˇetˇsinou nutn´e dokument, vˇcetnˇe pˇripojen´ ych styl˚ u, interpretovat. Tato operace je ˇcasto dosti v´ ypoˇcetnˇe n´aroˇcn´ a a pomal´ a. Nejpalˇcivˇejˇs´ım probl´emem u algoritm˚ u tohoto typu je, jak danou str´anku pohodlnˇe a v r´amci moˇznost´ı efektivnˇe renderovat. K tomuto u ´ˇcelu existuj´ı r˚ uzn´e n´astroje. Jedn´ım z nich je napˇr´ıklad CSSBox1 vyv´ıjen´ y na Fakultˇe informaˇcn´ıch technologi´ı VUT v Brnˇe2 . Program je naps´ an v jazyce Java a poskytuje pˇrehledn´e a jednoduch´e aplikaˇcn´ı rozhran´ı 1 2
pro vykreslov´ an´ı a pr´ aci s webov´ ymi dokumenty. Existuj´ı i dalˇs´ı n´astroje, napˇr. Selenium3 a dalˇs´ı.
2.3.1
Metody bez strojov´ eho uˇ cen´ı
Cai et al. [3] rozdˇeluje webov´ y dokument na jak´esi z´akladn´ı objekty. Jeden nebo v´ıce objekt˚ u pak tvoˇr´ı logick´e celky - bloky. Uzly v modelu zaloˇzen´em na vizu´aln´ıch vlastnostech nemusej´ı nutnˇe odpov´ıdat uzl˚ um v objektov´em modelu dokumentu. To je zp˚ usobeno t´ım, ˇze s´emantika dokumentu nen´ı pops´ana pouze pomoc´ı jazyka HTML, ale rovnˇeˇz pomoc´ı kask´ adov´ ych styl˚ u. Cai et al. [3] popisuje webov´ y dokument jako blok, skl´adaj´ıc´ı se z koneˇcn´e mnoˇziny nepˇrekr´ yvaj´ıc´ıch se podˇr´ızen´ ych blok˚ u, kter´e maj´ı opˇet vlastnosti rodiˇcovsk´eho bloku. Tyto bloky jsou oddˇeleny koneˇcnou mnoˇzinou jak vertik´aln´ıch tak horizont´aln´ıch oddˇelovaˇc˚ u. Kaˇzd´ y blok m´a nav´ıc informaci o vztaz´ıch mezi kaˇzd´ ymi dvˇema bloky, ze kter´ ych se skl´ ad´ a. Kaˇzd´emu oddˇelovaˇci je rovnˇeˇz pˇriˇrazena v´aha. Algoritmus zkoum´ a oddˇelovaˇce od nejmenˇs´ı v´ahy po nejvˇetˇs´ı a bloky mezi tˇemito oddˇelovaˇci spojuje a tvoˇr´ı bloky nov´e. Takto pokraˇcuje dokud nenaraz´ı na oddˇelovaˇc s nejvyˇsˇs´ı v´ahou. Pˇri vytvoˇren´ı nov´eho bloku je kontrolov´ ana spr´avn´a zrnitost. Pokud blok neodpov´ıd´a poˇzadavk˚ um, vrac´ı se algoritmus o krok zpˇet aby vytvoˇril vnitˇrn´ı obsah bloku. V´ ystupem algoritmu je dokument rozdˇelen´ y podle jeho vizu´aln´ıch vlastnost´ı na jednotliv´e bloky. Burget [2] ve sv´e pr´ aci popisuje algoritmus, kter´ y pracuje ve 4 kroc´ıch. Nejprve vykresl´ı dokument, kter´ y je pot´e rozdˇelen do blok˚ u. V t´eto kl´ıˇcov´e f´azi jsou urˇceny logick´e segmenty, kter´e mohou b´ yt uvaˇzov´ any jako samostatn´e. N´aslednˇe je urˇceno fin´aln´ı poˇrad´ı jednotliv´ ych celk˚ u a je generov´ an jednoduch´ y HTML k´od. Pro vykreslen´ı str´anky je vyuˇz´ıv´ an jiˇz zmiˇ novan´ y n´ astroj CSSBox [?]. V´ ystupem prvn´ı f´aze je strom blok˚ u, kdy je blokem rozumˇen obd´eln´ıkov´ y u ´tvar, kter´ y nen´ı skryt´ y. Ve f´az´ı segmentace jsou nal´ez´any logick´e celky. Samotn´ y proces sest´ av´ a ze 3 f´az´ı. Detekce jednotv´arn´ ych oblast´ı, kdy oblast tvoˇr´ı soused´ıc´ı bloky s konzistentn´ım stylem. Dalˇs´ı f´azi je detekce nadpis˚ u na z´akladˇe vlastnosti fontu. Posledn´ı f´ azi tohoto kroku je detekce logick´ ych celk˚ u, kter´e se skl´adaj´ı z v´ıce blok˚ u. Jako v´ ychoz´ı bod se vyuˇz´ıvaj´ı detekovan´e nadpisy. V´ ysledkem tohoto kroku je strom vizu´aln´ıch oblast´ı a informac´ı o nich. Na rozd´ıl od HTML k´odu je tato reprezentace mnohem bliˇzˇs´ı lidsk´emu vn´ıman´ı dokumentu. V kroku n´asleduj´ıc´ım se algoritmus snaˇz´ı pˇresunout d˚ uleˇzit´e oblasti k zaˇc´ atk˚ u dokumentu. Poˇrad´ı zb´ yvaj´ıc´ıch ˇc´asti se snaˇz´ı zachovat, aby nebyla naruˇsena konzistence obsahu. Na konec je vytvoˇren jednoduch´ y HTML k´od skl´adaj´ıc´ı se v podstatˇe pouze z element˚ u
pro kaˇzd´ y logick´ y celek a pro textov´e bloky, kter´ ym je rovnˇeˇz pˇriˇrazen odpov´ıdaj´ıc´ı styl. Experiment´aln´ı v´ ysledky ukazuj´ı, ˇze algoritmus funguje spolehlivˇe pro vˇetˇsinu testovan´ ych str´anek.
2.3.2
Metody se strojov´ ym uˇ cen´ım
Kunc a Burget [7] ve sv´em pˇr´ıspˇevku popisuj´ı zp˚ usob klasifikace dokument˚ u na z´akladˇe jejich vizu´ aln´ıch rys˚ u. V prvn´ım kroku prov´ad´ı rekonstrukci v´ ysledn´e podoby dokumentu. Tento krok vyˇzaduje kompletn´ı renderov´an´ı str´anky, kter´e m˚ uˇze b´ yt dosti n´aroˇcn´e. Pot´e jsou pro kaˇzdou oblast ze z´ıskan´e hierarchick´e struktury urˇceny jejich v´ yznamn´e vizu´aln´ı rysy a na z´ akladˇe tˇech jsou oblasti spojov´any do vˇetˇs´ıch celk˚ u. Nakonec jsou pro kaˇzd´ y celek vypoˇc´ıt´ any r˚ uzn´e vizu´ aln´ı atributy a na z´akladˇe tˇech je provedena anal´ yza. Zmiˇ novan´ ymi vlastnostmi jsou pr˚ umˇern´ a velikost p´ısma, pˇrevaˇzuj´ıc´ı v´aha p´ısma, pˇrevaˇzuj´ıc´ı styl p´ısma (sklonˇen´e nebo norm´ aln´ı), poˇcet oblast´ı v okol´ı, poˇcet znak˚ u textu, poˇcet ˇc´ıslic, mal´ ych 3
http://docs.seleniumhq.org/
6
a velk´ ych p´ısmen abecedy a mezer v textu, svˇetelnost textu a pozad´ı, a nakonec kontrast. Na z´akladˇe vypoˇcten´ ych atribut˚ u je pak moˇzn´e detekovat napˇr´ıklad text ˇcl´anku, protoˇze jak je v pr´ aci pops´ ano, tento text je vˇetˇsinou vˇetˇs´ı neˇz je pr˚ umˇern´a velikost textu v dokumentu a obsahuje delˇs´ı, souvisl´ y text. Pro klasifikaci byl vyuˇzit volnˇe dostupn´ y n´astroj Weka. i kdyˇz tato pr´ ace nesouvis´ı pˇr´ımo s extrakc´ı hlavn´ıho textu z dokumentu, lze vˇetˇsinu poznatk˚ u a popisovan´ y postup vyuˇz´ıt i pˇri ˇreˇsen´ı tohoto probl´emu.
Obr´ azek 2.2: Postup pˇri detekci hlavn´ıho obsahu na z´akladˇe vizu´aln´ıch vlastnost´ı
2.4
Metody pracuj´ıc´ı na u ´ rovn´ı DOM
Tyto metody vyˇzaduj´ı pro anal´ yzu pouze zdrojov´ y k´od dokumentu ve form´atu HTML nebo XML resp. jejich objektov´ y model dokumentu. Dalˇs´ı informace o str´ance, jako jsou kask´adov´e styly nebo soubory se skripty, nejsou vyˇzadov´any. Dokument je na z´akladˇe r˚ uzn´ ych vlastnost´ı textu, struktury a dalˇs´ıch ukazatel˚ u analyzov´an a na z´akladˇe tˇechto ukazatel˚ u je detekov´ an hlavn´ı obsah. Existuje v´ıce zp˚ usob˚ u jak tyto metody vyuˇz´ıt v praxi a jak je implementovat. Pˇred nˇekolika lety, byla extrakce textu pomˇernˇe jednoduch´a. Webov´e dokumenty nebyly pˇr´ıliˇs komplexn´ı a struktura str´anky byla tvoˇrena vˇetˇsinou pomoc´ı tabulky. Napˇr´ıklad McKeown et al. [8] popisuje zp˚ usob jak´ ym z´ısk´avaj´ı hlavn´ı obsah p´ar slovy. Pokud vybran´ a buˇ nka tabulky obsahuje po odstranˇen´ı znaˇcek a odkaz˚ u v´ıce znak˚ u neˇz je nastaven´ y pr´ ah, je toto povaˇzov´ ano za hlavn´ı obsah. V dneˇsn´ı dobˇe je vˇsak situace jin´a. Struktura HTML je sloˇzitˇejˇs´ı, tabulkov´e rozvrˇzen´ı je zˇr´ıdkakdy pouˇz´ıv´ ano a neˇz´ adouc´ı prvky, jako je napˇr´ıklad reklama, se ˇcasto vyskytuj´ı i mezi textem.
7
2.4.1
Metody bez strojov´ eho uˇ cen´ı
Kohlsch¨ utter et al. [6] pˇredstavuje postup pro detekci generick´eho obsahu, tud´ıˇz rozdˇelen´ı dokumentu na generick´ y obsah a hlavn´ı text, zaloˇzen´ y na z´akladn´ıch vlastnostech textu. Nejprve je dokument rozdˇelen do atomick´ ych blok˚ u a pot´e jsou pro kaˇzd´ y blok zjiˇstˇeny jeho vlastnosti. Bˇehem dˇelen´ı dokumentu na atomick´e bloky, je obsah nˇekter´ ych znaˇcek pˇr´ımo odstraˇ nov´ an, jelikoˇz je dopˇredu jasn´e, ˇze tyto znaˇcky neobsahuj´ı hlavn´ı obsah. Jedin´e znaˇcky, kter´e jsou v bloc´ıch ponech´any jsou odkazy. Pot´e jsou bloky analyzov´any pˇredevˇs´ım podle dvou vlastnost´ı, poˇctu slov a hustoty odkaz˚ u. V´ ysledky ukazuj´ı, ˇze i pomoc´ı takto jednoduch´eho ˇreˇsen´ı lze dosahovat velmi pˇresn´ ych v´ ysledk˚ u. Algoritmus implementovan´ y na z´akladˇe t´eto studie nese n´ azev boilerpipe. V z´akladn´ım extraktoru je pro anal´ yzu vyuˇzit rozhodovac´ı strom, zaloˇzen´ y ve v´ ysledku pouze na hustotˇe odkaz˚ u a poˇctu slov, jak pro aktu´aln´ı blok, tak pro pˇredchoz´ı a n´asleduj´ıc´ı. i pˇresto, ˇze pˇri implementaci bylo vyuˇzito n´astroje Weka, ˇrad´ım tento algoritmus mezi metody bez strojov´eho uˇcen´ı, jelikoˇz ve fin´ ale je pouˇzit hotov´ y rozhodovac´ı strom. N´astroj Weka byl pouˇzit pouze pro zjiˇstˇen´ı ide´aln´ıch prah˚ u. Vieira et al. [13] popisuje postup liˇs´ıc´ı se od pˇredchoz´ıch. Detekci a odstraˇ nov´an´ı generick´eho obsahu prov´ ad´ı na z´ akladˇe znalosti v´ıce podobn´ ych str´anek. i kdyˇz se na prvn´ı pohled m˚ uˇze zd´ at, ˇze toto ˇreˇsen´ı je neefektivn´ı, kv˚ uli nutnosti stahov´an´ı v´ıce str´anek, nen´ı tomu tak. Alespoˇ n ne v pˇr´ıpadˇe, kdy je analyzov´ano v´ıce dokument˚ u z jedn´e dom´eny. V tomto pˇr´ıpadˇe je nev´ yhoda nutnosti v´ıce str´anek eliminov´ana, jelikoˇz bychom je museli tak ˇci onak z´ıskat. z v´ ysledku je vidˇet, ˇze tato metoda dosahuje velmi uspokojiv´ ych v´ ysledk˚ u a je aplikovateln´ a na t´emˇeˇr jak´ ykoliv dokument, nez´avisle na oboru. Nutnost´ı je vˇsak m´ıt alespoˇ n dva dokumenty se stejnou nebo alespoˇ n podobnou strukturou. Pomik´ alek a jeho jusText [10] vyuˇz´ıv´a jednoduch´e heuristiky pro detekci. Vych´ az´ı z pˇredpoklad˚ u, ˇze kr´ atk´e bloky obsahuj´ıc´ı odkaz jsou t´emˇeˇr vˇzdy generick´ ym obsahem a tot´eˇz tvrd´ı o bloc´ıch obsahuj´ıc´ıch velk´e mnoˇzstv´ı odkaz˚ u. D´ale tvrd´ı, ˇze dlouh´e bloky obsahuj´ıc´ı gramatick´ y text jsou vˇetˇsinou hlavn´ım obsahem, a naopak jin´e dlouh´e bloky jsou t´emˇeˇr vˇzdy generick´ ym obsahem. Nakonec jeˇstˇe zav´ad´ı tvrzen´ı, kter´e ˇr´ık´a, ˇze bloky obsahuj´ıc´ı hlavn´ı text vˇetˇsinou tvoˇr´ı shluky, coˇz znamen´a, ˇze blok s generick´ ym obsahem je ˇcasto obklopen jin´ ymi bloky s generick´ ym obsahem a analogicky pro hlavn´ı obsah. Jeho algoritmus se skl´ ad´ a ze 3 hlavn´ıch ˇc´asti. Postupnˇe jsou to preprocessing, bezkontextov´ a anal´ yza a kontextov´ a anal´ yza. V prvn´ı ˇc´asti zbavuje dokument zbyteˇcn´ ych znaˇcek. Bˇehem bezkontextov´e anal´ yzy rozdˇeluje jednotliv´e bloky do n´asleduj´ıc´ıch tˇr´ıd: • ˇspatn´e - generick´ y obsah • dobr´e - hlavn´ı obsah • kr´ atk´e - nelze rozhodnout, pˇr´ıliˇs kr´atk´ y blok • t´emˇeˇr dobr´e - na pomez´ı mezi dobr´ ymi a kr´atkymi Toto rozdˇelen´ı je prov´ adˇeno pomoc´ı vyhodnocen´ı tˇr´ı vlastnost´ı, a to hustoty odkaz˚ u, poˇctu stopslov a poˇctu slov v bloku. V posledn´ı f´azi je za pomoc´ı kontextov´e anal´ yzy rozhodnuto zda jednotliv´e kr´ atk´e a t´emˇeˇr dobr´e bloky jsou dobr´e popˇr. ˇspatn´e. T´emˇeˇr dobr´e bloky soused´ıc´ı s alespoˇ n jedn´e strany s dobr´ ym blokem, je vyhodnocen takt´eˇz jako dobr´ y. Kr´atk´e bloky soused´ıc´ı z obou stran s dobr´ ymi nebo t´emˇeˇr dobr´ ymi jsou oznaˇceny jako dobr´e, zb´ yvaj´ıc´ı jako ˇspatn´e. Je d˚ uleˇzit´e uv´est, ˇze jako soused´ıc´ı bloky v t´eto anal´ yze ignoruj´ı bloky kr´ atk´e. Z´ aroveˇ n pokud se posloupnost kr´atk´ ych nebo t´emˇeˇr dobr´ ych blok˚ u objevuje na zaˇc´ atku nebo na konci dokumentu, jsou tyto bloky ihned oznaˇceny jako ˇspatn´e. 8
Evert [4] popisuje sv˚ uj algoritmus pod jm´enem NCleaner. NCleaner m´a dvˇe z´akladn´ı u ´rovnˇe zpracov´ an´ı. Prvn´ı f´ aze m´ a za u ´kol pˇripravit dokument na dalˇs´ı anal´ yzu. Jsou bˇehem n´ı pomoc´ı regul´ arn´ıch v´ yraz˚ u odstraˇ nov´any neˇz´adouc´ı znaˇcky vˇcetnˇe jejich obsahu (obr´azky, koment´ aˇre a skripty), pot´e je dokument zkonvertov´an na ˇcistˇe textov´ y. D´ale jsou odmaz´any lehce detekovateln´e prvky generick´eho obsahu, napˇr. ty, kter´e obsahuj´ı mnoho znak˚ u |. Druhou f´ az´ı je samotn´e j´ adro algoritmu, sest´avaj´ıc´ı z dvou samostatn´ ych znakov´ ych ngram [14] jazykov´ ych model˚ u, jeden pro ”spr´avn´ y”a druh´ y pro ”ˇspatn´ y”text. Tyto modely jsou pouˇzity na kaˇzdou ˇc´ ast dokumentu a pokud model pro ˇspatn´ y text vypoˇc´ıt´a vˇetˇs´ı pravdˇepodobnost, je tato ˇc´ ast povaˇzov´ana za generick´ y obsah a tud´ıˇz odstranˇena. 4 Z existuj´ıc´ıch n´ astroj˚ u jeˇstˇe zm´ın´ım Readability . Tento n´astroj byl ze zaˇc´atk˚ u pouze jednoduch´ ym algoritmem naprogramovan´ ym v Javascriptu, postupnˇe byl vˇsak pˇretvoˇren na kompletn´ı platformu pro extrakci hlavn´ıho textu ˇcl´anku a usnadnˇen´ı ˇcten´ı. K extrakci vyuˇz´ıv´ a jednoduch´ ych heuristik, kdy ohodnocuje bloky pozitivnˇe ˇci negativnˇe na z´akladˇe r˚ uzn´ ych textov´ ych vlastnost´ı a vlastnost´ı na u ´rovn´ı znaˇcek ˇci jejich atribut˚ u. V´ ysledn´e sk´ ore jednotliv´ ych blok˚ u jsou porovn´ any v˚ uˇci urˇcit´emu prahu a na z´akladˇe v´ ysledku je rozhodnuto zda blok vyhovuje hlavn´ımu textu ˇci ne.
2.4.2
Metody se strojov´ ym uˇ cen´ım
Pasternack et al. [9] popisuje metodu zamˇeˇrenou na dokumenty se ˇcl´anky, kter´a je schopna se vypoˇr´ adat i s dokumenty, kter´e nejsou tvoˇren´e pomoc´ı tabulek. Probl´em rozdˇeluje do dvou ˇc´ asti. Detekce zda str´ anka obsahuje ˇcl´anek a zjiˇstˇen´ı kde pˇresnˇe ˇcl´anek zaˇc´ın´a a kde konˇc´ı. V ˇc´ asti druh´e navrhuje odstranit ze ˇcl´anku reklamy a jin´e neˇz´adouc´ı prvky. Pro tento u ´kon popisuje jednoduchou heuristiku, kter´a nejdˇr´ıve odstran´ı obsah uvnitˇr vˇsech znaˇcek <iframe> a
