Implementacao do Algoritmo KNN - Trabalho Academico

Descricao Um problema de reconhecimento de padrao consiste de uma tarefa de classificacao ou categorizacao onde as classes sao definidas pelo projetista do sistema classificacao supervisionada ou sao aprendidas de acordo com a similaridade dos padroes classificacao nao supervisionada O KNN Kvizinhos mais proximos do inglˆes Knearest neighbors costuma ser um dos primeiros algoritmos aprendidos por iniciantes no mundo do aprendizado de maquina O KNN e muito utilizado em problemas de classificacao e felizmente e um dos algoritmos de aprendizado de maquina mais faceis de se compreender Em resumo o KNN tenta classificar cada amostra de um conjunto de dados avaliando sua distˆancia em relacao aos vizinhos mais proximos Se os vizinhos mais proximos forem majoritariamente de uma classe a amostra em questao sera classificada nesta categoria Neste trabalho deve ser implementado o algoritmo KNN Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 2 18 Descricao 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 saıda desejado Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 3 18 Descricao Exemplo Agora recebemos uma amostra que ainda nao esta classificada e gostarıamos de definir se ela pertence a classe azul ou a classe vermelha Digamos que essa nova amostra cor verde na figura abaixo esteja localizada nessa regiao Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 4 18 Descricao Exemplo Intuitivamente podemos observar que faz mais sentido classificar essa amostra como pertencendo a classe vermelha Mas o algoritmo nao possui intuicao ele precisa de um calculo matematico para poder definir a solucao No caso do KNN a logica e a seguinte observase a classe dos vizinhos mais proximos em uma votacao onde a maioria vence Por exemplo vamos supor que estamos analisando os 3 vizinhos mais proximos Obs mais proximo significa com a menor distˆancia em relacao a amostra Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 5 18 Descricao Exemplo Na figura acima podemos ver que os 3 vizinhos mais proximos pertencem a classe vermelha Entao 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 Descricao Exemplo Obs talvez agora esteja mais claro o significado do nome KNN que referese a kvizinhos mais proximos onde k e um numero que podemos determinar Nesse exemplo estamos usando k3 Agora recebemos outra amostra que queremos classificar Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 7 18 Descricao Exemplo Utilizando o mesmo metodo KNN com k3 Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 8 18 Descricao Exemplo Encontramos os 3 vizinhos mais proximos dessa amostra Dessa vez ha duas amostras da classe vermelha e uma da classe azul Como a votacao 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 Descricao Exemplo Essa metodologia poderia ser aplicada para qualquer nova amostra e estarıamos aptos a definir sua devida classificacao Porem ate agora utilizamos apenas o exemplo de k3 Na pratica podemos escolher outro valor de k Vamos supor que a mesma amostra anterior estivesse sendo analisada com o algoritmo de KNN com k5 Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 10 18 Descricao Exemplo Dessa vez dos 5 vizinhos mais proximos 3 sao azuis e 2 sao 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 Descricao Exemplo Notase que dependendo do valor de k poderemos ter resultados diferentes para cada situacao Quando o k e pequeno a classificacao fica mais sensıvel a regioes bem proximas podendo ocorrer o problema de overfitting Com k grande a classificacao fica menos sujeita a ruıdos pode ser considerada mais robusta porem 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 proximos em cada situacao Porem nao podemos esquecer que a forma como o algoritmo faz essa selecao e calculando a distˆancia de cada um dos pontos ja classificados em relacao a nova amostra que queremos classificar Ou seja como nos exemplos havia cerca de 30 amostras ja classificadas o algoritmo KNN teria que fazer o calculo da distˆancia de cada um desses pontos em relacao a nova amostra e ordenar depois do menor ao maior selecionando assim as amostras mais proximas Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 12 18 Algoritmo KNN Passo 1 Para um dado nao classificado calcule distˆancia do novo dado em relacao a cada um dos outros dados que ja estao classificados Passo 2 Selecione as k menores distˆancias Passo 3 Verifique as classes dos dados que tiveram as K menores distˆancias e contabilize a quantidade de vezes que cada classe que apareceu Passo 4 Classifique esse novo dado como pertencente a classe que mais apareceu Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 13 18 Descricao O que deve ser feito Sua tarefa neste trabalho sera implementar o algoritmo KNN na linguagem assembly O conjunto de treinamento esta armazenado em dois arquivos xtraintxt ytraintxt O conjunto teste esta armazenado em dois arquivos xtesttxt ytesttxt O tamanho maximo do vetor e denotado por n nao e conhecido a priori O Aluno deve varer o arquivo para identificar o numero de entrada e atributos Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 14 18 Requisitos A funcao principal deve chamar uma funcao knn deve obrigatoriamente possuir a seguinte assinatura Requisito 1 int knni float xtrain float ytrain float xtest onde knn Nome da funcao tambem 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 Documentacao descrevendo a logica principal da sua implementacao Codigo do fonte do seu programa em assembly Documentacao e codigofonte devem ser enviados como anexo para o edisciplina Quem Quando Grupos de 4 alunos Data da Entrega ate o dia 24102023 2359 Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 16 18 Dicas Utilize o simulador MARS para executar e testar seu programa Nele e possıvel acompanhar passoapasso a execucao do algoritmo alem de saber o valor de cada um dos registradores httpcoursesmissouristateedukenvollmarmars Listagem das chamadas de sistema disponıveis no MARS httpcourses missouristateedukenvollmarmarshelpsyscallhelphtml De modo a facilitar seu trabalho codifique primeiro o programa em linguagem de altonıvel e depois simplesmente o traduza para assembly MIPS Utilize como referˆencia os trechos de codigo abaixo Eles podem ser uteis na leitura dos dados digitados pelo usuario no MARS Prof Dr Clodoaldo A de Moraes Lima Trabalho Primeiro EP 17 18 Referˆencias PATTERSON D A HENNESSY J L Organizacao 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