O K-Nearest Neighbors (KNN) é um dos algoritmos mais simples de classificação da aprendizagem de máquina. Uma nova entrada é classificada de acordo com os exemplos dos dados de treinamento que são mais parecidos com ela, ou seja, que estão mais próximos num espaço n-dimensional de atributos.
Para começar, vamos carregar os dados que usaremos em toda a explicação.
from sklearn import datasets
iris_data = datasets.load_iris()
Neste dataset temos dados sobre flores. Os atributos são:
iris_data.feature_names
['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']
Um pouco de biologia para entendermos o que é uma pétala (petal) e uma sépala (sepal)
from IPython.core.display import Image
Image(filename='flower_parts.jpg')
O dataset contém dados de 150 flores com 4 atributos para cada flor:
iris_data.data.shape
(150, 4)
Vejamos os valores das 10 primeiras flores:
iris_data.data[:10]
array([[ 5.1, 3.5, 1.4, 0.2], [ 4.9, 3. , 1.4, 0.2], [ 4.7, 3.2, 1.3, 0.2], [ 4.6, 3.1, 1.5, 0.2], [ 5. , 3.6, 1.4, 0.2], [ 5.4, 3.9, 1.7, 0.4], [ 4.6, 3.4, 1.4, 0.3], [ 5. , 3.4, 1.5, 0.2], [ 4.4, 2.9, 1.4, 0.2], [ 4.9, 3.1, 1.5, 0.1]])
Cada linha na matriz representa uma flor, e para cada flor temos os seus quatro atributos.
Por exemplo, na primeira linha temos:
No dataset existem três classificações (rótulos) possíveis para as flores: 0, 1 e 2
iris_data.target
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2])
Se você quiser saber qual o rótulo da primeira linha dos dados (iris_data.data) basta acessar a primeira posição do iris_data.target. Se quiser saber o rótulo da segunda linha dos dados é só acessar a segunda posição e assim por diante.
Vamos plotar os dados num gráfico para visualizarmos a distribuição dos tipos de flores de acordo com seus atributos. Como temos um espaço de 4 dimensões (uma dimensão para cada atributo) foi escolhido apenas as colunas 2 e 3 da matriz para o gráfico abaixo.
plt.scatter(iris_data.data[:,2], iris_data.data[:,3], c=iris_data.target);
É possível perceber que existe uma organização nos dados e que nosso classificador deverá funcionar muito bem. Existe um grupo azul no canto inferior esquerdo, os verdes estão no centro, e o grupo marrom está mais afastado para o canto superior direito.
Para avaliarmos a nossa implementação do KNN, vamos usar validação cruzada dos dados. 30% dos dados carregados serão usados para teste e 70% para treinamento.
No exemplo abaixo, data_train são os dados de treinamento, target_train são os rótulos para os dados de treinamento, data_test são os dados de teste e target_test são os rótulos para os dados de teste.
from sklearn import cross_validation
data_train, data_test, target_train, target_test = \
cross_validation.train_test_split(iris_data.data, iris_data.target, test_size=0.3, random_state=0)
Vejamos quantos exemplos tem cada conjunto de dados:
len(data_train), len(data_test)
(105, 45)
No KNN, para cada exemplo no conjunto de testes, nós vamos calcular a distância para todos os exemplos do conjunto de treinamento. Em seguida, atribuiremos como rótulo do exemplo de teste o rótulo da maioria dos K exemplos mais próximos a ele.
De forma mais concreta, supondo um exemplo de teste X e três exemplos de treinamento: Y1 com rótulo 0, Y2 também com rótulo 0 e Y3 com rótulo 1, que são os três exemplos mais próximos de X, e que K=3. Dessa forma, a classificação do ponto X será 0, pois dos 3 exemplos mais próximos (já que K=3), dois possuem rótulo 0 e apenas um possui rótulo 1.
Vamos agora classificar a primeira linha dos dados de teste (data_test).
row = data_test[0]
row
array([ 5.8, 2.8, 5.1, 2.4])
Precisamos calcular a distância desse ponto para todos os outros dos dados de treinamento
from scipy.spatial.distance import euclidean
# para cada ponto em data_train (x), calcule a sua distância euclidiana para o ponto de teste (row)
distances = np.fromiter((euclidean(row, x) for x in data_train), np.float)
distances
array([ 2.40831892, 1.02469508, 1.19582607, 1.1045361 , 1.32287566, 1.80554701, 2.15870331, 1.14017543, 1.90525589, 0.81240384, 1.02956301, 1.32287566, 0.77459667, 1.66132477, 0.83666003, 1.18321596, 4.26380112, 0.50990195, 1.43874946, 1.8734994 , 1.61245155, 1.17473401, 1.81383571, 4.34281015, 4.85592422, 0.81240384, 1.51657509, 4.11339276, 4.41927596, 1.46628783, 4.39658959, 0.64031242, 2.5845696 , 4.4609416 , 1.3 , 1.9 , 1.42828569, 4.47437146, 1.56843871, 1.3190906 , 1.02956301, 0.83666003, 4.31045241, 4.29534632, 0.9 , 1.22882057, 4.55960525, 0.78740079, 4.40227214, 0.51961524, 1.21655251, 4.6260134 , 4.45084262, 1.7691806 , 4.36806593, 4.61302504, 4.11460812, 1.66132477, 1.3453624 , 2.37065392, 4.41701257, 4.3760713 , 4.38748219, 1.25698051, 1.47309199, 4.56618002, 3.98873414, 1.48996644, 4.18090899, 2.62678511, 2.48394847, 2.69443872, 1.54596248, 4.50555213, 0.72801099, 4.63573079, 2.51594913, 4.34281015, 4.29651021, 1.95192213, 4.40681291, 0.92736185, 1.48996644, 1.7 , 2.13775583, 0.75498344, 0.93273791, 1.09087121, 1.161895 , 4.21544778, 2.04205779, 1.07238053, 0.50990195, 4.31856458, 1.4525839 , 1.5132746 , 0.78740079, 1.4832397 , 4.45645599, 4.27317212, 4.3760713 , 0.93273791, 1.72336879, 2.68514432, 4.48664685])
Em seguida vamos descobrir em quais índices estão os menores elementos.
rank = distances.argsort()
rank
array([ 92, 17, 49, 31, 74, 85, 12, 96, 47, 9, 25, 14, 41, 44, 81, 101, 86, 1, 10, 40, 91, 87, 3, 7, 88, 21, 15, 2, 50, 45, 63, 34, 39, 11, 4, 58, 36, 18, 94, 29, 64, 97, 82, 67, 95, 26, 72, 38, 20, 57, 13, 83, 102, 53, 5, 22, 19, 35, 8, 79, 90, 84, 6, 59, 0, 70, 76, 32, 69, 103, 71, 66, 27, 56, 68, 89, 16, 99, 43, 78, 42, 93, 23, 77, 54, 100, 61, 62, 30, 48, 80, 60, 28, 52, 98, 33, 37, 104, 73, 46, 65, 55, 51, 75, 24])
Nesse caso, a posição 92 do array distances tem o menor elemento, a posiçao 17 tem o segundo menor elemento e assim por diante.
Com isso podemos concluir que o ponto da linha 92 nos dados de treinamento é o ponto mais próximo do ponto de teste.
Vamos usar K=5 e pegar as 5 menores distâncias:
K=5
closer = rank[:K]
closer
array([92, 17, 49, 31, 74])
Como cada distância do array distances corresponde a uma flor nos dados de treinamento (data_train). E, cada linha de data_train tem o seu rótulo em target_train. Se acessarmos a posição 92 de target_train, estaremos acessando o rótulo do ponto de menor distância para a linha de teste que estamos usando.
closer_labels = target_train.take(closer)
closer_labels
array([2, 2, 2, 2, 2])
Podemos perceber facilmente que o exemplo de teste será rotulado como 2, já que todos os pontos mais próximos também são do tipo 2.
Vamos verificar se nossa resposta está correta.
target_test[0]
2
Acertou :)