Detecção de Templates em blogs e news - Busca Web (PUC-Rio, 2007)

O trabalho a seguir é a implementação de um algoritmo para detecção de templates baseado no framework descrito em [1], que consiste em utilizar um método de aprendizado para desenvolver um classificador que, observando algumas características da página (e de seus elementos formadores), consegue atribuir uma probabilidade que o elemento seja ou não um template. Esses valores são então suavizados, para que fiquem mais próximos das propriedades reais de templateness.

Neste trabalho, o foco será a detecção de templates em blogs e sites de notícias (deste ponto em diante referidos como news).

Geração automática dos dados de treinamento

No trabalho original, foram escolhidos 3700 websites aleatórios do banco de dados do Yahoo!. Cada website deveria ter ao menos 100 páginas diferentes. Para cada site foram escolhidas no máximo 200 páginas aleatórias. A quantidade massiva de páginas não deve ter sido um grande problema aos autores, que tinham a sua disposição o volume gigantesco de dados do motor de busca Yahoo!.

Neste trabalho foram escolhidos aleatóriamente 20 blogs (retirados do site Technorati) e 20 sites de news (de famosos jornais de todo o mundo). Em cada um dos 40 sites, foi feito um crawl (usando a ferramenta Ruya, desenvolvida em Python) de, no máximo, 200 páginas do site, num total de cerca de 8.000 páginas.

Site Endereço
Consumerist http://www.consumerist.com
Engadget http://www.engadget.com/
Gigaom http://gigaom.com/
Gizmodo http://gizmodo.com/
How to Change the World http://blog.guykawasaki.com/
Huffington Post http://www.huffingtonpost.com/
ICanhasCheezburger http://www.icanhascheezburger.com/
Joystiq http://www.joystiq.com/
Kotaku http://kotaku.com/
Lifehacker http://lifehacker.com/
Mashable http://mashable.com/
Passionate http://headrush.typepad.com/
Perez Hilton http://perezhilton.com/
Read Write Web http://www.readwriteweb.com/
Scobleizer http://scobleizer.com/
Seth Godin http://sethgodin.typepad.com/
Tech Crunch http://www.techcrunch.com/
Think Progress http://thinkprogress.org/
TMZ http://www.tmz.com/
TUAW http://www.tuaw.com/

Tabela 1. Blogs utilizados para o treinamento do classificador

Site Endereço
ABC News http://www.abcnews.com
BBC http://news.bbc.co.uk
Bloomberg http://www.bloomberg.com
Boston Globe http://www.boston.com
CBS News http://www.cbsnews.com
Chicago Tribune http://www.chicagotribune.com/
CNN http://www.cnn.com
CNN Money http://money.cnn.com
El Pais http://www.elpais.com
FOX News http://www.foxnews.com
Financial Times http://www.ft.com
The Guardian http://www.guardian.co.uk
Herald http://www.theherald.co.uk
Houston Chronicle http://www.houstonchronicle.com
Herald Tribune http://www.iht.com
LA Times http://www.latimes.com
Le Monde http://www.lemonde.fr
MSNBC http://www.msnbc.com
NY Times http://www.nytimes.com
Telegraph http://www.telegraph.co.uk

Tabela 2. News utilizados para o treinamento do classificador

Vale salientar nesse ponto que a ferramenta utilizada para fazer o crawl das páginas não foi a mais adequada para o serviço, por ser uma ferramenta pouco documentada e com alguns erros internos - entretanto, como o objetivo era somente conseguir cerca de 200 URLs (diferentes) de cada site e não baixar os arquivos de cada site, foi decidido utilizar uma ferramenta mais simples. Talvez uma ferramenta mais desenvolvida, que faça um crawl mais completo e consiga baixar todos os arquivos referentes a cada página seja mais interessante em trabalhos futuros - é importante que todos os arquivos que definem o desenho da página (como imagens e estilos CSS) sejam também baixados pelo crawler, pois eles são importantes na hora de definir a posição de cada elemento na tela (suas coordenadas e seu tamanho). As URLs escolhidas para cada site podem ser encontradas no arquivo enderecos.zip.

Escolhidos os documentos, estes foram acessados e seus dados guardados em disco (mais detalhes abaixo). Depois disso, foi usado o algoritmo SiteLevel, proposto em [1], para analisar cada site e marcar os nós como template. O resultado do algoritmo SiteLevel foi então dado ao classificador como exemplo de treinamento. Os valores fornecidos pelo classificador foram então suavizados e a classificação final foi feita.

Usando o Mozilla para extrair informações das páginas

Todas as URLs neste projeto foram tratadas da mesma maneira: primeiro são renderizadas no Gecko (a engine gráfica do Mozilla), é feito um parse da árvore DOM do documento, e seus dados são armazenados em disco de maneira compactada.

Cada documento carregado gera um conjunto de arquivos compactados que representam seus nós. Nestes arquivos está a representação textual de várias propriedades dos nós:

  • ID (existe um identificador único para cada nó do mesmo documento)
  • Tag
  • Nível na árvore
  • ID do nó pai
  • Lista de IDs dos filhos
  • Coordenada X (diferença em relação a margem esquerda da tela)
  • Coordenada Y (diferença em relação a margem do topo da tela)
  • Largura na tela
  • Altura na tela
  • Número de links (número de links do nó, da sub-árvore enraizada no nó e número de links intra-site da sub-árvore)
  • Número de palavras (número de palavras do nó, da sub-árvore enraizada no nó e número de palavras dentro de links da sub-árvore)
  • Texto dentro de âncoras do nó
  • Texto dentro do nó
  • Conteúdo HTML do nó

Além disso, são armazenadas informações que serão utilizadas pelo classificador mais a frente (como o score de templateness do nó, entre outros). Uma das partes mais complicadas do projetofoi conseguir usar o Gecko para conseguir as informações acima, principalmente as informações relacionadas a posição do nó na tela, como altura e largura. Foi necessário encontrar uma maneira de se comunicar com o Gecko através do Python (já que todo o sistema estava sendo desenvolvido nesta linguagem), o que se tornou possível através do PyXPCOM, uma binding em Python do XPCOM, o modelo de objetos da Mozilla, que provê componentes para acesso ao funcionamento interno do Gecko. Entretanto, o uso do PyXPCOM já é demasiado complexo por si só, então foi necessário recorrer a uma biblioteca que facilitasse ainda mais o acesso ao Gecko.

O projeto HulaHop, parte do projeto OLPC (One Laptop Per Children), foi de grande ajuda nesse aspecto. O projeto tem como objetivo desenvolver um "Gecko embedding widget based on PyXPCOM", ou seja, um componente gráfico GTK que seja capaz de conter uma instância do Gecko. Através do HulaHop encontrou-se uma maneira fácil de, dado uma URL, desenhar seu conteúdo em uma janela gráfica (GTK) e, a partir dela, carregar as informações da árvore DOM do documento.

Algoritmo SiteLevel

O algoritmo SiteLevel, descrito em [1], recebe um conjunto de páginas do mesmo site e marca cada nó de cada página como template ou não.

Algoritmo SiteLevel(p)

  • Para cada site, obter um conjunto T de páginas aleatórias do site. Então, para cada página t pertencente a T e para cada nó it, computar h(i), onde h() é uma função de hash. O algoritmo retorna o conjunto de nós que ocorrem em pelo menos $p\%$ das páginas de T.
  • Nós que não possuam esta característica descrita acima, mas que tenham mais de 85% de seu conteúdo HTML marcado como template também são marcados como template.

O algoritmo procura nós repetidos em várias páginas do mesmo site, e aqueles nós que se repetem em ao menos $p\%$ das páginas são marcados como template. Além disso, é usado um segundo critério: nós cujo conteúdo HTML seja formado por 85% (ou mais) de templates, são também templates. No artigo e neste projeto, o parâmetro $p = 10\%$. Usando o algoritmo SiteLevel, cada nó de cada um dos documentos de treinamento é rotulado como template ou não.

Estatísticas dos dados de classificação

As duas tabelas abaixo apresentam informações sobre os resultados do algoritmo SiteLevel.

Site # pág. # nós # nós templ. % templ.
Consumerist 199 43242 7134 16,50%
Engadget 179 35688 13803 38,68%
Gigaom 179 42956 22776 53,02%
Gizmodo 199 40857 10616 25,98%
How to Change the World 200 43030 4213 9,79%
Huffington Post 200 24398 3292 13,49%
ICanhasCheezburger 141 31602 1880 5,95%
Joystiq 199 98013 57772 58,94%
Kotaku 199 46093 8385 18,19%
Lifehacker 199 40711 9061 22,26%
Mashable 198 5449 3578 65,66%
Passionate 200 47839 17669 36,93%
Perez Hilton 47 48701 17093 35,10%
Read Write Web 197 12741 5065 39,75%
Scobleizer 186 20197 2966 14,69%
Seth Godin 168 35388 17560 49,62%
Tech Crunch 198 16860 1732 10,27%
Think Progress 199 119100 9716 8,16%
TMZ 199 97275 77716 79,89%
TUAW 199 51953 34856 67,09%

Tabela 3. Conjunto de blogs: Número de documentos, nós, nós marcados como template pelo algoritmo SiteLevel e a porcentagem de nós template

Site # pág. # nós # nós templ. % templ.
ABC News 200 30043 6699 22,30%
BBC 200 38898 13297 34,18%
Bloomberg 200 31085 14390 46,29%
Boston Globe 200 49501 11143 22,51%
CBS News 199 23115 8627 37,32%
Chicago Tribune 200 13330 7903 59,29%
CNN 200 40478 16889 41,72%
CNN Money 200 5276 145 2,75%
El Pais 199 35669 9141 25,63%
FOX News 200 29131 8359 28,69%
Financial Times 200 41572 17684 42,54%
The Guardian 197 56732 20756 36,59%
Herald 200 35013 16293 46,53%
Houston Chronicle 200 44198 11771 26,63%
Herald Tribune 200 41757 20657 49,47%
LA Times 200 48518 19572 40,34%
Le Monde 196 58420 30274 51,82%
MSNBC 200 52304 20203 38,63%
NY Times 200 37069 13889 37,47%
Telegraph 200 39459 7053 17,87%

Tabela 4. Conjunto de news: Número de documentos, nós, nós marcados como template pelo algoritmo SiteLevel e a porcentagem de nós template

Treinando o classificador

Para o treinamento, é necessário escolher um conjunto de atributos (features) que serão analisadas pelo classificador para decidir se o nó é template. No trabalho original foram sugeridos seis atributos que geram melhores resultados, e neste projeto foram usados os mesmos atributos, listados a seguir (todos os atributos acima podem ser facilmente calculados quando o nó contém as informações mencionadas na seção anterior):

  1. Distância (proximidade) para as margens da página (nesse caso, são dois features: distância do margem superior da margem esquerda da página)
  2. Número de links por palavra
  3. Fração do texto dentro de âncoras
  4. Tamanho médio das âncoras
  5. Fração dos links que é intra-site
  6. Razão do número de caracteres do HTML que é visível

Como as diferença entre nós de diferentes tamanhos é grande, o artigo sugere o uso de diferentes classificadores para diferentes faixas de área dos nós. Neste projeto são usado 4 classificadores. Para decidir como seriam definidas as faixas de tamanho, foi necessário achar os intervalos que dividem igualmente os exemplos de teste.

area-histograma-nytimes.png
area-histograma-abcnews.png
area-histograma-scobleizer.png

Figura 1. Gráficos que mostram, para três sites, a frequência de aparecimento de cada tamanho possível de nó (eixo X: tamanho do nó, eixo Y: quantos nós deste tamanho aparecem no site).

Para cada site (lembrando que um site é composto de várias páginas e cada página contém vários nós), foram encontrados os 3 quartis das áreas dos nós. Foi então tomada a média dos primeiros, segundos e terceiro quartis, juntamente com o mínimo e máximo para formar os quatro intervalos. Os intervalos são, então: [mínimo, média dos primeiros quartis), [média dos primeiros quartis, média dos segundos quartis), [média dos segundos quartis, média dos terceiros quartis) e [média dos terceiros quartis, máximo]. Abaixo a tabela com os quartis e os valores escolhidos.

Site Mínimo 1º quartil 2º quartil 3º quartil Máximo
Consumerist 2000 8960 19475 61500 32145495
Engadget 2025 4738 11628 49200 17338920
Gigaom 2000 7000 21060 74424 206712000
Gizmodo 2000 7420 16940 67160 32063730
How to Change the World 2016 9600 33592 69660 79594080
Huffington Post 2006 7680 18368 74046 24553200
ICanhasCheezburger 2000 2478 7800 30906 30304005
Joystiq 2002 4096 9200 28105 22385835
Kotaku 2002 8400 20900 67160 35957640
Lifehacker 2000 8400 18655 67160 24964395
Mashable 2025 3306 10920 45000 3717345
Passionate 2006 5100 12220 48880 421831560
Perez Hilton 2010 2968 7200 16576 235614735
Read Write Web 2023 11736 17280 88803 8131470
Scobleizer 2166 9828 25296 61000 77617500
Seth Godin 2023 5698 12636 44200 38340675
Tech Crunch 2002 8585 16665 61568 52830855
Think Progress 2001 6855 13710 34790 894304095
TMZ 2010 2052 3534 9198 20190030
TUAW 2000 2870 8316 33726 23731995
ABC News 2000 4830 10440 34170 6196365
BBC 2000 3451 9900 27904 25171770
Bloomberg 2000 4144 11568 33932 27885420
Boston Globe 2000 5000 12348 36566 28974435
CBS News 2000 4200 9280 44652 8607840
Chicago Tribune 2034 4440 12400 37800 5000700
CNN 2000 3864 9600 38376 30904800
CNN Money 2000 4370 16120 79500 7326855
El Pais 2000 4690 10115 34100 19686405
FOX News 2010 3900 7868 23850 27124650
Financial Times 2010 4984 9360 25228 9644100
The Guardian 2006 2282 6300 21120 62263455
Herald 2025 2470 6644 23790 51603195
Houston Chronicle 2000 4658 10752 33354 12179430
Herald Tribune 2000 4800 8876 23520 15553125
LA Times 2000 2160 6244 23632 297977730
Le Monde 2000 2380 8236 29524 13763775
MSNBC 2000 2600 5986 26845 6963060
NY Times 2000 7056 14784 36000 18592650
Telegraph 2000 3220 7956 39600 32189340
Mínimo/Médias/Máximo 2000 5182 12504 42663 894304095

Tabela 5. Estatísticas dos tamanhos dos nós para cada site. A última linha mostra os valores escolhidos para a separação dos classificadores.

Foram treinados então 4 classificadores usando o método de aprendizado Logistic Regression, um para cada intervalo de tamanho de área. A implementação dos classificadores foi feita utilizando os módulos da biblioteca Orange, que provê diversos métodos de aprendizado de máquina em Python.

Suavização dos valores de classificação

Um dos pontos mais importantes de [1] é o uso da suavização dos scores de templateness dos nós. A partir da propriedade que o score de um nó não pode ser maior que o de seus filhos, o problema de ajustar os scores do classificador para atender essa propriedade é visto com um problema de regressão isotônica em uma árvore. É então proposto um algoritmo $$O(n^2 \log n)$$ para resolver o problema.

Neste trabalho foi implementado o algoritmo descrito no artigo, porém uma versão $$O(n^3)$$ do mesmo.

Descrição dos experimentos realizados

Foram escolhidas 20 páginas de news e 20 blogs para formar o conjunto de testes. Para cada uma dessas 40 páginas, o nó que contém o conteúdo foi encontrado e manualmente rotulado como não-template. Todos os filhos deste nó também são rotulados da mesma maneira e todos os seus ancestrais também. A descrição do conjunto de testes encontra-se nas seguintes tabelas:

Site Endereço # nós # template % template
Google Blog http://googleblog.blogspot.com/2007/08/first-year-of-google-wifi.html 213 198 92,96%
Dooce http://dooce.com 151 31 20,53%
Dilbert Blog http://dilbertblog.typepad.com/the_dilbert_blog/2007/08/true-story.html 1509 1485 98,41%
YouTube Blog http://www.youtube.com/blog 114 48 42,11%
Lessig http://lessig.org/blog/2007/08/on_clinton_and_lobbyists.html 208 189 90,87%
Freakonomics http://freakonomics.blogs.nytimes.com/2007/08/27/and-today-is-53/ 176 158 89,77%
IEBlogs http://blogs.msdn.com/ie/archive/2007/08/23/Analyzing-Web-2.0-Applications-with-Ajax-View.aspx 579 551 95,16%
Blogger Buzz http://buzz.blogger.com/ 211 106 50,24%
4 Ever Lasting http://www.4everlasting.com/2007/08/27/looking-for-donut-recipes/ 120 112 93,33%
Cool OSX Apps http://www.coolosxapps.net/2007/08/26/tinkertool-activate-hidden-features-in-os-x/ 151 132 87,42%
River Blog http://www.river-blog.com/?p=1776 257 243 94,55%
Cyberspace Nova http://mrsteel.wordpress.com/2007/08/28/amazed-by-flash-kubrick2001-the-space-oddysey-explained/ 158 141 89,24%
Perez Hilton http://www.boingboing.net/2007/08/psychology-of-riskta.html 128 119 92,97%
The Thinking Blog http://www.thethinkingblog.com/2007/08/how-firms-use-subliminal-mind-control.html 193 177 91,71%
Ms. Danielle http://www.msdanielle.com/tuesday-motivation/ 277 242 87,36%
XyHDTV http://www.xyhd.tv/2007/08/industry-news/video-compilation-of-television-logo-signoffs/ 27 11 40,74%
Random Expressions http://www.deepakjeswal.com/heyy-babbyy/ 94 59 62,77%
Ars Technica http://arstechnica.com/news.ars/post/20070828-getting-to-the-bottom-of-the-gphone-rumors.html 123 99 80,49%
Daily Kos http://www.dailykos.com/ 456 193 42,32%
Ancora Imparo http://scottwater.com/blog/archive/killer-designer/ 84 65 77,38%

Tabela 6: blogs do conjunto de testes

Site Endereço # nós # template % template
Baltimore Sun http://www.baltimoresun.com/news/world/iraq/bal-ghraib0829,0,5391186.story 72 39 54,17%
Canada.com http://www.canada.com/topics/news/national/story.html?id=0f23894f-ccbb-4878-a197-d545eea6de81&k=99168 279 261 93,55%
Wall Street Journal http://online.wsj.com/article/SB118833264199111300.html?mod=googlenews_wsj 173 152 87,86%
Sidney Morning Herald http://www.smh.com.au/news/world/upbeat-bush-hints-at-more-troops-for-iraq/2007/08/29/1188067191690.html 107 89 83,18%
France 24 http://www.france24.com/france24Public/en/administration/afp-news.html?id=070829093259.175rnxrh&cat=null 120 85 70,83%
NY Daily News http://www.nydailynews.com/sports/football/2007/08/29/2007-08-29_goodell_to_huddle_with_vick.html 215 196 91,16%
Washington Post http://www.washingtonpost.com/wp-dyn/content/article/2007/08/28/AR2007082801447.html 107 56 52,34%
The Australian News http://www.theaustralian.news.com.au/story/0,25197,22325267-30417,00.html 280 249 88,93%
The Citizen http://www.thecitizen.com/~citizen0/node/20054 762 738 96,85%
E! Online http://www.eonline.com/news/article/index.jsp?uuid=1a9b7b30-6998-41c8-ac8b-076aa79300cf 197 161 81,73%
VOA News http://voanews.com/english/2007-08-29-voa19.cfm 147 108 73,47%
Al Jazeera http://www.aljazeera.com/news/newsfull.php?newid=25782 946 863 91,23%
This is London http://www.thisislondon.co.uk/news/article-23410121-details/Prison+officers+stage+'illegal'+wildcat+strike+over+pay+dispute/article.do 219 147 67,12%
Russia Today http://www.russiatoday.ru/news/news/13208 61 38 62,30%
Liberation http://www.liberation.fr/actualite/monde/274982.FR.php 239 176 73,64%
Corriere http://www.corriere.it/Primo_Piano/Politica/2007/08_Agosto/29/fini_berlusconi.shtml 147 122 82,99%
Repubblica http://www.repubblica.it/2007/07/sezioni/economia/alitalia-10/anticipa-piano/anticipa-piano.html 72 47 65,28%
Detroit Free Press http://www.freep.com/apps/pbcs.dll/article?AID=/20070829/NEWS07/70829035/1018/BUSINESS05 213 173 81,22%
India Times http://economictimes.indiatimes.com/News/PoliticsNation/Ban_outlines_plan_to_bring_peace_in_Darfur/articleshow/2318666.cms 105 95 90,48%
Thoroughbred Times http://www.thoroughbredtimes.com/international-news/2007/August/29/Equine-flu-continues-to-upset-Australia-horse-industry.aspx 133 99 74,44%

Tabela 6: news do conjunto de testes

Cada um desses sites foi então submetido ao processo de detecção de templates:

  1. Cada nó recebe um score de seu classificador (lembrando que existem 4 classificadores, um para cada intervalo de tamanho dos nós)
  2. Todos os nós da árvore tem seu score suavizado
  3. Nós com score >= 0.5 são considerados template, o resto é considerado conteúdo

Foram feitos os seguintes testes, em um total de 8 diferentes testes:

  • Resultado da classificação com e sem suavização
  • Suavização com o parâmetro $$c$$ (um dos fatores que indica a penalidade no nó durante a suavização) assumindo valores 0.01, 0.1 e 0.1.
  • Classificação usando um classificador treinado somente no tipo específico de site - por exemplo, treinar o classificador somente com os exemplos de blogs para depois classificar os testes de blogs (chamado daqui em diante de classificação específica); classificação usando um classificador treinado em todos os exemplos de teste (chamado daqui pra frente de classificação total).

Resultados

Os resultados abaixo são apresentados em termos de Precision, Recall e f-Measure, como no artigo original. Além disso, é apresentado o tempo médio de processamento de cada site. As tabelas com informações site a site podem ser vistas neste link.

Suavização? Classificação? $c$ Precision Recall f-Measure Tempo
Não Específica - 0,64 0,49 0,53 0,20
Não Total - 0,67 0,58 0,60 0,20
Sim Específica 0.01 0,70 0,65 0,65 53,98
Sim Total 0.01 0,71 0,69 0,67 55,47
Sim Específica 0.1 0,75 0,88 0,79 53,70
Sim Total 0.1 0,76 0,92 0,81 55,09
Sim Específica 1 0,76 1,00 0,84 53,46
Sim Total 1 0,76 1,00 0,84 55,56

Tabela 7: resultados para blogs

Suavização? Classificação? $c$ Precision Recall f-Measure Tempo
Não Específica - 0,75 0,78 0,76 0,17
Não Total - 0,70 0,58 0,62 0,17
Sim Específica 0.01 0,76 0,85 0,80 36,46
Sim Total 0.01 0,74 0,72 0,72 40,40
Sim Específica 0.1 0,77 0,92 0,83 36,52
Sim Total 0.1 0,76 0,85 0,80 40,19
Sim Específica 1 0,78 1,00 0,87 36,55
Sim Total 1 0,78 1,00 0,87 40,43

Tabela 8: resultados para news

O parâmetro $c$ parece ter bastante influência no resultado final: quanto maior o valor $c$, mais páginas são marcadas como template, resultado em um maior recall - até o ponto em que, com $c=1$ todos os nós são considerados templates. Como boa parte dos nós são realmente templates (como pode ser visto na tabela 6), marcar todos como template não gera resultados ruins - gera os melhores valores de f-Measure.

Para $c=0.01$, valor usado no artigo, podemos perceber que a detecção em news é melhor quando são usados classificadores treinados somente com news, enquanto nos blogs é melhor usar um classificador treinado com todos os exemplos. Em todos os casos, o uso da suavização melhora os resultados. Nesse aspecto, os resultados são bastante semelhantes aos apresentados no artigo: a suavização dá um ganho de até 12% nos resultados da f-Measure.

Bibliografia
1. Chakrabarti, Kumar and Punera; Page-level template detection via isotonic smoothing. Proceedings of the 16th international conference on World Wide Web; Alberta, Canada; 2007. Disponível em http://portal.acm.org/citation.cfm?id=1242582.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.