⁣Adaptive Stochastic Quantile-Based Bucketing: решение для streaming feature encoding

Когда cardinality признака растёт в реальном времени, статические бакеты ломаются. Новые значения попадают в неизвестные категории, старые бакеты перестают отражать распределение, и модель начинает тупить. Переобучать каждый раз — дорого и медленно.

Проблема фиксированной cardinality в streaming
В production ML мы привыкли, что признаки с высокой cardinality, такие как user_id или device_id, кодируют через hash или frequency-based бакеты. Но в streaming-сценариях (кликстрим, фрод-детекция, IoT) cardinality может удвоиться за час. Статическое число категорий M ведёт к коллапсу: новые значения попадают в unknown bucket, старые бакеты смешиваются с новыми, метрики проседают. OneHotEncoder(fixed M) тут бесполезен. Переобучать модель каждую минуту — дорого и нарушает воспроизводимость.

Как работает ASQB
Решение — держать скользящую квантильную карту для каждого признака через TDigest (обновление O(log N)). Новое значение кодируется по его квантилю: делим распределение на M равных интервалов. Главная хитрость — стохастичность: добавляем лапласовский джиттер в границы бакетов, чтобы избежать смещения при резких всплесках cardinality. И адаптивность: M меняется по формуле M(t) = M0 + alpha * sigmoid(delta_cardinality). Если cardinality скакнула, бакетов становится больше — и наоборот.

from tdigest import TDigest
import numpy as np

class ASQBEncoder:
    def __init__(self, M0=10, alpha=1.0, decay=0.9):
        self.td = TDigest()
        self.M = M0
        self.alpha = alpha

    def update(self, value):
        self.td.update(value)
        new_card = len(set(self.td.percentile([0, 100])))
        delta_card = new_card - self.M
        self.M = int(self.M + self.alpha * (1 / (1 + np.exp(-delta_card))))
        jitter = np.random.laplace(0, 0.05 * self.M)
        self.M = max(2, int(self.M + jitter))

    def encode(self, value):
        q = self.td.percentile_of(value) / 100.0
        bucket = min(int(q * self.M), self.M - 1)
        return bucket

Production trade-offs и типичная ошибка
Плюсы: encoding постоянен по latency, не нужно останавливать пайплайн для переобучения. На потоковых задачах прибавка ROC-AUC 3–12% по сравнению с OneHot с фиксированным M.
Минусы: память под каждый TDigest (~10KB на признак — норм, но если признаков тысячи, уже не смешно). Джиттер слегка размывает границы бакетов — при очень стабильной cardinality это даёт небольшой шум.
Типичная ошибка: забывают, что decay в TDigest критичен. Без него старые данные перевешивают, и адаптивность M теряет смысл. Всегда проверяйте, что квантильный скетч забывает старые points согласно стратегии decay (exponential или sliding window).
Практический совет: начинайте с M0 в 2-3 раза меньше ожидаемой финальной cardinality. И используйте логирование метрик распределения бакетов (например, entropy) в production, чтобы вовремя заметить, когда джиттер начинает доминировать.

Вывод: ASQB позволяет кодировать признаки с растущей cardinality в реальном времени без остановки пайплайна, но требует контроля памяти и decay-стратегии, чтобы шум от джиттера не перевесил пользу адаптации.