Cláudia Rita de Franco Orientador: Adriano Joaquim de Oliveira Cruz Março/2002

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 CategoriasDescobrir 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árquicosDados distribuídos pelo número de categorias

pré-definidoCritério é otimizado

Minimização da variação interna das categorias


Hierárquico 1ª AbordagemCada 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


RígidosCada amostra pertence a uma única

categoria Nebulosos

Cada amostra pertence a todos os agrupamentos com diferentes graus de afinidade

Grau de inclusão


k-Means K-NN e K-NN nebulosoFCM FKCNGGGK


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


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


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

2mindn

JCS 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

S

SJ

W

B

Strace

StraceJ

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


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


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


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


Alocação errônea dos centros

Mínimo local = Ponto médio do conjunto de pontos

Je extremamente pequeno = 9,8010 x 10-5

ICC

ICC – Inter Class Contrast

EFLDCresce conforme o número de partições

cresceCresce 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

cDn

sICC Be min

ICC

cDn

sICC 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

cDn

sICC 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ígida

Medidas 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ígida

Medidas 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çãoEstabelecer estruturas nos dados

Primeira Fase de TreinamentoAvalia 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õesAtribuir 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ção

Mó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 Vsc

Calcular 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


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


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}


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

padrões da PFT


Dados 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)


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


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


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


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%

N95,75%

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

T36,5s

23,11s2,91s 2,59s 22,66s 18,14s


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 Tempos

Mé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 Tempos

ICC-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-KNNMaior eficiência sobre sistemas que usam

métodos de categorizaçãoMelhor 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

Documents

Cláudia Rita de Franco Orientador: Adriano Joaquim de Oliveira Cruz Março/2002