[WIP] Nearest Neighbors implementation

[mstallmo]

Issue tracking the implementation progress of Nearest Neighbors for linfa.

TODO:

• [x] Make kneighbor implementation more flexible to the specific algorithm chosen (brute force, ball tree, kd tree)
• [x] Make the input for NearestNeighbors::fit and NearestNeighbors::kneighbor more generic over input type and shape if possible
• [ ] Fix return type of kneighbors from Vec -> Array2
• [ ] Build out the NearestNeighborHyperParameter implementation
• [ ] Open WIP pull request against upstream
• [ ] Ball Tree implementation
• [ ] KD Tree implementation
• [ ] Optimize brute force algorithm implementation
• [ ] Open Pull Request against the upstream project

Progress so far: I have completed the basic project structure setup to get it building with linfa as well as pulling together the basic public API. For now this public API is based off of the API laid out by the original k-means clustering create. I'm planning on keeping the API following that pattern as long as it applies to nearest neighbor.

I've also completed an initial implementation of the brute force algorithm described in the scikit-learn for computing nearest neighbor of given coordinates. This is a very early stage implementation operating in an un-optimized fashion and doesn't quite return the correct value.

[mstallmo]

Minor update:

I tried to make some progress on making the inputs more generic over the array type it takes in but to very little success.

I'm pretty sure I can do this implementation but it'll take a different approach than what I came up for the first implementation. A generic trait on a generic struct seems to be a little tricky and the lack of any sort of other people running into a similar problem on stack overflow and the like leads me to believe I'm on a funky path with how I tried to come at it.

I also need to do some thinking on then general API approach. I've been generally following the Python API when building this out but after seeing some discussion on the main repo I don't think I need to stick to it as strictly as I have been.

I have a feeling that I'll be doing a minor rewrite of what I have so far to make it more flexible for generics. I might be a little in over my head here with my Rust skills but the generic approach feels like the right API for the problem.

[mstallmo]

Good news everyone!

I was able to make the API generic over both dimension and data type for the Nearest Neighbors wrapper as well as the concrete Brute type. Thanks to the fine people over in the r/rust subreddit I was able to get past the type constraint that I was missing to make the compiler happy.

I would have never been able to find that on my own, hopefully having that answer out there on reddit helps someone else down the line. Searching for that specific problem on Google was kind of a nightmare.

I'm still very much trying to wrap my head around the generic syntax of Rust. It seems as though it's not as straight forward as templates are in C++ but I also haven't done advanced templates in C++ so it's probably not a good personal comparison.

Hopefully having that done for Brute it will be easier to implement for the Ball and KD tree algorithms in the future.