Encontrar vizinhos K mais próximos e sua implementação

Eu estou trabalhando na sorting de dados simples usando KNN com distância euclidiana. Eu vi um exemplo sobre o que eu gostaria de fazer que é feito com a function knnsearch do MATLAB como mostrado abaixo:

 load fisheriris x = meas(:,3:4); gscatter(x(:,1),x(:,2),species) newpoint = [5 1.45]; [n,d] = knnsearch(x,newpoint,'k',10); line(x(n,1),x(n,2),'color',[.5 .5 .5],'marker','o','linestyle','none','markersize',10) 

O código acima assume um novo ponto, isto é, [5 1.45] e encontra os 10 valores mais próximos do novo ponto. Alguém pode me mostrar um algoritmo MATLAB com uma explicação detalhada do que a function knnsearch faz? Existe alguma outra maneira de fazer isso?

   

A base do algoritmo K-Nearest Neighbor (KNN) é que você tem uma matriz de dados que consiste em N linhas e M colunas, onde N é o número de pontos de dados que temos, enquanto M é a dimensionalidade de cada ponto de dados. Por exemplo, se colocamos coordenadas cartesianas dentro de uma matriz de dados, geralmente é uma matriz N x 2 ou N x 3 . Com essa matriz de dados, você fornece um ponto de consulta e procura os k pontos mais próximos dessa matriz de dados mais próximos desse ponto de consulta.

Geralmente, usamos a distância euclidiana entre a consulta e o resto de seus pontos na matriz de dados para calcular nossas distâncias. No entanto, outras distâncias como a L1 ou a distância City-Block / Manhattan também são usadas. Após esta operação, você terá distâncias N Euclideanas ou Manhattan que simbolizam as distâncias entre a consulta e cada ponto correspondente no dataset. Depois de encontrá-los, basta procurar os k pontos mais próximos da consulta classificando as distâncias em ordem crescente e recuperando os k pontos que têm a menor distância entre o dataset e a consulta.

Supondo que sua matriz de dados foi armazenada em x , e newpoint é um ponto de amostra em que tem colunas M (ou seja, 1 x M ), este é o procedimento geral que você seguiria na forma de ponto:

  1. Encontre a distância Euclidiana ou Manhattan entre o ponto newpoint e cada ponto em x .
  2. Classifique essas distâncias em ordem crescente.
  3. Retorna os k pontos de dados em x que estão mais próximos do newpoint .

Vamos fazer cada passo devagar.


Passo 1

Uma maneira que alguém pode fazer isso é talvez em um loop for assim:

 N = size(x,1); dists = zeros(N,1); for idx = 1 : N dists(idx) = sqrt(sum((x(idx,:) - newpoint).^2)); end 

Se você quisesse implementar a distância de Manhattan, isso seria simplesmente:

 N = size(x,1); dists = zeros(N,1); for idx = 1 : N dists(idx) = sum(abs(x(idx,:) - newpoint)); end 

dists seria um vetor de elemento N que contém as distâncias entre cada ponto de dados em x e newpoint . Fazemos uma subtração elemento-a-elemento entre o newpoint ponto e um ponto de dados em x , newpoint e newpoint todas elas juntas. Essa sum é então quadrada, o que completa a distância euclidiana. Para a distância de Manhattan, você executaria um elemento por subtração de elemento, pegaria os valores absolutos e sumria todos os componentes juntos. Esta é provavelmente a implementação mais simples de entender, mas pode ser a mais ineficiente … especialmente para conjuntos de dados maiores e maior dimensionalidade de seus dados.

Outra solução possível seria replicar newpoint e fazer com que essa matriz tenha o mesmo tamanho de x , em seguida, fazer uma subtração de elemento a elemento dessa matriz e, em seguida, sumr todas as colunas de cada linha e fazer a raiz quadrada. Portanto, podemos fazer algo assim:

 N = size(x, 1); dists = sqrt(sum((x - repmat(newpoint, N, 1)).^2, 2)); 

Para a distância de Manhattan, você faria:

 N = size(x, 1); dists = sum(abs(x - repmat(newpoint, N, 1)), 2); 

repmat pega uma matriz ou vetor e repete-os uma certa quantidade de vezes em uma determinada direção. No nosso caso, queremos pegar nosso vetor de novo ponto e empilhar N vezes um em cima do outro para criar uma matriz N x M , onde cada linha é M elementos longos. Subtraímos essas duas matrizes juntas e, em seguida, esquadramos cada componente. Depois disso, sum todas as colunas de cada linha e, finalmente, obtemos a raiz quadrada de todos os resultados. Para a distância de Manhattan, fazemos a subtração, pegamos o valor absoluto e summos.

No entanto, a maneira mais eficiente de fazer isso, na minha opinião, seria usar o bsxfun . Isso essencialmente faz a replicação que falamos sob o capô com uma única chamada de function. Portanto, o código seria simplesmente isso:

 dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2)); 

Para mim isso parece muito mais limpo e direto ao ponto. Para a distância de Manhattan, você faria:

 dists = sum(abs(bsxfun(@minus, x, newpoint)), 2); 

Passo 2

Agora que temos nossas distâncias, simplesmente as classificamos. Podemos usar o sort para classificar nossas distâncias:

 [d,ind] = sort(dists); 

d conteria as distâncias classificadas em ordem crescente, enquanto ind indica para cada valor na matriz não classificada onde aparece no resultado ordenado . Precisamos usar ind , extrair os primeiros k elementos desse vetor, então usar ind para indexar em nossa matriz de dados x para retornar os pontos que estavam mais próximos do newpoint .

Etapa 3

O passo final é retornar esses k pontos de dados que estão mais próximos do newpoint . Nós podemos fazer isso muito simplesmente por:

 ind_closest = ind(1:k); x_closest = x(ind_closest,:); 

ind_closest deve conter os índices na matriz de dados original x que são os mais próximos do newpoint . Especificamente, ind_closest contém em quais linhas você precisa amostrar em x para obter os pontos mais próximos do novo ponto. x_closest conterá esses pontos de dados reais.


Para o seu prazer de copiar e colar, é assim que o código se parece:

 dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2)); %// Or do this for Manhattan % dists = sum(abs(bsxfun(@minus, x, newpoint)), 2); [d,ind] = sort(dists); ind_closest = ind(1:k); x_closest = x(ind_closest,:); 

Passando pelo seu exemplo, vamos ver nosso código em ação:

 load fisheriris x = meas(:,3:4); newpoint = [5 1.45]; k = 10; %// Use Euclidean dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2)); [d,ind] = sort(dists); ind_closest = ind(1:k); x_closest = x(ind_closest,:); 

Ao inspecionar ind_closest e x_closest , é isso que recebemos:

 >> ind_closest ind_closest = 120 53 73 134 84 77 78 51 64 87 >> x_closest x_closest = 5.0000 1.5000 4.9000 1.5000 4.9000 1.5000 5.1000 1.5000 5.1000 1.6000 4.8000 1.4000 5.0000 1.7000 4.7000 1.4000 4.7000 1.4000 4.7000 1.5000 

Se você rodou knnsearch , você verá que sua variável n combina com ind_closest . No entanto, a variável d retorna as distâncias de newpoint para cada ponto x , não os próprios pontos de dados reais. Se você quiser as distâncias reais, basta fazer o seguinte após o código que eu escrevi:

 dist_sorted = d(1:k); 

Observe que a resposta acima usa apenas um ponto de consulta em um lote de N exemplos. Muito frequentemente, o KNN é usado em vários exemplos simultaneamente. Supondo que temos pontos de consulta Q que queremos testar no KNN. Isso resultaria em uma matriz kx M x Q , onde para cada exemplo ou cada fatia, retornamos os k pontos mais próximos com uma dimensionalidade de M Alternativamente, podemos retornar os IDs dos k pontos mais próximos, resultando em uma matriz Q xk . Vamos calcular os dois.

Uma maneira ingênua de fazer isso seria aplicar o código acima em um loop e repetir todos os exemplos.

Algo como isso funcionaria onde alocamos uma matriz Q xk e aplicamos a abordagem baseada em bsxfun para definir cada linha da matriz de saída para os k pontos mais próximos no dataset, onde usaremos o dataset da Fisher Iris exatamente como o que tínhamos antes. Também manteremos a mesma dimensionalidade do exemplo anterior e usaremos quatro exemplos, então Q = 4 e M = 2 :

 %// Load the data and create the query points load fisheriris; x = meas(:,3:4); newpoints = [5 1.45; 7 2; 4 2.5; 2 3.5]; %// Define k and the output matrices Q = size(newpoints, 1); M = size(x, 2); k = 10; x_closest = zeros(k, M, Q); ind_closest = zeros(Q, k); %// Loop through each point and do logic as seen above: for ii = 1 : Q %// Get the point newpoint = newpoints(ii, :); %// Use Euclidean dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2)); [d,ind] = sort(dists); %// New - Output the IDs of the match as well as the points themselves ind_closest(ii, :) = ind(1 : k).'; x_closest(:, :, ii) = x(ind_closest(ii, :), :); end 

Embora isso seja muito bom, podemos fazer ainda melhor. Existe uma maneira de calcular eficientemente a distância euclidiana ao quadrado entre dois conjuntos de vetores. Vou deixar como um exercício se você quiser fazer isso com o Manhattan. Consultando este blog , dado que A é uma matriz Q1 x M onde cada linha é um ponto de dimensionalidade M com pontos Q1 e B é uma matriz Q2 x M onde cada linha é também um ponto de dimensionalidade M com pontos Q2 , podemos eficientemente calcular uma matriz de distância D(i, j) onde o elemento na linha i e coluna j denota a distância entre a linha i de A e a linha j de B usando a seguinte formulação de matriz:

 nA = sum(A.^2, 2); %// Sum of squares for each row of A nB = sum(B.^2, 2); %// Sum of squares for each row of B D = bsxfun(@plus, nA, nB.') - 2*A*B.'; %// Compute distance matrix D = sqrt(D); %// Compute square root to complete calculation 

Portanto, se deixarmos que A seja uma matriz de pontos de consulta e B seja o dataset que consiste em seus dados originais, podemos determinar os k pontos mais próximos, classificando cada linha individualmente e determinando os k locais de cada linha que eram os menores. Também podemos usar isso para recuperar os próprios pontos.

Assim sendo:

 %// Load the data and create the query points load fisheriris; x = meas(:,3:4); newpoints = [5 1.45; 7 2; 4 2.5; 2 3.5]; %// Define k and other variables k = 10; Q = size(newpoints, 1); M = size(x, 2); nA = sum(newpoints.^2, 2); %// Sum of squares for each row of A nB = sum(x.^2, 2); %// Sum of squares for each row of B D = bsxfun(@plus, nA, nB.') - 2*newpoints*x.'; %// Compute distance matrix D = sqrt(D); %// Compute square root to complete calculation %// Sort the distances [d, ind] = sort(D, 2); %// Get the indices of the closest distances ind_closest = ind(:, 1:k); %// Also get the nearest points x_closest = permute(reshape(x(ind_closest(:), :).', M, k, []), [2 1 3]); 

Vemos que usamos a lógica para calcular a matriz de distância é a mesma, mas algumas variables ​​mudaram para se adequar ao exemplo. Também classificamos cada linha independentemente usando as duas versões de input de sort e, assim, ind conterá os IDs por linha e d conterá as distâncias correspondentes. Em seguida, descobrimos quais índices são os mais próximos de cada ponto de consulta, simplesmente truncando essa matriz para k colunas. Em seguida, usamos permute e reshape para determinar quais são os pontos mais próximos associados. Primeiro, usamos todos os índices mais próximos e criamos uma matriz de pontos que empilha todos os IDs uns sobre os outros, de modo que obtemos uma matriz Q * kx M Usar reshape e permute nos permite criar nossa matriz 3D para que ela se torne uma matriz kx M x Q como especificamos. Se você quiser obter as distâncias reais, podemos indexar em d e pegar o que precisamos. Para fazer isso, você precisará usar sub2ind para obter os índices lineares para que possamos indexar em d em um único disparo. Os valores de ind_closest já nos dão quais colunas precisamos acessar. As linhas que precisamos acessar são simplesmente 1, k vezes, 2, k vezes, etc. até Q k é para o número de pontos que queríamos retornar:

 row_indices = repmat((1:Q).', 1, k); linear_ind = sub2ind(size(d), row_indices, ind_closest); dist_sorted = D(linear_ind); 

Quando executamos o código acima para os pontos de consulta acima, estes são os índices, pontos e distâncias que obtemos:

 >> ind_closest ind_closest = 120 134 53 73 84 77 78 51 64 87 123 119 118 106 132 108 131 136 126 110 107 62 86 122 71 127 139 115 60 52 99 65 58 94 60 61 80 44 54 72 >> x_closest x_closest(:,:,1) = 5.0000 1.5000 6.7000 2.0000 4.5000 1.7000 3.0000 1.1000 5.1000 1.5000 6.9000 2.3000 4.2000 1.5000 3.6000 1.3000 4.9000 1.5000 6.7000 2.2000 x_closest(:,:,2) = 4.5000 1.6000 3.3000 1.0000 4.9000 1.5000 6.6000 2.1000 4.9000 2.0000 3.3000 1.0000 5.1000 1.6000 6.4000 2.0000 4.8000 1.8000 3.9000 1.4000 x_closest(:,:,3) = 4.8000 1.4000 6.3000 1.8000 4.8000 1.8000 3.5000 1.0000 5.0000 1.7000 6.1000 1.9000 4.8000 1.8000 3.5000 1.0000 4.7000 1.4000 6.1000 2.3000 x_closest(:,:,4) = 5.1000 2.4000 1.6000 0.6000 4.7000 1.4000 6.0000 1.8000 3.9000 1.4000 4.0000 1.3000 4.7000 1.5000 6.1000 2.5000 4.5000 1.5000 4.0000 1.3000 >> dist_sorted dist_sorted = 0.0500 0.1118 0.1118 0.1118 0.1803 0.2062 0.2500 0.3041 0.3041 0.3041 0.3000 0.3162 0.3606 0.4123 0.6000 0.7280 0.9055 0.9487 1.0198 1.0296 0.9434 1.0198 1.0296 1.0296 1.0630 1.0630 1.0630 1.1045 1.1045 1.1180 2.6000 2.7203 2.8178 2.8178 2.8320 2.9155 2.9155 2.9275 2.9732 2.9732 

Para comparar isso com o knnsearch , você deve especificar uma matriz de pontos para o segundo parâmetro, em que cada linha é um ponto de consulta e você verá que os índices e as distâncias classificadas coincidem entre essa implementação e a pesquisa do knnsearch .


Espero que isso ajude você. Boa sorte!