Relatorio Final - Estatística

7/23/2019 Relatorio Final - Estatística

http://slidepdf.com/reader/full/relatorio-final-estatistica 1/5

Avaliação Estatística sobre o Reconhecimento de Dígitos Manuscritos

Everton B. Lacerda, Jefferson O. A. de Araújo, Roberto H. W. Pinheiro, Silvio S. BandeiraCentro de Informática

Universidade Federal de PernambucoRecife, Brasil

[email protected], [email protected], [email protected], [email protected]

Abstract — The main goal of this work is to investigate the

recognition of handwritten digits. This task is of capital

importance in many applications and institutions as banks.

Seven classifier configurations are presented and compared

using samples from a known database. The performances of

those configurations are tested using statistical methods to

ensure comparison with mathematical grounding to determine

the best configuration.

Palavras-chave; reconhecimento; dígitos manuscri tos;máquinas de vetor es de supor te; teste de hi pótese

I. I NTRODUÇÃO

O reconhecimento de caracteres é uma atividade degrande importância na sociedade. Principalmente, quando seconsidera a necessidade crescente de integração entreinformações em meio físico e meio digital. Oreconhecimento de caracteres manuscritos se torna umatarefa bastante difícil devido à variedade de estilos de escritaentre pessoas diferentes, e até mesmo da mesma pessoa como passar do tempo.

Nesse contexto, o reconhecimento de dígitos manuscritos

se torna crucial em várias aplicações como: o processamentoautomático de cheques bancários [1], onde é necessário obtero valor correto do cheque, visto que caso contrário, haverá

prejuízos para o banco ou para o cliente; o endereçamentoautomático de envelopes postais por meio da leitura do CEP(Código de Endereçamento Postal) [2], data ou dados decatálogo em documentos históricos, o que permitiria aindexação automática do acervo.

Devido aos altos custos envolvidos quando há erros dereconhecimento, sempre existe a demanda porclassificadores mais precisos, ou de outra forma, com taxasde acerto mais altas.

Nesse cenário, foi proposto um classificador que obtevemuito bom desempenho no reconhecimento de dígitos

manuscritos em [3]. O método citado se baseia em umconjunto de SVMs (Máquinas de Vetores de Suporte) [4] queanalisam cada par de dígitos possível (0 a 9), não importandoa ordem em que eles aparecem, constituindo assim 45 parese, por conseguinte, 45 SVMs.

Este trabalho faz uma investigação sobre a melhorconfiguração de parâmetros do classificador sob estudo, noque tange a seus parâmetros (função de kernel e respectivo

parâmetro interno). O texto se organiza da seguinte maneira:a Seção II apresenta os conceitos estatísticos relacionados à

comparação entre classificadores. A Seção III descreve osexperimentos, e a Seção IV mostra a análise exploratória dosdados. Na Seção V, ilustram-se os resultados obtidos. Porfim, a Seção VI conclui o trabalho.

II. COMPARAÇÃO ENTRE CLASSIFICADORES

No presente projeto, deseja-se comparar os desempenhosdos algoritmos de modo a determinar se algum ou alguns

deles são superiores aos demais, com fundamentaçãomatemática e não apenas com uma análise informal ouempírica. Os testes de hipóteses estatísticos são, portanto,adequados e fundamentais para essa comparação. Pode-sedeterminar, baseando-se em um número adequado deamostras, se os desempenhos são diferentes ou equivalentes,como também, quais são os melhores.

III. ESPECIFICAÇÕES DOS EXPERIMENTOS

A. Base de dados

As imagens de dígitos foram extraídas da base NISTSD19 [5], que é uma base de formulários numéricos,disponibilizada pelo NIST ( National Institute of Standards

and Technology, dos Estados Unidos da América). Cadaimagem contém variadas quantidades de dígitos, como se pode ver na Figura 1.

Figura 1: Exemplos da base NIST SD19.

Os dígitos foram isolados por um algoritmo desegmentação específico para esse fim, baseado emcomponentes conectados [6]. Isso foi feito para separar cadadígito e armazenar em uma imagem individual. Depois disso,cada número foi rotulado com sua saída desejada, para

possibilitar o uso de aprendizagem supervisionada.Como os dígitos não têm o mesmo tamanho realizou-se

uma padronização, fazendo com que cada um fosse umaimagem 20x25 (Figura 2). Essas dimensões de imagemforam definidas empiricamente. O próximo passo consisteem encontrar as coordenadas que delimitam os dígitosusando projeções horizontais e verticais [7].

A base de dígitos isolados usada contém um total de11.377 dígitos. Cada classe tem em média 1.150 dígitos, comdiferenças pequenas entre cada uma delas, o que indica queos dados são balanceados por classe.



Figura 2: Imagens de dígitos redimensionadas para 20x25.

B. Metodologia dos experimentos

A experimentação se baseia no esquema de holdout estratificado [8]. O procedimento holdout consiste emreservar certa quantidade de dados para teste, e o restante

para treinamento. Normalmente, também sendo aconfiguração utilizada neste trabalho, usa-se 1/3 dos dados

para teste e consequentemente 2/3 para a aprendizagem.Emprega-se uma amostragem estratificada para manter as

proporções entre as classes da base como um todo em cadaconjunto. Isso garante que se tenham exemplos de todas asclasses nos conjuntos de treino e teste, além de facilitar aaprendizagem e também refletir a distribuição dos dados naconstrução da superfície de decisão.

Costuma-se repetir o holdout um número razoável de

vezes, visto que uma única execução pode trazer estimativasde desempenho não confiáveis. A ideia é que ao analisar odesempenho geral do método considerando todas asrepetições, ter-se-á uma estimativa mais confiável do poderde generalização do modelo, ou seja, sua confiabilidade aoanalisar novos exemplos.

Assim, teremos trinta taxas de acerto para cada um dossete classificadores analisados. Esses dados correspondem àsentradas para os testes de hipótese.

C. Implementações

As implementações deste trabalho foram realizadas emdois softwares/linguagens: o R [9] e o MATLAB [10]. Especificamente, no R se fez toda a parte de análise dos

dados, e a maior parte dos testes de hipótese (com exceçãodo teste de Lilliefors, que foi feito no MATLAB).

D.

Variáveis estudadas

Basicamente, a variável a ser estudada e analisada na pesquisa é a taxa de acerto média dos classificadores. Issoocorre porque se deseja verificar se os desempenhos delessão equivalentes ou não, e de forma natural, determinar qualclassificador apresenta melhor desempenho. Assim, os testesde hipótese visam dar suporte à determinação da melhorconfiguração de parâmetros do classificador de dígitosmanuscritos utilizado.

Não se fez uma análise de tempo porque como estamosestudando várias configurações do mesmo algoritmo, ostempos de treinamento são praticamente os mesmos, nãoimportando o classificador em questão.

IV. A NÁLISE EXPLORATÓRIA

Nesta seção descrevemos os dados da pesquisa, fazendoum estudo descritivo através das medidas estatísticas(apresentado na Tabela 1), gráficos box-plot das amostras(Figura 3) e dos histogramas (Figura 4). Além disso, fazemos

os testes de aderência para verificação da normalidade dosdados.

A. Estatística descritiva

Calculamos a média, desvio padrão e mediana dosalgoritmos em estudo (Tabela I). Não foi incluída a moda nasmedidas pelo fato de os dados serem contínuos. Como pode

se observar na Tabela I, as médias e medianas são bastante próximas para cada classificador. Isso indica certa tendênciaà normalidade visto que na distribuição normal, a média e amediana são iguais.

TABELA 1: ESTATÍSTICA DESCRITIVA DOS ALGORITMOS

Média MedianaPoli1 0,9298793 0,92923Poli2 0,9591030 0,95857Poli3 0,9593137 0,959RBF8 0,9653980 0,965495RBF9 0,9671793 0,96716RBF10 0,9675053 0,967405

RBF11 0,9669787 0,967105

Figura 3: Gráficos box-plot das amostras.

A observação visual dos dados apresentados na Figura 3 já mostra uma tendência à normalidade, em especial osresultados dos algoritmos RBF.

As amostras possuem poucos pontos aberrantes.Podemos ver na Figura 4 que o algoritmo RBF8 apresentou a

maior quantidade: três valores, sendo dois inferiores(0,95753 e 0,95886) e um superior (0,97356). Os algoritmosRBF9, RBF10 e RBF11 têm cada, apenas um valordiscrepante superior, que são: 0,97587, 0,97696 e 0,97591,respectivamente.



Figura 4: Histogramas das amostras.

B. Testes de aderência

A confirmação das amostras seguirem uma distribuiçãonormal foi obtida realizando os testes de aderência. Doistestes foram executados com as amostras padronizadas:Kolmogorov-Smirnov [11] e Lilliefors [12] (Tabela 2). A

padronização dos dados foi necessária porque os testes se baseiam na diferença entre a distribuição normal padrão e adistribuição da amostra. Logo, se as amostras não são

padronizadas, o resultado do teste tende a rejeitar a hipótesede normalidade, já que provavelmente não se tem amostrascom média zero, e variância um, como a normal padrão.

Em todas as tabelas, adotamos a convenção “Poli” paraos núcleos polinomiais, e o parâmetro interno de cada funçãokernel é descrito pelo número ao lado do nome da função.

TABELA 2: P-VALUES DOS TESTES DE ADERÊNCIA

P-values

Kolmogorov-Smirnov LillieforsPoli1 0,7350677 0,2612Poli2 0,9120706 0,5000*Poli3 0,9595365 0,5000*RBF8 0,8051991 0,3613

RBF9 0,8966829 0,5000*RBF10 0,6535829 0,2236RBF11 0,7211455 0,2981

Considerando que todos os p-values foram superiores aonível de significância empregado (5%), a hipótese nula não érejeitada e, portanto ambos os testes de aderência indicamque as amostras se aproximam de uma distribuição normal.

V. R ESULTADOS

A.

Formulação das hipóteses

Como o objetivo da pesquisa é determinar se hádiferença de desempenho entre os algoritmos e, em caso

positivo, qual(is) é(são) o(s) melhor(es), precisamos testaros resultados dos algoritmos aos pares. Essa estratégia é

justificada, inclusive, pelo fato de as mesmas 30 amostras

terem sido usadas para todos os algoritmos.

Figura 5: Fluxograma para decisão dos testes de hipótese.



Dessa forma, para cada par de algoritmos, testamos duashipóteses, nesta ordem: médias iguais ou diferentes , médiasiguais ou média do primeiro ser maior que a do segundo.Caso o segundo teste não rejeite a hipótese nula, conclui-seque a média do primeiro algoritmo é menor. Os testes foramrealizados utilizando o t-student pareado [11], com nível designificância 5%.

A decisão da comparação é dada pelo fluxograma daFigura 5.

B.

Testes de hipóteses

O método de Friedman com o pós-teste de Nemenyi foiutilizado como teste alternativo para comparação entreclassificadores. A distribuição de teste escolhida foi a chi-quadrado ao invés de Friedman, pois existem 30 amostrasde 7 classificadores como aponta [13], com α = 0,05. Para o

pós-teste de Nemenyi ,

q0,05 = 2,949.

Com p-value = 2,369791e-31, rejeitamos a hipótese deque os classificadores eram iguais. Com o valor crítico de

Nemenyi, CD = 1,644874, foi possível encontrar as

diferenças críticas entre pares de classificadores isolados,apresentados na Tabela 3. A Tabela 4 mostra as diferençasentre os rankings na comparação par a par feita no pós-testede Nemenyi. Estes valores são usados para decidir se hádiferença ou não entre os classificadores, comparando adiferença entre o par com o valor crítico (se for maior ouigual, há diferença significativa entre os classificadores).

TABELA 3: R ESULTADOS DO TESTE DE FRIEDMAN

Poli2 Poli3 RBF8 RBF9 RBF10 RBF11

Poli1 ≈ ≈ ≠ ≠ ≠ ≠

Poli2≈

≠

≠

≠

≠

Poli3 ≠ ≠ ≠ ≠

RBF8 ≈ ≠ ≈

RBF9 ≈ ≈

RBF10 ≈

TABELA 4: DIFERENÇAS ENTRE RANKINGS.


Poli1 1.50000 1.56667 3.28333 4.91667 5.30000 4.43333

Poli2 0.06667 1.78333 3.41667 3.80000 2.93333

Poli3 1.71667 3.35000 3.73333 2.86667

RBF8 1.63333 2.01667 1.15000

RBF9 0.383333 0.483333

RBF10 0.866667

A comparação dos algoritmos aos pares está resumida naTabela 5. Os sinais de menor, maior e equivalente dizemrespeito à comparação do algoritmo da linha com o dacoluna. Na Tabela 6 temos um ou dois p-values de acordocom a quantidade de hipóteses testadas para se chegar aoresultado (vide Figura 5).

Os espaços em branco na diagonal principal da tabelarepresentam o que seria a comparação de um algoritmo comele mesmo. Os demais representam comparações járealizadas na parte superior à diagonal principal.

Os resultados das comparações nos levam à conclusãoque o algoritmo RBF10 obteve o melhor desempenho noreconhecimento de dígitos manuscritos. Podemos aindamontar um ranking baseado nos desempenhos dosalgoritmos, como segue:

1. RBF102. RBF9, RBF113. RBF84. Poli3, Poli2

5. Poli1

TABELA 5: R ESULTADOS DO TESTE T.


Poli1 < < < < < <

Poli2 ≈ < < < <

Poli3 < < < <

RBF8 < < <

RBF9 < ≈

RBF10 >

TABELA 6: P-VALUES DO TESTE T.


Poli1 8,481e-281,0000000

4,851e-271,0000000

9,382e-291,0000000

1,277e-291,0000000

2,960e-301,0000000

9,105e-301,0000000

Poli20,7636 7,367e-11

1,00000003,402e-141,0000000

5,526e-141,0000000

9,580e-131,0000000

Poli3 2,641e-131,0000000

1.855e-151,0000000

3.343e-161,0000000

4.377e-161,0000000

RBF8 4,542e-111,0000000

5,073e-091,0000000

5,850e-060.9999971

RBF9 0,03724000,98138 0,3696756

RBF10 0,0009750,000487

VI. CONCLUSÕES

O reconhecimento de dígitos manuscritos é uma tarefaimportante em diversas aplicações. Dessa forma, odesempenho de classificadores se torna cada vez maiscrítico. Neste trabalho se investigou o desempenho de um



classificador baseado em um conjunto de SVMs, variando afunção kernel e seu parâmetro interno.

Assim, fez-se a análise exploratória dos dados relativosao desempenho dos classificadores, e construíram-se ashipóteses para fazer a avaliação dos mesmos. A partir daanálise exploratória, e das hipóteses formuladas, aplicaram-se os testes adequados para determinar qual classificador

obteve melhor desempenho.Os resultados evidenciaram que a configuração com

kernel RBF e desvio igual a 10 foi superior às demais.Portanto, pode-se dizer que essa configuração deve ser usadaao se empregar esse classificador para o reconhecimento dedígitos manuscritos.

R EFERÊNCIAS [1]

C. A. B. Mello et al., “An efficient thresholding algorithm for brazilian bank checks,” ICDAR 2007, Brazil, vol. 1, pp. 193-197.

[2]

T. Akiyama et al., “Handwritten address interpretation systemallowing for non-use of postal codes and omission of addresselements,” IWFHR 2004, Japan, pp. 527-532.

[3] Neves et al., “A SVM based off-line digit recognizer ,” SMC 2011,Anchorage, USA, pp. 510-515.

[4]

Cortes, C. and Vapnik, V. Support-Vector Networks. “MachineLearning”, vol. 20, no. 3, pp. 273-297, 1995.

[5]

NIST Special Database 19. Handprinted Forms and CharactersDatabase. Link: http://www.nist.gov/srd/nistsd19.cfm. Acessado em

junho, 2013.

[6]

E. R. Davies, “Machine Vision”, Morgan Kaufmann, 3rd ed, 2005.

[7]

J. R. Parker, “Algorithms for Image Processing and Computer Vision,John Wiley and Sons, 1997.

[8]

R. O. Duda, P. E. Hart and, D. G. Stork, “Pattern Classification”,John Wiley and Sons, 2nd ed, 2001.

[9]

R Project for Statistical Computing. Link: http://www.r-project.org/.Acessado em junho, 2013.

[10] MATLAB, Mathworks. The language of technical computing. Link:http://www.mathworks.com/products/matlab/. Acessado em junho,2013.

[11]

D. C. Montgomery and G. C. Runger, “Estatística Aplicada eProbabilidade para Engenheiros”, LTC, 5ª ed, 2012.

[12] H. W. Lilliefors, “On the Kolmogorov-Smirnov test for normalitywith mean and variance unknown.”, Journal of the AmericanStatistical Association. vol. 62, pp. 399 – 402, 1967.

[13]

J. Demšar. “Statistical Comparisons of Classifiers over Multiple DataSets”, J. Mach. Learn. Res., vol. 7, pp. 1-30, 2006.

Documents

Relatorio Final - Estatística