Привет, друзья!
В DS-задачах часто встречаются категориальные признаки с очень высокой кардинальностью (в которых много уникальных значений): ID, URL, слова в тексте, теги и прочее. Прямое one-hot кодирование таких признаков, скорее всего, приведёт к огромным разреженным матрицам и быстро "взорвёт" размерность🤯

Но прежде чем объединять редкие категории в "другое" или просто отбрасывать их, стоит рассмотреть hashing trick - простой и масштабируемый способ кодирования категориальных признаков.

В чём идея алгоритма?
➡️ берём строковое значение (например, user_id),
➡️ пропускаем его через хэш-функцию,
➡️ берём остаток по модулю D - заранее заданного размера выходного вектора,
➡️ получаем индекс, в который кладём 1 (или другое значение, если это count/frequency).

🧐Кажется, что похоже на one-hot - но вот в чём ключевое отличие: мы не храним словарь всех уникальных значений и сами выбираем размерность пространства D.

🤷‍♂️ Из минусов: при таком подходе возможны коллизии - два разных значения могут попасть в одну и ту же ячейку. Это происходит случайно, и по смыслу такие значения нельзя считать похожими. Но коллизии - это осознанная плата за компактность🤷‍♀️

👍 Из плюсов: метод работает стабильно и хорошо масштабируется. Даже если вдруг появляется новая категория, она автоматически попадает в какую-либо ячейку без пересоздания маппинга. Это делает hashing trick особенно удобным в стриминге, real-time inference и онлайн-обучении. Кроме того, можно кодировать "перекрестные" (парные, тройные и т.п.) категориальные фичи.

💻 В sklearn уже есть готовая реализация этого приёма:

from sklearn.feature_extraction import FeatureHasher

# хэшер на 10 выходных фичей
hasher = FeatureHasher(n_features=10, input_type='string')

# пример категориальных данных
data = [
    ['user_1', 'item_42'],
    ['user_2', 'item_17'],
]

# собственно преобразование
X = hasher.transform(data)

Hashing trick - не волшебная кнопка, но отличный инструмент в арсенале. Особенно там, где важны скорость, масштабируемость и минимальное потребление памяти.

Успехов в оптимизации размерности!🌹

#classic_ml@data_easy

Ну и раз уж речь зашла про математическую литературу, держите в дополнение к статистике ещё одно любопытное издание, посвящённое теории вероятности - книгу Сергея Самойленко "Вероятности и неприятности"🫴

Концентрация математики и формул повыше, чем у В. Савельева, но жизненные примеры и ассоциации не менее интересны!😊

#математика@data_easy

Привет, друзья!
Во многих задачах - от классификации и кластеризации до поиска похожих объектов и генерации рекомендаций - важно уметь эффективно находить ближайшие векторы в высокоразмерном пространстве. Но как только число векторов превышает несколько тысяч, простые методы из sklearn и numpy начинают работать непозволительно медленно🐌 При масштабах же в миллионы объектов стоит задуматься уже не только про быстроту, но и про оптимизацию, балансируя между точностью, скоростью и потреблением памяти.

В таких случаях приходят на помощь библиотеки для быстрого KNN в высокоразмерных пространствах. Самая известная, пожалуй, Faiss от Facebook AI Research. Вот её главные преимущества:

🔠 Подкапотная реализация на C++ с SIMD-оптимизациями и продуманным управлением памятью в Python-обёртке. А ещё это значит, что Faiss не блокируется GIL'ом и отлично масштабируется по потокам: можно параллелить поиск через joblib.Parallel или ThreadPoolExecutor.
🔠 Поддержка GPU, что также даёт прирост скорости в десятки раз.
🔠 Гибкость индексов: от точного поиска (Flat) до приближённых структур с квантованием и кластеризацией.

Рассмотрим основные типы индексов:

🔠 IndexFlat - базовая реализация, которая хранит все векторы в RAM и выполняет точный линейный поиск. Работает быстро на малых объемах (<100K векторов), также идеален для отладки или в случаях, если поиск каждый раз нужно осуществлять в разных ограниченных подпространствах векторов (тогда просто запускаете с тем же Parallel:)).
🔠 IndexIVF (Inverted File Index) - предварительно перед поиском он кластеризует всё пространство векторов (например, с помощью k-means).
При поиске сначала выбираются N ближайших кластеров, а затем производится поиск заданной глубины K внутри них.
На моей практике, даже с учётом времени на обучение индекса, IVF ускорил процесс поиска в ~8 раз по сравнению с Flat+Parallel, при этом точность результата по метрикам проявилась только в 5-м знаке после запятой (ещё и в бОльшую сторону! 😎)
Но есть уже озвученное "НО" - такой индекс требует предварительного обучения, и на это нужно время. Поэтому имеет смысл его использовать, если запросы каждый раз делаются из одинакового и фиксированного пространства.
Если захотите воспользоваться IVF, то упомянутые N и K лучше брать как √d и 2–4*(размер топа, который вы ищете) соответственно, где d - количество векторов в базе для поиска.
🔠 IndexIVFPQ (Product Quantization) добавляет к IVF еще одно ускорение - сжимает векторы до компактного кода (например, 8 байт вместо 128 float32). Работает ещё быстрее и экономит память при минимуме потерь в точности. Имеет смысл посмотреть в сторону этого подхода, если у вас порядка миллиарда векторов.
🔠HNSW-семейство индексов (Hierarchical Navigable Small World) - индексы на основе графов малого мира, где каждый вектор представляется как вершина, связанная с соседями в многослойной структуре. Поиск происходит за счёт навигации по графу: сначала на грубом уровне, затем всё точнее.
Такие индексы не требуют предварительного обучения и хорошо подходят для динамических баз, где данные часто добавляются на лету. Отличаются высокой точностью даже при небольшой глубине поиска, но потребляют больше памяти и не поддерживаются на GPU.

Полезные ссылки:
🔠 Официальный репозиторий Faiss.
Там же ссылка на quick start и базу jupyter-ноутбуков с примерами кода на Python
🔠 Ещё пара хороших туториалов с примерами кода тут и тут
⚠️Если решите установить версию с поддержкой GPU, лучше использовать эту

Лёгкой и солнечной недели! ☀️

#mlops@data_easy