Cleaneval

CLEANEVAL + BTE

11. 5. 2008

CLEANEVAL

• http://cleaneval.sigwac.org.uk/
• „čištění“ webových stránek → získání čistých lingvistických dat pro korpus
• mimo netextové prvky se odstraňuje i tzv. boilerplate – reklamy, hlavičky a záhlaví stránek, seznamy odkazů aj.
• výsledný text obsahuje pouze značky <h>, <l> a <p> pro nadpis, prvek seznamu a odstavec

CLEANEVAL – hodnocení

• byly poskytnuty ručně vyčištěné stránky jako referenční a testovací data (cca 100 HTML souborů)
• markup-text – test na správnost přiřazení značek <p>, <l>, <h>
• text-only – test na vyčištění od irelevantního textu
• vyčíslení na základě podobnosti (edit distance na slovech) s ručně vyčištěnými soubory

FIASCO Filtering the Internet by Automatic Subtree Classification

• Institut of Cognitive Science, University of Osnabrück
• DOM stromy, Lynx, Support Vector Machine
• vlastní trénovací data – FIASCO gold standard
• 2 fáze: v první se natrénuje SVM, v druhé se SVM použije na rozlišení clean a dirty textových bloků

FIASCO – preprocessing

• parsování HTML stránek – validace kódu pomocí TagSoup – opensource parser (zvládá i hodně znetvořené zdrojové soubory)
• následná konverze do UTF-8, odstranění Javascriptu, CSS, komentářů, …
• úprava některých tagů pro lepší odlišení bloků (<br /> → <p> apod.)

FIASCO – target nodes

• reprezentace stránky jako DOM strom
• automatický výběr textového bloku (kořen nazván target node)
• empiricky zvolené kritérium pro výběr TN:
• uzel v DOM stromu označen, když 100 % jeho textového obsahu je obsaženo v uzlech bezprostředních následníků
• dobře funguje pro detekování textových bloků na úrovni odstavců

FIASCO – znaky 1

• pro každý TN se určí vektor znaků
• ligvistické znaky
• celková délka textu celého podstromu
• počet slov a slovních typů
• počet vět a průměrná délka vět
• frekvence určitých klíčových slov typických jak pro čistý text, tak i pro boilerplate
• distribuce slovních druhů

FIASCO – znaky 2

• strukturální znaky
• hloubka tagu v DOM stromě
• je uzel nadpis?
• je uzel odstavec?
• počet <a>, <img> v podstromě daného TN

FIASCO – znaky 3

• vizuální znaky
• podle renderované stránky ve Firefoxu (upravený rendering engine, který obtahoval bloky barevným rámečkem – minimal bounding rectangle (MBR))
• na základě pozorování vytvořeny znaky:
• solidity 1 – podobnost MBR s obdélníkem
• solidity 2 – počet vrcholů MBR
• solidity 3 – prům. vzdálenost od vrcholů ke středu MBR
• relativní šířka prvku (k nejširšímu prvku)
• relativní výška prvku

FIASCO - trénování

• použita knihovna LIBSVM
• empiricky nastaveny parametry LIBSVM
• učení na vektorech znaků
• ve výsledku SVM pro daný TN určí pravděpodobnost, že jde o čistý (relevantní) text

FIASCO – závěr, resumé

• SVM určí typ uzlu, dirty bloky se odstraní
• úprava HTML tagů pouze na <p>, <l> a <h>
• slabiny systému FIASCO
• automatické určování TN
• závislost na jazyce (lingvistické znaky)
• výsledné skóre: 63.5 %

StupidOS A high-precision approach to boilerplate removal

• čistý Perl, velká rychlost
• natrénováno na FIASCO gold standard
• n-gramové modely, jazykové modely
• pracuje nad čistým textem, nikoli nad HTML strukturou

StupidOS – fáze

• preprocessing
• odstranění obrázků, komentářů,…
• <br /> -> </p><p>
• převod Lynxem na plain text
• čištění pomocí RE
• např. patičky obsahující mnohokrát „|“, …
• rozdělení pomocí tagů <p>, <l>, <h>

StupidOS - fáze

• vytvořeny jazykové n-gramové modely pro ručně vyčištěný text na základě podmíněné pravděpodobnosti
• SOS implementuje 3-gramy
• interpolované výsledky pro větší obecnost
• výpočet n-gramů pro boilerplate pomocí rozdílů mezi nečištěným a čištěným textem

StupidOS – resumé

• díky jazykovým modelům použitelné pouze pro daný jazyk
• je možné zobecnit n-gramy za cenu přesnosti
• velká rychlost (Perl) a přenositelnost
• skóre: 71.6 %

GenieKnows Web Page cleaning system

• příprava stránek pro indexování vyhledávači
• priorita zachování důležitého obsahu na úkor kvalitního odstranění zbytečného textu
• rozdělení stránky na sémantické bloky
• ani moc dlouhé, ani příliš krátké
• pomocí DOM stromu a vzhledu stránky

GenieKnows – výpočet důležitosti

• na základě znaků jako např.
• umístění bloku na stránce
• velikost písma bloku
• délka textu bloku (relativní – k celému dokumentu)
• počet odkazů bloku (relativní – dtto)
• poměr textu odkazu k textu celého bloku
• relativní počet vět v bloku (věta končí .,!?)
• obsahuje blok formulář, obrázek
• důležitost bloku je vážená hodnota znaků bloku

GenieKnows – vztahy bloků

• brány v potaz pro výpočet důležitosti bloku
• pomocí znaků:
• vzdálenost bloků
• horizontální odsazení bloků
• stejná šířka bloků

GenieKnows – čištění, resumé

• bloky s malou důležitostí odstraněny
• Perlovský skript na transformaci tagů
• <hx> → <h> atd.
• blok s tučným fontem a oddělený odstavcem → <h>
• položka tabulky → <l>
• konec seznamu je začátek odstavce aj.
• použitelnost i pro češtinu
• skóre: 73.6

HTMLCleaner

• Christian Girardi, IRST, Itálie
• založeno na pozorování:
• délka vět v čistém textu > v irelevantní části
• počet odkazů v irelevantní č. > v relevantní
• počet funkčních slov v ir. < v relevantní

HTMLCleaner

• parsing pomocí JerichoHTML
• odstranění Javascriptu, neviditelných prvků, obrázků, appletů, formulářů, …
• formátovacích tagů <b>, <i>, <em>, …

HTMLCleaner – určení rel. textu

• rozpoznání vět:
• délka větší než průměr
• první znak ve větě velký
• věta končí interpunkcí
• sekvence vět začínající a končící dobrou větou
• pro každou sekvenci se spočte nA – počet odkazových znaků a nFW – počet znaků ve funkčních slovech
• vyberou se sekvence s největším nFW - nA

HTMLCleaner – závěr, resumé

• úprava tagů
• <h3> → <h>
• věta kapitálkou → <h>
• závislost na jazyce – funkční slova
• skóre: 74.0 %

Web Corpus Cleaning using Content and Structure

• ISLA, Universiteit van Amsterdam
• 5 různých experimentálních řešení:
• baseline
• heuristika
• rozhodovací stromy
• jazykové modely
• genetické algoritmy

WCC – baseline

• parsování HTML (Perl – HTML::TreeBuilder)
• převod do UTF-8, extrakce textových bloků
• jednoduché úpravy - <br><br> → <p>
• všechny bloky jako <p>

WCC – heuristika

• Jericho HTML parser
• převedení na text
• heuristika na základě slov a písmen
• heuristické řešení – nejlepší výsledky

WCC – heur. algoritmus

for each L in lines
  if character lenght L > 3
    split L into words
    if number of words in L > 10 & average character length of words in L > 3
      if possible_title is set & line counter < 3
        add possible_title as header
        unset line counter, possible_title
      endif
      add L as paragraph
    else
      set possible_title to L
      reset line counter
    endif

• nebere v potaz seznamy
• vytvořena i složitější heuristika, ale příliš pomalá

WCC – rozhodovací stromy

• decision trees naučeny na CLEANEVAL testovacích datech
• rozhodovací znaky:
• počet slov
• rodičovský tag
• poměr slov začínajících vel. písmenem
• poměr slov k interpunkci
• nepoužitelné pro češtinu

WCC – jazykové modely

• experiment, princip z Information Retrieval:
• výsledek dotazu lze vygenerovat z jednoho nebo více souborů z celé množiny dokumentů
• dotaz se vytvoří na základě údajů ze zpracovávané stránky za předpokladu, že nejdůležitější informace nesou nadpisy
• spočte se LM dotazu a jednotlivých prvků stránky
• vybírá se prvek s Kullbach-Leiblerovou divergencí (vzhledem k dotazu) menší než daná konstanta

WCC – genetické algoritmy

• experiment se zpětnovazebným učením
• jsou generovány stromy, jejichž listy jsou RE (positivní a negativní výběr) a uzly s log. OR
• v každé generaci se ze stromů vytvoří RE, použije se na HTML, výsledek se ohodnotí pomocí CLEANEVAL skriptu
• nejlépe ohodnocené přežívají, kříží se
• pomalé vyhodnocování, rychlejší metoda:
• strom získá +2 body za každé slovo, které je i v ručně čištěných datech
• ztratí 1 bod za každé slovo navíc (boilerplate)

WCC - resumé

• baseline: 62.2 %
• heuristika: 68.5 %
• rozhodovací stromy: 52.4 %
• jazykové modely: 60.6 %
• použitelnost heur. přístupu pro češtinu
• CLEANEVAL skóre: 74.2 %

Web Page Cleaning with Conditional Random Fields

• validace HTML pomocí Tidy
• předčištění – odstranění skriptů, stylů, …
• separování textových bloků <p>Hello<b>world</b>!</p> → Hello | world | !
• určení znaků pro každý blok
• učení CRF modelu
• na základě ručně označených testovacích dat (<p>, … <other>)
• pomocí CRF se HTML soubor označkuje
• <other> značky jsou odstraněny

WPC – MARKUP znaky 1

• container znaky
• container.{a, p, u, img, class-{header, bold, italic, list, form}}
• pro každý blok se podle typu značky jeho rodičů nastaví příslušný znak na 1
• <p><a>text</a></p>, text bude mít znaky container.a = 1, container.p = 1
• vhodné pro klasifikaci bloků
• class znaky – určují navzájem podobné bloky

WPC – MARKUP znaky 2

• split znaky
• split.{p, br, hr, class-inline, class-block}
• pro rozhodování, jestli na sebe jednotlivé bloky navazují
• ukládá se i počet tagů určitého typu mezi dvěma boky
• jeden tag <br/> většinou neodděluje dva odstavce, dva už ano

WPC – CONTENT znaky 1

• char.{alpha-rel, num-abs, punct-rel, …}
• absolutní a relativní četnost určitých znaků (char)
• token.{alpha-rel, num-abs, mix-rel, other-rel…}
• relativní a absolutní četnosti tokenů v bloku typu slova, čísla, mix a jiné
• sentence.count
• počet vět – oddělené interpunkcí, naivní přístup, zkratky apod. neošetřovány
• sentence.avg-length
• průměrná délka vět ve slovech

WPC – CONTENT znaky 2

• sentence-{begin, end}
• určení bloků, které začínají a končí větu
• pomáhá rozpoznat seznamy a nadpisy
• nebo pokračující odstavec
• first-duplicate, duplicate-count
• počet stejných bloků na stránce a označení prvního z nich
• detekce „read more“, „comments“, …
• nalezení citací v diskuzích

WPC – CONTENT znaky 3

• regexp.{url, date, time}
• znak jako pole RE
• hodnota znaku je číslo prvního úspěšného RE
• závislé na jazyce
• bullet
• RE hledající časté položky seznamu: a, 1, ), -, …
• každá kombinace dává jinou hodnotu znaku
• bloky se stejnou hodnotou bullet – položky seznamu

WPC – CONTENT znaky 4

• {div, td}-group.word-ratio
• parser seskupuje bloky, které jsou bezprostředními potomky daných div a td tagů
• znaky ratio určují relativní velikost bloku ve slovech
• <div> a <div> b c </div> d <div> e f </div> g </div> parser seskupí: (a, d, g), (b, c) a (e, f)

WPC – DOCUMENT znaky

• position
• relativní pozice bloku v dokumentu
• předpokládá se, že textový „šum“ je hlavně na začátku a na konci stránky
• document.{word, sentence, block}-count
• document.max-{div, td}-group
• největší z relativních velikostí bloků (ve slovech)
• určuje členění dokumentu – nízká hodnota znamená, že je stránka tvořena z mnoha malých bloků – inzeráty, vývěsky, komentáře apod.

WPC – resumé

• 3 nastavení parametrů
• všechny znaky brány v potaz (73.92 %)
• bez word-ratio, numeric-count, mixed-count a nonword-count (74.5 %)
• dále bez regexp-url a document.word-count (75.15 %)
• výsledné skóre: 74.7 % (vítěz)
• s drobnými úpravami použitelné pro češtinu

Kimatu a tool for cleaning non-content text parts from HTML docs

• čte čistý XHTML
• detekce bloků
• blok je množina HTML prvků se stejnými vlastnostmi (tagy, class) a navzájem blízkých
• ratios
• relativní délka bloku (k nejdelšímu bloku)
• relativní průměrná délka bloku
• relativní počet interpunkce v bloku
• relativní počet odkazů bloku

Kimatu – kroky výpočtu 1

• detekování bloků
• na základě ratio určeni kandidáti
• odstranění funkčních bloků
• bloků s opakujícím se obsahem, např. „posted by X“ apod.
• odstranění citací
• na základě kandidátů spočtena LCS se všemi následujícími bloky malé velikosti
• velká LCS → odstranění
• dohledání bloků s malým ratio ale velkou příbuzností s kandidátními bloky

Kimatu – závěr, resumé

• vyhledání relevantních bloků v blízkosti kandidátních
• detekce detekce nadpisů, které mají nízké ratio
• určení podle tagů, interpunkce a velikosti prvku příslušný tag <p>, <l> a <h>
• skóre: 74.3 %
• použitelný pro češtinu

BTE – body text extraction

• publikované v roce 2001 – A. Finn a spol.
• HTML soubor se reprezentuje jako posl. 0 a 1 – slovu odpovídá 0 a tagu 1
• předpokládá se, že relevantní část textu v HTML souboru obsahuje méně tagů než např. menu, zápatí apod.
• hledá se začátek a konec úseku HTML souboru, který odpovídá relevantní části

BTE – body text extraction

• Hledá se i a j maximalizující ↓ výraz
• relevantní text z HTML získáme vyjmutím části mezi i a j