Логические методы классификации

Материал из MachineLearning.

Статья написана с использованием LLM Claude Sonnet 5 и проверена участником Д. Жумабеков 21:27, 19 июля 2026 (MSD)

Содержание

1 Введение
2 Логическая закономерность как объект
3 Определение решающего дерева
4 Алгоритм построения дерева ID3
5 Критерий ветвления
- 5.1 Энтропийный критерий и критерий Джини
6 CART — деревья регрессии и классификации
7 Обрезка дерева (Minimal Cost-Complexity Pruning)
8 Эквивалентность дерева набору конъюнктивных правил
9 Объяснимый ИИ (XAI) и интерпретируемость
10 Место решающих деревьев среди логических методов
11 Литература

Введение

Одно из направлений становления теории распознавания образов в отечественной научной традиции — школа символизма, основы которой заложены работами М. М. Бонгарда. Эталонной задачей этой школы служат тесты Бонгарда — наборы изображений, разбитых на две группы, для которых требуется не просто отнести новый объект к одной из групп (что решается численными методами по мере близости к обучающим примерам), а явно сформулировать правило, по которому произведено разбиение, опираясь на конечное число примеров^[1]. Существенное отличие такой постановки от численных моделей зависимости (линейных, метрических, байесовских) состоит в том, что результатом обучения является не набор числовых параметров, приближающих неизвестную функцию, а логическое высказывание об объекте — предикат, доступный содержательной интерпретации.

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

Логическая закономерность как объект

Правилом (предикатом-закономерностью) называется отображение $\varphi: X \to \{0,1\}$ , значение $\varphi(x)=1$ которого означает, что объект $x$ покрыт правилом (удовлетворяет его условию). Правило называется закономерностью относительно класса $y$ , если множество покрытых им объектов содержит существенно больше объектов класса $y$ , чем объектов прочих классов.

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

Так, в задаче медицинской диагностики закономерность вида «возраст пациента старше 60 лет и уровень маркера воспаления выше порогового значения» интерпретируема (два условия на измеримых признаках) и, при достаточном числе подтверждающих наблюдений, информативна относительно класса «повышенный риск осложнения». Ошибочное применение такого правила сопряжено с конкретной ценой: ложноотрицательное срабатывание (правило не сочло пациента из группы риска) может стоить своевременности лечения, ложноположительное — привести к излишним обследованиям. В задаче кредитного скоринга закономерность «срок кредита превышает 24 месяца и заёмщик снимает жильё» аналогичным образом сопоставляет интерпретируемое условие с оценённым по выборке риском невозврата; ошибка правила в эту сторону — отказ надёжному заёмщику (упущенная выгода), ошибка в обратную сторону — выдача кредита ненадёжному заёмщику (прямые финансовые потери). Оба примера показывают, что отдельное правило редко покрывает выборку целиком — необходим механизм построения набора взаимодополняющих закономерностей, что и решает решающее дерево.

Определение решающего дерева

Решающим деревом называется алгоритм классификации или регрессии, задаваемый конечным ациклическим ориентированным графом $T$ без циклов со следующей структурой:

граф имеет единственную корневую вершину без входящих рёбер;
каждая внутренняя вершина $v$ помечена признаком ветвления $f_v$ (и, для количественного признака, пороговым значением $t_v$ ) и имеет функцию перехода $\beta_v: X \to \{v_L, v_R\}$ , определяющую, в какую дочернюю вершину — левую $v_L$ или правую $v_R$ — направляется объект $x$ в зависимости от значения $f_v(x)$ ;
каждый лист $v$ (вершина без исходящих рёбер) помечен ответом $c_v \in Y$ (для классификации) либо $c_v \in \mathbb{R}$ (для регрессии).

Классификация объекта $x$ состоит в спуске от корня к некоторому листу: в каждой внутренней вершине $v$ вычисляется $f_v(x)$ , по значению функции перехода $\beta_v$ выбирается дочерняя вершина, процедура повторяется до достижения листа $v^*$ , ответом алгоритма служит метка этого листа: $a(x) = c_{v^*}$ .

Наиболее употребителен частный случай бинарного дерева, в котором каждая внутренняя вершина имеет ровно двух потомков, а функция перехода задаётся пороговым условием на одном количественном признаке:

$\beta_v(x) = \begin{cases} v_L, & f_v(x) \leq t_v \\ v_R, & f_v(x) > t_v \end{cases}$

Далее рассматриваются исключительно бинарные деревья как наиболее распространённый и вычислительно удобный частный случай.

Алгоритм построения дерева ID3

Построение дерева по обучающей выборке $X^{\ell}$ производится рекурсивно, методом «сверху вниз»: на каждом шаге для текущего множества объектов $U \subseteq X^{\ell}$ , попавшего в очередную вершину, ищется признак ветвления и порог, наилучшим образом разделяющие $U$ на две части, после чего процедура рекурсивно повторяется для каждой части.

Схема алгоритма (ID3 / TreeGrowing).

Если для множества $U$ выполнен критерий остановки (все объекты $U$ относятся к одному классу; либо $|U|$ меньше заданного порога; либо достигнута предельная глубина дерева; либо ни один признак не даёт положительного прироста качества), — создать лист с ответом $c_U$ , вычисленным как класс большинства объектов $U$ (для классификации) или как среднее значение целевой переменной по $U$ (для регрессии), и завершить рекурсию.
Иначе — перебором по всем признакам $f$ и по всем допустимым порогам $t$ найти пару $(f^*, t^*)$ , максимизирующую критерий ветвления $\mathrm{Gain}(f, t, U)$ (определён в следующем разделе).
Разбить $U$ на $U_L = \{x \in U: f^*(x) \leq t^*\}$ и $U_R = \{x \in U: f^*(x) > t^*\}$ .
Создать внутреннюю вершину с признаком ветвления $f^*$ и порогом $t^*$ ; рекурсивно построить её левое поддерево по $U_L$ и правое поддерево по $U_R$ .

Критерий остановки, применённый на первом шаге каждого вызова, — единственный механизм, ограничивающий рост дерева; без него рекурсия продолжалась бы до тех пор, пока каждый лист не содержал бы единственный объект, что ведёт к неограниченному переобучению (подробнее — в разделе «Обрезка дерева»).

Критерий ветвления

Пусть $Q_0(U)$ — суммарная функция потерь на множестве объектов $U$ при условии, что всем объектам $U$ присваивается единый, оптимальный для $U$ ответ $c_U$ (то есть потери, которые понёс бы лист, содержащий все объекты $U$ без дальнейшего ветвления):

$Q_0(U) = \min_{c} \sum_{x_i \in U} L(y_i, c)$

Если множество $U$ разбивается по признаку $f$ с порогом $t$ на $U_L$ и $U_R$ , суммарные потери после ветвления равны сумме потерь в каждой из частей при её собственном оптимальном ответе:

$Q(f, t, U) = Q_0(U_L) + Q_0(U_R)$

Приростом качества (information gain в широком смысле) от ветвления по $(f,t)$ называется разность потерь до и после разбиения:

$\mathrm{Gain}(f, t, U) = Q_0(U) - Q(f, t, U) = Q_0(U) - Q_0(U_L) - Q_0(U_R)$

Поскольку каждое из $Q_0(U_L)$ , $Q_0(U_R)$ вычисляется как минимум по $c$ , а $Q_0(U)$ — минимум по единому $c$ для всего множества, выполнено $\mathrm{Gain}(f,t,U) \geq 0$ для любого разбиения: раздельная оптимизация ответа в двух частях не может ухудшить суммарные потери по сравнению с единым ответом на всём $U$ . Алгоритм ID3 на каждом шаге выбирает $(f^*, t^*)$ , максимизирующие $\mathrm{Gain}(f,t,U)$ , — это и есть жадная (локально-оптимальная на каждом шаге) стратегия построения дерева.

Энтропийный критерий и критерий Джини

Конкретный вид критерия определяется выбором функции потерь $L$ . Для задачи классификации на $M$ классов естественно измерять потери множества $U$ через неопределённость распределения классов в нём. Пусть $p_y = |\{x_i \in U:\, y_i = y\}| / |U|$ — доля объектов класса $y$ в $U$ . Энтропия Шеннона этого распределения:

$H(U) = -\sum_{y=1}^{M} p_y \log_2 p_y$

Полагая $Q_0(U) = |U| \cdot H(U)$ , получаем энтропийный критерий прироста информации:

$\mathrm{Gain}_{\mathrm{IG}}(f,t,U) = |U|\, H(U) - |U_L|\, H(U_L) - |U_R|\, H(U_R)$

что после деления на $|U|$ совпадает с классической формулой прироста информации $H(U) - \frac{|U_L|}{|U|} H(U_L) - \frac{|U_R|}{|U|} H(U_R)$ . Данный критерий — частный случай информационного критерия ветвления, обобщающего идею измерения неопределённости распределения классов на произвольные меры разнородности.

Вычислительно более дешёвая аппроксимация энтропии — индекс Джини:

$G(U) = 1 - \sum_{y=1}^{M} p_y^2$

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

$\mathrm{Gain}_{\mathrm{Gini}}(f,t,U) = |U|\, G(U) - |U_L|\, G(U_L) - |U_R|\, G(U_R)$

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

CART — деревья регрессии и классификации

Схема CART (Classification and Regression Trees) конкретизирует общий критерий ветвления для задачи регрессии выбором квадратичной функции потерь $L(y,c) = (y-c)^2$ . Тогда

$Q_0(U) = \min_{c \in \mathbb{R}} \sum_{x_i \in U} (y_i - c)^2$

Минимум по $c$ находится приравниванием производной к нулю: $\frac{\partial}{\partial c}\sum_{x_i\in U}(y_i-c)^2 = -2\sum_{x_i\in U}(y_i-c) = 0$ , откуда оптимальный ответ в листе — среднее значение целевой переменной по объектам, попавшим в него:

$c^*(U) = \frac{1}{|U|} \sum_{x_i \in U} y_i$

а сама величина $Q_0(U)$ при подстановке $c^*(U)$ равна $|U|$ , умноженному на выборочную дисперсию $y$ на множестве $U$ . Критерий ветвления CART для регрессии — частный случай общей формулы $\mathrm{Gain}(f,t,U) = Q_0(U) - Q_0(U_L) - Q_0(U_R)$ с этой квадратичной $Q_0$ : ветвление ищется так, чтобы максимально уменьшить суммарную внутригрупповую дисперсию целевой переменной в дочерних множествах.

Для классификации CART использует критерий Джини (либо энтропийный критерий) в описанном выше виде, а ответом в листе служит класс большинства — частный случай минимизации $Q_0(U)$ при 0-1-функции потерь.

Построенное дерево $T$ с листьями $\mathrm{Leaves}(T)$ , каждому из которых сопоставлена область признакового пространства $R_v \subseteq X$ (множество объектов, достигающих листа $v$ при спуске по дереву) и ответ $c_v$ , реализует кусочно-постоянную функцию:

$a(x) = \sum_{v \in \mathrm{Leaves}(T)} c_v\, [x \in R_v]$

Области $R_v$ образуют разбиение всего признакового пространства $X$ на непересекающиеся прямоугольные (для количественных признаков — задаваемые пересечением полос вдоль осей координат) области, на каждой из которых ответ алгоритма постоянен.

Обрезка дерева (Minimal Cost-Complexity Pruning)

Дерево, построенное по схеме ID3/CART до полной остановки (все листья чистые либо содержат единственный объект), как правило, безупречно приближает обучающую выборку, но обладает избыточно высоким разбросом и плохо обобщается на новые данные — классический случай переобучения по причине чрезмерной сложности модели. Обрезка (pruning) — процедура упрощения уже построенного дерева, устраняющая эту избыточность.

Метод минимальной цено-сложностной обрезки вводит штраф за число листьев дерева и минимизирует комбинированный критерий

$R_{\alpha}(T) = R(T) + \alpha \, |\mathrm{Leaves}(T)|$

где $R(T) = \sum_{v \in \mathrm{Leaves}(T)} Q_0(U_v)$ — суммарные потери дерева $T$ на обучающей выборке, $|\mathrm{Leaves}(T)|$ — число листьев (мера сложности дерева), $\alpha \geq 0$ — параметр компромисса между точностью на обучении и сложностью модели. При $\alpha = 0$ минимум $R_{\alpha}$ достигается на полностью выращенном дереве; с ростом $\alpha$ оптимальное поддерево становится всё компактнее, вплоть до вырождения в единственный корневой лист при достаточно большом $\alpha$ .

Практическая процедура — обрезка слабейшего звена (weakest link pruning): для полностью выращенного дерева $T_0$ последовательно строится цепочка вложенных поддеревьев $T_0 \supset T_1 \supset \dots \supset T_K$ (корень), на каждом шаге удаляется поддерево, для которого увеличение штрафа на единицу сложности минимально компенсирует прирост $R(T)$ . Итоговое значение $\alpha$ (и, соответственно, дерево $T_k$ из построенной цепочки) выбирается по скользящему контролю: для каждого $\alpha$ из цепочки вычисляется ошибка на контрольных блоках, и выбирается поддерево, минимизирующее эту ошибку, а не ошибку на обучающей выборке (которая монотонно растёт с ростом $\alpha$ ).

Представление $a(x) = \sum_{v} c_v [x \in R_v]$ подчёркивает, что обрезанное дерево можно рассматривать как линейный классификатор над индикаторами листьев: индикаторные функции $[x \in R_v]$ играют роль базисных признаков, коэффициенты $c_v$ — роль весов линейной модели, а обрезка дерева — как отбор (регуляризация) числа базисных признаков в этой линейной модели, что делает пронинг концептуально родственным регуляризации в линейных моделях.

Эквивалентность дерева набору конъюнктивных правил

Каждый лист $v$ построенного дерева достигается единственным путём от корня, вдоль которого накапливается последовательность пороговых условий $f_{v_1}(x)\, \sigma_1\, t_{v_1}, \dots, f_{v_k}(x)\, \sigma_k\, t_{v_k}$ , где $\sigma_j \in \{\leq,\, >\}$ — знак сравнения, определяемый тем, в какую сторону (левого или правого потомка) сделан переход на $j$ -м шаге пути, — по одному условию на каждую внутреннюю вершину пути. Конъюнкция этих условий и есть в точности область $R_v$ , приписанная листу:

$[x \in R_v] = \bigwedge_{j=1}^{k} [f_{v_j}(x)\, \sigma_j\, t_{v_j}]$

Таким образом, дерево с $K$ листьями эквивалентно покрывающему набору из $K$ конъюнктивных правил $\varphi_1, \dots, \varphi_K$ , по одному на лист, — эквивалентность в том смысле, что оба представления задают одну и ту же функцию $a(x)$ ; данный факт связывает решающие деревья с общей теорией индукции правил, рассматривающей набор конъюнктивных закономерностей как самостоятельный объект построения, не обязательно порождаемый из древовидной структуры.

Иллюстрация на данных Фишера. Классическая выборка ирисов состоит из 150 объектов трёх видов (Iris setosa, Iris versicolor, Iris virginica) по 50 объектов на класс, описанных четырьмя признаками — длиной и шириной чашелистика, длиной и шириной лепестка^[1]. Ограничившись двумя наиболее информативными признаками — длиной лепестка $f_1$ и шириной лепестка $f_2$ , — алгоритм ID3 на корневой вершине ( $U$ — все 150 объектов, $H(U) = \log_2 3 \approx 1{,}585$ , поскольку классы равномощны) находит разбиение по порогу $f_1 \leq 2{,}45$ : все 50 объектов Iris setosa попадают в левое поддерево ( $H(U_L)=0$ — лист чистый), а 100 объектов Iris versicolor и Iris virginica — в правое ( $H(U_R)=1$ , поскольку в правом поддереве классы поровну). Прирост от этого разбиения:

$\mathrm{Gain} = 150 \cdot 1{,}585 - 50 \cdot 0 - 100 \cdot 1 \approx 237{,}75 - 100 = 137{,}75$

и такое разбиение по построению максимизирует критерий среди всех возможных порогов по $f_1$ и $f_2$ на этом шаге, поскольку сразу выделяет один класс целиком. Левое поддерево, будучи чистым, становится листом. Правое поддерево (100 объектов versicolor/virginica) далее разбивается по порогу ширины лепестка $f_2 \leq 1{,}75$ : объекты с меньшей шириной лепестка преимущественно относятся к Iris versicolor, с большей — к Iris virginica, что даёт второе ветвление с положительным приростом критерия и два новых листа.

Построенное дерево из трёх листьев переписывается как покрывающий набор из трёх конъюнктивных правил:

Правило 1. $[f_1 \leq 2{,}45]$ $\Rightarrow$ Iris setosa.
Правило 2. $[f_1 > 2{,}45] \wedge [f_2 \leq 1{,}75]$ $\Rightarrow$ Iris versicolor.
Правило 3. $[f_1 > 2{,}45] \wedge [f_2 > 1{,}75]$ $\Rightarrow$ Iris virginica.

Каждое правило — конъюнкция условий вдоль пути от корня до соответствующего листа; три правила в совокупности покрывают всё признаковое пространство без пересечений, в точности воспроизводя функцию, вычисляемую деревом.

Объяснимый ИИ (XAI) и интерпретируемость

Понятие интерпретируемости, интуитивно очевидное применительно к решающим деревьям и наборам правил, в литературе по объяснимому искусственному интеллекту распадается на несколько различаемых, хотя и связанных, понятий^[1]^[1].

Interpretability (интерпретируемость в узком смысле) — свойство модели, при котором её внутренний механизм принятия решения может быть непосредственно прослежен человеком: для решающего дерева это буквальный путь от корня до листа, для линейной модели — знаки и величины коэффициентов.
Understandability / Transparency (понятность / прозрачность) — более общее свойство модели быть в целом доступной пониманию как единый объект: можно ли охватить структуру всей модели целиком (для дерева с тремя листьями — да, для леса из тысячи деревьев — практически нет, хотя каждое отдельное дерево в лесу остаётся интерпретируемым в узком смысле).
Explainability (объяснимость) — способность связать конкретный ответ модели, в том числе устроенной как чёрный ящик, с содержательным объяснением постфактум, не обязательно раскрывающим точный внутренний механизм (например, путём приближения локального поведения чёрного ящика интерпретируемой моделью в окрестности конкретного объекта).
Comprehensibility (постижимость) — практическая, ориентированная на конкретного пользователя мера того, насколько объяснение или структура модели укладываются в его когнитивные возможности: правило из трёх условий постижимо для эксперта, правило из пятидесяти условий формально интерпретируемо, но практически непостижимо.

Между точностью модели и перечисленными свойствами, как правило, существует компромисс: расширение семейства моделей (увеличение глубины дерева, переход к ансамблю деревьев, добавление условий в правило) обычно повышает точность аппроксимации зависимости ценой снижения interpretability и understandability, тогда как explainability частично восстанавливается за счёт внешних постфактумных методов объяснения, не меняющих саму (менее интерпретируемую) модель.

Место решающих деревьев среди логических методов

Решающее дерево — не единственный, а лишь наиболее структурированный способ получения набора конъюнктивных правил из данных: как показано выше, любое дерево эквивалентно покрывающему набору правил, но не любой набор правил (в частности, полученный алгоритмами индукции правил со свободным, не древовидным поиском — усечённым поиском в ширину, покрывающими алгоритмами типа CN2 и RIPPER) обязан быть представим деревом. Древовидная структура накладывает на набор правил дополнительное ограничение — общую иерархию признаков и порогов, используемых на всех путях от корня, — тогда как алгоритмы прямой индукции правил ищут каждое правило независимо, что даёт больше гибкости, но требует отдельного механизма согласования правил в единый классификатор (взвешенное голосование).

Второе принципиальное ограничение решающих деревьев — неустойчивость: малое изменение обучающей выборки может привести к выбору другого признака ветвления в корне и, как следствие, к полностью иной структуре дерева, поскольку ошибка на верхних уровнях дерева распространяется на все нижестоящие разбиения. Это свойство высокого разброса единичного дерева — прямое следствие жадной, локально-оптимальной природы алгоритма ID3/CART, не пересматривающего уже принятые решения о ветвлении. Данное ограничение преодолевается композиционными (ансамблевыми) методами: случайный лес снижает разброс усреднением большого числа деревьев, построенных по независимым бутстреп-выборкам и случайным подпространствам признаков, а градиентный бустинг над решающими деревьями последовательно снижает смещение композиции, используя неглубокие деревья как базовые алгоритмы. В обоих случаях платой за повышение точности и устойчивости служит утрата interpretability отдельного дерева — набор из сотен деревьев уже не читается человеком как единая логическая закономерность, что возвращает к обсуждавшемуся выше компромиссу между точностью и объяснимостью модели.

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9B%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%86%D0%B8%D0%B8»

Категории: Методы классификации | Энциклопедия анализа данных | Логические методы классификации | Решающие деревья