Scikit Learn - K-Nearest Neighbours (KNN)

Este capítulo o ajudará a entender os métodos do vizinho mais próximo no Sklearn.

O método de aprendizagem baseado em vizinho é de ambos os tipos, a saber supervised e unsupervised. O aprendizado supervisionado baseado em vizinhos pode ser usado tanto para classificação quanto para problemas preditivos de regressão, mas é usado principalmente para problemas preditivos de classificação na indústria.

Os métodos de aprendizagem baseados em vizinhos não possuem uma fase de treinamento especializada e usam todos os dados para treinamento durante a classificação. Ele também não assume nada sobre os dados subjacentes. Essa é a razão pela qual eles são preguiçosos e não paramétricos por natureza.

O principal princípio por trás dos métodos de vizinho mais próximo é -

• Para encontrar um número predefinido de armário de amostras de treinamento em distância para o novo ponto de dados

• Preveja o rótulo a partir desse número de amostras de treinamento.

Aqui, o número de amostras pode ser uma constante definida pelo usuário, como no aprendizado de K-vizinho mais próximo ou variar com base na densidade local do ponto, como no aprendizado de vizinho baseado em raio.

Módulo sklearn.neighbors

Scikit-learn tem sklearn.neighborsmódulo que fornece funcionalidade para métodos de aprendizagem baseados em vizinhos não supervisionados e supervisionados. Como entrada, as classes neste módulo podem lidar com matrizes NumPy ouscipy.sparse matrizes.

Tipos de algoritmos

Diferentes tipos de algoritmos que podem ser usados ​​na implementação de métodos baseados em vizinhos são os seguintes -

Força bruta

O cálculo da força bruta das distâncias entre todos os pares de pontos no conjunto de dados fornece a implementação de pesquisa de vizinho mais ingênua. Matematicamente, para N amostras em dimensões D, escalas de abordagem de força bruta como0[DN²]

Para pequenas amostras de dados, esse algoritmo pode ser muito útil, mas se torna inviável à medida que o número de amostras aumenta. A pesquisa de vizinhança de força bruta pode ser ativada escrevendo a palavra-chavealgorithm=’brute’.

Árvore KD

Uma das estruturas de dados baseadas em árvore que foram inventadas para lidar com as ineficiências computacionais da abordagem de força bruta é a estrutura de dados em árvore KD. Basicamente, a árvore KD é uma estrutura de árvore binária que é chamada de árvore K-dimensional. Ele particiona recursivamente o espaço de parâmetros ao longo dos eixos de dados, dividindo-o em regiões ortográficas aninhadas nas quais os pontos de dados são preenchidos.

Vantagens

A seguir estão algumas vantagens do algoritmo de árvore KD -

Construction is fast - Como o particionamento é realizado apenas ao longo dos eixos de dados, a construção da árvore KD é muito rápida.

Less distance computations- Este algoritmo leva muito menos cálculos de distância para determinar o vizinho mais próximo de um ponto de consulta. É preciso apenas[ ()] cálculos de distância.

Desvantagens

Fast for only low-dimensional neighbor searches- É muito rápido para buscas vizinhas de baixa dimensão (D <20), mas à medida que D aumenta, torna-se ineficiente. Como o particionamento é realizado apenas ao longo dos eixos de dados,

As pesquisas de vizinho da árvore KD podem ser habilitadas escrevendo a palavra-chave algorithm=’kd_tree’.

Ball Tree

Como sabemos que a árvore KD é ineficiente em dimensões superiores, portanto, para resolver essa ineficiência da árvore KD, a estrutura de dados da árvore Ball foi desenvolvida. Matematicamente, divide os dados de forma recursiva, em nós definidos por um centróide C e raio r, de modo que cada ponto do nó fique dentro da hiperesfera definida pelo centróideC e raio r. Ele usa a desigualdade triangular, fornecida abaixo, o que reduz o número de pontos candidatos para uma pesquisa de vizinho

$$ \ arrowvert X + Y \ arrowvert \ leq \ arrowvert X \ arrowvert + \ arrowvert Y \ arrowvert $$

Vantagens

A seguir estão algumas vantagens do algoritmo Ball Tree -

Efficient on highly structured data - Como a árvore de bolas particiona os dados em uma série de hiperesferas de aninhamento, é eficiente em dados altamente estruturados.

Out-performs KD-tree - Ball tree supera a árvore KD em grandes dimensões porque tem geometria esférica dos nós da árvore ball.

Desvantagens

Costly - Particionar os dados em uma série de hiperesferas de aninhamento torna sua construção muito cara.

As pesquisas de vizinho da árvore de bolas podem ser habilitadas escrevendo a palavra-chave algorithm=’ball_tree’.

Algoritmo de escolha de vizinhos mais próximos

A escolha de um algoritmo ideal para um determinado conjunto de dados depende dos seguintes fatores -

Número de amostras (N) e Dimensionalidade (D)

Esses são os fatores mais importantes a serem considerados ao escolher o algoritmo do vizinho mais próximo. É por causa das razões apresentadas abaixo -

• O tempo de consulta do algoritmo de Força Bruta cresce como O [DN].

• O tempo de consulta do algoritmo Ball tree cresce como O [D log (N)].

• O tempo de consulta do algoritmo da árvore KD muda com D de uma maneira estranha que é muito difícil de caracterizar. Quando D <20, o custo é O [D log (N)] e este algoritmo é muito eficiente. Por outro lado, é ineficiente no caso quando D> 20 porque o custo aumenta para quase O [DN].

Estrutura de dados

Outro fator que afeta o desempenho desses algoritmos é a dimensionalidade intrínseca dos dados ou a dispersão dos dados. É porque os tempos de consulta dos algoritmos da árvore Ball e da árvore KD podem ser muito influenciados por ele. Considerando que o tempo de consulta do algoritmo de Força Bruta não é alterado pela estrutura de dados. Geralmente, os algoritmos Ball tree e KD tree produzem um tempo de consulta mais rápido quando implantados em dados mais esparsos com menor dimensionalidade intrínseca.

Número de vizinhos (k)

O número de vizinhos (k) solicitados para um ponto de consulta afeta o tempo de consulta dos algoritmos da árvore Ball e da árvore KD. O tempo de consulta torna-se mais lento conforme o número de vizinhos (k) aumenta. Considerando que o tempo de consulta da Força Bruta permanecerá inalterado pelo valor de k.

Número de pontos de consulta

Como eles precisam da fase de construção, os algoritmos da árvore KD e da árvore Ball serão eficazes se houver um grande número de pontos de consulta. Por outro lado, se houver um número menor de pontos de consulta, o algoritmo Brute Force tem um desempenho melhor do que os algoritmos de árvore KD e Ball tree.