EP1_2023 (1)

Prévia do material em texto

Trabalho Primeiro EP
Prof. Dr. Clodoaldo A. de Moraes Lima
Material baseado no livro “Patterson, David A., Hennessy, J. L.
- Computer Organization And Design: The Hardware/Software
Interface”
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 1 / 18
Descrição
Um problema de reconhecimento de padrão consiste de uma tarefa de
classificação ou categorização, onde as classes são definidas pelo projetista do
sistema (classificação supervisionada) ou são aprendidas de acordo com a
similaridade dos padrões (classificação não supervisionada).
O KNN ( K-vizinhos mais próximos do inglês K-nearest neighbors) costuma ser
um dos primeiros algoritmos aprendidos por iniciantes no mundo do aprendizado
de máquina. O KNN é muito utilizado em problemas de classificação, e felizmente
é um dos algoritmos de aprendizado de máquina mais fáceis de se compreender.
Em resumo, o KNN tenta classificar cada amostra de um conjunto de dados
avaliando sua distância em relação aos vizinhos mais próximos. Se os vizinhos
mais próximos forem majoritariamente de uma classe, a amostra em questão será
classificada nesta categoria.
Neste trabalho deve ser implementado o algoritmo KNN.
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 2 / 18
Descrição
Exemplo
Para entender como o KNN funciona detalhadamente, primeiro considere que
temos um conjunto de dados de treinamento dividido em duas classes: azul e
vermelho. Estes dados correspondem a dois arquivos, um com conjunto de
entrada e outro com o conjunto de sáıda desejado.
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 3 / 18
Descrição
Exemplo
Agora recebemos uma amostra que ainda não está classificada, e gostaŕıamos de
definir se ela pertence à classe azul ou à classe vermelha. Digamos que essa nova
amostra (cor verde na figura abaixo) esteja localizada nessa região:
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 4 / 18
Descrição
Exemplo
Intuitivamente, podemos observar que faz mais sentido classificar essa amostra
como pertencendo à classe vermelha. Mas o algoritmo não possui intuição, ele
precisa de um cálculo matemático para poder definir a solução.
No caso do KNN, a lógica é a seguinte: observa-se a classe dos vizinhos mais
próximos, em uma votação onde a maioria vence. Por exemplo, vamos supor que
estamos analisando os 3 vizinhos mais próximos. Obs: mais próximo significa com
a menor distância em relação à amostra:
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 5 / 18
Descrição
Exemplo
Na figura acima, podemos ver que os 3 vizinhos mais próximos pertencem à classe
vermelha. Então como houve 3 votos a zero para a classe vermelha, essa amostra
fica sendo classificada nessa classe:
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 6 / 18
Descrição
Exemplo
Obs: talvez agora esteja mais claro o significado do nome KNN, que refere-se a
k-vizinhos mais próximos, onde k é um número que podemos determinar. Nesse
exemplo, estamos usando k=3. Agora recebemos outra amostra que queremos
classificar:
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 7 / 18
Descrição
Exemplo
Utilizando o mesmo método KNN com k=3:
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 8 / 18
Descrição
Exemplo
Encontramos os 3 vizinhos mais próximos dessa amostra. Dessa vez, há duas
amostras da classe vermelha e uma da classe azul. Como a votação ficou 2x1 para
a classe vermelha, essa amostra ficaria sendo classificada nessa classe:
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 9 / 18
Descrição
Exemplo
Essa metodologia poderia ser aplicada para qualquer nova amostra e estaŕıamos
aptos a definir sua devida classificação. Porém até agora utilizamos apenas o
exemplo de k=3. Na prática, podemos escolher outro valor de k. Vamos supor
que a mesma amostra anterior estivesse sendo analisada com o algoritmo de KNN
com k=5:
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 10 / 18
Descrição
Exemplo
Dessa vez, dos 5 vizinhos mais próximos, 3 são azuis e 2 são vermelhos. Portanto
a classe vencedora foi a azul. Essa amostra seria classificada nessa classe:
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 11 / 18
Descrição
Exemplo
Nota-se que, dependendo do valor de k, poderemos ter resultados diferentes para
cada situação. Quando o k é pequeno, a classificação fica mais senśıvel a regiões
bem próximas (podendo ocorrer o problema de overfitting). Com k grande, a
classificação fica menos sujeita a rúıdos pode ser considerada mais robusta, porém
se k for grande demais, pode ser que haja o problema de underfitting.
Obs: nos exemplos desse artigo, tentamos mostrar visualmente quais eram os
vizinhos mais próximos em cada situação. Porém não podemos esquecer que a
forma como o algoritmo faz essa seleção é calculando a distância de cada um dos
pontos já classificados em relação à nova amostra que queremos classificar. Ou
seja, como nos exemplos havia cerca de 30 amostras já classificadas, o algoritmo
KNN teria que fazer o cálculo da distância de cada um desses pontos em relação à
nova amostra, e ordenar depois do menor ao maior, selecionando assim as
amostras mais próximas.
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 12 / 18
Algoritmo KNN
Passo 1 - Para um dado não classificado, calcule distância do novo dado em
relação a cada um dos outros dados que já estão classificados;
Passo 2 - Selecione as k menores distâncias;
Passo 3 - Verifique a(s) classe(s) dos dados que tiveram as K menores
distâncias e contabilize a quantidade de vezes que cada classe que apareceu;
Passo 4 - Classifique esse novo dado como pertencente à classe que mais
apareceu.
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 13 / 18
Descrição
O que deve ser feito
Sua tarefa neste trabalho será implementar o algoritmo KNN na linguagem
assembly.
O conjunto de treinamento está armazenado em dois arquivos: xtrain.txt,
ytrain.txt
O conjunto teste esta armazenado em dois arquivos: xtest.txt, ytest.txt
O tamanho máximo do vetor é denotado por n, não é conhecido a priori.
O Aluno deve varer o arquivo para identificar o número de entrada e
atributos.
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 14 / 18
Requisitos
A função principal deve chamar uma função knn deve obrigatoriamente possuir a
seguinte assinatura:
Requisito 1
int knn(i float *xtrain, float *ytrain, float *xtest), onde:
knn: Nome da função (também em assembly);
retorno: classe correspondente;
float *xtrain: especifica a base do vetor de entrada do treinamento;
float *ytrain: especifica a base do vetor de sIS do treinamento;
float *xtrain: especifica a base do vetor de entrada do teste
Requisito 2
Os dados devem ser lidos de um arquivo, o qual ser passado como entrada para o
programa. A classe predita para o conjunto de teste deve ser escrita num arquivo.
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 15 / 18
Entrega
O que deve ser entregue?
Documentação descrevendo a lógica principal da sua implementação;
Código do fonte do seu programa em assembly;
Documentação e código-fonte devem ser enviados como anexo para o
e-disciplina
Quem? Quando?
Grupos de 4 alunos.
Data da Entrega até o dia 24/10/2023 (23:59).
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 16 / 18
Dicas
Utilize o simulador MARS para executar e testar seu programa. Nele é
posśıvel acompanhar passo-a-passo a execução do algoritmo, além de saber o
valor de cada um dos registradores.
(http://courses.missouristate.edu/kenvollmar/mars/). Listagem
das chamadas de sistema dispońıveis no MARS: http://courses.
missouristate.edu/kenvollmar/mars/help/syscallhelp.html.
De modo a facilitar seu trabalho, codifique primeiro o programa em
linguagem de alto-ńıvel e depois simplesmente o traduza para assembly MIPS.
Utilizecomo referência os trechos de código abaixo. Eles podem ser úteis na
leitura dos dados digitados pelo usuário no MARS.
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 17 / 18
(http://courses.missouristate.edu/kenvollmar/mars/)
http://courses.missouristate.edu/kenvollmar/mars/help/syscallhelp. html
http://courses.missouristate.edu/kenvollmar/mars/help/syscallhelp. html
Referências
PATTERSON, D. A., HENNESSY, J. L., Organização e Projeto de
Computadores: A Interface Hardware/ Software, Ed. Campus, 5a ed., 2014.
Prof. Dr. Clodoaldo A. de Moraes Lima Trabalho Primeiro EP 18 / 18