Universidade Federal de Minas Gerais Instituto de Ciências Exatas

Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciências da Computação
MARLOS CHOLODOVSKIS MACHADO
MONOGRAFIA DE PROJETO ORIENTADO EM COMPUTAÇÃO I
CLASSIFICAÇÃO DE DOCUMENTOS MODELADOS COMO GRAFOS
Belo Horizonte – MG
2009 / 2o semestre
Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciências da Computação
CLASSIFICAÇÃO DE DOCUMENTOS MODELADOS
COMO GRAFOS
por
MARLOS CHOLODOVSKIS MACHADO
Monografia de Projeto Orientado em Computação I
Apresentado como requisito da disciplina de Projeto Orientado em
Computação I do Curso de Bacharelado em Ciência da Computação da UFMG
Prof. Dr. Marcos André Gonçalves
Orientador
Belo Horizonte – MG
2009 / 2o semestre
Aos meus pais,
à minha namorada,
aos professores,
aos colegas de curso e
aos meus familiares,
dedico este trabalho.
i
Agradecimentos
Agradeço inicialmente aos meus pais, por sempre terem acreditado em mim e por
terem investido com tamanha convicção na minha educação.
À minha namorada, por sempre estar ao meu lado, me apoiando e incentivando.
À todos os meus professores, essenciais para minha formação.
Ao meu orientador, pela paciência, ensinamentos e críticas.
Aos meus amigos, por terem transformado o curso em uma jornada prazerosa.
E finalmente à minha falecida avó, que possibilitou meu primeiro contato com um
computador, suficiente para me encantar.
ii
“Ciência da Computação tem tanto a ver com o computador
como a Astronomia com o telescópio,
a Biologia com o microscópio,
ou a Química com os tubos de ensaio.
A ciência não estuda ferramentas,
mas o que fazemos e o que descobrimos com elas.”
citação atribuída a Edsger Dijkstra
iii
Sumário
Lista de Figuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
Lista de Tabelas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
x
1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1
Contexto e Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.2
Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.3
Hipótese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2 REFERENCIAL TEÓRICO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1
Modelagem dos Textos como Grafos . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2
Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.2.1
Classificação de Gêneros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.2.2
Splogs Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3 MODELAGEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 MÉTRICAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.1
Grau máximo e médio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4.2
Caminho Mínimo Médio e Diâmetro . . . . . . . . . . . . . . . . . . . . . . . . .
19
4.3
Coeficiente de Clusterização Médio . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.4
Tamanho do Componente Gigante e do Número de Componentes Conectados . . .
20
iv
4.5
Betweenness Médio e Máximo . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.6
Closeness Médio e Máximo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.7
Densidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
5 DESCRIÇÃO DAS COLEÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1
Genre Dataset (GeDa) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
5.2
Splog Dataset (SPLOG) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
6 RESULTADOS E DISCUSSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.1
Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
6.1.1
Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
6.1.2
GeDa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
6.1.3
Splog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
Distribuição acumulada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
6.2.1
Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
6.2.2
GeDa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
6.2.3
Splog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
6.2
7 CONCLUSÕES E TRABALHOS FUTUROS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Referências Bibliográficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
v
Lista de Figuras
Figura 3.1 Exemplo de modelagem
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Figura 6.1 “Boas métricas” para a GeDa
Figura 6.2 Outras métricas para GeDa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Figura 6.3 “Não tão boas” métricas para a GeDa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Figura 6.4 Métricas Splog
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Figura 6.5 Métricas Splog
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Figura 6.6 Métricas Splog
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
vi
Lista de Tabelas
Tabela 5.1 Periódicos coletados da área Humanas, Ciências Sociais e Direito
Tabela 5.2 Periódicos coletados da área Biomédicas e Medicina
. . . . . . . . . 24
. . . . . . . . . . . . . . . . . . . . . 25
Tabela 6.1 Matriz de Confusão: GeDa com normalização
. . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Tabela 6.2 Matriz de Confusão: GeDa sem normalização
. . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Tabela 6.3 Matriz de Confusão: Baseline
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Tabela 6.4 Sumário dos resultados do método proposto e do baseline
Tabela 6.5 Matriz de Confusão: Splogs (Método proposto)
. . . . . . . . . . . . . . . . 29
. . . . . . . . . . . . . . . . . . . . . . . . . . 30
Tabela 6.6 Sumário dos resultados do método proposto e do baseline (7)
Tabela 6.7 Primeiras Quatro Métricas da GeDa
. . . . . . . . . . . . . 30
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Tabela 6.8 Outras Quatro Métricas da GeDa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Tabela 6.9 Últimas Quatro Métricas da GeDa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Tabela 6.10 Primeiras Quatro Métricas da Splog
Tabela 6.11 Outras Quatro Métricas da Splog
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
vii
Tabela 6.12 Últimas Quatro Métricas da Splog
viii
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Resumo
As palavras, em qualquer linguagem, não se conectam aleatoriamente e textos com
diferentes objetivos e estilos revelaram que suas palavras se relacionam em diferentes padrões.
Nesse trabalho propõe-se uma modelagem de documentos textuais como uma rede complexa
de palavras. São exploradas várias métricas de redes complexas nesses grafos para estudar
e analisar essas diferenças nos padrões de conexão. Experimentos em duas coleções textuais
diferentes isto é, conjunto de documentos com diferentes gêneros e blogs, mostraram que as
métricas de redes complexas são altamente discriminantes através da distribuição cumulativa
de seus valores para diferentes gêneros e blogs (blogs reais e spams), mostrando seu potencial
para diferenciar tipos de texto distintos.
Palavras-chave: Gênero textual, categorização, redes complexas, modelagem de grafos,
splogs.
ix
Abstract
Words in texts of any language are not randomly connected and texts with different
goals and styles have shown to present different patterns of word relationships. This work
proposes a graph modeling approach for text documents that represents them as a complex
network of words. It also explores several complex network metrics on top of these graphs
in order to study and analyze such differences in patterns of connections. Experiments in two
different textual collections, i.e., with sets of documents with different genre and blogs, have
shown that indeed our complex network features are highly discriminative as demonstrated by
the cumulative distribution of their values for different types of genre and blogs (i.e., real and
spam blogs), thus showing their potential for discriminating different types of text.
Keywords: Text genre, categorization, complex networks, graph modeling, splogs.
x
11
1
INTRODUÇÃO
1.1
Contexto e Motivação
Existe praticamente um consenso de que a “explosão de informação” é um dos proble-
mas mais difíceis encarados atualmente na computação e o gerenciamento efetivo de coleções
de texto tem sido um tópico bastante pesquisado. Nesse contexto, produzir características que
auxiliam a diferenciação dos textos em várias classes de interesse (e.g., por tópico, gênero,
opinião) é uma contribuição muito importante.
A capacidade de classificar documentos textuais em termos do seu gênero específico1
(e.g., textos científicos, jornalísticos ou literários) pode ser útil em várias aplicações como, por
exemplo, na remoção de ambiguidade relacionada ao significado de uma palavra específica, já
que muitos significados de uma dada palavra são restritos à textos de um estilo particular (1).
Por exemplo, o substantivo “Lula” tem dois significados bastante comuns: ele pode referenciar
tanto o animal marinho quanto o atual presidente da República (Luis Inácio Lula da Silva). É
impossível saber a que essa palavra se refere observando-a isoladamente mas, se esse substantivo é encontrado em um texto científico da área biológica é bem provável que ela faça
referência ao animal marinho; da mesma forma que quando presente em uma notícia de política
a probabilidade maior é que faça referência à pessoa.
A classificação por gêneros também pode proporcionar melhorias na usabilidade das
máquinas de busca, permitindo aos usuários ordenar os resultados de suas consultas com base
em gêneros específicos (2). O usuário poderia, por exemplo, fazer uma consulta com os termos
“Recuperação de Informação” e desejar ver, nas primeiras posições, artigos científicos e não
outras páginas Web (e.g., Wikipédia, Notícias, Ementas) como é feito atualmente.
Duas aplicações mais técnicas para a classificação de documentos por gêneros são: a
criação de um coletor focado, permitindo a existência de repositórios especializados em genêros
específicos (e.g., artigos científicos, ementas de curso, revisão de produtos, etc) (3) e a melhoria
1 Mais
precisamente, por gênero queremos dizer “qualquer classe de textos definida por seus propósitos comunicativos comuns ou outras características funcionais” (1).
12
no processo de re-visita de um coletor à uma página Web. O gênero de uma página Web pode
ajudar a determinar a frequência que ela é alterada (4), e.g., um página com notícias de jornal
provavelmente sofre mais alterações que uma página com um texto literário.
Identificação de spams é outra aplicação que pode se beneficiar de características discriminantes, esse problema é muito interessante devido, também, ao seu impacto econômico na
Web (5).
1.2
Objetivo
A preocupação específica desse trabalho é propor e avaliar o poder de discriminação de
um conjunto de novas características baseadas em uma modelagem de textos como grafos, que
são utilizadas para diferenciar documentos com padrões distintos de escrita. Mais especificamente, a abordagem proposta para a caracterização desses documentos é baseada na modelagem
de um texto como uma rede complexa (6). O documento é modelado como um grafo no qual os
vértices representam palavras distintas e as arestas representam relações de proximidade entre
essas palavras. Extrai-se então várias métricas dessa rede.
A avaliação do poder discriminativo das métricas para diferentes conteúdos textuais
é feita através da classificação de duas bases de dados2 . Essa classificação utiliza as métricas
propostas como evidências.
1.3
Hipótese
Considerando toda a discussão do capítulo pode-se sintetizar a hipótese do trabalho
como sendo: As métricas de redes complexas, quando aplicadas à textos modelados como
grafos, são capazes de capturar características do documento como, por exemplo, estilo e estrutura. Conseguindo diferenciar, de forma precisa, documentos de diferentes classes.
Esse trabalho visa confirmar essa hipótese. Essa abordagem é independente de linguagem por explorar apenas a estrutura do grafo que representa o documento, da mesma forma
que independe de análise sintática e semântica.
2 Uma
base é relacionada à gêneros, é composta de 9000 documentos pertencentes à três gêneros específicos:
literário, científico e jornalístico. A segunda base é relacionada à splogs (i.e., spam blogs). Ela possui 1389 blogs
onde 695 são spam (i.e., link spam blogs e fake blogs) (7).
13
2
REFERENCIAL TEÓRICO
Esse trabalho se articula em duas áreas distintas: a primeira —Redes Complexas—
trata da modelagem do texto como um grafo. Já a segunda área —Recuperação de Informação—
está voltada para a classificação dos documentos em diferentes classes. Para uma maior clareza
dividiu-se o estudo bibliográfico em duas seções principais.
2.1
Modelagem dos Textos como Grafos
Vários problemas reais podem ser modelados como redes complexas. Exemplos in-
cluem redes sociais, informacionais, tecnológicas e biológicas (6). Essas redes permitem a
modelagem de um problema como um conjunto de interconexões entre as entidades de interesse, permitindo a extração de informações importantes levando em consideração os padrões
dessas conexões.
No âmbito de representações textuais, vários trabalhos modelam textos como grafos,
apesar do fato de algumas modelagens variarem entre si. Jin e Srihari (2007), por exemplo,
modelam textos como grafos levando em consideração alguns dos seus aspectos sintáticos. Esse
trabalho ataca o problema de consulta de cadeia de conceitos1 (concept chain query).
Mais relacionado ao nosso trabalho, a modelagem de textos como grafos, desconsiderando fatores sintáticos ou semânticos e utilizando apenas a disposição das palavras no
texto é feita por Dorogovtsev e Mendes (2001), Ferrer-i-Cancho e Sole (2001) e Antiqueira
et al (2007).
Ferrer-i-Cancho e Sole (2001) analisam os grafos resultantes e suas propriedades,
mostrando que textos e linguagem natural normalmente seguem um modelo com características de grafos small-world (9). Uma discussão importante nesse trabalho é sobre a distância
máxima entre duas palavras para uma relação existir, com a distância dois sendo considerada a
melhor para representar as propriedades do texto.
1 Esse problema pode ser definindo como sendo a “busca por ligações entre conceitos através de documentos”(8)
14
A linguagem humana também é objeto de estudo de Dorogovtsev e Mendes (2001).
Nesse trabalho, os autores propõem uma teoria do desenvolvimento da linguagem humana
baseda na sua modelagem como uma rede crescente de palavras que se interagem. Eles mostram
que uma grande quantidade, ou o “núcleo”, da linguagem não varia com a evolução da linguagem (10).
Finalmente, Antiqueira et al (2007) exploram a modelagem de textos como grafos e
correlacionam a qualidade de um texto com métricas de Redes Complexas. Nesse trabalho eles
mostram a existência de uma correlação inversa entre o aumento das métricas coeficiente de
clusterização e outdegree com a qualidade do texto. (11).
2.2
Classificação
2.2.1 Classificação de Gêneros
Existem diversos trabalhos relacionados à classificação de gêneros e eles podem ser
divididos em dois grupos: aqueles que se baseiam no conhecimento de algum especialista,
dependentes assim do idioma, e aqueles que propõem abordagens mais automatizadas e independentes de idioma.
Várias abordagens já apresentadas na literatura podem ser enquadradas no primeiro
grupo como, por exemplo, a exploração de técnicas de aprendizado de máquina combinadas
à características baseadas em fatores linguísticos para mostrar, empiricamente, a diferença
retórica entre diferentes campos da ciência (12). Outra abordagem já apresentada é a classificação de gêneros utilizando um método baseado em tags (que são assinaladas manualmente)
além de análises sintáticas e linguísticas dependentes do idioma (13).
Outras abordagens interessantes são a classificação de gêneros baseada em Processamento de Linguagem Natural2 (14); e a modelagem de textos como vetores, incluindo características para a classificação como frequências Part-of-Speech (POS) (15).
Trabalhos mais próximos do nosso estão presentes na segunda categoria, que são independentes de linguagem e especialistas. Os trabalhos dessa categoria são mais interessantes
para a classificação de conteúdos Web, principalmente devido à escalabilidade das técnicas propostas. Um caso de estudo de um classificador de gêneros supervisionado, em um ambiente de
produção é apresentado em (16). Uma teoria baseada na modelagem de gêneros como bundles
of facets e sua correlação com as “pistas de superfícies” é apresentada em (1).
2 Campo
humana.
da computação que objetiva facilitar o “entendimento” dos computadores com relação à linguagem
15
Ainda nesse grupo está (17), que apresentaram um método independente de categorização baseado nos níveis n-gram3 dos caracteres da linguagem. Outro trabalho interessante é
(19), que apresentou um algoritmo de classificação baseado em estatísticas do texto (frequência
do termo e do documento, por exemplo) — utilizamos esse trabalho como baseline.
Finalmente, classificação de gêneros não está restrita somente à textos. Existem, por
exemplo, várias pesquisas relacionadas à classificação de músicas conforme seu gênero musical
(20, 21) — esse tópico foge do escopo do trabalho e não será discutido.
2.2.2 Splogs Classification
A “blogosfera” tem sido muito pesquisada atualmente e é um campo relativamente
novo. Macdonald e Ounis (2006) apresentam um dos primeiros esforços na construção de uma
coleção de blogs — Blogs06 — e discutem algumas características observadas nela, como, por
exemplo, a distribuição de palavras ofensivas, de links e da hora de postagem (22).
Já relacionado ao tópico de detecção de splogs, Datta e Sarkar (2008) apresentam um
estudo comparativo das características de blogs e splogs, como erros de digitação, frequência
das palavras e distribuição de assuntos (23).
Vários outros trabalhos existem, propondo abordagens para a detecção de vários tipos
de spam, utilizando diversas técnicas como aprendizado de máquina (24) e modelos baseados
em linguagem (25).
Um enfoque maior foi dado nos trabalhos de Kolari e.t. a.l. (7, 26), utilizando inclusive
a base de blogs proposta por eles nesse trabalho. Kolari, Finin e Joshi (2006) detalham a base
que utilizam para a detecção de splogs, definindo inclusive uma nomenclatura e apresentando
definições de termos como blogs e splogs (7). Posteriormente, Kolari e.t. a.l. (2006) formaliza
o problema de detecção de splogs e apresenta um método baseado em SVM, complementando
o trabalho anterior (26).
Comparativamente, a maior contribuição do projeto apresentado é a modelagem de
textos como uma rede complexa e a utilização de várias métricas dessas redes como características para discriminar diferentes classes de texto — até onde se sabe, nunca se explorou essa
abordagem antes. Nesse trabalho, classifica-se gêneros e splogs.
3 “Qualquer
substring de tamanho n” (18)
16
3
MODELAGEM
Esse é um dos aspectos mais importantes desse trabalho, a modelagem de textos como
grafos, além da posterior utilização de métricas desse grafo como evidências para a classificação dos documentos em diferentes classes. Assim sendo, é importante discutir de forma mais
precisa a modelagem realizada e as métricas utilizadas como evidências.
Para a modelagem de um documento como um grafo definiu-se cada uma de suas
palavras distintas como um vértice. Uma aresta existe entre dois vértices se a distância entre as
duas palavras que representam esses vértices for menor ou igual à um certo limiar em alguma
parte do texto.
O limiar citado acima representa então a distância máxima entre duas palavras para que
uma relação seja existente. Ferrer-i-Cancho e Sole (2001) utilizam a mesma modelagem desse
trabalho e discutem extensivamente o melhor limiar para ela. Partindo do pressuposto de que
as palavras mais correlacionadas em um texto são aquelas que estão mais próximas e levando
em consideração co-ocorrência de termos no idioma inglês e expressões comuns do idioma —
todos os documentos trabalhados estão em inglês — os autores concluem que a distância dois é
ideal para modelar o idioma inglês (27); outros trabalhos também já utilizaram essa modelagem
e esse limiar (10).
O grafo resultante é não-dirigido, já que a relação de proximidade não possui uma
direção específica. Decidiu-se avaliar grafos ponderados e não-ponderados, modelando o peso
das arestas como sendo determinado pela repetição de relações no texto. Ou seja, se duas
palavras estão próximas em três pontos distintos do texto, então o peso da aresta que as liga é
três. A distância em si não foi diferenciada, i. e., uma relação de duas palavras à uma distância
dois é exatamente igual à uma relação de duas palavras à uma distância igual à um.
Pontuação, acentuação e capitalização foram tratados previamente: Todos os acentos e marcas de pontuação, que não significam final de sentença — vírgulas, ponto e vírgula,
hífen, etc — foram removidos. Transformou-se também todas as letras maiúsculas em minúsculas. Essas transformações “asseguram que todas as ocorrências de uma palavra sejam contadas
17
como sendo do mesmo tipo, não importando se elas são a primeira palavra de uma sentença
e, consequentemente em letras maísculas. Um efeito colateral menor ocorre para nomes que
são escritos da mesma forma de uma palavra, que são contados como sendo essa palavra.”(28).
Possíveis laços no grafo são ignorados (vértices se relacionarem com si próprios).
Palavras entre colchetes são tratadas como sendo independentes das palavras fora do
mesmo. Considerou-se também separação de palavras (uma palavra começa em uma linha e
termina na outra). Levou-se também em consideração operações matemáticas e cada fator foi
assumindo como sendo uma palavra diferente, assim 1×2 resultará em: ‘1’, ‘×’ e ‘2’.
Para uma avaliação mais ampla, decidimos analisar os resultados levando em consideração stemming1 (utilizando ou não no texto) e stop-words2 (texto com e sem elas).
A Figura 3.1 oferece um exemplo do grafo gerado pela sentença: “Uma sentença exemplo utilizada como exemplo para a modelagem”, não aplicando stemming nem removendo
as stop-words. Observa-se, mesmo nessa simples sentença, um padrão diferente no vértice
que representa a palavra “examplo”, identificando sua repetição no texto. Ele foi desenhado
utilizando o software Pajek.3
como
1
1
1
utilizada
para
1
1
2
1
1
2
modelagem
a
sentenca
1
1
exemplo
1
1
uma
Pajek
Figura 3.1: Exemplo de modelagem
1 Remoção dos radicais das palavras, deixando apenas a raiz.
Por exemplo, as palavras “amarelo” e “amarelado”
têm a mesma raiz: “amarel”.
2 São palavras que supostamente não agregam significado a um texto.
3 Disponível em: http://pajek.imfm.si/doku.php
18
4
MÉTRICAS
A característica realmente inovadora desse trabalho é a utilização das métricas do
grafo — originário da modelagem proposta no capítulo anterior — como evidências para a
classificação de documentos. Esse capítulo apresenta as métricas utilizadas e suas respectivas
definições.
A hipótese do trabalho — que as diferenças no estilo e organização da escrita são refletidos na topologia das redes criadas — está diretamente relacionada à análise dessas métricas.
Por exemplo, textos jornalísticos tendem a utilizar um número menor de palavras na média e,
utilizar as palavras uniformemente ao longo do texto. Textos literários tendem a explorar mais
sinônimos enquanto textos científicos utilizam menos sinônimos e vários termos técnicos. Textos jornalísticos geralmente lidam com o mesmo assunto em todos os seus parágrafos enquanto
textos científicos e literários não. Isso porque duas seções de um artigo científico podem ser
parcialmente não-relacionadas, e.g., a seção ‘Trabalhos Relacionados’ pode lidar com assuntos parcialmente diferentes e independentes quando comparados à seção ‘Conclusão’. Textos
literários, por outro lado, podem apresentar parágrafos relacionados à dois personagens diferentes em lugares e tempos distintos. A maioria dessas características foram identificadas pelas
métricas propostas nesse trabalhos, esse tópico será discutido na seção resultados.
No caso dos splogs outras situações podem ser identificadas, por exemplo, se um blog
possui um pequeno número de arestas e um número de palavras similar a outros blogs, provavelmente é porque algumas palavras e frases seguem um padrão de repetição. Esse padrão é muito
comum em link spam blogs com intenções de propaganda, por exemplo. Um resultado esperado
é que as palavras nos splogs serão mais repetitivas que as palavras em blogs e, na média, serão
mais conectadas entre si do que a outras palavras diferentes em diferentes partes do texto.
As novas características propostas também são mais difíceis de se “enganar”. Por
exemplo, splogs atualmente são escritos por softwares que imitam uma distribuição Zipfian
de palavras (23), tentando prevenir sua detecção. Imitar uma determinada característica da
linguagem pode até ser simples, entretanto imitar todos os padrões de um grafo é muito mais
difícil. As métricas abaixo foram utilizadas como evidências para a classificação dos textos.
19
4.1
Grau máximo e médio
O grau médio (AD) de um grafo pode ser definido como:
V
∑ di
AD =
i=1
V
(4.1)
onde d i é o grau do vértice i e V é o número total de vértices do grafo. O grau máximo (MD)
pode ser identificado como:
MD = max(d 1 , d 2 , ..., dV )
(4.2)
No caso da representação de textos, o número de relações diferentes entre palavras
(vértices) é diretamente relacionado ao grau médio de um grafo. O grau máximo é relacionado
à utilização e frequência de algumas palavras. Se uma palavra aparece em muitos contextos ela
terá uma grau médio maior e uma palavra que apareça em todo lugar provavelmente terá o grau
máximo.
4.2
Caminho Mínimo Médio e Diâmetro
O caminho mínimo médio (ASP) é a média da menor distância entre um par de vértices.
Choueka e Lusignan (1985) definiram ASP como sendo (29):
ASP =
V V
1
∑ di j
∑
n(n − 1) i=1 j=1
(4.3)
onde di j é o caminho mínimo médio da rede do vértice i ao j. Podemos também definir diâmetro
(D) como o maior caminho míninmo para todo par de vértices, i.e.:
D = max(d11 , d12 , ..., d21 , ..., dVV −1 )
(4.4)
No contexto desse trabalho, essas duas métricas estão relacionadas ao número de
palavras utilizadas em um texto, o número de relações diferentes entre essas palavras além
de vários outros fatores. Se um texto possui um baixo número de palavras e elas se conectam de
diferentes maneiras, o caminho mínimo médio e o diâmetro serão menores do que em textos nos
quais algumas palavras são raramente utilizadas ou utilizadas apenas em situações específicas.
20
4.3
Coeficiente de Clusterização Médio
Watts e Strogatz (1998) apresentaram a definição de coeficiente de clusterização de um
vértice i (ci ) em (9) como ci =
NTi
NCi
onde NTi é o número de triângulos conectados ao vértice i e
NCi é o número de triplas centradas em i. Se um vértice tem grau igual a 1 ou 0 o numerador e
o denominador são zero e definimos ci = 0. Com essa definição, o coeficiente de clusterização
médio (ACC) pode ser formalizado como segue:
ACC =
1
V
V
∑ ci
(4.5)
i=1
Uma analogia comum para o coeficiente de clusterização é uma rede de amizades. O
coeficiente de clusterização mede a probabilidade de um amigo do seu amigo ser seu amigo.
Podemos dizer que essa métrica também está relacionada à coesão do texto. Ele possui um
valor maior quando dois diferentes pedaços do texto são relacionados, i.e., eles possuem várias
palavras em comum. Textos sem coesão provavelmente possuem um coeficiente de clusterização médio menor.
4.4
Tamanho do Componente Gigante e do Número de Componentes Conectados
Um componente conectado pode ser definido como sendo o subgrafo composto de
todos os vértices mutuamente alcançáveis.
Definindo GCi como o tamanho percentual de um componente conectado i e P o
número total de componentes conectados, podemos definir o tamanho do componente gigante
(SGC) e o número de componentes conectados (NCC):
SGC = max(GC1 , GC2 , ..., GCP )
(4.6)
NCC = P
(4.7)
Essas duas métricas também são relacionadas à coesão do texto. Geralmente, pelo
menos uma palavra que aparece em uma parte do texto também aparece em outra parte, stop
words pelo menos. Um texto que possui duas partes sem nenhuma palavra em comum terá
dois componentes conectados diferentes. Essas duas métricas medem quantas palavras não
pertencem ao “componente principal” e quantas partes do texto não se relacionam às outras.
21
4.5
Betweenness Médio e Máximo
Betweenness é um valor local e pode ser definido como sendo o número de caminhos
geodésicos entre dois vértices diferentes que passam pelo vértice que se quer calcular o betweenness. Pode-se dizer que o betweenness é uma medida de resiliência da rede (6) já que ele
nos diz quantos caminhos geodésicos serão maiores se um vértice for removido. Sendo Bti j um
vetor de tamanho V e Btikj = 1 se o caminho mínimo entre dois vértices i e j passar pelo vértice
k e Btikj = 0 se não passar, podemos definir o betweenness de um vértice k e, consequentemente
o betweenness médio (Bt(k) e ABt, respectivamente):
V
Bt(k) = ∑
V
∑ Btikj
(4.8)
∑ Bt(k)
(4.9)
i=1 j=1
ABt =
1
V
V
k=1
Define-se também o betweenness máximo:
MBt = max(Bt(1), Bt(2), ..., Bt(V ))
(4.10)
Essas duas métricas estão relacionadas à repetitividade do texto. Uma palavra (vértice)
possui um betweenness alto porque ela aparece em várias partes do texto e conecta palavras
diferentes (provavelmente stop words possuem um betweenness maior).
4.6
Closeness Médio e Máximo
Closeness mede quão perto, em média, um vértice está dos outros. Pode-se definir o
closeness (Cn(i)) de um vértice i em um grafo conectado G como segue:
Cn(i) =
f −1
∑ ASP(i, j)
(4.11)
i, j∈G
onde ASP(i, j) é o caminho mínimo de i para j e f é o número de vértices alcançáveis de i em
G, isto é, o closeness mede a proximidade de um vértice para todos os outros. Pode-se definir
também o closeness máximo e mínimo (ACn e MCn respectivamente):
1 f
ACn = ∑ Cn(i)
f i=1
(4.12)
MCn(i) = max(Cn(1),Cn(2), ...,Cn( f ))
(4.13)
22
Essas duas métricas também estão relacionadas à repetição de palavras. Se uma palavra
é utilizada várias vezes, em contextos não relacionados, é esperado que ela crie pontes entre
partes do grafo que diminuem as distâncias.
4.7
Densidade
Essa métrica é definida como a razão entre o número de arestas de um grafo (Ed) e o
número máximo de arestas possíveis (MEd). Uma formalização dessa medida é:
De =
Ed
MEd
(4.14)
Ela ignora laços e arestas múltiplas, situações inexistentes nos grafos desse trabalho.
Essa métrica é influenciada pelo número de palavras diferentes aplicadas ao texto; um texto com
mais sinônimos possui uma densidade menor que um texto que usa sempre as mesmas palavras.
23
5
DESCRIÇÃO DAS COLEÇÕES
Uma abordagem para investigar se a modelagem de textos como grafos realmente captura propriedades intrínsecas de diferentes tipos de texto é a experimentação. As próximas
seções desse capítulo discutem mais detalhadamente as coleções utilizadas nesse trabalho.
5.1
Genre Dataset (GeDa)
Uma coleção bastante comum nos trabalhos sobre classificação de gêneros é a Brown
Corpus (1, 13). “Ela é composta de 500 amostras de textos publicados em 1961 — divididas em
15 gêneros. Cada amostra começa em uma sentença no artigo ou outro documento escolhido,
selecionada randomicamente, e continua até o fim da sentença que ultrapassa o limite de 2000
palavras, a base é dividida em subcategorias.”(30)
Essa base não foi utilizada por ser muito pequena para o trabalho, já que nenhum de
seus gêneros possui mais do que algumas dezenas de documentos. Outra razão importante é
que amostras não são interessantes para esse trabalho, que explora a estrutura do texto como
um todo. A utilização de amostras poderia causar uma perda parcial de informação. Além disso,
a intenção é classificar textos simples i.e., assume-se que textos não possuem nenhuma marca
como tags ou qualquer outra informação que necessite do fornecimento por um especialista.
Não se discute a utilidade de tais marcas, mas a abordagem se torna menos genérica.
A Brown Corpus também foi desnecessária por não utilizarmos suas informações adicionais, além de pretendermos utilizar uma base com textos de diferentes períodos, ainda esperando bons resultados. Criou-se então uma coleção com três gêneros, que são praticamente
um superconjunto dos 15 gêneros da Brown Corpus. Um exemplo disso é o fato do gênero
jornalístico da GeDa ser dividido em três gêneros na Brown Corpus: Reviews, Editorial e Reportages.
Não tendo sido encontrada uma base já existe de gêneros, a GeDa foi montada com
a coleta de documentos de três gêneros diferentes: científico, jornalístico e literário. O gênero
24
literário é composto por textos que têm como propósito o entretenimento do leitor, sendo apresentado em vários formatos como, por exemplo, contos, crônicas, novelas, entre vários outros.
O gênero jornalístico é composto por textos que objetivam distribuir informação sobre acontecimentos do mundo real, algumas vezes eles são escritos com opiniões. Por fim, o
gênero científico é composto de textos publicados em materiais científicos com o propósito de
introduzir um novo conhecimento específico ao leitor.
A coleção GeDa é composta de 9,000 textos em inglês, com seus gêneros classificados
de acordo com sua origem — local de onde foram retirados. Cada um dos três gêneros possui
3,000 documentos nessa base. Os 3,000 textos jornalísticos foram selecionados aleatoriamente
entre 3,591 textos de uma amostra da base Wall Street Journal (31). Para o gênero literário
coletou-se 16,794 textos do portal do Projeto Gutenberg1 (selecionou-se aleatoriamente 3,000
documentos entre os menores, evitando grandes livros e possibilitando que os textos de diferentes gêneros tenham um tamanho similar).
Finalmente, para o gênero científico coletou-se textos de duas bibliotecas digitais:
ACM2 e Springer3 . Os textos científicos foram divididos em três áreas para uma justiça maior:
Ciência da Computação; Humanas, Ciências Sociais e Direito; Biomédicas e Medicina. Coletouse 2,186 textos na ACM (Ciência da Computação), 1,858 textos em cinco periódicos diferentes
sobre Humanas, Ciências Sociais e Direito (presentes na Tabela 5.1) e, por fim, 1,495 textos em cinco periódicos diferentes da área de Biomédicas e Medicina (listados na Tabela 5.2).
Selecionou-se então 1,000 textos — de cada área — entre os maiores, para evitar textos indesejados como cartas editoriais.
Higher Education
http://www.springerlink.om/ontent/102901/
European Demographic Information Bulhttp://www.springerlink.om/ontent/121145/
letin
Crime, Law and Social Change
http://www.springerlink.om/ontent/102868/
Advances in Health Sciences Education
http://www.springerlink.om/ontent/1382-4996/
International Journal of Technology and
http://www.springerlink.om/ontent/102912/
Design Education
Tabela 5.1: Periódicos coletados da área Humanas, Ciências Sociais e Direito
1 http://www.gutenberg.org/wiki/Main_Page
2 http://portal.am.org/dl.fm
3 http://www.springer.om
25
Behavior Genetics
Animal Cognition
Amino Acids
Annals of Biomedical Engineering
Archives of Toxicology
http://www.springerlink.om/ontent/105485/
http://www.springerlink.om/ontent/101775/
http://www.springerlink.om/ontent/104405/
http://www.springerlink.om/ontent/111241/
http://www.springerlink.om/ontent/0340-5761/
Tabela 5.2: Periódicos coletados da área Biomédicas e Medicina
5.2
Splog Dataset (SPLOG)
Uma descrição completa do conjunto de dados SPLOG foi feita por Kolari, Finin e
Joshi (2006) (7). Esse conjunto de dados também foi utilizado por várias outras pessoas, Datta
e Sarkar (2008) (23), além de Sculley e Wachman (2007) (24), por exemplo.
A SPLOG é composta de 1,389 blogs onde 695 blogs foram classificados como splogs,
i.e., link spam blogs ou fake blogs. Mais especificamente, fake blogs extraem textos de outros
locais na Web e os publicam como postagens. Link spam blogs também podem atuar como link
farms, i. e., um conjunto de splogs que possui vários links para outro blog específico, com a
intenção de aumentar seu PageRank. Outro exemplo de spam em blogs é a repetição de palavras
tentando deixar o blog mais relevante para certas consultas. Geralmente esse tipo de blog possui
intenções comerciais.
Por existirem muitos trabalhos na literatura que lidam com esse conjunto de dados, não
é necessário um detalhamento maior do mesmo.
26
6
RESULTADOS E DISCUSSÃO
Dois experimentos foram realizados para avaliar o desempenho do método proposto.
Cada seção discute a metodologia do experimento e os resultados obtidos para as duas bases.
Há um procedimento preliminar comum aos dois experimentos que será explicado agora. As
diferentes experimentações são feitas a partir do mesmo ponto de partida.
Inicialmente tem-se apenas os documentos em seu formato original, os splogs passam
por um parser HTML, tendo suas tags e marcadores removidos, com isso, todos os documentos,
de todas as coleções, passam a ser textos puros, esses documentos são então pré-processados
(como discutido no capítulo 3). Após esse pré-processamento, têm-se os documentos no formato correto para o gerador de grafos.
O gerador de grafos recebe esses documentos como entrada e gera como saída os
grafos, nesse momento define-se o limiar e a consideração ou não das stop words e de pesos.
A aplicação de stemming é feita na fase anterior. Tendo sido gerado o grafo, é necessário gerar
as métricas de redes complexas — a grande inovação do trabalho. Calcula-se então as métricas
e gera-se um arquivo em que cada linha representa um documento, sendo cada documento
modelado como um vetor.
O ponto de partida dos dois experimentos discutidos a seguir é o arquivo em que cada
linha representa um documento e, cada métrica é na verdade as dimensões do vetor, isso porque
o algoritmo de classificação é baseado no modelo vetorial (18) onde cada dimensão é uma das
métricas discutidas no capítulo 4.
6.1
Classificação
6.1.1 Metodologia
O primeiro experimento a ser realizado é a classificação dos documentos em diferentes
áreas, que foi feito utilizando-se o algoritmo SVM (Support Vector Machine) baseado em técnicas de aprendizagem de máquina. Utilizou-se a implementação chamada LIBSVM (32) para a
27
realização da classificação. O funcionamento do algoritmo não será detalhado, ele é largamente
utilizado na literatura — atualmente o estado-da-arte. Cristianini e Shawe-Taylor (2000) (33)
apresentam uma descrição bastante precisa desse algoritmo.
Tendo o arquivo com os vetores, citado acima, todas as características do vetor são
normalizadas para ficarem com valores entre -1 e +1, avaliamos também o desempenho do
classificador sem a normalização.
O SVM exige também a divisão da coleção em partes, para que uma parte seja utilizada para o treino (fase de aprendizagem), outra para teste (a que é realmente classificada, de
onde os resultados são obtidos) e a última para validação (para evitar overfitting, ou seja, a especialização do modelo gerado para um único conjunto de teste). Essa abordagem é conhecida
como validação cruzada, onde divide-se a base em n partes e as combina de maneiras distintas,
com a média de todas as combinações (cada uma é também conhecida como fold) sendo o resultado. Na base GeDa fez-se 10-fold cross-validation e na Splog, 5-fold cross-validation. Essa
diferença se deve ao tamanho das bases.
Classificou-se oito situações diferentes em cada base, que é o resultado da presença ou
ausência de stemming, stop words e pesos nas arestas. Os resultados desse procedimento são
apresentados nas próximas seções, divididos por coleção.
6.1.2 GeDa
O método utilizado como baseline foi proposto por Lee e Myaeng (2002) e ele se baseia
“no uso de estatísticas de dois conjuntos diferentes de classes, gênero e assunto, no conjunto de
treino ”(19), ou seja, ele busca palavras que são discriminantes entre diferentes gêneros, levando
em consideração sua distribuição e frequência nos documentos. Por não ter sido disponibilizado
o código e por se utilizar uma base nova na literatura, esse algoritmo teve de ser implementado
para essa comparação.
Realizou-se a classificação da maneira descrita na seção anterior. O método proposto
se mostrou indiferente para a utilização ou não de pesos nas arestas, stop words ou stemming;
ou seja, os resultados não variaram em nenhum dos oito cenários propostos (combinação das
configurações discutidas). Validou-se essa afirmação de que o método independe dos cenários
com um Teste T de significância estatística com uma confiabilidade de 95%.
Pelo método ser indiferente à essas alterações, apresentar-se-á somente os resultados
de uma configuração, a de menor custo, que gera o menor grafo, ou seja: Sem stop-words, sem
pesos e com stemming. Para uma justiça maior, utilizou-se a mesma configuração no baseline.
28
Os resultados são apresentados de duas formas: primeiramente se apresenta a matriz
de confusão do método e, posteriormente, os resultados de acurácia e macro-F1. Podemos
definir acurácia como sendo o total de documentos classificados corretamente dividido pelo
número total de documentos. A macro-F1 é a média aritmética dos F11 de cada classe. Não
há problema em utilizar essa métrica por todas as classes terem aproximadamente o mesmo
número de documentos.
Fez-se experimentos tanto para os vetores sem normalização quanto para os vetores
normalizados. As matrizes de confusão abaixo apresentam os resultados.
Literário
Científico
Jornalístico
Literário
187
98
217
Científico
104
189
50
Jornalístico
8
13
34
Acurácia
62.54%
63.00%
11.29%
Tabela 6.1: Matriz de Confusão: GeDa com normalização
Literário
Científico
Jornalístico
Literário
280
38
36
Científico
18
215
7
Jornalístico
1
47
258
Acurácia
93.64%
71.66%
85.71%
Tabela 6.2: Matriz de Confusão: GeDa sem normalização
O desempenho do classificador utilizando os vetores normalizados é muito pior. Acreditase que o motivo se origina das características intrínsecas das redes que representam a linguagem,
discutidas por Ferrer-i-Cancho e Sole (2001). As caracteísticas das redes small-world (9) são
ocultadas, provavelmente tornando todos os grafos semelhantes pela perda de escala. Assim
sendo, não foram feitas mais normalizações em nenhuma base.
Os resultados relativos à remoção ou não de stop words, stemming são interessantes
de serem discutidos: Esse método se mostra independente de pequenas variações no texto,
ele se torna independente de uma palavra específica ou um conjunto de palavras, mostrando
que possíveis variações seriam ignoradas pelo método, caso fossem pequenas, como erros de
digitação ou utilização de pronomes, novamente, a estrutura do texto que é importante.
Baseado em toda a discussão anterior, o baseline foi utilizado com a configuração de
ausência de stop words e pesos, e com a realização de stemming. Os resultados obtidos são
apresentados na tabela abaixo:
1 média
harmônica da precisão e revocação, é dada por: F =
2×P×R
(P+R)
onde P é precisão e R é revocação.
29
Literário
Científico
Jornalístico
Literário
300
0
0
Científico
0
300
0
Jornalístico
0
0
300
Acurácia
100.0%
100.0%
100.00%
Tabela 6.3: Matriz de Confusão: Baseline
A tabela 6.4 sumariza os resultados, possibilitando a comparação dos resultados do
método proposto e do baseline.
Método
Proposto Com Normalização
Proposto Sem Normalização
Baseline
Macro-F1 Acurácia
41.53%
45.56%
83.47%
83.67%
100.00% 100.00%
Tabela 6.4: Sumário dos resultados do método proposto e do baseline
A análise da razão da derrota do método proposto para o baseline é essencial: O baseline leva em consideração a frequência das palavras nos textos de cada classe e na coleção como
um todo, assim sendo, ele consegue classificar grande parte dos documentos com regras muito
simples, por exemplo, baseadas na frequência de palavras como “abstract”, “references”, datas,
etc; o método proposto não leva isso em consideração. Sem a utilização de indícios tão fortes,
a verificação dos padrões de frequência, a derrota é óbvia.
Apesar da derrota, esse experimento nos apresentou informações muito úteis como a
importância da não normalização dos dados, e o fato de stop words e pesos nas arestas não
serem importantes, assim como o stemming. As stop words não serem importantes até é um
resultado esperado, mas não se esperava que stemming não fosse importante.
Além de análises relativas ao método, os resultados finais da classificação mostraram
que há um potencial grande de melhoria, uma vez que obteve-se um Macro-F1 de 83.67% em
um problema no qual o método não tem a menor especialização. Observou-se também que a
classe mais “difícil” para o método é a classe científica, provavelmente por possuir documentos
de áreas tão diversas, principalmente a área humana, que se assemelha mais à outros gêneros
textuais. O desempenho excepcional do baseline se deve ao fato dele utilizar frequências, isso
porque algumas palavras nos textos identificam sua origem2 , logo, ele sempre acerta a classe,
ou seja, essa base dá a resposta para o método.
2 Por
exemplo, “from Gutemberg Project”, ou “Proceedings of ...”.
30
6.1.3 Splog
O método utilizado como baseline foi proposto por Kolari, Finin e Joshi (2006), onde
os autores utilizam características como bag-of-urls,bag-of-anchor, n-grams, além de abordagens tradicionais como bag-of-words para realizar a classificação de splogs. Muitas combinações foram discutidas em (7), aqui apresentaremos apenas o melhor resultado, que utiliza
bag-of-urls e o texto.
Os resultados do baseline estão apresentados em termos de Precisão, Revocação e F-1
em (7), para uma coerência com o mesmo, os resultados do método proposto também serão
apresentados em função dessas métricas de avaliação.
Assim como na GeDa, o método se mostrou indiferente à utilização ou não de stemming, de stop words e de peso nas arestas (confirmado com o Teste T de significância estatística com uma confiabilidade de 95%). Assim sendo, como na seção anterior, apresenta-se os
resultados da situação mais “barata” computacionalmete, ou seja: sem stop-words e pesos,
mas com stemming. Devido à grande diferença de desempenho entre o método quando normalizado e quando não normalizado, apresenta-se aqui apenas os resultados para o método
não-normalizado. Essa diferença é justificada por todos os argumentos da seção anterior. Os
resultados da classificação utilizando o método proposto são apresentados na Tabela 6.5
Splogs
Splogs
113
Blogs
56
Blogs Acurácia
26
81.29%
84
60.00%
Tabela 6.5: Matriz de Confusão: Splogs (Método proposto)
A Tabela 6.6 apresenta os resultados do método proposto e do baseline. Os valores
apresentados são a média aritmética de cada métrica de avaliação para as duas classes.
Método
Proposto
Baseline
Precisão Revocação
F1
71.5%
70.5%
71.0%
89.3%
86.9%
88.1%
Tabela 6.6: Sumário dos resultados do método proposto e do baseline (7)
Observa-se que novamente o método proposto perde para o baseline, mas a mesma
argumentação da seção anterior é válida: O método proposto é genérico, ele não é especializado
em um problema específico e, por isso, deixa de levar em consideração aspectos importantes,
como as urls, conforme provado em (7). Nesse trabalho os autores confirmam essa afirmação
31
ao dizerem que métodos baseados apenas em classificação de textos são insuficientes para essa
detecção.
Apesar de um resultado ruim com relação ao baseline, quando comparamos com outros
métodos, novamente confirmamos a hipótese de que essa modelagem é interessante. Técnicas
baseadas em heurísticas, e disponíveis para uso público3 conseguiram uma precisão de 66% e
uma revocação de 60% nessa mesma coleção, ou seja, o método proposto as supera. É importante salientar que há uma dificuldade enorme de classificação utilizando nosso método porque
existem fake blogs na base, ou seja, textos normais, mas copiados. Uma vez que buscamos
diferentes padrões de escrita, o método nunca conseguirá capturar esses splogs. Finalmente,
observando a Tabela 6.5 verifica-se que classificou-se muitos blogs como splogs, isso porque
o método “aprendeu errado” com os fake blogs, passando a achar que textos “normais” eram
splogs.
6.2
Distribuição acumulada
6.2.1 Metodologia
Esse experimento consistiu em plotar as curvas de distribuição acumulada (CDF) das
métricas discutidas no capítulo 4. Plotou-se as CDFs para as doze métricas de cada coleção.
Além disso, obteve-se o valor médio de cada métrica para cada classe na coleção, além do
intervalo de confiança. Por fim, fez-se testes de significância estatística (ANOVA para GeDa e
Teste T para Splog) com o intuito de validar os dados.
Todos os dados utilizados nessa fase são extraídos dos vetores gerados inicialmente.
Cada dimensão é uma métrica, um único valor, e esses valores é que são utilizados aqui.
Durante essa seção utiliza-se o termo “métrica discriminativa (ou não)” com base na
análise dos gráficos apresentados nas próximas seções. Essa análise se baseia em três fatores:
1) A distância entre as curvas que representam cada classe; 2) a distância relativa ao longo da
curva, i.e., algumas curvas podem estar próximas em algumas partes do gráfico e longe em
outras; 3) os valores médios de cada métrica, por classe.
Nos CDFs, o eixo x representa o valor da métrica e o eixo y a porcentagem de documentos da classe que têm o valor dessa métrica menor ou igual ao valor no eixo x. A interpretação
desses gráficos pode ser feita utilizando a Fig. 6.1(a) como exemplo, onde aproximadamente
18% dos documentos jornalísticos possuem um coeficiente de clusterização menor ou igual
3 http://antisplog.net/
32
à 0.1, enquanto 36% dos documentos científicos têm a mesma métrica abaixo desse valor e,
finalmente, 80% dos documentos literários estão abaixo desse valor.
Foi dito que a distância entre as curvas que representam classes específicas é importante, isso porque quanto mais distantes as curvas estiverem, maior é a diferença percentual
de documentos que estão em faixas de valores diferentes. As distâncias relativas ao longo da
curva também são interessantes de se analisar. Se duas curvas estão próximas uma à outra por
todo o gráfico, essas métricas certamente são inúteis, mas se elas estão próximas apenas em um
determinado intervalo, elas podem ser discriminantes fora desse intervalo. A Fig. 6.2(a) ilustra
a afirmação anterior, antes do valor 2000, o betweenness médio pode auxiliar na diferenciação
dos gêneros jornalísticos e científicos, mas após esse valor, certamente ele não ajuda.
Tanto para essa coleção quanto para a Splog serão apresentadas seis CDFs, três sendo
“boas métricas” e três não sendo.
6.2.2 GeDa
Todas as métricas da coleção GeDa possuem valores médios distintos, estatisticamente
significantes, confirmados com um teste ANOVA sobre os valores médios de cada classe — por
termos três classes, esse teste se mostrou necessário. Apesar disso, baseado na visualização do
gráfico classificou-se as métricas em dois grupos: “boas” e “não tão boas” (evitou-se o termo
100
100
90
90
80
80
70
70
P(X <= x)
P(X <= x)
“ruim” por ainda sim serem discriminantes).
60
50
40
30
60
50
40
30
20
20
Literario
Cientifico
Jornalistico
10
Literario
Cientifico
Jornalistico
10
0
0
0
0.1
0.2
0.3
0.4
0.5
0.6
Coeficiente de Clusterizacao
0
0.05
0.1
0.15
0.2
Densidade
Figura 6.1: “Boas métricas” para a GeDa
As métricas consideradas “boas” para essa coleção foram: grau médio e máximo, betweenness médio, coeficiente de clusterização, closeness médio e máximo, densidade e número
de componentes conectados. As “não tão boas” foram: betweenness máximo, diâmetro, caminho mínimo médio e tamanho do componente gigante.
CDFs de três métricas “boas” são apresentadas nas Fig. 6.1(a-b) e na Fig. 6.2(a). As
33
explicações para esses resultados são baseadas na premissa de que diferentes gêneros textuais
são escritos em diferentes padrões, e que essas diferenças são capturadas pelas métricas.
A análise dos gráficos está vinculada à uma análise das características dos gêneros
textuais: O gênero literário, por exemplo, tende geralmente a apresentar uma diversidade maior
de palavras do que os textos científicos e jornalísticos. Pode-se observar também que os textos
jornalísticos tendem a utilizar menos palavras do que todos, já que um texto mais direto e
conciso é desejado, o que implica em um uso menor de sinônimos. Esses diferentes padrões de
escrita induzem as diferenças observadas no gráfico de densidade (Fig. 6.1(b)), já que o gênero
100
100
90
90
80
80
70
70
P(X <= x)
P(X <= x)
jornalístico é o que tem a menor densidade, na média.
60
50
40
30
Literario
Cientifico
Jornalistico
60
50
40
30
20
Literario
Cientifico
Jornalistico
10
0
20
10
0
0
500 1000 1500 2000 2500 3000 3500 4000
Betwenness Medio
0.86
0.88
0.9
0.92
0.94
0.96
0.98
1
Tamanho do Componente Gigante
Figura 6.2: Outras métricas para GeDa
Altos valores da métrica betweenness médio são causados por padrões de repetição.
Textos jornalísticos são mais repetitivos (utilizam menos sinônimos, como discutido no parágrafo anterior, logo repetem mais) possuindo um betweenness médio maior do que os outros
gêneros, vide Fig. 6.2(a). O betwennes máximo não é considerado uma “boa” métrica com
relação ao gráfico, mas ao se analisar seus valores médios, fica nítida sua utilidade.
Outras características dos gêneros descritas abaixo justificam as diferenças entre os
valores das métricas. Por exemplo, o coeficiente de clusterização (Fig. 6.1(a)) possui um valor
maior quando partes diferentes do texto estão relacionadas. Não é suficiente que as mesmas
palavras apareçam em partes diferentes, as palavras próximas à elas devem aparecer também no
mesmo contexto. O gênero literário possui muito menos palavras relacionadas entre si, consequentemente um coeficiente de clusterização menor, já que suas palavras aparecem em diversos
contextos. Os textos jornalísticos sempre tratam do mesmo assunto com um vocabulário restrito, consequentemente seu coeficiente de clusterização é maior.
O gênero jornalístico também tende a ser mais coeso, com palavras aparecendo em
padrões específicos. Uma vez que os grafos são não ponderados, o grau máximo e médio estão
diretamente relacionados ao número de arestas diferentes no texto. Um grau médio alto é con-
34
seguido quando palavras se relacionam com um grande número de palavras distintas. Com base
nessa discussão pode-se dizer que o gênero literário é o que possui um grau máximo e médio
maior (e, como esperado, os textos jornalísticos possuem os menores). Essas suposições também são confirmadas pelo closeness máximo e médio, já que essas métricas medem o quão perto
um vértice está dos outros. Como esperado, o gênero jornalístico possui os maiores valores de
100
100
90
90
80
80
70
70
P(X <= x)
P(X <= x)
closeness.
60
50
40
30
60
50
40
30
20
20
Literario
Cientifico
Jornalistico
10
Literario
Cientifico
Jornalistico
10
0
0
0
5
10
15
20
Diametro
2
2.5
3
3.5
4
Caminho Minimo Medio
Figura 6.3: “Não tão boas” métricas para a GeDa
A métrica número de componentes conectados também segue esse padrão, textos jornalísticos possuem praticamente todas as sentenças interconectadas, enquanto textos literários
não, devido à liberdade poética, frases soltas e palavras desconexas acabam se tornando componentes isolados.
Um exemplo de métrica “não tão boa” é o tamanho do componente gigante (Fig. 6.2(b))
já que praticamente todo o texto é conectado em todos os gêneros. Entretanto, até mesmo essa
métrica tem sua utilidade, já que nos diz que textos jornalísticos tendem ser mais conectados,
como discutido acima. Nessa métrica, textos literários são os mais desconectados, como esperado. As “piores” métricas são o diâmetro e o caminho mínimo médio (Fig. 6.3), já que toda
rede que representa textos possui aspectos relacionados à redes small-world (9), independentemente do seu gênero (27).
Gênero
Literário
Científico
Jornaístico
p
Grau médio
10.384(±0.166)
8.840(±0.162)
3.807(±0.136)
0.000
Grau máximo
4024.084(±135.711)
1793.435(±75.142)
664.974(±84.494)
0.000
Cam. Min. Medio
2.717(±0.007)
2.835(±0.017)
2.949(±0.014)
0.000
Diâmetro
7.358(±0.092)
8.053(±0.132)
6.868(±0.069)
0.000
Tabela 6.7: Primeiras Quatro Métricas da GeDa
O gênero científico não foi citado nessa discussão porque suas métricas sempre estão
entre os gêneros jornalístico e literário, isso é algo até intuitivo, uma vez que esse gênero não
35
possui textos tão diretos quanto os textos jornalísticos (que na maioria das vezes são pragmáticos e objetivos). Eles podem também discutir vários tópicos, citar diversos trabalhos, utilizar
diversos métodos, etc, o que os deixa mais “desconexos”. Apesar disso, os textos científicos
estão longe de serem tão subjetivos e “amplos” quanto os textos literários.
Gênero
Literário
Científico
Jornaístico
p
Coef. Clust.
0.075(±0.001)
0.118(±0.002)
0.203(±0.004)
0.000
Tam. Comp. Gig.
0.9813(±0.0010)
0.9877(±0.0008)
0.9843(±0.0018)
0.000
Num. Comp. Con.
29.088(±1.352)
12.668(±0.658)
4.559(±0.540)
0.000
Bet. Medio
2482.12(±56.06)
1279.95(±38.79)
556.35(±49.06)
0.000
Tabela 6.8: Outras Quatro Métricas da GeDa
De forma complementar à esses gráficos, calcula-se também os valores médios com
seus respectivos intervalos de confiança. As Tabelas 6.7, 6.8 e 6.9 apresentam os resultados
para a GeDa.
Utilizou-se o teste ANOVA para verificar as diferenças dos valores médios de cada
classe. Adotou-se um nível de significância de 1% (α = 0.01) e os resultados mostram que os
valores médios de todas as métricas são diferentes entre as classes (p=0.000).
Gênero
Literário
Científico
Jornaístico
p
Bet. Max.
1730115(±75523)
468903(±36496)
306926(±47483)
0.000
Clos. Med.
0.00043(±0.00001)
0.00243(±0.00029)
0.01166(±0.00056)
0.000
Clos. Max.
0.0485(±0.0019)
0.1337(±0.0066)
0.3396(±0.0089)
0.000
Densidade
0.0087(±0.0002)
0.0203(±0.0011)
0.0504(±0.0019)
0.000
Tabela 6.9: Últimas Quatro Métricas da GeDa
As Tabelas 6.7, 6.8 e 6.9 apresentam os resultados dos testes estatísticos, os valores
médios para cada métrica de cada cada classe e o intervalo de confiança de 99%. Até mesmo as
métricas “não tão boas” (Caminho mínimo médio, Diâmetro, Betweenness máximo e Tamanho
do Componente Gigante) mostraram uma tendência de possuir valores ligeiramente diferentes
para as três classes. Apesar dos valores próximos de média para essas características nas três
classes, o intervalo de confiança é muito pequeno, mostrando que essas médias são realmente
diferentes.
6.2.3 Splog
Assim como na seção anterior, não há muito o que se discutir com relação à esse teste,
uma vez que ele já foi explicado previamente. Essa seção visa apresentar os resultados, também
36
já discutidos parcialmente na seção de classificação. Não julgou-se necessário dividir as métricas em “boas” e “ruins”, como feito anteriormente, porque todas possuem um comportamento
muito similar, como pode ser visto nos Gráficos 6.4, 6.5 e 6.6.
100
100
90
90
80
80
P(X <= x)
P(X <= x)
70
60
50
40
70
60
30
20
50
Splog
Blog
10
0
Splogs
Blogs
40
0
0.1
0.2
0.3
0.4
0.5
0
0.1
Coeficiente de Clusterizacao
0.2
0.3
0.4
0.5
0.6
Densidade
Figura 6.4: Métricas Splog
Obviamente cada métrica é mais ou menos discriminante que outra, mas a discussão
com base na análise dos gráficos seria leviana, devido à proximidade das curvas em vários
casos. Observa-se que as métricas são menos discriminantes quando comparadas às métricas na
GeDa, e isso já é esperado quando se considera o fato de que splogs tentam ludibriar qualquer
análise se passando por blogs.
Outra característica que provavelmente influenciou o resultado do nosso método foi o
parsing, que se resumiu a retirar todas as tags HTML dos blogs. Não houve um tratamento
diferenciado para comentários e posts, o que não deixa de ser outra generalização que piora os
nossos resultados.
Assim como na seção anterior, calculou-se o valor médio de cada métrica para cada
classe e aplicou-se um teste de significância estatística para verificar se os valores médios são
ou não estatisticamente significantes. Para a coleção aplicou-se o Teste T com uma confiança
de 99% (α =0.01), isso porque temos apenas duas classes, e não mais como na GeDa.
100
70
90
60
Splogs
Blogs
80
50
P(X <= x)
P(X <= x)
70
60
50
40
30
40
30
20
20
10
Splog
Blog
10
0
0
0
500
1000 1500 2000 2500
Betwenness Medio
3000
3500
0.86
Figura 6.5: Métricas Splog
0.88
0.9
0.92 0.94 0.96 0.98
Tamanho do Componente Gigante
1
37
As Tabelas 6.10, 6.11 e 6.12 apresentam os valores médios de cada métrica e o resultado do teste estatístico (p). Como esperado, as métricas propostas não possuem um poder
discriminativo tão alto, uma vez que seis delas não possuem médias diferentes para as duas
classes (p < 0.01).
As métricas que possuem médias diferentes são: Grau médio, Coeficiente de Clusterização, Betweenness médio, Closeness médio, Closeness máximo e Densidade; enquanto as
métricas não discriminantes são: Grau máximo, Caminho Mínimo médio, Diâmetro, Tamanho
100
100
90
90
80
80
70
70
P(X <= x)
P(X <= x)
do Componente Gigante, Número de Componentes Conectados e, Betweenness máximo.
60
50
40
30
60
50
40
30
20
20
Splog
Blog
10
Splogs
Blogs
10
0
0
0
2
4
6
8
10
12
14
2
Diametro
2.5
3
3.5
4
Caminho Minimo Medio
Figura 6.6: Métricas Splog
Uma análise mais detalhada nos permite entender o motivo de algumas métricas possuírem valores médios diferentes. É interessante observar que apesar de splogs tentarem ludibriar qualquer filtro, eles não conseguiram enganar algumas métricas, mostrando a dificuldade
de se enganhar, ao mesmo tempo, todas as métricas propostas. Novamente, o resultado ruim
se dá por causa dos fake blogs, tipo de spam indetectável por esse método. Assim sendo, essa
análise será focada nos outros tipos spam, i.e., seu comportamento.
Tipo
Splogs
Blogs
p
Grau médio
4.7396(±0.1729)
5.4222(±0.3411)
0.0000
Grau máximo
536.2892(±55.0725)
572.8919(±120.4415)
0.0999
Cam. Min. Medio
Diâmetro
2.8522(±0.0214) 6.4374(±0.1260)
2.8861(±0.0291) 6.6369(±0.1696)
0.0351
0.3868
Tabela 6.10: Primeiras Quatro Métricas da Splog
Spam blogs geralmente objetivam divulgar um produto, e muitas vezes seu conteúdo é
gerado automaticamente. Essa publicidade normalmente é feita com repetição de palavras em
vários pontos do texto, que inevitavelmente distorce o grafo correspondente, consequentemente
suas métricas. Com padrões de repetição muito bem definidos, as palavras de um texto acabam
por se associar em padrões muito específicos, formando pequenos grupos de relação, isto é
facilmente evidenciado pelo fato do coeficiente de clusterização dos splogs ser maior, uma vez
38
que palavras em blogs se relacionam de uma forma mais distribuída, o que acaba por diminuir
o seu coeficiente de clusterização.
Tipo
Coef. Clust.
Splogs 0.1148(±0.0042)
Blogs 0.1400(±0.0062)
p
0.0000
Tam. Comp. Gig.
0.9932(±0.0013)
0.9943(±0.0035)
0.1051
Num. Comp. Con.
Bet. Medio
5.6719(±3.2534) 651.9811(±45.3958)
4.8530(±1.5536) 538.7107(±50.8479)
0.4764
0.0000
Tabela 6.11: Outras Quatro Métricas da Splog
Baseado na premissa do parágrafo anterior, todas as outras métricas, como o grau médio, podem ser explicadas. Como os os blogs não possuem um padrão de repetição, as palavras
formam mais relações, essas relações acabam por aumentar o grau médio dos vértices, isto
porque o grafo analisado é não ponderado, logo, a repetição de uma ocorrência é simplesmente
ignorada. Uma consequência direta de um maior grau médio é uma maior densidade, já que
essa última é definida como uma relação do número de arestas e do número máximo de arestas
possíveis. Como blogs possuem um grau médio maior, eles possuem um número maior de
arestas, logo essa métrica pode ser diretamente inferida.
Pelo simples fato das palavras de um blog se relacionarem de forma mais “arbitrária”
do que de splogs, percebe-se que o closeness máximo e médio desse primeiro é maior. Como
dito no Capítulo 4, o closeness mede quão perto as palavras estão das outras. Com mais relações,
formam-se pontes entre grupos do texto que diminuem essa distância. Isso ocorre com bem
menos frequência nos splogs.
Por fim, o betweenness médio corrobora nossa hipótese inicial. Essa métrica representa o número de caminhos mínimos que passa por um determinado vértice, observamos que
ela possui um valor maior para os splogs, isso porque vários caminhos mínimos passam por
palavras centrais, aumentando a média dessa métrica em relação aos blogs.
Tipo
Bet. Max.
Splogs 126933(±22442)
Blogs 105533(±29161)
p
0.6796
Clos. Med.
0.2339(±0.0103)
0.2553(±0.0114)
0.0000
Clos. Max.
0.3341(±0.0182)
0.3737(±0.0199)
0.0000
Densidade
0.02328(±0.00295)
0.06027(±0.02463)
0.0001
Tabela 6.12: Últimas Quatro Métricas da Splog
Não há sentido em discutir as métricas que não possuem médias diferentes para as
duas classes, essas métricas simplesmente não conseguiram capturar padrões distintos entre os
textos, algumas por motivos mais óbvios como o Caminho Mínimo médio e Diâmetro estarem
diretamente relacionados às propriedades de redes small-world (9) enquanto outras foram bem
reproduzidas pelos splogs, mesmo que isso tenha sido sem querer. Não é improvável que a
tentativa de imitação de um blog real tenha tido êxito em alguns aspectos.
39
7
CONCLUSÕES E TRABALHOS FUTUROS
Apresentou-se nesse trabalho uma modelagem de documentos textuais e a idéia, até
onde se sabe inovadora, de utilizar métricas de redes complexas extraídas dos grafos gerados
como evidência para a classificação de textos de diferentes tipos.
O poder discriminativo dessas características foi validado através da classificação dos
documentos, da análise das curvas de distribuição acumulada e da diferença estatística das médias das doze métricas utilizadas na classificação de duas coleções: de gêneros e de splogs.
Apesar da não obtenção de excelentes resultados na classificação, as outras análises
se mostraram animadoras com relação à hipótese do trabalho, levando nos a crer que ela é
verdadeira, ou seja, as métricas são realmente discriminantes na classificação de documentos
de diferentes classes. Provalmente o método proposto não ganhou dos baselines por ignorar
informações valiosas na classificação, como, por exemplo, coisas intuitivas como a frequência
de palavras em diferentes gêneros (abstract e references em textos científicos, por exemplo)
—o que não é ignorado pelo baseline— até características não tão intuitivas como a utilização
de links nos splogs, informação comprovadamente útil (23).
Baseado na argumentação do parágrafo anterior, como trabalho futuro seria interessante mostrar que esse método é genérico e útil à várias aplicações, apresentando métricas que
auxiliam na classificação de documentos mas que não bastam por si só. Para isso, mais bases
teriam de ser incorporadas ao trabalho, para ampliar o escopo do mesmo. Uma base de provável
utilização é a ACM, onde avaliaremos a classificação de artigos utilizando tanto a rede do texto
quanto a rede de citações como evidências para a classificação.
Outra análise interessante a ser feita futuramente é o impacto da variação do limiar na
modelagem do texto, que foi fixado como dois nesse trabalho, além de aplicar esse método a
coleções com vários idiomas, para estudar o impacto de diferentes idiomas no método. Essa
modelagem também pode ser estendida outras aplicações, caso se consiga mostrar que agrega
informação aos modelos. Alguns dos problemas que ela poderia ter aplicação são identificação
de autoria e/ou de informações maliciosas em uma coleção, entre vários outros.
40
Referências Bibliográficas
1 KESSLER, B.; NUNBERG, G.; SCHIITZE, H. Automatic detection of text genre. In:
Eighth Conference of the Association for Computational Linguistics. [S.l.: s.n.], 1997. p.
32–38.
2 BRODER, A. A taxonomy of web search. SIGIR Forum, ACM, v. 36, n. 2, p. 3–10, 2002.
ISSN 0163-5840.
3 ASSIS, G. T. de et al. Exploiting genre in focused crawling. In: SPIRE. [S.l.: s.n.], 2007. p.
62–73.
4 BOESE, E. S.; HOWE, A. E. Effects of web document evolution on genre classification. In:
CIKM. [S.l.]: ACM, 2005. p. 632–639. ISBN 1-59593-140-6.
5 ANDROUTSOPOULOS, I. et al. An evaluation of naive bayesian anti-spam filtering.
CoRR, cs.CL/0006013, 2000.
6 NEWMAN, M. E. J. The structure and function of complex networks. SIAM Review, SIAM,
v. 45, n. 2, p. 167–256, 2003.
7 KOLARI, P.; FININ, T.; JOSHI, A. SVMs for the Blogosphere: Blog Identification and
Splog Detection. In: AAAI Spring Symposium on Computational Approaches to Analysing
Weblogs. [S.l.: s.n.], 2006.
8 JIN, W.; SRIHARI, R. K. Graph-based text representation and knowledge discovery. In:
SAC ’07: Proceedings of the 2007 ACM symposium on Applied computing. New York, NY,
USA: ACM, 2007. p. 807–811. ISBN 1-59593-480-4.
9 WATTS, D. J.; STROGATZ, S. H. Collective dynamics of ‘small-world’ networks. Nature,
Department of Theoretical and Applied Mechanics, Cornell University, Ithaca, New York
14853, USA. [email protected], v. 393, n. 6684, p. 440–442, 1998. ISSN 0028-0836.
10 DOROGOVTSEV, S. N.; MENDES, J. F. F. Language as an evolving word web. Proc. of
The Royal Soc. of London. Series B, Biological Sciences, v. 268, n. 1485, p. 2603–2606, 2001.
11 ANTIQUEIRA, L. et al. Strong correlations between text quality and complex networks
features. Phys. Rev. A, v. 373, p. 811, 2007.
12 ARGAMON, S.; DODICK, J. Conjunction and modal assessment in genre classification:
A corpus-based study of historical and experimental, science writing. In: In Notes of AAAI
Spring Symposium on Attitude and Affect in Text. [S.l.: s.n.], 2004.
13 KARLGREN, J.; CUTTING, D. Recognizing text genres with simple metrics using
discriminant analysis. In: . [S.l.: s.n.], 1994. p. 1071–1075.
41
14 STAMATATOS, E.; KOKKINAKIS, G.; FAKOTAKIS, N. Automatic text categorization
in terms of genre and author. Comput. Linguist., MIT Press, Cambridge, MA, USA, v. 26, n. 4,
p. 471–495, 2000. ISSN 0891-2017.
15 WOLTERS, M.; KIRSTEN, M. Exploring the use of linguistic features in domain
and genre classification. In: Proceedings of the ninth conference on European chapter
of the Association for Computational Linguistics. Morristown, NJ, USA: Association for
Computational Linguistics, 1999. p. 142–149.
16 FREUND, L.; CLARKE, C. L. A.; TOMS, E. G. Towards genre classification for ir in the
workplace. In: IIiX: Proceedings of the 1st international conference on Information interaction
in context. New York, NY, USA: ACM, 2006. p. 30–36. ISBN 1-59593-482-0.
17 PENG, F.; SCHUURMANS, D.; WANG, S. Language and task independent text
categorization with simple language models. In: Proceedings, Human Language Technology
Conference of the North American Chapter of the Association for Computational Linguistics.
[S.l.: s.n.], 2003. p. 110–117.
18 BAEZA-YATES, R.; RIBEIRO-NETO, B. Modern Information Retrieval. 1st. ed. [S.l.]:
Addison Wesley, 1999. Paperback. ISBN 020139829X.
19 LEE, Y.-B.; MYAENG, S. H. Text genre classification with genre-revealing and
subject-revealing features. In: SIGIR ’02: Proceedings of the 25th annual international ACM
SIGIR conference on Research and development in information retrieval. New York, NY, USA:
ACM, 2002. p. 145–150. ISBN 1-58113-561-0.
20 DECORO, C.; BARUTCUOGLU, Z.; FIEBRINK, R. Bayesian aggregation for
hierarchical genre classification. In: International Symposium on Music Information Retrieval
2007. [S.l.: s.n.], 2007.
21 JR., C. N. S.; KOERICH, A. L.; KAESTNER, C. A. A. A Machine Learning Approach to
Automatic Music Genre Classification. Journal of the Brazilian Computer Society, Brazilian
Computer Society (SBC), v. 14, n. 3, p. 7–18, September 2008. ISSN 0104-6500.
22 MACDONALD, C.; OUNIS, I. The TREC Blogs06 Collection : Creating and Analysing a
Blog Test Collection. [S.l.], 2006.
23 DATTA, S.; SARKAR, S. A comparative study of statistical features of language in
blogs-vs-splogs. In: AND. [S.l.]: ACM, 2008. p. 63–66. ISBN 978-1-60558-196-5.
24 SCULLEY, D.; WACHMAN, G. M. Relaxed online svms for spam filtering. In: SIGIR’07:
Proceedings of the 30th annual international ACM SIGIR conference on Research and
development in information retrieval. New York, NY, USA: ACM, 2007. p. 415–422. ISBN
978-1-59593-597-7.
25 MISHNE, G.; CARMEL, D.; LEMPEL, R. Blocking blog spam with language model
disagreement. In: Proceedings of the First International Workshop on Adversarial Information
Retrieval on the Web. [S.l.: s.n.], 2005.
26 KOLARI, P. et al. Detecting Spam Blogs: A Machine Learning Approach. In: Proceedings
of the 21st National Conference on Artificial Intelligence (AAAI 2006). [S.l.]: University of
Maryland, Baltimore County, 2006.
42
27 Ferrer-i-Cancho, R.; SOLE, R. V. The small world of human language. Proc. of The Royal
Soc. of London. Series B, Biological Sciences, v. 268, n. 1482, p. 2261–2265, 2001.
28 CAMP, M. van de. Explorations into Unsupervised Corpus Quality Assessment.
Dissertação (Mestrado) — Tilburg University, Faculty of Humanities, 2008.
29 CHOUEKA, Y.; LUSIGNAN, S. Disambiguation by short contexts. Computers and the
Humanities, n. 19, p. 147–158, 1985.
30 Wikipedia, the free encyclopedia. Brown Corpus. http://en.wikipedia.org/wiki/
Brown_Corpus.
31 HARMAN, D. Overview of the third text retrieval conference (trec-3). In: TREC-3. [S.l.:
s.n.], 1994. p. 1–19.
32 CHANG, C.-C.; LIN, C.-J. LIBSVM: a library for support vector machines. [S.l.], 2001.
Software available at http://www.sie.ntu.edu.tw/~jlin/libsvm.
33 CRISTIANINI, N.; SHAWE-TAYLOR, J. An introduction to support vector machines:
and other kernel-based learning methods. 1. ed. [S.l.]: Cambridge University Press, 2000.
Hardcover. ISBN 0521780195.