Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

{{well|Статья написана с использованием LLM '''OpenAI GPT-5''' и проверена участником [[Участник:Platon Usaсhev|Platon Usaсhev]] 11:19, 16 июня 2026 (MSD)}} '''Решающий список''' (англ. ''decision list'', ''rule list'') — интерпретируемая модель [[классификация|классификации]], задаваемая упорядоченной последовательностью правил вида «если условие выполнено, то выдать ответ». Правила просматриваются сверху вниз, и применяется первое правило, условие которого истинно для данного объекта. Последнее правило обычно является правилом по умолчанию и покрывает все оставшиеся объекты. Решающие списки занимают промежуточное положение между [[решающее дерево|решающими деревьями]] и наборами логических правил. Как и дерево, решающий список задаёт кусочно-постоянную модель на пространстве объектов; как и правило экспертной системы, каждая его строка может быть прочитана человеком. Главная особенность состоит в упорядоченности: одно и то же множество правил при разном порядке может задавать разные классификаторы. == Определение == Пусть <tex>X</tex> — пространство объектов, <tex>Y</tex> — множество классов. Решающий список длины <tex>K</tex> имеет вид ::<tex>(c_1,a_1),(c_2,a_2),\ldots,(c_K,a_K),</tex> где <tex>c_j:X\to\{0,1\}</tex> — условие применимости правила, а <tex>a_j\in Y</tex> — ответ правила. Последнее условие часто полагают тождественно истинным: ::<tex>c_K(x)\equiv 1,</tex> чтобы классификатор был определён на всех объектах. Для объекта <tex>x</tex> находится индекс первого сработавшего правила ::<tex>\tau(x)=\min\{j:c_j(x)=1\},</tex> и ответ равен ::<tex>f(x)=a_{\tau(x)}.</tex> В бинарных задачах условия часто строятся как литералы или конъюнкции литералов: ::<tex>c_j(x)=\ell_{j1}(x)\wedge\cdots\wedge \ell_{jr_j}(x),</tex> где литерал — это простое условие на один признак, например <tex>x_s=1</tex>, <tex>x_s=0</tex>, <tex>x_s\leq t</tex> или <tex>x_s\in A</tex>. В прикладных задачах условия могут быть и более сложными: регулярные выражения для текстов, пороговые правила для числовых признаков, проверки принадлежности категории или медицинские критерии. == Пример == Решающий список для бинарной классификации кредитных заявок может выглядеть так: * если у клиента была просрочка более 90 дней, отказать; * иначе если подтверждённый доход выше заданного порога и долговая нагрузка мала, одобрить; * иначе если кредитная история короче шести месяцев, отказать; * иначе одобрить с базовым решением. Здесь второе правило применяется только к объектам, не покрытым первым. Третье правило применяется только к объектам, не покрытым первыми двумя. Поэтому каждое правило следует читать вместе с неявным условием «если ни одно более раннее правило не сработало». В этом состоит отличие решающего списка от неупорядоченного набора правил. В наборе правил может возникнуть конфликт: несколько правил дают разные ответы. В решающем списке конфликт разрешается порядком. == Связь с решающими деревьями == Решающий список можно представить как вырожденное решающее дерево, в котором на каждом внутреннем узле одна ветвь ведёт к листу с ответом, а другая — к следующему правилу. Поэтому решающий список иногда называют деревом с одной длинной цепочкой проверок. Преимущество такой структуры — простота чтения: пользователь проходит список сверху вниз и видит, почему выбран ответ. Недостаток — меньшая симметрия по сравнению с деревом. В дереве положительный и отрицательный исходы проверки могут вести к двум содержательным поддеревьям, а в решающем списке один исход обычно завершает классификацию, другой передаёт объект дальше. Любое решающее дерево конечной глубины можно развернуть в список правил, соответствующих путям от корня к листьям. Однако такой список может быть длинным, а правила могут содержать много условий. Обратно, решающий список всегда легко переводится в дерево цепочечной формы. == Обучение решающего списка == Задача обучения состоит в выборе условий, ответов и порядка правил по обучающей выборке ::<tex>S=\{(x_i,y_i)\}_{i=1}^{m}.</tex> Естественный критерий качества сочетает ошибку классификации и сложность списка: ::<tex>Q(f)=\frac{1}{m}\sum_{i=1}^{m}[f(x_i)\ne y_i]+\lambda K+\mu\sum_{j=1}^{K}r_j,</tex> где <tex>K</tex> — число правил, <tex>r_j</tex> — число элементарных условий в правиле, <tex>\lambda</tex> и <tex>\mu</tex> задают штраф за длину и сложность. Минимизация такого критерия в общем случае трудна, поэтому на практике используют жадные, эвристические, байесовские или целочисленные методы оптимизации. Простая жадная схема напоминает последовательное покрытие: * построить множество кандидатов в правила; * выбрать правило, хорошо классифицирующее часть ещё не покрытых объектов; * добавить его в конец списка; * удалить или пометить покрытые объекты; * повторять, пока оставшиеся объекты не будут покрыты правилом по умолчанию. Критерий выбора правила может учитывать точность, покрытие, прирост информационного критерия, уменьшение ошибки или статистическую значимость. После построения список часто упрощают: удаляют слабые условия, объединяют соседние правила с одинаковым ответом, обрезают хвост, если он ухудшает качество на контрольной выборке. == Классические и байесовские варианты == В классической теории обучения рассматривались <tex>k</tex>-решающие списки, где каждое условие является конъюнкцией не более чем <tex>k</tex> литералов. При фиксированном <tex>k</tex> такое ограничение делает класс моделей более управляемым и позволяет строить алгоритмы обучения с теоретическими гарантиями. Эта постановка была введена Р. Ривестом как один из ранних формальных классов интерпретируемых булевых моделей. В современных прикладных работах популярны байесовские решающие списки. В них список правил рассматривается как случайный объект: задаётся априорное распределение на длину списка, условия и параметры ответов. Например, для бинарной классификации можно положить ::<tex>P(y=1| x)=\theta_{\tau(x)},</tex> где <tex>\theta_j</tex> — вероятность положительного класса в <tex>j</tex>-м правиле. Априорные распределения выбирают так, чтобы поощрять короткие списки и простые условия. Затем ищут наиболее вероятный список или усредняют прогнозы по апостериорному распределению. Байесовский подход удобен, когда интерпретируемость важна не меньше точности: длина списка и число условий задаются как часть модели, а не как необязательная постобработка. Кроме того, вероятностическая форма позволяет оценивать неопределённость ответов правил. == Интерпретируемость == Решающий список часто воспринимается как одна из наиболее понятных форм классификатора. Для отдельного объекта объяснение состоит из номера первого сработавшего правила и его условия. Для всей модели можно прочитать список сверху вниз и увидеть приоритеты принятия решений. Однако интерпретируемость решающего списка не гарантируется автоматически. Важны: * длина списка; * число условий в каждом правиле; * понятность признаков и порогов; * стабильность списка при изменении обучающей выборки; * доля объектов, покрываемых каждым правилом; * качество правила по отдельным группам объектов. Ранние правила могут «затенять» поздние: если объект покрыт верхним правилом, нижние правила уже не рассматриваются. Поэтому каждое правило имеет смысл только в контексте всех предыдущих правил. Это делает решающий список компактным, но иногда усложняет локальную интерпретацию нижних строк. == Сравнение с близкими моделями == Решающий список отличается от нескольких похожих классов моделей. * В [[решающее дерево|решающем дереве]] объект проходит по ветвям дерева; в решающем списке он проходит по линейному порядку правил. * В неупорядоченном наборе правил несколько правил могут сработать одновременно; в решающем списке применяется только первое. * В [[линейный классификатор|линейной модели]] вклад признаков суммируется, а в решающем списке решение принимается локально одним правилом. * В [[случайный лес|случайном лесе]] и [[градиентный бустинг|градиентном бустинге]] точность часто выше, но итоговая модель обычно сложнее для прямого чтения человеком. * В экспертных системах правила могут задаваться вручную; решающий список обычно обучается по данным и оптимизируется по статистическому критерию. Таким образом, решающий список полезен там, где нужен компромисс между точностью, проверяемостью и простотой объяснения. == Практическое использование == Решающие списки применяют в медицинской диагностике, кредитном скоринге, аудитах риска, текстовой классификации, обнаружении мошенничества, экспертных системах и задачах, где решение должно быть объяснимым для человека. Их удобно использовать в регламентированных областях, потому что каждое правило можно обсудить с предметным экспертом и при необходимости переписать в форму инструкции. При построении модели обычно проверяют: * качество на независимой выборке; * длину списка и среднее число проверяемых правил на объект; * точность и покрытие каждого правила; * устойчивость порядка правил; * поведение на редких группах объектов; * влияние дискретизации числовых признаков; * наличие правил, использующих нежелательные или запрещённые признаки. Если решающий список используется как объяснимая модель, важно публиковать не только общую точность, но и статистику по отдельным правилам. Правило, покрывающее мало объектов, может выглядеть убедительно, но быть результатом случайного совпадения. == Ограничения == Главное ограничение решающих списков — зависимость от порядка правил. Небольшое изменение верхнего правила может изменить распределение объектов по всем последующим правилам. Поэтому жадные алгоритмы иногда дают нестабильные списки. Другие ограничения: * пространство возможных правил быстро растёт с числом признаков; * редкие, но точные правила могут переобучаться; * непрерывные признаки требуют выбора порогов или дискретизации; * длинные списки теряют интерпретируемость; * простые списки могут плохо описывать задачи со сложными симметричными взаимодействиями признаков; * вероятностная калибровка ответов может быть хуже, чем у специально калиброванных моделей. На практике решающие списки часто сравнивают с деревьями решений, логистической регрессией, градиентным бустингом и случайным лесом. Если выигрыш сложных моделей невелик, короткий решающий список может быть предпочтительнее из-за прозрачности и удобства внедрения. == См. также == * [[Решающее дерево]] * [[Классификация]] * [[Алгоритмическая композиция]] * [[Интерпретируемость модели]] * [[Отбор признаков]] * [[Регуляризация]] * [[Случайный лес]] * [[Градиентный бустинг]] == Литература == * ''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. [[Категория:Машинное обучение]] [[Категория:Классификация]] [[Категория:Интерпретируемое машинное обучение]] [[Категория:Энциклопедия анализа данных]]

• Шаблон:Mbox
• Шаблон:Well

Возврат к странице Решающий список.