3.8 Algoritmo K-Nearest Neighbor (kNN)

Deixe nosso conjunto de treinamento consistir em pares de números \((x_1,x_2)(x_1,x_2)\) e os nomes de classe correspondentes. Os pares podem ser representados como pontos no plano, onde a primeira coordenada \(x_1\) denota o valor no eixo x e a segunda coordenada \(x_2\) denota o valor no eixo y. Na prática, os valores de \(x_1\) e \(x_2\) estão sempre associados a alguns atributos específicos, por exemplo, temperatura e humidade, mas agora podemos pensar neles como alguns valores gerais. Cada par de números pertence a uma de duas classes: triângulos vermelhos ou quadrados azuis. Como existem apenas duas classes, pode assumir-se que é uma classificação binária. Agora imagine que o círculo verde representa uma nova instância, um novo par de números, para o qual precisamos determinar a qual classe ele pertence: se é um triângulo vermelho ou um quadrado azul.

Kit de Formação

O algoritmo de vizinho k-mais próximo é um algoritmo de classificação que diz que primeiro corrigimos o número de vizinhos (instâncias circundantes) k para um valor específico e, em seguida, determinamos quantos dos vizinhos k-mais próximos existem vermelhos e azuis: o vizinho vermelho é uma instância pertencente à classe vermelha e o vizinho azul é uma instância pertencente à classe azul. Por exemplo, se fixarmos o número k a 3, os três vizinhos mais próximos do círculo verde estão dentro de um círculo sólido. Existem dois triângulos vermelhos e um quadrado azul.

Além disso, o algoritmo do vizinho k-mais próximo diz que a nova instância, um novo par de pontos é adicionado à classe do vizinho mais numeroso: se os vizinhos vermelhos são mais numerosos, dizemos que a nova instância pertence à classe vermelha e, da mesma forma, se os vizinhos azuis são mais numerosos, dizemos que a nova instância pertence à classe azul. Também pode pensar nisso como o ditado "com quem você está, é como você é" no mundo da aprendizagem automática.

No nosso exemplo, quando o valor de k é fixado em 3, concluímos que devemos associar o círculo verde à classe vermelha porque temos dois vizinhos vermelhos e um vizinho azul.

Vamos ver o que acontece se corrigirmos o número k em 5. Na figura é mostrado por um círculo tracejado. Uma vez que existem agora três quadrados azuis e dois triângulos vermelhos, a conclusão seria que o círculo verde deveria ser unido à classe azul.

 Esta seção é emparelhada com o Exercício 8 e o Jupyter Notebook 08-k-nearest_neighbors.ipynb. Para acompanhar o conteúdo, clique no link e, em seguida, no botão para abrir o conteúdo no Google Collab. Se estiver visualizando os blocos de anotações em sua máquina local, localize o bloco de anotações com o mesmo nome entre os conteúdos e execute-o.

O material que o acompanha contém o conjunto de pontos acima mencionado e uma aplicação na qual pode examinar o que acontecerá se escolher um valor diferente do número k. Como o algoritmo precisa decidir quais vizinhos há mais, é sábio escolher valores ímpares do número k.

Note que além do número de vizinhos k, o resultado do algoritmo também depende de como medimos as distâncias para os vizinhos! Para encontrar os vizinhos mais próximos, precisamos de alguma forma medir a distância até eles.

Até agora, encontramos uma distância chamada distância euclidiana. A distância euclidiana entre os pontos \(A\) e \(B\) é calculada como o comprimento dos comprimentos que ligam os pontos \(A\) e \(B\). Por exemplo, para os pontos \(A =(0,0)\) e \(B =(3,4)\), a distância euclidiana é calculada como \(\sqrt{(3 − 0)^2 +(4 − 0)^2} = 5\)

Distância euclidiana

Há muitas outras distâncias também. Por exemplo, você pode ficar intrigado com a distância de Manhattan. Ao contrário da distância euclidiana, que calcula a "hipotenusa" de um triângulo definido pelos pontos \(A\) e \(B\) e \(O\) (se seguirmos a figura anterior), a distância de Manhattan calcula a soma das "pernas" deste triângulo. Para os pontos \(A\) e \(B\), o valor da distância de Manhattan seria \(| 3 − 0 | + | 4 − 0 | = 7\).

A distância que escolhemos depende da natureza da tarefa e do significado que os atributos com os quais estamos trabalhando têm. Em geral, podemos tentar mais distâncias e escolher aquela para a qual obtemos os melhores resultados. Falaremos sobre isso mais adiante. É importante notar que uma função deve satisfazer certas propriedades matemáticas para ser declarada uma distância, portanto, nem todas as funções podem ser úteis.

 Assim como outros algoritmos de aprendizagem automática, o algoritmo do vizinho mais próximo x é treinado sobre o conjunto de treinamento. É interessante notar que a fase de aprendizagem neste algoritmo é realmente reduzida ao armazenamento apenas do conjunto de dados. Em outros algoritmos, como a regressão linear ou a regressão logística, vimos que, nesta fase, os valores de alguns parâmetros que aparecem no modelo são calculados procurando a função de erro mínimo. O algoritmo do vizinho mais próximo de x não é assim. O mapeamento que aprendemos Não é sobre uma função específica, é sobre os dados em si e as etapas que precisam ser tomadas. É por isso que é comum chamar modelos que possuem essa propriedade de modelos não paramétricos.

O algoritmo k-nearest neighbor executa todo o trabalho durante o aplicativo, ou seja, decide a qual classe a nova instância pertence. Quando precisamos classificar uma nova instância, primeiro calculamos a distância da nova instância de todas as instâncias no conjunto de dados de treinamento. Em seguida, classificamos essas distâncias do menor para o maior. Mantemos as primeiras distâncias k (porque são as distâncias para k vizinhos mais próximos) e escolhemos instâncias do conjunto de treino a que se referem. Continuamos a monitorizar o que está a acontecer no espaço dos seus marcos e procuramos os marcos mais numerosos, ou seja, a maior classe. Como vimos no exemplo introdutório, a nova instância deve ser associada à classe que é mais numerosa.

Este algoritmo é fácil de implementar, por isso vamos arregaçar as mangas e começar!

Vamos imaginar que estamos trabalhando com um conjunto de dados que usamos até agora e que cada instância tem um formulário \((x1, x2, mark)\) onde \(mark\) é o valor 0 para vermelho ou 1 para azul.

Para medir a distância entre instâncias, usaremos a função euklidsko_rastojanje, que é definida pelo seguinte bloco de código:

def euclidean_distance(instance1, instance2):
  return np.sqrt((instance1[0]-instance2[0])**2 + (instance1[1]-instance2[1])**2)

O algoritmo do vizinho mais próximo x em si é representado pelo seguinte bloco de código:

def kNN(k, instances, new_instance, classes={0: 'red', 1: 'blue'}):

  # first, calculate the distances between the new instance and all instances in the dataset
  distances = [euclidean_distance(instance, new_instance) for instance in instances]

  # then sort the distances, extract the k smallest ones and the corresponding instances
  # declare them as neighbors
  neighbors = np.argsort(distances)[0:k]

  # then read the labels of the neighbors and count them
  neighbor_labels = [instances[neighbor][2] for neighbor in neighbors]
  label_counts = np.bincount(neighbor_labels)

  # the label of the new instance will be the label of the most frequent neighbor
  label = np.argmax(label_counts)

  return classes[label]

Nele, como já discutimos, realizamos as seguintes etapas:

1. Calculamos a distância da nova instância para todas as instâncias no conjunto de dados.
2. E então nós os colocamos no meio da noite, e então os colocamos no escuro.
3. E somos nós que temos o direito de ser os vizinhos.
4. No conjunto de vizinhos isolados, contamos os mais numerosos,
5. Concluímos que a nova instância pertence à classe do vizinho mais numeroso.

Ainda temos que aprender a escolher o melhor valor do número k. Falaremos sobre isso na próxima lição.

Show answer

Show answer