Привет, Хабр!

Сегодня мы рассмотрим как спасаться от «эффекта соседа», рандомизируя не пользователей, а их кластеры в A/B тестах.

У классического AB-теста есть аксиома SUTVA: мол, результат конкретного юзера зависит только от его собственной ветки «treatment / control». Реальность улыбается и кидает в лицо соцсетью, где лайк друга поднимает и твою вовлечённость, курьером, который обгоняет коллег и заражает их скоростью, и cпасибками «приведи друга — получи бонус». Итог — наблюдения больше не независимы.

Внутрикамерный жаргон это называет network interference. Чем плотнее граф связей, тем сильнее лечение «просачивается» за контрольные границы.

Формируем кластеры так, чтобы сосед не испортил эксперимент

Графовые кластеры

Если у вас есть граф взаимодействий, вам крупно повезло. Это значит, что у вас есть карта влияния. Типичные примеры:

• друзья в соцсети

• пересекающиеся заказы одного курьера

• лайки/репосты/переписки между пользователями

• любые “заражаемые” события

Louvain кластеризация

Louvain — быстрый алгоритм детектирования сообществ. Он итерирует локальные улучшения modularity (насколько плотна связь внутри кластера по сравнению с вне его), и сам подбирает число кластеров.

Пример пайплайна:

import networkx as nx
import pandas as pd
import numpy as np
import community  # python-louvain
from collections import defaultdict

# 1. Считываем граф (например, взаимодействия между юзерами)
G = nx.read_edgelist("edges.csv", delimiter=",", nodetype=int)

# 2. Louvain-кластеризация
partition = community.best_partition(G, resolution=1.0)

# 3. Преобразуем в DataFrame
df = pd.DataFrame({
    "user": list(partition.keys()),
    "cluster": list(partition.values())
})

# 4. Назначаем treatment по кластеру
clusters = df["cluster"].unique()
np.random.seed(42)
treat_map = dict(zip(clusters, np.random.binomial(1, 0.5, size=len(clusters))))
df["treatment"] = df["cluster"].map(treat_map)

resolution=1.0 — крутите это значение, чтобы контролировать средний размеркластера. Больше — более мелкие группы.

Проверяйте итоговую дисперсию по кластерам (размер, средние значения ключевых метрик). Иногда алгоритм выделяет супер-кластеры из 80% графа. Это не очень.

df.groupby("cluster").size().describe()

Leiden: стабильнее, но чуть сложнее

Если Louvain вас не устраивает (может быть нестабильным, особенно на фрагментированных графах), можно прыгнуть в Leiden. Он сохраняет плюсы Louvain, но даёт гарантии связности кластеров и быстрее сходится на больших графах.

pip install leidenalg igraph

import igraph as ig
import leidenalg
import pandas as pd
import numpy as np

# 1. Загружаем ребра
edges = pd.read_csv("edges.csv")
g = ig.Graph.TupleList(edges.itertuples(index=False), directed=False)

# 2. Кластеризация
partition = leidenalg.find_partition(g, leidenalg.ModularityVertexPartition)

# 3. Назначаем кластеры
user_cluster_map = {}
for cid, cluster in enumerate(partition):
    for node in cluster:
        user_cluster_map[g.vs[node]["name"]] = cid

df = pd.DataFrame(list(user_cluster_map.items()), columns=["user", "cluster"])

# 4. Рандомизация
np.random.seed(42)
clusters = df["cluster"].unique()
df["treatment"] = df["cluster"].map(dict(zip(clusters, np.random.randint(0, 2, size=len(clusters)))))

В обоих подходах вы получаете не просто рандом юзеров, а рандом “островов”, где влияние течёт внутри, но не снаружи. Граф не всегда готовый — вес рёбер можно собирать как count(shared_sessions) или similarity(metrics).

# примитивная агрегация графа взаимодействий
interactions = pd.read_csv("events.csv")
edges = interactions.groupby(["user_a", "user_b"]).size().reset_index(name="weight")
edges = edges[edges["weight"] > 5]  # фильтрация слабых связей

Randomized Graph Cluster Randomization

Если хочется снизить дисперсию (ибо стандартная GCR может быть шумной, особенно на малых данных), можно применить мультиитеративную схему:

• Делаете несколько кластеризаций (например, с разными random seed)

• В каждой — разный assignment

• Затем агрегируете результат

Это чуть труднее, но мощность вырастает. Выглядит примерно так:

all_assignments = []

for seed in range(10):
    np.random.seed(seed)
    partition = community.best_partition(G)
    cluster_ids = list(set(partition.values()))
    treat_map = dict(zip(cluster_ids, np.random.binomial(1, 0.5, len(cluster_ids))))
    
    temp = pd.DataFrame({
        "user": list(partition.keys()),
        "cluster": [partition[u] for u in partition],
        "treatment": [treat_map[partition[u]] for u in partition]
    })
    all_assignments.append(temp)

# Агрегируем: кто чаще в treatment — тем выше экспозиция
from functools import reduce
df_agg = reduce(lambda left, right: pd.merge(left, right, on="user", how="outer"), all_assignments)
df_agg["treatment_mean"] = df_agg.filter(like="treatment").mean(axis=1)

Георандомизация — когда у нас нет графа, но есть карта

У вас нет графа, но вы понимаете, что поведение зависит от гео, города, района, улицы. Это значит: пора перейти к кластеризации на карте.

Типовой пайплайн:

1. Бьём карту на ячейки (например, S2, H3, квадраты)

2. Считаем фичи по каждой ячейке: число заказов, пользователей, плотность

3. Кластеризуем эти фичи

4. Назначаем treatment на кластеры или внутри пар-близнецов

import geopandas as gpd
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans

# Загружаем гео-ячейки
tiles = gpd.read_file("s2_tiles.geojson")

# Вычисляем фичи
features = tiles[["avg_orders", "courier_density", "users_count"]].fillna(0)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(features)

# Кластеризация
kmeans = KMeans(n_clusters=tiles.shape[0]//2, random_state=42)
tiles["cluster"] = kmeans.fit_predict(X_scaled)

# Назначаем лечение
np.random.seed(42)
tiles["treatment"] = tiles["cluster"].apply(lambda x: np.random.randint(2))

Если у вас карта — обязательно визуализируйте, не лежат ли соседние кластеры рядышком:

tiles.plot(column="treatment", cmap="bwr", legend=True)

Как считать метрики, когда наблюдения больше не независимы

Аггрегация на уровне кластера

Первый (и часто достаточный) шаг — сворачиваем всё до одного числа на кластер, а дальше обычный t-test:

agg = df.groupby("cluster").agg(conv_rate=("conversion", "mean"),
                                treat=("treat", "first"))
stats.ttest_ind(agg[agg.treat==1].conv_rate,
                agg[agg.treat==0].conv_rate,
                equal_var=False)

Минус: теряем информацию о гетерогенности юзеров внутри.

Cluster-robust стандарт-эрроры

Если хочется регрессию с ковариатами, используем sandwich-оценки:

import statsmodels.formula.api as smf

m = smf.ols("spend ~ treat + premium_user + C(device)", data=df).fit(
        cov_type="cluster", cov_kwds={"groups": df["cluster"]})
print(m.summary())

Но как жить, когда кластеров мало (часто <50)? Тут классический CRSE валится. Решение — wild cluster bootstrap: перетасовываем знаки ошибок внутри кластера и строим эмпирическое распределение t-статистики.

Randomisation inference

Когда доверие к асимптотам равно нулю, идём к первоисточнику — самому факту рандома. Генерируем все (или много) перестановок кластерных assignment-ов и сравниваем свою метрику с распределением под нулём:

def att(cl_assign):
    merged = agg.copy()
    merged["fake"] = merged["cluster"].map(cl_assign)
    return (merged.query("fake==1").conv_rate.mean()
          - merged.query("fake==0").conv_rate.mean())

obs = att(dict(zip(agg.cluster, agg.treat)))
perm_stats = [att(dict(zip(agg.cluster, np.random.permutation(agg.treat))))
              for _ in range(5000)]
pvalue = (np.abs(perm_stats) >= abs(obs)).mean()

Самое приятное — не нужно делать никаких предположений о форме распределения.

Обзор методов и где применять

Когда метод ломается и как это чинить

• Мало кластеров — мощность падает. На практике берут минимальный размер = 25, иначе резервируют фичу до накопления юзеров.

• Кластеры «текут»: курьер ушёл в другой район. Либо фиксим границы раз в сутки и лочим assignment, либо вводим buffer-зону без эксперимента.

• Переплетение графа: даже с GCR бывает residual interference через «длинные» рёбра. Помогает рекурсивное дробление + edge-cut-penalty.

• Сложно объяснить бизнесу: гео-рандомизация спасает — «этот регион на рекламе, этот без». Uber делал именно так, когда выводил новые цены в Eats.

• Неоднородная экспозиция: вводим взвешенные метрики (например, доля друзей на лечении) и анализируем непрерывный «дозаж».

Итоги

Кластерная рандомизация — базовая необходимость, когда пользователи влияют друг на друга, как курьеры на скорость или друзья в соцсетях. Всё это требует некоторых усилий, но и бережёт вас от ложных инсайтов. Делитесь в комментариях своими кейсами.

Если вы работаете с данными и хотите повысить качество своих экспериментов, приглашаем вас на серию открытых уроков, которые пройдут в рамках курсов по аналитике:

• На уроке «Data Science — это проще, чем кажется!» (10 июля, 18:00) вы познакомитесь с основами работы с данными и получите необходимые знания для анализа результатов A/B тестов и не только.

• Вебинар «Random Forest — мощный метод ансамблирования в ML» (16 июля, 18:00) позволит углубиться в работу с зависимостями и сложными структурами данных — навыки, которые пригодятся при кластеризации и моделировании поведения пользователей.

• А урок «Как строить визуализацию на больших данных: Superset + ClickHouse» (15 июля, 20:00) поможет вам научиться наглядно представлять большие объёмы информации и делать выводы, опираясь на качественный визуальный анализ.

Присоединяйтесь, чтобы расширить свои аналитические возможности и получить новые практические инструменты.