Classificação/Categorização
Christian Diego – cdad
Icamaan Viegas – ibvs
Roteiro




Introdução
Construção de classificadores
Aplicações
Algoritmos




Avaliação de Classificadores



Relevance Feedback (Rocchio)
K-Nearest Neighbors
Template Matching
K-Fold Cross Validation
Curva ROC
Referências
Classificação

Definição


Classificar um documento de acordo com
classes previamente definidas
Objetivos



Organizar documentos
Facilitar sua busca automática
Facilitar sua visualização
Classificação
Documentos
Classe 2
Classe 3
Classe 1
Clustering X Classificação

Clustering



Criar grupos de documentos
Classes geradas automaticamente
Classificação


Definir a que grupo pertence um documento
Classes pré-definidas
Construção de Classificadores

Classificação Manual


Construção Manual do Classificador


Realizada por um especialista
Regras escritas manualmente
Construção Automática do Classificador

Algoritmos de aprendizagem automática
Construção Automática

Conjunto de Treinamento


Conjunto de Validação


Treinamento do algoritmo
Ajuste do sistema
Conjunto de Teste

Avaliação do desempenho do sistema
Construção Automática
Documentos
Representação Inicial
Conhecimento
Adicional
Categorização
Indução
Redução da Dimensão
ou
Seleção de Termos
Representação Final
Aplicações

Sites


Emails


Recomendação
Filtro de Spam
Base de documentos
 RSS Feed’s
 Reconhecimento de Assinatura
 Reconhecimento de voz
Atributos

Categóricos

Nomes ou rótulos


Operações


Verde, casado, muito, baixo, pequeno
Igualdade, diferença
Numéricos

Número


Inteiros, Reais
Operações

Igualdade, diferença, adição, subtração...
Distâncias

Diversas maneiras de calcular


Euclidiana, Manhattan, Quadrática, Co-seno...
Problemas


Atributos Categóricos
Um atributo numérico pode ter um peso
excessivo em relação aos demais
Algoritmos

Relevance Feedback (Rocchio)

K-Nearrest Neighbor (k-NN)

Template Matching
Relevance Feedback (Rocchio)

Adaptação para Categorização de Texto




Modelo Vetorial
Utilizando vetores ponderados do TF/IDF
Para cada categoria cria um vetor de
“protótipo”, somando todos os vetores dos
documentos desta categoria
Similaridade por Cosseno
Relevance Feedback (Rocchio)
Classe 1
Classe 2
Relevance Feedback (Rocchio)
Protótipo:
Classe 1
Protótipo:
Classe 2
k-NN




Processo de aprendizagem baseado em
instâncias
Classificação baseado nos k vizinhos mais
próximos
Simplesmente armazena os exemplos de
treinamento
Se utiliza de todos os atributos disponíveis
k-NN
Para 1-NN classifica como +
Para 5-NN classifica como -
k-NN
k-NN

Ponderar o peso de cada vizinho de acordo
com a distância


Robusto a ruído
Maior efetividade quando há uma grande
quantidade de dados de treinamento
k-NN

Desvantagens


O custo de classificação de novos padrões
pode ser alto
Considera todos os atributos, quando apenas
alguns deles podem ser importantes
Template Matching

Utiliza um conjunto de templates para
definir qual mais se aproxima de uma nova
entrada

Aplicações



Reconhecimento de assinatura, voz, faces, etc.
Bioinformática
Estimação de Movimento
Template Matching
Template Matching
Avaliação de Classificadores

É necessário ter métricas para avaliar a
eficácia de um classificador

Como dividir o conjunto de exemplos em
treinamento, validação e testes
K-Fold Cross Validation

O conjunto de exemplos é dividido em K
partes



1 é utilizada para testes
K – 1 é utilizada para treinamento e validação
Iterativo

A parte selecionada para testes é trocada até
que todas tenham sido escolhidas
K-Fold Cross Validation
Example Set
K-Fold Cross Validation

Análise Estatística




Hipótese Nula
Hipótese Alternativa
Nível de confiabilidade - Significância
Utiliza-se após a aplicação do K-Fold Cross
Validation
Curva ROC

Reciever Operating Characteristics

Curva ROC é um método para visualização
e comparação da performance de
classificadores

Não é afetado pelo desbalanceamento das
classes nos exemplos
Curva ROC
Curva ROC
Curva ROC

Área sob a curva

Comparação de dois
algoritmos
Curva ROC

Desvantagens

Problemas com mais de duas classes


Separar em várias Curvas ROC
Problema de desbalanceamento



Cálculo das Áreas
Associar pesos a cada classe
Não é possível visualizar as áreas calculadas
Referências

Tom Fawcett. An introduction to ROC
analysis. Pattern. Recognition Letters, Vol.
27, No. 8., pp. 861-874, 2006.

Slides de George Darmiton e Tsang Ren:
Aprendizagem de Máquina

Slide de Flávia Barros: Mineração da Web
Classificação/Categorização
Christian Diego – cdad
Icamaan Viegas – ibvs