LSH 欧氏距离 KNN 代码

以下是使用 Locality Sensitive Hashing (LSH) 和欧氏距离计算K近邻的Python代码示例：

import numpy as np
from sklearn.neighbors import NearestNeighbors
from scipy.spatial.distance import euclidean

class LSHKNN:
    def __init__(self, n_hashes=10, hash_size=10, n_neighbors=5):
        self.n_hashes = n_hashes
        self.hash_size = hash_size
        self.n_neighbors = n_neighbors
        self.hash_tables = []
        self.data = None

    def fit(self, data):
        self.data = data
        n_samples, n_features = data.shape
        random_vectors = np.random.randn(n_features, self.n_hashes * self.hash_size)

        # Split data into hash buckets
        for i in range(self.n_hashes):
            hash_table = {}
            projection = random_vectors[:, i*self.hash_size:(i+1)*self.hash_size]
            hashes = np.dot(data, projection)
            for j, h in enumerate(hashes):
                if tuple(h) not in hash_table:
                    hash_table[tuple(h)] = []
                hash_table[tuple(h)].append(j)
            self.hash_tables.append(hash_table)

    def predict(self, query):
        # Compute query hash values
        n_samples, n_features = self.data.shape
        random_vectors = np.random.randn(n_features, self.n_hashes * self.hash_size)
        projection = random_vectors[:, :self.hash_size]
        query_hash = np.dot(query, projection)

        # Find candidate neighbors
        candidate_neighbors = set()
        for h in tuple(query_hash):
            if tuple(h) in self.hash_tables[0]:
                candidate_neighbors.update(self.hash_tables[0][tuple(h)])

        # Refine candidates
        candidate_distances = []
        for i in candidate_neighbors:
            d = euclidean(query, self.data[i])
            if len(candidate_distances) < self.n_neighbors or d < max(candidate_distances):
                candidate_distances.append(d)
                candidate_distances.sort()
                if len(candidate_distances) > self.n_neighbors:
                    candidate_distances = candidate_distances[:self.n_neighbors]
        
        # Find exact neighbors among candidates
        nbrs = NearestNeighbors(n_neighbors=self.n_neighbors, algorithm='brute', metric='euclidean').fit(self.data[candidate_neighbors])
        distances, indices = nbrs.kneighbors([query])
        
        return distances[0], indices[0]

使用示例：

import numpy as np

# Generate random data
np.random.seed(0)
data = np.random.rand(100, 10)

# Create LSHKNN object and fit data
lshknn = LSHKNN(n_hashes=5, hash_size=2, n_neighbors=5)
lshknn.fit(data)

# Generate a random query
query = np.random.rand(10)

# Find nearest neighbors to query
distances, indices = lshknn.predict(query)

print("Distances:", distances)
print("Indices:", indices)