RSS

Arquivo da categoria: Machine Learning

Classificação KNN rápida como the flash

Artist: Christopher Moeller

O método dos k vizinhos mais próximos (kNN, do inglês k nearest neighbors) é um dos métodos de classificação automática mais usados na industria. Entretanto é comum problemas de performance com KNN em linguagens interpretadas isso porque é tudo feito de forma genérica sem otimizações na parte da algebra linear(calma já explico), embora clusterizar seja interessante nestes casos no final torna-se um grande desperdício de energia e tempo.

Muitos processadores modernos tem recursos que não são usados por programadores comuns, fazer uso de um registrador RAX, no caso estaria usando apenas 64bits sendo que muitos processadores tem registradores de 128bits, 256bits e até 512bits, tais como XMM, YMM e ZMM(pensando em AVX).

“Se você pagou por uma ferrari, um dia você deve pensar em passar dos 60km/h”

Destravando todo esse poder dos registradores e instruções, podemos chegar a ter até 200% a mais de performance na algebra linear ou mais dependendo do contexto. O problema é que para programar usando intrinsics ou inline assembly pode ser tanto difícil, já que não é algo comum de se ver em cursos acadêmicos(comum para programadores de games ou aqueles que trabalham com criptografia).

Até aqui alguns devem de se perguntar, “há mas o GCC otimiza basta usar aquele argumento -Os, O3…” mesmo otimizando não é melhor(mais rápido) do que algumas implementações do Agner Fog por exemplo. Para ter algo empírico basta fazer benchmark e comparar as duas formas…

Apresento aqui uma solução para o problema de classificação usando KNN em alta performance, existe uma biblioteca para linguagem C++ chamada armadillo, internamente essa bibliotéca tem recursos para usar o BLAS, LAPACK, SIMD otimizando assim a parte de algebra linear.

Desenvolvi uma biblioteca usando armadillo para classificar classes usando método KNN, acabei testando no linux em uma distribuição debian, caso queira testar siga os passos:

1- Instale a lib do armadillo seguinto o comando:

$ apt-get install libarmadillo-dev

2- Configure o armadillo conforme sua necessidade seguindo o site oficial. http://arma.sourceforge.net/docs.html#config_hpp

3- Obtenha repositório do projeto, compile e faça um teste seguindo os comandos:

cooler@Nepal:/codes$ git clone https://github.com/CoolerVoid/libfast_knn
cooler@Nepal:~/codes/libfast_knn$ make
g++ -Wall -O3 -larmadillo -fstack-protector-all -D_FORTIFY_SOURCE=2 -c src/*.cpp -c lib/*.h -c lib/*.cpp
g++ -o bin/knn_test *.o -Wl,-z,relro,-z,now 
rm *.o

cooler@Nepal:~/codes/libfast_knn$ bin/knn_test 
Test Manhattan:
1:    5.0000   3.0000   1.6000   0.2000
	Result: 1
2:    1.0000   2.0000   1.6000   2.2000
	Result: 1
3:    6.0000   4.0000   4.6000   3.2000
	Result: 3
4:    0.9000   1.0000   2.6000   2.2000
	Result: 1
5:    9.0000   7.0000   4.6000   4.2000
	Result: 3

Test Euclidean:
1:    5.0000   3.0000   1.6000   0.2000
	Result: 1
2:    1.0000   2.0000   1.6000   2.2000
	Result: 2
3:    6.0000   4.0000   4.6000   3.2000
	Result: 3
4:    0.9000   1.0000   2.6000   2.2000
	Result: 2
5:    9.0000   7.0000   4.6000   4.2000
	Result: 3

Para aprender como usar a biblioteca basta ler o código no arquivo “src/main.c“.

Até o momento não existe implementação em Java, Python ou R que tenha maior performance, o consagrado MLpack usado até mesmo pelo google faz uso do armadillo, veja seus resultados em benchmarks.

Por que você implementou já que o Mlpack também faz KNN ?

Mlpack é muito bom entretanto se precisa fazer uso de apenas de uma função KNN, pode ficar triste quando notar a instalação do mlpack pedindo mais de 300mb de dependências. A curva de aprendizado é lenta já que a documentação do Mlpack é gigantesca. No meu código foi implementado algo simples a bala de prata certa para um problema específico, encontrei nada falando de classificação usando KNN no MLpack, nem mesmo na sua documentação(logo a lib apresentada neste post é muito útil).

Para quem gostou do assunto e quer saber outras formas de ganhar performance fica uma dica tente usar GPU, segue a dica: https://github.com/vincentfpgarcia/kNN-CUDA

Referências:

https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm

http://www.mlpack.org/benchmarks.html

http://arma.sourceforge.net/speed.htm

Livro – Machine Learning in Action – Peter Harrington April 2012 ISBN 9781617290183 (embora seja em python os exemplos, aprendi muito).

 
Deixe um comentário

Publicado por em julho 9, 2017 em Linguagem C, Machine Learning