Pull to refresh

Comments 47

про минимальность глубины дерева для шариков не верно. например, на втором уровне вместо 8 можно было взять 4 и на следующем уровне уже закончить. для одномерного множества количество условий очевидно считается и минимальная глубина достигается, в том числе, на максимально сбалансированном дереве. но так как важна целая часть логарифма, а общее число разбиений далеко не степень двойки, то и другие деревья могут быть «оптимальны» с точки зрения глубины. Дерево из статьи оптимально в том плане, что мы «отщипили» самую большую группу наиболее быстро

а где что-либо говорится про "минимальность глубины дерева для шариков"?

уже частично поправили:
Можно убедиться в том, что построенное в предыдущем примере дерево является в некотором смысле оптимальным – потребовалось только 5 «вопросов» (условий на признак x), чтобы «подогнать» дерево решений под обучающую выборку, то есть чтобы дерево правильно классифицировало любой обучающий объект. При других условиях разделения выборки дерево получится глубже.

здесь раньше были не 5 вопросов, а глубина. поэтому и последнее процитированное предложение про глубину теперь выглядит вырванным из контекста. Спасибо, что поправили. Обидно, что сделали это тихо, отчего появились вопросы ;)

я ничего не правил. Если что-то серьезное правлю, ставлю UPD
В репозитории в ipynb-файле та же фраза, что и сейчас.

ок. видимо сложилось вкупе со фразой
При других условиях разделения выборки дерево получится глубже.

как я написал выше, может получится и менее глубоким.
В любом случае, хорошо что пишите, а то народ играет в «кубики», меняя параметры, а что за этим стоит не всегда понимают
Зануда-mod on

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

Зануда-mod off

graphviz не обязателен. Достаточно создать dot-файл методом export_graphviz из sklearn.tree и дальше отрендерить этот dot-файл либо c помощью pydot (pip install pydot) либо онлайн-ковертером.

Конечно можно. Но это никак не поможет запуститься
!dot -Tpng '../../img/age_sal_tree.dot' -o '../../img/age_sal_tree.png'

А комментарий был именно про это.

Именно поэтому первый раз, когда в коде появляется вызов dot (в спойлере "Код для отображения дерева"), я пишу


# для этого понадобится библиотека pydot (pip install pydot)
!dot -Tpng '../../img/small_tree.dot' -o '../../img/small_tree.png'

Очевидно, если не установить pydot, не выполнится и команда.

Установка pydot не помогла. Нашел другой вариант для Windows: и посмотреть и сохранить дерево:

from sklearn.tree import DecisionTreeClassifier
clf_tree = DecisionTreeClassifier(criterion='entropy', max_depth=10, random_state=17)
clf_tree.fit(df_train, y)

from sklearn import tree
from IPython.display import Image
import pydotplus

dot_data = tree.export_graphviz(clf_tree, feature_names=df_train.columns, out_file=None)
graph = pydotplus.graph_from_dot_data(dot_data)
graph.write_pdf('df_train.pdf')
graph.write_png('df_train.png')
Image(graph.create_png())
Как вариант для пользующихся docker

  1. Устанавливаем пакет в запущенный контейнер
    sudo docker exec -u 0 -i -t mlcourse_open /usr/bin/apt install graphviz
    
  2. Конвертируем командой в jupyter-notebook
    !dot -Tpng '../../img/small_tree.dot' -o 'small_tree.png'
    
  3. Отрисовываем в Markdown-ячейке jupyter-notebook
    ![title](../../img/small_tree.png)
    

В файле настроек (Dockerfile) предлагаемого в курсе докер-контейнера уже прописана установка pydot. Graphviz не обязательно ставить, тут это будет из пушки по воробьям.

Мне кажется, вы заблуждаетесь. Выполняя !dot получаем вывод:
/bin/sh: 1: dot: not found


И и при этом
pip show pydot
Name: pydot
Version: 1.2.3
Summary: Python interface to Graphviz's Dot
Home-page: https://github.com/erocarrera/pydot
Author: Ioannis Filippidis
Author-email: jfilippidis@gmail.com
License: MIT
Location: /usr/local/lib/python3.5/dist-packages
Requires: pyparsing


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

Согласен, GraphViz указан как dependency в репозитории pydot. Значит, он у меня уже был установлен, а я не заметил.
С путем к pydot тоже приходилось повозиться, в случае Windows вообще не берусь комментировать, в случае *nix помогает StackOverflow, хотя если вдруг установлены 2 версии питона (2.x и 3.x), тоже могут быть осложнения.


Пути решения:


  • проверить установку pydot в докер-контейнере festline/mlcourse_open – инструкции в репозитории нашего курса
  • установить pydot самостоятельно, StackOverflow в помощь :)
  • накрайняк, использовать онлайн-конвертер из dot в png

А в целом, да, за отрисовку деревьев, sklearn-у незачет.

Код, который работал в jp notebook для меня после установки библиотек:

# используем .dot формат для визуализации дерева
from sklearn.tree import export_graphviz
export_graphviz(
    clf_tree,
    feature_names=['x1', 'x2'],
    out_file='/small_tree.dot',
    filled=True)
# для этого понадобится библиотека pydot (pip install pydot)


import pydot
(graph,) = pydot.graph_from_dot_file('/small_tree.dot')
graph.write_png('/small_tree.png')

from IPython.core.display import Image, display
display(Image('/small_tree.png', unconfined=True))

Немного картинок по результатам 2 домашек:


2 домашка оказалась сложнее (да, формулировки менее четкие, но тут уже исправленные результаты, где за 2 вопрос – всем 2 балла выставлено)
png
png


Стали больше откладывать на последний момент :) может быть связано с тем, что задание сложнее и вызвало большее оживление на форуме.


png
png


Ко второй домашке присоединились 26 новых участников, 107 "старых" – забили (из начальных 519 участников)

Из тех, кто не получил 10 баллов большая часть объявила Ализара наиболее часто минусуемым, я прав?)

Возможно – не смотрел. Но этот аспект обсуждался в #mlcourse_open

А приглашение туда когда придет? Вторую неделю жду.
пришли в лс мыло, которое указал при регистрации
Там не я отвечаю за утверждение заявок – написал контакт в личку.
Остается добавить, все вышеописанное по деревьям относилось к CRT, соответственно информация о недостатках и преимуществах относится к нему. На практике CRT используется крайне мало, в Штатах скормодель на базе CRT регулятор сразу завернет, потому что метод не стабилен. Основное применение — разведочный анализ и выделить полезные сложные взаимодействия признаков, которые логрегрессия и CHAID не смогут определить, а лес определит, но не даст увидеть, поскольку «черный ящик». Интересно было бы прочитать статьи по реализации CHAID в Питоне, преимущество CHAID — используем для формирования категорий и разбиения узлов жесткий статкритерий (хи-квадрат или F-тест), который работает как препрунинг. Собственно CHAID для скормоделей на втором месте идет после логрегрессии, либо сначала CHAID'ом делаем сегменты, а потом внутри них запускаем скормодели на базе логрегрессии, либо строим сразу скормодели на базе CHAID.
Вы все же имели в виду CART – Classification And Regression Trees. Реализация деревьев в Sklearn – это оптимизированная версия CART. Случайный лес в Sklearn опять же построен на деревьях CART, только усредняются не ответы, как в оригинале, а вероятности.
В документации Xgboost Вы опять же встретите CART.
Так что, мягко говоря, Вы поспешили заявить, что «На практике CRT используется крайне мало», а если не мягко, то надо порой отвлечься от того, что в твоей задаче происходит, и посмотреть немного вокруг.

mildly off-topic:
А есть концептуальная разница между CRT и CART?

Принципиальной разницы, конечно, нет, но давайте вещи называть своими именами – так, как его назвал Leo Breiman, а не товарищи из SPSS.


Интересно было бы прочитать статьи по реализации CHAID в Питоне

А написать про CHAID, случаем, вам не было бы интересно? :)

Кстати, интересно будет, если расскажете, как в деревьях с проверкой гипотез в узлах делается поправка на множественную проверку.
По поправкам…
Для контроля вероятности ошибки I рода p-значения, вычисленные для объединенных категорий (я про CHAID сейчас), умножаются на поправку Бонферрони, получаем так называемые скорректированные p-значения. Но необязательно Бонферрони использовать, можно и другие критерии. А вот в QUEST там двойная поправка применяется. Тоже интереснейший метод, я на его базе лес часто делаю и он часто превосходит по качеству лес на базе CRT. Например, QUEST провайдер Verizon использует в своих моделях оттока.
1. Для отбора переменных алгоритм исследует все предикторы с помощью статистических тестов значимости. Для каждого количественного или порядкового предиктора QUEST выполняет дисперсионный анализ (тестируется гипотеза о том, что различные категории зависимой переменной имеют одинаковое среднее значение предиктора), а затем предикторы упорядочиваются по значимости (p-значению) F-критерия для них. Для номинальных предикторов применяется критерий хи-квадрат и полученные в результате p-значения сохраняются.
2. Затем алгоритм выбирает предиктор с наименьшим p-значением, которое сравнивается с заданным уровнем значимости. При этом обратим внимание, что перед сравнением p-значения корректируются с помощью поправки Бонферрони: p-значение умножается на общее количество предикторов. Если нескорректированное p-значение равно 0,04, то после корректировки Бонферрони оно станет равным 0,40 = 0,04 x 10.
3. Если наименьшее p-значение (скорректированное по Бонферрони для теста на значимость) меньше заданного уровня значимости, алгоритм выбирает предиктор для разбиения данного узла. Если нет, происходит переход к шагу 4.
4. Для каждого порядкового или непрерывного предиктора алгоритм выполняет тест Ливиня на однородность дисперсии (т.е. тест на однородность дисперсии предиктора по категориям зависимой переменной). Это делается по причине того, что полезная для классификации информация может содержаться в переменной, которая для разных групп имеет одинаковые средние, но сильно отличающиеся дисперсии.
5. Алгоритм находит предиктор с наименьшим p-значением, которое сравнивается с заданным уровнем значимости. Перед сравнением p-значения корректируются с помощью новой поправки Бонферрони: теперь p-значение умножается на сумму общего числа предикторов и числа порядковых и количественных предикторов, используемых в анализе неоднородности. Если имеется 10 предикторов, 5 из которых являются количественными или порядковыми, то скорректированное p-значение для количественного или порядкового предиктора станет равным 0,6 = 0,04 x 15 (если нескорректированное p-значение было равно 0,04). Поскольку вероятности не могут превосходить 1, то скорректированные p-значения, превосходящие 1, полагаются равными 1.
Если наименьшее p-значение (скорректированное по Бонферрони для теста на однородность) меньше заданного уровня значимости, то соответствующий ему предиктор используется для разбиения узла. Если нет, то для этого используется наиболее значимый предиктор, полученный на предыдущем шаге (F-тест и критерий хи-квадрат).
Таким образом, чтобы отобрать предиктор для разбиения узла, используется последовательность статистических тестов.
Но тут я сбивчиво пишу, лучше всего я об этом в своей книге изложил, ссылку на которую дал вам в личке. Там и про недостатки CRT, техники прунинга, CHAID и прочее.

Да, она. Но лучше подождать «Прогнозное моделирование в IBM SPSS Statistics, R и Python. Деревья решений и случайный лес», там добавлено построение леса в SPSS, R и Python, а также деревья в Python. Тут с Юрием как раз обсуждали, что прунинг наиболее удачно реализован в rpart. Там используется метод отсечения ветвей, основанный на мере стоимости-сложности с перекрестной проверкой (кросс-валидацией) в том виде, как это задумывалось четырьмя авторами CART.
На каждом шаге построения дерева рассчитываются стоимости-сложности и кросс-валидационные ошибки, помогающие определить, когда достигнуто максимальное качество модели и дерево можно остановить в росте. Для дерева классификации считаем ошибку классификации на объектах, не входивших в обучении, для регрессии – сумму квадратов остатков, не входивших в обучение. Затем строится удобный график зависимости кросс-валидационных ошибок (xerror) от числа расщеплений (nsplit) и сложности модели (cp). Таким образом, общая логика прунинга в rpart состоит в том, чтобы построить полное дерево с максимальным количеством расщеплений (т.е. переобученное), а затем обрезать его до нужного размера, выбрав с помощью удобного графика оптимальное сочетание значений кросс-валидационной ошибки и стоимости-сложности.
К слову, в SPSS дерево обрезается с учетом ошибки классификации (или суммы квадратов остатков) на… обучающей выборке.

Да, использовал ее для книги, еще рекомендую книгу Андреаса Мюллера и Сары Гвидо по ML в Python. Андреасу удалось то, чего не удается многим авторам (я тут, наверно, не исключение) — снизить цену «входа» в ML, не просто доступное, а еще и увлекательное изложение методов ML в Python. И хоть «Вильямс» не удалось полностью передать дух книги (книга черно-белая, по тетрадкам не смогли договориться и код не очень хорошо сверстан), она будет существенной помощью в освоении Питон для самой широкой аудитории. Если нужны русифицированные тетрадки, они лежат здесь https://drive.google.com/open?id=0B6cpSQ5uHrxMbW93eXR3UmRBbjg
Правильно я понимаю, что если признаков (предикторов) много, скажем, 10 тыс, то такой подход не сработает?
Все p-value умножатся на 10 тыс., и тогда из п. 3 мы всегда переходим в п. 4. Там в п. 4 тоже поправка Бонферрони?

В-общем, как мы выберем первый признак, если таковых очень много, и все поправки Бонферрони привели к p-value 1 (после округления вниз). Другие поправки используются? Может, какие-то эвристики, чтоб не проверять все исходные признаки?

Или просто такой подход используется, когда признаков до нескольких сотен, не больше?
Спасибо, Юрий, а я перечитываю, понять не могу)) конечно же делим, а не умножаем, спутал с модифицированной реализацией для леса

в классическом QUEST
первая поправка Бонферрони — делим на общее количество предикторов, альфа/M
вторая поправка Бонферрони — делим на количество предикторов + количество порядковых, альфа/M+M1

https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0ahUKEwirzfG_ztvSAhXBhiwKHa76C8YQFggaMAA&url=http%3A%2F%2Fwww.springer.com%2Fcda%2Fcontent%2Fdocument%2Fcda_downloaddocument%2F9783319009599-c2.pdf%3FSGWID%3D0-0-45-1431236-p175268307&usg=AFQjCNFSczJLyOv4Dc4Fd2j6n6DhhPxs8g&sig2=NpzY-WC_isLK97wzv20wQQ&bvm=bv.149760088,d.bGg

стр. 27
В Python тоже удобной техники прунинга нет, но все равно поудобнее, чем в SPSS, регулируем сначала max_depth, а затем подбираем min_samples_split и min_samples_leaf (последние два значения подбираем так, чтоб min_samples_leaf был где-то в половину меньше чем min_samples_split, но если шумовых объектов может и не прокатить). Вот из реальной практики пример для Питон, на днях его крутил:
ln[1]:
tree = DecisionTreeClassifier(random_state=152)
tree.fit(X_train, y_train)
print(«Правильность на обучающей выборке: {:.3f}».format(tree.score(X_train, y_train)))
print(«Правильность на контрольной выборке: {:.3f}».format(tree.score(X_control, y_control)))

Out[1]:
Правильность на обучающей выборке: 0.992
Правильность на контрольной выборке: 0.897

Поскольку правильность – точечная оценка дискриминирующей способности, для более объективной оценки берем AUC

ln[2]:
tree = DecisionTreeClassifier(random_state=152)
tree.fit(X_train, y_train)
print(«AUC на обучающей выборке: {:.3f}».
format(roc_auc_score(y_train, tree.predict_proba(X_train)[:, 1])))
print(«AUC на контрольной выборке: {:.3f}».
format(roc_auc_score(y_control, tree.predict_proba(X_control)[:, 1])))

Out[2]:
AUC на обучающей выборке: 1.000
AUC на контрольной выборке: 0.793

Делаем прунинг
ln[3]:
tree2 = DecisionTreeClassifier(max_depth=15, min_samples_leaf=15,
min_samples_split=30, random_state=152)
tree2.fit(X_train, y_train)
print(«AUC на обучающей выборке: {:.3f}».
format(roc_auc_score(y_train, tree2.predict_proba(X_train)[:, 1])))
print(«AUC на контрольной выборке: {:.3f}».
format(roc_auc_score(y_control, tree2.predict_proba(X_control)[:, 1])))

Out[3]:
AUC на обучающей выборке: 0.940
AUC на контрольной выборке: 0.881

Но меня результат все равно не устроил, я сгенерировал дополнительные признаки (а еще лучше признаки с весами сделать) и потом снова обрезал, чтоб AUC повыше получить. Для более надежной оценки подрезанных моделей (обычно на практике берут каскад из 3-4 моделей) в Python рекомендую использовать решетчатый поиск с комбинированной проверкой (класс GridSearchCV), в R для этих целей можно пакет caret использовать
К.В. Воронцов описывает стрижку cost-compexity prunning (изложена вкратце у Е. Соколова тут), при которой дерево строится до макс. глубины, а затем последовательно, снизу вверх, на основе кросс-валидации удаляются лишние узлы (на CV сравнивается дерево с этим узлом и без него). Утверждают, что это работает лучше, чем подбор параметров. Но вычислительная сложность высокая. Не видел, где бы на Python было реализовано. И Conditional Inference Trees в питоне не хватает, хотя видел обсуждение, что кто-то собирался реализовать в sklearn.
В целом да, в реализации деревьев R обгоняет питон. То же можно сказать и про визуализацию и линейные модели.
Мне кажется там небольшая путиница в использовании терминов в начале. «Энтропия состояния», которая несколько раз встречается — это не совсем правильно, состояний там два исходя из исходного определения — «вытащили желтый» и «вытащили синий», а энтропия — одно единственное число. Лучше набором или группой везде называть. Ну и если уж совсем придраться — энтропия не группы шариков, а энтропия вытаскивания одного шарика из этой группы. Потому что если бы мы вытаскивали 2 шарика, то состояния, вероятности и в конечном итоге энтропия были бы уже другими. Может это буквоедство, но честно сказать сбило поначалу.
фу спам, как жеж тут призвать модератора что бы автора книги забанили
Просто если подняться по ветке выше, видно, что о книге спрашивали, поэтому дал информацию.

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

Новый запуск курса – 5 февраля 2018 г. Регистрация не требуется, но чтобы мы о вас знали, заполните форму. Главные новости будут в группе ВКонтакте, а жизнь во время курса будет теплиться в Slack OpenDataScience (вступить) в канале #mlcourse_open.

Проблемы с форматированием кода в пункте «Сложный случай для деревьев решений»

Новый запуск – 1 октября 2018 г., на английском. Подробности – тут.

Теперь курс можно проходить и самостоятельно – появились демо-версии заданий с решениями. Они описываются в конце каждой статьи, но есть и общий cписок. Решения доступны после отправки соотв. веб-формы.

Выражаю автору благодарность. Эта уже не первая статья, которая сильно помогает понять некоторые курсы о машинном обучении значительно глубже. Особенно выручают игрушечные примеры.
Only those users with full accounts are able to leave comments. Log in, please.