Решающий список

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

Версия от 07:19, 16 июня 2026; Platon Usaсhev (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM OpenAI GPT-5 и проверена участником Platon Usaсhev 11:19, 16 июня 2026 (MSD)

Решающий список (англ. decision list, rule list) — интерпретируемая модель классификации, задаваемая упорядоченной последовательностью правил вида «если условие выполнено, то выдать ответ». Правила просматриваются сверху вниз, и применяется первое правило, условие которого истинно для данного объекта. Последнее правило обычно является правилом по умолчанию и покрывает все оставшиеся объекты.

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

Определение

Пусть $X$ — пространство объектов, $Y$ — множество классов. Решающий список длины $K$ имеет вид

$(c_1,a_1),(c_2,a_2),\ldots,(c_K,a_K),$

где $c_j:X\to\{0,1\}$ — условие применимости правила, а $a_j\in Y$ — ответ правила. Последнее условие часто полагают тождественно истинным:

$c_K(x)\equiv 1,$

чтобы классификатор был определён на всех объектах. Для объекта $x$ находится индекс первого сработавшего правила

$\tau(x)=\min\{j:c_j(x)=1\},$

и ответ равен

$f(x)=a_{\tau(x)}.$

В бинарных задачах условия часто строятся как литералы или конъюнкции литералов:

$c_j(x)=\ell_{j1}(x)\wedge\cdots\wedge \ell_{jr_j}(x),$

где литерал — это простое условие на один признак, например $x_s=1$ , $x_s=0$ , $x_s\leq t$ или $x_s\in A$ . В прикладных задачах условия могут быть и более сложными: регулярные выражения для текстов, пороговые правила для числовых признаков, проверки принадлежности категории или медицинские критерии.

Пример

Решающий список для бинарной классификации кредитных заявок может выглядеть так:

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

Здесь второе правило применяется только к объектам, не покрытым первым. Третье правило применяется только к объектам, не покрытым первыми двумя. Поэтому каждое правило следует читать вместе с неявным условием «если ни одно более раннее правило не сработало».

В этом состоит отличие решающего списка от неупорядоченного набора правил. В наборе правил может возникнуть конфликт: несколько правил дают разные ответы. В решающем списке конфликт разрешается порядком.

Связь с решающими деревьями

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

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

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

Обучение решающего списка

Задача обучения состоит в выборе условий, ответов и порядка правил по обучающей выборке

$S=\{(x_i,y_i)\}_{i=1}^{m}.$

Естественный критерий качества сочетает ошибку классификации и сложность списка:

$Q(f)=\frac{1}{m}\sum_{i=1}^{m}[f(x_i)\ne y_i]+\lambda K+\mu\sum_{j=1}^{K}r_j,$

где $K$ — число правил, $r_j$ — число элементарных условий в правиле, $\lambda$ и $\mu$ задают штраф за длину и сложность. Минимизация такого критерия в общем случае трудна, поэтому на практике используют жадные, эвристические, байесовские или целочисленные методы оптимизации.

Простая жадная схема напоминает последовательное покрытие:

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

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

Классические и байесовские варианты

В классической теории обучения рассматривались $k$ -решающие списки, где каждое условие является конъюнкцией не более чем $k$ литералов. При фиксированном $k$ такое ограничение делает класс моделей более управляемым и позволяет строить алгоритмы обучения с теоретическими гарантиями. Эта постановка была введена Р. Ривестом как один из ранних формальных классов интерпретируемых булевых моделей.

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

$P(y=1| x)=\theta_{\tau(x)},$

где $\theta_j$ — вероятность положительного класса в $j$ -м правиле. Априорные распределения выбирают так, чтобы поощрять короткие списки и простые условия. Затем ищут наиболее вероятный список или усредняют прогнозы по апостериорному распределению.

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

Интерпретируемость

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

Однако интерпретируемость решающего списка не гарантируется автоматически. Важны:

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

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

Сравнение с близкими моделями

Решающий список отличается от нескольких похожих классов моделей.

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

Таким образом, решающий список полезен там, где нужен компромисс между точностью, проверяемостью и простотой объяснения.

Практическое использование

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

При построении модели обычно проверяют:

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

Если решающий список используется как объяснимая модель, важно публиковать не только общую точность, но и статистику по отдельным правилам. Правило, покрывающее мало объектов, может выглядеть убедительно, но быть результатом случайного совпадения.

Ограничения

Главное ограничение решающих списков — зависимость от порядка правил. Небольшое изменение верхнего правила может изменить распределение объектов по всем последующим правилам. Поэтому жадные алгоритмы иногда дают нестабильные списки.

Другие ограничения:

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

На практике решающие списки часто сравнивают с деревьями решений, логистической регрессией, градиентным бустингом и случайным лесом. Если выигрыш сложных моделей невелик, короткий решающий список может быть предпочтительнее из-за прозрачности и удобства внедрения.

См. также

Литература

Rivest R. L. Learning decision lists // Machine Learning. — 1987. — Vol. 2. — P. 229–246.
Clark P., Niblett T. The CN2 induction algorithm // Machine Learning. — 1989. — Vol. 3. — P. 261–283.
Cohen W. W. Fast effective rule induction // Proceedings of the 12th International Conference on Machine Learning. — 1995. — P. 115–123.
Letham B., Rudin C., McCormick T. H., Madigan D. Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model // Annals of Applied Statistics. — 2015. — Vol. 9, No. 3. — P. 1350–1371.
Angelino E., Larus-Stone N., Alabi D., Seltzer M., Rudin C. Learning certifiably optimal rule lists for categorical data // Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. — 2017. — P. 35–44.
Friedman J. H., Popescu B. E. Predictive learning via rule ensembles // The Annals of Applied Statistics. — 2008. — Vol. 2, No. 3. — P. 916–954.
Molnar C. Interpretable Machine Learning. — 2nd ed. — 2022.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B5%D1%88%D0%B0%D1%8E%D1%89%D0%B8%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA»

Категории: Машинное обучение | Классификация | Интерпретируемое машинное обучение | Энциклопедия анализа данных