Деревья решений и Случайный лес: Дискретная математика в машинном обучении

Дерево решений — это направленный ациклический граф в виде древовидной структуры. В каждом внутреннем узле этого дерева находится логическое условие, проверяющее значение определенного признака (например, «возраст клиента больше 30 лет?»). Ребра, исходящие из узла, соответствуют ответам (Да/Нет), а листовые узлы содержат итоговый прогноз — класс объекта или конкретное числовое значение.

Главная математическая задача при построении дерева — алгоритмически выбрать, какой именно признак поставить в корень дерева и в последующие узлы, чтобы разделить обучающую выборку максимально эффективно. Для этого используются метрики из теории информации (Клода Шеннона):

• Информационная энтропия: мера хаоса в данных. Если в узле находятся 50 больных и 50 здоровых пациентов, энтропия максимальна (1). Если 100 больных и 0 здоровых — энтропия равна 0 (полная определенность).
• Прирост информации (Information Gain): алгоритм перебирает все признаки и вычисляет, насколько упадет общая энтропия системы, если мы разобьем данные именно по этому признаку. Признак с максимальным приростом становится узлом ветвления (алгоритм ID3, C4.5).
• Индекс Джини (Gini Impurity): альтернативная, более быстрая в вычислении метрика вероятности того, что случайно взятый элемент выборки будет неверно классифицирован (используется в алгоритме CART).

Основной недостаток одного Дерева решений — склонность к переобучению (Overfitting). Дерево может вырасти настолько глубоким, что просто "зазубрит" каждый пример из тренировочной базы, потеряв способность к обобщению. Чтобы решить эту проблему, был создан Случайный лес (Random Forest).

Это ансамблевый метод, работающий по принципу "мудрости толпы" (бэггинг). Алгоритм генерирует сотни различных деревьев решений. Чтобы деревья не получились одинаковыми, применяется жесткая дискретная рандомизация: каждое дерево обучается на случайной подвыборке данных (созданной с возвращением — Bootstrapping), и в каждом узле дереву разрешается выбирать вопрос не из всех признаков, а только из их случайного малого подмножества. Когда поступает новый клиент, все сотни деревьев делают свой прогноз, а итоговый результат выбирается простым голосованием большинства. Этот метод до сих пор остается одним из самых мощных и устойчивых алгоритмов для работы с табличными данными в IT и банковском скоринге.