Universidade Federal de Ouro Preto (UFOP)
Programa de Pós-Graduação em Ciência da Computação (PPGCC)
Reconhecimento de Padrões
Dissimilaridade
David Menotti, Ph.D.
www.decom.ufop.br/menotti
Introdução
• Reconhecimento de padrões em geral
baseia-se na extração de características
capazes de discriminar objetos de
diferentes classes.
• Em alguns casos, porém, a extração de
características se torna complicada
– Desconhecimento do problema
– Dificuldade em definir características
Introdução
• Nesses casos, medidas de dissimilaridade
se tornam bastante interessantes.
• Dissimilaridade
– Valor que expressa a diferença entre dois
objetos
– Zero quando os objetos são idênticos.
• Dissimilarity-based Pattern Recognition
Dissimilaridade para
Representação
• A percepção humana nos permite reconhecer
características comuns em uma coleção de
objetos.
• Em alguns casos pode ser difícil formalizar esse
conhecimento.
• Considere as figuras abaixo
Dissimilaridade para Representação
• Várias medidas podem ser usadas
– Em geral depende do problema
Motivação
• Objetos similares podem ser agrupados
– Pertencem a mesma classe.
• A comparação sempre se dá com base em um
objeto de referência.
– Um ponto de vista particular
– Características básicas.
– Em outras palavras, levando em consideração o
contexto.
– Por exemplo, dois irmãos podem não ser parecidos,
porém quando comparados na presença de seus
pais, pode-se constatar que são parecidos.
Matriz de Dissimilaridade
• A representação por dissimilaridade é baseada
na comparação entre todos os objetos
envolvidos.
• Isso nos leva a uma matriz D, na qual cada
elemento da matriz representa o valor de
dissimilaridade entre dois objetos.
• Considere por exemplo, os seguintes objetos
de duas classes:
Matriz de Dissimilaridade
• A matriz de dissimilaridade ficaria assim
Classificando por Dissimilaridade
• Vizinho mais próximo
– Classificar um objeto X desconhecido na
classe com menor dissimilaridade.
– Não usa a matriz de dissimilaridade
Class(X) = label(argmin(di))
Classificando por Dissimilaridade
• Espaço de dissimilaridade
– Utiliza cada coluna da matriz de dissimilaridade como
um vetor de características.
– Qualquer algoritmo de classificação pode ser
utilizado.
– Seleção dos vetores pode ser benéfica.
Classificando por Dissimilaridade
• Considere por exemplo
– 3 classes
• Classe 1: 4 objetos
• Classe 2: 3 objetos
• Classe 3: 3 objetos
Note que os vetores de características,
(colunas) são similares para objetos
da mesma classe.
Como classificar um exemplo novo X?
-Comparar com a base de referência.
-Gerar o vetor de dissimilaridades.
Matriz de Dissimilaridade Hipotética
Classificador Universal
• A idéia de dissimilaridade pode ser estendida,
permitindo assim a construção de um
classificador universal.
• Bastante interessante quando o número de
classes é bastante grande
– Verificação de Assinaturas
– Identificação de Autoria
– Recuperação de Imagens
• Converter um problema de N classes para duas
classes: Similar ou Não Similar.
Classificador Universal
• Para tornar isso possível, é necessário contar
com um conjunto de referência.
• Diferentemente da classificação baseada em
dissimilaridade, nesse caso a dissimilaridade é
calculada para o vetor de característica.
• Se dois objetos pertencem a mesma classe, os
componentes do vetor de dissimilaridade
terão valores próximo de zero, caso contrário,
terão valores longe de zero.
– V = |A – B|
Estudo de Caso
• Identificação de Autoria
– Suponha que você precise construir um sistema que
diga se o documento foi escrito por uma determinada
pessoa.
– Para treinar seu sistema, estão disponíveis 20
autores, sendo que cada autor contribui com 10
amostras de documentos.
– Opção 1: Criar um classificador com 20 classes
• O que acontece se novos autores forem adicionados?
– Opção 2: Dissimilaridade
Exemplos de Textos
Autor 1
Autor 2
Calculando Dissimilaridades
Base de Treinamento
|A-B|
(A)
(B)
Vetor Próximo
de Zero
|C-D|
(C)
(D)
Vetor Próximo
de Zero
Vetor Longe
de Zero
|A-C|
Treinamento
• Gerar os vetores de dissimilaridade para
duas classes
– Genuíno
• Vetores resultantes das comparações entre os
exemplos de mesmos autores
• Vetores próximo de zero
– Falsificação
• Vetores resultantes da comparações entre os
exemplos de diferentes autores
• Vetores longe de zero
Teste
• Dado um exemplo questionado de um
certo autor X
– Comparar esse exemplo com as referências
do autor X.
– Se o exemplo questionado for realmente do
autor X, a tendência é que essa comparação
gere vetores próximos de zero.
• Logo, pertencente a classe de genuíno.
Teste
• Como geralmente existe mais de um
exemplo de referência, algum método de
tomada de decisão deve ser utilizado
– Voto
– Max
Vantagem
• Adição de novos objetos sem a
necessidade de re-treinar o classificador.
• Redução de um problema de N classes
para 2 classes.