Что такое approximate nearest neighbors (ANN)?

Approximate Nearest Neighbors (ANN)

Approximate Nearest Neighbors — это методология поиска ближайших соседей в пространстве высокой размерности, которая жертвует небольшой точностью ради значительного увеличения скорости. В отличие от точного поиска (exact nearest neighbors), ANN не гарантирует нахождение абсолютно ближайшего соседа, но находит близкие соседей намного быстрее. Это критично для масштабируемых систем с миллионами или миллиардами точек данных.

Почему нужны ANN

Проблема с exact nearest neighbors

from sklearn.neighbors import NearestNeighbors
import numpy as np
import time

# Создать большой датасет
X = np.random.randn(1_000_000, 128)  # 1 млн точек в 128 измерениях
query = np.random.randn(1, 128)

# Точный поиск (brute force)
start = time.time()
nn = NearestNeighbors(n_neighbors=10, algorithm='brute')
nn.fit(X)
distances, indices = nn.kneighbors(query)
brute_time = time.time() - start

print(f'Brute Force: {brute_time:.4f} сек')

# KD-Tree
start = time.time()
nn = NearestNeighbors(n_neighbors=10, algorithm='kd_tree')
nn.fit(X)
distances, indices = nn.kneighbors(query)
kd_time = time.time() - start

print(f'KD-Tree: {kd_time:.4f} сек')

# Для 128 измерений KD-Tree почти такой же медленный, как brute force!

Сложность

Algorithm          Time Complexity    Space Complexity
──────────────────  ────────────────   ─────────────────
Brute Force         O(n * d)           O(n * d)
KD-Tree            O(log n) best       O(n * d)
               O(n) worst
Ball-Tree          O(log n) best       O(n * d)
               O(n) worst
ANN (LSH)          O(1) on average     O(n log n)
ANN (HNSW)         O(log n) with      O(n)
               small constants
ANN (IVF)          O(sqrt(n))          O(n * d)

Для высокой размерности exact методы неэффективны, нужны ANN.

1. Locality-Sensitive Hashing (LSH)

Основная идея: хешировать точки так, чтобы близкие точки часто попадали в одну хеш-функцию.

import numpy as np
from sklearn.random_projection import SparseRandomProjection

class SimpleANNLSH:
    def __init__(self, n_hashes=10, hash_size=10):
        self.n_hashes = n_hashes
        self.hash_size = hash_size
        self.hash_tables = []
        self.data = None
    
    def fit(self, X):
        self.data = X
        # Создать несколько случайных проекций для хеширования
        for _ in range(self.n_hashes):
            projection = SparseRandomProjection(n_components=self.hash_size)
            projected = projection.fit_transform(X)
            hash_table = {}
            
            # Хешировать каждую точку
            for i, proj in enumerate(projected):
                hash_key = tuple(np.sign(proj).astype(int))
                if hash_key not in hash_table:
                    hash_table[hash_key] = []
                hash_table[hash_key].append(i)
            
            self.hash_tables.append(hash_table)
    
    def query(self, query_point, n_neighbors=10):
        # Найти потенциальные соседи из hash таблиц
        candidates = set()
        
        for i in range(self.n_hashes):
            projection = SparseRandomProjection(n_components=self.hash_size)
            proj = projection.fit_transform(query_point.reshape(1, -1))[0]
            hash_key = tuple(np.sign(proj).astype(int))
            
            if hash_key in self.hash_tables[i]:
                candidates.update(self.hash_tables[i][hash_key])
        
        # Из кандидатов найти ближайших
        if candidates:
            distances = np.linalg.norm(self.data[list(candidates)] - query_point, axis=1)
            nearest_indices = np.argsort(distances)[:n_neighbors]
            return list(candidates)[nearest_indices]
        
        return []

2. HNSW (Hierarchical Navigable Small World)

Один из лучших ANN алгоритмов. Используется в Pinecone, Weaviate и других vector databases.

import hnswlib
import numpy as np

# Создать индекс HNSW
dim = 128
index = hnswlib.Index(space='l2', dim=dim)  # l2 = евклидова метрика

# Добавить данные
X = np.random.randn(100_000, dim).astype('float32')
index.add_items(X, np.arange(len(X)))

# Параметры HNSW
index.ef = 200  # Точность поиска (больше = точнее но медленнее)
index.ef_construction = 200  # Точность при построении индекса

# Запрос
query = np.random.randn(1, dim).astype('float32')
labels, distances = index.knn_query(query, k=10)

print(f'10 ближайших соседей: {labels[0]}')
print(f'Расстояния: {distances[0]}')

# Сохранить индекс
index.save_index('my_index.bin')

# Загрузить
index = hnswlib.Index(space='l2', dim=dim)
index.load_index('my_index.bin')

Как работает HNSW

1. Построение: создаёт иерархию слоёв графа
2. Поиск: начинает с верхних слоёв, спускается вниз
3. На каждом слое использует локальный поиск
4. Результат: логарифмическая сложность с малыми константами

Пример структуры:

Layer 2:  A ---- B        (вершины с длинными связями)
          |\
          | C
          |/ \
Layer 1:  A -- B -- C      (более локальные связи)
          |\ /| /|
Layer 0:  A-B-C-D-E        (все вершины, много связей)

3. IVF (Inverted File Index)

Используется в Facebook AI Similarity Search (FAISS).

import faiss
import numpy as np

# Параметры
dim = 128
n_data = 1_000_000
data = np.random.randn(n_data, dim).astype('float32')

# Создать IVF индекс
nlist = 100  # Количество кластеров
quantizer = faiss.IndexFlatL2(dim)
index = faiss.IndexIVFFlat(quantizer, dim, nlist)

# Обучить на выборке
index.train(data[:10000])  # Обучить на 10k примерах

# Добавить все данные
index.add(data)

# Запрос
query = np.random.randn(1, dim).astype('float32')
k = 10
distances, indices = index.search(query, k)

print(f'10 ближайших соседей: {indices[0]}')
print(f'Расстояния (L2): {distances[0]}')

# Параметр nprobe контролирует точность/скорость
index.nprobe = 10  # Проверить 10 кластеров (по умолчанию 1)
index.search(query, k)  # Более точный, но медленнее

4. Product Quantization (PQ)

Для сжатия векторов и экономии памяти.

import faiss

# IVF с Product Quantization
dim = 128
nlist = 100
m = 8  # Количество подвекторов
nbits = 8  # Количество бит для квантизации

quantizer = faiss.IndexFlatL2(dim)
index = faiss.IndexIVFPQ(quantizer, dim, nlist, m, nbits)

index.train(data[:10000])
index.add(data)

distances, indices = index.search(query, k=10)

print(f'Memory usage: {index.total_mem() / (1024**3):.2f} GB')

Сравнение методов ANN

Практический пример: Semantic Search

from sentence_transformers import SentenceTransformer
import hnswlib

# Модель для эмбеддинга текста
model = SentenceTransformer('all-MiniLM-L6-v2')

# Документы
documents = [
    'The cat is on the mat',
    'Dogs are loyal pets',
    'Cats are independent animals',
    'Machine learning is powerful'
]

# Получить эмбеддинги
embeddings = model.encode(documents)

# Создать ANN индекс
dim = embeddings.shape[1]
index = hnswlib.Index(space='cosine', dim=dim)
index.add_items(embeddings, np.arange(len(embeddings)))

# Поиск
query = 'Cats and pets'
query_embedding = model.encode([query])
labels, _ = index.knn_query(query_embedding, k=2)

print(f'Query: {query}')
for idx in labels[0]:
    print(f'  Result: {documents[idx]}')

Метрики расстояния в ANN

# Евклидова метрика (L2)
def euclidean(a, b):
    return np.sqrt(np.sum((a - b) ** 2))

# Manhattan (L1)
def manhattan(a, b):
    return np.sum(np.abs(a - b))

# Cosine (для нормализованных векторов / текста)
def cosine(a, b):
    return 1 - np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))

# Inner Product (для нормализованных)
def inner_product(a, b):
    return -np.dot(a, b)  # Отрицательный для минимизации

Выводы

• ANN необходим для больших данных, где exact поиск неэффективен
• HNSW — лучший выбор для большинства случаев (быстро, точно, просто)
• IVF (FAISS) — для очень больших наборов с фиксированными данными
• Trade-off: скорость vs точность, который нужно настраивать под задачу
• Vector databases (Pinecone, Weaviate, Milvus) используют ANN под капотом
• Правильный выбор метрики расстояния критичен (L2, cosine, inner product)