complexidade computacional k-NN

Qual é a complexidade de tempo do algoritmo k -NN com abordagem de pesquisa ingênua (sem árvore kd ou similar)?

Estou interessado em sua complexidade de tempo, considerando também o hiperparâmetro k . Eu encontrei respostas contraditórias:

1. O (nd + kn), onde n é a cardinalidade do conjunto de treinamento ed a dimensão de cada amostra. [1]

2. O (ndk), onde novamente n é a cardinalidade do conjunto de treinamento ed da dimensão de cada amostra. [2]

[1] http://www.csd.uwo.ca/courses/CS9840a/Lecture2_knn.pdf (pag. 18/20).

[2] http://www.cs.haifa.ac.il/~rita/ml_course/lectures/KNN.pdf (pag. 18/31).

Supondo que seja fixo (como as duas palestras vinculadas), suas escolhas algorítmicas determinarão se sua computação leva tempo de execução O ( n d + k n ) ou tempo de execução O ( n d k ) .$k$$O(nd+kn)$$O(ndk)$

Primeiro, vamos considerar um algoritmo de tempo de execução :$O(nd+kn)$

• Inicialize para todas as observações i no conjunto de treinamento$selected_i = 0$$i$
• Para cada observação conjunto de treinamento , compute d i s t i , a distância entre a nova observação de conjunto de treinamento de observação $i$$dist_i$$i$
• Para a k : Faça um loop em todas as observações do conjunto de treinamento, selecionando o índice i com o menor valor d i s t i e para o qual s e l e c t e d i = 0 . Selecione esta observação definindo s e l e c t e d i = 1 .$j=1$$k$$i$$dist_i$$selected_i=0$$selected_i=1$
• Retornar os índices selecionados$k$

Cada cálculo da distância requer tempo de execução, de modo que o segundo passo requer S ( n d ) tempo de execução. Para cada iteração no terceiro passo, realizamos S ( n ) de trabalho por ciclo através das observações do conjunto de treino, de modo que o passo requer geral S ( n k ) de trabalho. As primeira e quarta etapas requerem apenas trabalho O ( n ) , portanto, obtemos um tempo de execução O ( n d + k n ) .$O(d)$$O(nd)$$O(n)$$O(nk)$$O(n)$$O(nd+kn)$

Agora, vamos considerar um runtime algoritmo:$O(ndk)$

• Inicialize para todas as observações i no conjunto de treinamento$selected_i = 0$$i$
• Para a k : Faça um loop em todas as observações do conjunto de treinamento e calcule a distância d entre a observação do conjunto de treinamento selecionado e a nova observação. Seleccionar o índice i com a menor d valor para o qual s e l e c t e d i = 0 . Selecione esta observação definindo s e l e c t e d i = 1 .$j=1$$k$$d$$i$$d$$selected_i=0$$selected_i=1$
• Retornar os índices selecionados$k$

Para cada iteração na segunda etapa, calculamos a distância entre a nova observação e cada observação do conjunto de treinamento, exigindo que trabalhe para uma iteração e, portanto, O ( n d k ) trabalhe em geral.$O(nd)$$O(ndk)$

A diferença entre os dois algoritmos é que o primeiro precomputa e armazena as distâncias (exigindo memória extra), enquanto o segundo não. No entanto, dado que já armazenar todo o conjunto de treino, exigindo S ( n d ) de memória, bem como o s e l e c t e d vetor, exigindo S ( n ) de armazenamento, o armazenamento dos dois algoritmos é assintoticamente o mesmo. Como resultado, o melhor tempo de execução assintótico para k > 1 torna o primeiro algoritmo mais atraente.$O(n)$$O(nd)$$selected$$O(n)$$k > 1$

Vale ressaltar que é possível obter um tempo de execução usando uma melhoria algorítmica:$O(nd)$

• Para cada observação conjunto de treinamento , compute d i s t i , a distância entre a nova observação de conjunto de treinamento de observação $i$$dist_i$$i$
• Executar o algoritmo QuickSelect para calcular o menor distância em S ( n ) de tempo de execução$k^{th}$$O(n)$
• Retorna todos os índices não maiores que a menor distância calculada $k^{th}$

Esta abordagem tira vantagem do fato de que as abordagens eficientes existem para encontrar o menor valor em uma matriz indiferenciados.$k^{th}$