Um Portal Web para a Organização Hierárquica de Notícias

Dissertação de mestrado04/11/2009

Hugo Lima Borges

Orientadora: Profa. Dra. Ana Carolina Lorena

Motivações e objetivos

• Estudar a CHT (Categ. Hierárquica de Textos) e aplicá-lo no contexto de um portal agregador de notícias

• Uso da hierarquia facilita acesso a notícias mais específicas e pode ajudar na categorização

• Avaliar uma boa configuração para o classificador no cenário proposto

Classificação Hierárquica

• Possível ganho na efetividade preditiva (depende do algoritmo)

• Decomposição do problema plano ( possível ganho de desempenho computacional)

• Usada em cenários em que é possível estruturar documentos em uma hierarquia de categorias

Naïve Bayes Plano x Hierárquico (20 Newsgroups)

Etapas Pré-processamento

Representação do texto Redução dimensional

Stemming e cuttof Seleção de atributos

Pesagem de atributos Abordagem hierárquica Algoritmo de classificação Avaliação da efetividade preditiva

Representação do Texto

• Bag of Words (BOW): cada palavra representa um atributo (ou termo)

• Desconsidera posição das palavras• Pesagem dos termos: frequência, binária …

• Alternativas:– Bigrama, trigrama (n-grama)– Análise de Semântica Latente– Extração de termos (ex.: agrupamento)

Stemming e cutoff

• Stemming: redução da palavra para radical (palavras com significado próximo)

• Cutoff: remoção de palavras com baixa/alta frequência que não são representativas para a distinção entre classes (típico: 3 ou 5)

Seleção de atributos• Selecionar atributos mais relevantes para

distinguir as classes• Filtragem ou wrapper

– Atributos que aparecem na classe– Atributos que não aparecem na classe

)|( ik ctP

)|( ik ctP

)()(

)]|()|()|()|([

),(2

2

ik

ikikikik

ik

cptp

ctpctpctpctpN

ct

Multinomial Naïve Bayes (MNB)

• Algoritmo probabilístico (regra de Bayes)• Assume independência dos termos• Variações do algoritmo e heurísticas para

contornar alguns problemas

)(

)|()()|(

j

ijiji dp

cdpcpdcp

MNB (2)

]log[logmaxarg )|cp(d)p(c l(d) ijic

i c

iij NN

Nfcdp

1 )|( ci

D

Dp c

c )(

• Fi – pesagem do termo i no documento dj

• Nci – ocorrências do termo i na classe c

• Nc – ocorrência de termos na classe c

• N – total de termos

• Dc – documentos pertencentes a classe c

• D – total de documentos

MNB (3)

• Eficiente computacionalmente

• Implementação simples

• Fácil adição de exemplos de treinamento

• Pré-processamento é importante

• Nem sempre apresenta boa efetividade

• Necessidade de quantidade mínima de exemplos

Abordagem top-down

• Mais empregada

• Fácil de implementar (algoritmos planos)

• Propagação de erros

• Escalável

x

1 2

1.1 1.2 2.1 2.2

f1_plano

f3_planof2_plano

1.1 1.2 2.1 2.2

Hierarquia

21

Avaliação da efetividade preditiva

||||

||.

||||

||.

ii

ii

ii

ii

FNVP

VPsens

FPVP

VPprec

ii

ii sensprec

sensprecF

..

..21

• Precisão: % das classificações corretas feitas para a classe i

• Sensibilidade: % dos exemplos da classe i classificados corretamente

• F1: igual peso para as duas medidas

Avaliação da efetividade preditiva (2)

• Medida média levando em conta todas as classes:– F1 macro: mesmo peso para todos exemplos– F1 micro: mesmo peso para todas as classes

Medida baseada em distância

• Peso negativo para erros cometidos no primeiro nível

||||

)||,0max(.

||||

)||,0max(.

ii

ii

ii

ii

FNVP

VPsens

FPVP

VPprec

ii

ii

FnConFpCon

FnConFpCon

Medida baseada em distância (2)

• Disθ = 2 : contribuição nula se erro ocorre no segundo nível

• Contribuição igual a -1 se erro ocorre no primeiro nível

Dis

ccDiscdCon

cdConFpCon

vppj

FPdiji

ij

),(1),(

))),(,1max(,1min(

1.1 1.2 2.1 2.2

Hierarquia

21

1

11

1

1 1

predita verdadeira

4),( vp ccDis

Experimentos

• Validação cruzada em 3 partes

• Avaliação F1 micro e macro

• Conjuntos de dados da literatura

• Seleção e pesagem de atributos realizada localmente (em cada classificador na hierarq.)

• Atributos distribuídos igualmente entre classificadores

Conjuntos de Dados da Literatura

Conjunto de Dados

• Hierarquia• # docs• # atributos• Tam. docs• Características

20 Newsgroups (20N)

• 2 níveis (5 / 15)• 13 mil• 28 mil• 308 ± 750• Balanceado• gerado por

usuários

Reuters 21578 (R21)

• 2 níveis ( 4 / 42)• 9 mil• 117 mil• 112 ± 122• Desbalanceado• notícias

Stemming (Porter 2)

• Não houve impacto na efetividade preditiva (todos atributos)

• Impacto + com número baixo de atributos considerados (seleção de atrib.)

• Redução de 18% (20N) e 27% (R21)

• Escolha: usar stemmingConjunto F1 micro F1 micro (1000) F1 micro (100) # atributos

20N 0,80 (0,80) 0,69(0,70) 0,40(0,47) 117019 (95749)

R21 0,83 (0,84) 0,79(0,80) 0,62(0,65) 27873 (20361)

sem stemming (com stemming)

Cutoff

• Remoção de palavras infrequentes no conjunto de testes

• Redução superior a 60% em ambos conjuntos com n = 2

• Pouco impacto na efetividade do classificador (com n baixo)

• Escolha: cutoff mínimo (2)

Cutoff (2)

Seleção de atributos

• Técnicas de filtragem: DF, IG, Chi², OR, BNS

• Atributos são distribuídos igualmente entre as classes (Round Robin)

• Escolha: Chi² (IG)

• Melhores resultados:

– 20N : IG, OR, Chi²

– R21 : IG, Chi²

Seleção de atributos 20N (2)

• macro F1

• macro F1 dist.

Seleção de atributos R21 (3)

• micro F1

• micro F1 dist.

• macro F1

Pesagem de atributos

• TF , binária, TF-IDF, e logTF-IDF

• Resultados:

– 20N: Binária, logTF-IDF

– R21: logTF-IDF, TF-IDF

• Escolha: logTF-IDF

Pesagem de atributos (20N)

• micro F1

• macro F1

• macro F1 dist.

Pesagem de atributos (R21)

• micro F1 dist.

• macro F1 dist.

Comparação MNB x SVM

Conjunto Algoritmo F1 micro F1 macro F1 macro dist. F1 micro dist.

20N MNB 0,83 0,82 0,76 0,75

SVM 0,76 0,76 0,63 0,61

R21 MNB 0,85 0,69 0,81 0,45

SVM 0,90 0,76 0,85 0,64

• MNB x SVM linear (LibSVM), com pesagem, seleção de atributos

Arquitetura do sistema

Base de dados

Agendador de Tarefas

Aplicação Web

Navegador

Capturador Feeds XMLClassificador

Capturador e fontes de notícia

• Feeds RSS/Atom: resumo de notícias

• Foco: Jornais e portais brasileiros

• Cerca de 15 fontes

• Pré-classificação de notícias

• Conjunto de testes:

• 16 mil notícias capturadas em um mês

• Classificação manual

• Tamanho médio: 72 ±83

Hierarquia de notícias

• 2 níveis ( 9 / 38 categorias ), 44 nós folha

• Desbalanceado

• Primeiro nível: Baseada em jornais / portais de notícia

• Não é necessariamente a melhor para o classificador

• Problema com notícias “sem” categoria (outros)

Resultados: Classificação

• Stemming: redução de atributos de 43%

• Primeiro nível: micro F1 = 0,82

• Micro F1: 0,72

• Micro F1 dist. : 0,60

• Macro F1: 0,62

• Macro F1 dist. : 0,40

ResultadosResultados: observações (1)

• Primeiro nível:– Bom desempenho:

• Esportes (0,96) • Economia (0,85)

– Desempenho ruim: • Ciências (0,63), Saúde (0,70) – poucos exemplos• Cotidiano (0,73) – muitos assuntos

ResultadosResultados: observações (2)

• Segundo nível :

– Educação: F1 = 0,75 ; F1 dist. = 0,38

– Biologia: F1 = 0,52 ; F1 dist. = 0,0

– Bolsas de valores: F1 = 0,91 ; F1 dist. = 0,90

– Automobilismo F1 = 0,94 ; F1 dist. = 0,94

– Categorias “Outros” : desempenho ruim em geral

Resultado: Pré-classificação

• 46% dos documentos de teste já classificados (corretamente) no primeiro nível

• Micro F1: 0,77 (0,72)

• Micro F1 dist. : 0,58 (0,69)

• Macro F1: 0,68 (0,62)

• Macro F1 dist. : 0,55 (0,39)

Plano x Hierárquico

• Plano– Micro F1 = 0,71 (0,01)

– Macro F1 = 0,58 (0,01)

– Tempo: 9min

• Hierárquico– Micro F1 = 0,72 (0,01)

– Macro F1 = 0,57 (0,01)

– Tempo: 7min30s

Sistema Informeme

• www.informeme.com• Interface do usuário• Interface do administrador

Trabalhos Futuros (CHT)• Melhorar a hierarquia (2 hierarquias)

• Ponto de vista do usuário

• Buscando melhor efetividade do classificador

• Métodos para “parar” a classificação no primeiro nível

• Automatizar o processo de treinamento

• Notícias completas (ao invés de resumos)

• Abordagem multirrótulos

• Hierarquias maiores, mais exemplos: RCV1

Trabalhos Futuros (aplicação)

• Lidar com notícias repetidas / similares

• Classificação por região

• Recomendação de notícias

• Considerar outros tipos de fontes e dados