Индукция правил

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

Версия от 18:26, 19 июля 2026; Danial Zhumabekov (Обсуждение | вклад)

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

Перейти к: навигация, поиск

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

Содержание

1 Введение
2 Логическая закономерность
3 Требования к правилу
4 Классификатор на основе набора правил
5 Часто используемые семейства правил
6 Алгоритмы генерации и отбора правил
7 Двухкритериальный отбор закономерностей на плоскости (p,n)
8 Зоопарк критериев информативности
- 8.1 Очевидные, но не вполне адекватные критерии
- 8.2 Адекватные, но не очевидные критерии
9 Связь с покрывающими алгоритмами
10 Литература

Введение

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

Альтернативный путь состоит в том, чтобы извлекать логические закономерности не из экспертных знаний, а непосредственно из обучающей выборки $X^{\ell} = (x_i, y_i)_{i=1}^{\ell}$ , где $x_i \in X$ — описание объекта совокупностью признаков, а $y_i \in Y = \{1, \dots, M\}$ — метка класса. Задача индукции правил (rule induction) формулируется как задача автоматического порождения множества логических правил, каждое из которых выделяет содержательно интерпретируемую область признакового пространства, характерную преимущественно для объектов одного класса, и последующего объединения этих правил в классификатор. Данный подход относится к семейству логических методов классификации и занимает промежуточное положение между полностью интерпретируемыми, но негибкими экспертными системами и точными, но малоинтерпретируемыми статистическими моделями.

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

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

Для количественной характеристики правила относительно класса $y$ вводятся величины:

$p = |\{ i:\, y_i = y,\, \varphi(x_i) = 1 \}|$ — число объектов класса $y$ , покрытых правилом;

$n = |\{ i:\, y_i \neq y,\, \varphi(x_i) = 1 \}|$ — число объектов остальных классов, покрытых правилом (число ложных срабатываний).

Дополнительно обозначим через $P$ и $N$ общее число объектов класса $y$ и остальных классов в выборке $X^{\ell}$ соответственно, так что $P + N = \ell$ . Пара $(p, n)$ полностью определяет качество правила $\varphi$ относительно класса $y$ с точностью до того, какие именно объекты покрыты — вся дальнейшая теория информативности правил строится как функция от $(p, n)$ .

Требования к правилу

К закономерности предъявляются два во многом противоречащих друг другу требования.

Интерпретируемость означает, что предикат $\varphi(x)$ должен быть выразим коротким, синтаксически простым логическим выражением от малого числа признаков — как правило, не более трёх-пяти. Правило вида «возраст заёмщика больше 45 лет и сумма кредита превышает шесть месячных доходов» интерпретируемо и допускает содержательную проверку экспертом; правило, использующее взвешенную комбинацию из полусотни признаков, интерпретируемым не является, даже если формально может быть записано в виде предиката. Ограничение сложности правила — необходимое условие того, чтобы результат работы алгоритма мог использоваться как объяснение решения, а не только как чёрный ящик.

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

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

Классификатор на основе набора правил

Отдельное правило $\varphi_k$ , будучи закономерностью класса $y_k$ , само по себе является интерпретируемым бинарным классификатором одного класса: оно относит объект к классу $y_k$ , если покрывает его, и воздерживается от ответа в противном случае. Для получения полноценного классификатора, отвечающего на всём множестве $X$ , строится набор правил $\varphi_1, \dots, \varphi_K$ , покрывающих в совокупности разные классы и разные подобласти признакового пространства, и итоговое решение принимается взвешенным голосованием:

$a(x) = \arg\max_{y \in Y} \sum_{k:\, y_k = y} w_k \, \varphi_k(x)$

где $w_k > 0$ — вес правила $\varphi_k$ , отражающий степень доверия к нему (как правило, монотонно связанный с его информативностью относительно класса $y_k$ ). Такая схема родственна ансамблевым методам голосования и в частных случаях (при определённом выборе весов $w_k$ , пропорциональных $\ln(p_k/n_k)$ ) в точности воспроизводит правило взвешивания слабых классификаторов в алгоритмах бустинга.

Часто используемые семейства правил

Пороговое условие. Простейшее правило — сравнение значения одного признака $f_j(x)$ с порогом $t$ :

$\varphi(x) = [f_j(x) > t]$

где $[\cdot]$ — индикатор истинности условия. Порог $t$ — единственный настраиваемый по данным параметр правила; его оптимальное значение находится перебором по всем различным значениям признака $f_j$ на обучающей выборке с максимизацией выбранного критерия информативности.

Конъюнкция пороговых условий. Более выразительное семейство образуется конъюнкцией нескольких пороговых условий по разным признакам:

$\varphi(x) = \bigwedge_{j \in J} [f_j(x) > t_j]$

где $J$ — небольшое подмножество индексов признаков, задающее сложность правила. Каждое добавление условия в конъюнкцию не увеличивает $p$ (покрытие может только сужаться), но, как правило, уменьшает $n$ — это и есть механизм, за счёт которого удлинение правила повышает его точность ценой снижения полноты.

Синдром. Обобщением конъюнкции и дизъюнкции служит понятие синдрома — правила, истинного при выполнении не менее $d$ из $k$ элементарных условий:

$\varphi(x) = \Big[ \sum_{j=1}^{k} [f_j(x) > t_j] \geq d \Big]$

При $d = k$ синдром вырождается в конъюнкцию, при $d = 1$ — в дизъюнкцию. Синдромные правила типичны для медицинских приложений, где диагноз ставится по совокупности симптомов, ни один из которых не является строго обязательным (например, «не менее трёх из пяти диагностических признаков синдрома присутствуют одновременно»).

Настройка параметров правила — порогов $t_j$ , набора признаков $J$ , глубины конъюнкции и порога $d$ для синдрома — производится путём максимизации критерия информативности (раздел «Зоопарк критериев информативности») на обучающей выборке, зачастую с последующей проверкой устойчивости выбранного правила по скользящему контролю.

Алгоритмы генерации и отбора правил

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

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

Конкретные реализации этой схемы различаются стратегией порождения и отбора кандидатов:

Стохастический локальный поиск. На каждом шаге к текущему правилу применяется случайно выбранная модификация (добавление, удаление или замена условия); модификация принимается, если она улучшает критерий информативности, либо принимается с некоторой вероятностью в духе алгоритмов имитации отжига — это позволяет избегать локальных оптимумов ценой отсутствия гарантии сходимости за фиксированное число шагов.
Генетические (эволюционные) алгоритмы. Правило кодируется хромосомой (например, битовой строкой, задающей включённые условия и их пороги); популяция правил эволюционирует посредством операторов скрещивания и мутации, отбор производится по значению критерия информативности как функции приспособленности.
Усечённый поиск в ширину (beam search). На каждой итерации сохраняется не более $B$ лучших по критерию информативности кандидатов (луч ширины $B$ ), от каждого из них порождаются все допустимые модификации, из объединённого множества снова отбирается $B$ лучших. При $B = 1$ вырождается в жадный поиск в глубину, при $B \to \infty$ приближается к полному перебору.
Поиск в глубину. Жадное наращивание конъюнкции: на каждом шаге к правилу добавляется условие, дающее наибольший прирост критерия информативности, до тех пор пока прирост положителен либо не достигнуто ограничение на сложность правила. Простейший и наиболее быстрый, но наиболее подверженный локальным оптимумам вариант схемы.

Двухкритериальный отбор закономерностей на плоскости (p,n)

Поскольку качество правила определяется одновременно двумя величинами — числом покрытых объектов своего класса $p$ и числом покрытых объектов чужих классов $n$ , — естественным способом сопоставления множества правил-кандидатов служит их визуализация точками на плоскости $(p, n)$ . Каждая точка на этой плоскости соответствует отдельному правилу, полученному на некоторой итерации алгоритма генерации; координата по оси $p$ отражает полноту покрытия целевого класса, координата по оси $n$ — величину ложных срабатываний.

Правило $\varphi$ с координатами $(p, n)$ называется доминируемым правилом $\varphi'$ с координатами $(p', n')$ , если $p' \geq p$ и $n' \leq n$ , причём хотя бы одно из неравенств строгое: правило $\varphi'$ не хуже $\varphi$ одновременно по обоим критериям. Правило называется Парето-оптимальным (недоминируемым), если не существует другого правила из рассматриваемого множества, доминирующего над ним. Множество всех Парето-оптимальных правил образует Парето-фронт — на плоскости $(p, n)$ он визуализируется ломаной, идущей из области больших $n$ при больших $p$ к области малых $n$ при малых $p$ , левее и выше которой (в терминах «больше $p$ , меньше $n$ ») не лежит ни одна точка выборки правил. Формально это соответствует понятию Парето-оптимальности в задаче двухкритериальной оптимизации $p \to \max,\, n \to \min$ .

Практическая ценность этого построения для задачи кредитного скоринга на German Credit состоит в следующем: множество закономерностей, порождённых алгоритмом генерации (например, всех конъюнкций длины до трёх по признакам «срок кредита», «цель кредита», «наличие поручителя», «тип жилья», «кредитная история»), наносится на плоскость $(p, n)$ , где класс $y$ — «заёмщик не вернёт кредит». Незакрашенная (выделенная) точка на таком графике — это правило, которое не хуже никакого другого правила на графике ни по $p$ , ни по $n$ одновременно, то есть принадлежит Парето-фронту. Правила, лежащие строго правее и ниже фронта (закрашенные точки), доминируются хотя бы одним фронтовым правилом и, как следствие, могут быть исключены из дальнейшего рассмотрения без потери качества классификатора: для любой такой точки найдётся правило Парето-фронта, дающее не меньшее $p$ при не большем $n$ . Итоговый набор правил для классификатора взвешенного голосования формируется, как правило, именно из точек Парето-фронта либо их окрестности, что заменяет скалярную оптимизацию единственного критерия информативности на явный анализ компромисса между полнотой и точностью.

Зоопарк критериев информативности

Отбор Парето-оптимальных правил сужает множество кандидатов, но не даёт единственного ответа: точки фронта по-прежнему нужно ранжировать или взвешивать для построения итогового классификатора. Для этого вводится скалярный критерий информативности $I(p, n)$ , агрегирующий пару $(p, n)$ в одно число. Исторически сложился широкий набор таких критериев — «зоопарк», — часть которых интуитивно очевидна, но при ближайшем рассмотрении оказывается не вполне адекватной, тогда как другая часть менее очевидна, но обладает лучшими теоретическими свойствами.

Очевидные, но не вполне адекватные критерии

Точность (precision) — доля объектов целевого класса среди всех покрытых правилом объектов:

$I_{\mathrm{prec}}(p, n) = \frac{p}{p + n}$

Недостаток: точность не учитывает абсолютный объём покрытия. Правило, покрывающее один-единственный объект своего класса и ни одного чужого ( $p=1, n=0$ ), формально имеет точность $1$ — максимально возможную, — но статистически ненадёжно и практически бесполезно ввиду ничтожной полноты.

Полнота (recall) — доля покрытых объектов целевого класса среди всех объектов этого класса в выборке:

$I_{\mathrm{rec}}(p, n) = \frac{p}{P}$

Недостаток: критерий полностью игнорирует $n$ и, тем самым, максимизируется тривиальным правилом $\varphi(x) \equiv 1$ , покрывающим вообще все объекты и не несущим никакой дискриминирующей информации.

Относительная точность (weighted relative accuracy) частично устраняет эти недостатки, сопоставляя долю целевого класса среди покрытых объектов с его долей во всей выборке:

$I_{\mathrm{wra}}(p, n) = \frac{p+n}{\ell} \left( \frac{p}{p+n} - \frac{P}{\ell} \right)$

Множитель $(p+n)/\ell$ взвешивает превышение точности над базовой частотой класса объёмом покрытия, штрафуя тем самым правила с чрезмерно узким охватом. Однако критерий остаётся линейным по $p$ и $n$ при фиксированном объёме покрытия и не отражает убывающую предельную ценность дополнительных объектов, характерную для статистически более обоснованных критериев.

Адекватные, но не очевидные критерии

Энтропийный критерий прироста информации основан на том же принципе, что и критерии ветвления в построении решающих деревьев: покрытие правилом рассматривается как разбиение выборки на две части (покрытую и непокрытую), и критерием служит уменьшение энтропии распределения классов при этом разбиении. Пусть $H(q) = -q \log_2 q - (1-q)\log_2(1-q)$ — энтропия Шеннона бинарного распределения с параметром $q$ . Тогда прирост информации от правила $\varphi$ равен

$I_{\mathrm{IG}}(p, n) = H\!\left(\frac{P}{\ell}\right) - \frac{p+n}{\ell}\, H\!\left(\frac{p}{p+n}\right) - \frac{\ell-p-n}{\ell}\, H\!\left(\frac{P-p}{\ell-p-n}\right)$

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

Критерий Джини — вычислительно более дешёвая аппроксимация энтропийного критерия, использующая индекс Джини $G(q) = 2q(1-q)$ вместо энтропии Шеннона $H(q)$ : обе функции достигают максимума в точке $q=1/2$ , обращаются в нуль на концах отрезка $[0,1]$ и являются вогнутыми, поэтому критерий Джини

$I_{\mathrm{Gini}}(p, n) = G\!\left(\frac{P}{\ell}\right) - \frac{p+n}{\ell}\, G\!\left(\frac{p}{p+n}\right) - \frac{\ell-p-n}{\ell}\, G\!\left(\frac{P-p}{\ell-p-n}\right)$

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

Критерий бустинга с квадратными корнями возникает из анализа экспоненциальной функции потерь, минимизируемой в схемах бустинга при подборе очередного слабого классификатора и его веса. Если правило $\varphi$ используется как слабый классификатор с оптимальным (по экспоненциальной функции потерь) весом $w = \frac{1}{2} \ln(p/n)$ , то соответствующее уменьшение экспоненциальной ошибки оказывается монотонной функцией от величины

$I_{\mathrm{boost}}(p, n) = \sqrt{p} - \sqrt{n}$

Критерий не следует напрямую из содержательных соображений о точности или полноте (в этом смысле он не очевиден), однако он теоретически обоснован как критерий, оптимальный именно для того способа агрегирования правил взвешенным голосованием, который описан в разделе «Классификатор на основе набора правил», и согласован с весами $w_k$ ансамбля^[1].

Сопоставление критериев информативности правила
Критерий	Формула	Учитывает объём покрытия	Согласован с ветвлением дерева	Согласован с весами бустинга
Точность	$p/(p+n)$	нет	нет	нет
Полнота	$p/P$	нет (игнорирует $n$ )	нет	нет
Относительная точность	$\frac{p+n}{\ell}\big(\frac{p}{p+n}-\frac{P}{\ell}\big)$	частично (линейно)	нет	нет
Прирост информации (энтропия)	разность энтропий Шеннона	да	да	нет
Критерий Джини	разность индексов Джини	да	да (аппроксимация)	нет
Критерий бустинга	$\sqrt{p}-\sqrt{n}$	да	нет	да

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

Связь с покрывающими алгоритмами

Отбор Парето-оптимальных правил по одному из критериев информативности решает задачу поиска отдельной закономерности, но не задаёт напрямую способ построения набора правил, совместно покрывающего всю обучающую выборку без чрезмерной избыточности. Эту задачу решает семейство покрывающих алгоритмов (covering algorithms, separate-and-conquer): правила извлекаются из выборки последовательно, по одному, причём после извлечения очередного правила $\varphi_k$ все покрытые им объекты удаляются из обучающей выборки, и поиск следующего правила $\varphi_{k+1}$ производится уже на оставшихся, ещё не покрытых объектах. Процедура завершается, когда все объекты целевого класса покрыты (либо когда лучший из вновь найденных кандидатов не проходит порог по критерию информативности), после чего описанная схема повторяется для следующего класса.

Такая стратегия «разделяй и властвуй» (separate: выделить покрытые объекты — conquer: исключить их и продолжить на остатке) лежит в основе классических алгоритмов индукции правил:

CN2 строит правила поиском в ширину (beam search) по критерию, близкому к энтропийному приросту информации, с последующей статистической проверкой значимости правила и удалением покрытых объектов на каждом шаге^[1].
RIPPER (Repeated Incremental Pruning to Produce Error Reduction) дополняет покрывающую схему этапом отсечения (pruning) построенного правила по отложенной контрольной подвыборке для снижения переобучения, а также последующей глобальной оптимизацией всего набора правил после первичного покрывающего прохода^[1].

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

Литература

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D1%83%D0%BA%D1%86%D0%B8%D1%8F_%D0%BF%D1%80%D0%B0%D0%B2%D0%B8%D0%BB»

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