Novos Métodos de Classificação Nebulosa e de Validação de Categorias e suas Aplicações a...

Novos Métodos de Classificação Nebulosa e de

Validação de Categorias e suas Aplicações a Problemas

de Reconhecimento de Padrões

Cláudia Rita de FrancoOrientador: Adriano Joaquim de Oliveira Cruz

Março/2002

Problemas Abordados Validação de Categorias

Descobrir o número e a disposição das categorias que melhor representam o problema

Reconhecimento de Padrões Identificar e classificar padrões recorrentes

nos dados

Índice Estudo Realizado

Categorização Classificação Validação de Categorias

PropostasEFLD ICCSistema ICC-KNN

Estudo Realizado

Categorização Classificação Validação de Categorias

Categorização Processo de particionar um conjunto de

amostras em subconjuntos (categorias) Dados similares entre si por suas

característicasDisposição EspacialCategoria definida pela proximidade das

amostras – Distância Partições Rígidas e Nebulosas

Classificação Técnica que associa amostras a classes

previamente conhecidas Rígida e Nebulosa Supervisionados

MLP treinamento Não supervisionados

K-NN e K-NN nebuloso sem treinamento

Reconhecimento de Padrões Reconhecimento de Padrões +

Categorização Sistema Estatístico Não paramétrico de Reconhecimento de Padrões

Estatístico avalia a similaridade dos dados através de medidas matemáticas

Não-Paramétrico sem conhecimento prévio da distribuição das amostras

Denominação de Características

Extração de Características

Identificação de Características

Categorização

Validação de Categorias

Classificador

Dados de Treinamento

Dados de Teste

Taxa de erro

Sistema Estatístico Não-Paramétrico de Reconhecimento de Padrões

Métodos de Categorização Não-Hierárquicos

Dados distribuídos pelo número de categorias pré-definido

Critério é otimizado Minimização da variação interna das categorias

Métodos de Categorização Hierárquico 1ª Abordagem

Cada ponto é um centro de categoriaCada 2 pontos mais próximos são fundidos

em uma categoriaNúmero de categorias desejado é atingido

Hierárquico 2ª AbordagemUma categoria contém todas as amostrasCritério é utilizado para dividí-la no número de

categorias desejado

Métodos de Categorização Rígidos

Cada amostra pertence a uma única categoria

NebulososCada amostra pertence a todos os

agrupamentos com diferentes graus de afinidade

Grau de inclusão

Métodos de Categorização k-Means K-NN e K-NN nebulosoFCM FKCNGGGK

Métodos de Categorização

K-Means e FCMDistância Euclidiana Hiperesferas

Gustafson-KesselDistância de Mahalanobis Hiperelipsóides

Gath-GevaDistância de Gauss superfícies convexas

de formato indeterminado

Rede Kohonen de Categorização Nebulosa FKCN

Método de Categorização Nebuloso não supervisionado

Distância Euclidiana Categorias hiperesféricas Converge mais rápido que FCM Forte tendência a convergir para mínimos

locaisCategorias pouco representam as classes

K-NN e K-NN nebuloso Métodos de Classificação Classes identificadas por padrões Classifica pelos k vizinhos mais próximos Conhecimento a priori das classes do

problema Não se restringe à uma distribuição

específica das amostras

K-NN Rígido

w1

w2 w3

w4

w13

w10

w9 w14

w5

w8

w12

w11

w6w7

Classe 1Classe 2

Classe 3

Classe 4 Classe 5

K-NN Nebuloso

w1

w2

w3

w4

w13

w10

w9 w14

w5

w8

w12

w11

w6w7

Classe 1Classe 2

Classe 3

Classe 4 Classe 5

Medidas de Validação

Medidas de Validação Usadas para encontrar o número ideal de

categorias que melhor representa o espaço amostralNúmero de classes desconhecidoNúmero de classes Número de categorias

Medidas de Validação Aplicadas a partições geradas por um

método de categorização

Estima qualidade das categorias geradas

Rígidas ou Nebulosas

Coeficiente de Partição – F Medida de Validação Nebulosa Maximizar – 1/c F 1 Diretamente influenciada pelo

Número de categorias e Sobreposição das classes

nFc

i

n

jij

1 1

2

Compacidade e Separação – CS

Medida de Validação Nebulosa Minimizar – 0 CS Avalia diferentes funções objetivo

2mindnJ

CS m

Compacidade e Separação – CS

Mede:O grau de separação entre as categoriasA compacidade das categoriasNão sofre influência da sobreposição das

categorias

Maior taxa de acertos dentre as medidas de validação estudadas

Discriminante Linear de Fisher - FLD

Medida de Validação Rígida

Mede a compacidade e a separação entre as categoriasMatriz de Espalhamento entre Classes – SB

Matriz de Espalhamento Interno – SW

Discriminante Linear de Fisher - FLD

Critério J – Maximizado

W

B

SS

J W

B

StraceStraceJ

Indicadores de Validade Calculam o grau de separação entre as

categorias Menor a sobreposição das categorias

melhor a categorização obtida MinRF, MaxRF e MinNMMcard

Propostas

EFLD ICC Sistema ICC-KNN

EFLD

EFLD Extended Fisher Linear Discriminant Extensão do Discriminante Linear de

Fisher Capacidade de validar categorias rígidas e

nebulosas

EFLD Matriz Estendida de Espalhamento entre

Classes

mie é o centróide da categoria i

c

i

Tn

jijBeS

1 1

mmmm eiei

i

j

μ

x

n

jij

eim1

n

jij

1

iμe

Tc

iiB

mmnS

ii mm1

EFLD Matriz Estendida de Espalhamento Interno

Matriz Estendida de Espalhamento Total

c

i

Tn

jWS

1 1ijij mxmx

c

i

Tn

jijWeS

1 1eijeij mxmx

SSS BeWeTeSSS BWT

EFLD Conclusão

Espalhamento total do sistema é independente da natureza das partições se o somatório dos graus de inclusão dos pontos em cada categoria é igual a 1 Constante

1,1

c

iijj

SSS T

n

j

T

BeWe

1

mxmx jj

EFLD Critério de Fisher Estendido

Determinante – limite em relação ao número de pontos de cada categoria

Traço – mais rápido de calcularSem limitações de número de pontos

We

Bee Strace

StraceJ We

Bee S

SJ

EFLD – Otimização Matrizes de Espalhamento – geradas pelo

produto de um vetor coluna por seu transpostoTraço – quadrado do módulo do vetor gerador

2

1 1

)(

c

i

n

jijBeBe

Straces mmei

2

1 1

)(

c

i

n

jijWeWe

Straces eij mx

EFLD – Otimização

Soma dos traços das matrizes SBe e SWe é constantesTe é calculado uma única vez

sBe é mais rápido de calcular que sWe

2

1

)(

n

jTTStraces mx j

EFLD – Otimização

O critério de Fisher J pode ser reescrito como

Vantagem – cálculo mais rápido Melhor número de categorias - Maximizar

BeT

Bee ss

sJ

We

Bee Strace

StraceJ

EFLD – Aplicação

Três classes com 500 pontos cada X1 – (1,1), (6,1), (3,5, 7) com Std 0,3 X2 – (1,5, 2,5), (4,5, 2,5), (3,5, 4,5) com Std 0,7 Aplicar FCM para m = 2 e c = 2 ...6

EFLD – Aplicação

EFLDNúmero de Categorias

2 3 4 5 6

Amostras X1 4,6815 4,9136 0,2943 0,2559 0,3157

Amostras X2 0,3271 0,8589 0,8757 0,9608 1,0674

Para classes sobrepostas, Je, como J, erra

alta sobreposição baixa confiabilidade Comportamento análogo ao FLD

EFLD – Aplicação

Alocação errônea dos centrosMínimo local = Ponto médio do conjunto de pontosJe extremamente pequeno = 9,8010 x 10-5

ICC

ICC – Inter Class Contrast EFLD

Cresce conforme o número de partições cresce

Cresce com a sobreposição das classes

Atinge um valor máximo para um falso número ideal de categorias

ICC Avalia um espaço particionado rígido ou

nebuloso Analisa:

Compacidade das categoriasSeparação das categorias

Maximizar

ICC

sBe – estima a qualidade da alocação dos centros das categorias

1/n – fator de escalaCompensa a influência do número de pontos

no termo sBe

cDnsICC Be min

ICCcD

nsICC Be min

Dmin – distância Euclidiana mínima entre os centros das categoriasNeutraliza o comportamento crescente de sBe

evitando o máximo valor de ICC para uma número de categorias superior ao ideal

2 ou mais categorias representam uma classe – Dmin decresce abruptamente

ICC

c

cDnsICC Be min

– Raiz do número de categorias Evita o máximo valor de ICC para uma

número de categorias inferior ao ideal1 categoria representa 2 ou mais classesDmin aumenta

ICC – Aplicação Nebulosa

Cinco classes com 500 pontos cada Sem sobreposição de classes X1 – (1,2), (6,2), (1, 6), (6,6), (3,5, 9) Std 0,3 Aplicar FCM para m = 2 e c = 2 ...10

MedidasNúmero de Categorias

2 3 4 5  

ICC M 7,596 41,99 51,92 96,70  

ICCTra M 7,596 41,99 51,92 96,70  

ICCDet M IND 154685 259791 673637  

EFLD M 0.185 0.986 1.877 13.65  

EFLDTra M 0,185 0,986 1,877 13,65  

EFLDDet M IND 0,955 3,960 182,70  

CS m 0,350 0,096 0,070 0,011  

F M 0,705 0,713 0,795 0,943  

MinHT M 0,647 0,572 2,124 1,994  

MeanHT M 0,519 0,496 1,327 1,887  

MinRF 0 0,100 0,316 0 0  

TemposNúmero de Categorias

2 3 4 5

ICC 0,0061 0,0069 0,0082 0,00914

ICCTra 0,0078 0,0060 0,0088 0,0110

ICCDet 0,0110 0,0088 0,0110 0,0132

EFLD 0.0053 0.0071 0.0063 0.0080

EFLDTra 0,7678 1,0870 1,4780 1,8982

EFLDDet 0,7800 1,1392 1,5510 2,0160

CS 0,0226 0,0261 0,0382 0,0476

NFI 0,0061 0,0056 0,0058 0,00603

F 0,0044 0,0045 0,0049 0,00491

FPI 0,0061 0,0045 0,0049 0,00532

ICC – Aplicação Nebulosa

Cinco classes com 500 pontos cada Alta sobreposição de classes X1 – (1,2), (6,2), (1, 6), (6,6), (3,5, 9) Std 0,3 Aplicar FCM para m = 2 e c = 2 ...10

Medidas 2 3 4 5 10

ICC M 5,065 4,938 6,191 7,829 5,69

ICCTra M 5,065 4,938 6,191 7,829 5,69

ICCDet M IND 715,19 3572 7048 6024

EFLD M 0.450 0.585 0.839 1.095 1.344

EFLDTra M 0,450 0,585 0,839 1,095 1,344

EFLDDet M IND 0,049 0,315 0,743 1,200

CS m 0,164 0,225 0,191 0,122 0,223

F M 0,754 0,621 0,591 0,586 0,439

MeanHT M 0,632 0,485 0,550 0,597 0,429

MinRF 0 0,170 0,294 0,194 0,210 0,402

MPE m 0,568 0,601 0,561 0,525 0,565

TemposNúmero de Categorias

2 3 4 5

ICC 0,0060 0,0064 0,0077 0,00881

ICCTra 0,0066 0,0060 0,0098 0,0110

ICCDet 0,0110 0,0078 0,0110 0,0120

EFLD 0.0063 0.0088 0.0096 0.0110

EFLDTra 0,7930 2,1038 1,7598 2,2584

EFLDDet 0,9720 1,2580 1,6090 1,8450

CS 0,0220 0,0283 0,0362 0,05903

F 0,0112 0,0121 0,0061 0,0164

MPE 0,0167 0,0271 0,0319 0,03972

ICC – Aplicação RígidaMedidas 4 5 6 7 8

ICC M 81,8485 105,4463 15,0987 14,8891 13,4127

DLF M 5,9021 67,262 72,354 77,413 79,549

CS m 0,1195 0,0121 0,6593 0,7413 16,1588

Tempos 4 5 6 7 8

ICC 0,0074 0,00801 0,0085 0,0093 0,0102

DLF 1,3216 1,6784 2,0324 2,3002 2,6140

CS 0,0308 0,03772 0,0437 0,0502 0,0569

ICC – Aplicação RígidaMedidas 4 5 6 7 8

ICC M 15,5823 18,1940 13,4461 13,3913 14,9289

DLF M 2,9176 4,8258 5,4257 6,0781 6,8428

CS m 0,2488 0,1898 0,3928 0,4338 0,3717

Tempos 4 5 6 7 8

ICC 0,0074 0,00991 0,0102 0,0115 0,0135

DLF 1,3258 1,6534 1,9850 2,3288 2,6166

CS 0,0321 0,03822 0,0454 0,0516 0,0582

ICC – Conclusões Rápida e Eficiente Analisa partições Nebulosas e Rígidas Eficiente com alta sobreposição das

classes Alta taxa de acertos

ICC-KNN

Sistema ICC-KNN Sistema Estatístico Não-Paramétrico de

Reconhecimento de Padrões Associa FCM, KNN nebuloso e ICC Avaliar dados dispostos em diversos

formatos de classes

Sistema ICC-KNN Módulo de Classificação

Estabelecer estruturas nos dados Primeira Fase de Treinamento

Avalia a melhor distribuição de padrões para o K-NN nebuloso

FCM – Aplicado para cada classe ICC – Encontra o melhor número de categorias que

representa cada classe

Sistema ICC-KNN Segunda Fase de Treinamento Avalia a melhor constante nebulosa e o

melhor número de vizinhos para o K-NN – maior performanceVaria-se m e kEscolhe-se m e k para a maior taxa de

Acertos Rígidos

Sistema ICC-KNN Módulo de Reconhecimento de Padrões

Atribuir os dados às classes definidas Utiliza os padrões, m e k para classificar

os dados

Sistema ICC-KNN

Classe 1

Classe s

FCM

FCM

ICC

ICC

K-NNnebuloso

m k

W, Uw

W Uw

w1

ws

U1cmin

U1cmáx

UScmin

UScmáx

K-NNnebuloso

Módulo de ClassificaçãoMódulo de

Reconhecimento de Padrões

Dados não classificados

Sistema ICC-KNN - Algoritmo Módulo de Classificação

Primeira fase do Treinamento Passo 1. Fixar m Passo 2. Fixar cmin e cmáx Passo 3. Para cada classe s conhecida

Gerar o conjunto Rs com os pontos de R pertencentes à classe sPara cada categoria c no intervalo [cmin , cmáx]Executar FCM para c e o conjunto Rs gerando Usc e VscCalcular a ICC para Rs e UscFimDefinir os padrões ws da classe s como a matriz Vsc que maximiza a ICC

Passo 4. Gerar o conjunto W = {w1, ..., ws}

Sistema ICC-KNN - Algoritmo Segunda fase do Treinamento Passo 5. Fixar mmin e mmáx Passo 6. Fixar kmin e kmáx

Para cada m do intervalo [mmin , mmáx] Para cada k do intervalo [kmin , kmáx]

Executar o K-NN nebuloso para os padrões do conjunto W, gerando Umk Calcular os acertos rígidos para Umk

Passo 7. Escolher o m e k que obtêm a maior taxa de acertos rígidos Passo 8. Se houver empate

Se os k são diferentesEscolher o menor k

SenãoEscolher o menor m

Sistema ICC-KNN - Algoritmo Módulo de Reconhecimento de Padrões

Passo 9. Aplicar o K-NN nebuloso com os padrões do conjunto W e os parâmetros m e k escolhidos aos dados a serem classificados

Sistema ICC-KNN - Avaliação

2000 amostras, 4 classes, 500 amostras em cada classe Classe 1 e 4 – classes côncavas Classes 2 e 3 – classes convexas com formato elíptico

Sistema ICC-KNN - Avaliação

Primeira Fase de Treinamento FCM aplicado a cada classe

Dados de treinamento 80% 400 amostrasc = 3..7 e m = 1,25

ICC aplicada aos resultadosClasses 1 e 4 4 categoriasClasses 2 e 3 3 categorias

Sistema ICC-KNN - Avaliação

Segunda Fase de Treinamento Execução do K-NN Nebuloso

Padrões da PFTPadrões Aleatóriosk = 3 a 7 vizinhosm = {1,1; 1,25; 1,5; 2}

Sistema ICC-KNN - Avaliação

Conclusão: K-NN é mais estável em relação ao valor de m para os

padrões da PFT

Sistema ICC-KNN - AvaliaçãoDados de Treinamento

ClassesPadrões da PFT Padrões Aleatórios

1 2 3 4 1 2 3 4

1 388 10 0 2 213 66 0 121

2 14 379 0 7 19 380 0 1

3 0 0 376 24 3 0 324 73

4 0 1 2 397 4 46 1 349

Dados de Treinamento Linhas classes Colunas classificação m = 1,5 e k = 3 96,25% m = 1,1 e k = 3 79,13% (padrões aleatórios)

Sistema ICC-KNN - Avaliação

Dados de Teste Módulo de Reconhecimento de padrões Execução do K-NN nebuloso nos dados de teste Pad. PFT – 94,75% Pad. Aleat – 79%

Dados de Testes

ClassesPadrões da PFT Padrões Aleatórios

1 2 3 4 1 2 3 4

1 97 2 0 1 53 27 0 20

2 4 93 0 3 4 96 0 0

3 0 0 90 10 0 0 82 18

4 0 0 1 99 0 15 0 85

Sistema ICC-KNN - Avaliação

Tempos de Execução Padrões da PFT 36,5 s

PFT FCM + ICC= 15,5 sSFT 21,04 sTotal 36,5 s

Aleatório 23,11s

Sistema ICC-KNN - Avaliação

Acerto Nebuloso grau de inclusão > 1/k

ICC-KNN x Mét. de Categorização

FCM, FKCN, GG e GK Fase de Treinamento (FTr)

Dados de treinamentoc = 4 e m = {1,1; 1,25; 1,5; 2}Associar as categorias às classes

Critério do somatório dos graus de inclusão Cálculo do somatório dos graus de inclusão dos pontos

de cada classe em cada categoria Uma classe pode ser representada por mais de uma

categoria

ICC-KNN x Mét. de Categorização

Fase de TesteDados de Teste Inicialização dos métodos com os centros da FTrCalcula o grau de inclusão dos pontos em cada

categoria Classe representada por mais de 1 categoria

Grau de inclusão = soma dos graus de inclusão dos pontos nas categorias que representam a classe

GK para m = 2 84% FCM e FKCN 66% para m = 1,1 e m = 1,25 GG-FCM 69% para m = 1,1 e 1,25 GG Aleatório 57,75% para m = 1,1 e 25% para m = 1,5

ICC-KNNKNN A.

FCM FKCN GG GK

R 94,75% 79% 66% 66% 69% 84%

N 95,75% 83% 70,75% 70,75% 69% 89,5%

T 36,5s 23,11s 2,91s 2,59s 22,66s 18,14s

ICC-KNN x Mét. de Categorização

FCM GG-FCM

GK

Reconhecimento de Dígitos Manuscritos

Problema Dígitos manuscritos extraídos de

formulários Escaneados imagens do tipo Tiff Algoritmo de Afinamento

Esqueleto da imagem Extração de características

Método do Polígono 122 características 4077 dígitos 3266 e 811 amostras

Aplicação do ICC-KNN PFT

FCM m = 1,25 e c = 2..30

0 1 2 3 4 5 6 7 8 9

22 29 12 25 15 26 25 23 10 30

SFT K-NN neb. Padrões da PFT e Aleatóriosk = 3..7 e m ={1,1; 1,25; 1,5; 2}

Acertos e TemposMétodos ICC-KNN K-NN Neb. Alea.

Acertos Ríg. 87,8% 72,4%

Acertos Neb. 94,53% 85,63%

Tempos 7166 s 1224,3 s

Dados de Teste m = 1,25 e k = 7 87,8% 21,3% superior

ICC-KNN x Mét. De Categorização

Comparação com os Mét. De CategorizaçãoFCM, FKCN, GG, GK

122 19 característicasPCA – Principal Components AnalysisVariância preservada 82,6%p(p-1)/2

Acertos e TemposICC-KNN K-NN A. FCM FKCN GG GK

86,7% 75,22% 57% 55% 51% 49%

93,8% 85,66% 60% 54% 39,5% 39,8%

1784 s 260 s 30,38 s 32,79 s 108,15 s 711,77 s

Dados de Teste ICC-KNN 86,7% param = 1,25 e k = 6 FCM 57% para m = 1,25 52% de ganho do ICC-KNN sobre o FCM

Acertos Rígidos

Pouco estável em relação à m

Conclusões EFLD

Estendeu eficientemente as funcionalidades do FLD partições rígidas e nebulosas

Maior velocidade ICC

Eficiente e rápidaSuporta alta sobreposição das classesAvalia a compacidade e a separação das

classesAlto grau de acertos

Conclusões Sistema ICC-KNN

Maior eficiência sobre sistemas que usam métodos de categorização

Melhor classificação dos dadosFacilidade de implementaçãoNão oferece restrições ao conjunto de amostrasTaxas superiores no problema de

reconhecimento de dígitos manuscritos

Trabalhos Futuros ICC-KNN com outros métodos de

categorização Variar a constante nebulosa na PFT Empregar redes MLP para avaliar os

graus de inclusão gerados pelo ICC-KNNAvaliar as amostras em um espaço

dimensional menor