O que é o algoritmo k-vizinhos mais próximos (kNN)?

kNN (k-vizinhos mais próximos) é um método não paramétrico usado para classificação e regressão. A ideia é simples: um objeto é classificado pela maioria dos votos de seus vizinhos, onde o objeto é atribuído à classe mais comum entre seus k vizinhos mais próximos. Para regressão, o valor médio das etiquetas dos k vizinhos mais próximos é previsto.

Aspectos-chave:

• Parâmetro k: Número de vizinhos considerados na decisão. A escolha de k influencia bastante o resultado. Um k pequeno pode ser sensível ao ruído, um k grande pode ignorar estruturas locais.
• Métrica de distância: Usada para determinar a "proximidade" entre pontos de dados. As mais comuns são: distância euclidiana, distância de Manhattan.
• Características:
  • Algoritmo "preguiçoso": não há ou há mínimo de treinamento (simplesmente armazenar os dados de treinamento). A previsão ocorre apenas na consulta.
  • Fácil de implementar e entender.
  • O desempenho na fase de previsão pode diminuir com conjuntos de dados grandes, pois requer calcular distâncias para todos os exemplos de treinamento.
  • Sensível à escala das características.
  • Pode não funcionar bem com dados com alto nível de ruído.

Etapas do processo (para classificação):

1. Escolher o valor de k.
2. Escolher a métrica de distância.
3. Para um novo objeto, para o qual se deseja fazer uma previsão: a. Calcular a distância entre este objeto e todos os objetos do conjunto de treinamento. b. Selecionar os k objetos mais próximos do conjunto de treinamento. c. Determinar a classe que aparece com maior frequência entre esses k objetos. d. Atribuir essa classe ao novo objeto.

Exemplo (pseudo-código):

# Função para calcular a distância euclidiana
def euclidean_distance(p1, p2):
    # ... cálculo da distância ...

# Função para buscar os k vizinhos mais próximos e prever a classe
def predict(training_data, new_data_point, k, distance_metric):
    distances = []
    for data_point in training_data:
        dist = distance_metric(new_data_point, data_point['features'])
        distances.append((dist, data_point['label']))

    # Ordenar por distância e selecionar os k mais próximos
    distances.sort(key=lambda x: x[0])
    k_nearest = distances[:k]

    # Contar votos de classes
    class_votes = {}
    for dist, label in k_nearest:
        class_votes[label] = class_votes.get(label, 0) + 1

    # Determinar a classe com mais votos
    predicted_class = max(class_votes, key=class_votes.get)
    return predicted_class