Отсечение ветвей дерева

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

Деревья решений в реальном мире

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

Деревья решений применяются в таких приложениях, как профилирование клиентов, анализ финансовых рисков, помощь в диагностике и транспортное прогнозирование.

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

Для сокращения необходимо проверить пары узлов, имеющих общего родителя, и посмотреть, насколько увеличится энтропия при их объединении. Если увеличение окажется меньше заданного порога, то оба листа сливаются в один, для которого множество результатов получается объединением результатов в исходных листьях. Таким образом, мы избегаем феномена переучивания и не даем дереву сделать прогноз с большей долей уверенности, чем позволяют данные. Добавьте в файл treepredict.py функцию сокращения дерева: def prune(tree,mingain):

#       Если ветви не листовые, вызвать рекурсивно if tree.tb.results==None:

prune(tree.tb,mingain) if tree.fb.results==None: prune(tree.fb,mingain)

#       Если обе подветви заканчиваются листьями, смотрим, нужно ли их

#       объединить

if tree.tb.results!=None and tree.fb.results!=None:

#       Строим объединенный набор данных tb,fb=[],[]

for v,c in tree.tb.results.items( ):

tb+=[[v]]*c for v,c in tree.fb.results.items( ): fb+=[[v]]*c

#       Вычисляем, насколько уменьшилась энтропия delta=entropy(tb+fb)-(entropy(tb)+entropy(fb)/2) if delta<mingain:

#       Объединить ветви tree.tb,tree.fb=None,None tree.results=uniquecounts(tb+fb)

При вызове для корневого узла эта функция обходит все дерево, спускаясь до узлов, единственными дочерними узлами которых являются листья. Она объединяет списки результатов, хранящиеся в обоих листьях, и проверяет, насколько изменилась энтропия. Если изменение меньше параметра mingain, то оба листовых узла удаляются, а хранившиеся в них результаты перемещаются в узел-родитель. Теперь объединенный узел сам становится кандидатом на удаление и объединение с другим узлом.

Протестируем эту функцию на текущем наборе данных и посмотрим, приведет ли это к объединению каких-нибудь узлов: >>> reload(treepredict)

<module ‘treepredict’ from ‘treepredict.pyc’> >>> treepredict.prune(tree,0.1) >>> treepredict.printtree(tree)

0:google? T-> 3:21? T-> {‘Premium’: 3} F-> 2:yes? T-> {‘Basic’: 1} F-> {‘None’: 1} F-> 0:slashdot? T-> {‘None’: 3} F-> 2:yes? T-> {‘Basic’: 4} F-> 3:21? T-> {‘Basic’: 1} F-> {‘None’: 3} >>> treepredict.prune(tree,1.0) >>> treepredict.printtree(tree) 0:google? T-> 3:21? T-> {‘Premium’: 3} F-> 2:yes? T-> {‘Basic’: 1} F-> {‘None’: 1} F-> {‘None’: 6, ‘Basic’: 5}

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100