Деревья решений – хорошо зарекомендовавший себя комплекс методов классификации, распознавания и поддержки принятия решений в машинном обучении, идентификации, анализе данных, ситуационном управлении. Дерево решений должно быть компактным – это экономит затраты при ответах на вопросы; кроме того, компактные деревья обладают лучшей прогностической способностью. Задача построения оптимального дерева решений является NP-полной. В связи с этим на практике используются многочисленные эвристические алгоритмы. Мы предлагаем простой «жадный» алгоритм построения дерева «сверху вниз», основанный на использовании оригинальной нижней оценки стоимости дерева, имеющей, в отличие от известных оценок, комбинаторную природу. Ее вычисление сводится к решению набора непрерывных релаксаций задачи о минимальном покрытии. Недостатком используемой нижней оценки является ее относительно высокая вычислительная сложность – порядка n2m (для каждого из n элементов обучающей выборки за время в среднем порядка n*m решается задача о покрытии). Рассмотрен вариант ее уменьшения за счет вычисления оценки на основе лишь части обучающей выборки.