Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 14
Божественно!
А Вы не подскажете некие общие возможно эмпирические оценки относительно того, когда следует ограничить построение дерева (понятно что если в исходном множестве N-элементов, то выделение N-подмножеств смысла не несет)
А Вы не подскажете некие общие возможно эмпирические оценки относительно того, когда следует ограничить построение дерева (понятно что если в исходном множестве N-элементов, то выделение N-подмножеств смысла не несет)
Эмпирические можно получить самим, поварьировать параметры (например макс.глубина и минимальное кол-во элементов в листе), и посмотреть производительность с учетом сложности модели (советую почитать про bayesian information criteria и model selection в общем).
Вообще для оценки сложности любой data mining модели (в том числе при построении деревьев принятия решения) — лучше использовать тесовую выборку (или кросс-валидацию). В этом случае как только пойдет переобучение тестовая выборка это покажет и можно остановить обучение.
Однако, алгоритмы CART и оригинальный Random Forest, например, предпологает строить модель «до упора» — пока есть сплиты (конечно с заданными минимальнми размерами листьев). После чего, в CART используется так называемый pruning — удаления вершин из дерева на основе сложности (complexity) вершины и насколько эта вершина уменьшает энтропию (i.e. node improvement). В RandomForest же просто используються полные деревья — и усредненеием голосов убирается возможное переобучение, так как каждое дерево построено на случайной подвыборке данных.
Однако, алгоритмы CART и оригинальный Random Forest, например, предпологает строить модель «до упора» — пока есть сплиты (конечно с заданными минимальнми размерами листьев). После чего, в CART используется так называемый pruning — удаления вершин из дерева на основе сложности (complexity) вершины и насколько эта вершина уменьшает энтропию (i.e. node improvement). В RandomForest же просто используються полные деревья — и усредненеием голосов убирается возможное переобучение, так как каждое дерево построено на случайной подвыборке данных.
Если я правильно понял вопрос — Вас интересует как выбрать количество деревьев в ансамбле.
Как уже отмечали, для этого полезно использовать выборку данных, которая не принимает участия в построении дерева — на ней будем тестировать качество классификатора.
Количество деревьев можно определить эмпирически — постепенно увеличивая их количество, и проверяя качество классификации на тестовых данных. В большинстве случаев получается примерно такая зависимость (схематически):
То есть, после некоторого порогового значения, увеличение количества деревьев перестаёт значительно увеличивать качество классификации. На этом количестве деревьев можно и остановиться.
Как уже отмечали, для этого полезно использовать выборку данных, которая не принимает участия в построении дерева — на ней будем тестировать качество классификатора.
Количество деревьев можно определить эмпирически — постепенно увеличивая их количество, и проверяя качество классификации на тестовых данных. В большинстве случаев получается примерно такая зависимость (схематически):
То есть, после некоторого порогового значения, увеличение количества деревьев перестаёт значительно увеличивать качество классификации. На этом количестве деревьев можно и остановиться.
попридираюсь :)
Пробовали когда-нибудь интерпретировать то, что в деревьях принятия решений получается?) У отдельных деревьев (построенных одним из широко применяемых алгоритмов — ID3, C4.5, CART и тд) очень большая вариативность — при небольших изменениях в данных может получаться совершенно другое дерево; в таких условиях сложно говорить о какой-то интерпретации результатов. Ну т.е. интерпретировать можно; чуть данные изменились — совсем другое дерево и совсем другая интерпретация, смысл в такой интерпретации. Там не получается так, чтоб сверху дерева были более важные критерии. То, что вы же описали — это, вроде бы, ID3; у него точно те же проблемы — интерпретация работает только на примитивных примерах и редко работает в реальной жизни.
Дальше, Random Forest. Их интерпретировать, разглядывая структуру деревьев, еще сложнее, т.к. вместо одного дерева имеем много деревьев (совсем разных).
Вы описали упрощенный вариант RF, где для тренировки деревьев выбираются случайные подмножества обучающего набора. Но: в оригинальном RF для тренировки деревьев выбираются не только случайные подмножества обучающего набора, но и случайные подмножества фич (характеристик) для каждого дерева. Благодаря этому, в частности, становится возможно интерпретировать результаты RF — смотря, какие из фич оказывали большее влияние на результат, какие важнее.
Т.е. на практике RF может быть более понятным для интерпретации, чем отдельные деревья принятия решений: для каждой фичи можно вычислить хотя бы ее «важность».
Деревья принятия решений являются удобным инструментом в тех случаях, когда требуется не просто классифицировать данные, но ещё и объяснить почему тот или иной объект отнесён к какому-либо классу.
Пробовали когда-нибудь интерпретировать то, что в деревьях принятия решений получается?) У отдельных деревьев (построенных одним из широко применяемых алгоритмов — ID3, C4.5, CART и тд) очень большая вариативность — при небольших изменениях в данных может получаться совершенно другое дерево; в таких условиях сложно говорить о какой-то интерпретации результатов. Ну т.е. интерпретировать можно; чуть данные изменились — совсем другое дерево и совсем другая интерпретация, смысл в такой интерпретации. Там не получается так, чтоб сверху дерева были более важные критерии. То, что вы же описали — это, вроде бы, ID3; у него точно те же проблемы — интерпретация работает только на примитивных примерах и редко работает в реальной жизни.
Дальше, Random Forest. Их интерпретировать, разглядывая структуру деревьев, еще сложнее, т.к. вместо одного дерева имеем много деревьев (совсем разных).
Вы описали упрощенный вариант RF, где для тренировки деревьев выбираются случайные подмножества обучающего набора. Но: в оригинальном RF для тренировки деревьев выбираются не только случайные подмножества обучающего набора, но и случайные подмножества фич (характеристик) для каждого дерева. Благодаря этому, в частности, становится возможно интерпретировать результаты RF — смотря, какие из фич оказывали большее влияние на результат, какие важнее.
Т.е. на практике RF может быть более понятным для интерпретации, чем отдельные деревья принятия решений: для каждой фичи можно вычислить хотя бы ее «важность».
Спасибо за Ваши замечания :-)
В общем, я с Вами согласен.
Хотя, по своему опыту, могу сказать, что используя дерево принятия решений в качестве бинарного классификатора для реальной задачи — интерпретировать результаты классификации было легко, и общая картина вырисовывалась довольно логично и последовательно.
Но действительно, как Вы и отметили, при увеличении количества классов, интерпретировать дерево принятия решений становится сложнее. Ну и «жадный» алгоритм построения, к сожалению, не всегда устойчивым к небольшим изменениям исходных данных.
В общем, я считаю, что многие подводные камни являются результатом специфики той или иной предметной области, в применении к которой используется классификатор.
В общем, я с Вами согласен.
Хотя, по своему опыту, могу сказать, что используя дерево принятия решений в качестве бинарного классификатора для реальной задачи — интерпретировать результаты классификации было легко, и общая картина вырисовывалась довольно логично и последовательно.
Но действительно, как Вы и отметили, при увеличении количества классов, интерпретировать дерево принятия решений становится сложнее. Ну и «жадный» алгоритм построения, к сожалению, не всегда устойчивым к небольшим изменениям исходных данных.
В общем, я считаю, что многие подводные камни являются результатом специфики той или иной предметной области, в применении к которой используется классификатор.
Действительно, Leo Breinman пришел в RandomForest, а Jerry Friedman к TreeNet (Gradient Boosted Decision Trees) по причине неустойчивости CART алгоритма и слишком сильной дискретизации при решении задачи регрессии (хотя, конечно можно в каждом leaf строить регрессию для создания smooth predictions).
Однако, у CART алгоритма есть такая же возможнсть оценить влияние переменных (фич) на результат. И в избравлении от неустойчивости очень помогает использование surrogates и competitors.
Хотя, конечно, анасамбли деревьев позволяют использовать соврешенно другую машинерию — в том числе Dependency Plots — которая показывает частную производную по переменной полученной функции (см. как влияет изменения переменной на конечный prediction). Так же для Random Forest есть множество интересных post-processing техник — Parallel Coordinates, Proximity matrices которые позволяют глубже взглянуть на имеющиеся данные.
Однако, у CART алгоритма есть такая же возможнсть оценить влияние переменных (фич) на результат. И в избравлении от неустойчивости очень помогает использование surrogates и competitors.
Хотя, конечно, анасамбли деревьев позволяют использовать соврешенно другую машинерию — в том числе Dependency Plots — которая показывает частную производную по переменной полученной функции (см. как влияет изменения переменной на конечный prediction). Так же для Random Forest есть множество интересных post-processing техник — Parallel Coordinates, Proximity matrices которые позволяют глубже взглянуть на имеющиеся данные.
У Вас — самый весёлый (или ехидный? ) демон Максвелла из тех что я видел :-). И без рожек.
Ну, допустим. А не подскажите, существуют ли какие-нибудь методы решения своего рода «обратной задачи». Когда известны классы и нужно понять по каким признакам объекты были отнесены к этим классам?
Так а сами признаки есть? Если нет — то тут будет сложно что-то решить :)
Если же есть — то это ничем не отличается от обычной классификации — у вас есть признаки и классы — вы обучаете классификатор (к примеру дерево принятия решения) и получаете вашу зависимости классов от признаков. Другой вопрос — что при обратной задаче существует неоднозначность интерпретации — из серии человек в категории высокого риска потому что: у него возраст меньше 18 или больше 65, но это решать нужно используя какие-то доменные знания и возможно модифицируя переменные, к примеру создавая переменные вида «18<=возраст<=65?» в зависимости что получилось при построении классификатора и какой именно вид связи Вам нужен.
Если же есть — то это ничем не отличается от обычной классификации — у вас есть признаки и классы — вы обучаете классификатор (к примеру дерево принятия решения) и получаете вашу зависимости классов от признаков. Другой вопрос — что при обратной задаче существует неоднозначность интерпретации — из серии человек в категории высокого риска потому что: у него возраст меньше 18 или больше 65, но это решать нужно используя какие-то доменные знания и возможно модифицируя переменные, к примеру создавая переменные вида «18<=возраст<=65?» в зависимости что получилось при построении классификатора и какой именно вид связи Вам нужен.
Спасибо.
Да, признаки есть. Суть задачи в следующем: Есть таблица базы данных с N полями и идентификатором. Идентификатор вычисляется на основе нескольких полей (бизнес-ключ), используя хеш-функцию. Хеш функция должна генерировать для одинаковых значений полей одинаковый хеш (так как это MD5). В результате чего-то неизвестного в определенный период времени мы обнаружили дубликаты: строчки с одинаковым бизнес-ключом, но разным идентификатором. Мы пытаемся понять, что могло послужить причиной такого поведения. Чтобы клиент не ворчал, мы обнули таблицу и перезагрузили таблицу заново, сохранив копию таблицы с дубликатами. В результате анализа мы обнаружили, что после новой перезагрузки таблицы, идентификаторы в тех строках, что дублировались стали совпадать с одним из дублировавшихся идентификаторов. Мы сравнили затем старую и новую таблицу и выяснили, что на самом деле иногда новые идентификаторы совпадают и со старыми. Таким образом, у нас есть два класса: строки с совпадающими идентификаторами в старых и новых таблицах и строки с разными идентификаторами. Наша задача, выявить какие-нибудь закономерности в полях, которые могли привести к в генерации «неправильных» хешей. Какие могут быть причины? Например, поплывшая кодировка у строковых полей (на самом деле, мы это проверили, но как пример), наличие пустых значений в некоторых полях (или групп полей).
Отладка довольно затруднительна, так как генерация ключа происходит в проприетарном продукте, поведение которого нам неизвестно точно. Поэтому мы хотим попытаться выявить какие-нибудь закономерности в строках, которые совпали и которые нет и в случае необходимости сообщить, например, вендору о нестабильности в его продукте, если таковые будут иметь место.
Поэтому меня вдохновила эта статья и я понадеялся, что реально провести соответствующий анализ.
Надеюсь, что удалось более мене подробно объяснить.
Да, признаки есть. Суть задачи в следующем: Есть таблица базы данных с N полями и идентификатором. Идентификатор вычисляется на основе нескольких полей (бизнес-ключ), используя хеш-функцию. Хеш функция должна генерировать для одинаковых значений полей одинаковый хеш (так как это MD5). В результате чего-то неизвестного в определенный период времени мы обнаружили дубликаты: строчки с одинаковым бизнес-ключом, но разным идентификатором. Мы пытаемся понять, что могло послужить причиной такого поведения. Чтобы клиент не ворчал, мы обнули таблицу и перезагрузили таблицу заново, сохранив копию таблицы с дубликатами. В результате анализа мы обнаружили, что после новой перезагрузки таблицы, идентификаторы в тех строках, что дублировались стали совпадать с одним из дублировавшихся идентификаторов. Мы сравнили затем старую и новую таблицу и выяснили, что на самом деле иногда новые идентификаторы совпадают и со старыми. Таким образом, у нас есть два класса: строки с совпадающими идентификаторами в старых и новых таблицах и строки с разными идентификаторами. Наша задача, выявить какие-нибудь закономерности в полях, которые могли привести к в генерации «неправильных» хешей. Какие могут быть причины? Например, поплывшая кодировка у строковых полей (на самом деле, мы это проверили, но как пример), наличие пустых значений в некоторых полях (или групп полей).
Отладка довольно затруднительна, так как генерация ключа происходит в проприетарном продукте, поведение которого нам неизвестно точно. Поэтому мы хотим попытаться выявить какие-нибудь закономерности в строках, которые совпали и которые нет и в случае необходимости сообщить, например, вендору о нестабильности в его продукте, если таковые будут иметь место.
Поэтому меня вдохновила эта статья и я понадеялся, что реально провести соответствующий анализ.
Надеюсь, что удалось более мене подробно объяснить.
Если у Вас достаточно много таких записей, то можно собрать все записи, для которых ожидается одинаковый айдишник (но по факту айдишники разные) — это будет обучающая выборка. Пусть записи с разными айдишниками будут принадлежать разным классам. Затем, на основе данной выборки, можно построить дерево принятия решений.
Если визуализировать дерево, и рассмотреть его ветки, то можно будет обнаружить условия, приводящие к разным айдишникам.
Если визуализировать дерево, и рассмотреть его ветки, то можно будет обнаружить условия, приводящие к разным айдишникам.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Энтропия и деревья принятия решений