( PDF ) Segmentação automática de páginas web

Download PDF

ads:

UNIVERSIDADE FEDERAL DO AMAZONAS

PROGRAMA DE P

OS-GRADUAC¸

AO EM INFORM

ATICA

DEPARTAMENTO DE CI

ENCIA DA COMPUTAC¸

SEGMENTAC¸

AO AUTOM

ATICA DE P

AGINAS WEB

EDISSON CAMPOS BRAGA JUNIOR

Manaus - AM

Setembro de 2010

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

UNIVERSIDADE FEDERAL DO AMAZONAS

PROGRAMA DE P

OS-GRADUAC¸

AO EM INFORM

ATICA

DEPARTAMENTO DE CI

ENCIA DA COMPUTAC¸

EDISSON CAMPOS BRAGA JUNIOR

Segmenta¸c˜ao Autom´atica de P´aginas

Web

Disserta¸c˜ao apresentada ao Programa de P´os-

gradua¸c˜ao em Inform´atica do Departamento

de Ciˆencia da Computa¸c˜ao da Universidade

Federal do Amazonas, como requisito par-

cial para a obten¸c˜ao do t´ıtulo de Mestre em

Inform´atica, ´area de concentra¸c˜ao Recupera¸c˜ao

de Informa¸c˜ao.

Prof. Dr. Edleno Silva de Moura

Orientador

Prof. Dr. David Braga Fernandes de Oli-

veira

Co-orientador

Manaus - AM

Setembro de 2010

ads:

EDISSON CAMPOS BRAGA JUNIOR

SEGMENTAC¸

AO AUTOM

ATICA DE P

AGINAS WEB

Disserta¸c˜ao apresentada ao Programa de P´os-

gradua¸c˜ao em Inform´atica do Departamento

de Ciˆencia da Computa¸c˜ao da Universidade

Federal do Amazonas, como requisito par-

cial para a obten¸c˜ao do t´ıtulo de Mestre em

Inform´atica, ´area de concentra¸c˜ao Recupera¸c˜ao

de Informa¸c˜ao.

Aprovado em 20 de Setembro de 2010.

BANCA EXAMINADORA

Prof. Dr. Edleno Silva de Moura

Departamento de Ciˆencia da Computa¸c˜ao – UFAM/PPGI

Prof. Dr. Nivio Ziviani

Departamento de Ciˆencia da Computa¸c˜ao – UFMG

Prof. Dr. David Braga Fernandes de Oliveira

Departamento de Ciˆencia da Computa¸c˜ao – UFAM/PPGI

Prof. Dr. Marco Antonio Pinheiro de Cristo

Departamento de Ciˆencia da Computa¸c˜ao – UFAM/PPGI

Um mundo no qual o tempo ´e absoluto

´e um mundo consolador.

Pois, embora os movimentos das pessoas sejam imprevis´ıveis,

o movimento do tempo ´e previs´ıvel.

Embora se possa duvidar das pessoas,

n˜ao se pode duvidar do tempo.

Enquanto as pessoas ﬁcam divagando,

o tempo prossegue em sua caminhada

sem olhar para tr´as.

— Alan Lightman

AGRADECIMENTOS

O apoio que recebi para concluir essa disserta¸c˜ao veio de diversas maneiras e

pessoas. Os muitos conselhos, orienta¸c˜oes, incentivos e outras manifesta¸c˜oes e atos

me deram condi¸c˜oes de chegar at´e aqui. A lista dos “respons´aveis” por eu alcan¸car

esse feito ´e extensa e inclui minha esposa, meus pais, amigos e professores. A todos

vocˆes minha sincera gratid˜ao.

Agrade¸co ao Edleno pela oportunidade e por toda a orienta¸c˜ao durante o curso

deste mestrado. Tamb´em agrade¸co ao David que deu um imenso suporte ao meu

trabalho.

A Vanessa, minha querida esposa, meu obrigado mais especial. Vocˆe ´e meu

suporte, e essa conquista tamb´em ´e sua.

Por ﬁm, meu principal agradecimento. A Deus. Mesmo quando eu desisto, Ele

me faz continuar.

SUM

ARIO

LISTA DE ABREVIATURAS E SIGLAS . . . . . . . . . . . . . . . . . . . 7

LISTA DE FIGURAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

LISTA DE TABELAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

RESUMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1 INTRODUC¸

AO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.3 Contribui¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.4 Organiza¸c˜ao da Disserta¸c˜ao . . . . . . . . . . . . . . . . . . . . . . 17

2 CONCEITOS B

ASICOS . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1 Representa¸c˜ao de documentos WEB por meio de ´arvores DOM 19

2.2 Site Style Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 Ranking Baseado em Estrutura de Blocos . . . . . . . . . . . . . 22

2.3.1 Modelagem do site em blocos . . . . . . . . . . . . . . . . . . . . . . 22

2.3.2 C´alculo da Importˆancia dos Blocos . . . . . . . . . . . . . . . . . . . 24

2.4 Avalia¸c˜ao de Segmenta¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . 25

2.4.1

Indice de Rand Ajustado . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.4.2 Informa¸c˜ao M´utua Normalizada . . . . . . . . . . . . . . . . . . . . . 28

3 SEGMENTAC¸

AO AUTOM

ATICA DE P

AGINAS WEB . . . . . . . . 30

3.1 SOM

tree

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.2 Pr´e-processamento: Prepara¸c˜ao de p´aginas Web para serem

inseridas na SOM

tree

. . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.2.1 Passo 1: Poda de regi˜oes com conte´udo aninhado . . . . . . . . . . . 33

3.2.2 Passo 2: Poda de regi˜oes com estrutura regular . . . . . . . . . . . . . 33

3.3 Inser¸c˜ao de p´aginas Web na SOM

tree

. . . . . . . . . . . . . . . . . 35

3.4 Ajustamento da SOM

tree

. . . . . . . . . . . . . . . . . . . . . . . . 37

3.4.1 Poda de n´os com conte´udo aninhado . . . . . . . . . . . . . . . . . . 37

3.4.2 Poda de n´os pela frequˆencia . . . . . . . . . . . . . . . . . . . . . . . 39

4 EXPERIMENTOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.1 Conﬁgura¸c˜ao dos Experimentos . . . . . . . . . . . . . . . . . . . . 41

4.1.1 Cole¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.1.2 Limiares utilizados na segmenta¸c˜ao autom´atica das cole¸c˜oes . . . . . . 42

4.2 An´alise da Segmenta¸c˜ao Autom´atica . . . . . . . . . . . . . . . . . 43

4.3 Compara¸c˜ao entre segmenta¸c˜ao manual e autom´atica . . . . . . 44

4.4 Avalia¸c˜ao do impacto da segmenta¸c˜ao autom´atica para ranking

baseado em blocos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5 CONCLUS

AO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

REFER

ENCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

LISTA DE ABREVIATURAS E SIGLAS

DOM Document Object Model

BC Block Class

BF-rulebased Block Fusion - rule based

IE Internet Explorer

SST Site Style Tree

AdjRand

Indice de Rand Ajustado (Adjusted Rand Index )

NMI Informa¸c˜ao M´utua Normalizada (Normalized Mutual Informa-

tion)

LISTA DE FIGURAS

2.1 Exemplo de representa¸c˜ao HTML e ´arvore DOM de uma p´agina

Web. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2

Arvores DOM e sua respectiva SST. . . . . . . . . . . . . . . . . 21

2.3 Exemplo de p´agina Web com blocos . . . . . . . . . . . . . . . . 23

3.1 Label tags e block tags em uma p´agina Web. . . . . . . . . . . . . 31

3.2 (a) Trecho de p´agina Web com conte´udo aninhado. (b) Repre-

senta¸c˜ao DOM deste trecho. . . . . . . . . . . . . . . . . . . . . . 33

3.3 Trecho de p´agina com estrutura regular. . . . . . . . . . . . . . . 34

3.4 (a) N´os de uma ´arvore DOM com estrutura regular. (b) Resultado

da poda sobre a estrutura regular na mesma ´arvore DOM. . . . . 34

3.5 Exemplo de ´arvore DOM. . . . . . . . . . . . . . . . . . . . . . . 36

3.6 SOM

tree

formada a partir de duas p´aginas Web. . . . . . . . . . . 37

3.7 SOM

tree

com conte´udo aninhado ap´os inser¸c˜ao de uma nova

p´agina, submetida ao processo de poda. . . . . . . . . . . . . . . 39

3.8 Exemplos de poda sobre a SOM

tree

com β = 8. (a) Poda execu-

tada sobre n´os com frequˆencia menor que β. (b) Poda n˜ao pode

ser executada pois a frequˆencia de um dos n´os ´e menor que β. . . 40

4.1 Compara¸c˜ao da m´etrica AdjRand nas segmenta¸c˜oes realizadas

com os m´etodos SOM

tree

e BF-RuleBased, sobre as bases CNN,

IG, CNET e BLOGS. . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.2 Compara¸c˜ao da m´etrica NMI nas segmenta¸c˜oes realizadas com

os m´etodos SOM

tree

e BF-RuleBased, sobre as bases CNN, IG,

CNET e BLOGS. . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

LISTA DE TABELAS

2.1 Tabela de contingˆencia para comparar as segmenta¸c˜oes ρ e ρ



. . . 26

4.1 Distribui¸c˜ao das p´aginas por cole¸c˜ao. . . . . . . . . . . . . . . . . 42

4.2 Quantidade de p´aginas por cole¸c˜ao, block classes e total de blocos

obtidos nas segmenta¸c˜oes manual e autom´atica e quantidade de

blocos na segmenta¸c˜ao autom´atica observados em block classes

(BC ) com frequˆencia abaixo do limiar (freq < β). . . . . . . . . . 43

4.3 Valores m´edios de AdjRand e NMI sobre as p´aginas segmentadas

com SOM

tree

e BF-RuleBased nas 4 bases (IG, CNN, BLOGS e

CNET). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.4 Valores de P@10 e MAP sobre o c´alculo de ranking utilizando o

modelo BM25 tradicional e utilizando o segrank nas 4 bases (IG,

CNN, BLOGS e CNET) para as segmenta¸c˜oes manual e com

SOM

tree

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

RESUMO

Uma nova abordagem em algoritmos de m´aquinas de busca leva em considera¸c˜ao

a estrutura das p´aginas Web para melhorar seus resultados. Nesses m´etodos, as

p´aginas s˜ao subdivididas em blocos e o peso de cada termo da p´agina ´e inﬂuenciado

de acordo com a importˆancia do bloco a qual pertence. O m´etodo proposto em [14]

utiliza informa¸c˜oes estat´ısticas dispon´ıveis na cole¸c˜ao para calcular a importˆancia

dos blocos, por´em sem um meio autom´atico para segmentar as p´aginas. O presente

trabalho tem o objetivo de estudar e avaliar o m´etodo de segmenta¸c˜ao autom´atica

de p´aginas Web proposto em [13], expandindo a utiliza¸c˜ao deste m´etodo para ou-

tras aplica¸c˜oes al´em do problema de busca baseada em blocos. Este m´etodo utiliza

uma nova estrutura de dados chamada SOM

tree

, tendo como entrada um conjunto

de p´aginas Web que comp˜oem um site e como sa´ıda essas mesmas p´aginas, por´em

segmentadas. A segmenta¸c˜ao ´e realizada em trˆes passos. O primeiro passo ´e um pr´e-

processamento sobre ´arvores DOM de cada p´agina do site, onde informa¸c˜oes locais

s˜ao utilizadas para deﬁnir uma vers˜ao inicial dos blocos de cada p´agina. No segundo

passo s˜ao inseridas todas as p´aginas do site, j´a pr´e-processadas, na SOM

tree

. No ter-

ceiro passo a SOM

tree

´e ajustada atrav´es de um novo processo de poda, redundando

em todas as p´aginas do site Web segmentadas em blocos. Para a avalia¸c˜ao da qua-

lidade deste m´etodo de segmenta¸c˜ao, foram realizados dois tipos de experimentos

sobre quatro cole¸c˜oes diferentes. No primeiro experimento foram coletadas e analisa-

das medidas estat´ısticas para quantiﬁcar a concordˆancia entre a segmenta¸c˜ao obtida

pela SOM

tree

e uma segmenta¸c˜ao de referˆencia. Ao comparamos as m´etricas obtidas

por este m´etodo com os valores alcan¸cados pelo m´etodo Rule-based Block Fusion,

que foi o m´etodo encontrado na literatura com melhor desempenho, veriﬁcamos que

os resultados da SOM

tree

foram signiﬁcantemente superiores. No segundo experi-

mento foi realizada uma avalia¸c˜ao do desempenho da segmenta¸c˜ao pela SOM

tree

nos resultados de ranking obtidos pelo m´etodo proposto em [14]. A utiliza¸c˜ao da

segmenta¸c˜ao autom´atica sobre este m´etodo de ranking levou a resultados muito

pr´oximos dos obtidos atrav´es de segmenta¸c˜ao de referˆencia.

Palavras-chave: Segmenta¸c˜ao de P´aginas Web, Documentos Estruturados, Im-

portˆancia de Blocos.

ABSTRACT

A new approach on search engine algorithms takes into account the structure

of Web pages to improve its results. In these methods the pages are divided into

blocks and the weight of each term of a page is inﬂuenced according to the im-

portance of the block it belongs. The method proposed by Fernandes et al. [14]

uses statistical information available in the collection to automatically calculate the

importance of the blocks. This work aims to study and evaluate the Web pages

segmentation method proposed in [13], expanding also its usage to other aplications

besides block based search engines. This segmentation method uses a new data

structure called SOM

tree

. It takes as input a set of Web pages from a given website

and provide these pages segmented into blocks as output. The segmentation process

is performed through three steps. The ﬁrst one is a pre-processing on the DOM tree

of each page of the site, where local information is used to deﬁne an initial version

of the blocks on each page. In the second step all pre-processed pages are inserted

in the SOM

tree

. In the third step the SOM

tree

is adjusted through a new prunning

process. After these steps we have all pages of the website segmented into blocks.

To evaluate the quality of this segmentation method we have performed two types of

experiments on four diﬀerent collections. The ﬁrst evaluation was performed using

statistical metrics to quantify the correlation between the segmentation obtained by

our method with a reference segmentation. When we compare the metrics obtained

by our method with the values obtained by Rule-based Fusion Block, which is the

best performing automatic segmentation algorithm currently found in the literature,

we can notice that the results of our method are signiﬁcantly better. The second ex-

periment is a performance evaluation of the ranking method proposed by Fernandes

et al. [14] using the SOM

tree

segmentation. The use of this segmentation method

on this ranking system led to results very close to those obtained through manual

segmentation.

Keywords: Web Page Segmentation, Structured Documents, Block Importance

1 INTRODUC¸

A medida que a Web vem se consolidando como a principal fonte para armazena-

mento e consulta de informa¸c˜oes, as p´aginas que a comp˜oem tornam-se visualmente

cada vez mais soﬁsticadas. Al´em do conte´udo ligado ao seu t´opico principal, uma

p´agina Web pode conter informa¸c˜oes que n˜ao s˜ao necessariamente ligadas a este,

como por exemplo: propagandas, menus de navega¸c˜ao, contatos, banners, avisos de

do usu´ario, eles podem levar a problemas de visualiza¸c˜ao da p´agina em dispositivos

com tela reduzida, al´em de inﬂuenciar negativamente nos resultados de algoritmos

de recupera¸c˜ao de informa¸c˜ao e minera¸c˜ao de dados. A identiﬁca¸c˜ao dos blocos

presentes nas p´aginas Web fornece meios para que estes problemas sejam tratados.

A segmenta¸c˜ao de p´aginas Web tem se mostrado com uma aplica¸c˜ao relevante

em diversas ´areas. Kang e Chai [18] segmentaram p´aginas Web para identiﬁcar

quais blocos em uma p´agina de fato possuem informa¸c˜oes, de modo que algoritmos

de extra¸c˜ao de informa¸c˜ao funcionem de maneira mais eﬁciente. Fauzi et al. [12]

utilizaram os blocos da p´agina para deﬁnir as informa¸c˜oes de contexto das imagens

presentes nesta. Chakrabarti et al. [9] e Kohlsch¨utter e Nejdl [19] utilizaram a

segmenta¸c˜ao de p´aginas Web para resolver o problema de detec¸c˜ao de duplicados.

Diversos autores propuseram m´etodos para a aplica¸c˜ao da segmenta¸c˜ao de p´aginas

Web para sua visualiza¸c˜ao em dispositivos com tela pequena [5, 11, 16, 26, 27, 28, 29].

O objetivo da segmenta¸c˜ao nestes m´etodos ´e que, uma vez identiﬁcados os blocos

de uma p´agina, o m´etodo pode selecionar quais blocos devem ser exibidos para o

usu´ario, al´em da ordem e da forma em que ser˜ao exibidos.

Uma nova abordagem em algoritmos de m´aquinas de busca tem levado em con-

sidera¸c˜ao a estrutura das p´aginas Web para melhorar seus resultados [14, 8, 23].

Nesses m´etodos, as p´aginas s˜ao subdivididas em blocos e o peso de cada termo de

uma p´agina ´e inﬂuenciado de acordo com a importˆancia do bloco a qual pertence.

Por exemplo, termos encontrados no t´ıtulo podem ser considerados mais importan-

tes do que os encontrados em outros blocos de uma mesma p´agina, assim como

textos em barras de navega¸c˜ao ou propaganda tˆem uma importˆancia inferior aos

encontrados em outros blocos da p´agina. O grande desaﬁo para tais sistemas ´e

encontrar uma maneira autom´atica de segmentar as p´aginas, de tal modo que os

blocos gerados por este processo sejam adequados aos seus prop´ositos.

O m´etodo de c´alculo de ranking proposto por Fernandes et al. [14] utiliza in-

forma¸c˜oes estat´ısticas dispon´ıveis na cole¸c˜ao para calcular automaticamente a im-

portˆancia dos blocos, atribuindo pesos maiores para informa¸c˜oes contidas em blocos

mais importantes. Apesar desse m´etodo apresentar resultados excelentes, carece de

um mecanismo que possibilite a identiﬁca¸c˜ao autom´atica dos blocos nas p´aginas

da cole¸c˜ao. Sem isto, sua utiliza¸c˜ao pr´atica em grandes cole¸c˜oes se torna invi´avel.

Uma das caracter´ısticas necess´arias para que uma segmenta¸c˜ao seja utilizada por

este m´etodo ´e que os blocos que se repetem em p´aginas distintas sejam agrupados.

Entretanto, os m´etodos de segmenta¸c˜ao de p´aginas Web que encontramos na lite-

ratura tˆem em comum o fato de que os blocos gerados em cada p´agina n˜ao tˆem

necessariamente rela¸c˜ao com blocos equivalentes gerados em p´aginas semelhantes.

Por exemplo, em duas p´aginas distintas de um mesmo site de not´ıcias, os t´ıtulos das

not´ıcias em cada p´agina n˜ao ser˜ao necessariamente representados por blocos equi-

valentes. Tal caracter´ıstica inviabiliza o uso desses m´etodos de segmenta¸c˜ao pelo

m´etodo de c´alculo de ranking de Fernandes et al.

A falta de um mecanismo de segmenta¸c˜ao autom´atica de p´aginas Web que sa-

tisfa¸ca os requisitos do sistema de busca proposto em [14], alinhado ao fato de

que n˜ao h´a ainda na literatura um m´etodo de segmenta¸c˜ao que seja considerado

referˆencia, d˜ao-nos a motiva¸c˜ao necess´aria para buscar uma nova alternativa que

possa solucionar estes problemas.

1.1 Objetivos

Este trabalho tem por objetivo estudar e avaliar o m´etodo de segmenta¸c˜ao au-

tom´atica de p´aginas Web proposto por Fernandes em [13], cuja ﬁnalidade ´e identiﬁ-

car os blocos presentes em todas as p´aginas de um mesmo site, agrupando os blocos

equivalentes. Por equivalentes, entenda-se blocos em p´aginas diferentes que com-

partilham a mesma fun¸c˜ao. Por exemplo, blocos em diferentes p´aginas que cont´em

uma mesma barra de navega¸c˜ao, ou blocos que cont´em o t´ıtulo de cada p´agina, s˜ao

considerados blocos equivalentes. Tal m´etodo se baseia na constru¸c˜ao de uma ´arvore

denominada SOM

tree

, que agrupa as ´arvores DOM de um conjunto de paginas Web

e, ap´os uma s´erie de passos de pr´e-processamento e ajustes, tem como sa´ıda tais

p´aginas segmentadas.

Uma das avalia¸c˜oes realizadas nessa disserta¸c˜ao ´e quanto `a eﬁciˆencia de sua

utiliza¸c˜ao em outras aplica¸c˜oes cujo requisito seja que a segmenta¸c˜ao utilizada se

aproxime da percep¸c˜ao que o usu´ario tem sobre esta. Para aferir essa assertiva,

foram utilizadas m´etricas de avalia¸c˜ao de clustering, com o objetivo de mensurar a

qualidade da segmenta¸c˜ao provida pelo m´etodo comparada a uma segmenta¸c˜ao de

referˆencia.

Uma aplica¸c˜ao importante para esse m´etodo de segmenta¸c˜ao ´e a sua utiliza¸c˜ao

nos algoritmos de busca que utilizam a estrutura das p´aginas para melhoria de seus

resultados, em especial o segrank proposto por Fernandes et al. [14], apresentado

na se¸c˜ao 2.3. Para avaliarmos essa condi¸c˜ao, comparamos os resultados do segrank

utilizando uma segmenta¸c˜ao manual de referˆencia com a segmenta¸c˜ao obtida atrav´es

da SOM

tree

. Os resultados alcan¸cados pelo segrank com a segmenta¸c˜ao autom´atica

foram muito pr´oximos dos obtidos com a segmenta¸c˜ao de referˆencia, evidenciando

a eﬁciˆencia deste m´etodo de segmenta¸c˜ao para este ﬁm.

1.2 Trabalhos Relacionados

No contexto da segmenta¸c˜ao de p´aginas Web em blocos, existem v´arios trabalhos

dispon´ıveis. A maior parte desses trabalhos se subdividide em duas vertentes: seg-

menta¸c˜ao baseada no formato visual da p´agina e segmenta¸c˜ao baseada na estrutura

DOM.

Os m´etodos de segmenta¸c˜ao baseados no formato visual das p´aginas tentam

identiﬁcar as caracter´ısticas e informa¸c˜oes sobre os itens visuais da p´agina, como

tamanho, posi¸c˜ao, cor de fundo, etc [7, 22, 6]. Essas caracter´ısticas s˜ao normalmente

obtidas tanto a partir das tags presentes na ´arvore DOM, como atrav´es da utiliza¸c˜ao

de navegadores Web para renderiza¸c˜ao das p´aginas, possibilitando a extra¸c˜ao de

informa¸c˜oes mais precisas sobre a apresenta¸c˜ao da p´agina.

Dentre os m´etodos de segmenta¸c˜ao baseados em formato visual, o que tem ga-

nhado mais aten¸c˜ao recentemente ´e o VIPS [7], cuja proposta ´e simular como o

usu´ario entende a estrutura de uma p´agina, baseado na sua percep¸c˜ao visual. O

VIPS utiliza todas as informa¸c˜oes dispon´ıveis sobre a apresenta¸c˜ao da p´agina, como

fonte, cor e tamanho, identiﬁcando separadores visuais entre diferentes blocos. A

partir desses separadores visuais identiﬁcados, ´e ent˜ao constru´ıda uma ´arvore para

cada p´agina, onde cada bloco ´e um n´o nessa ´arvore. S˜ao permitidos blocos aninha-

dos na p´agina, que s˜ao representados na ´arvore por uma rela¸c˜ao pai-ﬁlho. Um dos

fatores negativos ´e o fato de utilizar o renderizador do browser IE para obter as

informa¸c˜oes sobre a apresenta¸c˜ao da p´agina, restringindo o ambiente no qual esse

mecanismo pode ser usado.

Diversos trabalhos tˆem argumentado que a utiliza¸c˜ao da ´arvore DOM n˜ao ´e

adequada para a segmenta¸c˜ao semˆantica de uma p´agina Web, uma vez que tal ´arvore

tem por objetivo prover uma estrutura para apresenta¸c˜ao de conte´udo e n˜ao uma

estrutura semˆantica [7, 31, 8]. N˜ao obstante `a diﬁculdade citada, alguns autores

prop˜oem m´etodos de segmenta¸c˜ao autom´atica de p´aginas Web baseados na ´arvore

DOM [16].

O trabalho apresentado por Hattori et al. [16] prop˜oe uma abordagem h´ıbrida

para segmenta¸c˜ao de p´aginas HTML atrav´es da ´arvore DOM. Primeiro o m´etodo

divide a p´agina de acordo com tags que denotam separa¸c˜ao de conte´udo, como por

exemplo TABLE, DIV, FRAME, etc. Em seguida, para cada trecho resultante desta

divis˜ao ´e realizada uma nova segmenta¸c˜ao, baseada no c´alculo da distˆancia entre os

conte´udos de informa¸c˜ao (texto, imagem, etc.). Essa distˆancia ´e calculada a partir

da profundidade das tags que separam dois conte´udos.

O m´etodo de segmenta¸c˜ao proposto por Chakrabarti et al. [9] transforma o pro-

blema de segmenta¸c˜ao em um problema de otimiza¸c˜ao de grafos com pesos, onde

o peso representa se dois n´os na ´arvores DOM devem ﬁcar juntos ou separados na

segmenta¸c˜ao. Para isto, ´e realizado um treinamento sobre dados rotulados manual-

mente para aprendizado desses pesos.

Uma outra abordagem, baseada em conceitos de Lingu´ıstica Quantitativa e

estrat´egias da ´area de Vis˜ao Computacional, ´e a Block Fusion, proposta por

Kohlsch¨utter e Nejdl [19]. Nesse m´etodo, ´e utilizada a no¸c˜ao de densidade de texto

como medida para identiﬁcar blocos em uma p´agina Web. A partir de uma seg-

menta¸c˜ao inicial baseada simplesmente nas tags DOM, onde as por¸c˜oes de texto s˜ao

divididas em blocos por abertura ou fechamento de tags, ´e executado um algoritmo

guloso que percorre todos os blocos, buscando fundir blocos adjacentes com densi-

dades semelhantes. O m´etodo ainda apresenta duas varia¸c˜oes. A primeira, chamada

BF-SMOOTHED, tenta fundir blocos em que n˜ao s˜ao encontradas semelhan¸cas em

densidade com os blocos adjacentes, mas s˜ao encontradas semelhan¸cas em blocos

intercalados. A segunda varia¸c˜ao, chamada BF-RULEBASED, utiliza heur´ısticas

adicionais para identiﬁcar tags que certamente indicam divis˜ao de blocos e tags que

n˜ao devem ser consideradas para dividir blocos. Em seu artigo, Kohlsch¨utter e Nejdl

mostram atrav´es destas mesmas m´etricas que seu m´etodo tem resultados superio-

res ao m´etodo proposto por Chakrabarti et al. Devido ao seus bons resultados,

inclusive quando comparados a outros m´etodos, utilizamos o Block Fusion como

referˆencia para avalia¸c˜ao do m´etodo aqui estudado. Como seus melhores resulta-

dos foram obtidos atrav´es do BF-RULEBASED, utilizamos essa varia¸c˜ao nos nossos

experimentos.

1.3 Contribui¸c˜oes

O m´etodo de segmenta¸c˜ao autom´atica estudado e avaliado neste trabalho foi

realizado em conjunto com Fernandes, sendo proposto por este em [13]. No presente

trabalho este m´etodo ´e, entretanto, apresentado de maneira mais detalhada e com

um enfoque mais abrangente. Enquanto em [13] o foco era apenas a utiliza¸c˜ao da

segmenta¸c˜ao autom´atica no problema de busca baseada em blocos, neste trabalho

buscamos tamb´em apresentar este m´etodo de segmenta¸c˜ao como uma alternativa

para outras aplica¸c˜oes.

Nos m´etodos que encontramos na literatura, o processo de segmenta¸c˜ao ´e re-

alizado sobre cada p´agina individualmente, sem levar em considera¸c˜ao qualquer

informa¸c˜ao externa `a esta. No m´etodo aqui estudado, o processo de segmenta¸c˜ao

utiliza todo o site como entrada para ent˜ao particionar cada p´agina em blocos. Neste

processo, todo o contexto do site ´e utilizado para prover tal segmenta¸c˜ao. Uma vez

que os resultados alcan¸cados por este m´etodo se mostraram signiﬁcativamente su-

periores a outros m´etodos encontrados na literatura, podemos concluir que uma

contribui¸c˜ao importante deste trabalho ´e a constata¸c˜ao de que o contexto do site

contribui para uma segmenta¸c˜ao mais precisa.

Um diferencial importante deste m´etodo de segmenta¸c˜ao est´a no agrupamento

dos blocos equivalentes encontrados em p´aginas distintas, enquanto em outros

m´etodos que encontramos na literatura os blocos s˜ao deﬁnidos apenas no contexto

de sua p´agina, n˜ao tendo qualquer rela¸c˜ao com os blocos de outras p´aginas.

1.4 Organiza¸c˜ao da Disserta¸c˜ao

Esta disserta¸c˜ao est´a organizada como segue. No Cap´ıtulo 2 s˜ao apresentados

os conceitos b´asicos necess´arios para o entendimento do trabalho apresentado nesta

disserta¸c˜ao. No Cap´ıtulo 3 ser˜ao apresentados novos conceitos e o novo m´etodo

para segmenta¸c˜ao autom´atica de p´aginas Web. No Cap´ıtulo 4 s˜ao apresentados os

resultados dos experimentos, assim como as an´alises dos resultados obtidos. Por

ﬁm, no Cap´ıtulo 5 s˜ao apresentadas as conclus˜oes e trabalhos futuros.

2 CONCEITOS B

ASICOS

O m´etodo de segmenta¸c˜ao autom´atica de p´aginas Web aqui estudado baseia-

se na manipula¸c˜ao de ´arvores DOM e de uma nova estrutura de dados chamada

SOM

tree

, que ´e uma varia¸c˜ao do Site Style Tree (SST ). Na se¸c˜ao 2.1 fazemos uma

breve introdu¸c˜ao sobre ´arvores DOM e na se¸c˜ao 2.2 apresentamos o SST.

Visto que este processo de segmenta¸c˜ao tem como uma importante motiva¸c˜ao

fornecer entrada para o m´etodo de ranking baseado em blocos proposto por Fernan-

des et al., na se¸c˜ao 2.3 este m´etodo ´e apresentado. Nesta mesma se¸c˜ao ´e descrita

a modelagem de um site para que este possa ser utilizado pelo m´etodo de ranking.

A segmenta¸c˜ao autom´atica, tendo um site Web como entrada, deve fornecer como

sa´ıda o mesmo site com suas p´aginas segmentadas, de acordo com esta modelagem.

Na se¸c˜ao 2.4 s˜ao apresentadas as m´etricas

Indice de Rand Ajustado (AdjRand)

e Informa¸c˜ao M´utua Normalizada (NMI ). Estas m´etricas ser˜ao utilizadas para a

avalia¸c˜ao da qualidade do m´etodo de segmenta¸c˜ao aqui estudado. Esta avalia¸c˜ao ´e

apresentada na se¸c˜ao 4.3.

A apresenta¸c˜ao e revis˜ao desses conceitos permitir´a um melhor entendimento do

m´etodo de segmenta¸c˜ao de p´aginas Web apresentado no cap´ıtulo 3.

2.1 Representa¸c˜ao de documentos WEB por meio de

´arvores DOM

Uma p´agina Web pode ser representada por uma ´arvore, onde as tags do c´odigo

HTML correspondem aos n´os internos desta ´arvore e o conte´udo da p´agina, como

textos, links e imagens, as folhas. Essa ´arvore ´e conhecida como ´arvore DOM [1],

que ´e um acrˆonimo para “Document Object Model”.

Na Figura 2.1 temos um exemplo de como uma p´agina HTML ´e mapeada para

uma ´arvore DOM. Podemos observar que a hierarquia das tags presentes na p´agina

HTML ´e representada pela rela¸c˜ao pai-ﬁlho dos n´os da ´arvore.

Figura 2.1: Exemplo de representa¸c˜ao HTML e ´arvore DOM de uma p´agina Web.

Cada n´o na ´arvore DOM possui as seguintes informa¸c˜oes:

• nomeTag: identiﬁcador da tag;

• conte´udo: conte´udo do n´o, quando houver (texto, script, etc.);

• atributos: lista de atributos do n´o e seus respectivos valores. Cada atributo

´e identiﬁcado por uma tupla (nome, valor).

2.2 Site Style Tree

Site style tree (SST) ´e uma estrutura de dados proposta por Yi et al. [30] que

tem o objetivo de evidenciar o que h´a de comum em termos de apresenta¸c˜ao nas

p´aginas de um site Web. Tal estrutura ´e uma ´arvore constru´ıda a partir das ´arvores

DOM das p´aginas que comp˜oem o site. Enquanto uma ´arvore DOM descreve a

apresenta¸c˜ao de uma ´unica p´agina, uma SST representa as apresenta¸c˜oes de um

conjunto de p´aginas Web. Portanto, uma SST possibilita que visualizemos quais

partes s˜ao comuns em um conjunto de ´arvores DOM e quais partes s˜ao diferentes.

A Figura 2.2 mostra uma SST originada pela combina¸c˜ao de duas ´arvores DOM.

Figura 2.2:

Arvores DOM e sua respectiva SST.

Para compor uma SST correspondente `as p´aginas de um site, as ´arvores DOM de

cada uma dessas p´aginas devem ser inseridas na SST em um processo top-down. Na

SST, cada tag ´e chamada element node, que ´e equivalente a um n´o na ´arvore DOM.

Tags dispostas em um mesmo n´ıvel hier´arquico da estrutura DOM formam um style

node na SST. No exemplo mostrado na Figura 2.2, [body], [table-img-table],

[p-img-p-a] e [p-br-p] s˜ao style nodes e s˜ao representados por uma caixa ponti-

lhada na ﬁgura. Cada style node ´e formado por um ou mais element nodes.

Para inserir uma ´arvore DOM na SST, a partir de sua raiz, os n´os s˜ao inseridos

na SST em grupos de n´os irm˜aos, encaixando-se em algum style node existente, ou

criando um novo, caso n˜ao exista algum semelhante no mesmo n´ıvel. No exemplo

mostrado na Figura 2.2, podemos observar que as ´arvores d

e d

possuem v´arios

n´os em comum, exceto pelas tags no n´ıvel mais inferior nessas p´aginas. Ao serem

unidas na SST, esses n´os diferentes geram dois style nodes distintos.

Cada style node cont´em uma frequˆencia, que identiﬁca quantas p´aginas possui.

No exemplo da Figura 2.2, os style nodes que est˜ao presentes tanto em d

como

em d

tˆem frequˆencia 2. J´a os style nodes que est˜ao presentes em apenas uma das

´arvores DOM possuem frequˆencia 1.

2.3 Ranking Baseado em Estrutura de Blocos

O m´etodo de ranking proposto por Fernandes et al., que a partir deste momento

chamaremos segrank, utiliza a estrutura de blocos das p´aginas Web para melhorar

os resultados do ranking. Enquanto os m´etodos de busca tradicionais utilizam o

fator tf (frequˆencia de termos) para caracterizar a rela¸c˜ao de um termo com um

dado documento, tal m´etodo prop˜oe que as localiza¸c˜oes das ocorrˆencias do termo

no documento tamb´em sejam levadas em considera¸c˜ao para o c´alculo deste fator.

A vers˜ao do m´etodo originalmente proposto por Fernandes et al. [14] foi leve-

mente modiﬁcada pelos autores em [13]. Enquanto o m´etodo original requeria que

p´aginas com estrutura semelhante fossem agrupadas no que eram chamadas page

classes, na nova implementa¸c˜ao isso n˜ao ´e mais necess´ario.

Para a realiza¸c˜ao do c´alculo do ranking, o segrank utiliza como entrada um

conjunto de p´aginas, cada uma delas dividida em blocos de acordo com a modelagem

apresentada a seguir.

2.3.1 Modelagem do site em blocos

Uma p´agina Web t´ıpica pode ser visualmente dividida em regi˜oes com semˆanticas

bem deﬁnidas, as quais denominamos blocos. Como exemplo, podemos observar

na Figura 2.3 uma p´agina de not´ıcia com um menu `a esquerda, um conjunto de

propagandas `a direita, o texto principal da not´ıcia ao centro, t´ıtulo acima da not´ıcia,

etc. Cada uma dessas partes representa um bloco da p´agina. Apenas conte´udos

textuais s˜ao considerados para a forma¸c˜ao de blocos. Logo, blocos que apresentam

apenas v´ıdeos ou imagens, por exemplo, s˜ao desconsiderados.

Podemos deﬁnir um bloco como uma regi˜ao cont´ınua de uma p´agina Web repre-

sentada por um par (l, c), onde l ´e o r´otulo do bloco e c ´e o seu conte´udo. O r´otulo

de um bloco ´e representado pelo caminho da raiz at´e o bloco na ´arvore DOM da

Federer é o atual campeão do Grand Slam

britânico

Últimas de Wimbledon

» Dor nas costas faz Dinara Safina desistir de

Wimbledon

» Federer admite surpresa com apenas dois

britânicos em Wimblebon

» Nadal diz que não gostou do sorteio das

chaves de Wimbledon

» Andy Roddick não quer nem pensar em vice

novamente

Busque outras notícias no Terra:

O que é isto?

del.icio.us Facebook Technorati

My Yahoo! Menéame Fresqui

Divulga Fácil Terra Anuncie aqui »

Boletim

Receba as últimas

notícias em seu email

Fale Conosco

Mande suas críticas e

sugestões. Participe!

Wimbledon

Sexta, 18 de junho de 2010, 13h26 Atualizada às 13h43

Wimbledon se previne: vuvuzelas

estão banidas

Torneio de tênis que mais preza

pela manutenção das tradições,

Wimbledon anunciou a proibição

de uso das vuvuzelas no All

England Club. Os dirigentes

resolveram se antecipar ao

modismo que tomou conta da

África do Sul, incomodando

jogadores, técnicos e

torcedores.

» Bellucci enfrenta Mello

» Federer é cabeça de chave

» Williams serão as

cabeças

de chave 1 e 2 em

Wimbledon

» Tenistas e celebridades se

reúnem em evento

pré-Wimbledon

"Pedimos aos espectadores para

que não tragam itens que

possam causar distrações e

interferências nos jogos.

Buzinas, chocalhos e vuvuzelas

estão nesta categoria e não

terão entrada permitida nas

quadras. Nossa mensagem é

para nem trazer estes objetos",

declarou Ian Ritchie, chefe-

executivo do local de

competição.

As partidas da chave principal de Wimbledon começam na segunda-feira.

Gazeta Esportiva

Compartilhe esta notícia

PAULISTA DISTRIBUIDORA DE PECAS LTD

TRABALHAMOS COM PECAS P VEICULOS NAC/IMP LINHA LEVE E PESADOS

www.paulistadistribuidora.com.br

Lassabia Brindes Personalizados

Bolas, canecas, copos, squeezes, bonés Camisetas, bonés e diversos outros itens

www.lassabia.com

Emprestimo Pessoal e consignados

Emprestimo sem consulta no SERASA e SPC. ACESSE. em até 60x

www.alphacred.net

»Conheça o Terra em outros países

> Esportes > Tênis > Torneios > Wimbledon

STAR CINE

Dvd Guerreiros do Céu e da

Terra

Figura 2.3: Exemplo de p´agina Web com blocos

p´agina no qual este bloco pertence, e o conte´udo do bloco ´e todo o texto contido

dentro deste.

Logo, podemos modelar uma p´agina Web como um conjunto de blocos ρ =

, ..., b

}. A quantidade de blocos n varia de acordo com a p´agina. Por sua vez,

um site Web s pode ser modelado como um conjunto de p´aginas s = {ρ

, ..., ρ

cada uma delas composta por um conjunto de blocos.

Blocos de p´aginas distintas de um site que possuam a mesma fun¸c˜ao devem ser

agrupados em block classes (classe de blocos). Uma block class C ´e um conjunto de

blocos pertencentes a diferentes p´aginas de um site que possuem o mesmo r´otulo l.

2.3.2 C´alculo da Importˆancia dos Blocos

A importˆancia de uma block class ´e calculada a partir de estat´ısticas da

ocorrˆencia de seus termos na cole¸c˜ao. Tais estat´ısticas foram baseadas nos con-

ceitos de term frequency e inverse document frequency do modelo vetorial[4]. Desta

forma, para a obten¸c˜ao deste valor, s˜ao computados alguns fatores que ir˜ao compor

o seu c´alculo.

O primeiro fator ´e o ICF (Inverse Class Frequency), que denota a quantidade

de informa¸c˜ao gerada pela ocorrˆencia de um termo t na classe C.

O seu c´alculo ´e deﬁnido pela equa¸c˜ao a seguir, onde NB

´e a quantidade de

elementos (blocos) da classe C, e NB

(C,t)

´e a quantidade de elementos em que o

termo t aparece.

ICF (t, C) = log

(C,t)

(2.1)

Uma vez calculado o ICF dos termos de uma classe, calcula-se o ICF m´edio da

classe, denominado por AICF (C) (Average ICF ), da seguinte maneira:

AICF (C) =



t∈C

IFC (t, C)

(2.2)

onde NT

´e o n´umero de termos distintos que ocorrem pelo menos uma vez em C.

Note que, se os blocos de uma mesma classe tiverem seus conte´udos bastante

similares entre si, o AICF dessa classe ser´a baixo. Caso contr´ario, o AICF ter´a

um valor alto. Essa medida serve para identiﬁcar classes cujos conte´udos, por serem

repetidos entre diversas p´aginas, n˜ao ser˜ao ´uteis para os processos de busca por

informa¸c˜oes.

Um outro fator necess´ario para medir a importˆancia de uma classe ´e o espalha-

mento m´edio de um termo pela classe, ou class spread. A intui¸c˜ao por tr´as dessa

m´etrica ´e que blocos que tˆem termos em comum com outros blocos de uma mesma

p´agina tendem a ser relacionados com o t´opico principal desta p´agina.

Dados numBlockOcurr(t, ρ), que ´e a quantidade de blocos da p´agina ρ em que o

termo t ocorre, e numBlocks(ρ), que ´e a quantidade total de blocos de ρ, calcula-se

o espalhamento de um termo t em uma p´agina ρ, termSpread(t, ρ), por:

termSpread(t, ρ) =

numBlockOcurr(t, ρ)

numBlocks(ρ)

(2.3)

Em seguida, ´e calculado o espalhamento m´edio dos termos do bloco b na p´agina

P (b):

blockSpread(b) =



t∈b

termSpread(t, P (b))

numTerms(b)

(2.4)

onde numTerms(b) ´e a quantidade de termos distintos em b.

Por ﬁm, calcula-se classSpread(b), que ´e o espalhamento m´edio dos termos de

uma classe:

classSpread(C) =



b∈C

blockSpread(b)

(2.5)

onde N

´e o n´umero de blocos de uma classe C.

Uma vez calculadas as m´etricas AICF e classSpread para uma dada classe C,

calcula-se a importˆancia desta classe da seguinte maneira:

classImportance(C) = classSpread(C) × AICF (C) (2.6)

2.4 Avalia¸c˜ao de Segmenta¸c˜ao

Para avaliar a qualidade da segmenta¸c˜ao do m´etodo aqui estudado, utilizamos

duas m´etricas diferentes:

Indice de Rand Ajustado e Informa¸c˜ao M´utua Norma-

lizada. Ambas as m´etricas tˆem por objetivo avaliar o grau de acordo entre dois

particionamentos realizados sobre uma mesma base de dados e s˜ao frequentemente

utilizadas para avalia¸c˜ao de algoritmos de clustering. Para a avalia¸c˜ao da qualidade

de um m´etodo, compara-se o particionamento realizado por este com um particio-

namento considerado correto.

Chakrabarti et al. [9] e Kohlschutter et al. [19] ﬁzeram uso dessas m´etricas para

avaliar a qualidade de segmenta¸c˜ao de p´aginas Web. Nos dois artigos foram com-

ρ/ρ



. . . ρ



T otal

. . . n

T otal m

. . . m

Tabela 2.1: Tabela de contingˆencia para comparar as segmenta¸c˜oes ρ e ρ



parados os resultados da segmenta¸c˜ao autom´atica com segmenta¸c˜ao realizada ma-

nualmente. Para cada p´agina de suas respectivas cole¸c˜oes foram calculadas as duas

m´etricas, comparando as p´aginas segmentadas automaticamente com as mesmas

segmentadas manualmente.

Considere uma p´agina P = t

, ..., t

, sendo t

, ..., t

os n termos encontrados nessa

p´agina, e ρ = {b

, ..., b

} a segmenta¸c˜ao autom´atica em blocos pelo m´etodo aqui

estudado, e a mesma p´agina segmentada manualmente como ρ



= {b



, ..., b



}. Essas

m´etricas foram utilizadas para avaliar o qu˜ao pr´oxima a segmenta¸c˜ao autom´atica

deste m´etodo est´a da segmenta¸c˜ao manual de referˆencia, evidenciando a qualidade

deste. Para o c´alculo dessas m´etricas utilizamos a tabela de contingˆencia descrita

na Tabela 2.1, onde:

• n

´e o n´umero de termos que est˜ao ao mesmo tempo em ρ

e ρ



;

• a

´e o n´umero de termos que est˜ao no bloco ρ

;

• m

´e o n´umero de termos que est˜ao no bloco ρ



;

• x ´e a quantidade de blocos de ρ e

• y ´e a quantidade de blocos de ρ



2.4.1

Indice de Rand Ajustado

Ao segmentar uma p´agina Web P , composta por n termos, a inten¸c˜ao ´e que duas

palavras ﬁquem no mesmo segmento se e somente se elas ﬁzerem parte do mesmo

bloco, de acordo com a percep¸c˜ao visual que se tem da p´agina.

A execu¸c˜ao do processo de segmenta¸c˜ao de uma p´agina pode ser encarada como

uma s´erie de decis˜oes sobre qual bloco cada palavra ser´a atribu´ıda. A avalia¸c˜ao da

corretude de cada decis˜ao ´e realizada a partir da compara¸c˜ao da segmenta¸c˜ao au-

tom´atica em ρ com a segmenta¸c˜ao manual de referˆencia ρ



sobre esta mesma p´agina.

Uma decis˜ao ´e considerada positiva verdadeira (tp) quando duas palavras que fa-

zem parte do mesmo bloco s˜ao corretamente agrupadas no mesmo segmento. Uma

decis˜ao ´e negativa verdadeira (tn) quando duas palavras de blocos diferentes s˜ao

corretamente atribu´ıdas a segmentos distintos. Quando duas palavras de diferentes

blocos s˜ao erroneamente agrupadas no mesmo segmento, tem-se uma decis˜ao posi-

tiva falsa (fp). Uma decis˜ao negativa falsa (fn) ocorre quando duas palavras que

deveriam ﬁcar no mesmo bloco s˜ao atribu´ıdas a segmentos diferentes.

Indice de Rand ou Rand Index (Rand) tem por objetivo mensurar o percentual

de decis˜oes corretas em um particionamento, conforme a seguinte equa¸c˜ao:

Rand(ρ, ρ



) =

tp + tn

tp + fp + tn + fn

tp + tn





(2.7)

O valor de Rand se situa no intervalo entre 0 e 1. Seu valor ´e 1 quando ρ e ρ



est˜ao segmentados de maneira idˆentica. Por´em, n˜ao existe um valor constante para

identiﬁcar que as duas segmenta¸c˜oes sejam diferentes. Para resolver este problema,

Hubert e Arabie criaram uma varia¸c˜ao dessa m´etrica chamada

Indice de Rand Ajus-

tado ou Adjusted Rand Index (AdjRand) [17], que tornou-se a medida preferida para

avalia¸c˜ao de m´etodos de clustering [25]. Similarmente ao Rand, o valor de AdjRand

´e 1 quando as segmenta¸c˜oes ρ e ρ



s˜ao idˆenticas. Quando as segmenta¸c˜oes s˜ao com-

pletamente diferentes, o valor de AdjRand entre elas ´e 0. Seu c´alculo se d´a atrav´es

da seguinte equa¸c˜ao:

AdjRand(ρ, ρ



) =





(tp + tn) − [(tp + fp)(tp + fn) + (fn + tn)(fp + tn)]





− [(tp + fp)(tp + fn) + (fn + tn)(fp + tn)]

(2.8)

Uma forma mais pr´atica de se realizar o c´alculo do Adjusted Rand Index ´e atrav´es

da equa¸c˜ao abaixo, baseada na tabela de contingˆencia apresentada na Tabela 2.1:

AdjRand(ρ, ρ



) =

x,y



i,j





−





































−





















(2.9)

2.4.2 Informa¸c˜ao M´utua Normalizada

A Informa¸c˜ao M´utua (do inglˆes, Mutual Information) ´e uma medida que visa

quantiﬁcar a quantidade de informa¸c˜oes compartilhadas entre dois particionamentos.

Ela indentiﬁca o qu˜ao perto um algoritmo de clustering poderia reconstruir seu

particionamento para se igualar ao particionamento de referˆencia.

Dada uma vari´avel aleat´oria X, que representa a divis˜ao em blocos realizada pela

segmenta¸c˜ao autom´atica, e uma outra vari´avel aleat´oria Y , que representa a divis˜ao

realizada pela segmenta¸c˜ao manual, a informa¸c˜ao m´utua entre essas duas v´ari´aveis

´e denotada por I(X, Y ). Apesar de alguns considerarem a informa¸c˜ao m´utua como

uma m´etrica em si, ela n˜ao possui um limite superior, o que inviabiliza a sua uti-

liza¸c˜ao para compara¸c˜oes entre diferentes m´etodos. Strehl e Ghosh propuseram uma

normaliza¸c˜ao para essa m´etrica, chamada Informa¸c˜ao M´utua Normalizada, ou NMI

(Normalized Mutual Information) [24]. O NMI ´e, portanto, a informa¸c˜ao m´utua en-

tre duas segmenta¸c˜oes, normalizada pela m´edia geom´etrica de suas entropias. Sendo

H(X) a entropia de X, o c´alculo do NMI se d´a pela seguinte f´ormula:

NMI (X, Y ) =

I(X, Y )



H(X)H(Y )

(2.10)

A NMI mede a dependˆencia m´utua de duas solu¸c˜oes atrav´es da rela¸c˜ao entre

suas entropias. A partir da tabela de contingˆencia da Tabela 2.1, podemos calcular

o valor do NMI entre as segmenta¸c˜oes autom´atica (ρ) e manual (ρ



) de uma dada

p´agina atrav´es da equa¸c˜ao abaixo:

NMI (ρ, ρ



) =



i=1



j=1

i,j

log



n·n

i,j













i=1

log







j=1

log



(2.11)

3 SEGMENTAC¸

AO AUTOM

ATICA DE P

AGINAS

WEB

O m´etodo de segmenta¸c˜ao estudado neste trabalho tem como objetivo segmentar

automaticamente p´aginas Web, dividindo-as em blocos. Este processo tem como

entrada um conjunto de p´aginas que comp˜oem um site e, como sa´ıda, essas mesmas

p´aginas segmentadas de acordo com a modelagem descrita na se¸c˜ao 2.3.1. Blocos

equivalentes presentes em diferentes p´aginas s˜ao agrupados em block classes. Por

exemplo, blocos que cont´em um mesmo menu presente em v´arias p´aginas dever˜ao

ser agrupados, formando uma ´unica block class.

As tags de uma ´arvore DOM de uma p´agina podem ser divididas em dois tipos:

1. Block tags: tags que est˜ao dentro de um determinado bloco.

2. Label tags: tags que pertencem ao r´otulo de um ou mais blocos. Ou seja,

uma tag que esteja no caminho da raiz at´e o bloco em si.

Observe na Figura 3.1 uma p´agina Web simples com dois blocos, com destaque

para os block tags e label tags. No bloco mais `a direita as tags <body> e <div>,

por estarem no caminho da raiz at´e o bloco, s˜ao label tags. As tags <p> e <i>, por

sua vez, s˜ao block tags, j´a que est˜ao dentro do bloco. Observe que apesar da tag

<div> fazer parte de seu bloco, ela ´e considerada label tag, uma vez que ´e ela quem

determina a localiza¸c˜ao do bloco na ´arvore DOM. O mesmo vale para a tag <ul>

no bloco `a esquerda.

Figura 3.1: Label tags e block tags em uma p´agina Web.

A id´eia b´asica deste m´etodo de segmenta¸c˜ao ´e classiﬁcar as tags nessas duas cate-

gorias. Uma vez classiﬁcadas, as block tags s˜ao eliminadas, mas n˜ao seus conte´udos.

Ao eliminar as block tags de uma p´agina Web, todas as folhas de sua ´arvore DOM

que possu´ırem conte´udo de texto diretamente associado a elas identiﬁcam os blocos

da mesma.

O m´etodo de segmenta¸c˜ao autom´atica ´e composto por trˆes passos, realizados

sobre as ´arvores DOM das p´aginas a serem segmentadas, utilizando uma estrutura

de dados chamada SOM

tree

. O primeiro passo ´e um pr´e-processamento nas ´arvores

DOM de cada p´agina, onde informa¸c˜oes locais s˜ao utilizadas para deﬁnir uma vers˜ao

inicial dos blocos de cada p´agina. O segundo passo ´e inserir todas as p´aginas do

site, j´a pr´e-processadas, na SOM

tree

. O terceiro e ´ultimo passo ´e ajustar a SOM

tree

atrav´es de um novo processo de poda, redundando em todas as p´aginas do site Web

segmentadas em blocos.

Neste cap´ıtulo, inicialmente explicaremos o que ´e a SOM

tree

e de que maneira

ela ´e ´util para a divis˜ao das p´aginas Web em blocos. Em seguida s˜ao detalhados

todos os passos que comp˜oem o processo de segmenta¸c˜ao.

3.1 SOM

tree

Para a realiza¸c˜ao do processo de segmenta¸c˜ao das p´aginas de um site, utilizare-

mos uma estrutura de dados denominada SOM

tree

. SOM ´e um acrˆonimo para Site

Object Model, em referˆencia ao DOM. A SOM

tree

´e uma ´arvore capaz de comprimir

um conjunto de ´arvores DOM que comp˜oem um site Web. Seu objetivo principal ´e

identiﬁcar as block classes deste site. A SOM

tree

´e baseada na estrutura Site Style

Tree (SST ), apresentada na se¸c˜ao 2.2. A principal diferen¸ca ´e que na SOM

tree

n˜ao

existe o conceito de style node para agrupar n´os irm˜aos, presente na SST.

Os n´os de uma SOM

tree

cont´em algumas informa¸c˜oes idˆenticas `as dos seus res-

pectivos n´os na ´arvore DOM de origem, adicionado de outras, descritas a seguir:

• nomeTag: identiﬁcador da tag;

• atributos: lista de atributos do n´o e seus respectivos valores;

• label: r´otulo que identiﬁca o caminho da raiz at´e este n´o;

• frequˆencia: quantidade de p´aginas que contˆem n´os com label;

• docList: lista de p´aginas que possuem conte´udo de texto diretamente associ-

ados a este n´o.

E importante observar que um mesmo n´o pode ter conte´udo textual em uma

p´agina e em outra p´agina n˜ao ter qualquer conte´udo.

3.2 Pr´e-processamento: Prepara¸c˜ao de p´aginas Web para

serem inseridas na SOM

tree

Antes de inserir uma nova p´agina em uma SOM

tree

, sua ´arvore DOM ´e pr´e-

processada: seus n´os s˜ao submetidos a um processo de poda, com o objetivo de

eliminar block tags ainda na ´arvore DOM. Os passos necess´arios para que as ´arvores

inseridas na SOM

tree

estejam mais pr´oximas da segmenta¸c˜ao ﬁnal s˜ao apresentados

a seguir.

3.2.1 Passo 1: Poda de regi˜oes com conte´udo aninhado

Se uma tag tiver um conte´udo de texto diretamente associado a ela, ent˜ao todas

as tags descendentes na estrutura DOM ser˜ao eliminadas, formando um ´unico bloco.

Observe que somente as tags ser˜ao eliminadas, mas n˜ao seu conte´udo textual. To-

memos por exemplo a tag <div> na ´arvore DOM da Figura 3.2. Observe que esta

tag cont´em um texto diretamente associado a ela (“SkinnyGuy Writes”). Dentro

desta mesma tag existe uma tag <i> que tamb´em tem conte´udo textual, al´em de

outras tags. Nesse caso, dizemos que o conte´udo de <i> ´e aninhado ao conte´udo de

<div> e, logo, o conte´udo dessas tags comp˜oe um ´unico bloco.

(a) (b)

Figura 3.2: (a) Trecho de p´agina Web com conte´udo aninhado. (b) Representa¸c˜ao

DOM deste trecho.

3.2.2 Passo 2: Poda de regi˜oes com estrutura regular

E comum encontrarmos em ´arvores DOM regi˜oes com estruturas regulares. Essas

regi˜oes normalmente cont´em um conjunto de ´ıtens relacionados entre si, tais como

lista de links, menus, paragrafos e outros. Uma vez que os conte´udos desses ´ıtens

s˜ao relacionados, provavelmente o usu´ario os ver´a como um bloco ´unico.

Observe no trecho da p´agina Web de exemplo na Figura 3.3 o menu destacado,

que ´e formado por um conjunto de links dispostos em uma barra horizontal. Como os

´ıtens desse menu est˜ao visualmente coesos, a percep¸c˜ao de que tais ´ıtens pertencem

ao mesmo bloco ´e bastante intuitiva. Como pode-se observar em sua ´arvore DOM,

presente na Figura 3.4, o conjunto de tags que separam os ´ıtens deste menu s˜ao os

mesmos, dizemos que este menu tem uma estrutura regular.

Figura 3.3: Trecho de p´agina com estrutura regular.

Nesse passo do pr´e-processamento s˜ao podados os ´ıtens que formam uma regi˜ao

com estrutura regular, de tal maneira que os conte´udos desses ´ıtens sejam direta-

mente ligado a uma ´unica tag, representando assim um ´unico bloco. Este processo

est´a representado na Figura 3.4, que cont´em o trecho da ´arvore DOM relativo ao

menu destacado na Figura 3.3. O sinal * ´e utilizado para indicar que uma regi˜ao

com estrutura regular foi podada.

(a) (b)

Figura 3.4: (a) N´os de uma ´arvore DOM com estrutura regular. (b) Resultado da

poda sobre a estrutura regular na mesma ´arvore DOM.

A id´eia de identiﬁcar regi˜oes com estruturas regulares em ´arvores DOM ´e bas-

tante comum na ´area de extra¸c˜ao de informa¸c˜ao [20, 21, 3]. A id´eia ´e que a

informa¸c˜ao a ser extra´ıda normalmente se encontra em uma ordem espec´ıﬁca, e

padr˜oes repetitivos podem ser encontrados na p´agina Web quando m´ultiplos regis-

tros est˜ao agrupados. Chang e Lui propuseram em [10] um algoritmo linear base-

ado em

Arvores Patricia [15] para identiﬁcar padr˜oes repetitivos, dada uma ´arvore

DOM como entrada. Algur e Hiremath [2] tamb´em lidaram com o problema de

identiﬁca¸c˜ao e extra¸c˜ao de informa¸c˜oes em documentos Web, buscando identiﬁcar

regi˜oes com estrutura regular a partir de informa¸c˜oes sobre a disposi¸c˜ao visual dos

elementos na p´agina.

3.3 Inser¸c˜ao de p´aginas Web na SOM

tree

A inser¸c˜ao de ´arvores DOM na SOM

tree

´e feita de maneira similar `a SST , por´em

com algumas diferen¸cas. Dada uma p´agina Web ρ, para inserir sua ´arvore DOM

na SOM

tree

, essa ´e percorrida em um percurso pr´e-ordem. A cada n´o η visitado,

o mesmo ´e inserido na SOM

tree

de acordo com o seu r´otulo. Ou seja, seu r´otulo

determina a sua posi¸c˜ao na SOM

tree

O r´otulo de um n´o ´e deﬁnido recursivamente pela concatena¸c˜ao de nomeTag, os

nomes de seus atributos e o r´otulo do seu n´o pai, separados por uma barra (”/”).

Atrav´es do r´otulo ´e poss´ıvel identiﬁcar unicamente cada n´o da ´arvore DOM. Por

exemplo, o r´otulo do n´o <table> na ´arvore DOM representada na Figura 3.5 ´e

"table/width/body/bgcolor/html".

Caso dois n´os irm˜aos possuam mesmo nomeTag e atributos, adiciona-se um

identiﬁcador sequencial ao in´ıcio do r´otulo, de modo a garantir que cada n´o de

uma ´arvore DOM tenha um r´otulo ´unico. Na Figura 3.5, abaixo do n´o <body>

existem dois n´os <div>, que possuem o mesmo atributo "id". Os r´otulos des-

ses dois n´os ser˜ao 1/div/id/body/bgcolor/html e 2/div/id/body/bgcolor/html,

respectivamente. O r´otulo do n´o <img> nessa ´arvore DOM, por sua vez, ser´a

img/border/2/div/id/body/bgcolor/html.

Figura 3.5: Exemplo de ´arvore DOM.

Ao inserir um n´o η na SOM

tree

, ´e veriﬁcado se esta j´a possui um n´o com o mesmo

r´otulo. De acordo com esta veriﬁca¸c˜ao, ser´a executado um dos seguintes passos:

• Caso j´a exista na SOM

tree

um n´o N que possua o mesmo label que η, o valor

de frequˆencia de N ´e incrementado em um. Se η possuir conte´udo textual

diretamente ligado a ele, o identiﬁcador dessa p´agina ´e adicionado `a docList

de N.

• Caso n˜ao seja encontrado nenhum n´o equivalente a η na SOM

tree

, um novo

n´o ´e criado. Ao criar este novo n´o, os valores de nomeTag, atributos e label

atribu´ıdos ao n´o s˜ao os mesmos de η, enquanto o valor de frequˆencia ´e iniciado

com 1. Se η n˜ao possuir conte´udo textual associado, docList ser´a iniciado com

uma lista vazia. Se possuir, docList ser´a iniciado com uma lista contendo um

´unico elemento, que ´e o identiﬁcador desta p´agina sendo inserida.

Para um melhor entendimento do processo de inser¸c˜ao de p´aginas Web na SOM

tree

tomemos como exemplo as p´aginas ρ

e ρ

da Figura 3.6. Ao inserir a p´agina ρ

uma SOM

tree

vazia, cada um de seus n´os, ao ser percorrido, gera um novo n´o com o

mesmo r´otulo. Observe que os n´os de ρ

que tamb´em est˜ao presentes na p´agina ρ

aparecem como um ´unico n´o na SOM

tree

, com frequˆencia 2. Os n´os que est˜ao em

apenas uma das p´aginas est˜ao presentes na SOM

tree

com frequˆencia 1.

Figura 3.6: SOM

tree

formada a partir de duas p´aginas Web.

3.4 Ajustamento da SOM

tree

Uma vez ﬁnalizada a cria¸c˜ao da SOM

tree

a partir das ´arvores DOM de todas

as p´aginas de um dado site, um processo de poda sobre ela ´e iniciado. Apesar de

um outro processo de poda j´a ter sido realizado sobre as ´arvores DOM, pequenas

diferen¸cas entre p´aginas com estrutura de blocos semelhantes podem permanecer

ap´os tal processo. Logo, ao adicionar essas diferen¸cas `a SOM

tree

, permite-se que

alguns block tags se fa¸cam presentes na SOM

tree

No processo de poda da SOM

tree

, esta ´e percorrida em um percurso p´os-ordem.

Sobre cada n´o, a poda ´e executada em dois passos, apresentados nas se¸c˜oes a seguir.

O objetivo desse processo ´e eliminar as block tags da SOM

tree

3.4.1 Poda de n´os com conte´udo aninhado

Ao inserir v´arias p´aginas na SOM

tree

, ´e poss´ıvel que alguns de seus n´os possuam

conte´udo de texto para algumas p´aginas e sejam, ao mesmo tempo, n´os internos

para outras p´aginas. Isso leva a uma situa¸c˜ao de conte´udo aninhado na SOM

tree

que pode ser causada por dois motivos distintos.

O primeiro motivo para haver aninhamento na SOM

tree

se deve a pequenas dife-

ren¸cas nas ´arvores DOM de p´aginas com estruturas de blocos semelhantes, levando

conte´udos que deveriam estar no mesmo n´o folha a estarem em folhas diferentes.

Para que a SOM

tree

possa resultar numa segmenta¸c˜ao coerente, ´e desej´avel que

essas diferen¸cas sejam removidas, de modo que blocos semelhantes possam ser reco-

nhecidos como pertencentes `a mesma classe.

A segunda raz˜ao para que essa condi¸c˜ao se d´e ´e quando os n´os que comp˜oem

o r´otulo de um bloco numa p´agina est˜ao contidos no r´otulo de um bloco de outra

p´agina com estrutura diferente daquela. Nesse caso, o aninhamento n˜ao deve ser

removido, uma vez que estes blocos fazem parte de block classes diferentes.

A primeira etapa de poda da SOM

tree

visa eliminar pequenas diferen¸cas nos seus

n´os, causadas por aninhamento de conte´udos decorrentes do primeiro motivo citado

acima. Entretanto, devido `a segunda poss´ıvel raz˜ao para aninhamentos na SOM

tree

n˜ao podemos assumir que todo conte´udo aninhado deve ser removido da mesma.

Para efetuar a poda de conte´udos aninhados, tentando evitar que esta opera¸c˜ao

seja realizada para casos da segunda op¸c˜ao, esta s´o ser´a realizada sobre n´os que este-

jam pr´oximos. Essa distˆancia ´e medida pela diferen¸ca entre as profundidades desses

n´os. O limiar α deﬁne a distˆancia m´axima para que dois n´os sejam considerados

pr´oximos. Logo, dois n´os com conte´udo aninhado somente ser˜ao submetidos a este

passo de poda se sua distˆancia for menor do que α.

Tome como exemplo a inser¸c˜ao de uma nova p´agina ρ

na SOM

tree

deﬁnida na

Figura 3.6. Esse processo pode ser visualizado na Figura 3.7. Ap´os a p´agina ρ

ser inserida na SOM

tree

, essa passa a possuir conte´udo aninhado entre o n´o <div>

e seus ﬁlhos. Para eliminar esse conte´udo aninhado, os n´os ﬁlhos de <div> ser˜ao

mesclados a ele. Desse modo, a docList de cada um dos n´os ﬁlhos ser´a movida para

a sua docList, e esses n´os s˜ao removidos da SOM

tree

Figura 3.7: SOM

tree

com conte´udo aninhado ap´os inser¸c˜ao de uma nova p´agina,

submetida ao processo de poda.

3.4.2 Poda de n´os pela frequˆencia

No segundo passo do processo de poda busca-se estabelecer uma frequˆencia

m´ınima desejada para os n´os e eliminar aqueles com frequˆencia menor a este limiar.

O objetivo deste limiar ´e garantir que as block classes geradas sejam estat´ısticamente

relevantes para o m´etodo segrank, uma vez que classes com poucos blocos podem

produzir informa¸c˜oes estat´ısticas inexatas para o c´alculo de seus pesos [14].

Ao atingir um n´o N, o processo de poda ir´a veriﬁcar se todos os seus ﬁlhos

possuem frequˆencia inferior a um dado limiar β. Em caso aﬁrmativo, a docList de

cada n´o abaixo de N ser´a unida `a sua docList, e tais n´os s˜ao ent˜ao removidos da

SOM

tree

, conforme podemos observar no exemplo da Figura 3.8(a). Tal exigˆencia,

de somente serem podados n´os com frequˆencia abaixo de β se todos os seus n´os

irm˜aos tamb´em possu´ırem frequˆencia abaixo deste limiar, visa evitar que sejam

gerados novos n´os com conte´udo aninhado. Isso, entretanto, leva `a possibilidade

de que alguns n´os com frequˆencia inferior a β permane¸cam na SOM

tree

. Esse caso

pode ser observado na Figura 3.8(b). Por´em, os experimentos realizados mostraram

que a quantidade de blocos pertencentes a block classes com frequˆencia abaixo desse

limiar foi pequena, e n˜ao se mostrou capaz de inﬂuenciar os resultados.

div

...

#12

...

a b

div

...

pre

...

(a)

div

...

pre

#80

...

(b)

Figura 3.8: Exemplos de poda sobre a SOM

tree

com β = 8. (a) Poda executada

sobre n´os com frequˆencia menor que β. (b) Poda n˜ao pode ser executada pois a

frequˆencia de um dos n´os ´e menor que β.

4 EXPERIMENTOS

Para a avalia¸c˜ao da qualidade da segmenta¸c˜ao resultante do m´etodo SOM

tree

foram analisados dois diferentes aspectos. O primeiro aspecto analisado ´e o qu˜ao

pr´oxima ´e a segmenta¸c˜ao autom´atica da percep¸c˜ao que um usu´ario tem em rela¸c˜ao

aos blocos que comp˜oe uma p´agina. O outro aspecto avaliado ´e o desempenho desta

segmenta¸c˜ao nos resultados de ranking obtidos pelo m´etodo segrank. A partir da

an´alise dessas diferentes perspectivas, ´e poss´ıvel termos uma vis˜ao mais clara das

possibilidades de utiliza¸c˜ao do m´etodo de segmenta¸c˜ao autom´atica aqui estudado.

4.1 Conﬁgura¸c˜ao dos Experimentos

4.1.1 Cole¸c˜oes

Foram realizados experimentos em quatro cole¸c˜oes diferentes: CNN, IG, CNET

e BLOGS. A cole¸c˜ao CNN cont´em 16.257 p´aginas com conte´udo em inglˆes coletadas

do site de not´ıcias da rede CNN. A cole¸c˜ao IG cont´em 34.460 p´aginas em portuguˆes

coletadas de trˆes sites do portal www.ig.com.br. A cole¸c˜ao CNET cont´em 352.770

p´aginas em inglˆes coletadas de quatro sites do portal www.cnet.com. Por ﬁm, a

cole¸c˜ao BLOGS cont´em 54.055 p´aginas em inglˆes coletadas de nove blogs populares,

de acordo com o ´ındice de popularidade de blogs dispon´ıvel em technorati.com. A

Tabela 4.1 descreve estas cole¸c˜oes de maneira mais detalhada.

Com o intuito de reproduzir a percep¸c˜ao dos usu´arios quanto `a divis˜ao em

blocos destas p´aginas, todas estas cole¸c˜oes foram segmentadas de maneira semi-

supervisionada com o aux´ılio de um especialista, conforme descrito em [14]. No pri-

CNN

Site P´aginas

News www.cnn.com 16.257

Total 16.257

BLOGS

Site P´aginas

Boing Boing www.boingboing.net 14.173

CNET news.cnet.comtech-blogs 8.054

Engadget www.engadget.com 6.343

Gizmodo us.gizmodo.com 4.454

Google googlelog.blogspot.com 1.050

Life Hacker www.lifehacker.com 3.997

Mashable www.mashable.com 7.410

Slash Film www.slashﬁlm.com 5.376

Tech Crunch www.techcrunch.com 3.198

Total 54.055

CNET

Site P´aginas

News www.news.com 131.474

Downloads www.downloads.com 99.186

Reviews reviews.cnet.com 64.142

Shopper www.shopper.com 57.968

Total 352.770

Site P´aginas

News www.ultimosegundo.com.br 26.466

Forum www.jornaldedebates.com.br 6.389

Recipe www.panelinha.com.br 1.605

Total 34.460

Tabela 4.1: Distribui¸c˜ao das p´aginas por cole¸c˜ao.

meiro passo desse processo as p´aginas s˜ao manualmente agrupadas de acordo com

a similaridade de sua estrutura interna. No segundo passo, utiliza-se o algoritmo

VIPS para segmentar as p´aginas de cada agrupamento. Para cada agrupamento

de p´aginas ´e realizada uma sele¸c˜ao manual dos parˆametros do VIPS. Por ﬁm, o

usu´ario especilista veriﬁca a segmenta¸c˜ao realizada pelo VIPS e, caso n˜ao concorde,

ele adapta a divis˜ao de blocos de acordo com a sua percep¸c˜ao. Como esse processo

semi-supervisionado tem forte interven¸c˜ao manual, dizemos que essa segmenta¸c˜ao ´e

manual.

4.1.2 Limiares utilizados na segmenta¸c˜ao autom´atica das cole¸c˜oes

O processo de poda da SOM

tree

descrito na se¸c˜ao 3.4 requer dois limiares, α e

β, para a sua realiza¸c˜ao.

O limiar α, que determina a distˆancia m´axima para que dois n´os com conte´udo

aninhado sejam podados, foi deﬁnido empiricamente atrav´es de experimentos de

treino. O valor de α utilizado nos experimentos deste trabalho foi 6.

O valor de β, que estabelece um limite m´ınimo para a quantidades de blocos

em uma block class, foi deﬁnido de acordo com a demanda do m´etodo de ranking

segrank. Estudos emp´ıricos realizados sobre o segrank demonstraram que a quan-

tidade m´ınima de blocos considerada estatisticamente relevante para o c´alculo dos

pesos das classes ´e 8 [14, 13]. Logo, utilizamos o valor 8 para β, para garantir que

as classes de blocos geradas s˜ao aplic´aveis a tal m´etodo.

4.2 An´alise da Segmenta¸c˜ao Autom´atica

A Tabela 4.2 mostra a quantidade de block classes e blocos gerados para cada

cole¸c˜ao, tanto na segmenta¸c˜ao manual de referˆencia como na segmenta¸c˜ao au-

tom´atica.

SEG. MANUAL SEG. AUTOM

ATICA

Block Total de Block Total de Blocos em BC

Cole¸c˜ao P´aginas Classes Blocos Classes Blocos com freq < β

CNN 16.257 158 257.139 1.945 597.301 1.911 (0,32%)

IG 34.460 246 406.965 1.095 1.404.512 1.109 (0,08%)

CNET 352.770 373 4,812.129 7.587 25.458.565 7.678 (0,03%)

BLOGS 54.055 161 1,042.624 1.383 2.149.039 1.029 (0,05%)

Tabela 4.2: Quantidade de p´aginas por cole¸c˜ao, block classes e total de blocos

obtidos nas segmenta¸c˜oes manual e autom´atica e quantidade de blocos na seg-

menta¸c˜ao autom´atica observados em block classes (BC ) com frequˆencia abaixo do

limiar (f req < β).

Podemos observar que a quantidade de blocos gerados pelo m´etodo autom´atico

foi signiﬁcativamente superior `a quantidade gerada pela segmenta¸c˜ao manual. Ao

analisar as raz˜oes para a grande diferen¸ca na quantidade de blocos gerados pela

segmenta¸c˜ao autom´atica e pela segmenta¸c˜ao manual, observamos que o principal

motivo ´e a presen¸ca de pequenos detalhes e diferen¸cas entre p´aginas, que um humano

pode facilmente perceber e ignorar, mas que o algoritmo n˜ao pode, uma vez que ´e

baseado na forma como estes trechos s˜ao alocados na ´arvore DOM.

Na cole¸c˜ao CNN pode-se observar que, apesar da pequena quantidade de p´aginas

na cole¸c˜ao, a quantidade de block classes geradas pela segmenta¸c˜ao autom´atica foi

relativamente alta, quando comparada `a quantidade de block classes obtidas nas

outras cole¸c˜oes. Ao analisarmos as p´aginas de not´ıcia da cole¸c˜ao CNN, podemos

veriﬁcar que estas cont´em tabelas, gr´aﬁcos, fotos e outros componentes ilustrativos

em diferentes partes do texto. Isso faz com que alguns blocos com a mesma fun¸c˜ao

na cole¸c˜ao sejam alocados em block classes diferentes.

A quantidade de block classes na segmenta¸c˜ao autom´atica sobre a cole¸c˜ao CNET

apresentou uma diferen¸ca signiﬁcativa em rela¸c˜ao `a quantidade obtida atrav´es da

segmenta¸c˜ao manual. Ao avaliar estes resultados veriﬁcamos que algumas irregula-

ridades na estrutura DOM de algumas de suas p´aginas impedem que o processo de

segmenta¸c˜ao identiﬁque corretamente regi˜oes com estruturas regulares (veja se¸c˜ao

3.2.2). Na segmenta¸c˜ao manual isso n˜ao representou um problema, uma vez que

essas irregularidades n˜ao s˜ao percept´ıveis visualmente.

Ainda na Tabela 4.2, podemos veriﬁcar a existˆencia de blocos pertencentes a

block classes com frequˆencia inferior a β. Esses dados podem ser observados na

´ultima coluna da tabela. Tais ocorrˆencias se devem `a restri¸c˜ao presente na etapa

de poda da SOM

tree

, onde n´os com frequˆencia inferior a β s´o podem ser podados

caso todos os seus n´os irm˜aos tamb´em possuam frequˆencia inferior a β, conforme

descrito na se¸c˜ao 3.4.2. Entretanto, podemos observar que os percentuais de blocos

pertencentes a block classes nessa condi¸c˜ao em cada cole¸c˜ao ´e pequeno. A cole¸c˜ao

CNN foi a que apresentou o maior percentual, com aproximadamente 0,32%. As

cole¸c˜oes IG, CNET e BLOGS tiveram percentuais consideravelmente baixos, o que

evidencia um impacto insigniﬁcante desses blocos na segmenta¸c˜ao.

4.3 Compara¸c˜ao entre segmenta¸c˜ao manual e autom´atica

Apesar da motiva¸c˜ao principal da segmenta¸cao autom´atica pela SOM

tree

ser

voltada para m´etodos de ranking baseados em blocos, a divis˜ao em blocos obtida

por este pode ser aplic´avel a outras ´areas em que uma segmenta¸c˜ao pr´oxima da per-

cep¸c˜ao que o usu´ario tem como ideal seja necess´aria. Para avaliar a veracidade dessa

aﬁrma¸c˜ao, utilizamos as m´etricas

Indice de Rand Ajustado (AdjRand) e Informa¸c˜ao

M´utua Normalizada (NMI ), apresentadas na se¸c˜ao 4.3.

Como referˆencia para compara¸c˜ao, implementamos o m´etodo Block fusion, em

sua varia¸c˜ao Rule-Based (BF-RuleBased). Tal m´etodo, proposto por Kohlsch¨utter

e Nejdl, ´e apresentado na se¸c˜ao 1.2.

Para cada m´etodo de segmenta¸c˜ao, SOM

tree

e BF-RuleBased, foram calcula-

dos os valores de AdjRand e NMI em cada p´agina das quatro cole¸c˜oes utilizadas

nos experimentos. Na Tabela 4.3 podemos ver as m´edias das m´etricas AdjRand e

NMI para os dois m´etodos de segmenta¸c˜ao, calculadas sobres as p´aginas das quatro

SOM

tree

BF-RuleBased

CNN

AdjRand 0,8497 0,6108

NMI 0,8736 0,7695

AdjRand 0,8311 0,7281

NMI 0,8951 0,8415

CNET

AdjRand 0,5007 0,3457

NMI 0,7293 0,6732

BLOGS

AdjRand 0,8241 0,4872

NMI 0,8660 0,7391

Tabela 4.3: Valores m´edios de AdjRand e NMI sobre as p´aginas segmentadas com

SOM

tree

e BF-RuleBased nas 4 bases (IG, CNN, BLOGS e CNET).

cole¸c˜oes utilizadas nos experimentos.

E facil observar que a segmenta¸c˜ao obtida

pela SOM

tree

apresentou desempenho signiﬁcativamente superior `a obtida atrav´es

do BF-RuleBased.

Os valores m´edios das duas m´etricas para a SOM

tree

exibidos na tabela 4.3

mostram que o grau de concordˆancia entre os blocos obtidos pela segmenta¸c˜ao au-

tom´atica e pela segmenta¸c˜ao de referˆencia ´e elevado. Isso demonstra que mesmo

havendo uma grande diferen¸ca na quantidade de blocos geradas pela SOM

tree

pela segmenta¸c˜ao manual, a maioria dos blocos obtidos na segmenta¸c˜ao autom´atica

s˜ao equivalentes aos obtidos na segmenta¸c˜ao manual.

E interessante se observar que nas bases CNN, IG e BLOGS os valores m´edios de

AdjRand e NMI para a segmenta¸c˜ao com a SOM

tree

foram bastante pr´oximos, en-

quanto que os valores para a cole¸c˜ao CNET foram sobremaneira inferiores. Apesar de

os resultados para o m´etodo BF-RuleBased n˜ao terem sido t˜ao homogˆeneos, tamb´em

observou-se que o valor m´edio das m´etricas para a cole¸c˜ao da CNET tamb´em foi

inferior aos veriﬁcados nas outras cole¸c˜oes. Uma das raz˜oes para tal desempenho

na cole¸c˜ao CNET se deve `as irregularidades presente em suas p´aginas, conforme

discutido na se¸c˜ao 4.2.

Nas Figuras 4.1 e 4.2 podemos observar o comportamento dos dois m´etodos de

segmenta¸c˜ao autom´atica, SOM

tree

e BF-RuleBased, atrav´es das m´etricas AdjRand

e NMI , respectivamente. Para cada m´etrica, foram desenhados quatro gr´aﬁcos, um

para cada cole¸c˜ao (IG, CNN, CNET e BLOGS), demonstrando o desempenho dos

dois m´etodos de segmenta¸c˜ao. Cada m´etodo de segmenta¸c˜ao tem seu desempenho

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 2000 4000 6000 8000 10000 12000 14000 16000 18000

adjRand

Pages

Adjusted Rand Index: CNN COLLECTION

SOM Tree

Rule-based Blockfusion

(a)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 5000 10000 15000 20000 25000 30000 35000

adjRand

Pages

Adjusted Rand Index: IG COLLECTION

SOM Tree

Rule-based Blockfusion

(b)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 50000 100000 150000 200000 250000 300000 350000 400000

adjRand

Pages

Adjusted Rand Index: CNET COLLECTION

SOM Tree

Rule-based Blockfusion

(c)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 10000 20000 30000 40000 50000 60000

adjRand

Pages

Adjusted Rand Index: BLOGS COLLECTION

SOM Tree

Rule-based Blockfusion

(d)

Figura 4.1: Compara¸c˜ao da m´etrica AdjRand nas segmenta¸c˜oes realizadas com os

m´etodos SOM

tree

e BF-RuleBased, sobre as bases CNN, IG, CNET e BLOGS.

em uma cole¸c˜ao evidenciado atrav´es de uma das curvas. Logo, cada curva denota

o desempenho de um dos m´etodos de segmenta¸c˜ao, atrav´es de uma determinada

m´etrica, em uma dada cole¸c˜ao.

Para tra¸car a curva representando o desempenho de um m´etodo de segmenta¸c˜ao,

foram utilizados os c´alculos da m´etrica avaliando seu resultado sobre cada p´agina da

cole¸c˜ao, ordenando-as em ordem crescente pelo valor da m´etrica. Para cada p´agina

da cole¸c˜ao marcamos uma coordenada (x, y), onde x representa a ordem da p´agina,

e o y representa o valor da m´etrica calculada para esta p´agina.

Assim como observado na Tabela 4.3, os gr´aﬁcos exibidos nas Figuras 4.1 e

4.2 demonstram que a segmenta¸c˜ao realizada pela SOM

tree

superou a segmenta¸c˜ao

realizada pelo m´etodo BF-RuleBased. Atrav´es destes gr´aﬁcos podemos entender

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 2000 4000 6000 8000 10000 12000 14000 16000 18000

NMI

Pages

Normalized Mutual Information: CNN COLLECTION

SOM Tree

Rule-based Blockfusion

(a)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 5000 10000 15000 20000 25000 30000 35000

NMI

Pages

Normalized Mutual Information: IG COLLECTION

SOM Tree

Rule-based Blockfusion

(b)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 50000 100000 150000 200000 250000 300000 350000 400000

NMI

Pages

Normalized Mutual Information: CNET COLLECTION

SOM Tree

Rule-based Blockfusion

(c)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 10000 20000 30000 40000 50000 60000

NMI

Pages

Normalized Mutual Information: BLOGS COLLECTION

SOM Tree

Rule-based Blockfusion

(d)

Figura 4.2: Compara¸c˜ao da m´etrica NMI nas segmenta¸c˜oes realizadas com os

m´etodos SOM

tree

e BF-RuleBased, sobre as bases CNN, IG, CNET e BLOGS.

melhor como cada cole¸c˜ao se comportou para cada um dos algoritmos.

A cole¸c˜ao em que os algoritmos tiveram a maior diferen¸ca de performance foi a

cole¸c˜ao BLOGS. No gr´aﬁco presente na Figura 4.1(d) podemos observar que apro-

ximadamente 7.000 p´aginas da cole¸c˜ao BLOGS obtiveram valores de AdjRand infe-

riores a 0,7 para a SOM

tree

, enquanto que mais de 36.000 p´aginas tiveram AdjRand

inferior a esse valor para o BF-RuleBased. Para a m´etrica NMI observa-se um com-

portamento semelhante, conforme Figura 4.2(d). Cerca de 1.000 p´aginas tiveram

valor de NMI inferior a 0,7 para a segmenta¸c˜ao da cole¸c˜ao BLOGS com a SOM

tree

enquanto aproximadamente 17.000 est˜ao abaixo de 0,7 para o BF-RuleBased.

Na base CNN as curvas para as m´etricas AdjRand e NMI , apresentadas nas

Figuras 4.1(a) e 4.2(a), tamb´em mostram uma superioridade signiﬁcativa da seg-

menta¸c˜ao utilizando a SOM

tree

. Para a m´etrica NMI , por exemplo, a segmenta¸c˜ao

com a SOM

tree

resultou em menos de 500 p´aginas com valor abaixo de 0,7, conforme

observado da Figura 4.2(a). A segmenta¸c˜ao realizada pelo m´etodo BF-RuleBased

resultou em aproximadamente 5.000 p´aginas nessa condi¸c˜ao.

A cole¸c˜ao IG, por sua vez, mostrou um comportamento pr´oximo para os dois

algoritmos, conforme podemos veriﬁcar nas curvas mostradas nas Figuras 4.1(b) e

4.2(b), mas com a SOM

tree

ainda mostrando um desempenho superior. Na Figura

4.1(b) observamos poucas p´aginas com AdjRand inferior a 0,6 para a segmenta¸cao

com a SOM

tree

, enquanto que para o BF-RuleBased a quantidade de p´aginas nessa

condi¸c˜ao ´e aproximadamente 9.000.

De forma similar ao que j´a observamos anteriormente, podemos veriﬁcar nos

gr´aﬁcos das Figuras 4.1(c) e 4.2(c) que os resultados de ambos os algoritmos para a

cole¸c˜ao CNET apresentaram desempenho mais baixo do que para as outras cole¸c˜oes.

Ainda assim, a segmenta¸c˜ao atrav´es da SOM

tree

apresentou melhor performance,

conforme se pode observar nesses gr´aﬁcos.

4.4 Avalia¸c˜ao do impacto da segmenta¸c˜ao autom´atica para

ranking baseado em blocos

Para analisar a qualidade da segmenta¸c˜ao autom´atica para o m´etodo de ranking

segrank, foram comparadas as seguintes conﬁgura¸c˜oes:

• BM25 - Utiliza BM25 de maneira direta, sem considerar a estrutura das

p´aginas.

• segrank - manual - Utiliza o segrank mesclado ao BM25, com a segmenta¸c˜ao

manual.

• segrank - SOM

tree

- Utiliza o segrank mesclado ao BM25, com a segmenta¸c˜ao

autom´atica obtida atrav´es da SOM

tree

Nas conﬁgura¸c˜oes em que o segrank foi utilizado em conjunto com o BM25,

usou-se uma vers˜ao do BM25 estendida para incorporar o fator ClassImportance do

segrank, descrito na se¸c˜ao 2.3.2. Esta vers˜ao estendida do BM25 ´e apresentada com

maiores detalhes em [13].

As m´etricas utilizadas para mensurar a qualidade do c´alculo de ranking para

cada uma dessas conﬁgura¸c˜oes foram as seguintes:

1. MAP (Mean Average Precision) - A AP (average precision ou precis˜ao

m´edia) ´e calculada pela m´edia das precis˜oes computadas sobre o ponto em

que cada documento relevante ´e encontrado, de acordo com a ordem obtida

pelo ranking para uma dada consulta. O MAP ´e a m´edia dos valores de AP

obtidos para um conjunto de consultas.

2. P@10 (Precision at 10) - Mede a quantidade de documentos relevantes nas

10 respostas com maior ranking.

BM25 Manual SOM

tree

Cole¸c˜ao P@10 MAP P@10 MAP P@10 MAP

CNN 0,612 0,691 0,642 0,786 0,630 0,779

IG 0,594 0,621 0,667 0,749 0,659 0,733

CNET 0,476 0,458 0,552 0,498 0,512 0,470

BLOGS 0,584 0,644 0,604 0,678 0,602 0,677

Tabela 4.4: Valores de P@10 e MAP sobre o c´alculo de ranking utilizando o modelo

BM25 tradicional e utilizando o segrank nas 4 bases (IG, CNN, BLOGS e CNET)

para as segmenta¸c˜oes manual e com SOM

tree

Ao utilizar os resultados da segmenta¸c˜ao autom´atica com o segrank, pode-se

observar que os resultados de busca ﬁcaram superiores aos resultados de m´aquinas de

busca convencionais, demonstrado aqui pelo BM25, e muito pr´oximos dos resultados

obtidos com segmenta¸c˜ao manual, conforme pode ser observado na Tabela 4.4.

Estes resultados evidenciam que a SOM

tree

foi muito bem sucedida em prover

segmenta¸c˜ao de p´aginas para o segrank, apesar da diferen¸ca na quantidade de block

classes entre a segmenta¸c˜ao autom´atica obtida com a SOM

tree

e a segmenta¸c˜ao

realizada por um especialista.

5 CONCLUS

Este trabalho se propˆos a estudar e avaliar um novo m´etodo de segmenta¸c˜ao

autom´atica de p´aginas Web, chamado SOM

tree

, Esse m´etodo foi apresentado em [13]

e ´e capaz de particionar p´aginas em blocos, de acordo com a modelagem necess´aria

para o sistema de ranking baseado em blocos proposta em [14, 13]. Os experimentos

mostraram que, ao utilizar a segmenta¸c˜ao obtida atrav´es da SOM

tree

como entrada

para o sistema de ranking baseado em blocos, os resultados ﬁcaram muito pr´oximos

aos obtidos utilizando a segmenta¸c˜ao de referˆencia.

Enquanto grande parte dos m´etodos de segmenta¸c˜ao de p´aginas Web encontrados

na literatura baseiam-se em caracter´ısticas soﬁsticadas, como informa¸c˜aoes visuais,

densidade de texto, distˆancia de n´os, entre outros, a segmenta¸c˜ao pela SOM

tree

caracteriza pela simplicidade de sua proposta. Ele se baseia apenas em heur´ısticas

simples aplicadas sobre a ´arvore DOM e sobre a ´arvore denominada SOM

tree

Ao avaliar a segmenta¸c˜ao obtida por meio de m´etricas de avalia¸c˜ao de algor´ıtmos

de clustering, a segmenta¸c˜ao atrav´es da SOM

tree

obteve ´ındices expressivos, supe-

riores, inclusive, ao m´etodo Block fusion, proposto por Kohlsch¨utter e Nejdl [19].

Apesar da principal motiva¸c˜ao deste trabalho ser a segmenta¸c˜ao de p´aginas Web

para problemas de ranking baseado em blocos, essas m´etricas demostraram que a

segmenta¸c˜ao proposta pode ser utilizada para outros ﬁns.

Um dos diferenciais da segmenta¸c˜ao autom´atica pela SOM

tree

´e que uma p´agina

n˜ao ´e segmentada isoladamente. Como a estrutura DOM de todas as p´aginas s˜ao

relacionadas durante esse processo, isso leva a uma segmenta¸c˜ao mais coesa. Ou

seja, p´aginas com estrutura semelhante tendem a ter segmenta¸c˜oes similares.

5.1 Trabalhos Futuros

O processo de segmenta¸c˜ao utiliza dois limiares, α e β, para a sua execu¸c˜ao.

E importante que se realize um estudo mais aprofundado sobre o impacto dessas

vari´aveis, de modo a se descobrir um valor ´otimo para cada uma.

O mecanismo de segmenta¸c˜ao aqui proposto tem como principal motiva¸c˜ao a sua

aplica¸c˜ao para m´etodos de ranking baseado em blocos. Entretanto, ele foi apenas

testado com o m´etodo de ranking proposto em [14]. Uma avalia¸c˜ao da sua utiliza¸c˜ao

com outros m´etodos precisa ser realizado, de modo que este possa ser consolidado

como um mecanismo vi´avel e de bom desempenho para tais m´etodos.

Um dos problemas na atualidade que mais tem demandado esfor¸cos relaciona-

dos a segmenta¸c˜ao de p´aginas Web ´e a navega¸c˜ao em dispositivos m´oveis com tela

reduzida, como celulares, tablets, palmtops e outros. Os m´etodos de segmenta¸c˜ao

aplicados para este ﬁm que encontramos na literatura realizam a segmenta¸c˜ao no

pr´oprio dispositivo do usu´ario. Ao ler no dispositivo uma p´agina Web de um site,

esta ´e segmentada, os blocos considerados importantes para serem exibidos s˜ao sele-

cionados, uma nova p´agina modiﬁcada ´e criada e s´o ent˜ao a nova p´agina ´e carregada

no navegador. Apesar deste tipo de abordagem ter a vantagem de poder segmentar

e exibir p´aginas de qualquer site, ela possui algumas desvantagens. Uma delas ´e que

a p´agina s´o come¸ca a ser exibida quando ela ´e toda carregada, segmentada e modi-

ﬁcada. Al´em disso, a realiza¸c˜ao deste processo no dispositivo do usu´ario pode levar

a problema de consumo de recursos. Um outro problema nesta abordagem ´e que

um provedor de conte´udo n˜ao tem qualquer garantia que suas p´aginas podem ser

vistas de maneira adequada nestes dispositivos, uma vez que ele n˜ao tem qualquer

controle sobre a utiliza¸c˜ao ou n˜ao destes mecanismos por parte dos usu´arios.

A utiliza¸c˜ao da segmenta¸c˜ao atrav´es da SOM

tree

para a visualiza¸c˜ao de p´aginas

em dispositivos com tela pequena apresenta um novo paradigma para este problema.

Diferente das abordagens que encontramos na literatura, a segmenta¸c˜ao e sele¸c˜ao

de blocos a serem exibidos devem ser realizadas no pr´oprio site. A aplica¸c˜ao desta

nova abordagem pode ser de grande utilidade para portais e provedores de conte´udo

Web, que podem ter suas p´aginas vistas de maneira adequada nestes dispositivos,

independente do usu´ario usar ou n˜ao algum mecanismo especial para este ﬁm. Para

o usu´ario esta ´e uma opera¸c˜ao transparente, uma vez que o processo ocorre total-

mente no servidor. A principal lacuna a ser explorada para esta abordagem est´a nos

m´etodos utilizados para sele¸c˜ao e ordena¸c˜ao dos blocos das p´aginas a serem exibidos

para o usu´ario. Tais m´etodos podem envolver desde os c´alculos de importˆancia de

blocos apresentados em [14] at´e t´ecnicas de aprendizado de m´aquina.

REFER

ENCIAS

[1] Document object model (dom). http://www.w3.org/DOM, 2005.

[2] Siddu P. Algur and P. S. Hiremath. Extraction of ﬂat and nested data records

from web pages. In Proceedings of the ﬁfth Australasian conference on Data

mining and analystics - Volume 61, AusDM ’06, pages 163–168, Darlinghurst,

Australia, Australia, 2006. Australian Computer Society, Inc.

[3] Manuel

Alvarez, Alberto Pan, Juan Raposo, Fernando Bellas, and Fidel Ca-

cheda. Extracting lists of data records from semi-structured web pages. Data

Knowl. Eng., 64:491–509, February 2008.

[4] Ricardo A. Baeza-Yates and Berthier Ribeiro-Neto. Modern Information Re-

trieval. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA,

1999.

[5] Shumeet Baluja. Browsing on small screens: recasting web-page segmentation

into an eﬃcient machine learning framework. In Proc. of 15th WWW Confe-

rence, pages 33–42, New York, NY, USA, 2006. ACM.

[6] Yevgen Borodin, Jalal Mahmud, and I.V. Ramakrishnan. Context browsing

with mobiles - when less is more. In MobiSys ’07: Proceedings of the 5th

international conference on Mobile systems, applications and services, pages

3–15, New York, NY, USA, 2007. ACM Press.

[7] D. Cai, S. Yu, J.-R. Wen, and W.-Y. Ma. Vips: a vision-based page segmenta-

tion algorithm. Technical Report MSR-TR-2003-79, Microsoft, 2003.

[8] Deng Cai, Shipeng Yu, Ji-Rong Wen, and Wei-Ying Ma. Block-based web

search. In SIGIR ’04: Proceedings of the 27th annual international ACM SIGIR

conference on Research and development in information retrieval, pages 456–

463, New York, NY, USA, 2004. ACM Press.

[9] Deepayan Chakrabarti, Ravi Kumar, and Kunal Punera. A graph-theoretic

approach to webpage segmentation. In WWW ’08: Proceeding of the 17th

international conference on World Wide Web, pages 377–386, New York, NY,

USA, 2008. ACM.

[10] Chia-Hui Chang and Shao-Chen Lui. Iepad: information extraction based on

pattern discovery. In Proceedings of the 10th international conference on World

Wide Web, WWW ’01, pages 681–688, New York, NY, USA, 2001. ACM.

[11] Yu Chen, Wei-Ying Ma, and Hong-Jiang Zhang. Detecting web page structure

for adaptive viewing on small form factor devices. In Proc. of 12th WWW

Conference, pages 225–233, New York, NY, USA, 2003. ACM.

[12] Fariza Fauzi, Jer-Lang Hong, and Mohammed Belkhatir. Webpage segmen-

tation for extracting images and their surrounding contextual information. In

Proceedings of the seventeen ACM international conference on Multimedia, MM

’09, pages 649–652, New York, NY, USA, 2009. ACM.

[13] David Fernandes. Uso de Informa¸c˜ao Estrutural para Melhorar Qualidade de

Busca em Cole¸c˜oes Web. PhD thesis, Universidade Federal de Minas Gerais,

2010.

[14] David Fernandes, Edleno S. de Moura, Berthier Ribeiro-Neto, Altigran S.

da Silva, and Marcos Andr´e Gon¸calves. Computing block importance for sear-

ching on web sites. In Proc. of 16th ACM CIKM, pages 165–174, New York,

NY, USA, 2007. ACM.

[15] William B. Frakes and Ricardo Baeza-Yates, editors. Information retrieval:

data structures and algorithms. Prentice-Hall, Inc., Upper Saddle River, NJ,

USA, 1992.

[16] Gen Hattori, Keiichiro Hoashi, Kazunori Matsumoto, and Fumiaki Sugaya.

Robust web page segmentation for mobile terminal using content-distances and

page layout information. In WWW ’07: Proceedings of the 16th international

conference on World Wide Web, pages 361–370, New York, NY, USA, 2007.

ACM Press.

[17] L. Hubert and P. Arabie. Comparing partitions. Journal of Classiﬁcation, 1985.

[18] Jinbeom Kang and Joongmin Choi. Detecting informative web page blocks for

eﬃcient information extraction using visual block segmentation. In ISITC ’07:

Proceedings of the 2007 International Symposium on Information Technology

Convergence, pages 306–310, Washington, DC, USA, 2007. IEEE Computer

Society.

[19] Christian Kohlsch¨utter and Wolfgang Nejdl. A densitometric approach to web

page segmentation. In CIKM ’08: Proceeding of the 17th ACM conference

on Information and knowledge management, pages 1173–1182, New York, NY,

USA, 2008. ACM.

[20] Bing Liu, Robert Grossman, and Yanhong Zhai. Mining data records in web

pages. In Proceedings of the ninth ACM SIGKDD international conference on

Knowledge discovery and data mining, KDD ’03, pages 601–606, New York,

NY, USA, 2003. ACM.

[21] Rupesh R. Mehta, Pabitra Mitra, and Harish Karnick. Extracting semantic

structure of web documents using content and visual information. In Special

interest tracks and posters of the 14th international conference on World Wide

Web, WWW ’05, pages 928–929, New York, NY, USA, 2005. ACM.

[22] Kai Simon and Georg Lausen. Viper: augmenting automatic information ex-

traction with visual perceptions. In CIKM ’05: Proceedings of the 14th ACM in-

ternational conference on Information and knowledge management, pages 381–

388, New York, NY, USA, 2005. ACM Press.

[23] Ruihua Song, Haifeng Liu, Ji-Rong Wen, and Wei-Ying Ma. Learning block

importance models for web pages. In WWW ’04: Proceedings of the 13th

international conference on World Wide Web, pages 203–211, New York, NY,

USA, 2004. ACM Press.

[24] Alexander Strehl and Joydeep Ghosh. Cluster ensembles – a knowledge reuse

framework for combining multiple partitions. Journal on Machine Learning

Research (JMLR), 3:583–617, December 2002.

[25] Matthijs J. Warrens. On the equivalence of cohen’s kappa and the hubert-arabie

adjusted rand index. J. Classif., 25(2):177–183, 2008.

[26] Xiangye Xiao, Qiong Luo, Dan Hong, Hongbo Fu, Xing Xie, and Wei-Ying

Ma. Browsing on small displays by transforming web pages into hierarchically

structured subpages. ACM Trans. Web, 3:4:1–4:36, January 2009.

[27] Xing Xie, Chong Wang, Li-Qun Chen, and Wei-Ying Ma. An adaptive web

page layout structure for small devices. Multimedia Syst., 11(1):34–44, 2005.

[28] Xin Yang and Yuanchun Shi. Enhanced gestalt theory guided web page seg-

mentation for mobile browsing. In Proceedings of the 2009 IEEE/WIC/ACM

International Joint Conference on Web Intelligence and Intelligent Agent Te-

chnology - Volume 03, WI-IAT ’09, pages 46–49, Washington, DC, USA, 2009.

IEEE Computer Society.

[29] Xin Yang, Peifeng Xiang, and Yuanchun Shi. Finding user’s interest blocks

using signiﬁcant implicit evidence for web browsing on small screen devices.

World Wide Web, 12:213–234, June 2009.

[30] Lan Yi, Bing Liu, and Xiaoli Li. Eliminating noisy information in web pages

for data mining. In Proc. of 9th ACM SIGKDD, pages 296–305, New York,

NY, USA, 2003. ACM.

[31] Shipeng Yu, Deng Cai, Ji-Rong Wen, and Wei-Ying Ma. Improving pseudo-

relevance feedback in web information retrieval using web page segmentation.

In WWW ’03: Proceedings of the 12th international conference on World Wide

Web, pages 11–18, New York, NY, USA, 2003. ACM.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 