Desenvolva um algoritmo capaz de calcular a distância entre dois pontos na euclidogênese cósmica

2- Elabore um algoritmo capaz de calcular a distancia ente dois pontos em um espaço euclidianUNIVERSIDADE FEDERAL DE PERNAMBUCO

GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO

CENTRO DE INFORMÁTICA

2007.1

Avaliação do Comportamento de Métricas de Distância com Ponderação de Características

PROPOSTA DE TRABALHO DE GRADUAÇÃO EM

APRENDIZAGEM DE MÁQUINA

Aluno – Tiago Buarque Assunção de Carvalho <[e-mail]>

Orientador – George Darmiton da Cunha Cavalcanti <[e-mail]>

Co-Orientador – Tsang Ing Ren <[e-mail]>

Recife, 18 de Maio de 2007.

1. Contexto

O algoritmo de classificação baseado no vizinho mais próximo (Nearest Neighbor – NN) é uma técnica amplamente empregada para reconhecer padrões. O centro de seu funcionamento está em descobrir o vizinho mais próximo de uma dada instância. O algoritmo (k-Nearest Neighbor – k-NN) pertence a um grupo de técnicas denominada de Instance-based Learning. Nesse caso, são encontrados os k vizinhos mais próximos do padrão de consulta, ao invés de apenas o vizinho mais próximo. Dito dessa forma, esse método é bastante simples e de fácil implementação.

O kNN classifica um dado elemento de acordo com as respectivas classes dos k (k ≥ 1) vizinhos mais próximos – pertencentes a uma base de treinamentos dada. O algoritmo calcula a distância do elemento dado para cada elemento da base de treinamento e então ordenar os elementos da base de treinamento do mais próximo ao de maior distância. Dos elementos ordenados selecionam-se apenas os k primeiros, que servem de parâmetro para a regra de classificação. Exemplo: 1-NN é um k-NN sabendo que k = 1, ou seja, seleciona-se apenas o elemento do treinamento mais próximo da instância que se pretende classificar. 5-NN vai usar os cinco elementos mais próximos da instância e baseado nas classes dos cinco elementos, infere-se a classe do elemento de teste.

Dois pontos importantes no k-NN são: a regra de classificação e função que calcula a distância entre duas instâncias. A regra de classificação diz como o algoritmo vai tratar a importância de cada um dos k elementos selecionados – os k mais próximos. À função de distância cabe a tarefa de mensurar a disparidade entre dois elementos de forma a poder identificar quais são os k-NN.

Para k = 1 a regra de classificação é irrelevante, pois só existe um elemento só tem uma classe, logo atribui-se a classe desse elemento àquele que se pretende classificar. Porém, com k > 1, é preciso haver uma regra para discernir a qual classe se atribuirá o elemento. Em [1] são revistas as duas regras de classificação clássicas: maioria na votação e peso pela distância. Na primeira, cada elemento tem uma influência igual, a classe escolhida é aquela que possuir mais representantes entre o k-NN. Já no peso pela distância cada k-vizinho tem um peso inversamente proporcional à sua distância.

Na literatura são as funções de distância são o maior viés de estudo no kNN, pois possibilitam as maiores variações no resultados obtidos por esse algoritmo, podendo inclusive obter resultados em nível de estado da arte nessa área [1], [2], [4] e [6].

Em se tratando de distância entre dois elementos é preciso definir o que são esses elementos: cada elemento tem uma classe – usada na regra de classificação – e um vetor de atributos, e cada um desses atributos tem um tipo que indica quais operações se pode realizar sobre o atributo. E é por meio dessas operações que se torna possível o cálculo das distâncias. Dois elementos do mesmo domínio possuem o mesmo número n de atributos, seja i uma posição no vetor de atributos de um elemento qualquer, 1  i  n, se dois elementos pertencem ao mesmo domínio os atributos da posição i de cada elemento têm o mesmo tipo. Em [1] é listado quatro tipos de atributos: nominal, ordinal, intervalar e racional. Contudo apenas dois são considerados: nominal, também chamado de categórico, e racional, chamado numérico. Um atributo categórico é um nome ou um rótulo, e permite somente as operações de “igualdade” e de “diferença”. O numérico é um número, portanto, pode-se comparar não só a igualdade, mas também “maior”, “menor”, “adição”, “subtração”, “multiplicação” e “divisão”. Exemplo: uma base de canetas pode ser representada por quatro atributos: cor da tinta, fabricante, tamanho da ponta e preço. Caneta1(azul, BIC, 0.7, 0,50) e Caneta2(preta, Faber Castell, 0.5, 1,00). Pode-se definir que o preço é um atributo numérico e os demais são categóricos. Note que o tamanho da ponta apesar de poder ser representado por um número na prática é apenas um rótulo.

Wilson et al. [2] enumeram várias funções de distâncias entre atributos, o exemplo mais clássico é a distância Euclidiana para atributos numéricos e a distância de Hamming para atributos categóricos. Essas distâncias por si só não resolvem o problema de calcular a diferença entre dois vetores de atributos, é preciso combinar estratégias para realizar tal tarefa. Algumas estratégias apresentadas em [1] e em [2] estão aqui listadas: HEOM, HVDM, DVDM e IVDM.

Algumas das funções de distância em [2] servem como base para a comparação com outros resultados, portando valem a pena serem citadas nesse documento:

 HEOM – Heterogeneous Euclidean-Overlap Metric: utiliza distância Euclidiana para atributos numéricos e distância de Hammig(overlap) para atributos categóricos.

 HVDM – Heterogeneous Value Difference Metric: ainda usa distância Euclidiana para atributos numéricos, mas para atributos categóricos emprega vdm – value difference metric. Ambas as funções estão definidas abaixo. Na,x,c é o número de elementos na base de treinamento que, para o atributo de índice a, assumem o valor x e pertencem à classe c e Na,x é o somatório de Na,x,c para todas as classes, ou seja, o número total de elementos que assumem o valor x para a o atributo