УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ
на главную написать письмо карта сайта

јвтор:  √убко ћ.¬., Ћактионова ћ.ћ.
Ќазвание:  јлгоритм построени€ дерева решений
—татус:  опубликовано
»здательство (дл€ книг и брошюр):  ћ‘“»
√од:  2011
“ип публикации:  доклад
ѕолна€ библиографическа€ ссылка:  √убко ћ.¬., Ћактионова ћ.ћ. јлгоритм построени€ дерева решений / “руды 54 научной конференции ћ‘“» У—овременные проблемы фундаментальных и прикладных наукФ. »нформационные бизнес-системы. ћосква-ƒолгопрудный-∆уковский: ћ‘“», 2011. —. 112-113.
јннотаци€:  ƒеревь€ решений Ц хорошо зарекомендовавший себ€ комплекс методов классификации, распознавани€ и поддержки прин€ти€ решений в машинном обучении, идентификации, анализе данных, ситуационном управлении. ƒерево решений должно быть компактным Ц это экономит затраты при ответах на вопросы; кроме того, компактные деревь€ обладают лучшей прогностической способностью.
«адача построени€ оптимального дерева решений €вл€етс€ NP-полной. ¬ св€зи с этим на практике используютс€ многочисленные эвристические алгоритмы. ћы предлагаем простой Ђжадныйї алгоритм построени€ дерева Ђсверху внизї, основанный на использовании предложенной в [1] нижней оценки стоимости дерева, имеющей, в отличие от известных оценок, комбинаторную природу. ≈е вычисление сводитс€ к решению набора непрерывных релаксаций задачи о минимальном покрытии. Ёксперименты показывают, что кажда€ задача решаетс€ за врем€ в среднем пор€дка n*m, где n Ц объем используемой дл€ построени€ дерева обучающей выборки, а m Ц количество имеющихс€ вопросов (тестов). Ќа примере нескольких реальных задач классификации показываетс€, что предлагаемый алгоритм дает не худшие результаты, чем такие попул€рные эвристики как CS-ID3, IDX и EG2.
Ќедостатком используемой нижней оценки €вл€етс€ ее относительно высока€ вычислительна€ сложность Ц пор€дка n2m (дл€ каждого из n элементов обучающей выборки за врем€ в среднем пор€дка n*m решаетс€ задача о покрытии). –ассмотрен вариант ее уменьшени€ за счет вычислени€ оценки на основе лишь части обучающей выборки. ѕри этом трудоемкость ее вычислени€ уменьшаетс€ до A*n*m, где A Ц максимальное число элементов выборки, используемых дл€ расчета. ѕолученна€ огрубленна€ оценка уже не €вл€етс€ гарантированно нижней оценкой, однако дл€ ее применени€ в алгоритме это не об€зательно. ¬ результате дл€ типичного случа€ m << n оценка средней трудоемкости всего алгоритма имеет пор€док не более A*m3*n, то есть линейно растет по n, что принципиально дл€ практического применени€ алгоритма. ¬ докладе описываютс€ результаты вычислительных экспериментов по определению вли€ни€ параметра A на качество результирующих деревьев.
–абота частично выполнена при финансовой поддержке –оссийского фонда фундаментальных исследований (проект 10-07-00129).

Ћитература
1. Goubko M.V. Lower-bound Estimate for Cost-sensitive Decision Trees // Preprints of the 18th IFAC World Congress, Milano (Italy), August 28 - September 2, 2011. P. 9005-9010.


в формате PDF

ѕросмотров: 2067, загрузок: 656, за мес€ц: 8.

Ќазад

»ѕ” –јЌ © 2007. ¬се права защищены