Da mesma forma que podemos classificar modelos como _supervisionados_ ou _não-supervisionados_, podemos classificar modelos como **paramétricos** ou **não-paramétricos**
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.
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:
Assim o KNN efetivamente divide o espaço de features com uma granularidade K
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.
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.
A escolha de K nos coloca em um ponto entre o mínimo e o máximo de generalização.
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.
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)
In [6]:
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))
2) Agora criaremos uma função que calcula a distância entre cada item do gabarito e um item novo a ser julgado
In [4]:
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]))
3) Uma vez que temos os vizinhos mais próximos, precisamos contar a classe de cada um, para saber o que responder
In [5]:
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]
agora vamos brincar...
In [42]:
#############################################################
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)
In [ ]:
In [ ]: