<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 <h1><center>K-Nearest Neighbors<center></h1>
<p>Da mesma forma que podemos classificar modelos como _supervisionados_ ou _não-supervisionados_, podemos classificar modelos como **paramétricos** ou **não-paramétricos**</p>
<p>Os paramétricos têm um número fixo de paramêtros, e em geral são mais rápidos, mas fazem suposições mais fortes sobre a natureza dos dados e sua distribuição. Por outro lado, nos modelos não-paramétricos, o número de variáveis cresce com a quantidade de dados.<p>
Veremos aqui, como exemplo de um modelo não-paramétrico, um classificador chamado __K-Nearest Neighbors__ (KNN). O seu algoritmo é bem simples
Step1:  2) Agora criaremos uma função que calcula a distância entre cada item do gabarito e um item novo a ser julgado
Step2:  3) Uma vez que temos os vizinhos mais próximos, precisamos contar a classe de cada um, para saber o que responder
Step3:  agora vamos brincar...
<ASSISTANT_TASK:>
Python Code:
import math
#####################################################################################
# d = sqrt((a1-b1)^2 + (a2-b2)^2+(a3-b3)^2+(a4-b4)^2)
#####################################################################################
def euclidean_dist(data1, data2):
    
    # transformo [a1,a2,...,an] e [b1,b2,...,bn] em (a1,b1),(a2,b2),...(an,bn)
    points = zip(data1, data2)
    
    # quadrado das diferenças, dimensão por dimensão
    diffs_squared_distance = [pow(a - b, 2) for (a, b) in points if a is not None and b is not None]
    # retorno a raiz da soma
    return math.sqrt(sum(diffs_squared_distance))
Explanation: <h1><center>K-Nearest Neighbors<center></h1>
<p>Da mesma forma que podemos classificar modelos como _supervisionados_ ou _não-supervisionados_, podemos classificar modelos como **paramétricos** ou **não-paramétricos**</p>
<p>Os paramétricos têm um número fixo de paramêtros, e em geral são mais rápidos, mas fazem suposições mais fortes sobre a natureza dos dados e sua distribuição. Por outro lado, nos modelos não-paramétricos, o número de variáveis cresce com a quantidade de dados.<p>
Veremos aqui, como exemplo de um modelo não-paramétrico, um classificador chamado __K-Nearest Neighbors__ (KNN). O seu algoritmo é bem simples: compare o novo dado $X$ a ser classificado com os **K** pontos mais 'próximos' (há que se definir o que isso significa) e atribua a classe mais provável (a classe da maioria dos K comparados).
Formalizando: $$p(y=c|x,\mathcal{D},K) = \frac{1}{K}\sum_{i \in  N_{K}(x,\mathcal{D})} \mathbb{I}(y_{i}=c)$$
Onde $N_{k}(x,\mathcal{D})$ calcula os índices dos K vizinhos mais próximos a $x$, e $\mathbb{I}$ é **função indicador**:<br>
$$\mathbb{I}(e)=\left\{ \begin{array}{ll}
                  1 & \text{se $e$ é verdadeiro}\\
                  0 & \text{if $e$ é falso}
                \end{array}
              \right.$$
Assim o KNN efetivamente **divide** o espaço de _features_ com uma granularidade **K**
<br>
se K=1, o modelo terá erro zero ao treinar (visto que apenas retornamos os pontos originais de treino), mas terá muito pouco valor explicativo ao ser utilizado.
<br>
Ao aumentar K, as divisões do espaço vão ficando mais suaves, até que em K=N, é um classificador que chuta sempre a classe majoritária da massa de dados.
<br>
A escolha de K nos coloca em um ponto entre o mínimo e o máximo de generalização.
<h4>No Free Lunch Theorem</h4>
Cunhado por Wolpert (1966), diz que não há um único modelo que dê resultados ótimos para todo tipo de problema. Um conjunto de pressupostos que dão resultado bom para um problema podem não funcionar bem em outro (ou com outros dados). Assim, diferentes modelos são criados em resposta a diferentes problemas e dados do mundo real, e diferentes algoritmos podem ser usados para treinar cada modelo, que por sua vez terão diferentes desempehos nas dimensões **velocidade-acurácia-precisão**. 
<h4>Código</h4>
1) para calcular a proximidade entre os pontos, preciso de uma métrica de distância exitem várias: Jaccard, City-Block, Coseno ...para começar podemos usar a Euclideana:
para dois vetores de _features_: $X=(x_1,x_2,...,x_n)$ e $Y=(y_1,y_2,...,y_n)$
$$ d=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+...+(x_n-y_n)^2}$$
OBS: Vale observar que valores nominais não darão certo com esta escolha de métrica ...como resolver? 
(dummy coding, Jaccard)
End of explanation
from operator import itemgetter
#####################################################################################
# olho os vizinhos 1 a 1 e guardo os k mais próximos
#####################################################################################
def get_neighbours(training_set, test_instance, k):
    
    # calculo a distância do item a ser julgado de cada outro ponto
    # distances tem a forma: [(item1,d1), (item2,d2), ...]
    # onde d1 é a distância entre item1 e test_instance, 
    #      d2 é a distância entre item2 e test_instance ...e assim por diante
    distances = [_get_tuple_distance(training_instance, test_instance) for training_instance in training_set]
 
    # reordeno a lista de items da menor distância para a maior
    sorted_distances = sorted(distances, key=itemgetter(1))
 
    # não guardo as distâncias, só os items, uma vez ordenados
    sorted_training_instances = [x[0] for x in sorted_distances]
 
    # retorno os primeiros k items da lista ordenada
    return sorted_training_instances[:k]
#####################################################################################
# aplico a minha função de distância entre dois itens.
#####################################################################################
def _get_tuple_distance(training_instance, test_instance):
    return (training_instance, euclidean_dist(test_instance, training_instance[0]))
Explanation: 2) Agora criaremos uma função que calcula a distância entre cada item do gabarito e um item novo a ser julgado
End of explanation
from collections import Counter
 
def get_majority_vote(neighbours):
    # presumo aqui que a neighbours tem o formato 
    # [(item,classe), (item,classe)...]
    classes = [neighbour[1] for neighbour in neighbours]
    count = Counter(classes)
    return count.most_common()[0][0]
Explanation: 3) Uma vez que temos os vizinhos mais próximos, precisamos contar a classe de cada um, para saber o que responder
End of explanation
#############################################################
def run(dataset, item, K):
    neighbours = get_neighbours(dataset, item, K)
    guess = get_majority_vote(neighbours)
    print 'I think this guy likes:',guess
#############################################################    
def generate_random_data():
    for _ in range(30):
        item = []
        for i in range(10):
            item.append(random.randint(1,5))
        
        bucket = ''   
        cl = random.randint(0,8)
        if cl < 3: bucket = 'action'
        elif cl < 6: bucket = 'drama'
        else: bucket = 'comedy'
        data.append( (item,bucket) )
    print data
#############################################################
import random
if __name__ == '__main__':
    # generate_random_data()
    K = 5
    data = [([4, 2, 5, 3, 3, 3, 5, 3, 4, 2], 'action'), 
            ([5, 3, 4, 2, 2, 5, 5, 2, 3, 2], 'comedy'), 
            ([2, 5, 3, 3, 4, 4, 5, 1, 3, 5], 'action'), 
            ([1, 3, 3, 5, 3, 1, 2, 5, 1, 3], 'action'), 
            ([5, 3, 2, 4, 3, 1, 4, 3, 3, 4], 'drama'), 
            ([5, 5, 1, 3, 1, 3, 3, 4, 3, 3], 'action'), 
            ([1, 2, 3, 3, 2, 3, 2, 3, 5, 4], 'drama'), 
            ([3, 5, 1, 3, 4, 1, 4, 2, 3, 4], 'drama'), 
            ([1, 1, 1, 2, 1, 3, 3, 4, 5, 1], 'comedy'), 
            ([5, 3, 4, 2, 5, 2, 4, 1, 3, 2], 'comedy'), 
            ([4, 2, 3, 5, 1, 3, 1, 5, 3, 5], 'drama'), 
            ([1, 2, 3, 1, 3, 2, 4, 4, 4, 5], 'drama'), 
            ([3, 2, 1, 1, 2, 3, 1, 4, 2, 4], 'comedy'), 
            ([4, 5, 5, 3, 5, 3, 5, 1, 3, 4], 'drama'), 
            ([4, 4, 3, 3, 3, 2, 1, 5, 3, 4], 'comedy'), 
            ([4, 1, 2, 5, 4, 4, 5, 4, 1, 4], 'comedy'), 
            ([2, 2, 1, 3, 1, 5, 1, 3, 5, 1], 'comedy'), 
            ([2, 3, 1, 1, 2, 5, 2, 2, 4, 2], 'comedy'), 
            ([5, 2, 2, 4, 5, 3, 4, 5, 4, 2], 'comedy'), 
            ([1, 1, 4, 4, 2, 2, 4, 4, 3, 1], 'comedy'), 
            ([3, 3, 2, 2, 5, 1, 5, 3, 5, 2], 'comedy'), 
            ([5, 4, 1, 2, 1, 5, 1, 5, 1, 5], 'comedy'), 
            ([4, 1, 5, 5, 1, 3, 1, 5, 4, 1], 'comedy'), 
            ([3, 4, 2, 1, 1, 2, 5, 4, 3, 5], 'action'), 
            ([4, 5, 2, 1, 1, 1, 1, 2, 2, 2], 'drama'), 
            ([3, 3, 1, 5, 1, 1, 5, 2, 1, 2], 'action'), 
            ([1, 5, 2, 4, 1, 2, 1, 2, 3, 2], 'drama'), 
            ([5, 3, 3, 5, 1, 3, 1, 2, 1, 3], 'drama'), 
            ([1, 1, 4, 4, 4, 5, 2, 2, 1, 5], 'action'), 
            ([3, 1, 5, 2, 1, 1, 5, 1, 5, 1], 'drama'), 
            ([4, 2, 3, 4, 3, 2, 5, 4, 1, 3], 'comedy'), 
            ([3, 2, 5, 3, 2, 4, 2, 2, 5, 4], 'drama'), 
            ([1, 3, 1, 2, 5, 4, 2, 4, 4, 3], 'action'), 
            ([4, 3, 4, 5, 1, 2, 2, 1, 1, 2], 'drama'), 
            ([3, 3, 3, 1, 4, 3, 5, 2, 4, 5], 'action'), 
            ([2, 5, 1, 2, 3, 3, 1, 3, 5, 1], 'action'), 
            ([2, 4, 2, 1, 4, 2, 2, 4, 1, 1], 'action'), 
            ([3, 2, 3, 3, 3, 3, 4, 2, 2, 1], 'comedy'), 
            ([2, 5, 1, 5, 2, 5, 1, 1, 4, 5], 'action'), 
            ([5, 2, 4, 1, 2, 5, 5, 3, 3, 4], 'comedy'), 
            ([3, 5, 1, 3, 3, 5, 2, 1, 3, 1], 'action'), 
            ([4, 1, 4, 1, 5, 2, 3, 5, 5, 3], 'drama'), 
            ([3, 4, 2, 2, 4, 2, 1, 4, 1, 5], 'drama'), 
            ([3, 3, 5, 3, 3, 3, 3, 4, 1, 4], 'comedy'), 
            ([2, 3, 2, 1, 3, 1, 3, 2, 1, 4], 'comedy'), 
            ([3, 5, 1, 1, 2, 4, 1, 5, 1, 2], 'comedy'), 
            ([2, 2, 4, 1, 3, 4, 2, 3, 3, 5], 'comedy'), 
            ([5, 3, 4, 5, 1, 5, 2, 4, 1, 1], 'drama'), 
            ([4, 2, 5, 2, 3, 1, 2, 3, 2, 2], 'action'), 
            ([1, 3, 3, 5, 3, 3, 2, 5, 4, 2], 'drama'), 
            ([3, 4, 2, 1, 4, 2, 1, 4, 1, 3], 'drama'), 
            ([3, 1, 3, 4, 5, 5, 5, 2, 1, 3], 'drama'), 
            ([4, 4, 4, 2, 2, 1, 1, 2, 2, 1], 'action'), 
            ([1, 3, 3, 4, 4, 4, 3, 5, 1, 2], 'drama'), 
            ([3, 3, 3, 3, 2, 2, 1, 5, 5, 4], 'comedy'), 
            ([2, 5, 4, 2, 4, 1, 2, 4, 1, 5], 'drama'), 
            ([3, 1, 1, 1, 5, 1, 2, 3, 1, 1], 'action'), 
            ([1, 3, 4, 3, 3, 2, 1, 4, 3, 5], 'action'), 
            ([3, 2, 3, 1, 4, 5, 4, 3, 5, 2], 'action'), 
            ([5, 1, 3, 2, 3, 2, 4, 3, 4, 2], 'action')
           ]
    
     
            
    run(data, [5,5,5,1,1,1,5,1,1,1], K)
Explanation: agora vamos brincar...
End of explanation
<END_TASK>