Простые методы анализа данных

Недавно меня попросили выступить с лекцией на открытии одного хакатона, обычно я не очень люблю подобные мероприятия (они не очень продуманы, задачи искусcтвенные и с ликами, победителей определяют по «качеству» презентаций и т.п.). Но это мероприятие проходило в МГУ, поэтому я решил поддержать начинание в стенах родного университета. Чтобы рассказать что-то релевантное всем слушателям, которые могли быть очень неоднородны по знаниям и умениям, я выбрал тему, которую пропагандировал несколько лет назад… решать можно (и часто нужно) простыми методами, буквально в несколько строк. Ниже сокращённое описание доклада.

simple.jpg

Анализ данных всегда начинается с разведывательного анализа данных (EDA), который, кроме основной цели «понять, как устроены данные», имеет ещё несколько важных подцелей:

  • найти «волшебные признаки» (которые почти решают задачу, или с помощью которых чётко видны какие-то паттерны),
  • понять, как «меняются признаки» (насколько можно верить данным или синтезируемым признаковым описаниям при изменении времени или категорий объектов),
  • использовать контекст (= экспертные знания, нашу интуицию и т.п.),
  • выявить информационные утечки (не содержат ли описания явно/неявно  лишнюю информацию),
  • построить простые бенчмарки (алгоритмы в несколько строчек кода, которые надёжны, интерпретируемы и т.п.).

Забавно, но часто бывает, что полученный в рамках (качественной!) разведки бенчмарк становится финальным алгоритмом (как раз по причине простоты и надёжности). В бизнесе так бывает существенно чаще, но иногда это можно наблюдать и в спортивном анализе данных, где борьба идёт за доли процентов.

Классификация сигналов в 34 символа

Когда-то (в докэгловскую эпоху — в 2008 году) я принимал участие в соревновании «Ford Classification Challenge».  Необходимо было разработать алгоритм, который по сигналу датчика детектирует поломку. Сигналы классов: 1 (есть поломка) и 0 (нет) показаны на рис. 1.

signals_.png
Рис. 1. Сигналы разных классов в задаче FCC-2008.

Здесь, чтобы не загромождать картинку, показано всего 4 сигнала, но если проанализировать большее число, то будет заметно, что сигналы

  • непериодические (хотя и напоминают колебания),
  • не содержат заметных паттернов,
  • неоднородные.

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

means_.png
Рис. 2. Средние значения сигналов в начале и конце.

Кроме того, не находятся и волшебные признаки (по которым классы неплохо разделялись)… Когда фантазия по придумыванию признаков заканчивается, можно «поменять сигнал». Например, придумывать признаковое описание не самого сигнала, а его производной, см. рис. 3. На первый взгляд, на рис. 3 не видно ничего хорошего…

diff_.png
Рис. 3. Среднее и дисперсия модуля производной.

Но если увеличить масштаб…

diff_large.png
Рис. 4. Увеличение рис. 3.

Видно, что «хвостик» облака точек целиком состоит из объектов класса 0, т.е. если у сигнала небольшое среднее модуля производной, то, скорее всего, он соответствует нормальной работе механизма. Если покопать в эту сторону, то выяснится, что это просто следствие того, что в «нормальных» сигналах производная чаще обращается в ноль, см. рис 5.

_feature.png
Рис. 5. Среднее модуля производной vs число точек с нулевой производной.

Казалось бы мы нашли волшебный признак — число точек (понятно, что лучше взять процент), в которых производная обратилась в ноль! Но давайте на этом не остановимся… Как можно обобщить выражение, которое подсчитывает число точек с нулевой производной? На рис. 6 показано два способа:

  1. Вместо подсчёта числа точек, в которых разница текущего и следующего значения равна нулю, можно задаться некоторым порогом (чтобы разница отличалась не больше, чем на этот порог).
  2. Можно считать совпадения не соседних значений, а вообще — все совпадения, которые есть в сигнале (это, правда, не обобщение, а модификация идеи).
_2formulas
Рис. 6. Два обобщения формулы.

На рис. 7 показана диаграмма рассеивания в координатах двух новых признаков, построенных по обобщениям (1) и (2). Обобщение (1) провалилось, но зато обобщение (2) оказалось идеальным признаком! По нему обучающая выборка разделяется со 100%-й точностью!

_new_features.png
Рис. 7. Диаграмма рассеивания по обобщениям волшебного признака.

После окончания соревнования выяснилось, что и на тестовой выборке точность также 100% (тогда не было публичных турнирных таблиц, каждый участник делал всего одну отсылку, по которой и считалось качество) — она была лишь у одного участника и была получена с помощью 34 символов кода в системе Matlab

2*((sum(diff(sort(X'))==0)<20)'-1)

Чтение мысли с помощью параллельного переноса

Ещё одна история из давних времён… В начале 2000х проводилась серия соревнований «Brain Computer Interface», в которых предлагались задачи анализа сигналов головного мозга. В частности, сейчас я расскажу об одном решении бинарной классификации кортикограмм. Особенность задачи состояла в том, что обучающая и контрольная выборки были собраны в разные дни… для сигналов головного мозга это означает, что они будут очень непохожими (меняется эмоциональное состояние испытуемого, сопротивление проводников, даже точки установок электродов для снятия сигналов).

На рис. 8 показаны диаграммы рассеивания по нескольким придуманным признакам. Видно, что тестовая выборка лежит в стороне… но по форме и некоторому зазору между двумя облаками точек она очень похожа на обучающую.

_f_space.png
Рис. 8. Признаковое пространство в задаче классификации кортикограмм.

Поэтому в этой задаче решение было примитивным… пороговое правило по очень простому признаку. Порог выбран не с помощью скользящего контроля на обучении (как принято), а просто «по картинке» (верхнее облако теста — класс 1, нижее — класс 0).  Это, кстати, обеспечило 3е место в соревновании, в котром принимали участие лаборатории, специализирующиеся на BCI (первое место заняла китайская лаборатория, использовавшая SVM над CSSD + FDA + WM + FDA).

Кстати, чуть позже при решении подобных задач (когда обучение и тест распределены по-разному), я применял такой приём: находил преобразование признакового пространства, которое «накладывает» контрольную выборку на обучающую. В данном случае эти две выборки совмещаются небольшим поворотом и параллельным переносом.

Утечки («лики») в данных

Сейчас уже ликами никого не удивишь и рассказы победителей разных соревнований на 70% состоят из того, как они нашли что-то в данных, от чего зависит решение (хотя это и не может быть использовано при реальной эксплуатации алгоритма — только для фиксированного набора данных).

Автор первый раз столкнулся с ликами где-то 6 лет назад на платформе crowdanalytix. Там решалась задача определения реакции пользователя на рассылку: откликнется (1) или нет (0). Упрощённо (выбрасывая некоторые признаки) обучающая таблица выглядела так:

_table

Первое что надо сделать, когда есть информация о действиях клиента — вычленить отдельных и взглянуть на них. В этой задаче клиент идентифицировался уникальной парой (id, регион). Если теперь упорядочим подтаблицу, содержащую информацию об одном клиенте по признаку «сколько предложений», то получим что-то типа

_table2.png

Нетрудно видеть, что если какое-то предложение было успешным (y=1), то число успешных предложений увеличивалось на единицу в следующей строке. Понятно, что даже если y нам не известен он почти полностью (кроме последнего значения) восстанавливается по парам (число предложенией, число успешных) для каждого клиента! Это следует просто из названий признаков. Любопытно, что только 5 участников из 55 тогда заметили это (т.е. использовали смысл признаков для решения задачи). Полезно также отметить, что культура решения задач заметно выросла за 6 лет. Думаю, сейчас больший процент решателей понимают, что названия признаков тоже важны.

Кстати, подобный лик повторила компания WikiMart, когда устраивало своё соревнование. Тогда в данных был признак «число страниц в сессии», «номер страницы по порядку посещения», нужно было определить, является ли текущая страница последней в сесии пользователя…

kNN жив!

Не всегда задачи решаются сложными методами. Есть простые и довольно универсальные методы, которые работают. Например, метод k ближайших соседей (kNN) и различные его обобщения. В соревновании VideoLectures.Net Recommender System Challenge нужно было разработать рекомендательную систему, причём, в одной из подзадач — для работы в режиме холодного старта (cold start): надо рекомендовать новые видео (для них нет статистики просмотров) для совершенно нового пользователя (для которого нет истории поведения, но есть информация о первом просмотренном видео) на ресурсе видеолекций. Простая идея: давайте синтезируем «хорошую» метрику на множестве видео-лекций и решим задачу обычным ближайшем соседом (к уже просмотренной лекции порекомендуем самые похожие из новинок).

А как сделать метрику? Легко придумать метрики для частей описания видео-лекции:

  • Сравнение категорий видео (хэмингово расстояние — совпадают или нет)
  • Сравнение авторских коллективов (косинусная мера сходства на характеристических векторах авторов)
  • Сравнение языков (хэмингово расстояние — совпадают или нет)
  • Сравнение названий (любая метрика над текстами)
  • Сравнение описаний (любая метрика над текстами)
  • и т.п.

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

Резюме

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

Реклама

Простые методы анализа данных: Один комментарий

  1. Про сигналы просто огонь. Как математик в анамнезе, считаю что на кончике пера можно получить элегантное и точное решение достаточно часто. Если нет, то тогда начинаются инструменты.. 🙂 все ведь упирается в данные.

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

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход /  Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход /  Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход /  Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход /  Изменить )

Connecting to %s