#!/usr/bin/env python
# coding: utf-8

# # K-Nearest Neighbors (KNN)

# 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.

# In[2]:


from sklearn import datasets

iris_data = datasets.load_iris()


# Neste dataset temos dados sobre flores. Os atributos são:

# In[3]:


iris_data.feature_names


# Um pouco de biologia para entendermos o que é uma pétala (petal) e uma sépala (sepal)

# In[4]:


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:

# In[6]:


iris_data.data.shape


# Vejamos os valores das 10 primeiras flores:

# In[7]:


iris_data.data[:10]


# Cada linha na matriz representa uma flor, e para cada flor temos os seus quatro atributos.
# 
# Por exemplo, na primeira linha temos:
# 
# - sepal length (cm): 5.1
# - sepal width (cm): 3.5
# - petal length (cm): 1.4
# - petal width (cm): 0.2

# No dataset existem três classificações (rótulos) possíveis para as flores: 0, 1 e 2

# In[5]:


iris_data.target


# 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.

# In[8]:


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.

# In[9]:


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:

# In[11]:


len(data_train), len(data_test)


# 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).

# In[9]:


row = data_test[0]


# In[10]:


row


# Precisamos calcular a distância desse ponto para todos os outros dos dados de treinamento

# In[11]:


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)


# In[12]:


distances


# Em seguida vamos descobrir em quais índices estão os menores elementos.

# In[13]:


rank = distances.argsort()


# In[14]:


rank


# 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:

# In[15]:


K=5
closer = rank[:K]


# In[16]:


closer


# 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.

# In[17]:


closer_labels = target_train.take(closer)


# In[18]:


closer_labels


# 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.

# In[19]:


target_test[0]


# Acertou :)