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
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 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 
. 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):
- 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)
- Número de links por palavra
- Fração do texto dentro de âncoras
- Tamanho médio das âncoras
- Fração dos links que é intra-site
- 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.
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:
Tabela 6: blogs do conjunto de testes
Tabela 6: news do conjunto de testes
Cada um desses sites foi então submetido ao processo de detecção de templates:
- Cada nó recebe um score de seu classificador (lembrando que existem 4 classificadores, um para cada intervalo de tamanho dos nós)
- Todos os nós da árvore tem seu score suavizado
- 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? |  |
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? | |
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 parece ter bastante influência no resultado final: quanto maior o valor , mais páginas são marcadas como template, resultado em um maior recall - até o ponto em que, com 
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 
, 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.
