[MRG] Locality Sensitive Hashing for approximate nearest neighbor search(GSoC)

The data structure construction is already probabilistic. Do you think 
it is important for users that for a fixed index, answers be 
deterministic? there are advantages in debugging; on the other hand, I 
can imagine situations where "always return the first few in index" also 
causes significant surprise. But either way seems fine to me.

I think it is *important* that candidates do not repeat (user: lets get 
k neighbors and build an order k linear model on them. Oh, they are 
linearly dependent? what, they repeat!?).

Daniel

On 10/23/2014 04:29 AM, jnothman wrote:
> In sklearn/neighbors/approximate.py:
>
>> +        hashes = (grp.transform(self._fit_X) > 0).astype(int)
>> +        hash_function = grp.components_
>> +
>> +        binary_hashes = np.packbits(hashes).view(dtype='>u4')
>> +        original_indices = np.argsort(binary_hashes)
>> +
>> +        return original_indices, binary_hashes[original_indices], hash_function
>> +
>> +    def _compute_distances(self, query, candidates):
>> +        """Computes the cosine distance.
>> +
>> +        Distance is from the query to points in the candidates array.
>> +        Returns argsort of distances in the candidates
>> +        array and sorted distances.
>> +        """
>> +        distances = pairwise_distances(query, self._fit_X[candidates],
>
> So I think this change needs to be in |kneighbors|: it should not touch
> |radius_neighbors|. I think we need the return value to be
> deterministic, so I am not sure about this random selection idea. I'd
> even consider repeating candidates with a warning, or selecting indices
> 0, 1, 2, ... as needed.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/scikit-learn/scikit-learn/pull/3304/files#r19256708>.
>