В прошлые выходные в Музее Москвы проходила выставка, в рамках которой Билайн проводил хакатон. Я, на всякий случай, решил сходить. Была предложена интересная задача: дан граф, в вершинах абоненты, в рёбрах записано число звонков одного абонента другому, их продолжительность и число смсок. Данные выглядели вот так:

A,B,x_A,x_B,c_AB,d_AB,c_BA,d_BA,s_AB,s_BA
941235,666804,0,1,1,20,1,22,0,0
604328,367223,1,0,0,0,5,1364,0,0
932768,977234,0,0,1,168,0,0,0,0
395101,677107,0,1,1,160,0,0,0,0
250712,102647,0,0,0,0,3,456,0,0
510653,896558,0,0,139,50954,22,2990,0,0
...

A, B — абоненты, x — оператор, c — число звонков, d — продолжительность разговоров, s — число смсок. Всего ~6 000 000 рёбер. Кроме этого был секретный набор рёбер, которые заранее случайным образом удалили из графа. Предлагалось угадать, что это были за рёбра. То есть по известному набору связей сказать, какие ещё связи могу появиться.

Первым делом я взял 10 000 пар абонентов, между которыми была связь и 10 000 пар, между которыми связи не было. Два основных отличия заключались в следующем:

1. Если абоненты соединены, то почти всегда у одного из них оператор 0. Так получается, потому что Билайн обладает информацией только о своих клиентах
2. Если абоненты не соединены, то у них почти всегда нет общих контактов.

То есть, грубо говоря, моё решение заключалось в следующем: если у пары абонентов, есть хотя бы один общий контакт и хотя бы один из абонентов пользуется оператором 0, то добавляем между ними связь. Проблема заключалась только в том, что в графе было ~1 000 000 абонентов и в лоб проверить сколько общих контактов у каждой пары не получалось. Тут на помощь в очередной раз приходит алгоритм, который уже два раза упоминался на этом сайте, в статьях про поиск похожих групп в ВК и про поиск связанных запросов. Коротко опишу суть. Пускай есть 5 рёбер:

A    B
1    10
2    10
3    10
1    11
2    11

Абоненты 1 и 2 пересекаются по двум контактам 10 и 11. Сгруппируем рёбра по B и для каждой группы выпишем все паросочетания A:

1    2
1    3
2    3
1    2

Посчитаем частоту всех паросочетаний и, о чудо, у пары 1, 2 частота 2. Этот алгоритм хорошо ложиться на парадигму мап-редьюс, поэтому здесь опять очень пригождается нано-хадуп на 20 строчек.

Чтобы проверить на сколько качественным получается решение, я убрал из графа 20% рёбер и попробовал их угадать. В качестве метрики организаторы использовали f1 score. Если угадывать случайно f1 получается ~0. Бейзлайн, который предоставили организаторы набирает ~0.02. Моё решение — ~0.07. Оказалось, что при проверке не учитывается направление рёбер, поэтому f1 получается немного выше — ~0.08.

Ещё я попробовал учесть длительность разговоров. Действительно, один общий контакт, с которым оба абонента общались только один раз и недолго, совсем не означает, что абоненты должны быть как-то связаны. Но почему-то на практике никакого прироста в качестве я не получил.

Решение Артема Ерохина:

В целом, я отталкивался от простого измышления — связывал двух абонентов через третьего по интенсивности звонков. От идеи использования СМС в качестве такой меры я отказался, т.к. по ним получалось, что результаты концентрировались у слишком большого или слишком малого числа СМС. Со звонками было получше. Возможно, для большей точности следовало взять и СМС, но времени поиграться не было, т.к. спохватился я только во вторник вечером.

При таком выборе идеи для решения, получилось, что я взял пары абонентов, для них вычислил интенсивность звонков (в качестве меры интенсивности, я взял среднее гармоническое для среднего количества минут в пересчете на один звонок для исходящих и входящих вызовов).
Потом я решил отобрать из них только те пары, которые превышают какую-либо перцентиль (в итоге я остановился на перцентили уровня 0.99, что полнейший бред, но значений получалось много, а времени на расчеты — мало). И дальше искал среди оставшихся пар совпадения, чтобы соединить через общий элемент.

Наверное, если бы я продолжал дальше, я бы еще поигрался с параметрами. И может получилось бы что-нибудь интересное. Но, увы, я стартовал слишком поздно. Поэтому закономерный результат на уровне рандома, а может даже хуже.

Мораль одна: спешка — не лучший союзник в деле анализа данных.