Trabalho de reconhecimento de padrões

UNIVERSIDADE FEDERAL DO AMAZONAS

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA

 RECONHECIMENTO DE PADRÕES 2016/1 – TRABALHO 01

1 INTRODUÇÃO

Um problema a ser resolvido pela área científica denominada reconhecimento de padrões consiste na busca da classificação ou categorização de objetos de interesse.

Com a evolução da sociedade de uma fase industrial a uma fase pós-industrial, a automação de processos industriais e a necessidade do tratamento e recuperação de informações são cada vez mais importantes. Esta tendência fez com que o reconhecimento de padrões viesse a ocupar uma posição de destaque em aplicações e pesquisas avançadas de engenharia, sendo parte integrante da maior parte de sistemas de máquinas inteligentes envolvidos na tomada de decisão. [Pattern recognition, Sergis Theodoridis, 4th edition].

 Neste artigo, investigaremos a desempenho de três técnicas de classificação na resolução de um problema do livro texto supracitado adotado à disciplina Técnicas de reconhecimento de padrões do programa de pós-graduação em engenharia elétrica da Universidade Federal do Amazonas.

Serão utilizadas as técnicas de classificação de Bayes, baseada em teoria estatística, e de distância mínima Euclidiana e de Mahalanobis, métodos algébricos, em um problema no qual dois conjuntos de 1000 vetores bidimensionais, X5 e X5’, pertencentes a 3 classes modeladas por distribuição normal com valores médios  com matrizes de covariância iguais a duas vezes a matriz identidade de ordem 2. Na geração dos conjunto de vetores, dá-se que as classes de X5 são equiprováveis, enquanto as probabilidades a priori das classes de X5’ são dadas pelo vetor  .[pic 1][pic 2][pic 3][pic 4][pic 5]

 

2 FUNDAMENTAÇÃO TEÓRICA

Classificador de Bayes

O classificador de Bayes tem como objetivo calcular a probabilidade que uma amostra desconhecida pertença a cada uma das classes possíveis, ou seja, predizer a classe mais provável. Os classificadores Bayesianos simples assumem que o efeito do valor de um atributo sobre uma determinada classe independente dos valores dos demais atributos. Essa consideração, conhecida como independência condicional, tem como objetivo simplificar o processamento envolvido na tarefa de classificação. O classificador Bayesiano é baseado no teorema de Bayes para calcular as probabilidades de um elemento pertencer a uma classe.

Teorema de Bayes

Admitamos  um conjunto de classes e  uma instância cuja classe é desconhecida. Considerando-se que  pertence a uma das classes do conjunto , em problemas de classificação, deseja-se determinar , isto é, a probabilidade da classe  dada a instância  . O teorema de Bayes permite o cálculo da probabilidade à posteriori da classe  condicionada a ,  , da seguinte forma: [pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12][pic 13][pic 14][pic 15][pic 16]

Onde  é a probabilidade à priori de  ,  é a probabilidade à priori de  e  é a probabilidade à posteriori de  condicionada a . As probabilidades ,  , e podem ser estimadas a partir das instâncias de treinamento.[pic 17][pic 18][pic 19][pic 20][pic 21][pic 22][pic 23][pic 24][pic 25][pic 26]

O classificador Bayesiano simples considera que cada instância é representada por um vetor de atributos -dimensional,  , o qual contém os valores dos seus  atributos,  . Supondo que existam  classes, {, a uma instância  cuja classe é desconhecida, esse classificador atribuirá a classe que tem a maior probabilidade à posteriori  . Desse modo,  é associada à classe  , se e somente se:[pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36]

[pic 37]

Portanto, para se classificar uma instância desconhecida  , basta encontrar a maior probabilidade  . O cálculo de  é realizado utilizando-se o teorema de Bayes. Como  é constante para todas as classes,  pode ser expresso como:   .[pic 38][pic 39][pic 40][pic 41][pic 42][pic 43]

 pode ser estimado a partir da base de dados de treinamento da seguinte maneira:  [pic 44][pic 45]

Onde  é o número de instâncias de treinamento que pertencem à classe  e  é o número total de instâncias de treinamento.[pic 46][pic 47][pic 48]

Classificador Euclidiano

O classificador euclidiano baseia-se no cálculo da distância Euclidiana para cada elemento para atribuir classes aos objetos. Aplicando essa fórmula como distância, o espaço euclidiano torna-se um espaço métrico. A distância euclidiana pode ser calculada em espaços de uma dimensão e em espaços de  dimensões.[pic 49]

Distância euclidiana: [pic 50]

O classificador de distância euclidiana realaciona a menor distância de um elemento à média de uma classe mais próxima e classifica-o à esta classe.

Classificador de Mahalanobis

A distância de Mahalanobis é uma métrica que difere da distância Euclidiana por levar em consideração a correlação entre os conjunto de dados. A fórmula para distância de Mahalanobis entre dois vetores da mesma distribuição que possuam uma matriz de covariância Σ é dada por:

[pic 51]

Se a matriz de covariância é a matriz identidade, esta fórmula se reduz à distância euclidiana. Caso contrario sua fórmula é dada por:

[pic 52]

Semelhantemente ao classificador Euclidiano, as distâncias do ponto em relação às classes são  utilizadas para atribuir o objeto de entrada à classe cujos parâmetros resultaram no cálculo da menor magnitude.

---

3 METODOLOGIA

O desenvolvimento do código Matlab neste trabalho deu-se pela criação ordenada de funções para realizar a computação das equações relacionadas à geração dos conjuntos dos vetores de dados, à plotagem dos conjuntos gerados, à aplicação dos vetores na entrada dos classificadores de Bayes, Euclidiano, e de Mahalanobis, este último para fins de comparação mesmo que não tenha sido requisitado pelo exercício proposto, e à computação dos erros obtidos após as aplicações dos classificadores mencionados.