O kNN é um dos algoritmos mais intuitivos de machine learning e também um dos mais versáteis. Suas aplicações são vastas e se espalham desde o setor de saúde até o setor financeiro. Entre alguns de seus usos importantes estão a implementação de sistemas de recomendação, reconhecimento de padrões, mineração de dados e previsões do mercado financeiro.
Do ponto de vista técnico, o kNN é um algoritmo de aprendizagem supervisionada muito adequado para extrair padrões não-lineares de dados. Além disso, ele pode ser usado em tarefas de regressão e classificação.
O kNN se baseia na ideia de que é possível prever as características de um ponto de dados com base nas características de seus vizinhos. Embora ele possa ser usado para problemas de regressão ou classificação, normalmente ele é usado como um algoritmo de classificação.
O algoritmo
A base do funcionamento do kNN é bastante intuitiva. Ele parte do pressuposto de que pontos semelhantes são encontrados próximos uns dos outros. O algoritmo kNN opera medindo a similaridade entre pontos de dados usando uma métrica de distância como distância euclidiana ou de Manhattan.
Para problemas de classificação, o kNN classifica um ponto-alvo como pertencente a classe que predomina entre seus vizinhos mais próximos. Ou seja, os k vizinhos atuam como influenciadores de decisão, determinando a classificação de dados-alvo a partir da inteligência coletiva. A letra k se refere ao número de pontos vizinhos considerados e é um parâmetro que impacta bastante na precisão da classificação.
O algoritmo kNN classifica um dado-alvo, a estrela na figura, a partir da identificação da classe majoritária de seus vizinhos mais próximos.
Uma peculiaridade do kNN é que as distâncias entre vizinhos só são calculadas quando é necessário fazer uma previsão. Ou seja, o kNN faz parte de uma família de modelos de “aprendizado lento”, o que significa que ele armazena apenas um conjunto de dados de treinamento em vez de passar por um estágio de treinamento. Isto implica que todo o cálculo ocorre quando uma classificação ou previsão está sendo feita. Uma consequência negativa desse processo é que, à medida que o conjunto de dados cresce, o kNN torna-se cada vez mais ineficiente.
Um exemplo ilustrativo
Para ilustrar como o kNN opera na prática, utilizaremos o exemplo da criação de um pequeno sistema de recomendações. Considere a imagem abaixo. Cada eixo representa a classificação de um filme de acordo com diferentes espectadores.
O objetivo num sistema de recomendações com o kNN é identificar com quais vizinhos o indivíduo-alvo X é mais parecido a partir das notas que todos eles atribuíram aos filmes. Para isso, é necessário calcular as distâncias entre X e os outros pontos. Com a identificação dos pontos mais próximo, é possível fazer recomendações considerando os filmes que esses pontos assistiram e gostaram, mas X não assistiu ainda.
Implementação de um sistema de recomendação com kNN no Python
Agora vamos entender o kNN na prática. Para isso, vamos criar um sistema de recomendação no Python. Esse exemplo considera uma lista de clientes de uma loja de discos que avaliaram vários artistas. Veja o dicionário abaixo:
clientes = {"Angélica": {"Blues Traveler": 3.0, "Broken Bells": 2.0, "Phoenix": 5.0, "Slightly Stoopid": 1.5,"The Strokes": 2.5, "Vampire Weekend": 2.0},
"Rodrigo": {"Blues Traveler": 2.0, "Broken Bells": 3.5, "Deadmau5": 4.0, "Phoenix": 2.0, "Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
"Lucas": {"Blues Traveler": 5.0, "Broken Bells": 1.0, "Deadmau5": 1.0, "Norah Jones": 3.0, "Phoenix": 5, "Slightly Stoopid": 1.0},
"Daniel": {"Blues Traveler": 3.0, "Broken Bells": 4.0, "Deadmau5": 4.5, "Phoenix": 3.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 2.0},
"Maria": {"Broken Bells": 4.0, "Deadmau5": 1.0, "Norah Jones": 4.0, "The Strokes": 4.0, "Vampire Weekend": 1.0},
"Luciana": {"Broken Bells": 4.5, "Deadmau5": 4.0, "Norah Jones": 5.0, "Phoenix": 5.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 4.0},
"Sandra": {"Blues Traveler": 5.0, "Broken Bells": 2.0, "Norah Jones": 3.0, "Phoenix": 5.0, "Slightly Stoopid": 4.0, "The Strokes": 5.0},
"Verônica": {"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0, "Slightly Stoopid": 2.5, "The Strokes": 3.0}
}
Esse dicionário contém os nomes de vários clientes com as notas que eles atribuíram para diferentes artistas. É possível verificar as notas que um cliente deu digitando clientes[“nome_cliente”] como no exemplo abaixo.
print(clientes["Daniel"])
Iremos utilizar esse dicionário para criar um pequeno sistema de recomendações com o kNN.
Para implementar o kNN, é necessário criar uma função para calcular as distâncias de um cliente em relação aos demais. Usaremos uma função que calcula a distância de Manhattan entre dois clientes. Nessa função, a somatória das diferenças entre as notas que dois clientes deram para os mesmos produtos são usadas para computar a distância entre eles.
def manhattan(nota1, nota2):
"""Computa a distância de Manhattan distance. Ambos os argumentos nota1 and nota2 são
dicionários na forma {'The Strokes': 3.0, 'Slightly Stoopid': 2.5 ..."""
distancia = 0
for key in nota1:
if key in nota2: # precisa verificar se dois clientes avaliaram o mesmo produto
distancia += abs(nota1[key] - nota2[key])
return distancia
Vamos executar a função com dois clientes como exemplo.
distancia = manhattan(clientes['Lucas'], clientes['Sandra'])
Para esse exemplo, a distância calculada é 4.0.
Em seguida, é preciso fazer uma função (calcula_NN) para calculas a distância de um indivíduo-alvo em relação a todos os outros pontos. A função irá retornar uma lista ordenada com o vizinho mais próximo em primeiro lugar.
def calcula_NN(nome, clientes):
"""cria uma lista ordenada de clientes baseada na distância para um cliente-alvo"""
distancias = []
for cliente in clientes:
if cliente != nome:
distancia = manhattan(clientes[cliente], clientes[nome])
distancias.append((distancia, cliente))
distancias.sort()
return distancias
Vamos executar um exemplo usando a cliente Angélica para identificar sua proximidade em relação aos outros clientes.
distancias = calcula_NN("Angélica", clientes)
O resultado obtido é mostrado abaixo. Ele indica que a cliente Verônica é a mais parecida com a Angélica. Já a cliente Luciana é a que tem o gosto mais diferente.
[(2.5, 'Verônica'), (3.5, 'Lucas'), (4.5, 'Maria'), (7.0, 'Sandra'), (8.5, 'Daniel'), (8.5, 'Rodrigo'), (9.0, 'Luciana')]
Com esse cálculo, é possível agora fazer recomendações. Para isso, utilizaremos a função recomenda que é mostrada abaixo. Ela usará os vizinhos mais próximo de um cliente-alvo para verificar produtos que um desses vizinhos gostou e nosso alvo não conhece ainda.
def recomenda(nome, clientes):
"""Give list of recommendations"""
nearest = calcula_NN(nome, clientes)[0][1]
recomendacoes = []
# acha produtos que os vizinhos gostaram e que o alvo não conhece
vizinhoNotas = clientes[nearest]
nomeNotas = clientes[nome]
for artista in vizinhoNotas:
if not artista in nomeNotas:
recomendacoes.append((artista, vizinhoNotas[artista]))
print(recomendacoes)
return sorted(recomendacoes, key=lambda artistTuple: artistTuple[1], reverse = True)
Vamos testar a função para a cliente Angélica. Ela irá retornar uma sugestão de produtos baseada em produtos que um de seus vizinhos mais próximos tenha gostado, mas que ela ainda não conhece. Para chamar a função digite o código:
recomenda("Angélica", clientes)
A recomendação sugerida é mostrada baixo.
[('Norah Jones', 5.0)]
Esse código foi baseado num exemplo publicado no livro Numerati – A Programmer’s Guide to Data Mining.
Conclusões
Neste post, apresentamos um pouco sobre o kNN, um algoritmo de fácil implementação e bastante versátil. Fizemos uma pequena implementação no Python, mas ele também pode ser implementado com bibliotecas como scikit-learn.
Em que projetos você pode usar esse algoritmo? O kNN é usado para sistemas de recomendações, trading, filtros de e-mails e muitas outras aplicações.
