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
Out[3]:
['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)

In [4]:
from IPython.core.display import Image 
Image(filename='flower_parts.jpg') 
Out[4]:

O dataset contém dados de 150 flores com 4 atributos para cada flor:

In [6]:
iris_data.data.shape
Out[6]:
(150, 4)

Vejamos os valores das 10 primeiras flores:

In [7]:
iris_data.data[:10]
Out[7]:
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:

  • 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
Out[5]:
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.

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)
Out[11]:
(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).

In [9]:
row = data_test[0]
In [10]:
row
Out[10]:
array([ 5.8,  2.8,  5.1,  2.4])

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
Out[12]:
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.

In [13]:
rank = distances.argsort()
In [14]:
rank
Out[14]:
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:

In [15]:
K=5
closer = rank[:K]
In [16]:
closer
Out[16]:
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.

In [17]:
closer_labels = target_train.take(closer)
In [18]:
closer_labels
Out[18]:
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.

In [19]:
target_test[0]
Out[19]:
2

Acertou :)