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[DN2]
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.