Pré-requisito: K mais próximo vizinhos 
 

janela.open javascript

Introdução

Digamos que recebamos um conjunto de dados de itens, cada um com características avaliadas numericamente (como Altura, Peso, Idade, etc.). Se a contagem de recursos for n podemos representar os itens como pontos em um n grade dimensional. Dado um novo item, podemos calcular a distância do item a todos os outros itens do conjunto. Nós escolhemos o k vizinhos mais próximos e vemos onde a maioria desses vizinhos está classificada. Classificamos o novo item lá.
Então o problema passa a ser como podemos calcular as distâncias entre os itens. A solução para isso depende do conjunto de dados. Se os valores forem reais normalmente usamos a distância euclidiana. Se os valores forem categóricos ou binários, normalmente usamos a distância de Hamming.
Algoritmo:  
 

Given a new item: 1. Find distances between new item and all other items 2. Pick k shorter distances 3. Pick the most common class in these k distances 4. That class is where we will classify the new item

Lendo dados

Deixe nosso arquivo de entrada estar no seguinte formato:
 

Height Weight Age Class 1.70 65 20 Programmer 1.90 85 33 Builder 1.78 76 31 Builder 1.73 74 24 Programmer 1.81 75 35 Builder 1.73 70 75 Scientist 1.80 71 63 Scientist 1.75 69 25 Programmer

Cada item é uma linha e em 'Classe' vemos onde o item está classificado. Os valores sob os nomes dos recursos ('Altura' etc.) são o valor que o item possui para aquele recurso. Todos os valores e recursos são separados por vírgulas.
Coloque esses arquivos de dados no diretório de trabalho dados2 e dados . Escolha um e cole o conteúdo como está em um arquivo de texto chamado dados .
Leremos o arquivo (chamado 'data.txt') e dividiremos a entrada por linhas:
 

f = open('data.txt' 'r'); lines = f.read().splitlines(); f.close();

A primeira linha do arquivo contém os nomes dos recursos com a palavra-chave ‘Class’ no final. Queremos armazenar os nomes dos recursos em uma lista:
 

# Split the first line by commas # remove the first element and # save the rest into a list. The # list now holds the feature # names of the data set. features = lines[0].split(' ')[:-1];

Em seguida, passamos para o conjunto de dados em si. Salvaremos os itens em uma lista chamada Unid cujos elementos são dicionários (um para cada item). As chaves para esses dicionários de itens são os nomes dos recursos mais 'Classe' para conter a classe do item. No final queremos embaralhar os itens da lista (esta é uma medida de segurança caso os itens estejam em uma ordem estranha). 
 

items = []; for i in range(1 len(lines)): line = lines[i].split(' '); itemFeatures = {'Class' : line[-1]}; # Iterate through the features for j in range(len(features)): # Get the feature at index j f = features[j]; # The first item in the line # is the class skip it v = float(line[j]); # Add feature to dict itemFeatures[f] = v; # Append temp dict to items items.append(itemFeatures); shuffle(items); 

Classificando os dados

Com os dados armazenados em Unid agora começamos a construir nosso classificador. Para o classificador criaremos uma nova função Classificar . Tomaremos como entrada o item que queremos classificar na lista de itens e k o número dos vizinhos mais próximos.
Se k for maior que o comprimento do conjunto de dados, não prosseguimos com a classificação, pois não podemos ter vizinhos mais próximos do que a quantidade total de itens no conjunto de dados. (alternativamente, poderíamos definir k como o Unid comprimento em vez de retornar uma mensagem de erro)
 

if(k > len(Items)): # k is larger than list # length abort return 'k larger than list length';

Queremos calcular a distância entre o item a ser classificado e todos os itens do conjunto de treinamento ao final mantendo a k distâncias mais curtas. Para manter os vizinhos mais próximos atuais, usamos uma lista chamada vizinhos . Cada elemento contém no mínimo dois valores, um para a distância do item a ser classificado e outro para a classe em que o vizinho está. Calcularemos a distância através da fórmula euclidiana generalizada (para n dimensões). Então escolheremos a classe que aparece na maior parte do tempo vizinhos e essa será a nossa escolha. No código: 
 

def Classify(nItem k Items): if(k > len(Items)): # k is larger than list # length abort return 'k larger than list length'; # Hold nearest neighbors. # First item is distance  # second class neighbors = []; for item in Items: # Find Euclidean Distance distance = EuclideanDistance(nItem item); # Update neighbors either adding # the current item in neighbors  # or not. neighbors = UpdateNeighbors(neighbors item distance k); # Count the number of each # class in neighbors count = CalculateNeighborsClass(neighbors k); # Find the max in count aka the # class with the most appearances. return FindMax(count); 

As funções externas que precisamos implementar são Distância Euclidiana Atualizar vizinhos CalcularNeighborsClass e Encontrar Max .
 

Encontrando a distância euclidiana

matemática java

A fórmula euclidiana generalizada para dois vetores x e y é esta: 

distance = sqrt{(x_{1}-y_{1})^2 + (x_{2}-y_{2})^2 + ... + (x_{n}-y_{n})^2}

No código: 

def EuclideanDistance(x y): # The sum of the squared  # differences of the elements S = 0; for key in x.keys(): S += math.pow(x[key]-y[key] 2); # The square root of the sum return math.sqrt(S); 

Atualizando vizinhos

Temos nossa lista de vizinhos (que deve ter no máximo k ) e queremos adicionar um item à lista com uma determinada distância. Primeiro vamos verificar se vizinhos tem um comprimento de k . Se tiver menos adicionamos o item independente da distância (pois precisamos preencher a lista até k antes de começarmos a rejeitar itens). Caso contrário, verificaremos se o item tem uma distância menor que o item com a distância máxima na lista. Se isso for verdade, substituiremos o item com distância máxima pelo novo item.
Para encontrar o item de distância máxima mais rapidamente manteremos a lista ordenada em ordem crescente. Portanto, o último item da lista terá a distância máxima. Iremos substituí-lo por um novo item e iremos classificá-lo novamente.
Para agilizar esse processo podemos implementar um Insertion Sort onde inserimos novos itens na lista sem ter que ordenar a lista inteira. O código para isso, porém, é bastante longo e, embora simples, atrapalhará o tutorial. 
 

def UpdateNeighbors(neighbors item distance k): if(len(neighbors) > distance): # If yes replace the last # element with new item neighbors[-1] = [distance item['Class']]; neighbors = sorted(neighbors); return neighbors; 

CalcularNeighborsClass

Aqui calcularemos a classe que aparece com mais frequência em vizinhos . Para isso usaremos outro dicionário chamado contar onde as chaves são os nomes das classes que aparecem em vizinhos . Se uma chave não existir, iremos adicioná-la, caso contrário, incrementaremos seu valor. 
 

def CalculateNeighborsClass(neighbors k): count = {}; for i in range(k): if(neighbors[i][1] not in count): # The class at the ith index # is not in the count dict. # Initialize it to 1. count[neighbors[i][1]] = 1; else: # Found another item of class  # c[i]. Increment its counter. count[neighbors[i][1]] += 1; return count; 

Encontrar Max

java para loop

Iremos inserir nesta função o dicionário contar nós construímos em CalcularNeighborsClass e retornaremos seu máximo.
 

def FindMax(countList): # Hold the max maximum = -1; # Hold the classification classification = ''; for key in countList.keys(): if(countList[key] > maximum): maximum = countList[key]; classification = key; return classification maximum; 

Conclusão

Com isso este tutorial do kNN está concluído.
Agora você pode classificar a configuração de novos itens k como achar melhor. Normalmente para k um número ímpar é usado, mas isso não é necessário. Para classificar um novo item é necessário criar um dicionário com chaves, os nomes dos recursos e os valores que caracterizam o item. Um exemplo de classificação:
 

newItem = {'Height' : 1.74 'Weight' : 67 'Age' : 22}; print Classify(newItem 3 items);

O código completo da abordagem acima é fornecido abaixo: - 
 

# Python Program to illustrate # KNN algorithm # For pow and sqrt import math from random import shuffle ###_Reading_### def ReadData(fileName): # Read the file splitting by lines f = open(fileName 'r') lines = f.read().splitlines() f.close() # Split the first line by commas  # remove the first element and save # the rest into a list. The list  # holds the feature names of the  # data set. features = lines[0].split(' ')[:-1] items = [] for i in range(1 len(lines)): line = lines[i].split(' ') itemFeatures = {'Class': line[-1]} for j in range(len(features)): # Get the feature at index j f = features[j] # Convert feature value to float v = float(line[j]) # Add feature value to dict itemFeatures[f] = v items.append(itemFeatures) shuffle(items) return items ###_Auxiliary Function_### def EuclideanDistance(x y): # The sum of the squared differences # of the elements S = 0 for key in x.keys(): S += math.pow(x[key] - y[key] 2) # The square root of the sum return math.sqrt(S) def CalculateNeighborsClass(neighbors k): count = {} for i in range(k): if neighbors[i][1] not in count: # The class at the ith index is # not in the count dict.  # Initialize it to 1. count[neighbors[i][1]] = 1 else: # Found another item of class  # c[i]. Increment its counter. count[neighbors[i][1]] += 1 return count def FindMax(Dict): # Find max in dictionary return  # max value and max index maximum = -1 classification = '' for key in Dict.keys(): if Dict[key] > maximum: maximum = Dict[key] classification = key return (classification maximum) ###_Core Functions_### def Classify(nItem k Items): # Hold nearest neighbours. First item # is distance second class neighbors = [] for item in Items: # Find Euclidean Distance distance = EuclideanDistance(nItem item) # Update neighbors either adding the # current item in neighbors or not. neighbors = UpdateNeighbors(neighbors item distance k) # Count the number of each class  # in neighbors count = CalculateNeighborsClass(neighbors k) # Find the max in count aka the # class with the most appearances return FindMax(count) def UpdateNeighbors(neighbors item distance k ): if len(neighbors) < k: # List is not full add  # new item and sort neighbors.append([distance item['Class']]) neighbors = sorted(neighbors) else: # List is full Check if new  # item should be entered if neighbors[-1][0] > distance: # If yes replace the  # last element with new item neighbors[-1] = [distance item['Class']] neighbors = sorted(neighbors) return neighbors ###_Evaluation Functions_### def K_FoldValidation(K k Items): if K > len(Items): return -1 # The number of correct classifications correct = 0 # The total number of classifications total = len(Items) * (K - 1) # The length of a fold l = int(len(Items) / K) for i in range(K): # Split data into training set # and test set trainingSet = Items[i * l:(i + 1) * l] testSet = Items[:i * l] + Items[(i + 1) * l:] for item in testSet: itemClass = item['Class'] itemFeatures = {} # Get feature values for key in item: if key != 'Class': # If key isn't 'Class' add  # it to itemFeatures itemFeatures[key] = item[key] # Categorize item based on # its feature values guess = Classify(itemFeatures k trainingSet)[0] if guess == itemClass: # Guessed correctly correct += 1 accuracy = correct / float(total) return accuracy def Evaluate(K k items iterations): # Run algorithm the number of # iterations pick average accuracy = 0 for i in range(iterations): shuffle(items) accuracy += K_FoldValidation(K k items) print accuracy / float(iterations) ###_Main_### def main(): items = ReadData('data.txt') Evaluate(5 5 items 100) if __name__ == '__main__': main() 

Saída: 

0.9375

A saída pode variar de máquina para máquina. O código inclui uma função de validação de dobra, mas não está relacionada ao algoritmo; existe para calcular a precisão do algoritmo.