14750

Автор(ов): 

2

Параметры публикации
Тип публикации: 
Тезисы доклада
Название: 
Алгоритм построения дерева решений
Наименование конференции: 
54-я научная конференция МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» (Долгопрудный, 2011)
Наименование источника: 
Труды 54-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» (Долгопрудный, 2011)
Город: 
Москва
Издательство: 
МФТИ
Год издания: 
2011
Страницы: 
112-113
Аннотация
Деревья решений – хорошо зарекомендовавший себя комплекс методов классификации, распознавания и поддержки принятия решений в машинном обучении, идентификации, анализе данных, ситуационном управлении. Дерево решений должно быть компактным – это экономит затраты при ответах на вопросы; кроме того, компактные деревья обладают лучшей прогностической способностью. Задача построения оптимального дерева решений является NP-полной. В связи с этим на практике используются многочисленные эвристические алгоритмы. Мы предлагаем простой «жадный» алгоритм построения дерева «сверху вниз», основанный на использовании оригинальной нижней оценки стоимости дерева, имеющей, в отличие от известных оценок, комбинаторную природу. Ее вычисление сводится к решению набора непрерывных релаксаций задачи о минимальном покрытии. Недостатком используемой нижней оценки является ее относительно высокая вычислительная сложность – порядка n2m (для каждого из n элементов обучающей выборки за время в среднем порядка n*m решается задача о покрытии). Рассмотрен вариант ее уменьшения за счет вычисления оценки на основе лишь части обучающей выборки.
Библиографическая ссылка: 
Губко М.В., Лактионова М.М. Алгоритм построения дерева решений / Труды 54-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» (Долгопрудный, 2011). М.: МФТИ, 2011. С. 112-113.