Upload
truongkhue
View
217
Download
0
Embed Size (px)
Citation preview
Técnicas para Remoção de Links Não Informativos
André Manuel Arsénio de Brito
Dissertação para Obtenção do Grau de Mestre em
Engenharia Informática e de Computadores
Júri
Presidente: Prof. José Manuel Nunes Salvador Tribolet
Orientador: Prof. Pável Pereira Calado
Vogal: Profa Ana Margarida de Jesus Cardoso Cachopo
Setembro de 2008
Agradecimentos
Em primeiro lugar gostaria de agradecer ao meu orientador, Prof. Pável Calado, pelo esforço e empenho
neste trabalho. A sua liderança manteve-me focado e motivado na procura de melhores soluções e na
realização de um trabalho com qualidade.
Em segundo lugar, agradeço ao Prof. Andreas Wichert a sugestão de utilização de um processo de
clustering, que revelou ser o método mais e�caz para a detecção de links não informativos.
Finalmente, agradeço a todos os meus colegas e professores com quem tive contacto durante o curso
e que me acompanharam neste jornada inesquecível de cinco anos.
Abstract
The existence of spam in the web drastically reduces its usability and the user's experience. Further-
more, it has a negative impact in search engines' performances, which tend to present irrelevant results
as a consequence of the usage of the spam techniques used nowadays. In order to solve this problem, it
is necessary to be able to distinguish informative links and non-informative links. Unlike prior work in
this area, our work targets the detection of non-informative links and not just spam. Also, the fact that
we use a clustering method greatly increases our method's usability when compared to others.
In this work we propose three methods for automatic non-informative link detection, based on the
analysis of statistical features of the links between web pages: feature selection, where feature selection
methods for text categorization were adapted for web page categorization; classi�cation, using a linear
combination of features or a SVM classi�er; and clustering (CLUTO and k -means), where links are
separated in two classes � informative and non-informative.
The experiments with di�erent sized collections revealed that all the proposed methods, except the
feature selection method, proved e�ective in detecting non-informative links. Among all algorithms, k -
means has the greatest advantage, because, not only does it support large collections, but also it barely
requires human intervention to operate.
Keywords: Web, Spam, Detection, Non-Informative Links, Features, Clustering
Resumo
A existência de spam na web diminui signi�cativamente a sua usabilidade para os utilizadores. Além
disso, diminui também a performance dos motores de busca, que apresentam resultados pouco relevantes,
devido às diversas técnicas de manipulação existentes actualmente. Para combater este fenómeno, torna-se
necessário efectuar a distinção entre links informativos e links não informativos. Este trabalho distingue-
se de outros da mesma área pelo facto de se focar na detecção de links não informativos e não simplesmente
na detecção de spam (que é apenas um subconjunto). Além disso, a utilização de classi�cadores pela
maioria desses métodos diminui bastante a sua usabilidade, o que já não acontece no nosso caso, devido
ao uso de clustering.
Neste trabalho propomos três métodos distintos para a detecção automática de links não informativos,
com base na análise de características estatísticas dos links existentes entre páginas web: selecção de
features, em que métodos de selecção de features de texto são adaptados à selecção de links na web;
classi�cação, através de uma combinação linear de features ou de um classi�cador SVM; e clustering
(CLUTO e k -means), em que os links são separados em duas classes � informativos e não informativos.
Os testes realizados com colecções de diversos tamanhos revelaram que todos os métodos, com excep-
ção do método de selecção de features, são e�cazes na detecção de links não informativos. O algoritmo
k -means apresenta a maior vantagem pelo facto de suportar colecções grandes e de ser o algoritmo que
requer menor intervenção humana.
Palavras-Chave: Web, Spam, Detecção, Links Não Informativos, Features, Clustering
Técnicas para Remoção de Links Não
Informativos
i
Conteúdo
1 Introdução 1
1.1 Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Conceitos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Categorização de Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Selecção de Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 Análise de Conectividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Trabalhos Relacionados 9
2.1 Detecção de Spam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Detecção Baseada no Conteúdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Detecção Baseada na Estrutura de Links . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Remoção de Spam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 Detecção de Links Não Informativos 19
3.1 Selecção de Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Link Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.1 Features da Página . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.2 Features do Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Classi�cação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Combinação Linear de Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.2 Classi�cador SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4.1 Repeated Bisections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4.2 k -Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4 Testes 36
4.1 Ambiente de Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.1 Colecções Usadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
ii
4.1.2 Medidas Usadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.3 Métodos de Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1.4 Testes Executados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.1 Selecção de Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.2 Classi�cação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.3 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2.4 PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3 Discussão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5 Conclusão 66
5.1 Resumo geral do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2 Trabalho Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
iii
Lista de Figuras
2.1 3 -gramas independentes e condicionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Contraste entre uma link farm e uma página normal . . . . . . . . . . . . . . . . . . . . . 13
2.3 Estruturas de links ao nível do site . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1 Link entre páginas web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1 Interface web para classi�cação manual de links . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Distribuição dos valores das features na execução do algoritmo k -means na colecção WBR-99 57
4.3 Distribuição dos valores das features na execução do algoritmo k -means na colecção SS . . 59
4.4 Comparação dos tempos de execução dos algoritmos . . . . . . . . . . . . . . . . . . . . . 64
iv
Lista de Tabelas
3.1 Tabela de Contingência 2x2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Tabela de Contingência Generalizada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Tabela de Contingência Generalizada para Páginas web . . . . . . . . . . . . . . . . . . . 23
3.4 Relação entre palavras-chave e valores da feature Path Keywords . . . . . . . . . . . . . . 26
3.5 Exemplo de atribuição de pesos a features . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.1 CADE: Distribuição dos documentos pelas categorias . . . . . . . . . . . . . . . . . . . . . 38
4.2 Matriz de Confusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Testes à combinação linear: pesos das features . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 Resultados da medida MI com a colecção CADE2 . . . . . . . . . . . . . . . . . . . . . . . 47
4.5 Resultados da medida χ2 com a colecção CADE2 . . . . . . . . . . . . . . . . . . . . . . . 48
4.6 Resultados da medida MI com a colecção CADE6 . . . . . . . . . . . . . . . . . . . . . . . 49
4.7 Resultados da medida χ2 com a colecção CADE6 . . . . . . . . . . . . . . . . . . . . . . . 50
4.8 Resultados da combinação linear de features com a colecção SS . . . . . . . . . . . . . . . 51
4.9 Resultados da execução do SVM na colecção SS . . . . . . . . . . . . . . . . . . . . . . . . 52
4.10 Resultados do algoritmo CLUTO com a colecção SS . . . . . . . . . . . . . . . . . . . . . 54
4.11 Resultados do algoritmo k -means com a colecção WBR-99 . . . . . . . . . . . . . . . . . . 55
4.12 Resultados do algoritmo k -means com a colecção SS . . . . . . . . . . . . . . . . . . . . . 58
4.13 Resultados da execução do PageRank na colecção WBR-99 original . . . . . . . . . . . . . 60
4.14 Resultados da execução do PageRank na colecção WBR-99 (só links externos) . . . . . . . 60
4.15 Resultados da execução do PageRank na colecção WBR-99 (só links informativos) . . . . 61
4.16 Comparação dos métodos propostos para detecção de links não informativos . . . . . . . . 65
v
Lista de Abreviaturas
BMSR Bidirectional Mutual Site Reinforcement
CL Combinação Linear
CPC Category-Pivoted Categorization
DF Document Frequency
DPC Document-Pivoted Categorization
E Erro Quadrático
ESim Similaridade Externa
FN Falsos Negativos (False Negatives)
FP Falsos Positivos (False Positives)
HITS Hyperlink-Induced Topic Search
HSS Hidden Style Similarity
HTTP Hypertext Transfer Protocol
IG Information Gain
IP Internet Protocol
ISim Similaridade Interna
MI Mutual Information
MSR Mutual Site Reinforcement
SALSA Stochastic Approach for Link-Structure Analysis
SEO Search Engine Optimization
SLAbS Site Level Abnormal Support
SLLA Site Level Link Alliances
SVM Support Vector Machine
vi
TKC Tightly Knit Community
TN Verdadeiros Negativos (True Negatives)
TP Verdadeiros Positivos (True Positives)
TS Term Strength
UMSR Unidirectional Mutual Site Reinforcement
URL Uniform Resource Locator
vii
Capítulo 1
Introdução
Neste capítulo é descrito o contexto deste trabalho: a remoção de links não informativos, que diminuem
a usabilidade da web e a performance dos motores de busca. A hipótese que se pretende testar é se, ao
analisar certas características dos links entre páginas web, é ou não possível determinar automaticamente
se estes são informativos ou não informativos, para tarefas de Recuperação de Informação.
Apresentam-se ainda os conceitos básicos necessários à compreensão deste trabalho, nomeadamente
categorização de texto (decidir se um documento pertence ou não a uma dada categoria), selecção de
features (determinar quais as características que mais contribuem para a distinção entre documentos),
análise de conectividade (análise da informação da estrutura de links da web) e clustering (agrupamento
de objectos físicos ou abstractos em classes de objectos semelhantes).
1.1 Contexto
AWorld Wide Web (ou, simplesmente, web) é formada por um conjunto de páginas e hiperligações (links)
que interligam essas páginas. Um link entre duas páginas signi�ca, entre outras coisas, que o autor da
página de origem considera que a página de destino é relevante, ou seja, o link representa um voto de
con�ança por parte do autor da página de origem na qualidade da página de destino.
Existem vários algoritmos que exploram esta fonte de informação para �ns de pesquisa e classi�cação
[Bharat and Henzinger, 1998,Borodin et al., 2001,Lempel and Moran, 2000,Page et al., 1998], os quais
são usados principalmente por motores de busca, cuja tarefa é a procura de páginas relevantes sobre
um determinado tópico. Para efectuar pesquisas de páginas na web, os motores de busca recorrem à
informação sobre os links entre páginas para determinar quais as mais relevantes. Os resultados da
pesquisa são então apresentados ao utilizador por ordem de relevância.
Como a web representa um meio de comércio, se um vendedor conseguir angariar mais clientes através
dos motores de busca, terá consequentemente mais lucro. Neste sentido, existem cada vez mais formas de
aumentar arti�cialmente a probabilidade de uma página aparecer nos primeiros resultados de pesquisas.
Estas técnicas, designadas por Search Engine Optimization (SEO), compreendem métodos tais como a
adição de conteúdo (incoerente) às páginas web, a manipulação da estrutura de links entre as páginas,
1
entre outros. A prática de desenvolver páginas web cujo único propósito é aumentar a pontuação dessa
página, sem melhorar a sua utilidade para os utilizadores, designa-se por web spam, ou simplesmente,
spam.
O spam pode tomar diversas formas. As técnicas de spam actuais dividem-se em dois grupos: boosting
e hiding [Gyongyi and Garcia-Molina, 2005]. As técnicas de boosting têm como objectivo aumentar
a importância de uma página, alterando o seu conteúdo. Por exemplo, a inserção de termos (term
spamming) consiste na colocação propositada de termos não relacionados com o conteúdo da página para
que esta se torne relevante para determinadas procuras muito frequentes. Os termos introduzidos podem
ser repetidos várias vezes ao longo da página ou podem ser excertos de outros textos e podem também
ocupar diferentes áreas da página como o título, o corpo, o URL, etc. Outra forma de boosting consiste
na alteração da estrutura de links da página (link spamming) de forma a manipular os algoritmos que
analisam a web como um grafo. Esta técnica envolve a criação de links e estruturas de links que permitem
aumentar o valor de importância de uma página, por exemplo, criando entradas em blogs e forums com
links para a página ou criando estruturas complexas de páginas e links, designadas link farms.
Por sua vez, os métodos de hiding não in�uenciam directamente o rank da página, mas têm como
objectivo mascarar os métodos de boosting utilizados, para que os utilizadores que acedem à página não
se apercebam da sua presença. Isto pode ser feito de várias formas. Em primeiro lugar, no caso de term
spamming, pode-se esconder o texto, colorindo-o com a mesma cor de fundo da página, o que o torna
invisível para um humano. Existe também um método designado por cloaking, que consiste em ter duas
versões da página: uma para o utilizador (sem spam) e outra para o crawler1 (com spam) � o crawler
pode ser identi�cado via endereço IP (comparando com uma lista de endereços IP de crawlers conhecidos)
ou via análise do campo �user-agent� no pedido HTTP [Fielding et al., 1999]. Finalmente, pode ser usado
um mecanismo de redireccionamento imediato da página com spam para a página sem spam � o crawler
analisará apenas a página com spam, mas o utilizador não se apercebe da sua existência, porque só vê a
página sem spam.
Motivação
A existência de spam diminui signi�cativamente a usabilidade da web para os utilizadores. Além disso,
diminui também a performance dos motores de busca, que apresentam resultados pouco relevantes, devido
às técnicas de manipulação descritas acima.
Para combater este fenómeno, torna-se necessário efectuar a distinção entre links informativos e
links não informativos. Por informativo e não informativo, neste caso, referimo-nos à utilidade do link
em relação às necessidades de informação do utilizador. Em [Davison, 2000], Davison de�ne links não
informativos, ou nepotistic links, como links entre páginas que estão presentes por outras razões que não
o mérito, ou seja, links que representam um voto de con�ança ilegítimo por parte do autor da página de
origem em relação à página de destino. Esta de�nição engloba não só links de spam, mas também, por
1Um crawler (ou web crawler) é um programa ou um script automático que navega pela web de forma metódica e
automatizada com o objectivo (no caso dos motores de busca) de recolher versões actualizadas de páginas web para serem
indexadas.
2
exemplo, links de navegação. Por oposição, um link informativo, será um link entre duas páginas em que
é legítimo que a página de destino seja considerada mais relevante pelo facto de o link em questão existir.
Problema
Uma vez compreendida a importância da detecção de links não informativos, o problema que enfrentamos
é o de como identi�car esses links não informativos. Isto é, dado um link qualquer, como é que podemos
determinar se ele é um link informativo ou não informativo?
Proposta
A proposta para este trabalho é a aplicação de várias técnicas para descobrir links informativos e não
informativos automaticamente. De entre elas, destaca-se a proposta de aplicação de um algoritmo de
clustering para resolver o problema em questão. A hipótese que se pretende testar é a seguinte: analisando
certas características estatísticas dos links entre páginas web, é possível determinar automaticamente se
estes são informativos ou não informativos?
1.2 Conceitos Básicos
Nesta secção são descritos os conceitos básicos que suportam as várias técnicas de detecção e remoção
de spam estudadas. Nomeadamente, são apresentadas as características e métodos existentes para ca-
tegorização de texto, dando especial destaque às Support Vector Machines (SVM). Posteriormente são
apresentadas técnicas de selecção de features, como o document frequency e o information gain. Segui-
damente, fala-se de análise de conectividade, que consiste na utilização da estrutura de links entre as
páginas da web para obter informação adicional sobre uma página, informação essa que será utilizada
para determinar a importância e relevância da página relativamente a uma dada procura. Finalmente,
fala-se de clustering � agrupamento de objectos físicos ou abstractos em classes de objectos semelhantes
� dando especial atenção ao algoritmo k-means.
1.2.1 Categorização de Texto
A categorização de um documento consiste em decidir se ele pertence ou não a uma dada categoria.
Existem vários algoritmos que permitem categorizar documentos automaticamente num conjunto de
categorias prede�nido � árvores de decisão, redes neuronais [Sebastiani, 2002] e Support Vector Machines
[Joachims, 1998, Joachims et al., 2001] são alguns exemplos. A maior parte destes métodos baseia-se
apenas no conteúdo dos documentos para efectuar a sua decisão, não recorrendo a outras fontes de
informação, como a estrutura da página ou os links entre páginas.
A categorização de texto tem várias propriedades [Sebastiani, 2002], descritas de seguida:
• Single-lable / Multi-lable: a categorização pode ser single-lable, se um documento só pode pertencer
a uma categoria, ou multi-lable, se o documento pode pertencer a várias categorias simultaneamente.
3
Um caso especial de classi�cação single-lable é a classi�cação binária (binary) em que um documento
ou está numa categoria c ou está no seu complemento c̄;
• Category-Pivoted Categorization (CPC) / Document-Pivoted Categorization (DPC): os resultados
da categorização podem ser ordenados por categoria (CPC ) � permite saber quais os documentos
que pertencem a uma dada categoria � ou por documento (DPC ) � permite saber quais as
categorias a que um documento pertence;
• Hard Categorization / Ranking Categorization: a decisão de atribuição de um documento a uma
categoria pode ser tomada imediatamente (hard) ou pode ser feita uma lista com as probabilidades
de um documento pertencer às várias categorias, que depois é ordenada e usada para tomar a
decisão �nal (ranking).
Um classi�cador é um algoritmo que determina, para cada par (documento, categoria), se o documento
pertence ou não a essa categoria. O classi�cador necessita de uma amostra previamente classi�cada
para efectuar o treino da sua base de conhecimento. Trata-se portanto de um método de aprendizagem
supervisionada [Mitchell, 1997]. Essa amostra é dividida em duas partes: um conjunto de treino que
é usado pelo classi�cador para aprender e treinar a classi�cação; e um conjunto de teste, que permite
determinar a correcção do classi�cador.
Os classi�cadores podem ser de vários tipos, tais como probabilísticos, árvores de decisão, métodos
de regressão, redes neuronais, entre outros.
Support Vector Machines
Support Vector Machines (SVMs) são um método de classi�cação proposto por Vapnik em 1995 [Vapnik,
1995]. Mais recentemente, foram utilizadas com sucesso na classi�cação de documentos [Joachims, 1998,
Joachims et al., 2001]. Os documentos a classi�car são representados no espaço vectorial e a ideia é
encontrar o hiper-plano nesse espaço que melhor separa duas categorias. No entanto, nem sempre é
possível dividir perfeitamente o espaço, nomeadamente, quando a amostra não é linearmente separável.
Neste caso, é necessário encontrar o hiper-plano nesse espaço que melhor separa as duas categorias com
o menor erro possível.
Com este método, cada documento da amostra é atribuído a uma de duas categorias. No caso de
existirem múltiplas categorias, terá que existir um classi�cador distinto para cada categoria, sendo a
decisão �nal tomada tendo em conta os resultados de cada categoria. As SVMs lidam e�cazmente com os
vários desa�os impostos pela representação vectorial de documentos, nomeadamente a grande dimensão
do espaço vectorial e o facto de que os vectores são muito esparsos. As SVMs apresentam resultados
superiores a outros métodos, devido principalmente à sua capacidade de generalização.
1.2.2 Selecção de Features
No âmbito da análise automática de documentos, a representação vectorial [Salton et al., 1975] é a forma
mais utilizada para os representar. Nesta representação, cada documento é visto como um ponto no
4
espaço de documentos, cujas coordenadas são obtidas através da atribuição de pesos a cada um dos
termos (features) presentes no documento. Assim, cada documento Di é representado por um vector de
t dimensões:
Di = (di1, di2, ..., dit) (1.1)
em que dij representa o peso atribuído ao termo j e t é o número de termos presentes em toda a colecção.
Naturalmente, numa colecção de muitos documentos existem bastantes termos distintos e, conse-
quentemente, estes vectores atingem dimensões enormes. Isto signi�ca que os algoritmos que usam esta
representação têm um peso computacional muito grande. Para resolver este problema, existem técnicas
de selecção de features que visam reduzir a dimensão do espaço vectorial através da eliminação de ter-
mos que pouco ou nada contribuem para a distinção entre documentos [Yang and Pedersen, 1997]. As
principais técnicas de selecção de features existentes para classi�cação de documentos são:
• Document Frequency (DF): para cada termo, calcula-se o valor de DF, que é simplesmente o número
de documentos em que o termo ocorre. A ideia é que termos muito raros são não informativos e
irrelevantes na categorização. Uma vez calculados os valores de DF de cada termo, removem-se os
termos cujo valor é inferior a um limite de�nido;
• Information Gain (IG): mede o número de bits de informação obtidos na categorização, de acordo
com a presença (ou não) de um termo, ou seja, determina se o facto de o termo estar ou não
presente, é ou não relevante para a categorização;
• Mutual Information (MI): afere a relação de co-ocorrência entre um termo e uma categoria, ou seja,
se sempre que um termo ocorre, o documento é classi�cado numa categoria e se sempre que o termo
não ocorre, o documento é classi�cado noutra categoria diferente, então o termo é relevante para a
classi�cação. Para generalizar este cálculo a todas as categorias, faz-se a média ou o máximo dos
valores de MI de cada termo;
• χ2: este método mede a falta de independência entre um termo e uma categoria e pode ser compa-
rado com a distribuição χ2 com um grau de liberdade. Tal como no MI, para combinar o valor do
termo em todas as categorias, faz-se a média ou o máximo;
• Term Strength (TS): este método recorre ao clustering de documentos para determinar a depen-
dência entre um termo e uma categoria � calcula qual a probabilidade de, se um termo t aparece
num documento y, ele também aparecer noutro documento x do mesmo cluster que o primeiro, ou
seja, P (t ∈ x | t ∈ y).
A combinação dos vários métodos de selecção de features apresenta melhores resultados do que cada
método individualmente [Olsson and Oard, 2006]. Existem várias formas de combinar os métodos de
selecção de features: maior resultado obtido em qualquer um dos métodos, menor resultado obtido em
qualquer um dos métodos, média dos resultados obtidos em qualquer um dos métodos, entre outros.
5
1.2.3 Análise de Conectividade
No âmbito da web, os documentos em análise (páginas da web) apresentam outra fonte de informação
além do seu conteúdo: os links entre páginas. A existência de um link entre duas páginas signi�ca,
idealmente, que o autor da página de origem do link considera que a página de destino do link é relevante.
Existem vários algoritmos que exploram esta fonte de informação para �ns de pesquisa e classi�cação,
nomeadamente, PageRank [Page et al., 1998], HITS [Kleinberg, 1999,Bharat and Henzinger, 1998,Borodin
et al., 2001] e SALSA [Lempel and Moran, 2000]. Estes algoritmos são usados principalmente por motores
de busca, cuja tarefa é a procura de páginas relevantes sobre um determinado tópico de pesquisa.
O algoritmo HITS (Hyperlink-Induced Topic Search) baseia-se em dois conceitos: hub e authority. A
ideia é que uma página web que aponta para muitas outras é um bom hub e uma página que é apontada
por muitas outras é uma boa authority. Para determinar quais são os melhores hubs e authorities para
uma dada procura, o algoritmo parte de um conjunto de páginas que contêm todos os termos de procura,
juntando-lhe páginas que ligam ou são ligadas pelas páginas presentes no conjunto inicial. Estas páginas
e os respectivos links formam então um grafo em que os nós são as páginas web e os arcos são os links.
O algoritmo percorre o grafo aleatoriamente e atribui valores de authority (de acordo com os links de
entrada da página) e hub (de acordo com os links de saída da página) a cada página até atingir um estado
de convergência.
O HITS é vulnerável ao efeito de TKC (Tightly Knit Community), que são pequenos conjuntos
de páginas web fortemente interligadas. Isto leva a que estas páginas obtenham, erradamente, valores
de hub e authority muito elevados. Para minimizar este problema, foi proposto um outro algoritmo, o
SALSA (Stochastic Approach for Link-Structure Analysis), que percorre o grafo de forma diferente. Neste
algoritmo, o grafo é percorrido escolhendo dois links simultaneamente: um para a frente (link de saída)
e outro para trás (link de entrada). O SALSA minimiza, embora não elimine o efeito TKC.
Tanto o HITS como o SALSA percorrem apenas o conjunto de páginas assumidas como relevantes
para a procura com base no seu texto. Contrariamente, o PageRank calcula o valor de importância de
cada página independentemente da procura, percorrendo assim todo o grafo da web. Tal como nos dois
algoritmos anteriores, o PageRank baseia-se apenas na estrutura de links entre as páginas, ignorando o seu
conteúdo. Neste algoritmo, uma página terá maior valor de importância se tiver um link de outra página
considerada importante. Ou seja, o algoritmo não considera apenas a quantidade de links de entrada,
mas também a sua qualidade. O valor de importância de uma página (rank) é calculado recursivamente
sendo demonstrável que converge para um conjunto �xo de valores. Desta forma, os ranks de cada página
são calculados previamente e, quando se pretende fazer uma procura, seleccionam-se todas as páginas
que contêm todos os termos da procura, e ordenam-se pelo valor de PageRank, ou por uma combinação
deste com o valor de um algoritmo baseado em conteúdo textual.
Ainda no campo da análise da estrutura de links da web, é possível categorizar websites analisando
apenas o grafo da web e a estrutura do site, independentemente do seu conteúdo e URL [Amitay et al.,
2003]. Características como o número de links de entrada e de saída por página, a quantidade de links
internos e externos, a quantidade de páginas, a profundidade das páginas, entre outros, são factores
determinantes para a categorização de um site.
6
Todos estes algoritmos estão sujeitos a técnicas de manipulação, cujo objectivo é aumentar arti�cial-
mente o rank de uma página.
1.2.4 Clustering
O processo de agrupamento de objectos físicos ou abstractos em classes de objectos semelhantes denomina-
se clustering. Um cluster é um conjunto de objectos que são semelhantes entre si e que não são semelhantes
aos objectos de outros clusters. Embora a classi�cação seja um processo e�ciente de distinção de grupos e
classes de objectos, é necessária a prévia classi�cação de um conjunto de treino, o que se torna custoso em
colecções de grande dimensão. O clustering, por sua vez, é um processo de aprendizagem sem supervisão,
não sendo por isso necessária a existência de classes prede�nidas nem de conjuntos de treino [Han and
Kamber, 2006].
No âmbito de data mining, os requisitos típicos de clustering são:
• Escalabilidade;
• Capacidade de lidar com diversos tipos de atributos (numéricos, binários, categóricos, etc.);
• Descoberta de clusters com formas arbitrárias;
• Capacidade de lidar com ruído nos dados;
• Alta dimensionalidade;
Para calcular a semelhança entre dois pontos de dados, os algoritmos recorrem a uma medida de
similaridade. Uma medida de similaridade permite computar a similaridade entre dois documentos di e
dj . Existem dois métodos bem conhecidos para calcular a similaridade entre dois documentos. O primeiro
é o co-seno do ângulo entre os vectores como proposto por Salton em [Salton, 1989]:
cos(~di, ~dj
)=
~diT ~dj∥∥∥~di∥∥∥∥∥∥~dj∥∥∥ (1.2)
em que ~di = (xi1, xi2, ..., xit) e ~dj = (xj1, xj2, ..., xjt) são dois objectos de t-dimensões, ~diTé a
transposição de ~di,∥∥∥~di∥∥∥ é a norma euclidiana2 de ~di e
∥∥∥~dj∥∥∥ é a norma euclidiana de ~dj . Esta medida
tem valor 1 quando os documentos são idênticos e tem valor 0 quando os documentos são ortogonais.
O segundo método é a distância euclidiana (dist):
dist(~di, ~dj
)=√
(xi1 − xj1)2 + (xi2 − xj2)2 + ... + (xit − xjt)2 (1.3)
em que ~di = (xi1, xi2, ..., xit) e ~dj = (xj1, xj2, ..., xjt) são dois objectos de t-dimensões. Esta medida
tem valor 0 quando os documentos são idênticos [Han and Kamber, 2006].
Os métodos de clustering podem realizar a sua tarefa de diversas formas e, por isso, podem ser
divididos em várias categorias:
2A norma euclidiana de um vector ~x = (x1, x2, . . . , xt) de�ne-se como ‖~x‖ =√∑t
i=1 xi2.
7
• Métodos de particionamento: dado um conjunto de n objectos, um método de particionamento
divide o conjunto em k partições, sendo que cada partição representa um cluster e k ≤ n.
• Métodos hierárquicos: criam uma decomposição hierárquica do conjunto de dados. Os métodos
podem ser classi�cados como aglomerativos ou divisivos, dependendo da forma como realizam a
decomposição hierárquica.
• Métodos baseados em densidade: ao contrário da maioria dos métodos de partição que se baseiam
na distância entre objectos para fazerem clustering, os métodos baseados em densidade recorrem à
noção de densidade. A ideia é continuar a expandir um dado cluster até que a densidade (quantidade
de objectos) na vizinhança seja superior a um limite. Estes métodos permitem encontrar clusters
com formas arbitrárias.
• Métodos baseados em grelha (grid-based): estes métodos dividem o espaço dos objectos num número
�nito de células que formam uma grelha. Todas as operações de clustering são realizadas nesta
grelha. A vantagem destes métodos em relação aos outros é a rapidez de processamento, que é
independente do número de dados, dependendo apenas do número de células da grelha em cada
dimensão do espaço.
• Métodos baseados em modelos: de�nem um modelo para cada cluster e procuram a melhor combi-
nação dos dados com os modelos.
O Algoritmo k-Means
O algoritmo k-means é um método de clustering por particionamento, que recebe um parâmetro k,
especi�cando o número de clusters pretendidos e particiona um conjunto de n objectos em k clusters.
O objectivo do algoritmo é agrupar os objectos em clusters, de forma a maximizar a semelhança entre
objectos do mesmo cluster � similaridade intracluster � e, ao mesmo tempo, minimizar a semelhança
entre objectos de diferentes clusters � similaridade intercluster. A similaridade é medida em relação ao
centro de gravidade do cluster � o centroide [Han and Kamber, 2006].
O algoritmo k -means funciona da seguinte forma. Em primeiro lugar, o algoritmo selecciona aleato-
riamente k objectos, sendo que cada um deles será o centroide inicial de um cluster. Para os restantes
objectos, cada um será atribuído ao cluster cujo centroide estiver mais próximo, ou seja, aquele com o
qual tem maior similaridade. De seguida, calculam-se as novas coordenadas do centroide de cada cluster,
realizando a média das coordenadas de todos os pontos que pertencem a esse cluster. Este processo
continua até o algoritmo convergir, o que só acontece quando a variação do valor da função de custo de
duas iterações consecutivas for menor que um dado limite. A função de custo normalmente utilizada é o
erro quadrático:
E =k∑i=1
∑p∈Ci
dist(p, ci)2 (1.4)
em que E é o somatório dos erros quadráticos de todos os objectos da colecção, p é um ponto no espaço
que representa um objecto, ci é o centroide do cluster Ci e dist é a distância euclidiana entre p e ci [Han
and Kamber, 2006].
8
Capítulo 2
Trabalhos Relacionados
Neste capítulo são apresentados trabalhos realizados na área da detecção e remoção de spam na web. As
técnicas de detecção de spam na web podem ser divididas em duas categorias: baseadas no conteúdo e
baseadas na estrutura de links. Os métodos baseados no conteúdo analisam exclusivamente o conteúdo
da página, ignorando informação sobre a estrutura de links. Por sua vez, os métodos de detecção de spam
baseados na estrutura de links têm como objectivo detectar spam que incide na manipulação da estrutura
de links e que não seria detectado por uma análise restrita ao conteúdo das páginas web. Finalmente,
são descritas formas de actuar sobre o spam detectado que passam pela remoção dos links ou páginas
considerados spam, ou pela aplicação de uma penalização a esses links ou páginas.
2.1 Detecção de Spam
As várias técnicas de detecção de spam na web podem ser divididas em duas categorias: baseadas no con-
teúdo e baseadas na estrutura de links. Na secção seguinte apresentam-se alguns trabalhos representativos
de ambas as técnicas.
2.1.1 Detecção Baseada no Conteúdo
Os métodos de detecção de spam baseados no conteúdo analisam exclusivamente o conteúdo da página,
ignorando informação sobre a estrutura de links. A maioria destes métodos recorre a classi�cadores
semelhantes aos que são utilizados para classi�car texto, que neste caso são adaptados para classi�car
páginas web.
Em [Ntoulas et al., 2006] é apresentado um conjunto de heurísticas para detecção de spam com base
apenas no conteúdo das páginas web. Estas heurísticas são:
• Domínio: são apresentados resultados que demonstram que páginas de domínio .biz são maiorita-
riamente spam e páginas de domínio .edu não apresentam spam;
• Língua: o idioma da página � páginas em francês são 25% spam, em alemão 22% e em inglês 16%;
9
Figura 2.1: 3 -gramas independentes (à esquerda); 3 -gramas condicionais (à direita).
• Número de palavras na página: as páginas de spam têm naturalmente mais palavras do que uma
página legítima, devido ao uso da técnica de term spamming ;
• Número de palavras no título da página: tal como na heurística anterior, as páginas de spam
apresentam títulos consideravelmente maiores do que uma página legítima;
• Tamanho médio das palavras: tendo em conta que os utilizadores cometem erros ortográ�cos, os
spammers recorrem à concatenação de palavras-chave para explorar essa situação e conseguir que
a página de spam esteja presente em mais resultados de procuras. Desta forma, é provável que
páginas cujo tamanho médio das palavras é elevado sejam páginas de spam;
• Quantidade de texto dos links: como os motores de busca têm em conta a descrição do link (anchor
text) ao realizarem a procura, os spammers exploram isso criando páginas que contêm apenas links
e a respectiva descrição. Assim, estas páginas de spam são, na sua maioria, compostas por texto
de links, o que as distingue de outras páginas;
• Percentagem de conteúdo visível: as técnicas de spam contemplam também o conteúdo invisível das
páginas e, consequentemente, as páginas de spam têm mais conteúdo invisível do que as páginas
legítimas;
• Rácio de compressão: esta heurística destina-se a detectar situações de réplica do conteúdo de
páginas, que permitem que a página obtenha rank mais alto em motores de busca que têm em conta
a quantidade de vezes que um termo da procura aparece na página. Ao efectuar a compressão de
uma página, quanto mais conteúdo replicado houver, maior será o rácio de compressão (tamanho
da página descomprimida dividido pelo tamanho da página comprimida);
• Presença de palavras comuns: as técnicas de term spamming focam-se principalmente na coloca-
ção de palavras-chave, o que leva a que, em páginas de spam, existam poucas palavras comuns
(stop-words), ou seja, conjunções, determinantes, etc. Assim, é possível detectar páginas de spam,
determinando a fraca presença de palavras comuns na página � páginas de spam terão poucas
palavras comuns;
• Percentagem de palavras comuns: a heurística anterior apenas testa se cada palavra comum existe
(ou não) na página. Por sua vez, esta heurística pretende determinar o rácio entre as ocorrências
de cada termo comum e o número total de palavras;
• Probabilidade independente de n-gramas: esta heurística pretende analisar a correcção gramatical
das páginas, uma vez que as páginas de spam terão certamente incorrecções gramaticais, derivado
10
do uso das várias técnicas de spam apresentadas. A ideia é analisar as páginas, dividindo-as em n-
gramas (sequências de palavras) independentes (sem sobreposição) de n palavras consecutivas (ver
Figura 2.1, esquerda) e determinar a frequência de cada n-grama, dividindo o número de ocorrências
do n-grama pelo número total de n-gramas. As páginas de spam apresentam tanto valores muito
altos (devido à repetição de termos) como muito baixos (devido à improbabilidade da repetição de
texto aleatório);
• Probabilidade condicional de n-gramas: embora a heurística anterior seja mais simpli�cada devido
ao facto de analisar n-gramas independentes, pode no entanto ser incorrecta. Para efectuar o
cálculo de forma correcta, é necessário que haja sobreposição dos n-gramas, calculando então a
probabilidade do n-grama condicionada à observação da palavra anterior (ver Figura 2.1, direita).
O uso de cada heurística separadamente não é su�ciente para detectar spam e�cazmente, mas a
conjunção de todas essas heurísticas apresenta bons resultados. Nos testes efectuados, foi utilizado um
classi�cador de árvore de decisão C4.5 [Quinlan, 1993], que usa simultaneamente as várias heurísticas
descritas acima. Este classi�cador toma uma decisão binária sobre cada página, classi�cando-a como spam
ou não spam. O classi�cador apresenta resultados satisfatórios, conseguindo classi�car correctamente
95.4% das páginas presentes numa amostra de cerca de 100 milhões de páginas web.
Em [Fetterly et al., 2004] sugere-se um método de detecção de spam através da análise estatística de
características das páginas. A ideia base é que certas páginas de spam, particularmente as que são geradas
automaticamente, distinguem-se de outras páginas por uma série de características, como por exemplo,
o URL, o conteúdo da página, a evolução do conteúdo da página, entre outros. As características mais
relevantes que se focam no conteúdo das páginas são:
• Propriedades do URL: páginas cujo host name1 contém muitos caracteres, pontos, traços e dígitos
são provavelmente páginas de spam.
• Propriedades do conteúdo: páginas geradas automaticamente são bastante semelhantes e obedecem
a um padrão facilmente detectável através de, por exemplo, clustering.
• Propriedades da evolução do conteúdo: através da medição da evolução do conteúdo de uma página
web é possível identi�car páginas de spam que são geradas automaticamente em resposta a um
pedido, uma vez que a evolução do conteúdo dessas páginas é distintamente alta.
Em [Fetterly et al., 2005] descrevem-se várias técnicas de detecção de duplicação de frases que per-
mitem detectar sites que contêm grandes quantidades de páginas de spam geradas automaticamente e
permite também estimar quão original é o conteúdo de uma página web ou de um site. O método descrito
consiste na aplicação de um algoritmo de clustering a todas as páginas, sendo que cada classe (cluster)
contém todas as páginas que são exacta ou aproximadamente duplicadas das outras páginas dessa classe.
As conclusões da aplicação deste método a duas colecções foram as seguintes:
1. A frequência de frases na web, tal como a frequência de palavras, segue um distribuição quadrática;
1O host name é de�nido como a parte do URL da página web que está depois do pre�xo http:// e que termina na primeira
�/� encontrada de seguida. Por exemplo, dado o URL http://www.ist.utl.pt/html/ensino/, o host name será www.ist.utl.pt.
11
2. A maioria das frases populares (sequência de palavras consecutivas que aparece em pelo menos
cinco páginas web) não são interessantes � tratam-se normalmente de frases como a sequência dos
dias da semana, os meses do ano ou uma sequência de números;
3. Anúncios legais (por exemplo, �Copyright 2004 All rights reserved�) formam uma classe de frases
populares;
4. Frases de navegação (por exemplo, �prev date next thread prev�) revelam a estrutura base de uma
página, por exemplo, mailing list ou fórum de discussão;
5. Frases populares características de páginas de spam geradas automaticamente são normalmente
comuns a apenas um site ou a um conjunto de sites pertencentes à mesma entidade;
6. Mais de 90% das páginas das colecções testadas contêm pelo menos uma frase popular que partilham
com pelo menos 4 documentos distintos que não são exacta ou aproximadamente duplicados, sendo
este facto evidência de que a web contém bastante conteúdo replicado;
7. Páginas web com uma grande percentagem de frases não-originais apresentam tipicamente conteúdo
gerado automaticamente e têm maior probabilidade de serem páginas de spam do que páginas com
conteúdo predominantemente original e não-replicado.
Outra forma de detecção de spam com base no conteúdo das páginas web é apresentada em [Urvoy
et al., 2006] e recorre a uma medida de similaridade designada por Hidden Style Similarity (HSS),
calculada com base em características extra-textuais dos documentos. A primeira fase do algoritmo
proposto consiste no pré-processamento das páginas web, removendo todos os caracteres alfanuméricos
e retendo apenas o �ruído� HTML. De seguida, calcula-se o valor da medida de similaridade, bem como
a impressão digital da página. Finalmente, realiza-se o clustering das páginas recorrendo à medida de
similaridade. Este método permite agrupar páginas com base no template utilizado e no estilo de escrita,
o que possibilita a detecção de páginas de um determinado tipo, por exemplo, páginas de fóruns ou
páginas geradas automaticamente.
Relação com Este Trabalho
Este trabalho distingue-se dos métodos de detecção de spam baseados no conteúdo apresentados acima
por se basear principalmente na análise da estrutura de links entre as páginas. Embora também tenham
sido usadas algumas features baseadas no conteúdo das páginas, a análise é focada principalmente nos
links e na estrutura de links entre páginas web.
Além disso, os métodos aqui apresentados focam-se na remoção de spam e não propriamente na
remoção de links não informativos, que, como já vimos na introdução (secção 1.1), englobam não só
spam, mas também todos os links que estão presentes por outras razões que não o mérito.
Finalmente, devido ao uso de classi�cadores, alguns dos métodos apresentados acima requerem a
prévia classi�cação de uma amostra de páginas para suportar o seu funcionamento. Contrariamente, o
método apresentado neste trabalho recorre a um processo de clustering. Sendo o clustering um processo
12
de aprendizagem sem supervisão, elimina-se a necessidade de classi�car manualmente uma amostra, au-
mentando assim a sua usabilidade. Porém, é necessária a intervenção de um humano para determinar
qual dos clusters contém os links considerados informativos e qual o cluster que contém os links consi-
derados não informativos, mas o esforço requerido para esta tarefa é sem dúvida bastante menor que o
esforço de classi�car manualmente uma amostra de páginas web.
2.1.2 Detecção Baseada na Estrutura de Links
Figura 2.2: Contraste entre uma link farm (à esquerda) e uma página normal (à direita) [Becchetti et al.,
2006a].
Infelizmente, nem sempre é possível detectar spam através da análise do conteúdo das páginas, porque
algumas dessas páginas de spam diferem das páginas legítimas apenas na estrutura de links, apresentando
no entanto conteúdo idêntico [Becchetti et al., 2006a]. Exemplo disto são as link farms (Figura 2.2), que
manipulam a estrutura de links de um conjunto de páginas com o objectivo de aumentar o rank de uma
dessas páginas.
Em [Becchetti et al., 2006a] é apresentado um conjunto de métricas de caracterização de spam baseadas
na estrutura de links entre páginas, que podem ser usadas individualmente ou em conjunto. De seguida,
descrevem-se as mais importantes:
• Quantidade de links de entrada: páginas de spam terão muitos links de entrada, de forma a aumentar
o seu rank;
• Quantidade de links de saída: semelhante ao anterior, mas para links de saída;
• Reciprocidade de links: pretende-se medir se os links entre duas páginas A e B são apenas num sen-
tido (de A para B) ou em ambos (de A para B e de B para A). Páginas de spam terão naturalmente
valores de reciprocidade baixos;
13
• PageRank: distribuição dos valores de importância obtidos pelo algoritmo PageRank [Page et al.,
1998];
• TrustRank: o objectivo do TrustRank [Gyöngyi et al., 2004] é descobrir páginas suspeitas de spam,
ou seja, páginas que tenham um valor de PageRank alto, mas que não tenham relação com páginas
de con�ança prede�nidas;
• Truncated PageRank: Truncated PageRank [Becchetti et al., 2006b] é um algoritmo de ranking que
diminui o valor de importância dos vizinhos de uma página que estejam topologicamente perto dessa
página. Como as link farms têm pouca profundidade de links, este algoritmo pode ser adaptado à
detecção de spam utilizando uma função que remove a contribuição directa dos primeiros níveis de
links;
• Supporters: a página A é supporter da página B à distância d, se o menor caminho de A para B
no grafo da web tem tamanho d. O conjunto de supporters de uma página é composto por todas as
páginas que contribuem para o seu rank. Naturalmente, páginas de spam terão poucos supporters.
Logicamente, a combinação de todas estas métricas de caracterização de spam com base na estru-
tura de links demonstra melhores resultados do que cada uma das métricas utilizada individualmente.
Analisando os resultados, as dez melhores métricas combinadas são as seguintes:
1. Variável binária que indica se a página principal de um site é a página com maior valor de PageRank;
2. Reciprocidade de links;
3. Supporters à distância 4;
4. Supporters à distância 3;
5. Variação mínima de supporters;
6. Supporters à distância 2;
7. Valor de Truncated PageRank, dividido pelo valor de PageRank;
8. Valor de TrustRank dividido pelo valor de PageRank;
9. Supporters à distância 1;
10. Valor de Truncated PageRank à distância 2, dividido pelo valor de PageRank.
Em [Davison, 2000], Davison descreve uma série de setenta e cinco características que permitem
reconhecer links não informativos (nepotistic links), o que inclui não só spam, mas qualquer tipo de links
indesejados e irrelevantes para o cálculo do rank de uma página. Por exemplo, um site com links de
navegação e menus em todas as suas n páginas está a adicionar n links de entrada irrelevantes a cada
uma dessas páginas, aumentando consequentemente os respectivos ranks dessas mesmas páginas. As
características mais importantes para detectar estas situações são as seguintes:
• Título e descrição das páginas idênticos;
14
• Repetição parcial da descrição das páginas;
• Domínio igual;
• Host-names idênticos;
• Semelhança parcial ou total dos endereços IP das páginas;
• Semelhança parcial ou total dos URL's das páginas;
• Partilha de uma dada quantidade de links de saída;
• Domínios de alto nível (.com, .net, .org e .edu).
A combinação de todas as características usando um classi�cador apresenta resultados satisfatórios na
detecção de links não informativos, embora os testes tenham sido feitos com uma amostra muito pequena.
Seguindo a noção de supporter (página que contribui directamente � através de um link � para o
rank de uma outra página) apresentada anteriormente, o SpamRank [Benczúr et al., 2005] é um algoritmo
que mede a quantidade de valor de PageRank que uma página web recebe indevidamente. Tal como os
métodos anteriores, o SpamRank baseia-se apenas na estrutura de links. A ideia base deste método é que
não deverá existir uma dependência entre os supporters de uma página legítima, ou seja, os supporters
deverão estar distribuídos por fontes de diferente qualidade. Uma página que recebe o seu rank de muitas
páginas, todas elas com baixo rank, é considerada suspeita de spam. Este algoritmo tem três fases: a
primeira fase tem como objectivo detectar os supporters de cada página, através do algoritmo de Monte
Carlo [Fogaras and Rácz, 2004], que calcula o valor de suporte entre cada par de páginas interligadas; a
segunda fase é uma fase de penalização, em que cada página é penalizada de acordo com a quantidade
e in�uência dos supporters suspeitos; �nalmente, a terceira fase consiste na personalização do valor de
PageRank das páginas penalizadas. Este algoritmo revelou-se e�caz na detecção de páginas de spam.
Análise ao Nível do Site
Todos os métodos vistos até agora analisam a web ao nível da página, ou seja, analisam apenas os links
entre páginas, como unidades individuais e independentes. No entanto, há certas estruturas de links que
só podem ser detectadas numa análise feita ao nível do site e não página a página. Em [da Costa Carvalho
et al., 2006] são apresentadas três abordagens a este problema: identi�cação de situações de reforço mútuo
entre sites (Mutual Site Reinforcement � MSR); identi�cação de relações entre sites em que o valor de
PageRank de um desses sites deriva maioritariamente de um único outro site (Site Level Abnormal Support
� SLAbS); identi�cação de alianças entre sites que promovem arti�cialmente um outro site (Site Level
Link Alliances � SLLA).
A Figura 2.3.A demonstra um exemplo de MSR, em que os links existentes entre os sites criam uma
série de ciclos, o que leva ao aumento do rank das páginas de ambos os sites. Para detectar este tipo
de situações, é usada uma medida da densidade de links entre cada par de sites. Os links podem ser
considerados de forma unidireccional (UMSR) ou bidireccional (BMSR). Se o valor desta medida estiver
acima de um determinado limite, então os sites são identi�cados como um caso de MSR.
15
Figura 2.3: Estruturas de links ao nível do site: (A) MSR; (B) SLAbS; (C) SLLA [da Costa Carvalho
et al., 2006].
Um exemplo de SLAbS está ilustrado na Figura 2.3.B, em que os três sites aumentam o rank uns dos
outros através de uma cadeia de links entre eles. Esta situação pode ser detectada determinando quanto
é que cada site contribui para o rank de outro. Se este valor se encontrar acima de um determinado
limite, então essa é uma situação de SLAbS.
Finalmente, a Figura 2.3.C apresenta uma situação de SLLA, em que o rank de uma página é aumen-
tado por um conjunto de outras páginas que estão altamente interligadas. É proposta uma medida de
susceptibilidade que identi�ca este tipo de situações analisando os links de entrada da página em questão.
Os três métodos apresentam bons resultados individuais, destacando-se o SLLA que apresenta os
melhores resultados. A conjunção dos vários métodos (SLLA + BMSR + SLAbS) demonstra melhores
resultados do que qualquer um dos métodos individualmente. No entanto, estes métodos não substituem
a análise ao nível da página, que deverá ser usada em conjunção com os métodos apresentados.
Relação com Este Trabalho
Este trabalho, tal como os métodos de detecção de spam apresentados acima, foca-se na detecção de links
não informativos recorrendo a uma análise da estrutura de links entre páginas web, análise essa feita ao
nível da página. No entanto, este trabalho recorre também a algumas features baseadas no conteúdo
das páginas web, que são usadas em conjunção com as features baseadas na estrutura de links, com o
objectivo de melhorar o processo de detecção de links não informativos.
Com excepção do método de [Davison, 2000], os métodos aqui apresentados focam-se na remoção
de spam e não propriamente na remoção de links não informativos, que, como já vimos na introdução
(secção 1.1), englobam não só spam, mas também todos os links que estão presentes por outras razões
que não o mérito.
Finalmente, o que distingue este trabalho de outros (e principalmente do trabalho de [Davison, 2000])
é a utilização de um processo de aprendizagem sem supervisão, o clustering, que apresenta uma série de
16
vantagens já descritas.
2.2 Remoção de Spam
Reconhecendo a importância da detecção de spam, é igualmente importante penalizar ou, em alguns
casos, remover esse spam. Alguns dos métodos apresentados na secção 2.1, além de apresentarem formas
de detecção de spam, apresentam também formas de actuar sobre o spam detectado. Essas formas passam
por penalizar o rank das páginas envolvidas e, em alguns casos, proceder à sua remoção do cálculo dos
ranks.
No método de detecção de nepotistic links [Davison, 2000] são sugeridos três métodos distintos para
combater spam:
• Censura: manter uma lista negra de páginas que foram classi�cadas como spam;
• Pré-processamento: processo heurístico que �ltra links internos;
• Pós-processamento: ajustar os resultados de uma procura em que foram detectadas situações de
spam.
A abordagem escolhida consiste na utilização de pré-processamento, recorrendo às heurísticas apre-
sentadas para detectar links de spam e removê-los do cálculo dos ranks das páginas.
O SpamRank [Benczúr et al., 2005], por sua vez, não remove os links do cálculo dos ranks das páginas.
Em vez disso, é aplicada uma penalização aos links considerados suspeitos. O algoritmo atribui um valor
ρ ≤ 1 a cada página, que mede o grau de irregularidade dessa página (ρ = 1 signi�ca que a página
é regular). A penalização aplicada a cada página é proporcional a (ρ0 − ρ), em que ρ0 é um limite
prede�nido. Assim, quanto maior for o grau de irregularidade de uma página, maior será a penalização
aplicada.
Finalmente, o método de análise da estrutura de links ao nível do site [da Costa Carvalho et al., 2006]
apresenta também métodos de remoção e penalização de spam, descritos de seguida:
• MSR: quando a medida da densidade de links para um par de sites se encontra acima de um dado
limite, removem-se todos os links entre esses dois sites;
• SLAbS: tal como no MSR, sempre que a contribuição de um site para o rank de outro site se
encontrar acima de um dado limite, removem-se todos os links entre esses dois sites;
• SLLA: contrariamente ao MSR e ao SLAbS, o SLLA não remove os links de spam. Em vez disso,
é aplicada uma penalização ao rank das páginas envolvidas, penalização essa proporcional ao valor
de susceptibilidade calculado.
Relação com Este Trabalho
Neste trabalho, o processo de remoção dos links não informativos identi�cados está contemplado. A
abordagem escolhida consiste na utilização de pré-processamento, recorrendo a um conjunto de features
para detectar links não informativos e, posteriormente, removê-los do cálculo dos ranks das páginas.
17
2.3 Conclusão
Neste capítulo foram apresentados diversos métodos de detecção e remoção de spam, quer baseados no
conteúdo das páginas web, quer baseados na estrutura de links entre páginas web, tanto ao nível da
página, como ao nível do site. Este trabalho utiliza tanto métodos baseados no conteúdo, como métodos
baseados na estrutura de links, usando-os simultaneamente com o objectivo de melhorar o processo de
detecção de links não informativos.
Com excepção do trabalho de [Davison, 2000], os métodos apresentados neste capítulo focam-se na
remoção de spam e não propriamente na remoção de links não informativos, que englobam não só spam,
mas também todos os links que estão presentes por outras razões que não o mérito.
Devido ao uso de classi�cadores, a maioria dos métodos apresentados neste capítulo requer a prévia
classi�cação de uma amostra de páginas para suportar o seu funcionamento. Contrariamente, o método
apresentado neste trabalho recorre a um processo de clustering (aprendizagem sem supervisão), o que
elimina a necessidade de classi�car manualmente uma amostra e aumenta a sua usabilidade.
Este trabalho aborda também a remoção dos links não informativos identi�cados através de pré-
processamento, procedendo à remoção desses links do cálculo dos ranks das páginas.
18
Capítulo 3
Detecção de Links Não Informativos
Neste capítulo descreve-se o trabalho efectuado no sentido de detectar automaticamente links informativos
e links não informativos. São propostos três métodos distintos para a detecção de links não informativos:
selecção de features (secção 3.1), classi�cação (secção 3.3) e clustering (secção 3.4).
O método de selecção de features tem como objectivo adaptar os métodos de selecção de features de
texto à selecção de links na web e recorre às medidas IG, MI e χ2 [Yang and Pedersen, 1997]. Com o
objectivo de suportar os métodos de classi�cação e de clustering, foi de�nido um conjunto de features que
permite caracterizar páginas web e os respectivos links. Utilizando os valores produzidos pelas features, é
possível classi�car os links entre páginas web como informativos ou não informativos recorrendo a métodos
de classi�cação ou a uma simples combinação linear desses valores. Finalmente, o método de clustering
agrupa os links de acordo com as suas características (descritas pelos valores dados pelas features), o que
permite separar links informativos de links não informativos. Foram utilizadas duas implementações de
algoritmos de clustering: CLUTO e k -means.
3.1 Selecção de Features
O primeiro método usado para detectar links não informativos foi a selecção de features. O objectivo é
adaptar métodos de selecção de features de texto à selecção de links na web. Os métodos de selecção de
features permitem determinar quais os termos que mais contribuem para a distinção entre documentos.
No âmbito da web, pretendemos determinar quais os links que mais contribuem para a distinção entre
páginas web, que provavelmente serão os links informativos, sendo os restantes � os que pouco ou nada
contribuem para a distinção entre páginas web � considerados não informativos.
Os métodos de selecção utilizados foram as medidas Information Gain (IG), Mutual Information
(MI) e χ2 [Yang and Pedersen, 1997]. Embora estes métodos sejam destinados à selecção de termos na
categorização de texto, é possível adaptá-los à selecção de links na categorização de páginas web. Para
tal, podemos assumir que as páginas web correspondem aos documentos de texto e que os links entre as
páginas web correspondem aos termos do texto.
IG é uma medida bastante usada no âmbito da classi�cação de documentos como uma medida de
19
qualidade de um termo e é calculada da seguinte forma:
ig (t) = −∑c∈C
P (c) logP (c) +
P (t)∑c∈C
P (c|t) logP (c|t) +
P (t̄)∑c∈C
P (c|t̄) logP (c|t̄)
(3.1)
em que t é um termo, c é uma categoria e C é o conjunto de categorias. As probabilidades P (c), P (t),
P (t̄), P (c|t) e P (c|t̄) representam, respectivamente, a probabilidade de o documento estar classi�cado na
categoria c, a probabilidade de o termo t estar presente no documento, a probabilidade de o termo t não
estar presente no documento, a probabilidade de o documento estar classi�cado na categoria c dado que
o termo t está presente no documento e a probabilidade de o documento estar classi�cado na categoria c
dado que o termo t não está presente no documento.
A medida MI afere a relação entre um termo e uma categoria co-ocorrerem e é calculada da seguinte
forma:
mi (t, c) = logP (t ∧ c)P (t)P (c)
(3.2)
em que t é um termo e c é uma categoria. As probabilidades P (t), P (c) e P (t ∧ c) representam, respec-
tivamente, a probabilidade de o termo t estar presente no documento, a probabilidade de o documento
estar classi�cado na categoria c e a probabilidade de o termo t estar presente no documento e de o docu-
mento estar classi�cado na categoria c. Para tornar esta medida independente da categoria, utiliza-se a
média dos valores de MI (miavg):
miavg (t) =∑c∈C
P (c)mi (t, c) (3.3)
ou o máximo dos valores (mimax):
mimax (t) = maxc∈C{mi (t, c)} (3.4)
Finalmente, a medida χ2 mede o grau de dependência entre um termo e uma categoria e é calculada
da seguinte forma:
χ2 (t, c) =N [P (t|c)P (t̄|c̄)− P (t|c̄)P (t̄|c)]2
P (t)P (t̄)P (c)P (c̄)(3.5)
em que t é um termo, c é uma categoria e N é o número total de documentos na colecção. As pro-
babilidades P (t), P (t̄), P (c), P (c̄), P (t|c), P (t̄|c̄), P (t|c̄) e P (t̄|c) representam, respectivamente, a
probabilidade de o termo t estar presente no documento, a probabilidade de o termo t não estar presente
no documento, a probabilidade de o documento estar classi�cado na categoria c, a probabilidade de o
documento não estar classi�cado na categoria c, a probabilidade de o termo t estar presente no docu-
mento dado que esse documento está classi�cado na categoria c, a probabilidade de o termo t não estar
presente no documento dado que esse documento não está classi�cado na categoria c, a probabilidade de
o termo t estar presente no documento dado que esse documento não está classi�cado na categoria c e a
probabilidade de o termo t não estar presente no documento dado que esse documento está classi�cado
20
c c̄ Total
t A B Tt
t̄ C D Tt̄
Total Tc Tc̄ N
Tabela 3.1: Tabela de Contingência 2x2.
na categoria c. Para tornar esta medida independente da categoria, utiliza-se a média dos valores de χ2
(χ2avg):
χ2avg (t) =
∑c∈C
P (c)χ2 (t, c) (3.6)
ou o máximo dos valores (χ2max):
χ2max (t) = max
c∈C
{χ2 (t, c)
}(3.7)
No sentido de facilitar o cálculo destas medidas, foram usadas tabelas de contingência [Prabowo and
Thelwall, 2006]. Uma tabela de contingência permite analisar a relação entre duas variáveis. Neste caso,
irá armazenar informação sobre a frequência da co-ocorrência de termos e categorias, como exempli�cado
na Tabela 3.1 com um termo t e uma categoria c. O conteúdo da tabela tem o seguinte signi�cado:
• A: número de documentos que têm o termo t e pertencem à categoria c
• B: número de documentos que têm o termo t e não pertencem à categoria c
• C: número de documentos que não têm o termo t e pertencem à categoria c
• D: número de documentos que não têm o termo t e não pertencem à categoria c
• Tt: número total de documentos que contêm o termo t
• Tt̄: número total de documentos que não contêm o termo t
• Tc: número total de documentos que pertencem à categoria c
• Tt̄: número total de documentos que não pertencem à categoria c
• N : número total de documentos na colecção
A utilização de tabelas de contingência 2x2 iria requerer a existência de uma tabela para cada par
termo e categoria, o que, além de representar um elevado custo computacional, leva à existência de
informação redundante. Em [de Oliveira, 2007] é sugerida a utilização de uma tabela de contingência
generalizada para ultrapassar este problema. A Tabela 3.2 apresenta um exemplo de uma tabela de
contingência generalizada em que cada ci é uma categoria e cada tj é um termo. O valor fj,i representa
o número de documentos que pertencem à categoria ci e que contêm o termo tj . Fj contabiliza o número
total das ocorrências do termo tj em todas as categorias e é calculado como:∑id=1 fj,d. Si representa
o número total das ocorrências de todos os termos presentes em documentos que pertencem à categoria
ci e é calculado como:∑jd=1 fd,i. N é o número total das ocorrências de todos os termos em todas as
categorias.
21
c1 c2 · · · ci F
t1 f1,1 f1,2 · · · f1,i F1
t2 f2,1 f2,2 · · · f2,i F2
......
.... . .
......
tj fj,1 fj,2 · · · fj,i Fj
S S1 S2 · · · Si N
Tabela 3.2: Tabela de Contingência Generalizada.
Através desta tabela, é possível calcular os valores A, B, C e D da tabela de contingência 2x2 para
um dado termo t e uma categoria c da seguinte forma:
• A = ft,c
• B = Ft −A
• C = Sc −A
• D = N − (A+B + C)
Recorrendo aos valores A, B, C e D, as fórmulas dos métodos de selecção de features IG, MI e χ2
podem ser simpli�cadas, o que leva a uma diminuição signi�cativa do peso computacional do cálculo
dessas fórmulas [de Oliveira, 2007]. Assim, o IG pode ser calculado por:
ig (t) = −i∑
d=1
SdN
log(SdN
)+
Ft
i∑d=1
A
A+Blog(
A
A+B
)+
(1− Ft)i∑
d=1
C
C +Dlog(
C
C +D
)(3.8)
O MI será calculado da seguinte forma:
mi (t, c) = log
(A×N
(A+ C)× (A+B)
)(3.9)
Finalmente, o χ2 passará a ser calculado por:
χ2 (t, c) =N × [(A×D)− (C ×B)]2
(A+ C)× (B +D)× (A+B)× (C +D)(3.10)
Como a tabela de contingência generalizada se refere a documentos e termos, é necessário adaptá-la a
páginas web e links. Para isso, as páginas web serão consideradas documentos de texto e os links existentes
entre elas assumirão o papel de termos, sendo contabilizado em cada posição da tabela o número de links
que originam em páginas web pertencentes à categoria ci e que têm como destino a página web pj . Por
exemplo, se existir um link l que origina numa página web p1 pertencente à categoria c10 e tem como
destino uma página web p2 pertencente à categoria c11 (ver Figura 3.1), será contabilizada a existência
22
Figura 3.1: Link entre páginas web.
c1 c2 · · · ci F
p1 f1,1 f1,2 · · · f1,i F1
p2 f2,1 f2,2 · · · f2,i F2
......
.... . .
......
pj fj,1 fj,2 · · · fj,i Fj
S S1 S2 · · · Si N
Tabela 3.3: Tabela de Contingência Generalizada para Páginas web.
do link l na célula f2,10, signi�cando que existe um link que origina numa página da categoria c10 e que
tem como destino a página p2.
A Tabela 3.3 exempli�ca uma tabela de contingência generalizada adaptada a páginas web em que
cada ci é uma categoria e cada pj é uma página web. O valor fj,i representa o número de links que
originam em páginas web pertencentes à categoria ci e que têm como destino a página web pj . O valor
Fj contabiliza o número total de links que originam em páginas web de todas as categorias e que têm
como destino a página web pj (ou seja, o número de links de entrada da página web pj), sendo calculado
da seguinte forma:∑id=1 fj,d. O valor Si representa o número total de links que têm origem em páginas
web que pertencem à categoria ci e é calculado da seguinte forma:∑jd=1 fd,i. O valor N é o número total
de links existentes entre todas as páginas de todas as categorias.
Recorrendo a esta tabela de contingência generalizada para páginas web, é então possível calcular os
valores de IG, MI e χ2 para cada link, o que permitirá determinar quais os links que mais contribuem
para a distinção entre páginas. De�nindo um valor limite, os links podem ser divididos em dois grupos:
os que contribuem signi�cativamente para a distinção entre páginas web e que serão considerados links
informativos; e os que pouco ou nada contribuem para a distinção entre páginas web e que, portanto,
serão considerados não informativos.
3.2 Link Features
A detecção de links não informativos pode ser feita através da análise de certas características das páginas
web e dos links existentes entre elas. Nesse sentido, foi de�nido um conjunto de indicadores (features)
que permite caracterizar páginas web e os respectivos links, analisando informação como a quantidade
de links de entrada de uma página web, a quantidade de palavras no texto, o grau de semelhança entre
os host names, ou a posição do link na página de origem, entre outros.
23
O objectivo da de�nição destas features é permitir posteriormente a detecção de links não informativos,
recorrendo a classi�cadores ou a métodos de clustering. Esses métodos irão utilizar os valores produzidos
por estas features para classi�car/agrupar os links entre páginas web, permitindo assim detectar grupos
de links semelhantes, nomeadamente, grupos de links informativos e grupos de links não informativos.
As features apresentadas foram divididas em dois grandes grupos com base na informação que anali-
sam: features da página e features do link. De notar que esta divisão é diferente da divisão entre features
baseadas no conteúdo das páginas web e features baseadas na estrutura de links entre páginas web, como
descrito no Capítulo 2. As features aqui apresentadas como features da página e features do link analisam
tanto informação relativa ao conteúdo das páginas web como informação sobre a estrutura de links entre
essas páginas, existindo uma distinção apenas sobre o foco dessa análise � a página web (como uma
unidade independente) ou o link (como uma relação entre duas páginas web).
As features da página pretendem caracterizar apenas a página web si, analisando informação como a
quantidade de palavras no texto, o número de links de entrada, o número de links de saída, entre outros.
Por sua vez, as features do link pretendem caracterizar apenas o link entre duas páginas web especí�cas,
analisando informação como o URL de ambas as páginas, os endereços IP, entre outros. O valor dado
pelas features pode ser o resultado de um cálculo (contagem, média, etc.) ou um valor binário (zero ou
um), caso só seja relevante detectar se uma dada característica se veri�ca ou não.
A de�nição destas features foi baseada nos trabalhos de [Ntoulas et al., 2006], [Becchetti et al., 2006a]
e [Davison, 2000].
3.2.1 Features da Página
As features utilizadas para caracterizar as páginas web são descritas de seguida. Estas features pretendem
caracterizar apenas a página web si como uma unidade independente, analisando informação como a
quantidade de palavras no texto, o número de links de entrada, o número de links de saída, entre outros.
Word Count
Esta feature faz a contagem das palavras presentes no texto da página web. O objectivo desta feature é
distinguir páginas legítimas de páginas de spam através do número de palavras no texto, sendo expectável
que as páginas de spam tenham ou muitas palavras (term spamming) ou poucas palavras (manipulação
da estrutura de links).
O separador utilizado para delimitar palavras é o carácter espaço, o que leva à de�nição de palavra
como qualquer sequência de caracteres sem espaços. O valor dado por esta feature é a quantidade de
palavras presentes no texto da página web.
Title Word Count
Esta feature faz a contagem das palavras presentes no título da página web. O objectivo desta feature
é distinguir páginas legítimas de páginas de spam através do número de palavras no título da página,
sendo expectável que as páginas de spam tenham títulos muito longos devido ao uso de técnicas de term
spamming.
24
O separador utilizado para delimitar palavras é o carácter espaço. O valor dado por esta feature é a
quantidade de palavras presentes no título da página web.
Average Word Size
Esta feature calcula o tamanho médio das palavras presentes no texto da página web. O objectivo desta
feature é detectar páginas com tamanho médio de palavras elevado, que são provavelmente páginas de
spam que fazem concatenação de palavras-chave.
O tamanho de cada palavra é calculado contabilizando cada carácter da palavra. O valor dado por
esta feature é o resultado do cálculo da média aritmética simples do tamanho das palavras presentes no
texto da página web.
Compression Ratio
Esta feature calcula o rácio de compressão do texto da página web, que é o tamanho da página descom-
primida dividido pelo tamanho da página comprimida. O objectivo desta feature é detectar páginas com
rácio de compressão alto, que provavelmente serão páginas de spam que replicam conteúdo de forma a
obterem um rank mais alto em motores de busca que têm em conta a quantidade de vezes que um termo
da procura aparece na página.
O valor dado por esta feature é o rácio de compressão do texto da página web, calculado através
da divisão do tamanho da página descomprimida (em bytes) pelo tamanho da página comprimida (em
bytes). O algoritmo de compressão utilizado para comprimir o texto da página é o gzip [Ziv and Lempel,
1977].
Path Keywords
Esta feature afere a presença de palavras-chave no URL da página web que sugiram a presença de spam.
O objectivo é detectar páginas de spam que possam ser caracterizadas pela presença de palavras-chave
no URL da página, por exemplo, advertise, links, etc.
O valor dado por esta feature pode ser 0 (zero), 1, 2 ou 4, dependendo de quais as palavras-chave
presentes no URL da página. A Tabela 3.4 apresenta a relação entre as palavras-chave utilizadas e o
valores que esta feature pode tomar. No caso de serem encontradas palavras-chave com diferentes valores,
por exemplo, uma palavra p1 com valor 4 e outra palavra p2 com valor 2, o valor dado por esta feature
será sempre o valor mais alto � no exemplo, será o valor 4. A ocorrência de múltiplas palavras do mesmo
valor é contabilizada como a ocorrência de apenas uma, por exemplo, se o URL de uma página contiver
duas palavras de valor 4, o valor dado por esta feature será simplesmente 4.
Slash Count
Esta feature faz a contagem dos caracteres �/� presentes no URL da página web. O objectivo desta feature
é medir a profundidade da página web no site em que esta se encontra. Assim, quanto mais caracteres
�/� estiverem presentes no URL, mais profunda é a página.
25
Valor Palavras-chave
0 nenhuma palavra-chave encontrada
1 ~
2 ads, get
4 links, advertise, javascript
Tabela 3.4: Relação entre palavras-chave e valores da feature Path Keywords.
O valor dado por esta feature é a quantidade de caracteres �/� presentes no URL da página web. Todos
os caracteres �/� são contabilizados, incluindo a dupla barra presente na maioria dos URLs (http:// ).
InLinks
Esta feature faz a contagem dos links de entrada de uma página web, ou seja, todos os links que têm como
destino a página web em questão. O objectivo desta feature é detectar páginas que tenham muitos links
de entrada, que provavelmente serão páginas de spam que manipulam a estrutura de links para obterem
um rank mais elevado.
O valor dado por esta feature é a quantidade de links de entrada da página web. São contabilizados
todos os links de entrada da página, independentemente da sua origem. Múltiplos links oriundos da
mesma página são todos contabilizados independentemente.
OutLinks
Esta feature faz a contagem dos links de saída de uma página web, ou seja, todos os links que têm como
origem a página web em questão. O objectivo desta feature é detectar páginas que tenham muitos links de
saída, que provavelmente serão páginas de spam que manipulam a estrutura de links de forma a aumentar
o rank de outras páginas.
O valor dado por esta feature é a quantidade de links de saída da página web. São contabilizados
todos os links de saída da página, independentemente do seu destino. Múltiplos links para a mesma
página de destino são todos contabilizados independentemente.
3.2.2 Features do Link
As features utilizadas para caracterizar links entre páginas web são descritas de seguida. Estas features
pretendem caracterizar apenas o link entre duas páginas web especí�cas, analisando informação como o
URL de ambas as páginas, os endereços IP, entre outros.
Host Name
Esta feature compara os host names das páginas web de origem e de destino do link. O host name é
de�nido como a parte do URL da página web que está depois do pre�xo http:// e que termina na primeira
�/� encontrada de seguida. Por exemplo, dado o URL http://www.ist.utl.pt/html/ensino/, o host name
será www.ist.utl.pt.
26
O objectivo desta feature é medir a semelhança entre os host names das páginas de origem e de destino
do link, de forma a determinar se o link é entre páginas do mesmo site (link interno) ou entre páginas
de sites diferentes (link externo). Um link interno é considerado não informativo.
O valor desta feature é dado pela distância de edição entre os host names das páginas de origem e de
destino do link. A distância de edição entre duas sequências de caracteres s e t de�ne-se como o número
mínimo de operações (adição, remoção ou substituição de um carácter) que permite transformar s em
t [Levenshtein, 1966]. A implementação utilizada é a distância de edição Needleman-Wunsch presente no
projecto SecondString [Cohen et al., 2003]. Quanto maior for a distância de edição, menor é similaridade
entre os host names das páginas. Uma distância de edição 0 (zero) indica que os host names são idênticos.
Top Domain
Esta feature determina se os domínios de topo dos URLs das páginas web de origem e de destino do link
são idênticos. De�ne-se domínio de topo como os dois últimos componentes do host name do URL, sendo
que cada componente é separado por um ponto (.). Por exemplo, dado o host name www.ist.utl.pt, o
domínio de topo será utl.pt.
O objectivo desta feature é, tal como na feature Host Name, determinar se o link é interno ou externo
ao site. Esta feature pretende detectar a situação especí�ca em que, embora os host names das páginas
de origem e de destino do link sejam diferentes, os domínios de topo são iguais, o que signi�ca que o link
é provavelmente interno. Por exemplo, se existir um link entre as páginas http://www.example.com e
http://ftp.example.com, o link deverá ser considerado interno, porque os domínios de topo (example.com)
das duas páginas são idênticos.
O valor dado por esta feature é binário (zero ou um), uma vez que só é relevante detectar casos em
que os domínios de topo são idênticos. Um valor de 0 (zero) indica que os domínios de topo das páginas
web de origem e de destino do link são diferentes e um valor de 1 indica que eles são idênticos.
Domain Name
Esta feature determina se os domínios dos URLs das páginas web de origem e de destino do link são
idênticos. De�ne-se domínio como o primeiro componente do domínio de topo do URL, sendo que cada
componente é separado por um ponto (.). Por exemplo, dado o domínio de topo utl.pt, o domínio será
utl.
O objectivo desta feature é, tal como nas features Host Name e Top Domain, determinar se o link
é interno ou externo ao site. Esta feature pretende detectar a situação especí�ca em que, tanto os host
names, como os domínios de topo das páginas de origem e de destino do link são diferentes, mas os
domínios são iguais, o que signi�ca que o link é provavelmente interno. Por exemplo, se existir um
link entre as páginas http://www.example.com e http://www.example.net, o link deverá ser considerado
interno, porque os domínios (example) das duas páginas são idênticos.
O valor dado por esta feature é binário (zero ou um), uma vez que só é relevante detectar casos em
que os domínios são idênticos. Um valor de 0 (zero) indica que os domínios das páginas web de origem e
de destino do link são diferentes e um valor de 1 indica que eles são idênticos.
27
IP
Esta feature determina se os endereços IP das páginas web de origem e de destino do link são idênticos. O
objectivo desta feature é, tal como nas features apresentadas anteriormente que analisam a semelhança de
URLs das páginas, determinar se o link é interno ou externo ao site. A situação especí�ca que se pretende
detectar é a de duas páginas alojadas no mesmo dispositivo, o que nem sempre pode ser determinado
analisando apenas os URLs.
O valor dado por esta feature é binário (zero ou um), uma vez que só é relevante detectar casos em
que os endereços IP são idênticos. Um valor de 0 (zero) indica que os endereços IP das páginas web de
origem e de destino do link são diferentes e um valor de 1 indica que eles são idênticos. O endereço IP de
uma página é determinado realizando uma operação de ping ao URL da página, o que implica a resolução
desse URL num endereço IP.
Link Count
Esta feature contabiliza o número de vezes que o mesmo link aparece no grafo. O objectivo desta feature
é detectar situações de link spamming em que o mesmo link aparece várias vezes, com o objectivo de
aumentar o rank da página de destino. Considera-se que dois links são iguais se as suas páginas de origem
e de destino forem respectivamente as mesmas. Como exemplo, vamos assumir a existência de três links
l1, l2 e l3, com as seguintes características:
• l1: origina na página pA e tem como destino a página pB
• l2: origina na página pA e tem como destino a página pB
• l3: origina na página pB e tem como destino a página pA
Nesta situação, os links l1 e l2 são considerados duplicados, uma vez que têm as mesmas páginas de
origem e de destino. No entanto, o link l3 não é considerado duplicado de nenhum dos outros links,
porque, embora ele ligue as mesmas duas páginas (pA e pB) que os links l1 e l2, o link l3 é no sentido
oposto (de pB para pA).
O valor dado por esta feature é o número de vezes que o mesmo link aparece no grafo.
Link Position
Esta feature determina a posição do link no texto da página web de origem do link. O objectivo desta
feature é detectar páginas em que a maioria dos seus links está localizada nos extremos (topo e fundo
da página). Estas posições tornam os links mais visíveis e acessíveis para um humano, indicando que se
tratam de links de navegação no site ou de links de publicidade, portanto links não informativos.
O valor dado por esta feature é a posição (em bytes) na página de origem do primeiro carácter do
link. A posição é relativa ao início do corpo da página de origem, de�nido pela tag HTML <body>.
28
3.3 Classi�cação
Utilizando os valores produzidos pelas features de�nidas anteriormente, é possível classi�car os links entre
páginas web como informativos ou não informativos, recorrendo a métodos de classi�cação. Sugerem-se
dois métodos para este �m.
O primeiro é uma combinação linear dos valores dados pelas features. São atribuídos pesos às features
e é feita uma combinação linear dos valores dados pelas features para um link, tendo em conta os pesos de
cada feature. Finalmente, os links são classi�cados como informativos ou não informativos com base no
resultado da combinação linear e num valor limite, acima do qual um link é considerado não informativo.
O segundo método recorre ao método de classi�cação SVM, adaptado à classi�cação de links entre
páginas web. Cada link entre páginas web é representado por um vector de d dimensões (sendo d o
número total de features) e o valor de cada uma dessas dimensões é o valor dado pela respectiva feature.
O objectivo é encontrar o hiper-plano no espaço vectorial que melhor separa as duas categorias (links
informativos e links não informativos) com o menor erro possível.
Os métodos propostos são ambos métodos de aprendizagem supervisionada, uma vez que requerem
a intervenção de um humano para o seu funcionamento, seja para de�nir os pesos das features ou para
classi�car uma amostra para treinar a base de conhecimento do classi�cador.
3.3.1 Combinação Linear de Features
O primeiro método utilizado para classi�car os links entre páginas web como informativos ou não informa-
tivos, de acordo com os valores dados pelas features, foi uma combinação linear desses mesmos valores.
O método consiste na prévia atribuição de pesos às features, seguindo-se o cálculo dos valores dessas
features com base na informação disponível sobre as páginas web e os respectivos links. De seguida, é
feita uma combinação linear dos valores dados pelas features tendo em conta o peso individual de cada
feature. Finalmente, classi�cam-se os links como informativos ou não informativos com base no resultado
da combinação linear e num valor limite, que permitirá decidir se um dado link é informativo ou não
informativo.
A classi�cação realizada por este método pode ser caracterizada da seguinte forma:
• Binária � cada link ou é informativo ou é não informativo;
• Document-Pivoted � os resultados são ordenados por link, o que permite saber, para um dado link,
qual a categoria a que ele pertence (informativo ou não informativo);
• Ranking � não é tomada nenhuma decisão imediata por parte do classi�cador sobre qual a categoria
a que um dado link pertence, sendo essa decisão tomada apenas depois da ordenação dos links de
acordo com o valor calculado e com base no limite de�nido.
A combinação linear (CL) dos valores das features é calculada da seguinte forma:
CL (l) =d∑i=1
aivi,l (3.11)
29
em que l é um link entre duas páginas web, d é o número total de features, ai é o peso da feature i e vi,l
é o valor dado pela feature i para o link l.
Os pesos de�nidos para as features deverão garantir que, quanto maior for o valor da feature, maior
será a probabilidade de o link ser não informativo e, quanto menor for o valor da feature, maior será a
probabilidade de o link ser informativo. A ideia é que, um link cujo valor combinado das features seja
elevado será provavelmente um link não informativo, enquanto que um link em que o valor combinado
das suas features é baixo, será provavelmente um link informativo. A Tabela 3.5 exempli�ca a atribuição
de pesos a algumas das features descritas anteriormente.
Feature Peso
Host Name 40
Top Domain 20
Domain Name 15
IP 35
Path Keywords 10
Slash Count 5
. . . . . .
Tabela 3.5: Exemplo de atribuição de pesos a features.
Os resultados das combinações lineares dos valores das features de cada link são normalizados numa
escala de 0 e 1 para facilitar a de�nição do limite que permitirá decidir se um dado link é informativo ou
não informativo. A normalização é feita da seguinte forma:
δ =d− dmin
dmax − dmin(3.12)
em que δ é o valor normalizado, d é o valor original que se pretende normalizar, dmin é o valor mínimo
de d e dmax é o valor máximo de d. Assim, um link será considerado informativo, se o resultado da
combinação linear dos valores das features for inferior ou igual ao limite de�nido. Por oposição, um
link será considerado não informativo, se o resultado da combinação linear dos valores das features for
superior ao limite de�nido.
3.3.2 Classi�cador SVM
O segundo método utilizado para classi�car os links entre páginas web como informativos ou não informa-
tivos, de acordo com os valores dados pelas features, foi o método de classi�cação SVM (Support Vector
Machine) para classi�cação de texto [Joachims, 1998,Joachims et al., 2001]. Este método foi adaptado à
classi�cação de links entre páginas web, considerando as páginas web como documentos e os links entre
essas páginas web como termos. Os valores utilizados para caracterizar os links entre páginas web são os
valores normalizados dados pelas features descritas anteriormente. Desta forma, cada link entre páginas
web é representado por um vector de d dimensões (sendo d o número total de features) e o valor de cada
uma dessas dimensões é o valor dado pela respectiva feature. Os links são representados num espaço
30
vectorial de d dimensões e o objectivo é encontrar o hiper-plano nesse espaço que melhor separa as duas
categorias (links informativos e links não informativos) com o menor erro possível.
Este método de classi�cação é um método de aprendizagem supervisionada, uma vez que é necessária
a existência de uma amostra previamente classi�cada para efectuar o treino da sua base de conhecimento.
A implementação deste método recorre ao SVMLight [Joachims, 1999], uma implementação de SVMs
de Vapnik [Vapnik, 1995] para o problema de reconhecimento de padrões, para o problema de regressão
e para o problema de aprendizagem de uma função de ranking. O algoritmo tem requisitos de memória
escaláveis e é capaz de solucionar problemas e�cientemente com colecções de milhares de vectores. O
kernel utilizado foi o kernel linear com os parâmetros con�gurados por defeito.
3.4 Clustering
O último método sugerido para a detecção de links não informativos é a utilização de clustering para
agrupar os links de acordo com as suas características (descritas pelos valores dados pelas features), o
que, idealmente, permitirá separar links informativos de links não informativos. Este método recorre aos
valores dados pelas features descritas anteriormente na secção 3.2 para caracterizar os links. Os valores
dados pelas features têm todos o mesmo peso e são normalizados numa escala de 0 e 1.
Cada link entre páginas web é representado por um vector de d dimensões (sendo d o número total
de features) e o valor de cada uma dessas dimensões é o valor dado pela respectiva feature. Os links são
representados num espaço vectorial de d dimensões e é então aplicado o algoritmo de clustering que irá
agrupar os links de acordo com as suas características.
O objectivo do clustering é agrupar objectos físicos ou abstractos em classes de objectos semelhantes.
Neste caso, pretende-se agrupar links entre páginas web em duas classes: links informativos e links não
informativos. Este método é um método de aprendizagem sem supervisão, uma vez que não é necessária
a existência de classes prede�nidas nem de conjuntos de treino. Porém, é necessária a intervenção de um
humano para determinar qual dos clusters contém os links considerados informativos e qual o cluster que
contém os links considerados não informativos, mas o esforço requerido para esta tarefa é sem dúvida
bastante menor que o esforço de classi�car manualmente uma amostra de páginas web.
Foram utilizadas duas implementações de algoritmos de clustering, CLUTO e k -means, descritas de
seguida.
3.4.1 Repeated Bisections
A primeira implementação utilizada foi o CLUTO [Zhao and Karypis, 2002,Zhao and Karypis, 2004], um
pacote de algoritmos de clustering que suporta conjuntos de dados com múltiplas dimensões, disponibiliza
várias medidas de distância/similaridade e apresenta medidas de qualidade dos clusters, das quais se
destacam a similaridade interna, a similaridade externa, as features mais discriminativas e as features
mais descritivas de cada cluster. O programa utilizado foi o vcluster, que trata cada objecto como um
vector num espaço multi-dimensional. O algoritmo de clustering utilizado foi o repeated bisections, em
que a solução de clustering é computada através de uma sequência de k -1 operações de bissecção. Cada
31
operação de bissecção consiste no particionamento de um cluster em duas partes e é efectuada recorrendo
ao algoritmo k -means, com k = 2. Como nós pretendemos o particionamento da amostra em apenas 2
clusters (um com os links informativos e outro com os links não informativos), k terá o valor 2, o que
implica que o repeated bisections corresponde exactamente a uma execução do algoritmo k -means com
k = 2. A função de similaridade utilizada foi o co-seno e a função de custo utilizada foi o I2, como
descrito em [Zhao and Karypis, 2004].
O CLUTO lê todos os dados de entrada (matriz de vectores) para a memória antes de iniciar o
algoritmo de clustering. Embora este método seja viável para colecções pequenas, é incomportável para
colecções grandes, uma vez que os requisitos de memória se tornam demasiado elevados.
3.4.2 k-Means
A segunda implementação utilizada foi uma implementação do algoritmo k-means, desenvolvida proposi-
tadamente para este trabalho. O k-means é um método de clustering de particionamento que recebe um
parâmetro k, especi�cando o número de clusters pretendidos, e particiona um conjunto de n objectos em
k clusters. O objectivo do algoritmo é agrupar os objectos em clusters, de forma a maximizar a seme-
lhança entre objectos do mesmo cluster � similaridade intracluster � e, ao mesmo tempo, minimizar
a semelhança entre objectos de diferentes clusters � similaridade intercluster. A similaridade é medida
em relação ao centro de gravidade do cluster � o centroide [Han and Kamber, 2006].
Como já foi referido, o CLUTO tem elevados requisitos de memória, porque lê todos os dados de
entrada para a memória, o que se torna incomportável para colecções grandes. Esta implementação do
k -means visa resolver esse problema, lendo os dados de entrada em cada iteração do algoritmo, em vez de
os guardar em memória permanentemente. Esta solução tem obviamente um impacto negativo no tempo
de execução do algoritmo, mas é a única forma de fazer clustering de colecções grandes.
Esta implementação do k -means funciona da seguinte forma. Em primeiro lugar, o algoritmo selecciona
aleatoriamente k objectos, sendo que cada um deles será o centroide inicial de um dos k clusters. Para os
restantes objectos, cada um será atribuído ao cluster cujo centroide estiver mais próximo de si, ou seja,
aquele com o qual tem maior similaridade. A medida de similaridade utilizada é a distância euclidiana,
calculada da seguinte forma:
dist (x, cj) =
√√√√ d∑i=1
(xi − cj,i)2 (3.13)
em que x é um objecto, cj é o centroide do cluster j, d é o número de dimensões (features) do espaço
vectorial, xi é o valor da dimensão (feature) i do objecto x e cj,i é o valor da dimensão i do centroide do
cluster j. Esta medida tem valor zero quando os objectos são idênticos e quanto menor for a distância
entre dois objectos, maior é a similaridade entre eles.
Depois de todos os objectos terem sido atribuídos ao cluster cujo centroide está mais próximo de si,
calculam-se as novas coordenadas do centroide de cada cluster, realizando a média das coordenadas de
todos os pontos que pertencem a esse cluster. As coordenadas do novo centroide de cada cluster são
32
obtidas da seguinte forma:
cj =1|Cj |
∑x∈Cj
x (3.14)
em que Cj é o cluster j, cj é o centroide do cluster j e x é um objecto que foi atribuído ao cluster j.
Este processo prossegue até que a variação do valor da função de custo de duas iterações consecutivas
seja menor que um dado limite ou quando um número máximo de iterações prede�nido for atingido. A
função de custo utilizada é o erro quadrático E, calculado da seguinte forma:
E =k∑j=1
∑x∈Cj
dist (x, cj)2 (3.15)
em que x é um objecto, Cj é o cluster j, cj é o centroide do cluster j, dist é a distância euclidiana e k é
o número total de clusters.
Quando o algoritmo converge, o resultado obtido é a atribuição de cada um dos objectos no espaço
vectorial a um dos clusters, maximizando a similaridade intracluster e minimizando a similaridade inter-
cluster. Além desta atribuição, o programa retorna também um conjunto de medidas de qualidade dos
clusters, que se descrevem de seguida.
Similaridade Interna
A similaridade interna (ISim � Internal Similarity) de um cluster descreve a similaridade média entre
os objectos desse cluster. Esta medida de qualidade de um cluster j pode ser descrita como o inverso da
média das distâncias do centroide do cluster j a todos os objectos que pertencem ao cluster j. O valor
da ISim é obtido da seguinte forma:
ISimj =
∑x∈Cj
dist (x, cj)2
|Cj |
−1
(3.16)
em que ISimj é a similaridade interna do cluster j, dist é a distância euclidiana, x é um objecto, Cj é o
cluster j e cj é o centroide do cluster j.
Similaridade Externa
A similaridade externa (ESim � External Similarity) de um cluster descreve a similaridade média entre
os objectos desse cluster e os objectos de outros clusters. Esta medida de qualidade de um cluster l pode
ser descrita como o inverso da média das distâncias de todos os objectos do cluster l aos centroides de
todos os outros clusters. O valor da ESim é obtido da seguinte forma:
ESiml =
k∑j=1
∀j 6=l
(∑x∈Cl
dist (x, cj)2
|Cl| (k − 1)
)−1
(3.17)
em que ESiml é a similaridade externa do cluster l, dist é a distância euclidiana, x é um objecto, Cl é o
cluster l, cj é o centroide do cluster j e k é o número total de clusters.
33
Features Descritivas
Features descritivas são features que permitem caracterizar um cluster, ou seja, são as features que mais
contribuem para a similaridade interna de um cluster. A contribuição de uma feature i para a similaridade
interna de um cluster j pode ser calculada da seguinte forma:∑x∈Cj
(xi−cj,i)2|Cj |
ISim−1j
(3.18)
em que x é um objecto pertencente ao cluster j, xi é o valor da feature i do objecto x, cj,i é o valor da
feature i do centroide do cluster j, Cj é o cluster j e ISimj é a similaridade interna do cluster j.
Features Discriminativas
Features discriminativas são features que permitem distinguir um cluster dos outros, ou seja, são as
features que mais contribuem para a similaridade externa de um cluster. A contribuição de uma feature
i para a similaridade externa de um cluster l pode ser calculada da seguinte forma:∑kj=1 ∀j 6=l
(∑x∈Cl
(xi−cj,i)2|Cl|(k−1)
)ESim−1
l
(3.19)
em que x é um objecto pertencente ao cluster l, xi é o valor da feature i do objecto x, cj,i é o valor da
feature i do centroide do cluster j, Cl é o cluster l, ESiml é a similaridade externa do cluster l e k é o
número total de clusters.
3.5 Conclusão
Os métodos apresentados neste capítulo têm como objectivo detectar automaticamente links informativos
e links não informativos. Essa tarefa é realizada recorrendo a métodos de selecção de features, métodos de
classi�cação e métodos de clustering. Todos estes métodos suportam múltiplas dimensões e são escaláveis
a colecções de grande dimensão.
O método de selecção de features é um método de aprendizagem supervisionada. Embora não requeira
uma amostra previamente classi�cada, é necessário de�nir o valor limite que permite distinguir links
informativos de links não informativos. Esta tarefa não-trivial requer a intervenção de um humano, uma
vez que o valor limite varia de colecção para colecção e também entre as várias medidas utilizadas (IG,
MI e χ2).
Os métodos de classi�cação propostos são ambos métodos de aprendizagem supervisionada, uma vez
que requerem a intervenção de um humano para o seu funcionamento, seja para de�nir os pesos das
features ou para classi�car uma amostra para treinar a base de conhecimento do classi�cador.
Ao contrário dos métodos anteriores, os métodos de clustering podem ser considerados métodos de
aprendizagem sem supervisão, uma vez que não é necessária a existência de conjuntos de treino ou a
de�nição de valores limite. É no entanto necessário de�nir qual dos clusters contém os links informativos
e qual contém os links não informativos, mas essa é uma tarefa bastante simples quando comparada com
a intervenção humana necessária à execução dos outros métodos.
34
De entre os métodos apresentados, o método de clustering apresenta a maior vantagem devido à fraca
intervenção humana necessária à sua execução. Este factor torna-o no método mais usável para a detecção
de links não informativos.
35
Capítulo 4
Testes
Este capítulo apresenta a descrição dos testes realizados aos algoritmos de detecção de links não informa-
tivos propostos no capítulo anterior, nomeadamente, selecção de features, classi�cação por combinação
linear de features, classi�cador SVM, CLUTO e k -means. Os testes foram realizados recorrendo a três
colecções e os resultados levam-nos a concluir que é realmente possível determinar automaticamente se
um link entre páginas web é informativo ou não informativo, através da análise de certas características
estatísticas desse link.
4.1 Ambiente de Testes
Esta secção apresenta uma descrição do ambiente onde foram realizados os testes que permitem veri�car
a hipótese proposta. Os testes foram realizados recorrendo a três colecções: SS (colecção pequena que
permite efectuar testes de forma rápida), WBR-99 (colecção de grande dimensão) e CADE (baseada
na WBR-99, disponibiliza a classi�cação de alguns dos seus documentos). Os resultados são analisados
utilizando medidas de precision e recall, matriz de confusão, accuracy, medidas de qualidade dos clusters,
features mais descritivas, features mais discriminativas e o tempo de execução.
A máquina utilizada para executar os testes tem as seguintes características:
• Processador: Intel C2D E6420
� Dual core
� 2,13 GHz
� 4MB Cache L2
• Memória: 2GB
� 2x 1GB
� DDR2 400MHz
� Dual channel
• Disco: 2x Seagate 250GB
36
� 7200 rpm
� SATA II (3 Gbit/s)
� 16MB Cache
� RAID1
• Sistema Operativo: Microsoft Windows XP Professional, Service Pack 2
4.1.1 Colecções Usadas
Para testar os métodos sugeridos para a detecção de links não informativos, foram utilizadas algumas
colecções de vários tamanhos e com diferentes características. Estas colecções são descritas em detalhe
nesta secção.
WBR-99
A colecçãoWBR-99 foi construída a partir de um conjunto de documentos recolhidos da web Brasileira, em
Novembro de 1999. Foi retirada da base de dados do TodoBR, um motor de pesquisa para a web Brasileira,
e oferecida ao laboratório LATIN1 para ser utilizada em pesquisas sobre problemas de Recuperação de
Informação. A colecção contém cerca de 6 milhões de documentos HTML num formato já indexado e
aproximadamente 40 milhões de links entre esses documentos, que estão divididos em links internos e links
externos. Contém também o conjunto completo das pesquisas submetidas ao TodoBR durante Novembro
de 1999, das quais cinquenta têm disponível um conjunto de documentos relevantes. Seguem-se algumas
estatísticas sobre a colecção WBR-99 [Calado, 1999]:
• Tamanho total: 20 Gigabytes
• Tamanho do texto: 16 Gigabytes
• Número de documentos: 5.939.061
• Número de links: 40.871.504
• Número de links internos: 39.577.548 (96,83%)
• Número de links externos: 1.293.956 (3,17%)
CADE
O CADE é uma colecção baseada na WBR-99, que disponibiliza a categorização de alguns dos documentos
dessa colecção. A categorização dos documentos é feita sobre 12 categorias distintas e cada documento
pertence apenas a uma dessas categorias. As categorias são as seguintes: serviços, sociedade, lazer,
informática, saúde, educação, Internet, cultura, desporto, notícias, ciências e compras on-line.
Seguem-se algumas estatísticas sobre a colecção CADE:
1LAboratório para Tratamento da INformação, no Departamento de Ciência de Computação da Universidade Federal
de Minas Gerais.
37
• Tamanho total: 65 Megabytes
• Número de documentos classi�cados: 42.391
• Número de categorias: 12
A distribuição dos documentos pelas categorias está descrita na Tabela 4.1.
Categoria Número de documentos
serviços 8958 (21%)
sociedade 7183 (17%)
lazer 5693 (13%)
informática 4847 (11%)
saúde 3367 (8%)
educação 2977 (7%)
Internet 2561 (6%)
cultura 2130 (5%)
desporto 1942 (5%)
notícias 1135 (3%)
ciências 910 (2%)
compras on-line 688 (2%)
Total 42.391
Tabela 4.1: CADE: Distribuição dos documentos pelas categorias.
SS
A colecção SS é um colecção de pequena dimensão que contém páginas retiradas aleatoriamente da web.
Esta colecção foi criada no decurso deste trabalho (especi�camente no mês de Janeiro de 2008) com o
objectivo de ser uma colecção de pequena dimensão que permitisse efectuar testes rápidos. A colecção
SS permitiu determinar a viabilidade de algumas ideias numa fase inicial, as quais foram posteriormente
testadas noutras colecções de maior dimensão.
A colecção SS contém 52 documentos HTML no formato original (com tags HTML) e aproximada-
mente 5000 links que originam nesses documentos. Embora os documentos de origem dos links estejam
garantidamente na colecção, não se garante o mesmo para os documentos de destino dos links. Como
todos os documentos são identi�cados pelo seu URL, os documentos de destino dos links podem ser
obtidos facilmente. Seguem-se algumas estatísticas sobre a colecção SS:
• Tamanho total: 4 Megabytes
• Número de documentos: 52
• Número de links: 5162
38
4.1.2 Medidas Usadas
De�nimos agora as medidas utilizadas para avaliar os métodos propostos para a detecção de links não
informativos.
Precision e Recall
Precision e recall são duas medidas básicas para a avaliação da qualidade de métodos de Recuperação
de Informação. Neste trabalho, estas medidas baseiam-se na de�nição de dois conjuntos: {Relevant},
o conjunto dos links pertencentes a uma classe C ∈ {uteis, inuteis}; {Retrieved}, o conjunto dos links
classi�cados pelo nosso método como pertencentes à classe C. A precision é calculada da seguinte forma:
precision =|{Relevant} ∩ {Retrieved}|
|{Retrieved}|(4.1)
e pode ser de�nida como a percentagem de links retornados que pertencem à classe correcta. O recall é
calculado da seguinte forma:
recall =|{Relevant} ∩ {Retrieved}|
|{Relevant}|(4.2)
e pode ser de�nido como a percentagem de links da classe correcta que foram retornados [Han and
Kamber, 2006].
Matriz de Confusão
Uma matriz de confusão é uma ferramenta útil para analisar o grau de correcção de um classi�cador.
Um exemplo de uma matriz de confusão pode ser visto na Tabela 4.2. Dadas m classes, uma matriz de
Classe Real
Classe Prevista
C1 C2
C1 TP FP
C2 FN TN
Tabela 4.2: Matriz de Confusão.
confusão é uma tabela de dimensão mínima m por m. Cada entrada MCi,j nas primeiras m linhas e m
colunas da tabela indica o número de links da classe j que foram classi�cados como pertencentes à classe
i. Um classi�cador com boa precisão apresentará a maioria dos links nas células diagonais da tabela, de
MC1,1 até MCm,m, indicando que a classe real e a classe prevista pelo classi�cador são a mesma para a
maioria dos links. A tabela pode ainda conter linhas ou colunas adicionais que apresentam totais e rácios
para cada classe [Han and Kamber, 2006]. Para duas classes, como é o caso deste trabalho, podemos
de�nir links positivos (links que pertencem à classe principal de interesse, por exemplo, a classe C1) e
links negativos (links que pertencem à outra classe, por exemplo, C2). Tal como representado na Tabela
4.2, podemos de�nir cada célula da matriz de confusão de duas classes como:
• Verdadeiros Positivos (TP � True Positives): links positivos que foram correctamente classi�cados
pelo classi�cador;
39
• Falsos Positivos (FP � False Positives): links negativos que foram incorrectamente classi�cados
pelo classi�cador, ou seja, links cuja classe real é C2 mas que foram classi�cados como C1;
• Falsos Negativos (FN � False Negatives): links positivos que foram incorrectamente classi�cados
pelo classi�cador, ou seja, links cuja classe real é C1 mas que foram classi�cados como C2;
• Verdadeiros Negativos (TN � True Negatives): links negativos que foram correctamente classi�ca-
dos pelo classi�cador.
Recorrendo a estes valores TP, FP, FN e TN, as fórmulas de precision e recall podem também ser
calculadas da seguinte forma:
precision =TP
TP + FP(4.3)
recall =TP
TP + FN(4.4)
Accuracy
A medida accuracy é de�nida como a proporção do número total de predições que estão correctas em
relação a todas as predições [Joachims, 1999]. Recorrendo a uma matriz de confusão (Tabela 4.2), a
accuracy é calculada da seguinte forma:
accuracy =TP + TN
TP + FP + FN + TN(4.5)
Qualidade dos Clusters
Existem duas medidas que permitem avaliar a qualidade dos clusters produzidos por métodos de clus-
tering: a similaridade interna e a similaridade externa [Zhao and Karypis, 2002], detalhadas na secção
3.4.2.
O valor ideal destas medidas para um dado cluster é alta similaridade interna, o que indica que os
objectos do cluster são muito semelhantes entre si, e baixa similaridade externa, o que indica que os
objectos do cluster são muito diferentes dos objectos dos outros clusters.
Features Descritivas e Discriminativas
Relativamente aos métodos de clustering, é interessante determinar quais as features que mais contribuem
para a de�nição de um cluster (features descritivas) e as que mais contribuem para distinguir os clusters
(features discriminativas). Estas features são determinadas através do cálculo da contribuição individual
de cada feature para os valores de ISim e ESim, tal como descrito na secção 3.4.2.
Tempo de Execução
A medição do tempo de execução de um método é essencial para avaliar a sua aplicabilidade prática.
Esta medida permite comparar vários métodos e determinar qual é o mais viável com base no consumo
de recursos computacionais.
O tempo de execução foi medido desde o momento em que o método é invocado até ao �nal da escrita
dos resultados.
40
Figura 4.1: Interface web para classi�cação manual de links.
4.1.3 Métodos de Avaliação
Para aplicar algumas das medidas de�nidas nas secções anteriores, é necessário classi�car manualmente
cada link como informativo ou não informativo. Para tal, foram usadas as seguintes abordagens.
Avaliação Manual dos Links
Para colecções pequenas é viável fazer uma avaliação manual de todos os links para determinar o grau
de correcção do método utilizado. Esta avaliação compreende a classi�cação (como link informativo ou
não informativo) manual dos links da colecção e a posterior comparação com a classi�cação obtida pelo
método de identi�cação de links não informativos.
Para efectuar a classi�cação manual dos links, foi criada uma interface web que permite visualizar os
vários links da colecção. Nesta é disponibilizada informação como o URL das páginas de origem e de
destino do link bem como o conteúdo dessas páginas. Recorrendo a esta informação, o utilizador classi�ca
o link como informativo ou como não informativo. A interface web pode ser vista na Figura 4.1, onde se
distinguem, à esquerda a lista dos links (identi�cadores), ao centro o URL e o texto da página web de
origem do link, e à direita o URL e o texto da página web de destino do link. Através da comparação
da classi�cação manual dos links com a classi�cação obtida pelo método de identi�cação de links não
informativos, é possível calcular o valor das medidas de precision, recall e accuracy.
41
Amostragem
Um processo de amostragem é um processo de inferência estatística que permite determinar conhecimento
sobre uma população, com base apenas na selecção de observações individuais. Neste caso especí�co, dado
o elevado número de links em algumas das colecções utilizadas, pretendemos determinar a proporção p
de links informativos e não informativos na colecção com base na análise de uma pequena amostra. Para
tal, recorre-se ao processo de estimativa de uma proporção (de links informativos e não informativos) p,
que permite determinar p com um grau de con�ança de 100(1 − α)% (em que α é a probabilidade de
observação de valores fora do intervalo de con�ança) e com uma margem de erro máxima de E. O erro
associado à estimativa da proporção p é dado por:
E = Zα2
√p (1− p)
n(4.6)
em que Zα2representa o valor crítico (i.e., valor que delimita o intervalo de con�ança e que é obtido
através da distribuição normal padrão para o valor α2 ), p é a proporção e n é o tamanho da amostra.
Resolvendo a equação 4.6 em ordem a n, é possível determinar o tamanho da amostra necessária para o
cálculo de p em função do erro, do intervalo de con�ança e de uma estimativa de p:
n =(Zα
2
E
)2
p (1− p) (4.7)
Uma vez que o tamanho da amostra é dependente de uma estimativa de p e esse valor é desconhecido,
assume-se que p = 0, 5, que representa o valor máximo da equação 4.7 [Montgomery and Runger, 1998].
Assumindo que a amostra é recolhida de forma aleatória e que tem uma distribuição normal, o tamanho
da amostra necessária ao cálculo de p num intervalo de con�ança de 95% (que corresponde a α = 0, 05),
com um valor crítico de Zα2
= 1, 96 (valor tabelado para a distribuição normal padrão) e com uma
margem de erro máxima de 0,05 é:
n =(
1, 960, 05
)2
0, 5 (1− 0, 5) = 384, 16 (4.8)
Isto signi�ca que, com base na proporção de links informativos e não informativos numa amostra de
385 links, podemos estimar a proporção de links informativos e não informativos em toda a colecção com
con�ança de 95% e com uma margem de erro máxima de 0,05.
4.1.4 Testes Executados
Nesta secção descrevem-se os testes realizados aos métodos de detecção de links não informativos propos-
tos no capítulo 3: selecção de features, classi�cação (combinação linear de features e classi�cação SVM)
e clustering (CLUTO e k -means). Os testes foram executados sobre as colecções SS, CADE e WBR-99.
Selecção de Features
Para testar o método de selecção de features descrito na secção 3.1, foi realizada uma série de testes
usando os métodos de selecção de features IG (Information Gain), MI (Mutual Information) e χ2. Como
foi explicitado na descrição dos métodos de selecção de features, os valores dados pelos métodos de MI
42
e χ2 são relativos a uma dada categoria, sendo portanto necessário combiná-los. Os testes efectuados
combinam esses valores através da selecção do valor máximo (mimax e χ2max).
Os testes foram realizados sobre a colecção CADE, pelo facto de os documentos dessa colecção estarem
já classi�cados em categorias. Foram ainda realizados testes sobre uma versão estendida do CADE, que foi
construída propositadamente para este trabalho. Esta versão categoriza os p-antecessores e os p-sucessores
das páginas que compõem a colecção, sendo p o nível de profundidade pretendido. Os antecessores e
sucessores de uma dada página do CADE são determinados seguindo os links que apontam para a página
e os links que têm origem na página, respectivamente. Tanto os antecessores como os sucessores são
categorizados na mesma categoria da página original. Foram gerados dois �cheiros de classi�cação do
CADE estendido � um com 2 níveis de profundidade e outro com 6 níveis de profundidade � sobre os
quais foram realizados testes ao método de selecção de features.
Os testes realizados consistiram no seguinte: cálculo dos valores de IG, MI e χ2 para as várias instâncias
da colecção CADE (CADE original, CADE estendido com 2 níveis de profundidade e CADE estendido
com 6 níveis de profundidade); combinação dos valores por categoria de MI e χ2 através da selecção do
valor máximo; interpretação dos valores dados pelas medidas de selecção de features.
Classi�cação
Para testar os métodos de classi�cação descritos na secção 3.3, foram realizados testes com os métodos
de combinação linear de features e SVM. A colecção utilizada foi a SS, cujos links foram classi�cados
manualmente como informativos ou não informativos para permitir o uso do método de classi�cação
SVM. Relativamente às features utilizadas nos testes, referi-mo-nos à página web de origem do link como
parent e à página web de destino do link como page. Por exemplo, a feature Parent Outlinks refere-se
à contagem dos links de saída da página web de origem do link, enquanto que a feature Page Outlinks
se refere à contagem dos links de saída da página web de destino do link. Nos testes aos métodos de
classi�cação, as features utilizadas para caracterizar os links foram as seguintes: Host Name, Domain
Name, Top Domain, IP, Parent OutLinks, Path Keywords, Link Position, Link Count e Slash Count.
Para testar o método de combinação linear de features, os pesos das features foram parametrizados
através de várias execuções do algoritmo com diferentes pesos de features e comparação dos resultados,
até se obterem os pesos descritos na Tabela 4.3. Em relação ao valor limite que permite classi�car um
link como informativo ou não informativo, a parametrização levou à de�nição do valor de 0,25, isto é,
links cujo resultado da combinação linear é inferior ou igual a 0,25 são considerados links informativos e
os links cujo resultado da combinação linear é superior a 0,25 são considerados links não informativos. Os
testes consistiram no cálculo dos valores das features para cada link da colecção SS, que foram combinados
linearmente, tendo em conta o peso atribuído a cada feature.
Relativamente ao método de classi�cação SVM, os testes foram realizados recorrendo ao método 10 -
fold cross-validation [Kohavi, 1995]. Para tal, a colecção SS previamente classi�cada foi dividida em dez
subconjuntos e foram efectuadas dez execuções independentes do método de classi�cação SVM. Cada
subconjunto foi usado como conjunto de teste exactamente uma vez, assumindo o papel de conjunto de
treino nas restantes nove execuções. Os dez valores obtidos foram combinados através de uma média.
43
Feature Peso
Host Name 30
Domain Name 27
Top Domain 40
IP 40
Parent OutLinks 15
Path Keywords 45
Link Position 15
Link Count 20
Slash Count 20
Tabela 4.3: Atribuição de pesos às features utilizadas nos testes do método de combinação linear de
features.
Clustering
Para testar os métodos de clustering descritos na secção 3.4, foram realizados testes com os algoritmos
CLUTO e k -means, recorrendo às colecções SS e WBR-99. Relativamente à colecção SS, as features usadas
foram as seguintes: Host Name, Domain Name, Top Domain, IP, Parent OutLinks, Path Keywords, Link
Position, Link Count e Slash Count.
Para os testes com a colecção WBR-99 foram usadas as features descritas acima, exceptuando: IP,
uma vez que a maioria dos sites já não existe; Link Position, porque as páginas não têm tags HTML, o
que torna impossível determinar a posição dos links nas páginas de origem; e Link Count, uma vez que
não há links repetidos na WBR-99. Além dessas features, foram também usadas as seguintes: Parent
Average Word Size, Page Average Word Size, Page OutLinks, Parent InLinks, Page InLinks, Parent Word
Count, Page Word Count, Parent Title Word Count e Page Title Word Count.
Dada a grande dimensão da colecção WBR-99, foi recolhida aleatoriamente uma amostra de 385 links,
a qual foi classi�cada manualmente para permitir o cálculo das medidas de precision, recall e accuracy. A
classi�cação manual identi�cou nessa amostra 14 links como informativos e os restantes 371 links como
não informativos.
Os testes realizados começaram com o cálculo dos valores das features para cada link entre páginas
web. Cada link entre páginas web é representado por um vector de d dimensões (sendo d o número
total de features) e o valor de cada uma dessas dimensões é o valor dado pela respectiva feature. De
seguida, o algoritmo de clustering foi executado, realizando o agrupamento dos links de acordo com as
suas características, ou seja, de acordo com o valor de cada uma das suas dimensões. Os algoritmos de
clustering foram con�gurados para a produção de dois clusters: um deveria conter os links considerados
informativos e o outro os links considerados não informativos. No caso do CLUTO, só foi possível realizar
testes com a colecção SS, porque o algoritmo não suporta colecções de grande dimensão como a WBR-99.
Relativamente ao algoritmo k -means, foi possível realizar testes com as duas colecções � SS e WBR-99.
44
PageRank
Para determinar a aplicabilidade do algoritmo de clustering k -means, foram efectuados testes com uma
implementação do algoritmo PageRank [Page et al., 1998] utilizando o algoritmo k -means e a colecção
WBR-99. A implementação do PageRank utilizada foi desenvolvida pelo LAW2 [Boldi et al., 2005] e
permite calcular os valores de PageRank de um grafo de três formas distintas, destacando-se o Power
Method, que foi o método escolhido para executar os nossos testes. Os testes recorreram a três conjuntos
de dados: a WBR-99 original; a WBR-99 contendo apenas os links externos de cada página; a WBR-
99 contendo apenas os links considerados informativos depois da execução do algoritmo k -means. O
procedimento utilizado para a execução dos testes foi o seguinte: criação dos �cheiros de dados e conversão
para o formato de entrada do programa; execução do algoritmo PageRank; extracção dos 15 resultados
de topo (páginas com rank mais alto) para cada conjunto de dados; análise dos resultados.
4.2 Resultados
Os resultados dos testes efectuados aos métodos de detecção de links não informativos são apresentados
de seguida. A informação obtida é apresentada recorrendo a grá�cos e tabelas. A discussão dos resultados
é apresentada na secção seguinte (secção 4.3).
4.2.1 Selecção de Features
Os testes realizados ao método de detecção de links não informativos através de selecção de features
(secção 3.1) estão descritos na secção 4.1.4. Os testes realizados aos métodos de IG, MI e χ2 incidiram
sobre a colecção CADE, pelo facto de os documentos dessa colecção estarem já classi�cados em cate-
gorias. Devido aos maus resultados obtidos nos testes ao CADE original, foram realizados testes sobre
duas versões estendidas do CADE: uma com dois níveis de profundidade e a outra com seis níveis de
profundidade.
CADE Original
A execução dos testes aos métodos de selecção de features com a colecção CADE original revelou um
problema nas fórmulas dos métodos de selecção de features que impede a realização de testes conclusivos.
Recordemos a tabela de contingência generalizada adaptada a páginas web ilustrada na Tabela 3.3
(secção 3.1) e as de�nições das medidas de selecção de features IG (equação 3.8), MI (equação 3.9) e χ2
(equação 3.10). Dado o caso de um página pj não ter links de entrada (links cuja página de destino é a
página pj), fj,i terá o valor 0 para todas as categorias ci e, consequentemente, Fj terá também valor 0.
Tendo em conta estes valores, teremos A = fj,i = 0 e B = Fj − A = 0, o que implica que, nas fórmulas
que permitem calcular os valores de IG, MI e χ2, existirão várias divisões por 0, tornando impossível o
cálculo dessas medidas para a página pj .
2O Laboratory for Web Algorithmics (LAW) foi criado em 2002 no Dipartimento di Scienze dell'Informazione (DSI) da
Università degli studi di Milano.
45
Como a colecção CADE incide apenas sobre uma pequena percentagem das páginas pertencentes à
colecção WBR-99 e contém na maioria páginas de topo dos sites, existem poucos links entre as páginas
da colecção, o que leva a que a situação descrita acima suceda em muitas delas. Nos testes efectuados,
só foi possível calcular o valor de IG para 36 páginas (0,0008% da colecção) e os valores de MI e χ2 para
11.325 páginas (27% da colecção).
Como este teste não foi conclusivo, optou-se pela criação de uma versão estendida do CADE com o
objectivo de aumentar a densidade de links entre as páginas da colecção.
CADE Estendido com 2 Níveis de Profundidade
Com a expansão do CADE a 2 níveis de profundidade (CADE2), a colecção passou a conter 142.909
páginas classi�cadas sob as mesmas 12 categorias do CADE original. Nos testes efectuados, foi possível
calcular o valor de IG para 622 páginas (0,004% da colecção) e os valores de MI e χ2 para 126.705 páginas
(89% da colecção). Como o valor de IG não pôde ser calculado para a maioria das páginas, consideramos
apenas os resultados obtidos para as medidas de MI e χ2.
A Tabela 4.4 apresenta no topo as 15 páginas web com valor de MI mais alto e no �nal as 15 páginas
web com menor valor de MI. A Tabela 4.5 apresenta igualmente no topo as 15 páginas web com valor de
χ2 mais alto e no �nal as 15 páginas web com menor valor de χ2.
É notório que as medidas não estão a efectuar uma distinção correcta de links informativos e não
informativos, uma vez que tanto páginas web de topo como páginas web internas a um site têm quer
valores altos, quer valores baixos.
CADE Estendido com 6 Níveis de Profundidade
Com a expansão do CADE a 6 níveis de profundidade (CADE6), a colecção passou a conter 143.130
páginas classi�cadas sobre as mesmas 12 categorias do CADE original. Nos testes efectuados, foi possível
calcular o valor de IG para 703 páginas (0,005% da colecção) e os valores de MI e χ2 para 131.297 páginas
(92% da colecção). Mais uma vez, como o valor de IG não pôde ser calculado para a maioria das páginas,
consideramos apenas os resultados obtidos para as medidas de MI e χ2.
A Tabela 4.6 apresenta no topo as 15 páginas web com valor de MI mais alto e no �nal as 15 páginas
web com menor valor de MI. A Tabela 4.7 apresenta igualmente no topo as 15 páginas web com valor de
χ2 mais alto e no �nal as 15 páginas web com menor valor de χ2.
Tal como anteriormente, nota-se que as medidas não estão a efectuar uma distinção correcta de links
informativos e não informativos. Podemos então concluir que as medidas de selecção de features não são
adequadas para o problema em causa.
4.2.2 Classi�cação
Os testes realizados aos métodos de detecção de links não informativos através de classi�cação por com-
binação linear de features (secção 3.3.1) e pela utilização do classi�cador SVM (secção 3.3.2) foram
realizados na colecção SS, cujos links foram classi�cados manualmente como informativos ou não infor-
mativos, tendo sido identi�cados 639 links informativos e 4523 links não informativos. A classi�cação
46
Valor URL
5,626 http://www.creche123eja.com.br/
5,626 http://www.mastersbooks.com.br/
5,626 http://www.studiodacrianca.com.br/
5,626 http://www.corgett.com.br/
5,626 http://www.infolink.com.br/escolasb/
5,626 http://www.emporiumbrazil.com.br/
5,626 http://www.sion.com.br/
5,626 http://www.neutrik.com.br/produtos/a1/na1-4.htm
5,626 http://www.contrapontoeditora.com.br/
5,626 http://www.compuland.com.br/alaor
5,626 http://www.malitcia.com.br/
5,626 http://www.casadiroma.com.br/
5,626 http://www.compuland.com.br/colegiosaojose
5,626 http://www.domain.com.br/clientes/escolamodelo
5,626 http://www.sapatos-especiais.com.br/
0,265 http://www.unimontes.br/
0,265 http://tucows.cmg.com.br/win95soft.html
0,263 http://tucows.cmg.com.br/localpda.html
0,262 http://www.hpg.com.br/
0,259 http://tucows.cmg.com.br/win95.html
0,255 http://www.hpg.com.br/assistente/index.php3
0,25 http://www.bcb.gov.br/
0,243 http://www.�nasa.com.br/
0,238 http://www.surf.com.br/
0,231 http://www.hpg.com.br/cadastro/form.php3
0,23 http://www.cade.com.br/
0,224 http://www.hpg.com.br/gerenciador/index.php3
0,221 http://www.ufg.br/
0,221 http://www.hpg.com.br/galeria/index.php3
0,217 http://www.hpg.com.br/galeria/todos.php3
Tabela 4.4: Resultados da medida MI com a colecção CADE2.
47
Valor URL
6.392,42 http://www.imn.com.br/frases/
6.376,48 http://www.imn.com.br/index2.shtml
5.301,21 http://www.netquero.com.br/Lojas/shoppings-virtuais.htm
5.301,21 http://www.netquero.com.br/Lojas/produtos-farmaceuticos.htm
5.301,21 http://www.netquero.com.br/Lojas/passagensaereas.htm
5.301,21 http://www.netquero.com.br/Lojas/perfumescosmeticos.htm
5.301,21 http://www.netquero.com.br/Lojas/supermercados.htm
5.301,21 http://www.netquero.com.br/Lojas/sex-shops.htm
5.217,63 http://www.rbsjornalmidias.com.br/apoio/dicionario_t.html
5.217,63 http://www.rbsjornalmidias.com.br/apoio/dicionario_s.html
5.217,63 http://www.rbsjornalmidias.com.br/apoio/dicionario_z.html
5.217,63 http://www.rbsjornalmidias.com.br/apoio/dicionario_v.html
5.217,63 http://www.rbsjornalmidias.com.br/apoio/dicionario_u.html
5.128,66 http://www.netquero.com.br/Lojas/brindes-presentes.htm
5.128,66 http://www.netquero.com.br/Lojas/brinquedos-artigos-infantis.htm
0,533 http://www.saci.inpe.br/index.html
0,52 http://www.enabletecnologia.com.br/lojas.htm
0,491 http://www.sline.com.br/
0,49 http://www.disal.com.br/conheca/conheca_distribuidores.htm
0,49 http://www.astroslogos.com.br/
0,49 http://www.disal.com.br/conheca/conheca_enderecos.htm
0,49 http://web.horizontes.com.br/~cjacques
0,49 http://www.a�rma.inf.br/
0,49 http://www.insetcenter.com.br/
0,49 http://www.nautilus.com.br/chat.html
0,49 http://www.taiusurf.com.br/
0,49 http://www.enq.ufsc.br/conaq-jr/conaq-jr.html
0,481 http://www.�eto.com.br/
0,477 http://netpage.em.com.br/celular
0,449 http://www.socarba.com.br/
Tabela 4.5: Resultados da medida χ2 com a colecção CADE2.
48
Valor URL
5,443 http://tucows.rio.com.br/ftpnt_size.html
5,443 http://tucows.centroin.com.br/bookmarknt_rating.html
5,443 http://www.labplan.ufsc.br/~guilherme/ufsc/ufscGBR.htm
5,443 http://www.rede-rs.com.br/~lula
5,443 http://tucows.centroin.com.br/bookmarknt_size.html
5,443 http://www.carambella.com.br/esquerda.html
5,443 http://www.jodeval.jor.br/brasil.html
5,443 http://netpage.em.com.br/heine
5,443 http://www.jamboree.org.br/Instructions.htm
5,443 http://tucows.tic.psi.br/cachent.html
5,443 http://www.suprimento.com.br/buscam.htm
5,443 http://tucows.centroin.com.br/bookmarknt_license.html
5,443 http://sputnik.dpi.inpe.br/dpi/spring/usuario/edobje.htm
5,443 http://www.farolweb.com.br/home/usuarios/raisingtears
5,443 http://tucows.atarde.com.br/webnt_license.html
0,268 http://www.apmp.com.br/
0,268 http://www.macnit.com.br/
0,262 http://www.bancodobrasil.com.br/
0,262 http://www.amb.com.br/
0,261 http://www.servicosgratis.com.br/
0,259 http://www.hp.com.br/
0,252 http://www.viavale.com.br/english/sk.html
0,248 http://www.wsguide.com.br/
0,23 http://www.atarde.com.br/
0,23 http://www.viplink.com.br/servic.htm
0,222 http://www.solar.com.br/~amatra
0,221 http://www.fcc.org.br/index.html
0,219 http://www.riototal.com.br/
0,211 http://www.faroljuridico.com.br/
0,174 http://www.estadao-escola.com.br/
Tabela 4.6: Resultados da medida MI com a colecção CADE6.
49
Valor URL
18.452,13 http://www.iso9000.com.br/bbs/index.sht
14.282,59 http://www.anatel.gov.br/mapa_site/default.asp
14.282,59 http://www.anatel.gov.br/glossario/default.asp
14.254,74 http://www.anatel.gov.br/tools/favoritos.asp
14.149,27 http://www.anatel.gov.br/servicos/default.asp
14.147,34 http://www.anatel.gov.br/duvidas/Default.asp
14.103,78 http://www.anatel.gov.br/eventos_publicos/Default.asp
14.103,78 http://www.anatel.gov.br/telemapa/Default.asp
13.970,79 http://www.anatel.gov.br/ajuda/default.asp
13.968,98 http://www.anatel.gov.br/conheca_anatel/default.asp
13.924,60 http://www.anatel.gov.br/comites_comissoes/Default.asp
13.880,48 http://www.anatel.gov.br/biblioteca/default.asp
13.836,64 http://www.anatel.gov.br/atendimento/Default.asp
13.749,74 http://www.anatel.gov.br/Radiofrequencia/default.asp
13.713,78 http://www.anatel.gov.br/Pesquisa/default.asp
0,597 http://www.sampaonline.com.br/educaforum/
0,597 http://www.cnpt.embrapa.br/redbiobr
0,596 http://www.portfolioarte.com.br/
0,596 http://www.datamec.com.br/
0,596 http://www.compumax-sw.com.br/
0,496 http://www.cori.com.br/
0,496 http://www.muvucabaiana.com.br/
0,488 http://www.pelotas.com.br/
0,453 http://agest.ecof.org.br/
0,453 http://www.saude.com.br/2nd_level/saude_na_comunidade.html
0,418 http://home.iis.com.br/~cfreitas/pages/violao.htm
0,244 http://www.ufscar.br/~lapa
0,244 http://www.tariq.com.br/squash/
0,244 http://www.turmatricolor.com.br/
0,244 http://www.inf.unisinos.tche.br/~mathe
Tabela 4.7: Resultados da medida χ2 com a colecção CADE6.
50
prévia da colecção SS viabiliza a utilização do método de classi�cação SVM, que necessita de uma amostra
previamente classi�cada para efectuar o treino da sua base de conhecimento, e permite também o cálculo
das medidas de precision, recall e accuracy.
Combinação Linear de Features
Para testar o método de combinação linear de features foram efectuados testes com a colecção SS, como
descrito na secção 4.1.4.
Quanto ao tempo de execução, foram necessários 311 segundos (cerca de 5 minutos) para o cálculo
dos valores das features e a execução do algoritmo de combinação linear dos valores das features demorou
1 segundo.
Para determinar se o algoritmo está a classi�car os links correcta ou incorrectamente, foi feito o
cruzamento da classi�cação obtida pela combinação linear de features com a classi�cação manual da
colecção SS. O resultado é descrito na matriz de confusão da Tabela 4.8.
Classi�cação Manual
Classi�cação Link Informativo Link Não Informativo
Comb. Linear Link Informativo 564 (10,93%) 89 (1,72%)
Link Não Informativo 75 (1,45%) 4434 (85,90%)
Tabela 4.8: Matriz de Confusão - resultados da combinação linear de features com a colecção SS.
A partir da matriz de confusão é possível calcular os valores de precision e recall para links informa-
tivos:
precision =TP
TP + FP=
564564 + 89
≈ 0, 86 (4.9)
recall =TP
TP + FN=
564564 + 75
≈ 0, 88 (4.10)
e para links não informativos:
precision =TN
TN + FN=
44344434 + 75
≈ 0, 98 (4.11)
recall =TN
TN + FP=
44344434 + 89
≈ 0, 98 (4.12)
Finalmente, calculamos também a accuracy:
accuracy =TP + TN
TP + FP + FN + TN=
564 + 4434564 + 89 + 75 + 4434
≈ 0, 97 (4.13)
Estes valores são bastante altos, o que indica que o algoritmo está a classi�car correctamente a maioria
dos links.
SVM
Os testes realizados com o método de classi�cação SVM recorreram ao método de avaliação 10 -fold
cross-validation. Em cada execução, foram medidos valores de accuracy, precision e recall para links
informativos (I) e links não informativos (NI), que foram combinados através de uma média das várias
51
Conjunto Accuracy Precision (I) Recall (I) Precision (NI) Recall (NI)
1 95,20% 37,25% 100,00% 100,00% 95,06%
2 98,95% 86,54% 100,00% 100,00% 98,87%
3 97,60% 87,65% 92,21% 98,98% 98,31%
4 88,46% 56,63% 53,41% 92,98% 93,30%
5 96,55% 76,77% 100,00% 100,00% 96,11%
6 99,70% 93,94% 100,00% 100,00% 99,69%
7 98,80% 80,49% 100,00% 100,00% 98,58%
8 91,60% 96,92% 87,26% 86,55% 73,82%
9 99,70% 92,00% 100,00% 100,00% 99,69%
10 98,20% 62,50% 100,00% 100,00% 98,15%
Média 96,48% 77,07% 93,29% 97,85% 95,16%
Tabela 4.9: Resultados da execução do SVM na colecção SS.
execuções. Os resultados deste teste estão descritos na Tabela 4.9. Todas as medidas apresentam valores
bastante altos, o que indica que as predições do algoritmo de classi�cação SVM estão correctas para
maioria dos links.
Quanto ao tempo de execução, foram necessários 312 segundos (cerca de 5 minutos) para a construção
dos vectores que representam os links e o tempo médio das dez execuções do algoritmo de classi�cação
SVM foi de 1 segundo.
4.2.3 Clustering
Para testar os métodos de clustering descritos na secção 3.4, foram realizados testes com os algoritmos
CLUTO e k -means, recorrendo às colecções SS e WBR-99, como descrito na secção 4.1.4. No caso do
CLUTO, só foi possível realizar testes com a colecção SS, porque o algoritmo não suporta colecções de
grande dimensão como a WBR-99. Relativamente ao algoritmo k -means, foi possível realizar testes com
as duas colecções � SS e WBR-99.
CLUTO
Os testes realizados com o CLUTO na colecção SS revelaram os resultados seguintes onde, para cada
cluster, é indicado o número de links que foi atribuído a esse cluster, a similaridade interna (ISim), a
similaridade externa (ESim), as features mais descritivas e a sua contribuição para o valor da similaridade
interna (só são listadas aquelas que contribuem mais do que 10%), e as features mais discriminativas e
a sua contribuição para o valor da similaridade externa (só são listadas aquelas que contribuem mais do
que 10%).
• Tempo de execução:
� Construção dos vectores que representam os links: 312 segundos (cerca de 5 minutos)
52
� Execução do algoritmo de clustering: 1 segundo
• Cluster 0 (cluster dos links não informativos):
� Tamanho: 4501 links foram atribuídos a este cluster
� ISim: 0,878
� ESim: 0,133
� Features mais descritivas (> 10%):
∗ Domain Name (36,6%)
∗ Top Domain (36,4%)
∗ IP (21,5%)
� Features mais discriminativas (> 10%):
∗ Host Name (39,6%)
∗ Domain Name (21,8%)
∗ Top Domain (21,6%)
∗ IP (11,6%)
• Cluster 1 (cluster dos links informativos):
� Tamanho: 661 links foram atribuídos a este cluster
� ISim: 0,793
� ESim: 0,133
� Features mais descritivas (> 10%):
∗ Host Name (72,9%)
∗ Link Position (14,9%)
∗ Parent OutLinks (11,2%)
� Features mais discriminativas (> 10%):
∗ Host Name (39,6%)
∗ Domain Name (21,8%)
∗ Top Domain (21,6%)
∗ IP (11,6%)
Para determinar se o CLUTO está a classi�car os links correcta ou incorrectamente, foi feito o cru-
zamento da classi�cação obtida pelo CLUTO com a classi�cação manual da colecção SS. O resultado é
descrito na matriz de confusão da Tabela 4.10.
A partir da matriz de confusão é possível calcular os valores de precision e recall para links informa-
tivos:
precision =TP
TP + FP=
569569 + 92
≈ 0, 86 (4.14)
53
Classi�cação Manual
Classi�cação Link Informativo Link Não Informativo
CLUTO Link Informativo 569 (11,02%) 92 (1,78%)
Link Não Informativo 70 (1,36%) 4431 (85,84%)
Tabela 4.10: Matriz de Confusão - resultados do algoritmo CLUTO com a colecção SS.
recall =TP
TP + FN=
569569 + 70
≈ 0, 89 (4.15)
e para links não informativos:
precision =TN
TN + FN=
44314431 + 70
≈ 0, 98 (4.16)
recall =TN
TN + FP=
44314431 + 92
≈ 0, 98 (4.17)
Finalmente, calculamos também a accuracy:
accuracy =TP + TN
TP + FP + FN + TN=
569 + 4431569 + 92 + 70 + 4431
≈ 0, 97 (4.18)
Estes valores são bastante altos, o que indica que o algoritmo está a classi�car correctamente a maioria
dos links.
k-Means: WBR-99
Relativamente aos testes efectuados com o algoritmo k -means sobre a colecção WBR-99, foram calculadas
diversas medidas que permitem avaliar este método na sua tarefa de detecção de links não informativos. Os
resultados são apresentados de seguida, sendo indicadas as mesmas medidas que para os testes anteriores.
• Número de iterações: o algoritmo convergiu depois de completar cinco iterações
• Tempo de execução:
� Construção dos vectores que representam os links: 5 dias
� Execução do algoritmo de clustering: 1750 segundos (cerca de 30 minutos)
• Cluster 0 (cluster dos links informativos):
� Tamanho: 1.661.835 links foram atribuídos a este cluster
� ISim: 36,20011
� ESim: 2,1538022
� Features mais descritivas (> 10%):
∗ Page InLinks (35,0%)
∗ Host Name (30,6%)
∗ Path Keywords (19,0%)
∗ Parent Outlinks (10,5%)
54
� Features mais discriminativas (> 10%):
∗ Domain Name (39,8%)
∗ Top Domain (39,8%)
∗ Host Name (16,0%)
• Cluster 1 (cluster dos links não informativos):
� Tamanho: 39.209.669 links foram atribuídos a este cluster
� ISim: 2,2528687
� ESim: 1,0810055
� Features mais descritivas (> 10%):
∗ Domain Name (48,2%)
∗ Top Domain (48,2%)
� Features mais discriminativas (> 10%):
∗ Domain Name (46,3%)
∗ Top Domain (46,3%)
Para determinar se o algoritmo k -means está a classi�car os links correcta ou incorrectamente, foi
feito o cruzamento da classi�cação obtida pelo k -means com a classi�cação manual da amostra de 385
links retirada da WBR-99. O resultado é descrito na matriz de confusão da Tabela 4.11.
Classi�cação Manual
Classi�cação Link Informativo Link Não Informativo
k -means Link Informativo 14 (3,64%) 5 (1,30%)
Link Não Informativo 0 (0,00%) 366 (95,06%)
Tabela 4.11: Matriz de Confusão - resultados do algoritmo k -means com a colecção WBR-99.
A partir da matriz de confusão é possível calcular os valores de precision e recall para links informa-
tivos:
precision =TP
TP + FP=
1414 + 5
≈ 0, 74 (4.19)
recall =TP
TP + FN=
1414 + 0
= 1, 00 (4.20)
e para links não informativos:
precision =TN
TN + FN=
366366 + 0
= 1, 00 (4.21)
recall =TN
TN + FP=
366366 + 5
≈ 0, 99 (4.22)
Finalmente, calculamos também a accuracy:
accuracy =TP + TN
TP + FP + FN + TN=
14 + 36614 + 5 + 0 + 366
≈ 0, 99 (4.23)
55
Estes valores são bastante altos, o que indica que o algoritmo está a classi�car correctamente a maioria
dos links.
Os grá�cos da Figura 4.2 ilustram a distribuição do valor de cada feature pelos clusters para cada uma
das features mais descritivas e mais discriminativas. Con�rma-se que as features Domain Name (Figura
4.2a) e Top Domain (Figura 4.2c) são realmente as que mais contribuem tanto para a caracterização dos
clusters como para a sua distinção.
k-Means: SS
Relativamente aos testes efectuados ao algoritmo k -means com a colecção SS, foram calculadas diversas
medidas que permitem avaliar este método na sua tarefa de detecção de links não informativos. Os
resultados são apresentados de seguida.
• Número de iterações: o algoritmo convergiu depois de completar seis iterações
• Tempo de execução:
� Construção dos vectores que representam os links: 312 segundos (cerca de 5 minutos)
� Execução do algoritmo de clustering: 1 segundo
• Cluster 0 (cluster dos links informativos):
� Tamanho: 1217 links foram atribuídos a este cluster
� ISim: 3,0980885
� ESim: 0,83691394
� Features mais descritivas (> 10%):
∗ Link Position (24,6%)
∗ Domain Name (20,3%)
∗ Top Domain (20,3%)
∗ IP (18,4%)
� Features mais discriminativas (> 10%):
∗ Parent Outlinks (54,5%)
∗ Link Position (17,4%)
∗ IP (12,8%)
• Cluster 1 (cluster dos links não informativos):
� Tamanho: 3945 links foram atribuídos a este cluster
� ISim: 1,5792657
� ESim: 0,6641053
� Features mais descritivas (> 10%):
56
1,661835 00,01451439,195155
0510152025303540450 1Ocorrências(Milhõe
s)Valor
Cluster 0 Cluster 1
(a) Domain Name
0510152025303540450 0,2 0,4 0,6 0,8 1 1,2Ocorrências(Milhõ
es)Valor
Cluster 0 Cluster 1
(b) Host Name
1,661835 00,01640239,193267
0510152025303540450 1Ocorrências(Milhõe
s)Valor
Cluster 0 Cluster 1
(c) Top Domain
1,635139 0,016134 0,00354 0,00702237,579203
1,243877 0,113902 0,27268705101520253035400 0,33333334 0,6666667 1Ocorrências(Milhõ
es)Valor
Cluster 0 Cluster 1
(d) Path Keywords
0510152025300 0,2 0,4 0,6 0,8 1 1,2Ocorrências(Milhõ
es)Valor
Cluster 0 Cluster 1
(e) Page InLinks
05101520253035400 0,2 0,4 0,6 0,8 1 1,2Ocorrências(Milhõ
es)Valor
Cluster 0 Cluster 1
(f) Parent OutLinks
Figura 4.2: Distribuição dos valores das features na execução do algoritmo k -means na colecção WBR-99.
57
∗ IP (37,0%)
∗ Top Domain (21,8%)
∗ Domain Name (21,5%)
� Features mais discriminativas (> 10%):
∗ Parent Outlinks (43,2%)
∗ IP (21,3%)
Para determinar se o algoritmo k -means está a classi�car os links correcta ou incorrectamente, foi
feito o cruzamento da classi�cação obtida pelo k -means com a classi�cação manual da colecção SS. O
resultado é descrito na matriz de confusão da Tabela 4.12.
Classi�cação Manual
Classi�cação Link Informativo Link Não Informativo
k -means Link Informativo 74 (1,43%) 1143 (22,14%)
Link Não Informativo 565 (10,95%) 3380 (65,48%)
Tabela 4.12: Matriz de Confusão - resultados do algoritmo k -means com a colecção SS.
A partir da matriz de confusão é possível calcular os valores de precision e recall para links informa-
tivos:
precision =TP
TP + FP=
7474 + 1143
≈ 0, 06 (4.24)
recall =TP
TP + FN=
7474 + 565
≈ 0, 12 (4.25)
e para links não informativos:
precision =TN
TN + FN=
33803380 + 565
≈ 0, 86 (4.26)
recall =TN
TN + FP=
33803380 + 1143
≈ 0, 75 (4.27)
Finalmente, calculamos também a accuracy:
accuracy =TP + TN
TP + FP + FN + TN=
74 + 338074 + 1143 + 565 + 3380
≈ 0, 67 (4.28)
Os valores são aceitáveis para os links não informativos, mas são bastante baixos para os links informa-
tivos. Isto deve-se ao facto de a colecção ser bastante pequena (quando comparada com a WBR-99) e de
algumas features sobre a estrutura de links não poderem ser usadas (Page InLinks, Page OutLinks, etc.).
Os grá�cos da Figura 4.3 ilustram a distribuição do valor de cada feature pelos clusters para cada
uma das features mais descritivas e mais discriminativas. Os grá�cos con�rmam os maus resultados
revelados pelos valores de precision e recall. É visível que os links estão a ser divididos pelos clusters
independentemente do valor das features Domain Name (Figura 4.3a), Top Domain (Figura 4.3b) e IP
(Figura 4.3c), que se esperava que fossem as features mais descritivas e mais discriminativas.
58
87 11307573188
05001000150020002500300035000 1Ocorrências Valor
Cluster 0 Cluster 1
(a) Domain Name
87 11307573188
05001000150020002500300035000 1Ocorrências Valor
Cluster 0 Cluster 1
(b) Top Domain
78 11391451 2494050010001500200025003000
0 1Ocorrências ValorCluster 0 Cluster 1
(c) IP
0200400600800100012000 0,2 0,4 0,6 0,8 1 1,2Ocorrências Valor
Cluster 0 Cluster 1
(d) Parent OutLinks
02004006008001000120014000 0,2 0,4 0,6 0,8 1 1,2Ocorrências Valor
Cluster 0 Cluster 1
(e) Link Position
Figura 4.3: Distribuição dos valores das features na execução do algoritmo k -means na colecção SS.
59
Valor URL
0,000298 http://www.hpg.com.br/
0,000275 http://www.dji.com.br/diversos/bibliogra�a.htm
0,000247 http://cvs.conectiva.com.br/cgi-bin/cvsweb.cgi/linuxconf/
0,000238 http://www.araujo.eti.br/Family2/surnames.htm
0,000216 http://www.usp.br/
0,00021 http://www.terra.com.br/cabeceira.htm
0,000191 http://www.radaruol.com.br/
0,000183 http://www.araujo.eti.br/
0,000174 http://www.mvhp.conectta.com.br/pagode.htm
0,00017 http://www.hpg.com.br/assistente/index.php3
0,000169 http://www.hpg.com.br/cadastro/form.php3
0,000169 http://www.hpg.com.br/gerenciador/index.php3
0,000165 http://www.hpg.com.br/galeria/index.php3
0,00015 http://www.cade.com.br/
0,000145 http://www.mte.gov.br/default.htm
Tabela 4.13: Resultados da execução do PageRank na colecção WBR-99 original.
Valor URL
0,001008 http://www.iconet.com.br/
0,000339 http://www.saude.gov.br/genericos/hot_site/index.htm
0,000307 http://www.cade.com.br/
0,000234 http://www.cnpq.br/
0,000196 http://www.aqui.com.br/
0,000195 http://credpab.saude.gov.br/
0,000185 http://www.itautec.com.br/
0,000158 http://www.brasil.gov.br/
0,000141 http://www.�nep.gov.br/
0,000132 http://www.uol.com.br/
0,000124 http://www.computerworld.com.br/
0,000121 http://www.rnp.br/
0,000119 http://www.epoca.com.br/
0,000118 http://www.itaucom.com.br/
0,000115 http://www.pcworld.com.br/
Tabela 4.14: Resultados da execução do PageRank na colecção WBR-99, contendo apenas os links exter-
nos.
60
Valor URL
0,000994 http://www.iconet.com.br/
0,000801 http://www.usp.br/
0,000518 http://www.unicamp.br/
0,000507 http://www.ufrj.br/
0,00031 http://www.cade.com.br/
0,000272 http://www.cead.puc-rio.br/
0,000223 http://www.defenda-se.inf.br/
0,000222 http://www.editora.unicamp.br/
0,000221 http://www.licitacoes.unicamp.br/
0,000216 http://www.emplasa.sp.gov.br/
0,0002 http://www.ufmg.br/
0,000196 http://www.ufu.br/
0,000192 http://credpab.saude.gov.br/
0,000188 http://www.puc-rio.br/
0,000182 http://www.itautec.com.br/
Tabela 4.15: Resultados da execução do PageRank na colecção WBR-99, contendo apenas os links con-
siderados informativos depois da execução do algoritmo k -means.
4.2.4 PageRank
As Tabelas 4.13, 4.14 e 4.15 apresentam os valores de PageRank e os URLs das 15 páginas que obtiveram
valores mais altos para as colecções WBR-99 original, WBR-99 contendo apenas os links externos de cada
página e WBR-99 contendo apenas os links considerados informativos depois da execução do algoritmo k -
means, respectivamente. Os resultados demonstram uma melhoria aparente na qualidade das páginas de
topo para as duas últimas colecções (WBR-99 só com links externos e WBR-99 só com links informativos).
4.3 Discussão
Selecção de Features
Relativamente aos testes efectuados ao método de selecção de features, os resultados revelam que este
método não é e�caz na detecção de links não informativos. Por observação das Tabelas 4.4, 4.5, 4.6 e
4.7, é notório que as medidas não estão a efectuar uma distinção correcta de links informativos e links
não informativos, uma vez que tanto páginas web de topo como páginas web internas a um site têm quer
valores altos, quer valores baixos.
Vejamos, por exemplo, a Tabela 4.4 em que a primeira página apresentada com maior valor de MI é
�http://www.creche123eja.com.br/� e a primeira página com menor valor é �http://www.unimontes.br/�.
Seria expectável que ambas tivessem valores altos, uma vez que são páginas informativas, mas tal não
acontece. Conclui-se com estes testes que a detecção automática de links não informativos com base na
61
relação entre páginas web e as categorias dessas páginas web não é e�caz.
Classi�cação
Quanto aos testes realizados aos métodos de classi�cação, no caso do método de combinação linear
de features os resultados foram muito bons. Os valores de precision e recall são bastante altos, tanto
para links informativos, como para links não informativos, e apenas 3% dos links foram classi�cados
incorrectamente (Tabela 4.8). No entanto, estes testes foram efectuados apenas na colecção SS, que é
bastante pequena. Embora os resultados tenham sido bastante bons para a colecção SS, a execução dos
testes a este método revelou que é necessário um enorme esforço para parametrizar correctamente os pesos
das features e o valor limite que distingue links informativos de não informativos. Este facto diminui
bastante a usabilidade deste método e inviabiliza a sua utilização em colecções de grande dimensão.
Relativamente ao método de classi�cação SVM, os valores apresentados na Tabela 4.9 revelam resul-
tados médios muito bons. A medida mais importante neste teste é a accuracy que indica quantos links
foram classi�cados correctamente (tanto links informativos, como links não informativos). Como se pode
ver na Tabela 4.9, a accuracy apresenta valores bastante altos, sendo o valor mais baixo obtido 88,46% e
a média 96,48%. Concluindo, o método de classi�cação SVM revela-se e�caz, mas o facto de necessitar
de treinar previamente a sua base de conhecimento a partir de uma colecção anteriormente classi�cada
diminui bastante a sua usabilidade.
Clustering � CLUTO
Os testes realizados com o algoritmo CLUTO revelaram bons resultados para a colecção SS. Os valores
de precision e recall são bastante altos, tanto para links informativos, como para links não informativos,
e apenas 3% dos links foram classi�cados incorrectamente (Tabela 4.10). As medidas de qualidade dos
clusters revelam um bom particionamento da amostra, uma vez que ambos os clusters têm valores de
ISim altos (0,878 no primeiro cluster e 0,793 no segundo cluster) e valores de ESim baixos (0,133 em
ambos os clusters).
Analisando as features mais descritivas do primeiro cluster, con�rma-se que este cluster contém os
links não informativos, uma vez que as features mais descritivas são features que analisam os URLs das
páginas de origem e de destino do link, com o objectivo de identi�car links entre páginas que pertencem
à mesma entidade. O mesmo acontece com as features mais discriminativas, que são também features
relacionadas com o URL, o que indica que a separação dos links está a ser feita principalmente pela
análise do URL.
Clustering � k-Means
Finalmente, os testes efectuados com o algoritmo k -means revelaram bons resultados para a colecção
WBR-99 e maus resultados para a colecção SS. No caso da colecção WBR-99, os valores de precision
e recall são bastante altos, tanto para links informativos, como para links não informativos, e apenas
1% dos links foram classi�cados incorrectamente (Tabela 4.11). As medidas de qualidade dos clusters
revelam um bom particionamento da colecção, uma vez que ambos os clusters têm valores de ISim altos
62
(36,2 no primeiro cluster e 2,25 no segundo cluster) e valores de ESim baixos (2,15 no primeiro cluster e
1,08 no segundo cluster). De notar que o valor de ISim do primeiro cluster (links informativos) é bastante
maior que o valor de ISim do cluster dos links não informativos, o que signi�ca que o primeiro cluster é
muito mais compacto que o segundo e que os links são muito semelhantes entre si.
Analisando os grá�cos da Figura 4.2 que ilustram a distribuição dos links pelos clusters para cada uma
das features mais descritivas e mais discriminativas, con�rma-se que as features Domain Name (Figura
4.2a) e Top Domain (Figura 4.2c) são as que mais contribuem tanto para a caracterização dos clusters
como para a sua distinção. Por observação dos grá�cos é notório que todos os links que têm os host
names iguais (valor 1 ) estão no cluster dos links não informativos (cluster 1) e a maioria dos links que
têm os host names diferentes está no cluster dos links informativos (cluster 0), e o mesmo acontece com
os top domains.
Embora os resultados dos testes ao k -means tenham sido bastante promissores com a colecção WBR-
99, o mesmo não acontece com a colecção SS. Os valores de precision e recall são extremamente baixos
no caso dos links informativos e relativamente altos para links não informativos e, além disso, 33% dos
links foram classi�cados incorrectamente (Tabela 4.12). As medidas de qualidade dos clusters, ISim e
ESim, revelam que os clusters são bastante esparsos, uma vez que os valores de ISim são baixos, quando
comparados com os valores obtidos no teste com a colecção WBR-99. Relativamente a features, os maus
resultados são explicados pelas features mais discriminativas: Parent OutLinks, Link Position e IP. Os
grá�cos da Figura 4.3 demonstram que os links estão a ser divididos pelos clusters independentemente
do valor das features Domain Name (Figura 4.3a), Top Domain (Figura 4.3b) e IP (Figura 4.3c), que se
esperava que fossem as features mais descritivas e mais discriminativas.
O grá�co da feature mais discriminativa � Parent OutLinks (Figura 4.3d) � con�rma que a amostra
está a ser dividida principalmente pelo valor desta feature: os links cuja página de origem tem poucos
links de saída são atribuídos ao cluster 1 (linha vermelha no grá�co) e os links cuja página de origem tem
muitos links de saída são atribuídos ao cluster 0 (linha azul no grá�co). A razão para tal acontecer é o
facto de a colecção, além de ser muito pequena, ter poucas páginas web e muitos links, o que se re�ecte na
de�nição de dois grandes conjuntos: páginas com muitos links e páginas com poucos links. Além disso, o
facto de a colecção SS conter apenas as páginas web de origem dos links impede a utilização de algumas
features relacionadas com a estrutura de links, por exemplo, Page InLinks, Page OutLinks, entre outras.
Page Rank
Os resultados apresentados nas Tabelas 4.13, 4.14 e 4.15 demonstram que, para a colecção WBR-99 com-
pleta, surgem múltiplas páginas do mesmo web site (por exemplo, �www.hpg.com.br� aparece cinco vezes)
e, além disso, nota-se a presença de muitas páginas internas (por exemplo, �http://cvs.conectiva.com.br/
cgi-bin/cvsweb.cgi/linuxconf/�). No entanto, isso não acontece com as outras duas colecções, que re-
velam uma signi�cativa melhoria na qualidade das páginas de topo. Comparando os resultados da
colecção com os links externos da WBR-99 com a colecção com os links informativos, nota-se uma
ligeira vantagem desta última devido, em primeiro lugar, à presença exclusiva de páginas de topo de
web sites e, em segundo lugar, ao facto de todas as páginas de topo serem de entidades diferentes, o
63
310310,5311311,5312312,5313313,5CL SVM CLUTO k-MeansTempo (em segundos) Algoritmos
Construção ExecuçãoFigura 4.4: Comparação dos tempos de execução dos algoritmos de detecção de links não informativos.
que já não é verdade para a colecção com os links externos da WBR-99, devido à presença da página
�http://www.saude.gov.br/genericos/hot_site/index.htm�.
Conclui-se assim que o algoritmo k -means pode ser aplicado com sucesso na detecção e remoção de
links não informativos e que melhora signi�cativamente o desempenho do PageRank.
Tempo de Execução
Quanto ao tempo de execução dos algoritmos, é interessante compará-los e determinar qual deles consegue
melhor desempenho. A Figura 4.4 apresenta um grá�co de comparação dos tempos de construção dos
vectores e de execução nos testes realizados com a colecção SS aos algoritmos que se revelaram e�cazes
na detecção de links não informativos, nomeadamente, combinação linear de features (CL), classi�cação
SVM, CLUTO e k -means. Os tempos de execução são bastante semelhantes em todos os algoritmos,
destacando-se o método de combinação linear que é mais rápido na fase de construção dos vectores.
Conclusão
Com excepção dos métodos de selecção de features, todos os métodos revelaram e�cácia na tarefa de detec-
ção automática de links não informativos. A Tabela 4.16 permite comparar esses algoritmos (combinação
linear de features, classi�cação SVM, CLUTO e k -means) através das medidas de accuracy, precision e
recall para links informativos (Links Inf.) e não informativos (Links Não Inf.), as quais revelam bons
resultados. No caso do k -means, os testes revelaram um fraco desempenho na colecção pequena (SS),
contrariando os bons resultados obtidos com a colecção grande (WBR-99). Relativamente a tempos de
execução, os algoritmos são bastante semelhantes, notando-se apenas uma ligeira vantagem do método
de combinação linear de features.
64
Colecção AccuracyPrecision Recall
Links Inf. Links Não Inf. Links Inf. Links Não Inf.
Comb. Linear SS 97% 86% 98% 88% 98%
SVM SS 96% 77% 98% 93% 95%
CLUTO SS 97% 86% 98% 89% 98%
k -means WBR-99 99% 74% 100% 100% 99%
k -means SS 67% 6% 86% 12% 75%
Tabela 4.16: Comparação dos métodos propostos para detecção de links não informativos.
De entre os algoritmos propostos, o algoritmo k -means apresenta a maior vantagem pelo facto de
suportar colecções grandes e de ser o algoritmo que requer menor intervenção humana. Ao contrário dos
métodos de classi�cação que requerem a classi�cação prévia de uma amostra e do método de combina-
ção linear de features que requer a parametrização dos pesos das features, o k -means requer apenas a
intervenção de um humano para determinar qual dos clusters contém os links considerados informativos
e qual o cluster que contém os links considerados não informativos. O esforço requerido para esta tarefa
é sem dúvida bastante menor que o esforço de classi�car manualmente uma amostra de páginas web ou
de parametrizar os pesos das features.
Recordando a hipótese que se pretendia testar neste trabalho � �analisando certas características
estatísticas dos links entre páginas web, é possível determinar automaticamente se estes são informativos
ou não informativos?� � a resposta é a�rmativa, como comprovado pelos resultados apresentados acima.
65
Capítulo 5
Conclusão
5.1 Resumo geral do trabalho
O capítulo da Introdução descreve o contexto deste trabalho: a remoção de links não informativos, que
diminuem a usabilidade da web e a performance dos motores de busca. A hipótese que se pretende
testar é se, ao analisar certas características dos links entre páginas web, é ou não possível determinar
automaticamente se estes são informativos ou não informativos, para tarefas de Recuperação de Informa-
ção. Apresentam-se ainda os conceitos básicos necessários à compreensão deste trabalho, nomeadamente:
categorização de texto, que consiste em decidir se um documento pertence ou não a uma dada categoria;
selecção de features, que consiste em determinar quais as características que mais contribuem para a
distinção entre documentos; análise de conectividade, ou seja, a análise da informação disponível sobre a
estrutura de links da web; e, �nalmente, clustering, um processo de agrupamento de objectos físicos ou
abstractos em classes de objectos semelhantes.
No segundo capítulo são apresentados trabalhos realizados na área da detecção e remoção de spam
na web. As técnicas de detecção de spam na web podem ser divididas em duas categorias: baseadas no
conteúdo e baseadas na estrutura de links. Os métodos baseados no conteúdo analisam exclusivamente o
conteúdo da página, ignorando informação sobre a estrutura de links. Por sua vez, os métodos de detecção
de spam baseados na estrutura de links têm como objectivo detectar spam que incide na manipulação
da estrutura de links e que não seria detectado por uma análise restrita ao conteúdo das páginas web.
Finalmente, são descritas formas de actuar sobre o spam detectado que passam pela remoção dos links
ou páginas considerados spam, ou pela aplicação de uma penalização a esses links ou páginas.
Com excepção do trabalho de [Davison, 2000], os métodos apresentados focam-se na remoção de spam
e não propriamente na remoção de links não informativos, que englobam não só spam, mas também todos
os links que estão presentes por outras razões que não o mérito. Devido ao uso de classi�cadores, a maioria
dos métodos apresentados requer a prévia classi�cação de uma amostra de páginas para suportar o seu
funcionamento. Contrariamente, o método apresentado neste trabalho recorre a um processo de clustering
(aprendizagem sem supervisão), o que elimina a necessidade de classi�car manualmente uma amostra e
aumenta a sua usabilidade.
66
O capítulo 3 descreve os três métodos propostos para a detecção de links não informativos: selecção
de features (secção 3.1), classi�cação (secção 3.3) e clustering (secção 3.4). O método de selecção de
features tem como objectivo adaptar os métodos de selecção de features de texto à selecção de links na
web e recorre às medidas IG, MI e χ2. Para suportar os métodos de classi�cação e de clustering, foi
de�nido um conjunto de features que permite caracterizar páginas web e os respectivos links. Utilizando
os valores produzidos pelas features, é possível classi�car os links entre páginas web como informativos ou
não informativos recorrendo a um classi�cador SVM ou a uma simples combinação linear desses valores.
Finalmente, o método de clustering agrupa os links de acordo com as suas características (descritas pelos
valores dados pelas features), o que permite separar links informativos de links não informativos. Foram
utilizadas duas implementações de algoritmos de clustering: CLUTO e k -means.
Comparando os métodos propostos, o método de selecção de features é um método de aprendiza-
gem supervisionada, que, embora não requeira uma amostra previamente classi�cada, necessita que seja
de�nido o valor limite que permite distinguir links informativos de links não informativos. Esta tarefa
não-trivial requer a intervenção de um humano, uma vez que o valor limite varia de colecção para co-
lecção e também entre as várias medidas utilizadas. Os métodos de classi�cação propostos são ambos
métodos de aprendizagem supervisionada, uma vez que requerem a intervenção de um humano para o seu
funcionamento, seja para de�nir os pesos das features ou para classi�car uma amostra para treinar a base
de conhecimento do classi�cador. Ao contrário dos métodos anteriores, os métodos de clustering podem
ser considerados métodos de aprendizagem sem supervisão, uma vez que não é necessária a existência
de conjuntos de treino ou a de�nição de valores limite. É no entanto necessário de�nir qual dos clusters
contém os links informativos e qual contém os links não informativos, mas essa é uma tarefa bastante
simples quando comparada com a intervenção humana necessária à execução dos outros métodos. De
entre os métodos apresentados, o método de clustering apresenta a maior vantagem devido à fraca inter-
venção humana necessária à sua execução. Este factor torna-o no método mais usável para a detecção de
links não informativos.
O último capítulo apresenta a descrição dos testes realizados aos métodos propostos para a detecção
de links não informativos. Os testes foram realizados recorrendo a três colecções: SS, uma colecção de
pequena dimensão, que permite efectuar testes de forma rápida; WBR-99, uma colecção de grande dimen-
são construída a partir da web Brasileira; e CADE, uma colecção baseada na WBR-99, que disponibiliza
a classi�cação de alguns dos seus documentos em várias categorias. Foram utilizadas diversas medidas
para avaliar os métodos propostos, por exemplo, precision, recall, accuracy, entre outras. No sentido de
avaliar a correcção dos métodos utilizados para a detecção de links não informativos, foram utilizados
vários métodos, nomeadamente, avaliação manual de links e amostragem.
Com excepção do método de selecção de features, todos os métodos revelaram e�cácia na tarefa
de detecção automática de links não informativos. No caso do k -means, os testes revelaram um fraco
desempenho na colecção pequena (SS), contrariando os bons resultados obtidos com a colecção grande
(WBR-99). Relativamente a tempos de execução, os algoritmos são bastante semelhantes, notando-
se apenas uma ligeira vantagem do método de combinação linear de features. De entre os algoritmos
propostos, o k -means apresenta a maior vantagem pelo facto de suportar colecções grandes e de ser o
67
algoritmo que requer menor intervenção humana � requer apenas a escolha manual do cluster que contém
os links considerados informativos e do cluster que contém os links considerados não informativos. Além
disso, este algoritmo demonstrou melhorias signi�cativas nos resultados do PageRank.
Recordando a hipótese que se pretendia testar neste trabalho � �analisando certas características
estatísticas dos links entre páginas web, é possível determinar automaticamente se estes são informativos
ou não informativos?� � a resposta é a�rmativa, como comprovado pelos resultados obtidos.
5.2 Trabalho Futuro
Para aperfeiçoar o trabalho aqui apresentado, podem ser implementadas algumas alterações aos algorit-
mos.
Em primeiro lugar, o algoritmo de clustering pode ser melhorado de forma a conseguir detectar
automaticamente qual o cluster que contém os links considerados informativos e qual o cluster que contém
os links considerados não informativos. Desta forma, eliminar-se-ia a necessidade de intervenção humana
no processo, sendo assim possível detectar links não informativos de forma totalmente automática. Isto
pode ser feito através da análise do valor que as features mais discriminativas tomam em cada cluster.
Como demonstrado na Figura 4.2, as features Domain Name e Top Domain apresentam valor 1 para
todos os links presentes no cluster 1 (cluster dos links não informativos) e apresentam valor 0 para a
maioria dos links presentes no cluster 0 (cluster dos links informativos). Com base nesta informação seria
possível determinar de forma automática qual o cluster que contém os links informativos (aquele cuja
maioria dos links tem valor 0 nas features Domain Name e Top Domain) e qual o cluster que contém
os links não informativos (aquele cuja maioria dos links tem valor 1 nas features Domain Name e Top
Domain).
Em segundo lugar, os testes revelam que há features que não são nem descritivas nem discriminativas
(por exemplo, Word Count, Average Word Size, entre outras) e que podem ser removidas. Por outro lado,
poderão existir outras features que contribuam positivamente para a detecção de links não informativos
e que poderão ser descobertas realizando testes com outras colecções.
68
Bibliogra�a
[Amitay et al., 2003] Amitay, E., Carmel, D., Darlow, A., Lempel, R., and So�er, A. (2003). The con-
nectivity sonar: detecting site functionality by structural patterns. In HYPERTEXT '03: Proceedings
of the fourteenth ACM conference on Hypertext and hypermedia, pages 38�47, New York, NY, USA.
ACM.
[Becchetti et al., 2006a] Becchetti, L., Castillo, C., Donato, D., Leonardi, S., and Baeza-Yates, R.
(2006a). Link-based characterization and detection of Web Spam. In Second International Workshop
on Adversarial Information Retrieval on the Web (AIRWeb), Seattle, USA.
[Becchetti et al., 2006b] Becchetti, L., Castillo, C., Donato, D., Leonardi, S., and Baeza-Yates, R.
(2006b). Using rank propagation and probabilistic counting for link-based spam detection. In Procee-
dings of the Workshop on Web Mining and Web Usage Analysis (WebKDD), Pennsylvania, USA. ACM
Press.
[Benczúr et al., 2005] Benczúr, A. A., Csalogány, K., Sarlós, T., and Uher, M. (2005). Spamrank fully
automatic link spam detection work in progress. In Proceedings of the First International Workshop
on Adversarial Information Retrieval on the Web (AIRWeb 2005), pages 25�38.
[Bharat and Henzinger, 1998] Bharat, K. and Henzinger, M. R. (1998). Improved algorithms for topic
distillation in a hyperlinked environment. In Proceedings of the 21st Annual International ACM SI-
GIR Conference on Research and Development in Information Retrieval, pages 104�111, Melbourne,
Australia.
[Boldi et al., 2005] Boldi, P., Santini, M., and Vigna, S. (2005). Pagerank as a function of the damping
factor. In WWW '05: Proceedings of the 14th international conference on World Wide Web, pages
557�566, New York, NY, USA. ACM.
[Borodin et al., 2001] Borodin, A., Roberts, G. O., Rosenthal, J. S., and Tsaparas, P. (2001). Finding
authorities and hubs from link structures on the world wide web. In WWW '01: Proceedings of the
10th international conference on World Wide Web, pages 415�429, New York, NY, USA. ACM.
[Calado, 1999] Calado, P. P. (1999). The WBR-99 Collection: Description of the WBR-99 collection
data-structures and �le formats. Laboratório para o Tratamento de Informação, Belo Horizonte, Brazil.
69
[Cohen et al., 2003] Cohen, W., Ravikumar, P., and Fienberg, S. (2003). A comparison of string distance
metrics for name-matching tasks. In Proceedings of the IJCAI: International Joint Conference on
Arti�cial Intelligence, pages 73�78, Acapulco, Mexico.
[da Costa Carvalho et al., 2006] da Costa Carvalho, A. L., Chirita, P. A., de Moura, E. S., Calado, P.,
and Nejdl, W. (2006). Site level noise removal for search engines. In WWW '06: Proceedings of the
15th international conference on World Wide Web, pages 73�82, New York, NY, USA. ACM.
[Davison, 2000] Davison, B. (2000). Recognizing nepotistic links on the web. In Arti�cial Intelligence
for Web Search: Papers from the AAAI Workshop, pages 23�28, Austin, Texas.
[de Oliveira, 2007] de Oliveira, B. M. F. S. (2007). Sugestões de tags para digg. Master's thesis, Instituto
Superior Técnico.
[Fetterly et al., 2004] Fetterly, D., Manasse, M., and Najork, M. (2004). Spam, damn spam, and sta-
tistics: using statistical analysis to locate spam web pages. In WebDB '04: Proceedings of the 7th
International Workshop on the Web and Databases, pages 1�6, New York, NY, USA. ACM.
[Fetterly et al., 2005] Fetterly, D., Manasse, M., and Najork, M. (2005). Detecting phrase-level duplica-
tion on the world wide web. In SIGIR '05: Proceedings of the 28th annual international ACM SIGIR
conference on Research and development in information retrieval, pages 170�177, New York, NY, USA.
ACM.
[Fielding et al., 1999] Fielding, R., Gettys, J., Mogul, J., Frystyk, H., Masinter, L., Leach, P., and
Berners-Lee, T. (1999). HyperText Transfer Protocol � HTTP/1.1. RFC 2616.
[Fogaras and Rácz, 2004] Fogaras, D. and Rácz, B. (2004). Towards scaling fully personalized pagerank.
In Algorithms and Models for the Web-Graph, volume 3243/2004, pages 105�117. Springer Berlin /
Heidelberg.
[Gyongyi and Garcia-Molina, 2005] Gyongyi, Z. and Garcia-Molina, H. (2005). Web spam taxonomy. In
First International Workshop on Adversarial Information Retrieval on the Web (AIRWeb).
[Gyöngyi et al., 2004] Gyöngyi, Z., Garcia-Molina, H., and Pedersen, J. (2004). Combating web spam
with trustrank. In VLDB '04: Proceedings of the Thirtieth international conference on Very large data
bases, pages 576�587. VLDB Endowment.
[Han and Kamber, 2006] Han, J. and Kamber, M. (2006). Data Mining: Concepts and Techniques,
Second Edition. Morgan Kaufmann Publishers Inc.
[Joachims, 1998] Joachims, T. (1998). Text categorization with support vector machines: learning with
many relevant features. In Proceedings of ECML-98, 10th European Conference on Machine Learning,
pages 137�142, Chemnitz, Germany.
[Joachims, 1999] Joachims, T. (1999). Making large-scale support vector machine learning practical.
In Schölkopf, B., Burges, C., and Smola, A., editors, Advances in Kernel Methods: Support Vector
Machines, pages 169�184. MIT Press, Cambridge, MA, USA.
70
[Joachims et al., 2001] Joachims, T., Cristianini, N., and Shawe-Taylor, J. (2001). Composite kernels for
hypertext categorisation. In Proceedings of the 18th International Conference on Machine Learning,
ICML-01, pages 250�257, Williams College, US.
[Kleinberg, 1999] Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. J. ACM,
46(5):604�632.
[Kohavi, 1995] Kohavi, R. (1995). A study of cross-validation and bootstrap for accuracy estimation
and model selection. In Proceedings of the Fourteenth International Joint Conference on Arti�cial
Intelligence, volume 2, pages 1137�1145.
[Lempel and Moran, 2000] Lempel, R. and Moran, S. (2000). The stochastic approach for link-structure
analysis (SALSA) and the TKC e�ect. Computer Networks, 33(1�6):387�401. Also in Proceedings of
the 9th International World Wide Web Conference.
[Levenshtein, 1966] Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions,
and reversals. Soviet Physics Doklady, 10(8):707�710.
[Mitchell, 1997] Mitchell, T. M. (1997). Machine Learning. McGraw-Hill Higher Education.
[Montgomery and Runger, 1998] Montgomery, D. C. and Runger, G. C. (1998). Applied Statistics and
Probability for Engineers. John Wiley & Sons, 2nd edition.
[Ntoulas et al., 2006] Ntoulas, A., Najork, M., Manasse, M., and Fetterly, D. (2006). Detecting spam
web pages through content analysis. In WWW '06: Proceedings of the 15th international conference
on World Wide Web, pages 83�92, New York, NY, USA. ACM.
[Olsson and Oard, 2006] Olsson, J. O. S. and Oard, D. W. (2006). Combining feature selectors for text
classi�cation. In CIKM '06: Proceedings of the 15th ACM international conference on Information
and knowledge management, pages 798�799, New York, NY, USA. ACM.
[Page et al., 1998] Page, L., Brin, S., Motwani, R., and Winograd, T. (1998). The PageRank citation
ranking: Bringing order to the Web. Technical report, Stanford Digital Library Technologies Project.
[Prabowo and Thelwall, 2006] Prabowo, R. and Thelwall, M. (2006). A comparison of feature selection
methods for an evolving rss feed corpus. Information Processing and Management, 42(6):1491�1512.
[Quinlan, 1993] Quinlan, J. R. (1993). C4.5: programs for machine learning. Morgan Kaufmann Pu-
blishers Inc., San Francisco, CA, USA.
[Salton, 1989] Salton, G. (1989). Automatic Text Processing: The Transformation, Analysis, and Retri-
eval of Information by Computer. Addison-Wesley Longman Publishing Co., Inc.
[Salton et al., 1975] Salton, G., Wong, A., and Yang, C. S. (1975). A vector space model for automatic
indexing. Communications of the ACM, 18(11):613�620.
[Sebastiani, 2002] Sebastiani, F. (2002). Machine learning in automated text categorization. ACM Com-
puting Surveys, 34(1):1�47.
71
[Urvoy et al., 2006] Urvoy, T., Lavergne, T., and Filoche, P. (2006). Tracking web spam with hidden style
similarity. In Proceedings of the 2nd International Workshop on Adversarial Information Retrieval on
the Web (AIRWeb'06), pages 25�31, Seattle, USA.
[Vapnik, 1995] Vapnik, V. N. (1995). The nature of statistical learning theory. Springer-Verlag New York,
Inc., New York, NY, USA.
[Yang and Pedersen, 1997] Yang, Y. and Pedersen, J. O. (1997). A comparative study on feature selec-
tion in text categorization. In ICML '97: Proceedings of the Fourteenth International Conference on
Machine Learning, pages 412�420, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
[Zhao and Karypis, 2002] Zhao, Y. and Karypis, G. (2002). Evaluation of hierarchical clustering algo-
rithms for document datasets. In CIKM '02: Proceedings of the eleventh international conference on
Information and knowledge management, pages 515�524, New York, NY, USA. ACM.
[Zhao and Karypis, 2004] Zhao, Y. and Karypis, G. (2004). Empirical and theoretical comparisons of
selected criterion functions for document clustering. Machine Learning, 55(3):311�331.
[Ziv and Lempel, 1977] Ziv, J. and Lempel, A. (1977). A universal algorithm for sequential data com-
pression. IEEE Transactions on Information Theory, 23(3):337�343.
72