UNICAMP – Universidade Estadual de Campinas
FEEC – Faculdade de Engenharia Elétrica e de Computação
DCA – Departamento de Computação e Automação Industrial
IA 707 – Computação Evolutiva
Prof. Dr. Fernando J. Von Zuben
Uma Proposta Evolutiva para um
Classificador de Distância Mínima
Fábio Gaiotto Dias
[email protected]
RA: 025635
Orientador: Prof. Dr. Roberto de Alencar Lotufo
29 de Junho de 2004
Conteúdo
• Introdução
• Classificador de Distância Mínima
• Medidas de Similaridade
• Algoritmo Genético
• Representação do Cromossomo
• Função de Avaliação (Fitness)
• Estruturas Populacionais
• Experimentos Didáticos
• Experimento Prático
• Conclusão
• Perspectivas
• Referências
Resumo
Este projeto foi desenvolvido no curso da disciplina “IA 707 – Computação
Evolutiva”, ministrado pelo Prof. Dr. Fernando J. Von Zuben, na Universidade
Estadual de Campinas, durante o primeiro semestre de 2004. Sendo apresentado
como projeto de conclusão do curso, visando utilizar os conceitos adquiridos na
disciplina para resolução problemas reais.
O problema prático a ser resolvido é a configuração de um vetor de pesos a
ponderar os vetores de características utilizados em um classificador de distância
mínima, tendo como medida de similaridade a distância euclidiana ponderada.
Este sistema fará o reconhecimento de letras maiúsculas e números obtidos, por
técnicas de visão computacional, de imagens de placas de licenciamento veicular.
Nesta etapa inicial da proposta o objetivo é verificar a funcionalidade e viabilidade
da metodologia. Deste modo, não é garantido obter bons resultados, mas sim um
caminho de melhorias que levarão ao sucesso da metodologia.
Palavras-chave: Computação Evolutiva, Algoritmo Genético, Reconhecimento de Padrões,
OCR (Optical Character Recognition), Classificador de Distância Mínima, Medidas de
Similaridade, Compartilhamento de Fitness, Especiação.
Introdução
Classificar um padrão desconhecido, dado um conjunto de classes
conhecidas, é um problema fundamental em reconhecimento de padrões.
O classificador de distância mínima é um método comum. Consiste em
encontrar o padrão de maior similaridade em um conjunto de referências
utilizando uma medida de distância, também conhecida como medida de
similaridade.
Cada padrão é descrito por um conjunto de características denominado
vetor de características. Sendo assim, os padrões e seus representantes
(classes) são descritos em um espaço N-Dimensional, onde N é a quantidade
de características.
O principal problema é encontrar um conjunto de características que
distribua da melhor forma possível as classes no espaço.
Uma proposta consiste em ponderar as características com um vetor de
pesos. Isso pode ser feito utilizando como medida de similaridade a
distância Euclidiana ponderada.
Nossa proposta utiliza como ferramenta o Algoritmo Genético para
configurar o vetor de pesos que otimize a distribuição das classes.
Classificador de Distância Mínima
As classes W1, W2 e W3 são descritas
respectivamente pelos vetores de protótipo
(médio) m1, m2, m3:
1
mj 
Nj
Onde:
v
vω j
j = 1, 2, ..., M
Nj é o número de vetores de padrões (v) da
classe Wj e a soma é realizada sobre esses
vetores.
M é o número de classes.
O vetor x é um padrão a ser classificado,
representado por um vetor de características:
x = [X1, X2]
Adotando como medida de similaridade a distância Euclidiana, temos o padrão ‘x’ associado a classe j
com menor distância D(x, mj) do vetor de protótipo mj ao padrão ‘x’.
D(x, m j ) 
 (x
i
 m j i )2
i
As fronteiras de decisão, são definidas como retas perpendiculares ao segmento que liga dois
protótipos (classes), sendo que a fronteira intercepta a mediatriz desse segmento.
Medidas de Similaridade
Em um classificador de distância mínima as fronteiras de decisão são obtidas
através da medida de similaridade. As mais usadas são:
• Distância Euclidiana: D(x, m j ) 
2
(x

m
)
 i ji
i
 (p (x
• Distância Euclidiana Ponderada: D(x, m j ) 
i
2

m
))
i
ji
i
• Distância Euclidiana Normalizada: D(x,m j )  (x  m j )σ j1 (x  m j )T
1
• Distância de Mahalanobis: D(x,m j )  (x  m j ) j (x  m j )
• Distância de Manhattan: D(x,m j ) 
| x
i
T
 mji |
i
• Distância de Minkowsky: D(x, m j )  p
 (| x
i
 m j i |)p
i
Como algumas características descrevem uma classe melhor do que outras, torna-se
necessário aplicar uma ponderação de modo que estas características tenham mais
importância na classificação do que as outras.
A medida de similaridade que permite fazer isto é a distância Euclidiana ponderada.
Algoritmo Genético
Os algoritmos genéticos (AG’s) foram desenvolvidos por HOLLAND (1975;
1992), da Universidade de Michigan.
O AG’s foram inspirados na teoria da evolução das espécies. O processo de
evolução que ele executada corresponde a um procedimento de busca em um
espaço de soluções potenciais para o problema. Onde cada solução candidata é
representada por um cromossomo. Utiliza uma abordagem populacional, a qual
trabalha com um grupo de soluções candidatas por vez de maneira iterativa, onde a
cada iteração (geração) temos um novo conjunto de soluções candidatas. Elas são
selecionadas de acordo com sua adaptação (fitness), ou seja, quanto mais próximo
da solução melhor adaptada e maior será a possibilidade de participar da próxima
geração. A cada geração aplica-se os operadores de reprodução (crossover), o qual
combina valores de duas soluções candidatas fazendo uma exploração no espaço
de busca, em seguida aplica o operador de mutação, sendo este uma variação
aleatória na solução fazendo uma busca local.
Uma das vantagens de um algoritmo genético é a simplificação que eles
permitem na formulação e solução de problemas de otimização.
Iremos utilizar o Algoritmo Genético Padrão para otimizar o vetor de
pesos que deve ser utilizado na distância Euclidiana ponderada.
Para implementação será utilizada a ferramenta AGBIN [7] (Domínio
Público) com o MATLAB R13 (CopyRight The MathWorks Inc.).
Representação do Cromossomo
Cada característica dos padrões será ponderada por um peso
de valor inteiro no intervalo [0, 15].
A codificação do cromossomo será em binário, visando seguir
a Teoria dos Esquemas, proposta por HOLLAND (1975; 1992), a
qual utiliza o conceito de blocos construtivos para provar o
funcionamento dos AG’s. Deste modo, cada peso no vetor é
representado por 4 bits.
Para forçar que vizinhos no espaço de busca também sejam
vizinhos no espaço de parâmetros, foi adotado o código de Gray
para a transformação de genótipo em fenótipo.
Sendo assim, para padrões com 2 características temos:
Genótipo: [ 0 0 1 1 0 1 1 1 ]
Fenótipo: [ 2 5 ]
Função de Avaliação (Fitness)
Para otimizar a distribuição das classes no espaço de características, temos que
maximizar a distância entre as classes, interclasses (Objetivo 1) e minimizar a distância
dos padrões em relação a sua classe, intraclasses (Objetivo 2). Portanto temos um
problema multi-objetivo que pode ser representado da seguinte maneira:
Fitness =  Objetivo1 +  Objetivo 2
Para minimizar o Objetivo 2, devemos adotar o valor de  negativo.
Como todo problema multi-objetivo, teremos dificuldade em otimizar a superfície de
Pareto. Uma maneira de evitar este problema é criar uma interdependência dos
objetivos, utilizando o operador multiplicativo no lugar do aditivo.
Sendo que para minimizar o Objetivo 2 devemos
utilizar o inverso de seu valor restringindo o valor
zero:
Se (Objetivo 2 = 0) então Objetivo 2  1
Adotando para o calculo do fitness a pior
situação, ou seja, o padrão que está mais próximo
da fronteira de decisão ou em outra região, temos:
Fitness = min
Objetivo 1 i
Objetivo 2 i
, i { 1 .. N }
Onde N é o número de padrões de treinamento.
Estruturas Populacionais
A otimização do vetor de pesos pode admitir múltiplas soluções. Configurações
variadas do cromossomo podem apresentar valor de adaptação (fitness) com pouca
diferença do máximo global. Sendo assim foram implementados métodos de
Compartilhamento de Fitness e Especiação visando aumentar a probabilidade de se
obter o máximo global. Para o Compartilhamento de Fitness temos:
fitnessshare ( x i ) 
fitness(xi )
N
 sh(d(x , x ))
j 1
i
j
γ

 d 
 1 
 , se d  σ share

sh(d )  
 σ share 
 0,
, outroscasos

Sendo que para d(.) foi adotada a distância de Hamming.
Na Especiação somente é permitido a reprodução (crossover) de indivíduos que
tenham distância d(xi, xj) < mate e diferente de zero.
Outro problema é que o alto custo computacional do cálculo de fitness não
permite trabalhar com muitos indivíduos na população. Portanto foi implementado
um sistema de controle visando compensar a deriva genética, tendo como variável
controlada a taxa de mutação e como realimentação a porcentagem da diversidade da
população, sendo assim temos a taxa de mutação auto-ajustável de TMmin a TMmax:
TM = TMmin + ( 1 – Diversidade ) . ( TMmax – TMmin )
Experimentos Didático
Estes experimentos foram sintetizados em 2 dimensões
visando reforçar o entendimento e a motivação através da
demonstração visual dos resultados obtidos.
Parâmetros utilizados no Algoritmo Genético:
• População: 15 indivíduos (20 para o Experimento Didático 4)
• Indivíduos selecionados para a próxima geração: 60%
• Tipo de seleção: Roleta
• Taxa de crossover: 100%
• Tipo de recombinação: Crossover de um ponto
• Taxa de mutação: AUTO AJUSTAVEL 1% até 5%
• Parâmetros para o compartilhamento de fitness e especiação:
• GAMA: 1
• SIGMAshare: 1
• SIGMAmate: 2
(Distância Hamming)
(Distância Hamming)
Experimento Didático 1
Distância Euclidiana
Distância Euclidiana Ponderada
Classe: 1
Razão: 3.757985
Classe mais próxima: 2
Classe: 1
Razão: 4.857143
Classe mais próxima: 2
Classe: 2
Razão: 0.779272
Classe mais próxima: 1
Classe: 2
Razão: 5.833333
Classe mais próxima: 1
Vetor de Pesos: [ 0 4 ]
Experimento Didático 2
Distância Euclidiana
Distância Euclidiana Ponderada
Classe: 1
Razão: 3.757985
Classe mais próxima: 2
Classe: 1
Razão: 4.411288
Classe mais próxima: 3
Classe: 2
Razão: 0.779272
Classe mais próxima: 1
Classe: 2
Razão: 1.916254
Classe mais próxima: 1
Classe: 3
Razão: 3.440456
Classe mais próxima: 2
Classe: 3
Razão: 1.899517
Classe mais próxima: 2
Vetor de Pesos: [ 4 11 ]
Experimento Didático 3
Classe: 1
Razão: 4.219005
Classe mais próxima: 2
Classe: 1
Razão: 4.052595
Classe mais próxima: 2
Classe: 2
Razão: 2.587253
Classe mais próxima: 3
Classe: 2
Razão: 2.466827
Classe mais próxima: 3
Classe: 3
Razão: 1.166667
Classe mais próxima: 2
Classe: 3
Razão: 2.464598
Classe mais próxima: 2
Classe: 1
Razão: 4.030291
Classe mais próxima: 2
Classe: 2
Razão: 2.450615
Classe mais próxima: 3
Classe: 3
Razão: 3.135322
Classe mais próxima: 2
Vetor de Pesos: [ 9 3 ]
Vetor de Pesos: [ 9 4 ]
Experimento Didático 4
Distância Euclidiana
Distância Euclidiana Ponderada
Classe: 1
Razão: 3.757985
Classe mais próxima: 2
Classe: 1
Razão: 3.943876
Classe mais próxima: 2
Classe: 2
Razão: 0.779272
Classe mais próxima: 1
Classe: 2
Razão: 1.029078
Classe mais próxima: 1
Classe: 3
Razão: 1.387417
Classe mais próxima: 2
Classe: 3
Razão: 1.026741
Classe mais próxima: 2
Vetor de Pesos: [ 8 11 ]
Experimento Didático 4
A ilustração da superfície de fitness comprova que a configuração do
vetor de pesos admite múltiplas soluções. E que grandes variações no
cromossomo podem ter um valor de fitness próximo do valor global. O que
dificulta ao Algoritmo Genético obter o máximo global.
O máximo global está circulado em azul.
Experimento Didático 4
Com o AG Padrão
Resultado:
Fitness: 1.0012
Pesos: [ 9 12 ]
Com a utilização de
Compartilhamento de
Fitness, Especiação e
Taxa de Mutação AutoAjustável
Resultado:
Fitness: 1.0267
Pesos: [ 8 11 ]
Experimento Didático 4
Algoritmo Genético Padrão
Geração
Geração20
0
1
2
3
4
5
6
7
8
9
Experimento Didático 4
AG com Compartilhamento de Fitness, Especiação e Taxa de Mutação Auto-Ajustável
Geração
Geração19
0
1
2
3
4
5
6
7
8
9
Experimento Prático
Como experimento prático será utilizada uma aplicação OCR (Optical Character Recognition) para
um sistema de identificação de placas de licenciamento veicular. O qual classifica as 26 letras
maiúsculas e 10 números, totalizando 36 caracteres. As imagens foram obtidas com câmeras
analógicas em ambiente aberto, ou seja, possui características que dificultam a aplicação OCR.
Um classificador de distâncias mínimas com distância Euclidiana ponderada será utilizado para
classificar os caracteres, tendo como conjunto de treinamento 10 padrões de cada classe, totalizando
360 padrões de treinamento.
Cada padrão é descrito por um vetor contendo 47 características, obtidas da imagem binária do
caractere, composto por:
Posição 1: Valor lógico (1 ou 0) indicando se a razão de aspecto do caractere é menor que 0,3.
Característica importante para identificar o caractere 1 ou I.
Posição 2: Coordenada vertical do centro do primeiro furo normalizado pela altura do caractere.
Posição 3: Coordenada horizontal do centro do primeiro furo normalizado pela largura do caractere.
Posição 4: Área do primeiro furo normalizada pela área total do caractere.
Posição 5: Coordenada vertical do centro do segundo furo normalizado pela altura do caractere.
Posição 6: Coordenada horizontal do centro do segundo furo normalizado pela largura do caractere.
Posição 7: Área do segundo furo normalizada pela área total do caractere.
Posição de 8 até 47: Valores na seqüência de leitura raster (da esquerda para direita e de cima para
baixo) de uma reamostragem da imagem binária com 5 de largura e 8 de altura, ou seja, a imagem do
caractere é dividida em partes 5 horizontais e 8 partes verticais, onde é calculando a porcentagem de
preenchimento de cada quadrante.
Para os caracteres que não contém furos deve-se atribuir o valor zero nessas características.
Experimento Prático
Exemplo de um vetor de características do número 6:
V = [ 0 0.7296 0.3703 0.0504 0 0 0 0 0 0 0.6988 0.9678 0 0 0.3113 0.9922 0.4143 0 0.1042 0.9072
0.6473 0.0076 0.0410 0.8068 1.0000 0.3539 0.0050 0.5045 0.9704 0.7876 0.9974 0.4787 0.9548
0.4735 0 0.6602 0.9548 0.9806 0.6293 0.1119 0.8172 0.7040 0.4015 1.0000 1.0000 0.8660 0.1428 ]
Primeiro furo.
Este caractere
não tem o
segundo furo.
Imagem binária com 21 bits
de largura e 37 bits de altura
Imagem reamostrada com
5 de largura e 8 de altura
Experimento Prático
Parâmetros utilizados no Algoritmo Genético:
• População: 50 indivíduos
• Indivíduos selecionados para a próxima geração: 60%
• Tipo de seleção: Roleta
• Taxa de crossover: 100%
• Tipo de recombinação: Crossover de um ponto
• Taxa de mutação: AUTO AJUSTAVEL 1% até 5%
• Parâmetros para o compartilhamento de fitness e especiação:
• GAMA: 1
• SIGMAshare: 23
• SIGMAmate: 47
(Distância Hamming)
(Distância Hamming)
Os caracteres “0”, “O” e “Q” possuem características conflitantes.
Como este problema é pouco tratável, resolveu-se associar os
caracteres “O” e “Q” na mesma classe do caractere “0”.
Experimento Prático
Resultado obtido após 500 gerações:
Vetor de pesos: [ 10 15 0 10 3 6 11 10 1 11 15 15 2 12 5 1 11 14 1 13 7 13
7 2 11 7 13 8 8 12 9 1 9 4 11 6 15 6 3 5 11 15 9 12 9 0 2 ]
Experimento Prático
Razão da Distância Interclasses / Intraclasses
5
4
3
2
1
0
-1
-2
5
S
C
G
2
7
Z
2
V
Y
H
M
Distância Euclidiana
N
W
U
E
F
L
3
J
T
K
X
9
P
R
6
6
9
4
A
0
D
O
Q
4
1
I
8
Distância Euclidiana Ponderada
Este gráfico mostra as contribuições positivas e negativas do vetor de pesos
encontrado pelo AG e aplicado na Distância Euclidiana Ponderada. Onde padrões
próximos da fronteira foram afastados, como conseqüência padrões distantes foram
aproximados.
B
Experimento Prático
Distância Euclidiana
Os dendrogramas
ao lado permitem
visualizar a distância
entre classes
vizinhas.
Verificamos
melhoras locais onde
alguns grupos foram
afastados (O, Q, 0 e
D); (9 8 B); (P e R); (H
e N); (2 e 2); (7 e Z); (E
e F); (1 e I); (P e R).
Porém a distância
entre os caracteres
dentro de um grupo
(Ex.: O, Q, 0, D) não
foram melhoradas.
Distância Euclidiana Ponderada
Experimento Prático
Classificação Correta dos Caracteres
35
30
25
20
15
10
5
0
0
1
2
3
4
5
6
7
8
9
A
Distância Euclidiana
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Distância Euclidiana Ponderada
Este gráfico mostra a performance do classificador de distância mínima. Tendo
como conjunto de validação 30 amostras de cada classe.
Z
Experimento Prático
A porcentagem total de classificação correta foi:
Distância Euclidiana: 95.19%
Distância Euclidiana Ponderada: 94.91%
O conjunto de pesos aplicado na distância Euclidiana ponderada
apresentou melhoras locais, ou seja, em alguns caracteres, porem não de
maneira global. Embora tenha seu resultado final próximo do obtido com a
distância Euclidiana.
A explicação está no gráfico que mostra a razão das distância interclasses
pelas intraclasses. A razão de algumas classes melhorou enquanto as de
outras piorou.
Existe a possibilidade de que o conjunto de características não esteja
descrevendo as classes da melhor forma possível, sendo assim o conjunto de
pesos não conseguiu melhorar as piores condições sem prejudicar as demais.
Uma solução seria modificar o conjunto de características.
O conjunto de treinamento também é importante na descrição da classe,
sendo assim é necessário verificar a utilização de outras amostras.
Talvez esta medida de adaptação (fitness) não seja a melhor proposta.
Conclusão
O método utilizado apresentou melhoras nas classes em pior
condição (padrões próximos das fronteiras), mas não conseguiu
melhoras de maneira global (porcentagem total de acertos na
classificação). Isto deve-se principalmente a medida de adaptação
(fitness), pois o que ela propõe é melhorar a pior condição, tendo a
melhora global como conseqüência. Outra melhora constatada foi o
afastamento de alguns grupos, embora a distância entre as classes
de um mesmo grupo não tenham aumentado.
Torna-se necessário verificar novas formas de cálculo da
adaptação (fitness) para que o sistema tenha uma melhora global
mesmo não tendo uma melhora local.
Este método mostrou-se promissor na tarefa de qualificar cada
característica. Não apenas selecionando, mas ponderando as
características de acordo com sua importância. Esta tarefa é
necessária e não trivial.
Perspectivas
Modificar a medida de adaptação (fitness) para que o vetor de
pesos consiga melhorar o sistema classificador de maneira global.
Uma possibilidade é a utilização da matriz de dispersão (scatter) [6].
Utilizar um Classificador Hierárquico. No qual classes com
características semelhantes são agrupadas. Primeiramente serão
ajustados pesos para os grupos e depois para cada grupo será
calculado um conjunto de pesos utilizando somente as classes deste
grupo. Essa possibilidade mostrou-se promissora através da melhora
de alguns grupos de classes no dendrograma da distância Euclidiana
ponderada.
Verificar a possibilidade de aplicar a Regra Majoritária utilizando
vários resultados obtidos com diferentes inicializações da população,
ou com um conjunto dos k melhores indivíduos.
Fazer testes comparativos com outras medidas de similaridade
(Ex.: Mahalanobis).
Estender o método para aprendizagem não supervisionada,
utilizando um método de agrupamento (Ex.: k-means).
Livros:
Referências
[1] F. J. Von Zuben, “Notas de Aula, IA 707 – Computação Evolutiva”,
http://www.dca.fee.unicamp.br/~vonzuben/courses/ia707.html, Unicamp, Brasil, 2002
[2] R. O. Duda and P. E. Hart, “Pattern Classification and Scene Analysis”, WileyInterscience Publication, California, USA, 1973
[3] R. C. Gonzalez e R. E. Woods, “Processamento de Imagens Digitais”, Edgard
Blücher, Brasil, 2000
Artigos:
[4] G. Dimauro, S. Impedovo, R. Modugno and G. Pirlo, “Numeral Recognition by
Weighting Local Decisions”, 7th ICDAR – IEEE Computer Society Press, 2003
[5] S. Cha, C. C. Tappert and S. N. Srihari, “Optimizing Binary Feature Vector
Similarity Measure using Genetic Algorithm and Handwritten Character
Recognition”, 7th ICDAR – IEEE Computer Society Press, 2003
[6] M. Morita, R. Sabourin, F. Bortolozzi and C. Y. Suen, “Unsupervised Feature
Selection Using Multi-Objective Genetic Algorithms for Handwritten Word
Recognition”, <draft version>
Ferramentas:
[7] “AGBIN: Algoritmo Genético para Codificação Binária”,
ftp://ftp.dca.fee.unicamp.br/pub/docs/vonzuben/ia707_1s04/projetos/binario.zip