Facebook V: Предсказываем «чекины»

Автор: Том ван де Виле (Tom van de Wiele)

Я выиграл соревнование на Kaggle!

Только что на Kaggle завершилось соревнование «Facebook V: Predicting Check Ins». В этом соревновании участники должны были предсказать место, где пользователь мобильного устройства выполнил чекин (checkin), то есть объявил о своем присутствии. Я принял участие, чтобы приобрести как можно больше новых знаний и постараться попасть в топ 10%, поскольку это была моя первая серьезная попытка участия в подобном мероприятии. В итоге мне удалось превзойти все ожидания и финишировать первым из 1212 участников! В этой статье я расскажу о своем подходе.

Обзор

Далее мы рассмотрим весь процесс от исходных данных до победы в соревновании. Статья содержит следующие разделы:

  • Введение.

  • Исследовательский анализ.

  • Постановка задачи.

  • Стратегия.

  • 1-й этап отбора мест-кандидатов.

  • Инженерия признаков.

  • 2-й этап отбора мест-кандидатов.

  • Модели 1-го уровня.

  • Модели 2-го уровня.

  • Заключение.

Исходный код на R доступен на GitHub. Данная ветка форума на Kaggle содержит более краткое описание моего решения и дальнейшее обсуждение. Если вы участвовали в соревнование, тогда вам будет удобнее начать с форума.

Введение

На странице, описывающей соревнование, содержится следующая информация: «Для данного соревнования сотрудники Facebook создали виртуальный мир, где присутствует более 100000 различных мест, расположенных в квадрате размером 10 км на 10 км. На основе координат и других данных участник должен предсказать место, где был выполнен чекин. Прогнозы должны быть представлены в виде ранжированного списка из трех наиболее вероятных мест. Данные имитируют реальные сигналы с координатами, приходящие с мобильных устройств. Благодаря этому участники имеют возможность ощутить вкус работы в реальных условиях, когда данные осложнены неточностями и шумом. Решение этой задачи имеет большое значение, поскольку противоречивые или ошибочные координаты могут значительно ухудшить качество обслуживания в таких сервисах, как Facebook Check In».

Обучающий набор данных содержит примерно 29 миллионов наблюдений (чекинов). Каждое наблюдение содержит две координаты (x, y), точность координат (accuracy), время (time) и идентификатор места (place_id), где был выполнен чекин. Этот идентификатор является целевой переменной, которую необходимо предсказать для тестового набора данных, содержащего 8.6 миллионов наблюдений. Разделение данных на обучающий и тестовый набор выполнено на основе времени. Данные не предусматривают наличие концепции «пользователь». Все наблюдения являются событиями, а не людьми.

Для каждого наблюдения в тестовом наборе данных необходимо предсказать ранжированный список из трех наиболее вероятных мест. Прогнозы оцениваются с помощью метрики MAP@3. Логика метрики является следующей: если идентификатор истинного места расположен первым из трех предсказанных для данного наблюдения – за данный прогноз выставляется оценка 1; если вторым – оценка 1/2, если третьим – оценка 1/3. Если же в тройке предсказанных мест нет истинного значения, тогда данный прогноз получает оценку 0. Итоговая оценка, на основе которой формируется турнирная таблица, вычисляется как среднее значение оценок прогнозов для всех наблюдений.

Чекины. Различные места обозначены различными цветами.

Исследовательский анализ

Анализ координат в обучающем наборе выявил интересные особенности. Как оказалось, координата x имеет намного больший разброс, чем координата y. Было высказано предположение, что это связано с наличием улиц в виртуальном мире. Кроме того, выяснилось, что разница в разбросе x и y различна для всех мест, следовательно, в этом отношении отсутствуют какие-либо явные пространственные закономерности.

Общими усилиями сообщества было установлено, что время представлено в минутах, а значит, его можно преобразовать в относительные часы и сутки. Таким образом, обучающий набор данных охватывает 546 суток, а тестовый набор данных – 153 суток. Все места находятся в независимых «часовых поясах» с четкими часовыми и суточными ритмами. В процессе анализа не было найдено никаких пространственных закономерностей, связанных с временными ритмами. Следует отметить два отчетливых спада в количестве чекинов в течение обучающего периода.

Самым трудным для интерпретации исходным признаком была точность координат (accuracy). Предполагалось, что этот признак должен сильно коррелировать с разбросом координат, однако по началу существенные тенденции выявить не удалось. Примерно в середине соревнования я все-таки «расшифровал» этот признак, о чем подробно расскажу далее в разделе «Инженерия признаков».

Я написал интерактивное Shiny-приложение, которым вы можете воспользоваться, чтобы самостоятельно исследовать данные.

Постановка задачи

Основная трудность данной задачи – это большое количество классов (мест). Учитывая, что в тестовом наборе содержится 8.6 миллионов наблюдений, возможно около триллиона (10^12) комбинаций место-наблюдение. К счастью, большинство классов имеет очень малую условную вероятность при данных координатах, времени и точности. На форуме в качестве основной стратегии упрощения задачи предлагалось вычислять отдельные классификаторы для множества прямоугольных координатных сеток. Такой подход вполне оправдан, поскольку логично предположить, что пространственная информация содержит определенные тенденции для различных мест. Однако, несмотря на то, что этот подход позволяет упростить задачу, его применение, вероятно, привело бы к потере значительного количества информации, поскольку данные очень разнообразны. Я решил моделировать задачу с помощью одной модели бинарной классификации, поскольку опасался, что в противном случае я получу множество моделей с большой дисперсией.

Стратегия

Единый классификатор для всех комбинаций место-наблюдение было бы трудно реализовать даже при наличии мощного кластера. Мой подход основывается на пошаговой стратегии, в рамках которой условная вероятность места моделируется только для ограниченного набора мест-кандидатов. Схема стратегии представлена ниже:

Схема стратегии.

Исходные обучающие данные (на схеме: Given train data) я разделил на две части в хронологическом порядке примерно в таком же соотношении, которое имеет место для исходных обучающих данных и тестовых данных (на схеме: Given test). После разделения я получил две части исходных обучающих данных, которые далее мы будем называть соответственно: сводные данные (на схеме: Summary period) и обучающие/валидационные данные (на схеме: Train/Validation period). Сводные данные охватывают первые 408 суток исходных обучающих данных. Обучающие/валидационные данные охватывают последние 138 суток исходных обучающих данных и включают в себя чередующиеся пакеты обучающих данных (на схеме: train batches) и валидационных данных (на схеме: validation batches). Тестовые данные, как мы уже говорили, охватывают 153 суток.

Сводные данные используются для создания признаков для обучающих и валидационных данных. Исходные обучающие данные используются для создания тех же признаков для тестовых данных.

Три набора необработанных данных (обучающие, валидационные и тестовые) (на схеме: Raw data) первым делом разбиваются на пакеты (на схеме: Downsampling). Мы стремимся к тому, чтобы пакеты имели как можно больший размер, но при этом для их моделирования хватало доступной нам памяти. Я работал с пакетами, содержащими около 30000 наблюдений, на машине, где было установлено 48 ГБ памяти. Разбиение на пакеты выполняется случайным образом, в результате пакеты обучающих/валидационных данных распределены по всему 138-суточному интервалу.

Уменьшив количество мест-кандидатов с более чем 100000 до 100, далее уменьшаем количество мест-кандидатов до 20 с помощью 15 XGBoost-моделей. Условная вероятность P(соответствие_места)|признаки) (P(place_match|features)) моделируется для всех ~30000*100 комбинаций место-наблюдение, а затем среднее значение вероятностей, предсказанных 15 моделями, служит для отбора 20 наиболее вероятных мест-кандидатов для каждого наблюдения. Эти модели используют признаки, созданные с помощью сводных данных.

Те же признаки используются для создания моделей 1-го уровня. Каждая из 100 моделей 1-го уровня также является XGBoost-моделью и создается на основе ~30000*20 комбинаций. Предсказанные вероятности P(соответствие_места|признаки) (P(place_match|features)) используются в качестве признаков для моделей 2-го уровня наряду с 21 признаком, отобранным вручную. Финальные места-кандидаты ранжируются на основе среднего значения вероятностей, предсказанных 30 XGBoost-моделями 2-го уровня.

Все модели были созданы на основе различных пакетов обучающих данных. Гиперпараметры моделей были настроены с помощью локальной валидации.

1-й этап отбора мест-кандидатов

На первом этапе отбора мест-кандидатов, мы уменьшаем количество потенциальных классов с более чем 100000 до 100 с помощью метода k ближайших соседей. Я анализировал количества ближайших соседей, принадлежащих различным классам, среди 2500 ближайших соседей. При этом важность координаты y была в 2.5 раза больше, чем координаты x. В том случае, если к наиболее распространенным классам принадлежало одинаковое количество соседей, выбор делался на основе средней разницы во времени от момента наблюдения. Такой подход обусловлен смещениями в популярности мест.

Подсчет количеств ближайших соседей был эффективно выполнен с помощью разбиения данных на перекрывающиеся прямоугольные координатные сетки. Размер сетки выбирался как можно более малым, но таким, чтобы 2500 ближайших соседей находились в пределах сетки. Код на R неэффективен по причине наличия нескольких циклов, но основное узкое место (упорядочивание расстояний) было оптимизировано с помощью пакета Rcpp, в результате чего удалось добиться ускорения примерно на 50%. Дальнейшая оптимизация логики не являлась приоритетом, поскольку вычисление признаков выполнялось в фоновом режиме и не мешало мне заниматься другими аспектами решения.

Инженерия признаков

Стратегия инженерии признаков

На третьей неделе восьминедельного соревнования я добрался до вершины турнирной таблицы, используя около 50 признаков. В течение всего оставшегося времени я продолжал разрабатывать новые признаки, чтобы учесть различные тенденции в данных. Я также добавил признаки, подобные наиболее важным уже имеющимся признакам, предполагая, что они позволят смоделировать слабые или незаметные тенденции. Моя итоговая модель содержала 430 числовых признаков. Далее мы обсудим основные из них.

Можно выделить два типа признаков. Для вычисления признаков первого типа были использованы только сводные данные, например, количество исторических чекинов. Признаки второго типа комбинируют сводные данные мест-кандидатов с данными наблюдений. Примером является историческая плотность места-кандидата (historical density of a place candidate) за один год до наблюдения.

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

Координаты

Большая часть из 430 признаков была получена с помощью метода k ближайших соседей. В результате подсчета количества соседей, принадлежащих различным классам, для различных k (1, 5, 10, 20, 50, 100, 250, 500, 1000, 2500) и различных соотношений важности координат (1, 2.5, 4, 5.5, 7, 12, 30) было создано 10*7 признаков. Для примера предположим, что 3 из 5 ближайших соседей тестового наблюдения относятся к классу A, а 2 из 5 – к классу B. Тогда для кандидата A данный признак будет иметь значение 3, для кандидата B – значение 2, а для всех остальных 18 кандидатов данный признак будет равен 0. Еще 70 признаков были получены на основе средней разницы во времени между кандидатом и 70 комбинациями. 10 признаков были созданы на основе расстояния между признаками для разных k и наблюдениями при коэффициенте соотношения 2.5. Эти признаки являются индикаторами пространственной плотности. Еще 40 признаков были созданы на более позднем этапе на основе самых значимых уже имеющихся признаков. Аналогичным образом я выбрал различные k (35, 75, 100, 175, 375) и коэффициенты соотношения (0.4, 0.8, 1.3, 2, 3.2, 4.5, 6, 8). Для всех 40 комбинаций расстояния до наиболее удаленного соседа также были использованы в качестве признаков. Пространственные признаки были разделены на количество сводных наблюдений, чтобы обеспечить эквивалентную интерпретацию обучающих и тестовых признаков.

В дальнейшем я добавил несколько признаков на основе (сглаженных) пространственных плотностей. Другие пространственные признаки базируются на статистике мест, в частности, используется медианное абсолютное отклонение (МАО, median absolute deviation) и среднеквадратическое отклонение (СКО, standard deviation) координат. Также в качестве признака был добавлен коэффициент отношения медианных абсолютных отклонений. Во всех случаях, когда это имело смысл, признаки были релаксированы с помощью сглаживания по Лапласу (additive (Laplace) smoothing). Использовались коэффициенты релаксации 20 и 300.

Время

Вторая по величине часть признаков была создана на основе времени. Количества, подсчитанные за определенные периоды (period counts), я преобразовал в плотности (period density counts), чтобы учесть два существенных спада в частоте. Периоды включают: 27 двухнедельных периодов перед окончанием сводных данных и 27 однонедельных периодов перед окончанием сводных данных. Кроме того, я добавил признаки на основе двухнедельных плотностей, полученных, двигаясь назад во времени в интервале между 75-й и 1-й неделями от наблюдения. При создании этих признаков появились отсутствующие значения, но XGBoost хорошо с ними справился. Также были созданы дополнительные признаки для учета заметного годового ритма некоторых мест.

Недельные количества.

Часовые, суточные и недельные признаки были рассчитаны с помощью исторических плотностей с применением и без применения циклического сглаживания, а также с применением или без применения релаксации. Я предполагал, что существует взаимосвязь между часом суток и сутками недели, поэтому также создал циклические признаки час-сутки. Кроме того, были созданы признаки для суточных 15-минутных интервалов. Я применил циклическое сглаживание с гауссовскими окнами (Gaussian window). Окна были выбраны таким образом, чтобы сглаженный час, час-неделя и 15-минутные блоки отражали различные частоты.

В качестве других временных признаков были использованы экстраполированные недельные плотности, полученные с помощью различных моделей для временных рядов (ARIMA, метод Хольта-Уинтерса (Holt-Winters), экспоненциальное сглаживание). Кроме того, я использовал время с момента окончания сводного периода и время с момента окончания сводного периода до последнего чекина.

Точность координат

Понимание исходного признака, описывающего точность координат, стало результатом создания множества визуализаций. Существует небольшая корреляция между точностью координат и разбросом x и y. Но чтобы заметить ее, точность координат необходимо разбить на группы примерно одинакового размера. Сигнал более точен для диапазона точностей координат 45-84 (вероятно, GPS-данные).

Среднее отклонение от медианы x для 6 групп по времени и 32 групп по точности координат.

Распределение точности координат представляет собой смешанное распределение с тремя пиками, которые изменяются с течением времени. Вероятно, это связано с тремя различными типами мобильного подключения (GPS, WiFi, сотовый). Различные места имеют различные тенденции в отношении точности, поэтому я создал признаки, характеризующие относительные плотности групп точностей. В качестве средней группы точностей был выбран диапазон 45-84. Я добавил относительные плотности мест для 3 и 32 примерно равных групп точностей. Также было обнаружено, что для многих мест координаты связаны с тремя группами точностей. Эта тенденция была учтена посредством дополнительных признаков для различных групп точностей. Следует отметить, что при вычислении ближайших соседей можно было бы учесть группу точностей, но у меня уже не было времени на реализацию этого подхода.

Координата x связана с группой точностей для таких мест, как 8170103882.

Z-оценки

В качестве признаков я также вычислил десятки z-оценок (zscore), показывающих, насколько новое наблюдение вписывается в исторические тенденции для мест-кандидатов. Наилучший результат обеспечили робастные z-оценки: (f-медиана(f))/МАО(f) вместо (f-среднее(f))/СКО(f).

Наиболее важные признаки

Наиболее важными оказались признаки на основе ближайших соседей, в частности, при k около 100 и соотношении координат около 2.5. Часовые и суточные плотности также продемонстрировали большую значимость после сглаживания. Относительные плотности трех групп точностей также оказались среди наиболее важных признаков. Следует отметить интересный и очень важный признак, который описывает суточную плотность за 52 недели до чекина. Наблюдается отчетливая годовая закономерность, которая максимально проявляется для мест с наибольшими суточными количествами чекинов.

Отчетливая годовая закономерность для места 5872322184. Зеленая линия показывает положение во времени за 52 недели до максимального суточного количества.

Файлы с признаками имели размер около 800 МБ для каждого пакета. Я сохранил все признаки на внешнем жестком диске.

2-й этап отбора мест-кандидатов

Признаки, описанные в предыдущем разделе, используются для создания бинарных классификационных XGBoost-моделей на основе 15 различных обучающих пакетов. Мы уменьшаем количество мест-кандидатов до 20, поскольку при наличии 100 мест-кандидатов для каждого наблюдения процесс вычислений является очень длительным. В своем финальном подходе я не использовал подмножества данных (downsampling), поскольку все нули (несовпадения между кандидатом и истинным значением) содержат полезную информацию. Как показывает практика, XGBoost хорошо справляется с несбалансированными данными. Я рассматривал возможность исключить наблюдения, для которых истинный класс не попал в топ 100, но в результате валидационные оценки оказались немного хуже. Причина та же: эти данные содержат полезную информацию! 15 моделей для отбора кандидатов были созданы на основе 142 лучших признаков. Ранжирование признаков по важности выполнено с помощью 20 XGBoost-моделей, обученных на различных пакетах. Гиперпараметры были подобраны посредством локальной валидации. Я усреднил вероятность, спрогнозированную 15 моделями, чтобы отобрать 20 наиболее вероятных кандидатов.

На данном этапе я также исключил наблюдения, относящиеся к местам, имеющим наблюдения только в обучающих/валидационных данных. Такая же фильтрация была применена к тестовым данным.

Модели 1-го уровня

Модели 1-го уровня очень похожи на модели 2-го этапа отбора кандидатов, за исключением того, что 75 из 100 моделей были обучены на одной пятой части данных. Остальные 25 моделей были обучены на 100 кандидатах для каждого наблюдения. 100 базовых XGBoost-моделей были обучены на различных случайных частях обучающих данных. Наилучших результатов мне удалось добиться при глубине деревьев (max_depth) равной 11 и скорости обучения (eta) на уровне (11 или 12)/500 при 500 раундах. Семплирование столбцов (colsample_bytree = 0.6) обеспечило определенное улучшение. Семплирование строк (subsample = 0.5) тоже не повредило и позволило уменьшить время обучения. Я использовал либо все 430 признаков, либо равномерно случайно отобранные признаки из ранжированного по важности списка в пределах интересующего меня диапазона (100-285 и 180-240). Фреймворк для моделей 1-го уровня предусматривал возможность работы не только с XGBoost, но и с различными другими типами моделей. Я экспериментировал с нейронными сетями из пакетов nnet и H2O, но они были либо слишком медленными (H2O), либо слишком смещенными (nnet). Большим преимуществом XGBoost перед описанными реализациями нейронных сетей также является его способность эффективно обрабатывать отсутствующие значения. Кроме того, XGBoost-модели были очень разнообразны, поскольку они обучались на различных случайных пакетах обучающих данных при различных значениях гиперпараметров (скорость обучения, количество признаков, количество кандидатов (20 или 100)).

Модели 2-го уровня

30 моделей 2-го уровня используют прогнозы 100 моделей 1-го уровня и 21 отобранный вручную признак для всех 20 кандидатов. В число 21 признака вошли высокоуровневые признаки, такие как координаты и точность координат, а также время с момента окончания сводного периода. Эффект от 21 добавленного признака был небольшим, но зато совпадал как для локальной валидации, так и для открытой турнирной таблицы (~0.02%). Лучший результат локальной валидации был достигнут при умеренной глубине деревьев (max_depth = 7) и скорости обучения (eta), составляющей 8/200 при 200 раундах. Семплирование столбцов (colsample_bytree = 0.6) позволило немного улучшить результат. Семплирование строк (subsample = 0.5) не ухудшило результат, но опять же позволило уменьшить время обучения. Тройка финальных кандидатов ранжирована на основе среднего значения вероятностей, предсказанных 30 XGBoost-моделями 2-го уровня.

Анализ метрики MAP@3 для локальной валидации показал, что лучшие результаты наблюдаются для точностей координат в диапазоне 45-84. Различие в результатах для валидационных и тестовых данных во многом связано с этим наблюдением. Вероятно, имеет место тенденция в сторону использования устройств, дающих меньшее пространственное отклонение.

Значения MAP@3 при локальной валидации для различных групп точностей.

Заключение

30 команд, занявших верхние позиции в закрытой турнирной таблице, представлены на рисунке ниже. В конце соревнования у меня не было большого отрыва, и Markus также имел все шансы стать победителем. Наши результаты были очень близки с третьей недели соревнования, и мы подталкивали друг друга вперед. Поскольку тестовые данные содержали 8.6 миллионов наблюдений и были разделены для открытой и закрытой турнирной таблицы случайным образом, по своему положению в открытой турнирной таблице можно было достаточно точно судить о положении в закрытой турнирной таблице. Больше всего меня впечатлили подходы, которые использовали Markus (2-е место) и Jack (Japan) (3-е место). Подробнее об их подходам вы можете прочитать на форуме. Другие участники также предложили множество интересных идей.

Результаты в закрытой турнирной таблице (MAP@3). Два участника оторвались от остальных.

Я начал соревноваться на скромном ноутбуке с 8 ГБ памяти, но на второй неделе решил купить более мощную машину за €1500, чтобы ускорить моделирование. Ограниченные ресурсы в начале соревнования послужили преимуществом, поскольку я был вынужден оптимизировать логику создания признаков. Моим лучшим другом в этом соревновании был пакет data.table.

Полное вычисление моего решения на моей машине с 48 ГБ памяти заняло около месяца. Такое невероятно длительное время объясняется необходимостью значительных ресурсов для вычисления признаков на основе ближайших соседей. Тем не менее, в то время как выполнялись вычисления признаков, я постоянно работал над другими составляющими решения, поэтому ускорение этих вычислений все равно не позволило бы улучшить итоговый результат.

Однако следует отметить, что получить результат около 0.62 можно примерно за 2 недели, если сфокусировать внимание на наиболее значимых признаках на основе ближайших соседей. Я рекомендую использовать 3 из 7 коэффициентов соотношения координат (1, 2.5, 4) и исключить промежуточные признаки. Кроме того, можно уменьшить количество моделей 1-го уровня со 100 до 10, а количество моделей 2-го уровня – с 30 до 5. Итоговая оценка от этого существенно не уменьшится (ожидаемое уменьшение составит около 0.1%), при этом вычисления займут меньше недели. Безусловно, вычисления можно выполнять параллельно на нескольких машинах, что еще больше ускорит процесс.

Мне очень понравилось участвовать в соревновании, несмотря на то, что этот период деятельности был одним из самых напряженных в моей жизни. Начало соревнования пришлось на тот момент, когда я писал свою магистерскую диссертацию по статистике, и, кроме того, работал в полный рабочий день. В данных присутствует множество шумных и зависящих от времени тенденций, что стимулировало меня к серьезному анализу. Все это действительно стоило каждой секунды моего времени! Я был вдохновлен работой других победителей Kaggle-соревнований и успешно реализовал свою первую двухуровневую модель. Победа в соревновании это приятное дополнение ко всему тому, чему я научился у других участников. Спасибо всем!

Вам также может понравиться

Добавить комментарий

Ваш e-mail не будет опубликован.

закрыть

Поделиться

Отправить на почту
закрыть

Вход

закрыть

Регистрация

+ =