Pull to refresh

Comments 16

Было бы действительно интересно увидеть какой-нибудь промышленный пример применения Data Mining, в духе Delloite нужно решить следующую задачу и вот так вот, мы её решили — статья про то-то и то-то.

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

P.S. При прочтении сначала показалось, что Gradient Boosting Machines — это практически Random Forest, оказалось, что нет. Если кому-то вдруг тоже так показалось, то разница объяснена в одной из ссылок:
Заголовок
объяснение
The common ensemble techniques like random forests rely on simple averaging of models in the ensemble. The family of boosting methods is based on a different, constructive strategy of ensemble formation. The main idea of boosting is to add new models to the ensemble sequentially. At each particular iteration, a new weak, base-learner model is trained with respect to the error of the whole ensemble learnt so far. The first prominent boosting techniques were purely algorithm-driven, which made the detailed analysis of their properties and performance rather difficult (Schapire, 2002). This led to a number of speculations as to why these algorithms either outperformed every other method, or on the contrary, were inapplicable due to severe overfitting (Sewell, 2011).
Вы попали в самую точку — одна из шишек, которую мы набили на конференциях как раз заключалась в том, что весьма непросто пробить стену непонимания того, что же такое этот data mining (людям на ум вообще частенько приходил майнинг биткойнов).

Пару раз дело доходило до абсурда, когда мы натыкались на букально дремучие предрассудки: заказчик скорее всего имел очень негативный опыт работы в области анализа данных, после чего он проклял не только его, но и весь род математиков, в красках и ярких русских выражениях обвиняя всю математику в шарлатанстве как таковую :)
Это конечно же единичные случаи — куда важнее наглядно и «на яблочках» донести до людей, чем именно анализ данных может быть полезен конкретно им. На конкретно их данных в конкретно их области (например, онлайн игры, маркетинг или анализ соцсетей).

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

P.S. Про градиентный бустинг мы тоже можем рассказать, это одна из основных рабочих лошадок на платформе kaggle, так что наверное хабрасообществу будет интересно узнать и про них тоже (на хабре они упомянались только вскользь).
1. Как попасть на курсы и сколько они стоят если они платные?
2. Будет ли онлайн вариант обучения?
3. Интересно ли сотрудничать с лекторами в этой области?

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

Мы бы хотели сделать эксперимент и устроить платформу вроде этой с задачками как на кеггле, но побить baseline можно только поняв особенность задачи (оверфиттинг, правильная модель, отбор признаков, чистка данных, ...). Платформ с онлайн-лекциями много, например недавно Яндекс выложил пачку отличных лекций, а вот практику пока стоит искать только на kaggle.

Можно попробовать совместить приятное с полезным, те более платформа для проверки задач уже есть и опробована на наших студентах (в рамках классов).
Как отобрать значимые признаки, когда их очень много: десятки и сотни тысяч?

А чем старый добрый FCBF не подходит?
У меня на 800к атрибутах работал, больше не гонял, не надо было.

Хотя есть недостатки, но достаточно быстренький, особенно если атрибуты слабенькие, он их отсеивает моментально.
Честно признаемся, о FCBF мы узнали только что. Мы привыкли к методологии sparse методов вроде lasso и продолжения темы в виде glmnet, тем более их адаптировали и под нелинейные модели и модели смесей регрессий. А можете рассказать побольше про свой опыт? И есть ли реализации на Python/R, поверхностное гугление выдало только feature selection toolbox?

Если говорить об именно нашем опыте с нетривиальным и харкдорным отбором фич, то первой проблемой, с которой мы сталкивались было то, что сложно подобрать адекватную метрику близости в высокой размерности (проклятье!). Мы встречались со случаями, когда в зависимости от типа данных, как корреляции, так и многие другие метрики были слабо применимы (давали заведомо бесполезный и\или неадекватный результат). Особенно все было плохо, когда были очень по-разному распределенные признаки (data fusion). Конкретнее, у нас были условно-нормальные признаки (1000 сенсоров), еще несколько тысяч сильно разряженных бинарных меток (онтологии, но их можно группировать), плюс что-то еще. Можно делать группировку вручную, конечно, и внутри нее проводить свой отбор, но это путь для не ленивых :)

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

Сейчас мы копаем в сторону кластеризации признаков и выделения иерархического дерева признаков с помощью sparse pca. Получается, что в большом иерархическом древе признаков, на каждом уровне всегда будет пара признаков-представителей, которые характеризуют этот кластер признаков целиком (вплоть до уровня листьев). А далее, построив модель на пачке признаков-представителей этого дерева, можно эффективно проводить отбор и копать вглубь, отбирая признаки как раз на уровне моделей (пост-фактум). Это решает вторую нашу проблему, а возможность построить пачку таких деревьев для разных метрик между признаками, по идее, решает и первую проблему. Было бы классно это вообще делать через sparse nca но его пока не изобрели, а нам пока лень :)

Если что-то получится, то можем рассказать про это на хабре, картинки у нас очень клевые получаются :)
У меня чуть другой подход, достаточно отличающийся от общепринятого.
Дело в том, что я пишу высоконагруженные бэкенды, и там каждая оптимизация дает отдачу, а делать в таких условиях PCA на матрицах порядка 10^6 x 10^6 — это имхо из репертуара маркиза де Сада. :-)
Ну и опять же линейный метод, значит кучу всего оставит за кадром.

Я двигаюсь обычно так:

1. Атрибуты должны быть дискретными, лучше бинарными.
Т.е. дискретизация на самых ранных стадиях.

Пример — работа с изображениями. Можно построить дескрипторы на плавающей точке, в 128-мерном пространстве.
А потом искать по ближайшим соседям (высосав из пальца, что метрика евклидова).
А можно взять например случайный набор пар точек в области. И для каждой пары установить в соответствие бит — интенсивность выше у первого пикселя в паре или у второго.
И получаем сразу битовуюю строку бинарных атрибутов, которую можно использовать как напрямую, так и опять же через ближайших соседей (Bag of Words), но уже с Хемминговской метрикой.

Соответственно на таких атрибутах в задачах классификации естественная мера качества — взаимная информация, или ее нормированный аналог symmetrical uncertainty.
И FCBF или mRMR методы показывают себя достаточно неплохо, ну и проклятие размерности там не столь важно.
Опять же — единая мера качества атрибута (т.е. взаимная информация) убирает необходимость кластеризации атрибутов — вместо поиска групп в большом пространстве мы просто располагаем их на одномерной линии.
Я одно время, когда еще не пользовался своей схемой тоже ковырял кластеризацию признаков — спектральную кластеризацию делал.
Ушел оттуда, результаты хорошими не назвать, а задачу расплавить процессор заказчик обычно не оплачивает.

Реализацию FCBF видел в Weka.
В Python не встречал, но вполне может быть.

Я иногда конструирую атрибуты генетическим программированием — задаю грамматику, и потом фильтрую результат, который и определяет fitness function.

А иногда и монте-карло хватает, чтобы обрисовать картину — главное потом фильтровать атрибуты.

Очень просто найти черную кошку в темной комнате — надо лишь кидаться тяжелыми предметами в случайных направлениях и ждать где мяукнет.
:-)

2. Random Forest (или Extremely Random Forest или др. варианты) — наше все.
Не знаю других методов, сравнимых по скорости сканирования (не обучения) с ним при том же качестве. SVM в топку или только на предварительный анализ данных.
Соответственно RF и становится рабочей лошадкой.
GPU в датацентрах конечно появляется, и может что изменится, но пока так.

Ну вот сейчас Semantic Role Labeling на коленке делал — 2-10 документов в секунду (это пока). В то время, как крутые аналоги — один абзац в минуту иногда показывают.
Ну да, качество чуть похуже (пока).
Но когда надо терабайты через мясорубку пропустить — самое оно.

Ну и сам по себе RF — тоже неплохой фильтр атрибутов, то что он не использовал, можно удалять с пути вычислений, а это тоже такты процессора.
Плюс на RF можно делать простенькую кластеризацию (на одноклассовых деревьях например или тренируя против случайного набора), не ахти, но опять же поворот/редукцию координат из произвольного пространства атрибутов в номинальные признаки оно проводит.

И у RF есть неплохое, но незаметное достоинство.
Каждая нода каждого дерева хранит условное распределение вероятностей атрибутов. А из этого очень многое можно вытащить, если уметь готовить.
:-)

Минусы RF общеизветны, из необщеизвестных — при нестандартных методах отбора или создания атрибутов RF падает в оверфит моментально.
FCBF это кстати лечит.

Последние пару лет думаю переползать на Very Fast Decision Trees.
Надо пробовать, для потоковых данных — самое то, плюс concept drift прикручивается проще.

3. У меня правило — чтобы разобраться в алгоритме я его имплементирую.
:-)
А поскольку страдаю наслаждаюсь мазохизмом, то имплементирую на С.
Ну заодно и нет проблем с производительностью.

Поэтому наличие алгоритмов в других пакетах особо не отслеживаю.
С другой стороны для быстро попробовать — большинство мейнстримовых вещей есть в Weka/RapidMiner, формат простой, можно экспериментировать сколько угодно.
Ну а если приспичит — свой прототип всегда можно написать.

Как-то так.

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

PS
Не совсем понял почему атрибуты ищутся после построения модели.
В задаче по DataFusion я тоже не совсем понял проблемы.

Есть ~1к сенсоров (т.е. ~1к ординальных переменных) и ~1к бинарных (онтологии).
Это как бы очень немного и уже на этом можно дерево строить сразу, а если данных мало, то и SVM на одном ядре все решит.
А если сэмплов много — то надо делать выборку и ансамбль.
Тут можно вообще без фильтрации обойтись.

Т.е. для PCA подобных методов — да, проблемы.
Но неясно насколько тут нужны такие методы.
И опять же — выход сенсора гауссианой будет только в спецификации сенсора, а что в реальности надо на реальных данных смотреть.
вкусно! а как насчет imbalanced modeling для данных 1 к 10000? кол-во позитивных классов около 5k-20k? в данный момент интересует именно такие модели
А негативных классов получается 50М — 200М?
Серьезная задача.

Я не скажу, что на таких моделях всегда весело выходит.
И там кстати еще сильно зависит от того, что надо минимизировать — FP, FN или симметричную ошибку.

Один из самых простых методов вот какой.
При тренировке Random Forest как известно для тренировки каждого дерева делается подвыборка с повторениями.
У Бреймана, в оригинальной трактовке, надо брать размер выборки идентичный исходному сету, а так как после выборки с повторениями останется примерно 1/3, то на ней и ошибку дерева считают.

Но никто не запрещает сделать выборку по другому.
Например набрать одинаковое количество позитивных и негативных семплов.
Причем именно выборкой с повторениями, т.е. имея например 5К позитивов и 100К негативов — можно вполне работать с выборкой 10к позитивов + 10к негативов, — для каждого дерева естественно уникальной.
Правда надо забыть о мере оценки на оставшихся сэмплах, их может просто не остаться.

Этот подход не всегда решает проблему, но бывает помогает.

Есть еще способ — нестандартная асимметричная Impurity function (полином со смещенной модой обычно), ну или сплит-критерий доработанный напильником.
Не скажу, что мне понравились результаты, но я пробовал всего пару раз, наскоком.
Так что мог чего-то не заметить.

Т.е. общего решения так не скажу.

Если возникает такая задача — то первым делом я применяю метод, описанный в начале коммента.
А там уже копаю глубже.

Но вот 1 к 10К так даже не могу вспомнить, пожалуй не было в моей практике.
оптимизировать надо все ) но акцент лучше на TP. Задачи на самом деле часто встречающиеся, с imbalanced ratio 1 к 100, 1 к 1000. Мне посоветовали посмотреть на outlier detection, плюс идет интенсивное обсуждение «а необходим ли полный набор imbalanced или умная выборка достаточна?»
Логично выглядит натренировать one-class систему на негативах, получить распределение вероятностей негативов и скомбинировать с стандартным бинарным классификатором.
Встречал такие советы.

И для undersampled positives в этом видна логика, полной информации не хватает для полноценного бинарного классификатора, и ее можно попытаться добрать из распределения негативов.

Но у меня такие штуки работали достаточно плохо, в первую очередь потому, что одноклассовые системы сами по себе дают ошибку побольше, чем бинарные классификаторы.
И редко добавляют ту информацию, которую планировалось добрать.

Но вообще надо пробовать, данные всегда разные и что не работает на одних сетах — работает на других.
Иногда очень странные закономерности выскакивают, предвидеть которые достаточно сложно.
краткий обзор литературы по imbalanced classification (если это интересовало): тут

слайды с одной из летних школ, где автор рассказывал про imbalanced classification:
части 1, 2 и 3
спасибо, тема мне интересна
1. Они бесплатны. Попасть студентам можно через набор (тестовые задания + собеседование — пока не знаем, когда будем делать новый), а экспертам — просто написать нам =)
2. Мы бы очень хотели, но пока просто не хватает времени на его организацию. Если вы можете как-то помочь, то это бы ускорило процесс появления он-лайна. У нас есть несколько идей как можно это сделать круто, очень хотелось бы запустить демку в ближайшие месяцы
3. Конечно! Можем организовать телемост

А можете более подробно про систему рассказать? Какие алгоритмы вы использовали?
А киньте в меня списком ваших публикаций, пожалуйста?
Sign up to leave a comment.