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 &gt; 3
    split L into words
    if number of words in L &gt; 10 &amp; average character length of words in L &gt; 3
      if possible_title is set &amp; line counter &lt; 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
May 27, 2008 |