Dove posso trovare un'implementazione C/C++ seriale dell'algoritmo k-nearest neighbor?
Sai di una libreria che ha questo?
Ho trovato openCV ma l'implementazione è già parallela.
Voglio iniziare da un'implementazione seriale e parallelizzarla con pthreads openMP e MPI.
Implementazione C/C++ prossimo più prossimo a K
Grazie,
Alex
Che ne dici di ANN? http://www.cs.umd.edu/~mount/ANN/. Una volta ho usato l'implementazione di kdtree, ma ci sono altre opzioni.
Citazione dal sito Web: "ANN è una libreria scritta in C++, che supporta strutture dati e algoritmi per il vicino più vicino esatto e approssimativo che cerca in dimensioni arbitrariamente alte."
Grazie, ANN è un buon punto di partenza. – alexsardan
Il modo più semplice per implementare questo è un ciclo tra tutti gli elementi e deposito K più vicino. (solo confrontando). La complessità di questo è O(n) che non è così buona, ma non è necessaria alcuna pre-elaborazione. Quindi ora dipende davvero dalla tua applicazione. È necessario utilizzare un indice spaziale per l'area di partizione in cui si cerca knn. Per alcune applicazioni, la struttura spaziale basata sulla griglia va bene (basta dividere il mondo in blocco fisso e cercare solo all'interno di blocchi prima). Questo è buono quando le tue entità sono equamente distribuite. Meglio approccio è quello di utilizzare alcuni struttura gerarchica come kd-tree ... E 'davvero tutto dipende da quello che vi serve
Per ulteriori informazioni, tra cui sguardo pseudocodice in queste presentazioni:
Grazie per la risposta. In realtà devo iniziare da una versione già implementata. – alexsardan
Ho scritto un C++ implementation for a KD-tree con la ricerca più vicina. Puoi estenderlo facilmente per i vicini K vicini aggiungendo una coda di priorità.
Aggiornamento: ho aggiunto il supporto per k-nearest ricerca prossimo in N dimensioni
Grazie, ma nessuna informazione sulla licenza deve essere vista. –
Per quali problemi stanno per applicare questo algoritmo? KNN è davvero semplice e puoi provare a implementare il tuo approccio. –