Data Mining Camp: как мы вдохновились на год вперед

Как-то в самом начале нового года мы решили совместить приятное с полезным: дружно отдохнуть и поработать. И пригласили сотрудников, наших студентов и экспертов из компаний EMC ^[1], Rosalind ^[2], Yota ^[3], Game|Changers ^[4] провести три дня зимних каникул в домике под Петербургом.

Встреча с друзьями-единомышленниками за городом хороша, чтобы поделиться идеями, написать статью или закончить работу, до которой никак не доходили руки. Для этого мы и организовали выезд на Data Mining Camp. Решили, что будет сауна, настольные игры, контактный зоопарк и – гвоздь программы – хакатон.

На хакатоне ребята при помощи экспертов работали над тремя исследованиями: модель иерархической кластеризации признаков, модель ухода слушателей онлайн-курсов, попробовали улучшить алгоритм Gradient Boosting Machines, а также поучаствовали в международном конкурсе на платформе Kaggle. О том как это было и как ребята продолжают работать над этими идеями под катом…

Потехе час...

Первым делом мы отправились в частный зоопарк ^[5]. Порезвились там, вспомнили детство: каждый нашел развлечение на свой вкус. Кому-то по душе пришелся попрошайка-енот, кому-то верблюд или лама…

… но самые смелые отважились поиграть с большими, но добрыми собаками.

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

Вдохновленные развлекательной программой мы приступили к обсуждению насущных дел. Прямо за игрой в “Манчкин” разговор перешел к образованию в сфере Data Mining и идеям для новых исследований.

… а делу время!

Среди нас были специалисты в области биоинформатики, финансов, телекома и больших данных, которые за чашечкой чая поделились своим исследовательским опытом. Например, после рассказа Владимира Суворова, эксперта из EMC ^[1], о расшифровке генома стрекозы, появился десяток идей, что бы еще такого можно расшифровать и как начать сотрудничество в области биоинформатики.

Эксперты из Rosalind ^[2] поделились своим образовательным опытом. Мы пришли к выводу, что лекции по машинному обучению и анализу данных менее эффективны, чем практика. Хакатоны, конкурсы, реальные задачи от экспертов — вот что нужно, чтобы стать хорошим специалистом. Открытым остался вопрос: “Как совместить онлайн и оффлайн образование? Рекомендовать перед началом обучения прослушать определенные курсы на Coursera? Совсем исключить лекции? Или есть другой путь?”

Тем временем близился хакатон, который мы решили разделить на два независимых потока: участники хакатона #1 проводили свое мини-исследование и писали статью по его результатам, а участники хакатона #2 общими усилиями решали задачу для международного конкурса.

Хакатон #1

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

Предположим, что мы хотим предсказать, какое место наша страна займет на олимпиаде, и решили набрать побольше информации. Об экономике: ВВП на душу населения, объем внешнего долга, минимальный размер оплаты труда, объем импорта и экспорта, количество иммигрантов. О географии: широта столицы, процент площади, занятой горами, площадь всей страны. О прошедших олимпиадах: количество медалей каждого достоинства, количество спортсменов, количество видов спорта, в котором представлена страна, место проведения… В общем, мы так увлеклись сбором данных, что не заметили, как количество признаков превысило количество участвующих стран. А это, прямо скажем, нехорошо, потому что количество уравнений стало меньше количества неизвестных, что ведет либо к несовместности системы, либо к бесконечному количеству решений.

Придется отсеять лишнюю информацию. Обычно для выбора модели с оптимальным набором признаков используют информационные критерии (AIC ^[6], BIC ^[7]). Лучшей считается модель, в достаточной мере полно описывающая данные с наименьшим количеством признаков. Или используют встроенные в модели методы регуляризации, другими словами, надеются, что модель сама справится с некорректными данными. Или понижают размерность данных с помощью метода главных компонент (PCA). Суть метода главных компонент легче всего передать на примере с двумя признаками:

Каждой строке таблицы соответствует точка на плоскости. Проведем через них прямую так, чтобы вдоль нее происходило максимальное изменение данных, она называется первой главной компонентой — PC1. Затем спроецируем все исходные точки на эту ось. Все отклонения от новой оси будем считать шумом. Проверить, действительно ли это шум, можно, поступив с этими остатками так же, как мы поступили с исходными данными — найти в них ось максимальных изменений. Она называется второй главной компонентой (PC2). И так надо действовать до тех пор, пока шум уже не станет действительно шумом, то есть случайным хаотическим набором величин. Пример взят отсюда ^[8], здесь же можно поподробнее почитать про метод главных компонент.

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

Рассмотрим поподробнее получившийся алгоритм. Иерархия будет формироваться с помощью алгоритма кластеризации, наиболее популярный из них — метод k-средних. Количество кластеров k известно заранее, предположим, что мы задали k=2. Выберем случайным образом два признака из нашей модели и начнем формировать вокруг них кластеры. Будем переносить центр кластера, пока суммарное квадратичное отклонение не станет минимальным. Признак в нашем случае превращается в точку в n-мерном пространстве, где n-количество записей в таблице, то есть количество стран, принимающих участие в олимпиаде. О механизме работы алгоритма k-средних можно почитать здесь ^[9].

Теперь наши признаки разделены на две группы. В каждой из них мы выбрали один характерный признак по принципу близости к медиане кластера (1). Снова кластеризуем каждую из получившихся групп, исключив характерный признак (2). Будем повторять до тех пор, пока количество признаков в подгруппе >2.

В итоге получим дерево, в узлах которого к нижним уровням находятся все менее значимые признаки (3). После этого производится отбор. Предположим, что нам нужно оставить 8 признаков. Сначала наша модель обучается только на признаках из верхнего уровня иерархии. Для каждого из них принимается решение на основе вклада признака в модель: оставить в модели, убрать или углубиться в подгруппу. Если вклад достаточно велик — оставляем, если средний — оставляем и углубляемся в подгруппу, если совсем мал — выбрасываем всю подгруппу вместе с ним. Продолжаем спускаться вниз по дереву до тех пор, пока ошибка предсказания нашей модели уменьшается и количество отобранных признаков <8 (4).

Вторая команда работала над созданием модели ухода пользователей MOOC (Massive Open Online Course) на примере трех платформ: Coursera ^[10], Rosalind ^[2] и Stepic ^[11]. Эта задача сейчас очень актуальна для онлайн образования — в одном из интервью Дафна Коллер рассказывала, что только 7% пользователей заканчивают курс на Coursera. Цель — создать модель, которая будет описывать поведение пользователя на разных этапах обучения, чтобы отслеживать активность и найти «узкие места».

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

На хакатоне посчитали не все признаки (не хватило мощностей и рабочих рук), но зато стало понятно, куда ребятам двигаться в дальнейших исследованиях.

Третья команда попробовала усовершенствовать алгоритм Gradient Boosting ^[12]. Этот алгоритм строит модель предсказания из ансамбля «слабых» предсказывающих моделей, которые называют «base-learner» или «базовые кирпичики». «Слабые» модели обучаются на тренировочной выборке, после чего объединяются таким образом, чтобы итоговая модель предсказания становилась точнее на каждой итерации. Обычно используется алгоритм Gradient Tree Boosting, где в качестве «базовых кирпичиков» выступают деревья принятия решений CART ^[13] фиксированного размера. В узлах деревьев принятия решений лежат условия перехода, а в листьях — значения целевой функции. На картинке классический пример дерева принятия решений про пассажиров Титаника (sibsp — количество родственников на корабле):

Ребята задумались, можно ли увеличить точность модели, различным образом смешивая компоненты ансамбля. Были рассмотрены варианты GBM(Gradient Boosting Machines), где ансамбль состоит из SVM ^[14]-регрессий, линейных моделей и всевозможных вариантов деревьев. Пока что стандартный GBM победить не удалось, но работа продолжает кипеть и после окончания хакатона.

Целью всех трех команд было написать статью для участия в международной конференции по машинному обучению ICML ^[15], которая пройдет летом в Пекине.

Хакатон #2

Второй хакатон был посвящен конкурсу от компании Яндекс на краудсорсинговой платформе Kaggle ^[16]. Задача — ранжировать веб-страницы в выдаче на основе предпочтений пользователя. Яндекс предоставил историю почти 6 миллионов пользователей за 27 дней, это около 21 миллиона запросов. Для каждого запроса имелись: id пользователя, список слов в запросе, 10 позиций из выдачи, номер позиции, которую выбрал пользователь, и время каждого действия пользователя. В дополнение к этому были предоставлены данные тестовых сессий за следующие 3 дня.

Нужно было расположить выдачу в тестовых сессиях так, чтобы получить максимальный показатель NDCG (Normalized discounted cumulative gain) ^[17]. Рассмотрим подробнее, что это такое. DCG — discounted cumulative gain или приведенная суммарная эффективность релевантности рассчитывается по следующей формуле:

где i-порядковый номер выдачи, а rel — степень соответствия запросу. По шкале соответствия 0 до 3 первые шесть страниц в выдаче могут быть оценены, например, так: 3,2,3,0,1,2. Рассчитаем приведенную суммарную эффективность релевантности:

и приведенную суммарную эффективность релевантности при идеальном ранжировании:

Нормируем результат, разделив реальный DCG на идеальный:

Эта метрика часто используется в информационном поиске и при оценке ранжирования.

Разобравшись с показателями эффективности, ребята приступили к работе. Подготовленные логи пользовательских запросов заняли более 60 гигабайт, что затруднило применение алгоритмов машинного обучения. Времени до дедлайна оставалось всего-ничего, поэтому было решено оставить данные только о персональных навигационных запросах. Они составили 10% от выборки, то есть 6 гигабайт.

Для того чтобы улучшить текущую выдачу команда решила проверить, есть ли такие пользователи, которые в прошлом вводили тот же самый запрос (query_id). Во многих случаях так и оказалось. Ребята проализировали время посещения этим пользователем определенных документов, частоту кликов и другие параметры в обучающей выборке, а затем использовали эти данные для ранжирования текущей выдачи. Было использовано простейшее правило: веб-документ продвигался наверх, если раньше пользователь с таким же запросом посещал его несколько раз, и среднее время посещения было более 400 t.s.(time stamp — эквивалент времени. По условию время, равное 400 t.s и более, означало релевантность документа пользователю).

По итогам конкурса наша команда преодолела baseline — результат удалось улучшить на 0.6% по сравнению с тем, что предложил Яндекс в качестве образца. Для сравнения, лучший результат в таблице лидеров обошел baseline всего на 1,6%. Вот за такие копейки идет борьба по улучшению качества сервиса.

Впечатления

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

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

Автор: DMwarden

Источник ^[18]